<<

. 28
( 29)



>>

Chess Grandmaster Problem, 109
Chinese Lottery, 156“157
Chinese remainder theorem, 249“250, 470



Page 633 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Chor-Rivest knapsack, 466
Chosen-ciphertext attack, 6“7, 471“472
Chosen-key attack, 7
Chosen-plaintext attack, 6“7, 359
Chosen-text attack, 7
Cipher:
substitution, 10“12
transposition, 12
Cipher block chaining mode, 193“197, 208“210
DES, 277“278
error extension, 196
error propagation, 195“196
initialization vector, 194
message authentication codes, 456
padding, 195
security, 196“197
self-recovering, 196
triple encryption, 360“361
Cipher block chaining of plaintext difference mode, 208
Cipher block chaining with checksum, 207“208
Cipher-feedback mode, 200“202, 208“210
DES, 277
error propagation, 201“202
initialization vector, 201
Cipher mode:
choosing, 208“210
summary, 208“210
Ciphertext, 1“2
auto key, 198
hiding in ciphertext, 227“228
pairs, differential cryptanalysis, 285
stealing, 191
Ciphertext-only attack, 5“6
Cleartext, see Plaintext
Clipper chip, 591“593
Clipper key-escrow, 328
Clipper phone, 594
Clock-controlled generators, 381
Clocking, 381
CoCom, 610
Code, 9
Coefficients, solving for, 248
Coin flipping, 89“92
fair, 541“543
into a well, 92
key generation, 92
using Blum integers, 543
using one-way functions, 90
using public-key cryptography, 90“91
using square roots, 541“542
Collision, 166
Collision-free, 30
Collision-resistance, 429



Page 634 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Combination generator, 381
Combining function, 381
Commercial COMSEC Endorsement Program, 269, 598“599
Commercial Data Masking Facility, 366, 574
Common Cryptographic Architecture, 573“574
Common modulus, dangers of, 493
Common modulus attack, RSA, 472
Communications:
using public-key cryptography, 31“34
using symmetric cryptography, 28“29
Communications channels, encryption, 216“220
Communications Setup, 517“518
Complementation property, 281
Complement keys, DES, 281“282
Completely blind signatures, 112“113
Complete set of residues, 242
Complexity-theoretic approach, stream ciphers, 415“418
Complexity theory, 237“242
algorithms, 237“239
complexity of problems, 239“241
Compression, 226
Compression function, 431
Compression permutation, 273“274
Compromise, 5
Compromised keys, 182“183
Computational complexity, 237
Computationally secure, 8
Computer algorithms, 17
Computer clock, as random-sequence generator, 424
Computer Security Act of 1987, 600“601
Computing, with encrypted data, 85“86, 540“541
COMSET, 517“518
Conditional Access for Europe, 606“607
Conference key distribution, 524
Confusion, 237, 346“347
Congruent, 242
Connection integer, 403
feedback with carry shift registers, maximal-period, 406“407
Continued fraction algorithm, 256
Contract signing, simultaneous:
with an arbitrator, 118
without an arbitrator
face-to-face, 118“119
not face-to-face, 119“120
using cryptography, 120“122
Control Vector, 180
Convertible undeniable signatures, 538“539
Coppersmith, Don, 94, 266, 280, 283, 293, 398, 457
Coppersmith™s algorithm, 263
Correlation attack, 380
Correlation immunity, stream ciphers, 380
Correlations, random-sequence generators, 425
Counter mode, 205“206, 209



Page 635 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Counting coincidences, 14
Crab, 342“344
Credit cards, anonymous, 147
Crepeau, Claude, 555
Crypt(1), 414
CRYPT(3), 296
Cryptanalysis, 1, 5“8
differential, see Differential cryptanalysis
FEAL, 311“312
GOST, 333“334
IDEA, 323
linear, 290“293
LOKI91, 316
Madryga, 306
N-Hash, 434“435
related-key, 290
Snefru, 432
types, 5“7
Cryptanalysts, 1
Crypt Breakers Workbench, 414
Cryptographers, 1
Cryptographic algorithm, see Cipher
Cryptographically secure pseudo-random, 45
Cryptographic facility, 562
Cryptographic mode, 189
Cryptographic protection, databases, 73“74
Cryptographic protocol, 22
Cryptography, 1
CRYPTO-LEGGO, 414
Cryptologists, 1
Cryptology, 1
CRYPTO-MECCANO, 346
Cryptosystems, 4
fair, 97
finite automaton public-key, 482
hybrid, 32“34
security, 234“235
weak, 97
Cusick, Thomas, 312
Cut and choose, 103
Cypherpunks, 609
Daemen, Joan, 325, 341, 349, 414
Damgard, Ivan, 446
Damm, Arvid Gerhard, 13
Data, encrypted:
computing with, 85“86, 540“541
discrete logarithm problem, 540“541
for storage, 220“222
Databases, cryptographic protection, 73“74
Data complexity, 9
Data Encryption Algorithm, see Data Encryption Standard
Data Encryption Standard, 17, 265“301
adoption, 267“268



Page 636 of 666
Applied Cryptography: Second Edition - Bruce Schneier



algorithm, brute-force attack efficiency, 152“153
characteristics, 286“288
commercial chips, 279
compared to GOST, 333“334
compression permutation, 273“274
CRYPT(3), 296
decryption, 277
description, 270
DESX, 295
development, 265“267
differential cryptanalysis, 284“290
DES variants, 298
expansion permutation, 273“275
final permutation, 277
generalized, 296“297
hardware and software implementation, 278“279
with independent subkeys, 295
initial permutation, 271
iterated block cipher, 347
key transformation, 272“273
linear cryptanalysis, 290“293
modes, 277“278
multiple, 294“295
1987 review, 268“269
1993 review, 269“270
outline of algorithm, 270“272
P-boxes
design criteria, 294
permutation, 275, 277
RDES, 297“298
related-key cryptanalysis, 290
RIPE-MAC, 457“458
S-boxes, 349
alternate, 296“298
design criteria, 294
key-dependent, 298, 300, 354
substitution, 274“276
security, 278, 280“285
algebraic structure, 282“283
complement keys, 281“282
current, 300“301
key length, 283“284
number of rounds, 284
possibly weak keys, 281“282
S-box design, 284“285
semiweak keys, 280“281
weak keys, 280“281
snDES, 298“299
source code, 623“632
speeds on microprocessors and computers, 279
validation and certification of equipment, 268
Data Exchange Key, 581
Data Keys, 176



Page 637 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Davies, Donald, 562
Davies-Meyer, 448
abreast, 452
modified, 449“450
parallel, 451
tandem, 451“452
Davies-Price, 358
Decoherence, 165
Decryption, 1
DES, 277
key, 3
key-error detection, 179
knapsack algorithms, 465
with a public key, 39
with symmetric algorithm, 4
den Boer, Bert, 434, 436, 441
Denning-Sacco protocol, 63
Dense, 378
Dereferencing keys, 221“222
Derived sequence attack, 381
Designated confirmer signatures, 82“83, 539“540
Desmedt, Yvo, 81
DES, see Data Encryption Standard
Destruction:
information, 228“229
of keys, 184“185
DESX, 295
Dictionary attack, 52, 171“173
Differential cryptanalysis, 284“290
attacks against
DES, 288“290
DES variants, 298
Lucifer, 303
extending to higher-order differentials, 293
strength against, block cipher design theory, 348“349
Differential-linear cryptanalysis, 293
Diffie, Whitfield, 31, 37, 122, 216, 283, 419, 461, 501, 565
Diffie-Hellman:
EKE implementation, 519“520
extended, 515
failsafe, 547“548fair, 546“547
Hughes variant, 515
key exchange without exchanging keys, 515
patents, 516
with three or more parties, 514
Diffie™s randomized stream cipher, 419
Diffusion, 237, 346“347
Digital card, properties, 146
Digital cash, 139“147
anonymous, 139
credit cards, 147
money orders, 140
double spending problem, 140“141



Page 638 of 666
Applied Cryptography: Second Edition - Bruce Schneier



off-line systems, 146
on-line systems, 145“146
other protocols, 145“147
perfect crime, 145
practical, 145
secret splitting, 142“145
Digital certified mail, 122“123
Digital Notary System, 78
Digital Signature Algorithm, 17, 483“494
attacks against k, 492
computation time comparison with RSA, 489
criticisms, 484“486
dangers of common modulus, 493
description, 486“488
ElGamal encryption with, 490“491
patents, 493“494
prime generation, 488“490
proposal for NIST standard, 483“486
RSA encryption with, 491
security, 491“492
speed precomputations, 487“488
subliminal channel, 493, 534“536
foiling, 536
variants, 494“495
Digital signatures, 34“41
algorithms, 39
applications, 41
blind, 112“115, 549“550
convertible undeniable signatures, 538“539
converting identification schemes to, 512
definition, 39
designated confirmer signatures, 82“83, 539“540
ElGamal, 476“478
with encryption, 41“44
entrusted undeniable, 82
fail-stop, 85
Fiat-Shamir signature scheme, 507“508
group signatures, 84“85
Guillou-Quisquater signature scheme, 509“510
improved arbitrated solution, 76
key exchange with, 50
multiple, 39“40
Guillou-Quisquater, 510
nonrepudiation, 40
oblivious, 117
protocol, 40
proxy, 83
public-key algorithms, 483“502
Cade algorithm, 500“501
cellular automata, 500
Digital Signature Algorithm, see Digital Signature Algorithm
discrete logarithm signature schemes, 496“498
ESIGN, 499“500



Page 639 of 666
Applied Cryptography: Second Edition - Bruce Schneier



GOST digital signature algorithm, 495“496
Digital signatures (Cont.)
public-key algorithms (Cont.)
Matsumoto-Imai algorithm, 500
Ong-Schnorr-Shamir, 498“499
public-key cryptography, 37“38
attacks against, 43“44
one-way hash functions and, 38“39
resend attack, foiling, 43
RSA, 473“474
Schnorr signature scheme, 511“512
subliminal-free, 80
with symmetric cryptosystems and arbitrator, 35“37
terminology, 39
timestamps, 38
trees, 37
undeniable, 81“82, 536“539
Dining Cryptographers Problem, 137
Discrete logarithm, 245
in finite field, 261“263
zero-knowledge proofs, 548
Discrete Logarithm Problem, 501, 540“541
Discrete logarithm signature schemes, 496“498
Distributed Authentication Security Service, 62
Distributed convertible undeniable signatures, 539
Distributed key management, 187
DNA computing, 163“164
DNRSG, 387
DoD key generation, 175
Double encryption, 357“358
Double OFB/counter, 363“364
Double spending problem, 140“141
Driver-level encryption, 222“223
DSA, see Digital Signature Algorithm
Dynamic random-sequence generator, 387
E-box, 273
ECB, see Electronic codebook mode
Electronic checks, 146
Electronic codebook mode, 189“191, 208“210
combined with OFB, 364
DES, 277“278padding, 190“191
triple encryption, 362“363
Electronic coins, 146
Electronic Frontier Foundation, 608
Electronic-funds transfer, DES adoption, 268
Electronic Privacy Information Center, 608
ElGamal, 532“533
EKE implementation, 519
encryption, 478
with DSA, 490“491
patents, 479
signatures, 476“478
speed, 478“479



Page 640 of 666
Applied Cryptography: Second Edition - Bruce Schneier



ElGamal, Taher, 263
Elliptic curve cryptosystems, 480“481
Elliptic curve method, 256
Ellison, Carl, 362
Encoding, 226
Encrypt-decrypt-encrypt mode, 359
Encrypted Key Exchange:
applications, 521“522
augmented, 520“521
basic protocol, 518“519
implementation with
Diffie-Hellman, 519“520
ElGamal, 519
RSA, 519
strengthening, 520
Encryption, 1
communication channels, 216“220
combining link-by-link and end-to-end, 219“221
with compression and error control, 226
data, for storage, 220“222
detection, 226“227
digital signatures with, 41“44
driver-level versus file-level, 222“223
ElGamal, 478
with DSA, 490“491
end-to-end, 217“220
with interleaving, 210“211
key, 3
knapsack algorithms, 464
link-by-link, 216“218
multiple, 357
with a private key, 39
probabilistic, 552“554
RSA, 468
with DSA, 491
with symmetric algorithm, 4
using public key, 5
End-to-end encryption, 217“220
combined with link-by-link, 219“221
Enigma, 13, 414
Entropy, 233“234
Entrusted undeniable signature, 82
Error detection:
during decryption, 179
during transmission, 178
Error extension, cipher block chaining mode, 196
Error propagation:
cipher block chaining mode, 195“196
cipher-feedback mode, 201“202
output-feedback mode, 204
Escrow agencies, 592
Escrowed Encryption Standard, 97, 593
ESIGN, 499“500, 533“534



Page 641 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Euclid™s algorithm, 245
Euler totient function, 248“249
Expansion permutation, 273“275, 315
Export:
of algorithms, 215“216, 610“616
foreign, 617
Exportable Protection Device, 389
Export Administration Act, 610
EXPTIME, 241
Extended Euclidean algorithm, 246“248
Factoring, 255“258
general number field sieve, 159“160
long-range predictions, 162
public-key encryption algorithms, 158“159
special number field sieve, 160“161
using quadratic sieve, 159
Factoring Problem, 501
Failsafe:
Diffie-Hellman, 547“548
key escrowing, 98
Fail-stop digital signatures, 85
Fair cryptosystems, 97
Fait-Shamir, 508
FAPKC0, 482
FAPKC1, 482
FAPKC2, 482
FEAL, 308“312
cryptanalysis, 311“312
description, 308“10
patents, 311
Feedback:
cipher block chaining mode, 193, 195
internal, output-feedback mode, 203
Feedback function, 373
Feedback shift register, 373
Feedback with carry shift registers, 402“404
combining generators, 405, 410
maximal-length, tap sequences, 408“409
maximal-period, connection integers, 406“407
Feedforward, cipher block chaining mode, 195
Feige, Uriel, 503“504
Feige-Fiat-Shamir, 503“508
enhancements, 506“507
identification scheme, 504“505
simplified, 503“504
Feistel, Horst, 266, 303
Feistel network, 347
Blowfish, 337
practically secure, 349
Fermat™s little theorem, 248
Euler™s generalization, 248
FFT-Hash, 446
Fiat, Amos, 503“504



Page 642 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Fiat-Shamir signature scheme, 507“508
Fibonacci configuration, 373, 379
Fibonacci shrinking generator, 391
File-level encryption, 222“223
Filter generator, 381
Finite field, 254
discrete logarithms, 261“263
FIPS PUB 46, 267
FIPS PUB 74, 267
FIPS PUB 81, 267
FIPS PUB 112, 267
Fish, 391
Fixed bit index, 543
Flat keyspace, 176
Flipping coins, see Coin flipping
Fortified key negotiation, 522
Galois configuration, linear feedback shift registers, 378“379
Galois field, computing in, 254“255
Garey, Michael, 241
Gatekeeper, 278
Geffe generator, 382“383
General number field sieve, 159“160, 256
General Services Administration, DES adoption, 268
Generators, 253“254
Gifford, 392“393
Gifford, David, 392
Gill, J., 501
Global deduction, 8
Goldwasser, Shafi, 94, 552
Gollmann, Dieter, 386
Gollmann cascade, 387“388
Goodman-McAuley cryptosystem, 466
Goresky, Mark, 404
GOST, 331“334, 354
source code, 643“647
GOST digital signature algorithm, 495“496
GOST hash function, 454
GOST R 34.10“94, 495
Gosudarstvennyi Standard Soyuza SSR, 331“334
Graham-Shamir knapsacks, 465
Graph isomorphism, 104“105
Greatest common divisor, 245“246
Grossman, Edna, 266
Group signatures, 84“85
Group Special Mobile, 389
Group structure, block ciphers design theory, 348
GSM, 389
Guillou, Louis, 102, 508
Guillou-Quisquater:
identification scheme, 508“510
signature scheme, 509“510
Gutmann, Peter, 353
Guy, Richard, 159



Page 643 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Haber, Stuart, 75, 485, 488
Hamiltonian cycles, 105“106
Hard drive, encrypted, providing random access to, 222
Hardware:
DES implementation, 278“279
encryption, 223“225
RSA, 469
Hash functions, see One-way hash functions
Hash value, 30
HAVAL, 445“446
Hellman, Martin, 31“32, 37, 262, 283, 293, 358“359, 461“462
Hiding information from an oracle, 86
Historical terms, 9
Homophonic substitution cipher, 10“11
Hughes, 515
Hughes, Eric, 609
Hughes XPD/KPD, 389“390
Hybrid cryptosystems, 32“34, 461
IBC-Hash, 458
IBM Common Cryptographic Architecture, 573“574
IBM secret-key management protocol, 561“562
IDEA, 319“325, 354
cryptanalysis, 323
description, 320“322
modes of operation, 323“325
overview, 320“321
patents, 325
S-boxes, 349
source code, 637“643
speed, 322“323
strength against differential cryptanalysis, 348
variants, 325
Ideal secrecy, 236
Identification schemes:
converting to signature schemes, 512
Feige-Fiat-Shamir, 503“508
Guillou-Quisquater, 508“510
Ohta-Okamoto, 508
Schnorr authentication and signature scheme, 510“512
Identity-based cryptosystems, 115
Ignition key, 564
Import, foreign, 617
Index of coincidence, 14
Information:
amount, information theory definition, 233
deduction, 8
destruction, 228“229
Information-theoretic approach, 418
stream ciphers, 415
Information theory, 233“237
cryptosystem security, 234“235
entropy and uncertainty, 233“234
in practice, 236“237



Page 644 of 666
Applied Cryptography: Second Edition - Bruce Schneier



rate of the language, 234
unicity distance, 235“236
Ingemarsson, Ingemar, 418
Initialization vector:
cipher block chaining mode, 194
cipher-feedback mode, 201
output-feedback mode, 204
Inner-CBC, 360, 363
Insertion attack, synchronous stream ciphers, 203
Instance deduction, 8
Institute of Electrical and Electronics Engineers, 608
Integrated Services Digital Network, 563“565
Integrity, 2
Interactive protocol, 103
Interchange Key, 581
Interleave, 210“211
Interlock protocol, mutual authentication using, 54“55
Internal feedback, 203
International Association for Cryptologic Research, 605
International Standards Organization:
authentication framework, 574“577
DES adoption, 268
International Traffic in Arms Regulations, 610“614
Internet, Privacy-Enhanced Mail, 577“584
Introducers, 187
Inverses modulo a number, 246“248
IPES, 319
ISDN, 563“565
ISO 8732, 359
ISO 9796, 472, 474, 486
ISO/IEC 9979, 607
ISO X.509 protocols, 574“577
Iterated block cipher, 347
Jacobi symbol, 252“253
J-algebras, 501
Jam, 414
Jennings generator, 383“384
Johnson, David, 241
Jueneman™s methods, 457
Kaliski, Burt, 342
Karn, 351“352
Karn, Phil, 351
Karnin-Greene-Hellman, 530
Kerberos, 60, 566“571
abbreviations, 567
authentication steps, 567
credentials, 568
getting initial ticket, 569
getting server tickets, 569“570
licenses, 571
model, 566
requesting services, 570
security, 571



Page 645 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Version 4, 570“571
Version 5 messages, 568
Kerckhoffs, A., 5
Kerckhoffs™s assumption, 7
Key, 3
backup, 181“182
CDMF shortening, 366
complement, DES, 281“282
compromised, 182“183
controlling usage, 180
dereferencing, 221“222
destroying, 184“185
distribution in large networks, 177
generating, 170“175
ANSI X9.17 standard, 175
DoD, 175
pass phrases, 174“175
poor choices, 171“173
random keys, 173“174
reduced keyspaces, 170“171
ISDN, 563“564
lifetime, 183“184
possibly weak, DES, 281“282
semiweak, DES, 280“281
session, 33, 180
storing, 180“181
transferring, 176“177
transmission, error detection, 178
updating, 180
using, 179“180
verification, 178“179
weak
block ciphers design theory, 348DES, 280“281
Key and message broadcast, 51“52
Key and message transmission, 51
Key Auto-Key, 202
Keyboard latency, as random-sequence generator, 424“425
Key Certification Authority, 43
Key control vectors, 562
Key distribution:
anonymous, 94“95
conference, 524
Key Distribution Center, 43“44
Key-Encryption Keys, 176, 184
Key escrow, 97“100, 181“182, 591
politics, 98“100
Key exchange, 47“52
DASS, 62
Denning-Sacco protocol, 63
with digital signatures, 50
interlock protocol, 49“50
Kerberos, 60
key and message broadcast, 51“52



Page 646 of 666
Applied Cryptography: Second Edition - Bruce Schneier



key and message transmission, 51
man-in-the-middle attack, 48“49
Needham-Schroeder protocol, 58“59
Neuman-Stubblebine protocol, 60“62
Otway-Rees protocol, 59“60
protocols, formal analysis, 65“68
with public-key cryptography, 48
with symmetric cryptography, 47“48
Wide-Mouth Frog protocol, 56“57
without exchanging keys, 515
Woo-Lam protocol, 63“64
Yahalom, 57“58
Key-exchange algorithms:
COMSET, 517“518
conference key distribution and secret broadcasting, 523“525
Diffie-Hellman, 513“516
Encrypted Key Exchange, 518“522
fortified key negotiation, 522
Shamir™s three-pass protocol, 516“517
station-to-station protocol, 516
Tatebayashi-Matsuzaki-Newman, 524“525
Key generation, using coin flipping, 92
Key length:
comparing symmetric and public-key, 165“166
deciding on, 166“167
DES, 283“284
public-key, 158“165
DNA computing, 163“164
quantum computing, 164“165
recommended lengths, 161“163
symmetric, 151“158
biotechnology as cryptanalysis tool, 156“157
brute-force attack, 151“154
Chinese Lottery, 156“157
neural networks, 155
software-based brute-force attacks, 154“155
thermodynamic limitations on brute-force attacks, 157“158
using viruses to spread cracking program, 155“156
Key management, 169“187
distributed, 187
public-key, 185“187
Key negotiation, fortified, 522
Key notarization, 562
Key revocation certificate, 585
Keyspace, 3
flat, 176
nonlinear, 175“176
reduced, 170“171
Keystream generator, 197“198
counter mode, 206
periodic, 202
Khafre, 317“318, 349
Khufu, 317, 349



Page 647 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Kilian, Joe, 116
Kim, Kwangjo, 298, 350
Kinetic Protection Device, 389“390
Klapper, Andy, 404
Klein, Daniel, 53, 171
Knapsack algorithms, 462“466
decryption, 465
encryption, 464
implementations, 465
patents, 466
public key created from private key, 464
security, 465
superincreasing, 463“464
variants, 465“466
Knapsack problem, 501
Known-plaintext attack, 6“7, 151, 359
Knudsen, Lars, 8, 293, 314, 316, 348“349
Knuth, 393, 501
Koblitz, Neal, 480
Konheim, Alan, 266, 280
Kravitz, David, 493
Kravitz-Reed, 481
KryptoKnight, 571“572
Lagged Fibonacci generators, 390
LaGrange interpolating polynomial scheme, 528“529
Lai, Xuejia, 319, 449
Langford, Susan, 293
Law Enforcement Access Field, 591
Legal issues, 618
Legendre symbol, 251
Lehmann, 259
Lehmann algorithm, 259
Length, shift register, 373
Lenstra, Arjen, 159, 162, 257, 485, 488
LFSR/FCSR summation/parity cascade, 410“411
Lidl, Rudolph, 481
Linear complexity:
profile, 380
stream ciphers, 380
Linear congruential generators, 369“372
combining, 371“372
constants, 370
Linear consistency test, 381
Linear cryptanalysis:
DES, 290“293
strength against, block cipher design theory, 348“349
Linear error-correcting codes, algorithms based on, 480
Linear feedback shift registers, 372“379
Galois, 378“379
primitive polynomials mod 2, 376“377
software, 378“379
stream ciphers using, see Stream ciphers
Linear syndrome algorithm, 381



Page 648 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Link-by-link encryption, 216“218
combined with end-to-end, 219“221
Linking protocol, timestamping, 76“77
Li-Wang algorithm, 346
Local deduction, 8
Lock-in, 388
Logarithms, discrete, see Discrete logarithm
LOKI, 314“316
S-boxes, 349
source code, 632“637
LOKI Double-Block, 451
Low decryption exponent attack, RSA, 473
Low encryption exponent attack, RSA, 472“473
Luby, Michael, 352
Luby-Rackoff, 352“353
xDES1, 365
LUC, 481
Lucas number, 481
Luccio-Mazzone, 501
Lucifer, 266, 303“304
Lu-Lee cryptosystem, 466
Lyndon words, 501
MacGuffin, 346
Madryga, W. E., 304
Mafia Fraud, 110
Magic numbers, 423
Manasse, Mark, 159, 257
Man-in-the-middle attack, 48“49
Masks, REDOC II, 312
Massey, James, 319, 339, 386, 418, 449
Master Key, 561
Master Terminal Key, 561
Matsui, Mitsuru, 290“291
Matsumoto-Imai algorithm, 500
Mauborgne, Joseph, 15
Maurer, Ueli, 419
Maurer™s randomized stream cipher, 419
Maximal period generator, 369
MBAL, 344
McEliece, Robert, 479
McEliece algorithm, 346, 479“480
MD2, 441
MD3, 446
MD4, 435“436
MD5, 436“441
MDC, 353“354
MDC-2, 452“453
MDC-4, 452“454
MD-strengthening, 431
Meet-in-the-middle attack, 358, 381
Mental poker, 92“95
Merkle, Ralph, 34, 316“318, 358“359, 432, 455, 461“462
Merkle™s puzzles, 34



Page 649 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Merritt, Michael, 67, 518, 520“521, 571
Message:
authentication, 56
broadcasting, 69
Privacy-Enhanced Mail, 579“582
recovery, 497“498
resending as receipt, 42“43
Message authentication codes, 31, 455“459
bidirectional, 457
CBC-MAC, 456
IBC-Hash, 458
Jueneman™s methods, 457
message authenticator algorithm, 456“457
one-way hash functions as, 458“459
RIPE-MAC, 457“458
stream ciphers, 459
Message authenticator algorithm, 456“457
Message broadcast, anonymous, 137“139
Message Digest, 435“436
Message Digest Cipher, 353
Message Integrity Check, 578
Message-meaning rule, 66
Message Security Protocol, 584
Meyer, Carl, 266, 278
Meyer, Joseph A., 614
Meyer-Schilling, 452
Micali, Silvio, 94, 508, 546“547, 552
Miller, Gary, 259
Miller, V. S., 480
Mimic functions, 10
Minimum-disclosure proofs, 108
MITRENET, 562“563
Miyaguchi, Shoji, 308
MMB, 325“327
m*n-bit S box, 349
Modular arithmetic, 242“245
Modular Multiplication-based Block cipher, 325“327
Modular reduction, 242
Modulo, inverses, 246“248
Monoalphabetic cipher, 10
Montgomery™s method, 244
Moore™s Law, 153
m-sequence, 374
MSP, 584
Muller, Winfried, 481
Multiparty unconditionally secure protocols, 137
Multiple-bit generator, 421
Multiple encryption, 357
quintuple, 366
Multiple Identity Fraud, 111
Multiple-key public-key cryptography, 527“528
Multiple signatures, 39“40
Multiplier, 369



Page 650 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Multispeed inner-product generator, 386“387
Mush, 392
Mutual shrinking generator, 392
MYK-80, 593“594
Mykotronx Clipper chip, 328
MYK-78T, 591“593
Nanoteq, 390
National Bureau of Standards, see National Institute of Standards and Technology
National Computer Security Center, 599“600
National Institute of Standards and Technology, 600“603
DES development, 265“267
Memorandum of Understanding, 601“603
National Security Agency, 597“599
DES development, 266“267
export of cryptography, 614“615
Memorandum of Understanding, 601“603
S-box development role, 278, 280
Navy Research Laboratory, protocol analyzer, 67“68
Needham, Roger, 58, 66, 216
Needham-Schroeder protocol, 58“59
Networks, large, key distribution, 177
Neuman-Stubblebine protocol, 60“62
Neural networks, breaking algorithms, 155
NewDES, 306“308
N-Hash, 433“435
Niederreiter, Harald, 501
Niederreiter algorithm, 480
Niemi cryptosystem, 466
Nobauer, Wilfried, 481
Noise, random, using as random-sequence generator, 423“424
Nonce-verification rule, 66
Non-Interactive Key Sharing systems, 115
Nonlinear-feedback shift registers, 412“413
Nonlinear keyspace, 175“176
Nonrepudiation, 2
Notz, Bill, 266
NP-complete problem, 240“242
graph isomorphism, 104
knapsack algorithms, 462
McEliece algorithm, 479
solving, 163“164
NRL Protocol Analyzer, 67“68
NSDD-145, 268
Nuclear Non-Proliferation Act, 610
Number field sieve, 256
Numbers:
2“adic, 404
large, 17“18
Number theory, 242“255
Barrett™s algorithm, 244
Blum integers, 253
Chinese remainder theorem, 249“250
Euclid™s algorithm, 245



Page 651 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Euler totient function, 248“249
extended Euclidean algorithm, 246“248
Fermat™s little theorem, 248
Galois field, computing in, 254“255
generators, 253“254
greatest common divisor, 245“246
inverses modulo a number, 246“248
Jacobi symbol, 252“253
Legendre symbol, 251
modular arithmetic, 242“245
Montgomery™s method, 244
prime numbers, 245
quadratic residues, 250“251
solving for coefficients, 248
Nyberg, Kaisa, 348
Oblivious transfer, 116“117, 550
Oblivous signatures, 117
OFB, see Output-feedback mode
Ohta, Kazuo, 146, 501
Ohta-Okamoto identification scheme, 508
Okamoto, Tatsuaki, 146, 501
1/p generator, 414
One-time pad, 15“17
hiding ciphertext in ciphertext, 227“228
One-time tape, 418
One-way accumulators, 95“96, 543
One-way function, 29“30
authentication using, 52
bit commitment using, 87“88
coin flipping using, 90
trap-door, 158
One-way hash functions, 30“31, 351“354
background, 429“431
birthday attacks, 165“166, 430
choosing, 455
cipher security, 353“354
compression function, 431
encryption speeds, 456
HAVAL, 445“446
improved arbitrated solution, 76
Karn, 351“352
length, 430“431
Luby-Rackoff, 352“353
MD2, 441
MD3, 446
MD4, 435“436
MD5, 436“441
MD-strengthening, 431
message authentication codes, 455“459
Message Digest Cipher, 353“354
multiple signatures, 40
N-Hash, 433“435
RIPE-MD, 445



Page 652 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Secure Hash Algorithm, 442“445signing documents with, 38“39
Snefru, 432
as unbiased random-bit generator, 107
using public-key algorithms, 455
using symmetric block algorithms, 446“455
AR hash function, 453
GOST hash function, 454
hash length equals block size, 447“449
LOKI Double-Block, 451
MDC-2 and MDC-4, 452“454
modified Davies-Meyer, 449“450
parallel Davies-Meyer, 451
Preneel-Bosselaers-Govaerts-Vandewalle, 450
Quisquater-Girault, 450
tandem and abreast Davies-Meyer, 451“452
Ong-Schnorr-Shamir, 498“499, 531“532
Orange Book, 599“600
Otway-Rees protocol, 59“60
Outerbridge, Richard, 363
Outer-CBC, 360
Output-feedback mode, 203“205, 208“210
combined with ECB, 364
DES, 277
with a nonlinear function, 208
Overtake, 598
Overwriting, 229
Padding:
cipher block chaining mode, 195
electronic codebook mode, 190“191
MD5, 436
Secure Hash Algorithm, 442
triple encryption with, 362
Painvin, Georges, 12
Pass phrases, 174“175
Passive attack, 27
Passive cheaters, 27
Patents, 609“610; See also specific algorithms
P-boxes:
design criteria, 294
permutation, 275, 277, 316
PEM, see Privacy-Enhanced Mail
Perfect secrecy, 235
Period, 11
shift register, 373
Permutation, 237
key, DES, 272“273
PES, 319, 324
Pike, 391“392
PKZIP, 394“395
Plaintext, 1“2
Plaintext block chaining mode, 208
Plaintext feedback mode, 208
Plaintext pair, right and wrong pairs, 287



Page 653 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Pless generator, 413“414
p-NEW scheme, 498
Pohlig, Stephen, 262
Pohlig-Hellman encryption scheme, 474
Polarized photons, 555
Pollard™s Monte Carlo algorithm, 256
Polyalphabetic substitution cipher, 10“11
Polygram substitution cipher, 10“11
Polynomials:
degree, shift register length, 374
dense, 378
irreducible, 255, 481
sparse, 378
Pomerance, Carl, 257
Powerline System, 466
Pre-image, 30
Preneel, Bart, 457
Preneel-Bosselaers-Govaerts-Vandewalle, 450
Pretty Good Privacy, 584“587
Price, William, 562
Prime numbers, 245
generation, 258“261
DSA, 488“490
practical considerations, 260“260
relatively prime, 245
strong, 261
Primitive, 253
Principal square root, 251
Privacy-Enhanced Mail, 577“584
certificates, 579
documents, 578
messages, 579“582
RIPEM, 583“584
security, 582“583
TIS/PEM, 583
Private key, 5
creating public key from, 464
for public-key cryptography, lifetime, 184
Probabilistic encryption, 552“554
Problems:
complexity, 239“241
EXPTIME, 241
hard, 239
intractable, 239
PSPACE, 241
Problems (Cont.)
tractable, 239
undecidable, 240
See also NP-complete problem
Processing complexity, 9
Product cipher, 347
Proofs of Membership, 111
Propagating cipher block chaining mode, 207



Page 654 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Proposed Encryption Standard, 319
Protocols, 21, 47
adjudicated, 26, 70“71
all-or-nothing disclosure of secrets, 96
analysis, approaches, 65“66
anonymous message broadcast, 137“139
arbitrated, 23“26
attacks against, 27
authentication, 576“577
authentication and key-exchange, formal analysis, 65“68
BAN logic, 66“67
basic zero-knowledge, 102“104
bit commitment, 86“88
blind signatures, 112“115
characteristics, 21
cryptographic, 22
DASS, 62
definition, 21
Denning-Sacco, 63
digital cash, see Digital cash
digital certified mail, 122“123
digital signatures, 40
distributed, timestamping, 77“78
fair coin flips, 89“92
IBM Common Cryptographic Architecture, 573“574
IBM secret-key management, 561“562
identity-based public-key cryptography, 115
interactive, 103
interlock, 49“50, 54“55
Kerberos, 60, 566“571
key escrow, 97“100
key exchange, 47“52
KryptoKnight, 571“572
lessons, 64“65
mental poker, 92“95
multiparty unconditionally secure, 137
Needham-Schroeder, 58
Neuman-Stubblebine, 60“62
oblivious signatures, 117
oblivious transfer, 116“117
one-way accumulators, 95“96
Otway-Rees, 59“60
purpose, 22“23
secret splitting, 70“71
secure circuit evaluation, 137
secure elections, see Secure elections
secure multiparty computation, 134“137
self-enforcing, 26“27
SESAME, 572
simultaneous contract signing, 118“122
simultaneous exchange of secrets, 123“124
subliminal channel, 79“80
timestamping, 75“79



Page 655 of 666
Applied Cryptography: Second Edition - Bruce Schneier



types, 24
Wide-Mouth Frog, 56“57
Woo-Lam, 63“64
Yahalom, 57“58
See also Authentication; Zero-knowledge proofs
Pseudo-Hadamard Transform, 340
Pseudo-random function family, SEAL, 398“399
Pseudo-random-number generator, 78, 416
Pseudo-random sequence, 44“45
Pseudo-random-sequence generator, 44
bit commitment using, 88
generating multiple streams, 420“421
linear congruential generators, 369“372
linear feedback shift registers, 372“379
PSPACE, 241
Public key, 5
certificates, 185“187
creating from private key, 464
key length, 158“165
recommended lengths, 161“163
key management, 185“187
Public-key algorithms, 4“5, 33, 500“502
background, 461“462
based on linear error-correcting codes, 480
Diffie-Hellman, 513
ElGamal, 476“479
elliptic curve cryptosystems, 480“481
finite automaton cryptosystems, 482
knapsack algorithms, 462“466
LUC, 481
McEliece, 479“480
one-way hash functions using, 455
Pohlig-Hellman, 474
Rabin, 475“476
RSA, see RSA
security, 461“462
strength, 502
Public-key cryptography:
attacks against, 43“44
authentication using, 53“54
coin flipping using, 90“91
communications using, 31“34
identity-based, 115
key exchange with, 48
multiple-key, 68“69
private keys, lifetime, 184
signing documents with, 37“38

<<

. 28
( 29)



>>