The Laws of
Cryptography
with Java Code
by Neal R. Wagner
Permission is granted to retrieve a single electronic copy of this book for personal use, but the
permission does not extend to printing a copy of the book or to making a copy, electronic or in
any other form, for any other than personal use.
Table of Contents
Parts and Chapters
Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii
I. Preliminaries . . . . . . . . . . . . . . . . . . . . . 2
1. Cryptographers’ Favorites . . . . . . . . . . . . . . . . . . 3
2. Cryptographers’ Favorite Algorithms . . . . . . . . . . . . 14
II. Coding and Information Theory . . . . . . . . . . . . 22
3. Coding and Information Theory . . . . . . . . . . . . . . 23
4. Visualizing Channel Capacity . . . . . . . . . . . . . . . 31
5. The Huffman Code for Compression . . . . . . . . . . . . 35
6. The Hamming Code for Error Correction . . . . . . . . . . 44
7. Coping with Decimal Numbers . . . . . . . . . . . . . . . 48
8. Verhoeff’s Decimal Error Detection . . . . . . . . . . . . . 54
III. Introduction to Cryptography . . . . . . . . . . . . . 60
9. Cryptograms and Terminology . . . . . . . . . . . . . . . 61
10. The One-Time Pad . . . . . . . . . . . . . . . . . . . . 66
11. Conventional Block Cipher Cryptosystems . . . . . . . . . . 70
??. Conventional Stream Cipher Cryptosystems
IV. Public Key Cryptography . . . . . . . . . . . . . . . 78
12. Public Key Distribution Systems . . . . . . . . . . . . . . 79
13. Public Key Cryptography: Knapsacks . . . . . . . . . . . . 82
14. The RSA Public Key Cryptosystem . . . . . . . . . . . . . 86
15. Rabin’s Version of RSA . . . . . . . . . . . . . . . . . . 93
??. Elliptic Curve Cryptosystems
??. Other Public Key Cryptosystems
V. Random Number Generation . . . . . . . . . . . . . 98
16. Traditional Random Number Generators . . . . . . . . . . 99
17. Random Numbers From Chaos Theory . . . . . . . . . . . 106
18. Statistical Tests and Perfect Generators . . . . . . . . . . . 112
VI. The Advanced Encryption Standard (AES) . . . . . . . . 114
19. Introduction to the AES . . . . . . . . . . . . . . . . . . 115
20. The Finite Field GF(256) . . . . . . . . . . . . . . . . . 119
21. The S-Boxes . . . . . . . . . . . . . . . . . . . . . . . 127
22. Key Expansion . . . . . . . . . . . . . . . . . . . . . . 130
23. Encryption . . . . . . . . . . . . . . . . . . . . . . . 133
24. Decryption . . . . . . . . . . . . . . . . . . . . . . . 136
VII. Hash Functions and Digital Signatures
??. One-Way Functions and Hash Functions
??. Digital Signatures
VIII. Randomization Techniques
??. Simple Randomization
??. More Complex Tricks
??. The Rip van Winkle Cipher and Rabin’s Scheme
IX. Identification and Key Distribution . . . . . . . . . . . 140
25. Passwords . . . . . . . . . . . . . . . . . . . . . . . . 141
26. Zero-Knowledge Protocols . . . . . . . . . . . . . . . . . 144
27. Identification Schemes . . . . . . . . . . . . . . . . . . 150
28. Threshold Schemes . . . . . . . . . . . . . . . . . . . . 153
??. Case Study: the Secure Shell (ssh)
Java Programs . . . . . . . . . . . . . . . . . . . . . . 159
Appendices . . . . . . . . . . . . . . . . . . . . . . . 307
A. Using Printed Log Tables . . . . . . . . . . . . . . . . . . . 309
B. Unsigned bytes in Java . . . . . . . . . . . . . . . . . . . . 310
C. Projects . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
I. Preliminaries
1. Cryptographers’ Favorites
Law XOR-1 . . . . . . . . . . . . . . . . . . . . . . . 3
Law XOR-2 . . . . . . . . . . . . . . . . . . . . . . . 5
Law LOG-1 . . . . . . . . . . . . . . . . . . . . . . . 5
Law LOG-2 . . . . . . . . . . . . . . . . . . . . . . . 7
Law GROUP-1 . . . . . . . . . . . . . . . . . . . . . 8
Law FIELD-1 . . . . . . . . . . . . . . . . . . . . . . 9
Law FIELD-2 . . . . . . . . . . . . . . . . . . . . . . 10
Law FERMAT-1 . . . . . . . . . . . . . . . . . . . . . 10
2. Cryptographers’ Favorite Algorithms
Law ***-1 . . . . . . . . . . . . . . . . . . . . . . . 14
Law EXP-1 . . . . . . . . . . . . . . . . . . . . . . . 17
Law PRIME-1 . . . . . . . . . . . . . . . . . . . . . 19
Law PRIME-2 . . . . . . . . . . . . . . . . . . . . . 20
II. Coding and Information Theory
3. Coding and Information Theory
Law ENTROPY-1 . . . . . . . . . . . . . . . . . . . . 23
Law ENTROPY-2 . . . . . . . . . . . . . . . . . . . . 24
Law INFORMATION-1 . . . . . . . . . . . . . . . . . 25
Law SHANNON-1 . . . . . . . . . . . . . . . . . . . . 29
4. Visualizing Channel Capacity
5. The Huffman Code for Compression
Law SHANNON-2 . . . . . . . . . . . . . . . . . . . . 35
Law COMPRESSION-1 . . . . . . . . . . . . . . . . . 36
6. The Hamming Code for Error Correction
Law HAMMING-1 . . . . . . . . . . . . . . . . . . . 46
7. Coping with Decimal Numbers
Law DECIMAL-1 . . . . . . . . . . . . . . . . . . . . 48
Law DECIMAL-2 . . . . . . . . . . . . . . . . . . . . 53
8. Verhoeff’s Decimal Error Detection
Law DECIMAL-3 . . . . . . . . . . . . . . . . . . . . 57
III. Introduction to Cryptography
9. Cryptograms and Terminology
Law CRYPTOGRAPHY-1a . . . . . . . . . . . . . . . . 62
Law CRYPTOGRAPHY-1b . . . . . . . . . . . . . . . . 62
Law CRYPTOGRAPHY-2 . . . . . . . . . . . . . . . . 63
Law CRYPTANALYSIS-1 . . . . . . . . . . . . . . . . . 64
Law CRYPTANALYSIS-2 . . . . . . . . . . . . . . . . . 64
Law CRYPTANALYSIS-3 . . . . . . . . . . . . . . . . . 64
Law CRYPTANALYSIS-4 . . . . . . . . . . . . . . . . . 65
Law CRYPTANALYSIS-5 . . . . . . . . . . . . . . . . . 65
10. The One-Time Pad
Law PAD-1 . . . . . . . . . . . . . . . . . . . . . . . 69
11. Conventional Block Cipher Cryptosystems
Law BLOCKCIPHER-1 . . . . . . . . . . . . . . . . . 71
Law BLOCKCIPHER-2 . . . . . . . . . . . . . . . . . 73
??. Conventional Stream Cipher Cryptosystems
IV. Public Key Cryptography
12. Public Key Distribution Systems
13. Public Key Cryptography: Knapsacks
14. The RSA Public Key Cryptosystem
Law RSA-1 . . . . . . . . . . . . . . . . . . . . . . . 86
Law RSA-2 . . . . . . . . . . . . . . . . . . . . . . . 91
15. Rabin’s Version of RSA
Law RABIN-1 . . . . . . . . . . . . . . . . . . . . . . 93
??. Elliptic Curve Cryptosystems
??. Other Public Key Cryptosystems
V. Random Number Generation
16. Traditional Random Number Generators
Law RNG-1 . . . . . . . . . . . . . . . . . . . . . . . 99
Law RNG-2 . . . . . . . . . . . . . . . . . . . . . . . 99
Law RNG-3 . . . . . . . . . . . . . . . . . . . . . . 100
17. Random Numbers From Chaos Theory
18. Statistical Tests and Perfect Generators
VI. The Advanced Encryption Standard (AES)
19. Introduction to the AES
Law AES-1 . . . . . . . . . . . . . . . . . . . . . . 115
20. The Finite Field GF(256)
21. The S-Boxes
22. Key Expansion
23. Encryption
24. Decryption
VII. Hash Functions and Digital Signatures
??. One-Way Functions and Hash Functions
??. Digital Signatures
VIII. Randomization Techniques
??. Simple Randomization
??. More Complex Tricks
??. The Rip van Winkle Cipher and Rabin’s Scheme
IX. Identification and Key Distribution
25. Passwords
26. Zero-Knowledge Protocols
27. Identification Schemes
28. Threshold Schemes
Law THRESHOLD-1 . . . . . . . . . . . . . . . . . 157
??. Case Study: the Secure Shell (ssh)
Java Programs
Appendices
A. Using Printed Log Tables
B. Unsigned bytes in Java
Law JAVA-BYTES-1 . . . . . . . . . . . . . . . . 311
Law JAVA-BYTES-2 . . . . . . . . . . . . . . . . 312
III. Introduction to Cryptography
9. Cryptograms and Terminology
a. Cryptogram Program . . . . . . . . . . . . . . . 62 229
10. The One-Time Pad
a. Caesar Cipher . . . . . . . . . . . . . . . . . . 67 232
b. Beale Cipher . . . . . . . . . . . . . . . . . . 67 235
c. Generate a One-time Pad . . . . . . . . . . . . . 69 239
d. Wheels to Encrypt/Decrypt With a Pad . . . . . . . 69 242
11. Conventional Block Cipher Cryptosystems
??. Conventional Stream Cipher Cryptosystems
IV. Public Key Cryptography
12. Public Key Distribution Systems
13. Public Key Cryptography: Knapsacks
14. The RSA Public Key Cryptosystem
a. RSA Implementation . . . . . . . . . . . . . . . 90 246
b. Faster RSA, Using Chinese Remainder Theorem . . . 92 251
15. Rabin’s Version of RSA
a. Square Roots mod n = p*q . . . . . . . . . . . . . 94 256
??. Elliptic Curve Cryptosystems
??. Other Public Key Cryptosystems
V. Random Number Generation
16. Traditional Random Number Generators
a. Linear Congruence Random Number Generators . . 103 259
b. Exponential and Normal Distributions . . . . . . . 103 262
17. Random Numbers From Chaos Theory
a. The logistic Lattice as a RNG . . . . . . . . . . 110 266
18. Statistical Tests and Perfect Generators
a. Maurer’s Universal Test . . . . . . . . . . . . . 112 270
b. The Blum-Blum-Shub Perfect Generator . . . . . . 112 272
VI. The Advanced Encryption Standard (AES)
19. Introduction to the AES
20. The Finite Field GF(256)
a. Generate Multiplication Tables . . . . . . . . . . 125 273
b. Compare Multiplication Results . . . . . . . . . 126 275
21. The S-Boxes
a. Generate AES Tables . . . . . . . . . . . . . . 127 277
22. Key Expansion
23. Encryption
a. AES Encryption . . . . . . . . . . . . . . . . 135 282
24. Decryption
a. AES Decryption . . . . . . . . . . . . . . . . 138 290
b. Test Runs of the AES Algorithm . . . . . . . . . 138 293
VII. Hash Functions and Digital Signatures
??. One-Way Functions and Hash Functions
??. Digital Signatures
VIII. Randomization Techniques
??. Simple Randomization
??. More Complex Tricks
??. The Rip van Winkle Cipher and Rabin’s Scheme
IX. Identification and Key Distribution
25. Passwords and Key Distribution
26. Zero-Knowledge Proofs
27. Identification Schemes
28. Threshold Schemes
a. Shamir’s Threshold Schemes . . . . . . . . . . . 157 299
??. Case Study: the Secure Shell (ssh)
The Java programs in the book are available online in machine-readable form on the author’s web page:
http://www.cs.utsa.edu/˜wagner/lawsbook/
This book was partly inspired by two undergraduate courses in cryptography taught at the
University of Texas at San Antonio during the Spring 2002 and Spring 2003 semesters. The
web page for the course has many links and other information:
http://www.cs.utsa.edu/˜wagner/CS4953/index.html
A one-semester undergraduate course in cryptography might cover the following material:
D Part I. Introductory Material on Functions and Algorithms, referring back to it as
needed.
D Part II. Coding and Information Theory, without the Huffman or Hamming codes,
and with emphasis on Verhoeff’s detection method.
D Part III. Introduction to Cryptography, covered quickly.
D Part IV. Public Key Cryptography, the first four chapters.
D Part V. Random Number Generation, the first two chapters.
D Part VI. The Advanced Encryption Standard (AES), all.
D Plus selected remaining topics as desired.
The author would like to thank his mother for giving birth to him, but can’t think of anyone else to thank at this time.
San Antonio, Texas
June, 2003
