Nội dung


  
 
"!"#%$&$(')$(* +-,.,"/10123!547698&,":$(;(6< ,.=&8?>A@BDCFEHGIKJLK>NMOEQPRJ S UTV
>?JWDXE YZJ1J>?[\M U>^]`__aE b(c1
ZJU7J>&UKedfd3dhgUifjfikhg1lOjm3nhg1ofdOjmfpfkOqfr3rsgUifjRtnOj3i [uM UK
wvUJKWx
7yyVz{Jv|AKTK}T~O7J 
~KyKTUJTwPKU€QJ?
 @AR‚fƒ M.K7U€J-^vQJW{„U€PHK>OJ J W†‡Z„U€J vy€FTKB|f
^TV
Q^ AKUJQyˆc KE
€ O7JW R J`‰Š3KJWDD@€J W€J v„c y‹€y†TV
ŒQ 
@A3‚f>ˆ
3TKQBOJvIwURW cTKJvTK{w
K
JŽAKUJy cU†
 AKUJ5TK`Jv
‰TKB>„7‚fJvKyKTQJ€T-TKŒ‘PRy€Q@y€† U’’PRy^@B 
KUsz{‹
c U€hAKU~U€QJJ7z{U‹€Jv~Q“[MˆUKUE ”&ŠOTKK<•z{
KU‰‘PHK1–VU€WW KJ—@BŽ
‰UOTK}T-O7J5@A‘PH>˜
‰1J WW™TKBOv
xJ€T Q“[\M UKZ y€K%š
€hKyKTUJThPKU€QJƒ ›FKœ

€@O3‚ŒJ QJBD ‡F7‘B@AZK 3WcTKW‰&UJU~œKW‰J†QJBDQu @BJBž7KQJ>hKyKTUJT‰„7TV
JTKy>h€J TKycWJvŸ
RTBNJv>7TKU}y~Jv> J WKTW €JvQ>%š@B5JB€JQ7J1UvŒe’’PRys1BO‡7>?z{œ
c~U€ AKU~U€QJJ7z{U‹€Jv~Q 
{ c@y€U
KUE 
7TJJ†Q[ M {WR J~Š3KJWx-TBNJvD vJKUysW‡@cJ> Q~`J>NQTK`Jv•J’z¡ze‚f>N^yKEhXAKT€}TeO7€UJx„c1{@O @<JKWDJ7z{U‹€Jv~Q“[\M UKZUcTV
TBNJvE T¢ ]__Q£•@BŽ[^¤M >¥¦JTE Index Symbols §‹¨f§ © ª « ¬ ­ ® ° ± ² ¯ ì ¨ integers), 49 ì Û (the (integers modulo Ï ), 68 ìéÛ (multiplicative group of ì Û ), 69 í Û (quadratic residues modulo Ï ), 70 í (quadratic non-residues modulo Ï ), 70 îH» Û (finite field of order ï ), 81 î é » (multiplicative îH» group of ), 81 ðs¼ â À (polynomial ring), ñ (inclusive-OR), 213 78 ò (exclusive-OR), 20 ó 213 Û ô (AND), (addition mod Ô ), 263 õ (subtraction mod Ô Û ), 270 ö (modified multiplication mod Ô Û÷ æ ), 263 ã˜ø (left rotation), 213 ù ú (right rotation), 213 û úŽ ü (message transfer), 396 (cardinality of a set ), 49 (set member), 49 (subset), 49 (proper subset), 49 (set intersection), 49 (set union), 49 (set difference), 49 (Cartesian product), 49 (empty set), 50 -notation (big-O), 58 -notation (big-omega), 59 -notation (big-theta), 59 -notation (little-o), 59 (by definition), 213 (subexponential notation), 60 (polytime reduction), 61 (asymptotic equivalence), 134 (mathematical constant pi), 49 (base of natural logarithms), 49 (sum), 50 (product), 50 (factorial), 50 (floor), 49 (ceiling), 49 (Euler phi function), 65, 286 (Möbius function), 154 (base logarithm), 50 (natural logarithm), 50 (interval of integers), 49 (divides relation), 63, 79 (congruence relation), 67, 79 (much less than), 529 (much greater than), 170 (binomial coefficient), 52 (Legendre symbol), 72 (inner product), 118 (length of a vector ), 118 (assignment operator), 66 (concatenation of strings , ), 38 (bitstrings of bitlength ), 447 (bitstrings of arbitrary bitlength), 447 (the rational numbers), 49 (the real numbers), 49 ³ ´ µ·¶¸ ºN¹ »·¼ ½(¾€¿ÁÀ Â?Ã Ä Å Æ ë Ç È`É `Ê Ë Ì Í3ÎÐÏ3Ñ Ò‹Ó Ô Ò‹Õ ¼§ Ö¾€×ÁÀ Ø Ù Ú ÛÜ Ý ß7Þ à á1âfá Öã× Ö á× Ü ä’å ¾·æ‘ç ä’å ¾·æ‘çÁé ê A Abelian group, 75 Abstract Syntax Notation One (ASN.1), 660 Access control, 3 Access control matrix, 387 Access matrix model, 569 Access structure, 526 monotone, 527 Accredited Standards Committee (ASC), 648 Active adversary, 15, 37 Active attack, 41, 495 Ad hoc security, 43 Adaptive chosen-ciphertext attack, 42 Adaptive chosen-message attack, 433 Adaptive chosen-plaintext attack, 41 Addition chains, 621, 633 Adversary, 13, 495 active, 15 insider, 496 one-time, 496 permanent, 496 outsider, 496 passive, 15 Affine cipher, 239 Algebraic normal form, 205 Algorithm definition of, 57 â Ö × è 755 756 deterministic, 62 exponential-time, 59 polynomial-time, 59 randomized, 62 expected running time, 63 running time, 58 asymptotic, 58 average-case, 58 worst-case, 58 subexponential-time, 60 Alphabet of definition, 11 Alternating step generator, 209–211, 220 Anonymity, 3 ANSI standards, 648–651, 660 ordering and acquiring, 656 ANSI X9.17 pseudorandom bit generator, 173 Anti-palindromic keys of DES, 257 Appended authenticator, 361 Arbitrated signature scheme, 472–473 Arithmetic integer, see Multiple-precision integer arithmetic modular, see Multiple-precision modular arithmetic Arthur-Merlin games, 421 ASN.1, see Abstract Syntax Notation One (ASN.1) Asymmetric cryptographic system, 544 Asymptotic running time, 58 Atkin’s primality test, 145 implementation report, 166 Attack active, 41, 495 adaptive chosen-ciphertext, 42 adaptive chosen-message, 433 adaptive chosen-plaintext, 41 chosen-ciphertext, 41, 226 chosen-message, 433 chosen-plaintext, 41, 226 chosen-text, 417 ciphertext-only, 41, 225 dictionary, 42, 392 differential cryptanalysis, 258 differential-linear, 271 exhaustive key search, 233–234 forced delay, 417 forward search, 42, 288, 420 impersonation, 42, 417 interleaving, 42, 417, 531, 540 intruder-in-the-middle, 530, 540 key-only, 432 known-key, 42, 496, 534 known-key triangle, 538 known-message, 432 known-plaintext, 41, 225 linear cryptanalysis, 258 Index local, 419 meet-in-the-middle, 235 misplaced trust in server, 531 non-interactive, 419 off-line, 419 on-line, 419 passive, 41, 495 pre-play, 397 reflection, 417, 530, 540 related-key, 226 remote, 419 replay, 42, 417 time-memory tradeoff, 236 truncated differentials, 271 universal forgery, 482 Attacker, 13 Attacker (alternate names), 495 see also Adversary Attribute certificate, 561 Audit trail, 549, 583 Audit trail information, 545 Authenticated key establishment, 492, 493 Authenticated key exchange protocol AKEP1/AKEP2, 499, 535, 541 Authentication data origin, 4, 361 see also Data origin authentication entity, 4 see also Entity authentication explicit key, 492 key, 492 message, 361 mutual, 494 protocol, 493 transaction, 362 unilateral, 494 see also Entity authentication (and Identification) Authentication code, 376, 382 Authentication path, 557 Authentication server, 491, 549 Authentication tree, 466–468, 485, 556–559, 587 Authority revocation list (ARL), 577 Authorization, 3 Authorized subset, 527 Auto-key cipher, 242 Autocorrelation function, 180 Autocorrelation test, 182 Auxiliary-input zero-knowledge, 423 Avalanche effect, 277 Average-case running time, 58 B Baby-step giant-step algorithm, 104–106, 128 ý c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. Index 757 BAN logic, 420, 534, 541 Bandwidth efficiency, 437 Barrett reduction, 603–605, 631 Base representation, 592 Basis, 80 Bayes’ theorem, 51 BEAR block cipher, 282 Beaufort cipher, 241 Beller-Yacobi key transport 2-pass, 514 4-pass, 513 Berlekamp’s -matrix algorithm, 124, 132 Berlekamp-Massey algorithm, 200–201 next discrepancy, 200 Bernoulli trial, 52 Biased, 172 Big-endian, 344 Big-O notation, 58 Big-omega notation, 59 Big-theta notation, 59 Bijection, 7, 50 Binary additive stream cipher, 194 keystream generator, 194 running key generator, 194 Binary alphabet, 11 Binary Euclidean algorithm, 632 Binary extended gcd algorithm, 608–610, 632 Binary gcd algorithm, 606–607, 632 Binary operation, 75 Binary representation, 592 Binary tree, 557 balanced, 558 children, 557 depth of, 558 internal vertex, 557 leaf, 557 parent, 557 root vertex, 557 Binomial coefficient, 52 distribution, 52 theorem, 52 Biometrics, 387, 420 Birthday attack, 352, 369 Birthday problem, 53 Birthday surprise, 53 Bit commitment, 421 Bitzer’s hash function, 374 Black-box, 329, 341, 369, 378 Blakley’s threshold scheme, 538 Blind signature scheme, 475, 487 based on DSA, 487 based on Nyberg-Rueppel, 487 Chaum, 475 × í fair, 487 Blinded message, 475 Blinding function, 475 based on RSA, 475 Blob, 421 Block cipher, 223–282 3-WAY, 281 attacks on differential cryptanalysis, 258 differential-linear, 271 exhaustive key search, 233–234, 273 key clustering attack, 281 linear cryptanalysis, 258 meet-in-the-middle attack, 235 related-key attack, 226, 281 time-memory tradeoff, 236, 273 truncated differentials, 271, 280 BEAR, 282 Blowfish, 281 CAST, 281 classical cipher, 237–250 definition of, 16, 224 DES, 250–259 double DES, 235 FEAL, 259–262 GOST, 282 IDEA, 263–265 iterated, 251 Khafre, 271 Khufu, 271 LION, 282 LOKI’91, 270 Luby-Rackoff, 282 Lucifer, 276 modes of operation, 228–233, 272 ANSI X3.106 standard, 649 ANSI X9.52 standard, 651 CBC with checksum (CBCC), 367 cipher feedback mode (CFB), 231 cipher-block chaining mode (CBC), 230 counter mode, 233 electronic codebook mode (ECB), 228– 230 FIPS 81 standard, 654 ISO 8372 standard, 645 ISO/IEC 10116 standard, 647 output feedback mode (OFB), 232–233 plaintext-ciphertext block chaining (PCBC), 368 Randomized DES (RDES), 278 RC2, 282 RC5, 269–270 round function, 251 SAFER, 266–269 Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. 758 semi-weak keys (of DES), 257 anti-palindromic keys (of DES), 257 SHARK, 281 SKIPJACK, 282, 584 TEA, 282 triple DES, 272 WAKE, 282 Block of a sequence, 180 Blocklength, 224 Blom’s KDS bound, 505 Blom’s key pre-distribution system, 506, 536 Blowfish block cipher, 281 Blum integer, 74–75 Blum-Blum-Shub pseudorandom bit generator, 186– 187, 308 Blum-Goldwasser probabilistic public-key encryption, 308–311 decryption algorithm, 309 encryption algorithm, 309 key generation, 308 security of, 310 Blum-Micali pseudorandom generator, 189 Blundo’s conference KDS bound, 529 Boolean function, 202 algebraic normal form of, 205 correlation immune, 207 nonlinear order of, 205 BPP, 63 Break-backward protection, 496 Brickell-McCurley identification protocol, 423 Broadcast encryption, 528 Bucket hashing, 382 Burmester-Desmedt conference keying, 528 Burst error, 363 C CA, see Certification authority (CA) CA-certificate, 572 Caesar cipher, 239 CALEA, 590 Capability (access control), 570 Capstone chip, 589 Cardinality of a set, 49 Carmichael number, 137 Carry-save adder, 630 Cartesian product, 49 Cascade cipher, 234, 237 Cascade generator -sequence, 221 -cycle, 220 Cascading hash functions, 334 CAST block cipher, 281 patent, 659 CBC, see Cipher-block chaining mode þ ÿ Index CBC-MAC, 353–354, 367 ANSI X9.9 standard, 650 ANSI X9.19 standard, 650 FIPS 113 standard, 654 ISO 8731-1 standard, 652 ISO 9807 standard, 652 ISO/IEC 9797 standard, 646 Cellular automata stream cipher, 222 Certificate ANSI X9.45 standard, 651 ANSI X9.55 standard, 651 ANSI X9.57 standard, 651 caching, 576 chain, 572 directory, 549 pull model, 576 push model, 576 forward, 575 on-line, 576 public-key, see Public-key certificate reverse, 575 revocation, 566, 576–577 RFC 1422, 655 secret-key, see Secret-key certificate symmetric-key, see Symmetric-key certificate X.509 standard, 660 Certificate of primality, 166 Certificate revocation list (CRL), 576–577 Certification, 3 path, 572 policy, 576 topology, 572 Certification authority (CA), 491, 548, 556, 559 Certificational attack, 236 Certificational weakness, 285 CFB, see Cipher feedback mode CFB-64 MAC, 650 Challenge, 397, 409 Challenge-response identification, 397–405, 420– 421 public-key, 403–405 ISO/IEC 9798-3, 404–405 modified Needham-Schroeder, 404 X.509, 404 symmetric-key, 400–403 ISO/IEC 9798-2, 401–402 SKID2, 402 SKID3, 402 Channel, 13 physically secure, 13 secure, 13 secured, 13 unsecured, 13 Characteristic of a field, 77 ý c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. Index Chaum’s blind signature protocol, 475 Chaum-van Antwerpen undeniable signature scheme, 476–478 disavowal protocol, 477 key generation, 476 security of, 478 signature generation, 476 Chebyshev’s inequality, 52 Checksum, 362,
367–368 Chi-square ( ) distribution, 177–179 degrees of freedom, 177 mean of, 177 variance of, 177 Chinese remainder theorem (CRT), 68 Garner’s algorithm, 612–613 Gauss’s algorithm, 68 Chipcard, 387, 424 Chor-Rivest public-key encryption, 302–306, 318 attacks on, 318 decryption algorithm, 303 encryption algorithm, 303 key generation, 303 recommended parameter sizes, 305 security of, 305 Chosen-ciphertext attack, 41, 226, 285 adaptive, 285 indifferent, 285 Chosen-message attack, 433 directed, 482 generic, 482 Chosen-plaintext attack, 41, 226 Cipher, 12 see also Encryption Cipher-block chaining mode (CBC), 230 integrity of IV in, 230 use in public-key encryption, 285 Cipher feedback mode (CFB), 231 as a stream cipher, 233 ISO variant of, 231 Cipher machine, 242–245 Jefferson cylinder, 243 rotor-based machine, 243–245, 276 Enigma, 245 Hagelin M-209, 245 Hebern, 244 Wheatstone disc, 274 Ciphertext, 11 Ciphertext-only attack, 41, 225 Ciphertext space, 11 Claimant, 385, 386 Classical cipher, 237–250, 273–276 cipher machines, see Cipher machine cryptanalysis, 245–250, 275–276 index of coincidence, 248 759 Kasiski’s method, 248 measure of roughness, 249 polyalphabetic substitution cipher, see Polyalphabetic substitution cipher substitution cipher, see Substitution cipher transposition cipher, see Transposition cipher Classical modular multiplication, 600 Classical occupancy problem, 53 Claw-resistant (claw-free), 376, 468 Clipper chip, 584, 589 key escrow, 584 law enforcement access field (LEAF), 584 Clipper key escrow, 654 Clock-controlled generator, 209–212 co-NP, 60 Codebook, 240 Codomain of a function, 6, 50 Collision, 321 pseudo-collision, 371 Collision resistance, 324, 325 Collision resistant hash function (CRHF), 325 Combining function, 205 Common modulus attack on RSA, 289 Commutative ring, 77 Complementation property of DES, 256–257 Complete function, 277 Complexity classes, 59–62 BPP, 63 co-NP, 60 NP, 60 NP-complete, 61 NP-hard, 62 NPC, 61 P, 60 RP, 63 ZPP, 63 Complexity measure 2-adic span, 218 linear complexity, 198–201 maximum order complexity, 217 Turing-Kolmogorov-Chaitin complexity, 217 Ziv-Lempel complexity, 217 Complexity of attacks on a block cipher, 225–227 active complexity, 226 attack complexity, 226 data complexity, 226 passive complexity, 226 processing complexity, 226 storage complexity, 226 Complexity theory, 57–63 Complexity-theoretic security, 43 Compliant, 532 Composite integer, 64 Composition of functions, 19 Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. 760 Computation-resistance (MAC), 325 Computational problems computationally equivalent, 88 polytime reduction, 88 Computational security, 43, 226 Computational zero-knowledge protocol, 407 Computationally equivalent decision problems, 61 COMSET, 421, 536 Conditional entropy, 56 Conditional probability, 51 Conditional transinformation, 57 Conference keying, 528–529, 540 Blundo’s conference KDS bound, 529 Burmester-Desmedt, 528 definition of, 528 Confidentiality, 3, 4, 12 Confirmation, 3 Confounder, 418 Confusion, 20 Congruences integers, 67 polynomials, 79 Conjugate gradient method, 129 Connection polynomial of an LFSR, 196, 204 known versus secret, 204 sparse versus dense, 205 Constrained linear equations problem, 423 Continued fraction factoring algorithm, 126 Continuous random variable, 176 Control vector, 569 patent, 639, 658 Conventional encryption, 15 Coprime, 64 Correcting-block chaining attack, 373 Correlated, 172 Correlation attack, 206, 218 Correlation immunity, 207, 218 Counter mode, 233 CRC-based MAC, 359 Credential, 501 CRHF, see Collision resistant hash function Cross-certificate (CA-certificate), 572 Cross-certificate pair, 573 CRT, see Chinese remainder theorem Cryptanalysis, 15 Cryptanalyst, 15 Cryptographic check value, 363 Cryptographic primitives, 4 taxonomy of, 5 Cryptographically secure pseudorandom bit generator (CSPRBG), 185–187 Blum-Blum-Shub generator, 186–187 Blum-Micali generator, 189 definition of, 171 Index Micali-Schnorr generator, 186 modified-Rabin generator, 190 RSA generator, 185–186 Cryptography definition of, 4 goals of, 4 CRYPTOKI, 656 Cryptology, 15 Cryptoperiod of a key, 553 Cryptosystem, 15 Cut-and-choose protocol, 410, 421 Cycle of a periodic sequence, 180 Cyclic group, 69, 76 generator of, 76 Cyclic redundancy code (CRC), 363 Cyclic register, 220 Cycling attacks on RSA, 289, 313 D Data Authentication Algorithm (DAA), 654 Data Encryption Standard, see DES block cipher Data integrity, 3, 4, 33, 359–368, 383 Data key, 552 Data origin authentication, 3, 4, 25, 359–368, 491 Davies-Meyer hash function, 341 de Bruijn FSR, 203 de Bruijn sequence, 203 De-skewing, 172 DEA, 649 Decimated subsequence, 211 Decision problems, 60 computationally equivalent, 61 polytime reduction, 61 Decryption, 11 Decryption exponent for RSA, 286 Decryption function, 11 DECT, 586 Degrees of freedom, 177 Delay element of an FSR, 202 of an LFSR, 195 Delayed-carry adder, 630 Density of a knapsack set, 120 Derivative of a polynomial, 123 DES block cipher, 250–259, 276–278 ANSI X3.92 standard, 649 attacks on differential cryptanalysis, 258–259 exhaustive key search, 233–234, 272 linear cryptanalysis, 258–259 complementation property, 256–257 decryption algorithm, 255 DESX, 273 double DES, see Double DES ý c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. Index encryption algorithm, 253 expansion permutation, 252 FIPS 46 standard, 654 initial permutation (IP), 252, 277 key schedule decryption, 256 encryption, 255 modes of operation, see Block cipher, modes of operation patent, 636 permuted choices (PC1, PC2), 252 properties and strengths, 256–259 round, 252 S-box, 252 semi-weak key, 257 anti-fixed point of, 257 test vectors, 256 triple-DES, 273 weak key, 257 fixed point of, 257 Designated confirmer signature, 487 Deterministic, 306 Deterministic algorithm, 62 Dickson polynomial, 314 Dickson scheme, 314 Dictionary attack, 42 Difference of sets, 49 Differential chaining attack, 375 Differential cryptanalysis of block ciphers, 258, 271, 278–280 Differential-linear cryptanalysis, 271 Diffie-Hellman key agreement, 515–520, 522–524 ANSI X9.42 standard, 651 composite modulus, 537 patent, 637 Diffie-Hellman problem, 113–114 composite moduli, 114, 131 generalized, 113 Diffie-Lamport one-time signature scheme, 485 Diffusion, 20 Digital envelope, 550 Digital fingerprint, 321 Digital signature, see Signature Digital Signature Algorithm (DSA), 452–454, 483 ANSI X9.30-1 standard, 651 FIPS 186 standard, 655 key generation, 452 patent, 640, 658 security of, 453 signature generation, 452 signature verification, 453 use and throw coupons, 483 Dimension of a vector space, 80 Dirichlet theorem, 135 761 Disavowal protocol, 477 Discrete Fourier Transform (DFT), 631 Discrete logarithms, 103–113 baby-step giant-step algorithm, 104–106 composite moduli, 114 exhaustive search, 104 for class groups, 130 for elliptic curves, 130 for hyperelliptic curves, 130 function field sieve, 129 generalized problem, 103 heuristic running time, 129 in subgroups of , 113 index-calculus algorithms, 109–112 lambda method, 128 number field sieve, 128 Pohlig-Hellman algorithm, 107–109 Pollard’s rho algorithm, 106–107 problem definition, 103 rigorously analyzed algorithms, 129 security of individual bits, 116 Divisible electronic coin, 487 Division of integers, 63 of polynomials, 79 Division algorithm for integers, 64 for polynomials, 78 Dixon’s algorithm, 95, 127 DNA computer, 130 Domain of a function, 6, 50 Double DES, 235 Double spending, 487 Double-length MDC, 339 DSA, see Digital Signature Algorithm Dynamic key establishment, 491 Dynamic secret sharing scheme, 527 ìéÞ E E-D-E triple encryption, 235, 272 E-E-E triple encryption, 272 Eavesdropper, 13, 495 ECA, see Elliptic curve factoring algorithm ECB, see Electronic codebook mode Effective key size, 224 Electronic cash divisible, 487 untraceable, 487 Electronic codebook mode (ECB), 228–230 ElGamal key agreement, 517 ElGamal public-key encryption, 294–298 generalized decryption algorithm, 297 encryption algorithm, 297 Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone. 762 in Index ì key éÞ generation, 297 decryption algorithm, 295 encryption algorithm, 295 key generation, 294 recommended parameter sizes, 296 security of, 296 ElGamal signature scheme, 454–459, 484 generalized key generation, 458 signature generation, 458 signature verification, 458 in key generation, 454 security of, 455–456 signature generation, 454 signature verification, 454 signature verification, 618 variants of, 457 Elliptic curve discrete logarithm problem, 130 ElGamal public-key encryption, 297 in public-key cryptography, 316 patents, 659 RSA analogue, 315 supersingular curve, 130, 316 Elliptic curve factoring algorithm (ECA), 94, 125 implementation reports, 126 Elliptic curve primality proving algorithm, 145 Encrypted key exchange (EKE), 538 Encryption, 11 see also Block cipher see also Public-key encryption see also Stream cipher Encryption exponent for RSA, 286 Encryption function, 11 Encryption scheme, 12 breakable, 14 Enemy, 13, 495 Enigma, 245, 276 Entity, 13 Entity authentication, 3, 386, 491 ANSI X9.26 standard, 651 FIPS 196 standard, 655 ISO 11131 standard, 652 ISO/IEC 9798 standard, 401–402, 404–405, 421, 647 see also Identification Entropy, 56–57, 246 Ephemeral secret, 494 Equivalence class, 68, 79 Equivocation, 56 Error-correcting code, 298, 363, 506 Escrowed Encryption Standard (EES) ìéÞ FIPS 185, 654 ESIGN signature scheme, 473–474, 486 key generation, 473 patent, 638, 658 security of, 474 signature generation, 473 signature verification, 473 Euclidean algorithm for integers, 66 for polynomials, 81–83 Euler liar, 138 Euler phi function ( ), 65 Euler pseudoprime, 138 Euler witness, 137 Euler’s criterion, 137 Euler’s theorem, 69 Exclusive-or (XOR), 20 Exhaustive key search, 14, 233–234, 272 Existential forgery, 30, 326, 432  (exponential function), 50 Expected running time, 63 Explicit authentication, 492 Exponent array, 617 Exponent recoding, see Exponentiation Exponential-time algorithm, 59 Exponentiation, 613–629, 633–634 addition chains, 621 exponent recoding, 627–629 signed-digit representation, 627–628 string-replacement representation, 628– 629 fixed-base comb method, 625–627 fixed-base Euclidean method, 624–625 fixed-base windowing method, 623–624 left-to-right binary method, 615 left-to-right -ary method, 615 modified left-to-right -ary method, 616 Montgomery method, 619–620 repeated square-and-multiply algorithm, 71, 84 right-to-left binary method, 614 simultaneous multiple, 617–618 sliding-window method, 616 vector-addition chains, 622–623 Extendable secret sharing scheme, 526 Extended Euclidean algorithm for integers, 67 for polynomials, 82 Extended Riemann Hypothesis (ERH), 165 Extension field, 77 Extractor, 406 Ì è F Factor base, 94, 109 ý c 1997 by CRC Press, Inc. — See accompanying notice at front of chapter. è Index Factoring integers, see Integer factorization Factoring polynomials, see Polynomial factorization Fail-stop signature scheme, 478–481, 488 Heijst-Pedersen, 478–481 Fair blind signature scheme, 487 Fair cryptosystems, 640–641, 658 for Diffie-Hellman key agreement, 641 patent, 640 FEAL block cipher, 259–262, 278–279 attacks on, 278–279 FEAL decryption algorithm, 261 FEAL-8 encryption algorithm, 261 FEAL-8 key schedule, 261 FEAL-N, 262 FEAL-NX, 262 patent, 639 test vectors, 262 Feedback shift register (FSR), 195–203 de Bruijn, 203 definition of, 202 delay element of, 202 feedback bit of, 202 feedback function of, 202 Feedback with carry shift register (FCSR), 217– 218, 222 initial state of, 202 linear feedback shift register, see Linear feedback shift register (LFSR) non-singular, 203 nonlinear feedback shift register, 202 output sequence of, 202 stage of, 202 Feedback with carry shift register (FCSR), 217–218, 222 Feige-Fiat-Shamir identification protocol, 410–412, 422 Feige-Fiat-Shamir signature scheme, 447–449, 483 identity-based modification, 449 key generation, 447 security of, 448 signature generation, 448 signature verification, 448 Feistel cipher, 251, 276 Fermat liar, 136 Fermat number, 143, 166 Fermat witness, 136 Fermat’s primality test, 136 Fermat’s theorem, 69 Fiat-Shamir identification protocol basic version, 408 patent, 638, 658 Fiat-Shamir signature scheme, 483 patent, 638, 658 763 Field, 77 characteristic of, 77 definition of, 77 extension field of, 77 finite, see Finite field subfield of, 77 Filtering function, 208 Finite field, 80–85 definition of, 80 order of, 80 polynomial basis, 83 FIPS, 654–655, 661 ordering and acquiring, 656 FIPS 186 pseudorandom bit generator, 174–175 FISH stream cipher, 222 Fixed-point chaining attack, 374 Floyd’s cycle-finding algorithm, 91, 125 Forced delay attack, 417 Formal methods, 534, 541 Forward certificate, 575 Forward error correction, 363 Forward search attack, 34, 42, 288, 420 Fractionation, 276 Frequency distribution of English digrams, 247 of single English characters, 247 Frequency test, 181 Fresh key, 494 Function, 6–10, 50 bijection, 7 composition of, 19 definition of, 6 injective, 46 inverse, 7 involution, 10 one-to-one, 7 one-way, 8 onto, 7 permutation, 10 surjective, 46 trapdoor one-way, 9 Function field sieve, 129 Functional diagram, 6 Functional graph, 54 component size, 55 cycle length, 55 predecessors size, 55 rho-length, 55 tail length, 55 tree size, 55 Functionally trusted third party, 39 G Gap of a sequence, 180 Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.