Finite Automata and Application to Cryptography (eBook)

Renji Tao (Autor)

eBook Download: PDF

2009
350 Seiten
Springer Berlin (Verlag)
9783540782575 (ISBN)

Infos

Finite Automata and Application to Cryptography mainly deals with the invertibility theory of finite automata and its application to cryptography. In addition, autonomous finite automata and Latin arrays, which are relative to the canonical form for one-key cryptosystems based on finite automata, are also discussed.

Finite automata are regarded as a natural model for ciphers. The Ra Rb transformation method is introduced to deal with the structure problem of such automata; then public key cryptosystems based on finite automata and a canonical form for one-key ciphers implementable by finite automata with bounded-error-propagation and without data expansion are proposed.

The book may be used as a reference for computer science and mathematics majors, including seniors and graduate students.

Renji Tao is a Professor at the Institute of Software, Chinese Academy of Sciences, Beijing.

 

 

Inhalt

Foreword 3
Preface 5
Contents 8
1. Introduction 11
1.1 Preliminaries 12
1.2 Definitions of Finite Automata 16
1.3 Linear Finite Automata 26
1.4 Concepts on Invertibility 36
1.5 Error Propagation and Feedforward Invertibility 44
1.6 Labelled Trees as States of Finite Automata 51
Historical Notes 55
2. Mutual Invertibility and Search 57
2.1 Minimal Output Weight and Input Set 58
2.2 Mutual Invertibility of Finite Automata 64
2.3 Find Input by Search 66
Historical Notes 86
3. Ra Rb Transformation Method 87
3.1 Sufficient Conditions and Inversion 88
3.2 Generation of Finite Automata with Invertibility 96
3.3 Invertibility of Quasi-Linear Finite Automata 105
Historical Notes 117
4. Relations Between Transformations 119
4.1 Relations Between Ra Rb Transformations 120
4.2 Composition of Ra Rb Transformations 125
4.3 Reduced Echelon Matrix 138
4.4 Canonical Diagonal Matrix Polynomial 142
Historical Notes 162
5. Structure of Feedforward Inverses 163
5.1 A Decision Criterion 164
5.2 Delay Free 167
5.3 One Step Delay 170
5.4 Two Step Delay 175
Historical Notes 185
6. Some Topics on Structure Problem 187
6.1 Some Variants of Finite Automata 188
6.2 Inverses of a Finite Automaton 195
6.3 Original Inverses of a Finite Automaton 208
6.4 Weak Inverses of a Finite Automaton 211
6.5 Original Weak Inverses of a Finite Automaton 215
6.6 Weak Inverses with Bounded Error Propagation of a Finite Automaton 218
Historical Notes 224
7. Linear Autonomous Finite Automata 225
7.1 Binomial Coefficient 226
7.2 Root Representation 234
7.3 Translation and Period 255
7.4 Linearization 264
7.5 Decimation 275
Historical Notes 281
8. One Key Cryptosystems and Latin Arrays 283
8.1 Canonical Form for Finite Automaton One Key Cryptosystems 284
8.2 Latin Arrays 289
8.3 Linearly Independent Latin Arrays 337
Historical Notes 356
9. Finite Automaton Public Key Cryptosystems 357
9.1 Theoretical Fundamentals 358
9.2 Basic Algorithm 361
9.3 An Example of FAPKC 366
9.4 On Weak Keys 372
9.5 Security 374
9.6 Generalized Algorithms 382
Historical Notes 402
References 405
Index 413

Produkt-Details

• Erscheint lt. Verlag: 8.3.2009
• Zusatzinfo: 350 p. 2 illus.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Informatik ► Netzwerke ► Sicherheit / Firewall
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• Schlagworte: cryptography • Cryptosystems • digital signature • FAPKC • Finite • Finite Automata • invertibility theory • Latin array • Mathematics • TUP
• ISBN-13: 9783540782575 / 9783540782575