Item Details

# Making, Breaking Codes: An Introduction to Cryptography

Paul Garrett
Format
Book
Published
Upper Saddle River, NJ : Prentice Hall, c2001.
Language
English
ISBN
0130303690
Contents
• 1 Simple Ciphers 1
• 1.1 Shift Cipher 2
• 1.2 Reduction/Division Algorithm 5
• 1.3 One-Time Pad 10
• 1.4 Affine Cipher 13
• 2 Probability 18
• 2.1 Counting 19
• 2.2 Basic Ideas 21
• 2.3 Statistics of English 31
• 2.4 Attack on the Affine Cipher 37
• 3 Permutations 39
• 3.1 Cryptograms: Substitutions 40
• 3.2 Anagrams: Transpositions 43
• 3.3 Permutations 47
• 3.4 Shuffles 54
• 3.5 Block Interleavers 56
• 4 A Serious Cipher 58
• 4.1 Vigenere Cipher 58
• 4.2 LCMs and GCDs 62
• 4.3 Kasiski Attack 64
• 4.4 Expected Values 69
• 4.5 Friedman Attack 73
• 5 More Probability 88
• 5.1 Generating Functions 89
• 5.2 Variance, Standard Deviation 91
• 5.3 Chebycheff's Inequality 93
• 5.4 Law of Large Numbers 94
• 6 Modern Symmetric Ciphers 96
• 6.1 Design Goals 96
• 6.2 Data Encryption Standard 100
• 6.3 Advanced Encryption Standard 106
• 7 Integers 108
• 7.1 Divisibility 108
• 7.2 Unique Factorization 112
• 7.3 Euclidean Algorithm 118
• 7.4 Multiplicative Inverses 122
• 7.5 Computing Inverses 124
• 7.6 Equivalence Relations 127
• 7.7 Integers mod m 130
• 7.8 Primitive Roots, Discrete Logs 136
• 8 Hill Cipher 139
• 8.1 Hill Cipher Operation 139
• 8.2 Hill Cipher Attacks 141
• 9 Complexity 147
• 9.1 Big-Oh/Little-Oh Notation 148
• 9.2 Bit Operations 149
• 9.3 Probabilistic Algorithms 153
• 9.4 Complexity 153
• 9.5 Subexponential Algorithms 155
• 9.6 Kolmogorov Complexity 156
• 9.7 Linear Complexity 157
• 9.8 Worst-Case versus Expected 158
• 10 Public-Key Ciphers 159
• 10.1 Trapdoors 161
• 10.2 RSA Cipher 162
• 10.3 Diffie-Hellman Key Exchange 171
• 10.4 ElGamal Cipher 172
• 10.5 Knapsack Ciphers 176
• 10.6 NTRU Cipher 179
• 10.7 Arithmetica Key Exchange 183
• 10.8 Quantum Cryptography 187
• 10.9 U.S. Export Regulations 189
• 11 Prime Numbers 190
• 11.1 Euclid's Theorem 190
• 11.2 Prime Number Theorem 191
• 11.3 Primes in Sequences 192
• 11.4 Chebycheff's Theorem 193
• 11.5 Sharpest Asymptotics 196
• 11.6 Riemann Hypothesis 197
• 12 Roots mod p 199
• 12.1 Fermat's Little Theorem 200
• 12.2 Factoring Special Expressions 201
• 12.3 Mersenne Numbers 203
• 12.5 Exponentiation Algorithm 207
• 12.6 Square Roots mod p 210
• 12.7 Higher Roots mod p 211
• 13 Roots Mod Composites 213
• 13.1 Sun Ze's Theorem 214
• 13.2 Special Systems 216
• 13.3 Composite Moduli 219
• 13.4 Hensel's Lemma 221
• 13.5 Square-Root Oracles 225
• 13.6 Euler's Theorem 228
• 13.7 Facts about Primitive Roots 229
• 13.8 Euler's Criterion 231
• 14 Weak Multiplicativity 234
• 14.1 Weak Multiplicativity 234
• 14.2 Arithmetic Convolutions 237
• 14.3 Mobius Inversion 239
• 15 Quadratic Reciprocity 242
• 15.1 Square Roots 243
• 15.2 Quadratic Symbols 244
• 15.3 Multiplicative Property 245
• 15.4 Quadratic Reciprocity 246
• 15.5 Fast Computation 251
• 16 Pseudoprimes 255
• 16.1 Fermat Pseudoprimes 256
• 16.2 Non-Prime Pseudoprimes 258
• 16.3 Euler Pseudoprimes 260
• 16.4 Solovay-Strassen Test 262
• 16.5 Strong Pseudoprimes 263
• 16.6 Miller-Rabin Test 263
• 17 Groups 265
• 17.2 Subgroups 268
• 17.3 Lagrange's Theorem 269
• 17.4 Index of a Subgroup 271
• 17.5 Laws of Exponents 272
• 17.6 Cyclic Subgroups 274
• 17.7 Euler's Theorem 276
• 17.8 Exponents of Groups 277
• 18 Sketches of Protocols 279
• 18.1 Basic Public-Key Protocol 280
• 18.2 Diffie-Hellman Key Exchange 281
• 18.3 Secret Sharing 282
• 18.4 Oblivious Transfer 284
• 18.5 Zero-Knowledge Proofs 287
• 18.6 Authentication 288
• 18.7 e-Money, e-Commerce 290
• 19 Rings, Fields, Polynomials 292
• 19.1 Rings, Fields 293
• 19.2 Divisibility 298
• 19.3 Polynomial Rings 300
• 19.4 Euclidean Algorithm 302
• 19.5 Euclidean Rings 307
• 20 Cyclotomic Polynomials 312
• 20.1 Characteristics 313
• 20.2 Multiple Factors 315
• 20.3 Cyclotomic Polynomials 318
• 20.4 Primitive Roots 321
• 20.5 Primitive Roots mod p 322
• 20.6 Prime Powers 323
• 20.7 Counting Primitive Roots 326
• 20.8 Non-Existence 327
• 20.9 Search Algorithm 329
• 21 Random Number Generators 330
• 21.1 Fake One-Time Pads 331
• 21.2 Period of a pRNG 332
• 21.3 Congruential Generators 333
• 21.4 Feedback Shift Generators 335
• 21.5 Blum-Blum-Shub Generator 337
• 21.6 Naor-Reingold Generator 338
• 21.7 Periods of LCGs 339
• 21.8 Primitive Polynomials 343
• 21.9 Periods of LFSRs 346
• 21.10 Examples of Primitives 349
• 21.11 Testing for Primitivity 352
• 22 More on Groups 355
• 22.1 Group Homomorphisms 355
• 22.2 Finite Cyclic Groups 359
• 22.3 Infinite Cyclic Groups 363
• 22.4 Roots and Powers in Groups 363
• 22.5 Square Root Algorithm 367
• 23 Pseudoprimality Proofs 371
• 23.1 Lambda Function 371
• 23.2 Carmichael Numbers 374
• 23.3 Euler Witnesses 375
• 23.4 Strong Witnesses 378
• 24 Factorization Attacks 388
• 24.1 Pollard's Rho Method 389
• 24.2 Pollard's p - 1 method 392
• 24.3 Pocklington-Lehmer Criterion 396
• 24.4 Strong Primes 402
• 24.5 Primality Certificates 405
• 25 Modern Factorization Attacks 411
• 25.1 Gaussian Elimination 412
• 25.2 Random Squares Factoring 414
• 25.3 Dixon's Algorithm 415
• 25.4 Non-Sieving Quadratic Sieve 417
• 25.5 Quadratic Sieve 421
• 25.6 Other Improvements 421
• 26 Finite Fields 423
• 26.1 Making Finite Fields 424
• 26.2 Examples of Field Extensions 426
• 26.3 Addition mod P 427
• 26.4 Multiplication mod P 428
• 26.5 Multiplicative Inverses mod P 428
• 27 Discrete Logs 431
• 27.1 Baby-step Giant-step 432
• 27.2 Pollard's Rho Method 434
• 27.3 Index Calculus 441
• 28 Elliptic Curves 444
• 28.1 Abstract Discrete Logarithms 445
• 28.2 Discrete Log Ciphers 445
• 28.3 Elliptic Curves 448
• 28.4 Points at Infinity 454
• 28.5 Projective Elliptic Curves 456
• 29 More on Finite Fields 457
• 29.1 Ideals in Commutative Rings 458
• 29.2 Ring Homomorphisms 462
• 29.3 Quotient Rings 466
• 29.4 Maximal Ideals and Fields 468
• 29.5 More on Field Extensions 469
• 29.6 Frobenius Automorphism 471
• 29.7 Counting Irreducibles 479
• 29.8 Counting Primitives 482
• A.1 Sets and Functions 484
• A.2 Searching, Sorting 489
• A.3 Vectors 492
• A.4 Matrices 497
• A.5 Stirling's Formula 501
• T.1 Factorizations under 600 505
• T.2 Primes Below 10,000 509
• T.3 Primitive Roots under 100 511.
Description
xix, 524 p. ; 24 cm.
Notes
Includes bibliographical references (p. 512-515) and index.
Technical Details
• Access in Virgo Classic

• LEADER 07780pam a22003134a 4500
001 u3723113
003 SIRSI
005 20001211151951.0
008 000525s2001 nju b 001 0 eng
a| 00042742
a| 0130303690
a| (Sirsi) i0130303690
a| (OCoLC)44173039
a| DLC c| DLC d| DLC d| MvI
a| pcc
050
0
0
a| QA268 b| .G37 2001
082
0
0
a| 652/.8 2| 21
a| SCIENG/QA268 b| .G37 2001
100
1

a| Garrett, Paul B.
245
1
0
a| Making, breaking codes : b| an introduction to cryptography / c| Paul Garrett.
a| Upper Saddle River, NJ : b| Prentice Hall, c| c2001.
a| xix, 524 p. ; c| 24 cm.
a| Includes bibliographical references (p. 512-515) and index.
505
0
0
g| 1 t| Simple Ciphers g| 1 -- g| 1.1 t| Shift Cipher g| 2 -- g| 1.2 t| Reduction/Division Algorithm g| 5 -- g| 1.3 t| One-Time Pad g| 10 -- g| 1.4 t| Affine Cipher g| 13 -- g| 2 t| Probability g| 18 -- g| 2.1 t| Counting g| 19 -- g| 2.2 t| Basic Ideas g| 21 -- g| 2.3 t| Statistics of English g| 31 -- g| 2.4 t| Attack on the Affine Cipher g| 37 -- g| 3 t| Permutations g| 39 -- g| 3.1 t| Cryptograms: Substitutions g| 40 -- g| 3.2 t| Anagrams: Transpositions g| 43 -- g| 3.3 t| Permutations g| 47 -- g| 3.4 t| Shuffles g| 54 -- g| 3.5 t| Block Interleavers g| 56 -- g| 4 t| A Serious Cipher g| 58 -- g| 4.1 t| Vigenere Cipher g| 58 -- g| 4.2 t| LCMs and GCDs g| 62 -- g| 4.3 t| Kasiski Attack g| 64 -- g| 4.4 t| Expected Values g| 69 -- g| 4.5 t| Friedman Attack g| 73 -- g| 5 t| More Probability g| 88 -- g| 5.1 t| Generating Functions g| 89 -- g| 5.2 t| Variance, Standard Deviation g| 91 -- g| 5.3 t| Chebycheff's Inequality g| 93 -- g| 5.4 t| Law of Large Numbers g| 94 -- g| 6 t| Modern Symmetric Ciphers g| 96 -- g| 6.1 t| Design Goals g| 96 -- g| 6.2 t| Data Encryption Standard g| 100 -- g| 6.3 t| Advanced Encryption Standard g| 106 -- g| 7 t| Integers g| 108 -- g| 7.1 t| Divisibility g| 108 -- g| 7.2 t| Unique Factorization g| 112 -- g| 7.3 t| Euclidean Algorithm g| 118 -- g| 7.4 t| Multiplicative Inverses g| 122 -- g| 7.5 t| Computing Inverses g| 124 -- g| 7.6 t| Equivalence Relations g| 127 -- g| 7.7 t| Integers mod m g| 130 -- g| 7.8 t| Primitive Roots, Discrete Logs g| 136 -- g| 8 t| Hill Cipher g| 139 -- g| 8.1 t| Hill Cipher Operation g| 139 -- g| 8.2 t| Hill Cipher Attacks g| 141 -- g| 9 t| Complexity g| 147 -- g| 9.1 t| Big-Oh/Little-Oh Notation g| 148 -- g| 9.2 t| Bit Operations g| 149 -- g| 9.3 t| Probabilistic Algorithms g| 153 -- g| 9.4 t| Complexity g| 153 -- g| 9.5 t| Subexponential Algorithms g| 155 -- g| 9.6 t| Kolmogorov Complexity g| 156 -- g| 9.7 t| Linear Complexity g| 157 -- g| 9.8 t| Worst-Case versus Expected g| 158 -- g| 10 t| Public-Key Ciphers g| 159 -- g| 10.1 t| Trapdoors g| 161 -- g| 10.2 t| RSA Cipher g| 162 -- g| 10.3 t| Diffie-Hellman Key Exchange g| 171 -- g| 10.4 t| ElGamal Cipher g| 172 -- g| 10.5 t| Knapsack Ciphers g| 176 -- g| 10.6 t| NTRU Cipher g| 179 -- g| 10.7 t| Arithmetica Key Exchange g| 183 -- g| 10.8 t| Quantum Cryptography g| 187 -- g| 10.9 t| U.S. Export Regulations g| 189 -- g| 11 t| Prime Numbers g| 190 -- g| 11.1 t| Euclid's Theorem g| 190 -- g| 11.2 t| Prime Number Theorem g| 191 -- g| 11.3 t| Primes in Sequences g| 192 -- g| 11.4 t| Chebycheff's Theorem g| 193 -- g| 11.5 t| Sharpest Asymptotics g| 196 -- g| 11.6 t| Riemann Hypothesis g| 197 -- g| 12 t| Roots mod p g| 199 -- g| 12.1 t| Fermat's Little Theorem g| 200 -- g| 12.2 t| Factoring Special Expressions g| 201 -- g| 12.3 t| Mersenne Numbers g| 203 -- g| 12.5 t| Exponentiation Algorithm g| 207 -- g| 12.6 t| Square Roots mod p g| 210 -- g| 12.7 t| Higher Roots mod p g| 211 -- g| 13 t| Roots Mod Composites g| 213 -- g| 13.1 t| Sun Ze's Theorem g| 214 -- g| 13.2 t| Special Systems g| 216 -- g| 13.3 t| Composite Moduli g| 219 -- g| 13.4 t| Hensel's Lemma g| 221 -- g| 13.5 t| Square-Root Oracles g| 225 -- g| 13.6 t| Euler's Theorem g| 228 -- g| 13.7 t| Facts about Primitive Roots g| 229 -- g| 13.8 t| Euler's Criterion g| 231 -- g| 14 t| Weak Multiplicativity g| 234 -- g| 14.1 t| Weak Multiplicativity g| 234 -- g| 14.2 t| Arithmetic Convolutions g| 237 -- g| 14.3 t| Mobius Inversion g| 239 -- g| 15 t| Quadratic Reciprocity g| 242 -- g| 15.1 t| Square Roots g| 243 -- g| 15.2 t| Quadratic Symbols g| 244 -- g| 15.3 t| Multiplicative Property g| 245 -- g| 15.4 t| Quadratic Reciprocity g| 246 -- g| 15.5 t| Fast Computation g| 251 -- g| 16 t| Pseudoprimes g| 255 -- g| 16.1 t| Fermat Pseudoprimes g| 256 -- g| 16.2 t| Non-Prime Pseudoprimes g| 258 -- g| 16.3 t| Euler Pseudoprimes g| 260 -- g| 16.4 t| Solovay-Strassen Test g| 262 -- g| 16.5 t| Strong Pseudoprimes g| 263 -- g| 16.6 t| Miller-Rabin Test g| 263 -- g| 17 t| Groups g| 265 -- g| 17.2 t| Subgroups g| 268 -- g| 17.3 t| Lagrange's Theorem g| 269 -- g| 17.4 t| Index of a Subgroup g| 271 -- g| 17.5 t| Laws of Exponents g| 272 -- g| 17.6 t| Cyclic Subgroups g| 274 -- g| 17.7 t| Euler's Theorem g| 276 -- g| 17.8 t| Exponents of Groups g| 277 -- g| 18 t| Sketches of Protocols g| 279 -- g| 18.1 t| Basic Public-Key Protocol g| 280 -- g| 18.2 t| Diffie-Hellman Key Exchange g| 281 -- g| 18.3 t| Secret Sharing g| 282 -- g| 18.4 t| Oblivious Transfer g| 284 -- g| 18.5 t| Zero-Knowledge Proofs g| 287 -- g| 18.6 t| Authentication g| 288 -- g| 18.7 t| e-Money, e-Commerce g| 290 -- g| 19 t| Rings, Fields, Polynomials g| 292 -- g| 19.1 t| Rings, Fields g| 293 -- g| 19.2 t| Divisibility g| 298 -- g| 19.3 t| Polynomial Rings g| 300 -- g| 19.4 t| Euclidean Algorithm g| 302 -- g| 19.5 t| Euclidean Rings g| 307 -- g| 20 t| Cyclotomic Polynomials g| 312 -- g| 20.1 t| Characteristics g| 313 -- g| 20.2 t| Multiple Factors g| 315 -- g| 20.3 t| Cyclotomic Polynomials g| 318 -- g| 20.4 t| Primitive Roots g| 321 -- g| 20.5 t| Primitive Roots mod p g| 322 -- g| 20.6 t| Prime Powers g| 323 -- g| 20.7 t| Counting Primitive Roots g| 326 -- g| 20.8 t| Non-Existence g| 327 -- g| 20.9 t| Search Algorithm g| 329 -- g| 21 t| Random Number Generators g| 330 -- g| 21.1 t| Fake One-Time Pads g| 331 -- g| 21.2 t| Period of a pRNG g| 332 -- g| 21.3 t| Congruential Generators g| 333 -- g| 21.4 t| Feedback Shift Generators g| 335 -- g| 21.5 t| Blum-Blum-Shub Generator g| 337 -- g| 21.6 t| Naor-Reingold Generator g| 338 -- g| 21.7 t| Periods of LCGs g| 339 -- g| 21.8 t| Primitive Polynomials g| 343 -- g| 21.9 t| Periods of LFSRs g| 346 -- g| 21.10 t| Examples of Primitives g| 349 -- g| 21.11 t| Testing for Primitivity g| 352 -- g| 22 t| More on Groups g| 355 -- g| 22.1 t| Group Homomorphisms g| 355 -- g| 22.2 t| Finite Cyclic Groups g| 359 -- g| 22.3 t| Infinite Cyclic Groups g| 363 -- g| 22.4 t| Roots and Powers in Groups g| 363 -- g| 22.5 t| Square Root Algorithm g| 367 -- g| 23 t| Pseudoprimality Proofs g| 371 -- g| 23.1 t| Lambda Function g| 371 -- g| 23.2 t| Carmichael Numbers g| 374 -- g| 23.3 t| Euler Witnesses g| 375 -- g| 23.4 t| Strong Witnesses g| 378 -- g| 24 t| Factorization Attacks g| 388 -- g| 24.1 t| Pollard's Rho Method g| 389 -- g| 24.2 t| Pollard's p - 1 method g| 392 -- g| 24.3 t| Pocklington-Lehmer Criterion g| 396 -- g| 24.4 t| Strong Primes g| 402 -- g| 24.5 t| Primality Certificates g| 405 -- g| 25 t| Modern Factorization Attacks g| 411 -- g| 25.1 t| Gaussian Elimination g| 412 -- g| 25.2 t| Random Squares Factoring g| 414 -- g| 25.3 t| Dixon's Algorithm g| 415 -- g| 25.4 t| Non-Sieving Quadratic Sieve g| 417 -- g| 25.5 t| Quadratic Sieve g| 421 -- g| 25.6 t| Other Improvements g| 421 -- g| 26 t| Finite Fields g| 423 -- g| 26.1 t| Making Finite Fields g| 424 -- g| 26.2 t| Examples of Field Extensions g| 426 -- g| 26.3 t| Addition mod P g| 427 -- g| 26.4 t| Multiplication mod P g| 428 -- g| 26.5 t| Multiplicative Inverses mod P g| 428 -- g| 27 t| Discrete Logs g| 431 -- g| 27.1 t| Baby-step Giant-step g| 432 -- g| 27.2 t| Pollard's Rho Method g| 434 -- g| 27.3 t| Index Calculus g| 441 -- g| 28 t| Elliptic Curves g| 444 -- g| 28.1 t| Abstract Discrete Logarithms g| 445 -- g| 28.2 t| Discrete Log Ciphers g| 445 -- g| 28.3 t| Elliptic Curves g| 448 -- g| 28.4 t| Points at Infinity g| 454 -- g| 28.5 t| Projective Elliptic Curves g| 456 -- g| 29 t| More on Finite Fields g| 457 -- g| 29.1 t| Ideals in Commutative Rings g| 458 -- g| 29.2 t| Ring Homomorphisms g| 462 -- g| 29.3 t| Quotient Rings g| 466 -- g| 29.4 t| Maximal Ideals and Fields g| 468 -- g| 29.5 t| More on Field Extensions g| 469 -- g| 29.6 t| Frobenius Automorphism g| 471 -- g| 29.7 t| Counting Irreducibles g| 479 -- g| 29.8 t| Counting Primitives g| 482 -- g| A.1 t| Sets and Functions g| 484 -- g| A.2 t| Searching, Sorting g| 489 -- g| A.3 t| Vectors g| 492 -- g| A.4 t| Matrices g| 497 -- g| A.5 t| Stirling's Formula g| 501 -- g| T.1 t| Factorizations under 600 g| 505 -- g| T.2 t| Primes Below 10,000 g| 509 -- g| T.3 t| Primitive Roots under 100 g| 511.
a| 5
650

0
a| Coding theory.
a| QA268 .G37 2001 w| LC i| X004523540 l| STACKS m| SCI-ENG t| BOOK

## Availability

### Google Preview

Library Location Map Availability Call Number
Brown Science and Engineering Stacks N/A Available