RSA and public-key cryptography

RSA and PUBLIC-KEY CRYPTOGRAPHY......Page 1
Preface......Page 6
About the Author......Page 8
Contents......Page 10
1.1 Terminology......Page 12
Definition 1.3 (Enciphering and Deciphering Functions)......Page 16
Diagram 1.6 An Illustrated Cryptosystem......Page 17
Definition 1.10 (Block Ciphers)......Page 18
Definition 1.12 (Keystreams, Seeds, and Generators)......Page 19
The Vernam Cipher......Page 20
Affine Ciphers......Page 24
Vigenere Cipher......Page 25
THE VIGEN`ERE TABLEAU......Page 26
Definition 1.19 (Synchronous Stream Ciphers)......Page 27
Definition 1.22 (Autokey Ciphers)......Page 28
Beaufort Cipher......Page 29
The Playfair Cipher......Page 30
The Hill Cipher......Page 31
Definition 1.28 (Transposition/Permutation Ciphers)......Page 32
Known-Plaintext......Page 36
Chosen-Ciphertext......Page 37
Man-in-the-Middle Attack......Page 38
Kasiski’s Attack on Polyalphabetic Ciphers......Page 39
Example 1.32 (Kasiski’s Attack on the Vigenere Cipher)......Page 40
2.1 Cryptographic Protocols......Page 44
Feige-Fiat-Shamir Identification Protocol — Simplified Version......Page 45
Self-Enforcing Protocols......Page 47
Coin Flipping by Telephone......Page 48
Silver-Pohlig-Hellman Algorithm for Computing Discrete Logs......Page 50
Baby-Step Giant-Step Algorithm for Computing Discrete Logs......Page 53
The Index-Calculus Algorithm for Computing Discrete Logs......Page 54
Pohlig-Hellman Symmetric-Key Exponentiation Cipher......Page 58
Coin Flipping by Exponentiation......Page 59
The Diffie-Hellman Key-Exchange Protocol......Page 60
The Repeated Squaring Method for Modular Exponentiation......Page 61
Definition 3.1 (One-Way Functions)......Page 64
Coin Flipping Using One-Way Functions......Page 65
Bit Commitment Protocol Using One-Way Functions......Page 66
Definition 3.4 (Trapdoor One-Way Functions)......Page 68
Diagram 3.5 Trapdoor One-Way Function......Page 69
Diagram 3.8 (Asymmetric (Public-Key) Cryptosystems)......Page 71
The RSA Public-Key Cryptosystem......Page 72
The RSA Conjecture......Page 76
The ElGamal Cryptosystem......Page 78
Generalized ElGamal Public-Key Cryptosystem......Page 81
Massey-Omura Cryptosystem......Page 82
Advantages of Public-Key Cryptosystems......Page 84
Analysis and Summary......Page 85
Diagram 3.16 (Digital Envelope — Hybrid Cryptosystem)......Page 86
3.5 Secret History of Public-Key Cryptography......Page 88
Types of Probabilistic Algorithms......Page 90
Las Vegas Algorithms......Page 91
Definition 4.1 (Pseudoprimes)......Page 92
Definition 4.3 (Carmichael Number)......Page 93
The Solovay-Strassen Primality Test......Page 95
The Miller -Selfridge -Rabin Primality Test......Page 98
The Integer Factorization Problem (IFP)......Page 104
Universal Exponent Factorization Method......Page 105
Pollard’s p – 1 Factoring Method......Page 107
Elliptic Curve Facts......Page 110
Lenstra’s Elliptic Curve Method (ECM)......Page 111
Multipolynomial Quadratic Sieve (MPQS)......Page 115
5.5 The Number Field Sieve......Page 119
General Number Field Sieve (GNFS)......Page 120
6.1 Implementation Attacks......Page 122
Timing Attack......Page 123
Other Attacks and Implementation Security Issues......Page 124
Theorem 6.2 (Coppersmith)......Page 126
Theorem 6.3 (Strong Hastad Broadcast Attack)......Page 127
Theorem 6.5 (Coppersmith’s Short Pad Attack)......Page 128
Theorem 6.9 (Weiner’s Attack)......Page 129
Definition 6.10 (Strong Primes)......Page 131
Gordon’s Algorithm for Generating (Probable) Strong Primes......Page 132
Cycling Attack on RSA......Page 133
Theorem 6.11 (Pocklington’s Theorem)......Page 135
Maurer’s Large (Provable) Prime Generation (Brief Version)......Page 136
Diagram 7.1 (Impersonation Attack on Public-Key Cryptosystems)......Page 138
Definition 7.3 (Digital Signature Schemes)......Page 139
Schnorr Identification Protocol......Page 140
Okamoto Identification Protocol......Page 142
Replay (or Playback) Attack......Page 144
RSA Signature Scheme......Page 146
ElGamal Signature Scheme......Page 147
Schnorr Signature Scheme......Page 149
Digital Signature Algorithm (DSA)......Page 150
7.3 Digital Cash and Electronic Commerce......Page 154
ECash™ Scheme......Page 156
ECash Spending Scheme (Offline) in Brief......Page 158
Brands\'Digital Cash Scheme......Page 159
8.1 Secret Sharing......Page 164
Shamir’s Threshold Scheme......Page 165
Asmuth-Bloom Threshold Scheme......Page 167
Blakely’s Secret Sharing Vector Scheme......Page 168
8.2 Key Establishment......Page 171
Station-to-Station Protocol (STS)......Page 172
Girault’s Self-Certifying Key Agreement Scheme......Page 173
Blom’s (Simplified) Key Predistribution Scheme......Page 175
Kerberos Authentication/Session Key Distribution Protocol — Simplified......Page 177
Needham-Schroeder Key Predistribution Scheme......Page 178
Needham-Schroeder (Modified) Public-Key Scheme......Page 179
Encrypted Key Exchange (EKE)—Diffie-Hellman Implemented......Page 180
8.3 Public-Key Infrastructure (PKI)......Page 184
9.1 Secrecy and Authentication......Page 190
Nuclear Test Ban Treaty Compliance......Page 191
S/MIME Authentication Protocol — Without Secrecy......Page 192
S/MIME Secrecy Protocol — Without Authentication......Page 193
S/MIME Authentication and Secrecy Protocol......Page 194
9.2 Other Threats to System Security......Page 196
Birthday Attack......Page 197
Alice Cheats Bob Using the Birthday Attack......Page 198
9.3 Wireless Security......Page 201
The Beller-Yacobi Wireless Authentication/Key Agreement Protocol......Page 203
Aziz-Diffie Wireless Authentication/Key Agreement Protocol......Page 205
Guillou-Quisquater Identification Scheme......Page 209
Guillou-Quisquater Signature Scheme......Page 210
Appendix A: Letter Frequency Analysis......Page 214
Definition B.1 (Asymptotic or Big O Notation)......Page 216
Example B.4......Page 217
Definition C.2 (Relative Primality)......Page 223
Definition C.7 (The Least Common Multiple)......Page 224
Theorem C.11 (The Field Z/pZ)......Page 225
Theorem C.16 (Euler’s Generalization of Fermat’s Little Theorem)......Page 226
Proposition C.22 (Primitive Roots and Primality)......Page 227
Theorem C.25 (Euler’s Criterion for Power Residue Congruences)......Page 228
Vector Spaces......Page 229
Basic Matrix Theory......Page 230
Theorem C.38 (Cramer’s Rule)......Page 232
Gaussian Elimination......Page 233
Theorem C.43 (Finite Simple Continued Fractions Are Rational)......Page 234
Section 1.1......Page 235
Section 1.2......Page 236
Section 1.3......Page 237
Section 2.1......Page 238
Section 2.2......Page 239
Section 3.1......Page 240
Section 3.2......Page 241
Section 3.3......Page 242
Section 3.4......Page 243
Section 4.3......Page 244
Section 4.4......Page 245
Section 5.1......Page 246
Section 5.2......Page 247
Section 5.3......Page 248
Section 6.1......Page 249
Section 6.3......Page 250
Section 7.1......Page 251
Section 7.3......Page 252
Section 8.1......Page 253
Section 8.2......Page 255
Section 9.2......Page 257
Section 9.4......Page 258
Bibliography......Page 259