Stream Ciphers and Number Theory (eBook)

Cover 1
Contents 10
Preface 8
Chapter 1. Introduction 16
1.1 Applications of Number Theory 16
1.2 An Outline of this Book 20
Chapter 2. Stream Ciphers 26
2.1 Stream Cipher Systems 26
2.2 Some Keystream Generators 36
2.3 Cryptographic Aspects of Sequences 40
2.4 Harmony of Binary NSGs 51
2.5 Security and Attacks 55
Chapter 3. Primes. Primitive Roots and Sequences 58
3.1 Cyclotomic Polynomials 58
3.2 Two Basic Problems from Stream Ciphers 59
3.3 A Basic Theorem and Main Bridge 62
3.4 Primes. Primitive Roots and Binary Sequences 65
3.5 Primes. Primitive Roots and Ternary Sequences 70
3.6 Primes. Negord and Sequences 73
3.7 Prime Powers. Primitive Roots and Sequences 75
3.8 Prime Products and Sequences 77
3.9 On Cryptographic Primitive Roots 80
3.10 Linear Complexity of Sequences over Zm 82
3.11 Period and its Cryptographic Importance 90
Chapter 4. Cyclotomy and Cryptographic Functions 92
4.1 Cyclotomic Numbers 92
4.2 Cyclotomy and Cryptography 94
4.3 Cryptographic Functions from Zp, to Zd 97
4.4 Cryptographic Functions from Zpq to Zd 108
4.5 Cryptographic Functions from Zp2 to Z2 119
4.6 Cryptographic Functions Defined on GF(pm) 122
4.7 The Origin of Cyclotomic Numbers 122
Chapter 5. Special Primes and Sequences 128
5.1 Sophie Germain Primes and Sequences 128
5.2 Tchebychef Primes and Sequences 132
5.3 Other Primes of Form k x 2n + 1 and Sequences 134
5.4 Primes of Form (an - l)/(a - 1) and Sequences 138
5.5 n! ± 1 and p# ± 1 Primes and Sequences 142
5.6 Twin Primes and Sequences over GF(2) 144
5.7 Twin Primes and Sequences over GF(3) 148
5.8 Other Special Primes and Sequences 149
5.9 Prime Distributions and their Significance 149
5.10 Primes for Stream Ciphers and for RSA 150
Chapter 6. Difference Sets and Cryptographic Functions 154
6.1 Rudiments of Difference Sets 154
6.2 Difference Sets and Autocorrelation Functions 157
6.3 Difference Sets and Nonlinearity 158
6.4 Difference Sets and Information Stability 160
6.5 Difference Sets and Linear Approximation 162
6.6 Almost Difference Sets 164
6.7 Almost Difference Sets and Autocorrelation Functions 168
6.8 Almost Difference Sets, Nonlinearity and Approximation 169
6.9 Summary 169
Chapter 7. Difference Sets and Sequences 172
7.1 The NSG Realization of Sequences 172
7.2 Differential Analysis of Sequences 174
7.3 Linear Complexity of DSC (ADSC) Sequences 176
7.4 Barker Sequences 179
Chapter 8. Binary Cyclotomic Generators 182
8.1 Cyclotomic Generator of Order 2k 182
8.2 Two-Prime Generator of Order 2 185
8.3 Two-Prime Generator of Order 4 197
8.4 Prime-Square Generator 198
8.5 Implementation and Performance 210
8.6 A Summary of Binary Cyclotomic Generators 211
Chapter 9. Analysis of Cyclotomic Generators of Order 2 214
9.1 Crosscorrelation Property 215
9.2 Decimation Property 216
9.3 Linear Complexity 216
9.4 Security against a Decision Tree Attack 220
9.5 Sums of DSC Sequences 234
Chapter 10. Nonbinary Cyclotomic Generators 238
10.1 The rth-Order Cyclotomic Generator 238
10.2 Linear Complexity 239
10.3 Autocorrelation Property 241
10.4 Decimation Property 243
10.5 Ideas Behind the Cyclotomic Generators 243
Chapter 11. Generators Based on Permutations 246
11.1 The Cryptographic Idea 246
11.2 Permutations on Finite Fields 248
11.3 A Generator Based on Inverse Permutations 249
11.4 Binary Generators and Permutations of GF(2n) 251
11.5 Cyclic-Key Generators and their Problems 266
11.6 A Generator Based on Permutations of Zm 271
Chapter 12. Quadratic Partitions and Cryptography 280
12.1 Quadratic Partition and Cryptography 281
12.2 p = x 2 + y2 and p = x2 + 4y2 282
12.3 p = x2 + 2y2 and p = x2 + 3y2 289
12.4 p = x2 + ny2 and Quadratic Reciprocity 290
12.5 p = x2 + 7y2 and Quadratic Forms 290
12.6 p = x 2 + 15y2 and Genus Theory 294
12.7 p = x 2 + ny2 and Class Field Theory 296
12.8 Other Cryptographic Quadratic Partitions 298
Chapter 13. Group Characters and Cryptography 301
13.1 Group Characters 301
13.2 Field Characters and Cryptography 303
13.3 The Nonlinearity of Characters 313
13.4 Ring Characters and Cryptography 315
13.5 Group Characters and Cyclotomic Numbers 316
Chapter 14. P-Adic Numbers, Class Numbers and Sequences 321
14.1 The 2-Adic Value and 2-Adic Expansion 321
14.2 A Fast Algorithm for the 2-Adic Expansion 327
14.3 The Arithmetic of Q[2] and Z[2] 327
14.4 Feedback Shift Registers with Carry 332
14.5 Analysis and Synthesis of FCSRs 334
14.6 The 2-Adic Span and 2-RA Algorithm 340
14.7 Some Properties of FCSR Sequences 349
14.8 Blum-Blum-Shub Sequences & Class Numbers
Chapter 15. Prime Ciphering Algorithms 361
15.1 Prime-32: A Description 361
15.2 Theoretical Results about Prime-32 366
15.3 Security Arguments 368
15.4 Performance of Prime-32 371
15.5 Prime-32 with a 192-Bit Key 371
15.6 Prime-64 371
Chapter 16. Cryptographic Problems and Philosophies 373
16.1 Nonlinearity and Linearity 373
16.2 Stability and Instability 376
16.3 Localness and Globalness 381
16.4 Goodness and Badness 383
16.5 About Good plus Good 384
16.6 About Good plus Bad 385
16.7 About Bad plus Good 386
16.8 Hardware and Software Model Complexity 387
Appendices 389
Appendix A. More About Cyclotomic Numbers 389
Appendix B. Cyclotomic Formulae of Orders 6, 8 and 10 397
Appendix C. Finding Practical Primes 403
Appendix D. List of Research Problems 405
Appendix E. Exercises 407
Appendix F. List of Mathematical Symbols 413
Bibliography 415
Index 443