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
    010
      
      
    a| 00042742
    020
      
      
    a| 0130303690
    035
      
      
    a| (Sirsi) i0130303690
    035
      
      
    a| (OCoLC)44173039
    040
      
      
    a| DLC c| DLC d| DLC d| MvI
    042
      
      
    a| pcc
    050
    0
    0
    a| QA268 b| .G37 2001
    082
    0
    0
    a| 652/.8 2| 21
    090
      
      
    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.
    260
      
      
    a| Upper Saddle River, NJ : b| Prentice Hall, c| c2001.
    300
      
      
    a| xix, 524 p. ; c| 24 cm.
    504
      
      
    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.
    596
      
      
    a| 5
    650
      
    0
    a| Coding theory.
    999
      
      
    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