?UBLIC-KEY CRYPTOGFAPHY
`NIST Special Publication 800-2
`
`J ames Nechva t a l
`Securi t y Technology Group
`Nati o n a l Compu ter Systems Labora t o r y
`National I nstitu te of Standards and Tectnology
`Gait hersburg, MD 20899
`
`April 1 991
`
`-- 1 --
`
`MasterCard, Exh. 1005, p. 1
`
`

`
`tnk)
`riTLE AND SUBTITLE
`blic-Key Cryptography (NIST Special Publication 800-2)
`
`1 4/1/1991
`
`I Report 4/1/1991
`
`5. FUNDING NUMBERS
`
`'UTHOR(S)
`chvatal, James
`
`'ERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES)
`
`8. PERFORMING ORGANIZATION
`REPORT NUMBER
`
`curity Technology Group,
`tional Computer Systems
`boratory, NIST
`i then;l:.mrg, MD
`
`20899
`
`SPONSORING I MONITORING AGENCY NAME(S) AND ADDRESS(ES)
`
`TAC
`90 Fairview Park Drive
`lls Church, VA
`22042
`
`SUPPLEMENTARY NOTES
`
`10. SPONSORING I MONITORING
`AGENCY REPORT NUMBER
`
`'·DISTRIBUTION I AVAILABILITY STATEMENT
`proved for public release; Distribution unlimited
`
`12b. DISTRIBUTION CODE
`
`A
`
`ABSTRACT (Maximum 200 Words)
`
`is publication presents a state-of-the-art survey of public-key cryptography circa 1988-
`90.
`In doing so, it covers a number of different topics including: the theory of public-
`u cryptography, comparisons to conventional (secret-key) cryptography, a largely self-
`ntained summary of relevant mathematics, a survey of major existing public-key systems,
`exploration of digital signatures and hash functions, a survey of public-key
`plementations in networks, an introductiop to zero-knowledge protocols and probabilistic
`cryption, and an exploration of security issues and key sizes.
`
`SUBJECT TERMS
`TAC Collection, public key cryptography, systems, networks
`
`SECURITY CLASSIFICATION
`:)FREPORT
`UNCLASSIFIED
`
`18. SECURITY CLASSIFICATION
`OF THIS PAGE
`UNCLASSIFIED
`
`19. SECURITY CLASSIFICATION
`OF ABSTRACT
`UNCLASSIFIED
`
`N 7540·01-280·5500
`
`15. NUMBER OF PAGES
`
`148
`
`16. PRICE CODE
`
`20. LIMITATION OF ABSTRACT
`
`UNLIMITED
`
`Standard Form 298 (Rev. 2-89)
`Prescribed by ANSI Sid. Z39·18
`298·102
`
`-- 2 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 2
`
`

`
`PREFACE
`
`This publication presents a state-of-the-art survey of public(cid:173)
`key cryptography circa 1988 - 1990. In doing so, it covers a number
`of different topics including:
`
`1. The theory of public-key cryptography.
`
`2. Comparisons to conventional (secret-key) cryptography.
`
`3. A largely self-contained summary of relevant mathematics.
`
`4. A survey of major existing public-key systems.
`
`5. An exploration of digital signatures and hash functions.
`
`6. A survey of public-key implementations in networks.
`
`7. An introduction to zero-knowledge protocols and
`probabilistic encryption.
`
`8. An exploration of security issues and key sizes.
`
`The treatment of public-key cryptography in this publication
`includes both theory and practice. Much of the existing published
`work, including those documents listed in the references, treats
`either the theory or specific systems/implementations, but not
`both. The viewpoint here is that the theory and practice are
`inseparable.
`
`Any mention of commercial products is for purposes of
`explanation and illustration only. Also, the selection of
`cryptosystems and hash functions mentioned in this publication
`serve only to provide examples. Such identification does not imply
`recommendation or endorsement by the National Institute of
`Standards and Technology, nor does it imply that systems or
`functions identified are necessarily the best available for the
`purpose.
`
`The focus is on issues such as criteria for systems and
`protocols for usage. These are presumably long-term, in contrast,
`to the set of existing public-key systems which is more volatile.
`Thus we provide information which will hopefully be of use to
`implementors of systems, but the frameworks we develop are
`versatile enough to be relevant in a variety of settings. The
`latter may include, for example, both electronic mail systems and
`electronic fund transfer systems.
`
`The core of this exposition is sections 1 to 5. Sections 1 to
`3 cover the fundamentals of public-key cryptography and the related·
`topics Of hash functions and digital signatures. Extensive coverage
`of key management is also included, with a focus on certificate(cid:173)
`based management. Section 4 gives some examples of public-key
`
`-- 3 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 3
`
`

`
`systems and hash functions. Section 5 gives some examples of actual
`or proposed implementations of public-key cryptography. The major
`example is the International Organization for Standardization (ISO)
`authentication framework.
`
`Section 6 gives a sample proposal for a local-area network
`implementation of public-key cryptography. It draws heavily on the
`work of ISO.
`
`A variety of topics are covered in the appendices, including a
`summary of relevant mathematics and algorithms. Also included is
`a brief introduction to zero-knowledge protocols, probabilistic
`encryption and identity-based public-key systems.
`
`In the following, letters refer to appendices; e.g. lemma G.2.1
`refers to a
`lemma appearing in section 2 of appendix G.
`
`The author wishes to thank Dr. Ronald L. Rivest, Dr. Gustavus
`Simmons, and Dr. Dennis Branstad for providing many comments and
`suggestions, and Dr. Burton S. Kaliski Jr. for providing
`information on implementations of the RSA public-key system. The
`paper was edited by Miles Smid.
`
`This paper was supported in part by the United States Department
`of Computer-Aided Logistics Supports, Department of Defense.
`
`-- 4 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 4
`
`

`
`CONTENTS
`
`1. Cryptosystems and cryptanalysis ............................... 1
`
`1.1 Requirements for secrecy .................................. 2
`1.2 Requirements for authenticity and integrity ........... · .... 4
`1. 3 Conventional systems ...................................... 5
`1.4 Example of a conventional cipher: DES ..................... 5
`1.5 Another conventional cipher: exponentiation ............... 6
`1. 6 Public-key cryptosyslems .................................. 7
`1.6.1 Secrecy and authenticity .......................... ,8
`1.6.2 Applicability and limitations ..................... 10
`
`2. Key management ................. , .............................. 12
`
`2.1 Secret-key management .................................... 12
`2.2 Public distribution of secret keys ....................... 13
`2.3 Management of public components in a public-key system ... 15
`2. 3. 1 Use of certificates ............................... 16
`2.3.2 Generation and storage of component pairs ......... 17
`2.3.3 Hardware support for key management ............... 18
`2.4 Using public-key systems for secret key distribution ..... 19
`2.4.1 A protocol for key exchange ....................... 20
`2.5 Protocols for certificate-based key management ........... 22
`2.5.1 Certificate management by a central authority ..... 22
`2.5.2 Decentralized management ......... , ................ 23
`2.5.3 A phone-book approach to certificates ............. 24
`
`3. Digital signatures and hash functions, ....................... 25
`
`3.1 Public-key implementation of signatures .................. 27
`3 .1. 1 Signing messages .................................. 27
`3.1.2 The issue of nonrepudiation ....................... 29
`3.1.3 The issue of proof of delivery ................... ,30
`3.2 Hash functions and message digests ...................... ,31
`3.2.1 Usage of hash functions ........................... 33
`3.2.2 Relation to one-way functions ..................... 33
`3.2.3 Weak and strong hash functions .................... 34
`3.3 Digital signatures and certificate-based systems ......... 35
`
`4. Examples of public-key systems and hash functions ............ 37
`
`4.1 The RSA public-key scheme ................................ 39
`4.1.1 Choice of p and q ................................. 41
`4.1.2 Further notes on implementation ................... 42
`4 .1. 3 Security of RSA ....... , ........................... 43
`4.1.3.1 Restrictions on p and q .................. 43
`4.1.3.2 Notes on factoring ....................... 44
`4.1.4 Low-exponent versions of RSA ...................... 45
`
`-- 5 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 5
`
`

`
`4.2 Other public-key systems ................................. 46
`4. 2. 1 Knapsack systems .................................. 4 7
`4.2.2 The ElGamal signature scheme ...................... 49
`4. 3 Examples of hash functions ............................... 53
`4. 3. 1 Merkle 1 s meta-method .............................. 53
`4. 3. 2 Coppersmith 1 s attack on R.abin-type functions ...... 56
`4.3.3 Quadratic congruentia1 hash functions ............. 57
`4.4 Hardware and software support ............................ 58
`4.4.1 Design considerations for RSA chips ............... 58
`4.4.2 Proposed designs for RSA chips .. , ................. 59
`
`5. Implementations of public-key cryptography ................... 61
`
`5. 1 MITRE NET ... , . , .. , . , , , , ....... , , , ........ , ......... , , ..... 61
`5.2 ISDN ..................................................... 62
`5. 2 . 1 Keys ....................................... , ...... 62
`5. 2. 2 Calling .................................... , ...... 63
`5.3 ISO Authentication Framework ............................. 64
`5.3.1 Use of certificates ................... , ........... 64
`5. 3. 2 Certification paths .............. , ................ 65
`5.3.3 Expiration and revocation of certificates ........ ,66
`5. 3. 4 Authentication protocols ............. , ............ 67
`5. 3. 5 Further notes,, .... ,,., ........... ,, ....... ,,, .... 71
`5. 4 DARPA-Internet ..... ,,, .... , ....... ,.,, ...... ,.,,, .... ,, .. 71
`
`6. A sample proposal for a LAN implementation., ................. 73
`
`6.1 Integration into a network ......... , .. , ........ , .. , ...... 73
`6. 2 Security threats .. , .... , ........... , .. , .... , .. , ........ ,. 74
`6.3 Security services., ......... , ............................ 74
`6. 4 Security mechanisms .. , ............. , ........... , ......... 7 5
`6.5 Criteria for cryptosystems ............................. , .76
`6.5.1 Security .......................................... 77
`6.5.2 Numerical criteria ................................ 77
`6.5.3 Other criteria ..................................... 78
`6.6 Criteria for hash functions .............................. 78
`6.7 Example of a LAN security framework ........ , ............. 78
`6. 7 . 1 Key management. , .................................. 7 9
`6.7.2 Component generation and storage .... , ............... 79
`6. 7. 3 Secret-key generation ............ .' ................ 7 9
`6.7.4 Issuance and distribution of certificates .... ~ .... 80
`6.7.5 Compromised or invalidated certificates ... , ....... 80
`6. 7. 6 Authentication .................................... 81
`
`Appendix A. Mathematical and computational aspects ... : .......... 83
`
`A.1 Computational complexity and cryptocomplexity ............ 83
`A.2 Classical complexity theory .............................. 84
`A.3 Public-key systems and cryptocomplexity .................. 84
`A. 4 Probabilistic algorithms ..... , . , ......................... 85
`A.S Status of some relevant problems ......... ,, .............. 86
`
`-- 6 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 6
`
`

`
`Appendix B. Algorithms and architectures ........................ 89
`
`B.l Technology ........ , ..... ,,.,,, ... ,, .......... , ... ,., ... , .89
`B. 2 Computing modes ... , .. , .......... , .... , ........... , , ...... 90
`B.3 Some relevant algorithms and implementation ... , .... , ..... 92
`B.3.1 Quadratic sieve factoring algorithm ......... , ... , .. 92
`B.3.2 Computations in finite fields .... ,,., .. , ........... 93
`B. 3. 3 Other .algorithms .. ,,.,,, ......... , ................. 94
`B. 4 Application-specific architectures ..... , . , ............... 94
`B.4.1 Systolic and wavefront arrays ......... , ............ 94
`B.4.2 Proposal for a quadratic sieve machine ............. 95
`B. 4. 3 Massively parallel machines, ......... , ............. 95
`
`Appendix C. The classical theory of computation ................. 97
`
`C .1 Turing machines .................. , ......... , , ..... , ...... 97
`C.2 Nondeterministic Turing machines ......................... 98
`C.3 Computational complexity ......... ,,, ..................... 99
`
`Appendix D. The theory of probabilistic computing .............. 101
`
`Appendix E. Breaking knapsacks ..... , .. , .... ,,,,,, .. ,,,, ... ,,,,, .103
`
`Appendix F, Birthday attacks, , . , ........... , ....... , ........... 105
`
`Appendix G. Modular arithmetic and Galois fields ........... ,., .107
`
`G.l The Euler Phi function .. ,., ....... ,,, ... ,, ....... , ... , .. 108
`G.2 The Euler-Fermat Theorem.,,, ..... , .... , ................. 108
`G.3 Galois fields ............ , .. , ........................... 110
`
`Appendix H. Euclid's algorithm ........ ,,,, .. , ....... , .......... 111
`
`Appendix I. The Chinese Remainder Theorem ... ,, .... , .......... , .113
`
`Appendix J. Quadratic residues and the Jacobi symbol ....... ,, .. 115
`
`J.1 Quadratic residues modulo a prime ......... , ......... , ... 115
`J. 2 The Jacobi symbol ................... , ............ , , ..... 116
`J.3 Square roots modulo a prime ... ,, ..... , ...... ,., ......... 117
`J.4 Quadratic residuosity modulo a prime, ................... 118
`
`Appendix K. Primitive roots and discrete logarithms ........ , ... 119
`
`-- 7 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 7
`
`

`
`Appendix L. Primality testing .............. , ................... 123
`
`1.1 The Solovay/Strassen test ... , ...... , .................... 124
`L. 2 Lehman's test ........................................... 125
`L. 3 The Miller /Rab.in test ................................... 12 6
`
`Appendix M. Mathematics of RSA and other exponential systems ... 127
`
`Appendix N. Quadratic residuosity modulo a composite ........... 129
`
`N.1 Characterizing quadratic residues, ...................... 129
`N.2 The Jacobi symbol once more ............... , ............. 130
`N.3 Quadratic residuosity and factoring .... , .... , ........... 132
`N.4 Quadratic residuosity and Blum integers ..... , ..... ,, .... 133
`
`Appendix 0. An introduction to zero-knowledge .... ,., ........... 137
`
`Appendix P. Alternatives to the Diffie/Hellman model ........... 143
`
`P.1 Probabilistic encryption .......... , ....... , ............. 143
`P.2 Identity-based schemes ...................... , ........... 145
`
`References ............... , .......... , .............. ·, ............ 147
`
`-- 8 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 8
`
`

`
`LIST OF ILLUSTRATIONS
`
`Figure 1. Adaptive Chosen Plaintext Attack ........................ 3
`
`Figure 2. Using Public-Key for Secrecy and Authenticity .......... 10
`
`Figure 3. The Diffie/Hellman Key Exchange ........................ 15
`
`Figure 4. A Protocol for Real-Time Authentication ................ 21
`
`Figure 5. A Protocol for Signing with Hash Function and Secrecy .. 28
`
`Figure 6. Using RSA for Authenticity and Secrecy ................. 40
`
`Figure 7. The ElGamal Signature Algorithm ........................ 51
`
`Figure B. One-Way Authentication Protocol .......... ,., ........... 69
`
`-- 9 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 9
`
`

`
`1. Cryptosystems and cryptanalysis.
`
`Cryptography deals with the transformation of ordinary text
`(plaintext) into coded form (ciphertext) by encryption, and
`transformation of ciphertext into plaintext by decryption. Normally
`these transformations are parameterized by one or more keys. The
`motive for encrypting text is security for transmissions over
`insecure channels.
`
`Three of the most important services provided by cryptosystems
`are secrecy, authenticity, and integrity. Secrecy refers to denial
`of access to information by unauthorized individuals. Authenticity
`refers to validating the source of a message; i.e., that it was
`transmitted by a properly identified sender and is not a replay of
`a previously transmitted message. Integrity refers to assurance
`that a message was not modified accidentally or deliberately in
`transit, by replacement, insertion or deletion. A fourth service
`which may be provided is nonrepudiation of origin, i.e., protection
`against a sender of a message later denying transmission, Variants
`of these services, and other services, are discussed in [IS0-87].
`
`Classical cryptography deals mainly with the secrecy aspect. It
`also treats keys as secret. In the past 15 years two new trends
`have emerged:
`
`a. Authenticity as a consideration which rivals and sometimes
`exceeds secrecy in importance.
`
`b. The notion that some key material need not be secret.
`
`The first trend has arisen in connection with applications such
`as electronic mail systems and electronic funds transfers. In such
`settings an electronic equivalent of the handwritten signature may
`be desirable. Also, intruders into a system often gain entry by
`masquerading as legitimate users; cryptography presents an
`alternative to password systems for access control,
`
`The second trend addresses the difficulties which have
`traditionally accompanied the management of secret keys. This may
`entail the use of couriers or other costly, inefficient and not
`really secure methods. In contrast, if keys are public the task of
`key management may be substantially simplified.
`
`An ideal system might solve all of these problems concurrently,
`i.e., using public keys; providing secrecy; and providing
`authenticity. Unfortunately no single technique proposed to date
`has met all three criteria. Conventional systems such as DES
`require management of secret keys; systems using public key
`components may provide authenticity but are inefficient for bulk
`encryption of data due to low bandwidths.
`
`Fortunately, conventional and public-key systems are not
`mutually exclusive; in fact they can complement each other. Public(cid:173)
`key systems can be used for signatures and also for the
`
`-- 10 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 10
`
`

`
`distribution of keys used in systems such as DES. Thus it is
`possible to construct hybrids of conventional and public-key
`systems which can meet all of the above goals: secrecy,
`authenticity and ease of key management.
`
`For surveys of the preceding and related topics see, e.g.,
`( [BRAS88], [COPP87], [DENN83], [DIFF82], [DIFF79], [KLIN79], [KONHBl],
`[LEMP79], [MASS88], [MERK82], [POPE78], [POPE79], [SAL085], [SIMM79]).
`More specialized discussions of public-key cryptography are given,
`e.g., in ( [DIFFBBJ, [LAKS83], [MERKB2b]). Mathematical aspects are
`covered, e.g., in ( [KRAN86], [PATT87]).
`
`In the following, E and D represent encryption and decryption
`transformations, respectively. It is always required that D(E(M))
`= M. It may also be the case that E(D(M)) .= M; in this event E or
`D can be employed for encryption. Normally D is assumed to be
`secret, but E may be public. In addition it may be assumed that E
`and D are relatively easy to compute when they are known.
`
`1.1 Requirements for secrecy.
`
`Secrecy requires that a cryptanalyst (i.e., a would-be intruder
`into a cryptosystem) should not be able to determine the plaintext
`corresponding to given ciphertext,· and should not be able to
`reconstruct D by examining ciphertext for known plaintext. This
`translates int'o two requirements for a cryptosystem to provide
`secrecy:
`
`a. A cryptanalyst should not be able to determine M from
`E(M); i.e., the cryptosystem should be immune to
`ciphertext-only attacks.
`
`b. A cryptanalyst should not be able to determine D given
`{E(Mi)) for any sequence of plaintexts {Ml,M2, ... };
`i.e. the cryptosystem should be immune to known-plaintext
`attacks. This should remain true even when the
`cryptanalyst can choose {Mi} (chosen-plaintext attack),
`including the case in which the cryptanalyst can inspect
`(E(Ml), ... ,E(Mj)} before specifying Mj+l (adaptive
`chosen-plaintext attack) .
`
`Adaptive chosen plaintext attack is illustrated below.
`
`i
`
`0
`
`I
`I
`1/
`1\
`I
`
`i
`
`I
`:= i + 1 1/
`1\ -/1\
`I
`
`-- 11 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 11
`
`

`
`___ \II ___ _
`
`choose M(i+l)
`
`I
`I
`___ \II ______ _
`
`compute E(M(i+l))
`
`I
`
`I
`___ \II ______ _
`
`inspect E(M(l)), .. ,E(M(i+l))
`
`I
`
`I
`
`I
`I
`I
`
`I
`I
`I
`I
`
`I
`
`I
`
`I
`I
`I
`
`I
`
`I
`I
`I
`
`I
`\II
`I
`\
`I
`\
`
`I
`I
`I
`I
`\-------,,-------\ I
`I
`I
`continue
`\ I
`I
`stop I
`\II
`
`Figure 1. Adaptive Chosen Plaintext Attack
`
`To illustrate the difference between these two categories, we
`use two examples. First, suppose E (M) ~ M3 mod N, N = p
`·k q, where
`p and q are large secret primes. Then (cf, sec. 4) it is infeasible
`for a cryptanalyst to determine D, even after inspecting numerous
`pairs of the form {M,E(M)}. However, an eavesdropper who intercepts
`E(M) = 8 can conclude M = 2. Thus a ciphertext-only attack may be
`feasible in an instance where known- or chosen-plaintext attack is
`not useful.
`
`5M mod N where N is secret.
`On the other hand, suppose E(M)
`Then interception of E(M) would not reveal MorN; this would
`remain true even if several ciphertexts were intercepted. However,
`an intruder who learns that E(l2) ~ 3 and E(l6) ~ 4 could conclude
`N = 19. Thus a known- or chosen-plaintext attack may succeed where
`a ciphertext-only attack fails.
`
`Deficiencies in (a), i.e., vulnerability to ciphertext-only
`attack, can frequently be corrected by slight modifications of the
`encoding scheme, as in the M3 mod N encoding above. Adaptive
`chosen-plaintext is often regarded as the strongest attack.
`
`Secrecy ensures that decryption of messages is infeasible.
`However, the enciphering transformation E is not covered by the
`above requirements; it could even be public, Thus secrecy, per se,
`leaves open the possibility that an intruder could masquerade as
`a legitimate user, or could compromise the integrity of a message
`
`-- 12 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 12
`
`

`
`by altering it. That is, secrecy does not imply authenticity/
`integrity.
`
`1.2 Requirements for authenticity and integrity.
`
`Authenticity requires that an intruder should not be able to
`masquerade as a legitimate user of a system. Integrity requires
`that an intruder should not be able to substitute false ciphertext
`for legitimate ciphertext. Two minimal requirements should be met
`for a cryptosystem to provide these services:
`
`a. It should be possible for the recipient of a message to
`ascertain its origin.
`
`b. It should be possible for the recipient of a message to
`verify that it has not been modified in transit.
`
`These requirements are independent of secrecy. For example, a
`message M could be encoded by using D instead of E. Then assuming
`D is secret, the recipient of C = D(M) is assured that this message
`was not generated by an intruder. However, E might be public; C
`could then be decoded by anyone intercepting it.
`
`A related service which may be provided is nonrepudiation; i.e.,
`we may add a third requirement if desired:
`
`c. A sender should not be able to deny later that he sent a
`message.
`
`We might also wish to add:
`
`d. It should be possible for the recipient of a message to
`detect whether it is a replay of a previous transmission.
`
`1.3 Conventional systems.
`
`In a conventional cryptosystem, E and D are parameterized by a
`single key K, so that we have DK(EK(M))
`M. It is often the case
`that the algorithms for obtaining DK and EK from K a~e public,
`although both EK and DK are secret. In this event the security of
`a conventional system depends entirely on keeping K a secret. Then
`secrecy and authenticity are both provided: if two parties share
`a secret K,
`they can send messages to one another which are both
`private (since an eavesdropper cannot compute DK(C)) and
`authenticated (since a would-be masquerader cannot compute EK(M))
`In some cases (e.g., transmission of a random bit string), this
`does not assure integrity; i.e., modification of a message en route
`may be undetected. Typically integrity is provided by sending a
`
`-- 13 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 13
`
`

`
`compressed form of the message (a message digest) along with the
`full message as a check.
`
`Conventional systems are also known as one-key or symmetric
`systems [SIMM79].
`
`1.4 Example of a conventional cipher: DES.
`
`The most notable example of a conventional cryptosystem is DES
`(Data Encryption Standard). It is well-documented (e.g.
`[DENN83], [EHRS78], [NATI77], [NATI80], [NATI81], [SMIDSJ.], [SMID88b])
`and will not be discussed in detail here, except to contrast it
`with other ciphers. It is a block cipher, operating on 64-bit
`blocks using a 56-bit key. Essentially the same algorithm is used
`to encipher or decipher. The transformation employed can be written
`P-l(F(P(M))), where Pis a certain permutation and F is a certain
`function which combines permutation and substitution. Substitution
`is accomplished via table lookups in so-called S-boxes.
`
`The important characteristics of DES from the standpoint of this
`exposition are its one-key feature and the nature of the operations
`performed during encryption/decryption. Both permutations and table
`lookups are easily implemented, especially in hardware. Thus
`encryption rates exceeding 40 Mbit/sec have been obtained (e.g.,
`[BANE82], [MACM81]). This makes DES an efficient bulk encryptor,
`especially when implemented in hardware.
`
`The security of DES is produced in classical fashion:
`alternation of substitutions and permutations. The function F is
`obtained by cascading a certain function f(x,y), where xis 32 bits
`andy is 48 bits. Each stage of the cascade is called a round. A
`sequence of 48-bit strings {Ki) is generated from the key. Let L(x)
`and R(x) denote the left and right halves of x, and let XOR denote
`exclusive-or. Then if Mi denotes the output of stage i, we have
`
`L(Mi)
`
`R(Mi-1),
`
`R(Mi)
`
`L(Mi-1) XOR f(L(Mi),Ki).
`
`The hope is that after 16 rounds, the output will be
`statistically flat; i.e., all patterns in the initial data will be
`undetectable.
`
`1.5 Another conventional cipher: exponentiation.
`
`Pohlig and Hellman [POHL78] noted a type of cipher which
`deviated from the classical methods such as transposition and
`substitution. Their technique was conceptually much simpler. Let
`GCD denote greatest common divisor (app. G). Suppose p > 2 is
`a prime and suppose K is a key in [J.,p-1) with GCD(K,p-1) = 1
`(i.e., K is relatively prime to p-1). If M is plaintext in [J.,p-
`
`-- 14 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 14
`
`

`
`1], an encryption function E may be defined by
`
`E(M)
`
`MK mod p.
`
`,~ 1 implies (lem. G.1) that we can
`Now the condition GCD(K,p-1)
`find I with I * K 6 1
`(mod p-1). Note that I is not a separate key;
`I is easily derived from K or vice-versa (app. H). We may set
`
`D(C) = CI mod p.
`
`It may then be shown (cor. G.2.3) that D(E(M)) = M, as required.
`Furthermore, E(D(C)) =Cas well; i.e., E and Dare inverse
`functions. This makes exponentiation a versatile cipher; in
`particular, we can encipher with D as well as E. Later we will note
`that this can be useful in authentication. However, Pohlig and
`Hellman used the above only as an example of a conventional
`cryptosystem. That is, since I is easily derived from K, both E and
`Dare generated by the single, secret, shared key K. In section 4.1
`we will see that if p were replaced by a product of two primes,
`derivation of I from K would be non-trivial. This would cause the
`key material to be split into two portions.
`
`Despite the relative simplicity of the definitions of E and D,
`they are not as easy to compute as their counterparts in DES. This
`is because exponentiation mod p is a more time-consuming operation
`than permutations or table lookups if p is large.
`
`Security of the system in fact requires that p be large. This
`is because K should be nondeterminable even in the event of a
`known-plaintext attack. Suppose a cryptanalyst knows p, M, c, and
`furthermore knows that C = MK mod p for some K. He should still be
`unable to find K; i.e., he should not be able to compute discrete
`logarithms modulo p. At present there are no efficient algorithms
`for the latter operation: the best techniques now available take
`time (e.g.,
`[ADLE7 9], [COPPS 6])
`
`exp (c ((log p) (log log p)) 1/2).
`
`Computing modulo p is equivalent to using the Galois field
`GF(p); .it is possible to use GF(pn) instead (app. G). There are
`both advantages and disadvantages to the extension. Arithmetic in
`.is generally easier if n > 1, and especially so in GF(2n).
`GF(pn)
`On the other hand, taking discrete logarithms in GF(pn) is also
`easier. The case of small n is treated in [ELGA85b]. The greatest
`progress has been made for the case p = 2 (e.g.,
`[BLAK84], [COPP84]). In [COPP84] it is shown that discrete
`logarithms in GF(2n) can be computed .in time
`
`exp (c * n1/3 * (log n) 2/3).
`
`-- 15 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 15
`
`

`
`For a survey of the discrete logarithm problem see, e.g.,
`[ADLE86] I [COPP87] I [MCCU89] I [ODLY84b].
`
`1.6 Public-key cryptosystems.
`
`The notion of public-key cryptography was introduced by Diffie
`and Hellman [DIFF76b]; for a ·history see (DIFFBB]. Public-key
`systems, also called two-key or asymmetric (SIMM79], differ from
`conventional systems in that there is no longer a single secret key
`shared by a pair of users. Rather, each user has his own key
`material. Furthermore, the key material of each user is divided
`into two portions, a private component and a public component. The
`public component generates a public transformation E, and the
`private component generates a private transformation D. In analogy
`to the conventional case E and D might be termed encryption and
`decryption functions, respectively. However, this is imprecise: in
`a given system we may have D(E(M))
`M, E(D(M)) = M, or both.
`
`A requirement is that E must be a trapdoor one-way function.
`One-way refers to the fact that E should be easy to compute from
`the public key material but hard to invert unless one possesses the
`corresponding D, or equivalently, the private key material
`generating D. The private component thus yields a "trapdoor" which
`makes the problem of inverting E seem difficult from the point of
`view of the cryptanalyst, but easy for the (sole legitimate)
`possessor of D. For example, a trapdoor may be the knowledge of the
`factorization of an integer (see sec. 4.1).
`
`We remark that the trapdoor functions employed as public
`transformations in public-key systems are only a subclass of the
`class of one-way functions. The more general case will be discussed
`in section 3,2.2.
`
`We note also that public/private dichotomy of E and D in public(cid:173)
`key systems has no analogue in a conventional cryptosystem: in the
`latter, both EK and OK are parameterized by a single key K. Hence
`if EK is known then it may be assumed that K has been compromised,
`whence it may also be assumed that OK is also known, or vice(cid:173)
`versa. For example, in DES, both E and D are computed by
`essentially the same public algorithm from a common key;. so E and
`D are both known or both unknown, depending on whether the key has
`been compromised.
`
`1.6.1 Secrecy and authenticity.
`
`To support secrecy, the transformations of a public-key system
`must satisfy D(E(M)) = M. Suppose A wishes to send a secure message
`M to B. Then A must have access to EB, the public transformation of
`B (note that subscripts refer to users rather than keys in this
`.context). Now A encrypts M via C = EB(M) and sends C to B. On
`receipt, B employs his private transformation DB for decryption;
`i.e., B computes DB(C) = DB(EB(M)) = M. If A's transmission is
`
`-- 16 --
`
`REDACTED
`
`MasterCard, Exh. 1005, p. 16
`
`

`
`overheard, the intruder cannot decrypt C since DB is private, Thus
`secrecy is ensured. However, presumably anyone can access EB; B has
`no way of knowing the identity of the sender per se. Also, A's
`transmission could have been altered. Thus authenticity and
`integrity are not assured.
`
`To support authentication/integrity, the transformations in a
`public-key system must satisfy E(D(M)) = M. Suppose A wishes to
`send an authenticated message M to B. That is, B is to be able to
`verify that the message was sent by A and was not altered. In this
`case A could use his private transformation DA to compute C = DA(M)
`and send C to B. Now B can use A's public transformation EA to find
`EA(C) = EA(DA(M)) = M. Assuming M is valid plaintext, B knows that
`C was in fact sent by A, and was not altered in transit. This
`follows from the one-way nature of EA: if a cryptanalyst, starting
`with a message M, could find C' such that EA(C') = M, this would
`imply that h