CryptographyThe focus is on issues such as criteria for systems and protocols for usage. These are presumably longterm, in contrast, to the set of existing publickey 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 publickey cryptography and the relatedÔneway functions.....................33 3.2.3 Weak and strong hash functions....................34 3.3 Digital signatures and certificatebased systems.........35 4. Examples of publickey systems and hash functions............37 4.1 The RSA publickey 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Ôion protocols..........................67 5.3.5 Further notes.....................................71 5.4 DARPAInternet...........................................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......................................75 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....................................79 6.7.2 Component generation and storage....................79 6.7.3 Secretkey generation.............................79 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 Ôtic sieve factoring algorithm................92 B.3.2 Computations in finite fields......................93 B.3.3 Other algorithms...................................94 B.4 Applicationspecific 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.1 The Euler Phi function..................................108 G.2 The EulerFermat 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 Ô26 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 O. An introduction to zeroknowledge..................137 Appendix P. Alternatives to the Diffie/Hellman model...........143 P.1 Probabilistic encryption................................143 P.2 Identitybased schemes..................................145 References.....................................................147Ô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 [ISO87]. 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.Ô key systems can be used for signatures and also for the distribution of keys used in systems such as DES. Thus it is possible to construct hybrids of conventional and publickey 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],[KONH81], [LEMP79],[MASS88],[MERK82],[POPE78],[POPE79],[SALO85],[SIMM79]). More specialized discussions of publickey cryptography are given, e.g., in ([DIFF88],[LAKS83],[MERK82b]). 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 wouldbe 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 into 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 ciphertextonly attacks. b. A cryptanalyst should not be able to determine D given {E(Mi)} for any sequence of plaintexts {M1,M2,...}; i.e. the cryptosystem should be immune to knownplaintext attacks. This should remain true even when the cryptanalyst can choose {Mi} (chosenplaintext attack), including the case in which the cryptanalyst can inspect {E(M1),...,E(Mj)} before specifying Mj+1 (adaptive chosenplaintext attack). Adaptive chosen plaintext attack is illustrated below. Ôtext Attack To illustrate the difference between these two categories, we use two examples. First, suppose E(M) = M3 mod N, N = p * 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 ciphertextonly attack may be feasible in an instance where known or chosenplaintext attack is not useful. On the other hand, suppose E(M) = 5M mod N where N is secret. Then interception of E(M) would not reveal M or N; this would remain true even if several ciphertexts were intercepted. However, an intruder who learns that E(12) = 3 and E(16) = 4 could conclude N = 19. Thus a known or chosenplaintext attack may succeed whereÔor 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. Ôed in detail here, except to contrast it with other ciphers. It is a block cipher, operating on 64bit blocks using a 56bit key. Essentially the same algorithm is used to encipher or decipher. The transformation employed can be written P1(F(P(M))), where P is a certain permutation and F is a certain function which combines permutation and substitution. Substitution is accomplished via table lookups in socalled Sboxes. The important characteristics of DES from the standpoint of this exposition are its onekey 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 x is 32 bits and y is 48 bits. Each stage of the cascade is called a round. A sequence of 48bit 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 exclusiveor. Then if Mi denotes the output of stage i, we have L(Mi) = R(Mi1),Ô) = MK mod p. Now the condition GCD(K,p1) = 1 implies (lem. G.1) that we can find I with I * K ÀÀ 1 (mod p1). Note that I is not a separate key; I is easily derived from K or viceversa (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)) = C as well; i.e., E and D are 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 D are 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 nontrivial. 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 timeconsuming 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 knownplaintext 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Ôhms 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). For a survey of the discrete logarithm problem see, e.g., [ADLE86],[COPP87],[MCCU89],[ODLY84b]. 1.6 Publickey cryptosystems. The notion of publickey cryptography was introduced by Diffie and Hellman [DIFF76b]; for a history see [DIFF88]. Publickey systems, also called twokey 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 oneway function. Oneway 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 publickey systems are only a subclass of the class of oneway functions. The more general case will be discussedÔ and D in public key systems has no analogue in a conventional cryptosystem: in the latter, both EK and DK 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 DK is also known, or vice 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 publickey 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 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 publickey 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 oneway nature of EA: if a cryptanalyst, starting with a message M, could find C' such that EA(C') = M, this would imply that he can invert EA, a contradiction. If M, or any portion of M, is a random string, then it may be difficult for B to ascertain that C is authentic and unaltered merely by examining EA(C). Actually, however, a slightly more complex procedure is generally employed: an auxiliary public function H is used to produce a digital signature S = DA(H(M)) which A sends to B along with M. On receipt B can compute H(M) directly. The latter may be checked against EA(S) to ensure authenticity and integrity, since once again the ability of a cryptanalyst to find a valid S' for a given M would violate the oneway nature of EA. Actually H must also be oneway; we return to this subject in section 3.2. Sending C or S above ensures authenticity, but secrecy isÔy. In actuality there are no common systems versatile enough for the last usage without modification. In fact there is only one major system (RSA) which satisfies E(D(M)) = D(E(M)) = M. The lack of a common domain between two users creates a technical problem in using such a system for secrecy and authenticity. We discuss some approaches to this problem in section 4.1. If the question of domains is ignored, the usage of a system satisfying E(D(M)) = D(E(M)) = M with a hash function H is illustrated below. There EA,DA,EB,DB are the public transformations of A and B, respectively. A: B: ____________________ _________________   _____\   compute H(M)  /\ / receive (C,S)  ____________________  _________________       ________\/_________  _________\/_________       compute C = EB(M)    compute M' = DB(C)  ____________________  _____________________       _________\/__________  _________\/_________Ô   \/________________\ / Figure 2. Using PublicKey for Secrecy and Authenticity 1.6.2 Applicability and limitations. The range of applicability of publickey systems is limited in practice by the relatively low bandwidths associated with public key ciphers, compared to their conventional counterparts. It has not been proven that time or space complexity must necessarily be greater for public key systems than for conventional systems. However, the publickey systems which have withstood cryptanalytic attacks are all characterized by relatively low efficiency. For example, some are based on modular exponentiation, a relatively slow operation. Others are characterized by high data expansion (ciphertext much larger than plaintext). This inefficiency, under the conservative assumption that it is in fact inherent, seems to preclude the use of publickey systems as replacements for conventional systems utilizing fast encryption techniques such as permutations and substitutions. That is, using publickey systems for bulk data encryption is not feasible, at least for the present. On the other hand, there are two major application areas for publickey cryptosystems: a. Distribution of secret keys. b. Digital signatures. The first involves using publickey systems for secure and authenticated exchange of dataencrypting keys between two parties (sec. 2). Dataencrypting keys are secret shared keys connected with a conventional system used for bulk data encryption. This permits users to establish common keys for use with a system such as DES. Classically, users have had to rely on a mechanism such as a courier service or a central authority for assistance in the key exchange process. Use of a publickey system permits users toÔonvenience and robustness. Digital signatures are a second major application (sec. 3). They provide authentication, nonrepudiation and integrity checks. As noted earlier, in some settings authentication is a major consideration; in some cases it is desirable even when secrecy is not a consideration (e.g., [SIMM88]). We have already seen an example of a digital signature, i.e., when A sent DA(M) to B. This permitted B to conclude that A did indeed send the message. As we will note in section 3, nonrepudiation is another property desirable for digital signatures. Public key cryptosystems provide this property as well. No bulk encryption is needed when publickey cryptography is used to distribute keys, since the latter are generally short. Also, digital signatures are generally applied only to outputs of hash functions (sec. 3). In both cases the data to be encrypted or decrypted is restricted in size. Thus the bandwidth limitation of publickey is not a major restriction for either application. 2. Key management. Regardless of whether a conventional or publickey cryptosystem is used, it is necessary for users to obtain other users' keys. In a sense this creates a circular problem: in order to communicate securely over insecure channels, users must first exchange key information. If no alternative to the insecure channel exists, then secure exchange of key information presents essentially the same security problem as subsequent secure communication. In conventional cryptosystems this circle can be broken in several ways. For example, it might be assumed that two users can communicate over a supplementary secure channel, such as a courier service. In this case it is often the case that the secure channel is costly, inconvenient, lowbandwidth and slow; furthermore, use of a courier cannot be considered truly secure. An alternative is for the two users to exchange key information via a central authority. This presumes that each user individually has established a means of communicating securely with the central authority. Use of a central authority has several disadvantages as noted below. In publickey systems the key management problem is simpler because of the public nature of the key material exchanged between users, or between a user and a central authority. Also, alternatives to the insecure channel may be simpler; e.g., a physical mail system might suffice, particularly if redundant information is sent via the insecure (electronic) channel. Ôkey is needed, at least two communications involving the central authority are needed for each pair of users. Furthermore, such a system may not be robust: failure of the central authority could disrupt the key distribution system. Some of the disadvantages of a central authority can be mitigated by distributing key distribution via a network of issuing authorities. One possibility is a hierarchical (treestructured) system, with users at the leaves and key distribution centers at intermediate nodes. However, distributing key management creates a new security problem, since a multiplicity of entry points for intruders is created. Furthermore, such a modification might be inefficient unless pairs of users communicating frequently were associated to a common subtree; otherwise the root of the tree would be a bottleneck as before. Another alternative is a key translation center which requires only one keyencrypting key exchange through a certification authority. Some of these disadvantages can also be mitigated by a public key approach to key distribution. 2.2 Public distribution of secret keys.Ôeach number in [1,p) can be expressed as gx mod p for some x. Both p and g may be public. To establish a common secret key, A chooses a random x(A) in [0,p1] and B chooses a random x(B) in [0,p1]; these are kept secret. Then A computes y(A) = gx(A) mod p while B computes y(B) = gx(B) mod p. These need not be secret. Finally A sends y(A) to B and B sends y(B) to A. Now A knows x(A) and y(B) and can compute K = y(B)x(A) mod p = gx(B)x(A). Similarly, B knows x(B) and y(A) and can compute K = y(A)x(B) mod p = gx(A)x(B). The Diffie/Hellman algorithm is illustrated below. Ô     ________\/_________ ________\/_________      compute K = yB**xA   compute K = yA**xB  ____________________ ____________________ Figure 3. The Diffie/Hellman Key Exchange This establishes K as a secret common quantity which can be used in some agreedupon fashion to generate a secret key. The secrecy of this scheme depends, as in section 1.5, on the difficulty ofÔous section. If A thinks that EC is really EB then A might encrypt using EC and inadvertently allow C to decrypt using DC. A second problem is integrity: any error in transmission of a public component will render it useless. Hence some form of error detection is desirable. Regardless of the scheme chosen for public component distribution, at some point a central authority is likely to be involved, as in conventional systems. However, it may not be necessary for the central authority to be online; exchange of public components between users need not involve the central authority. An example of how this can be implemented is given in section 2.5. We also note there that the implications of compromise of the central authority are not as severe as in the conventional case. Validity is an additional consideration: a user's public component may be invalidated because of compromise of the corresponding private component, or for some other reason such as expiration. This creates a staledata problem in the event that public components are cached or accessed through a directory. Similar problems have been encountered in management of multi cache systems and distributed databases, and various solutions have been suggested. For example, users could be notified immediately of key compromises or invalidations. This may be impractical, in which case either users should be informed within a given time period of changes needed for cached information on public components, or users should periodically check with a centralÔ user possess ECA, the public transformation of the CA. Then each user A may register EA with the CA. Since EA is public, this might be done via the postal service, an insecure electronic channel, a combination of these, etc. Normally A will follow some form of authentication procedure in registering with the CA. Alternatively, registration can be handled by a treestructured system: the CA issues certificates to local representatives (e.g., of employing organizations), who then act as intermediaries in the process of registering users at lower levels of the hierarchy. An example of such a system is given in section 5.4. In any case, in return A receives a certificate signed by the CA (see sec. 3 for a more thorough discussion of signatures) and containing EA. That is, the CA constructs a message M containing EA, identification information for A, a validity period, etc. Then the CA computes CERTA = DCA(M) which becomes A's certificate. The latter is then a public document which both contains EA and authenticates it, since the certificate is signed by the CA. Certificates can be distributed by the CA or by users, or used in a hierarchical system which we return to later. The inclusion of the validity period is a generalization of timestamping. The latter was not treated in [KOHN78], but Denning [DENN81] notes the importance of timestamping in guarding against the use of compromised keys. In general, the problem of stale data is not wholly solved by timestamping: a certificate may be invalidated before its expiration date, because of compromise or administrative reasons. Hence if certificates are cached by users (as opposed to being re distributed by the CA each time they are used), the CA must periodically issue lists of invalidated certificates. Popek and Kline [POPE79] have noted that certificates are analogous to capabilities in operating systems. Management of certificates creates analogous problems, such as selective revocation of capabilities. The public nature of certificates, however, a priori precludes an analogue of a useful feature of a capability system: users cannot be restricted to communicating with a subset of other users. If a selective capability feature is desired it must be implemented through a controlled distribution of certificates,Ôus disadvantage to the ROM mode of hardware key storage, namely the fact that the party which loads a private key to ROM could retain a copy. An alternative, but still classical, scheme is for the user to be provided with a means of writing to a memory chip and then sealing it from further writing. A more modern and more secure hardware adjunct is a smart token, smart card or other device which contains both memory and a microprocessor. Such a device can both generate and store user keys. Ideally, it should be implemented via a single chip which stores both cryptographic algorithms and data. In the classical case, encryption and decryption are handled by separate units in a hardware device acting as an interface between a user's computer and the network. As noted in [DENN79], thisÔeady seen an example of a publickey cryptosystem implementing public key distribution in section 2.2. Both secrecy and authentication can be provided simultaneously in the distribution process via publickey systems. This may be achieved using a single publickey system if its encryption and decryption functions are inverses, or via a hybrid of two public key systems providing secrecy and authentication separately. The essence of this usage is very simple: a secret key is merely a particular form of message. Assuming that a system has been established for distribution of public components of users as discussed in the previous section, users can then establish secret keys at will by employing the public system for encryption and signing of secret keys. Thus the latter can be exchanged or changed without difficulty. This is in contradistinction to a system in which secret keys must be established via couriers or a central authority. The use of publickey cryptography thus reduces the problem of secret key distribution to the problem of binding user identities and user public keys. The latter is a simpler problem in that no communication of secret information is necessary. That is, users can generate their own private/public key pairs and need not expose their private keys to anyone, including themselves. However, it is critical that user public keys be properly authenticated. This is a nontrivial consideration in large networks. Since only integrity and authenticity are considerations, usersÔion path. Such a path need not require use of insecure channels if the nodes in the path can communicate securely. For example, a user might register with a local certifying authority in person. The local authority might be affiliated with an organization and may be able to use the user's organization ID to certify the user's public key. If the local authority can communicate securely with the central authority, the user's public key may then be forwarded to the central authority for distribution. Assuming that user public components can be certified and distributed, two users may use each other's public components to establish common keys for use in message encryption, again without resort to a secure channel. 2.4.1 A protocol for key exchange. Suppose A and B wish to establish a shared secret key. Suppose further that they have obtained each other's public components. Some possible modes for binding user public keys to user identities and distributing certified user public keys are discussed in sections 5.3.1  5.3.2 and 5.4.6. In any case, A may now generate a secret key K. For example, this may be a keyencrypting key to be used to exchange session keys and possibly initialization vectors if, e.g., DES is used in cipher feedback mode or cipher blockchaining mode [NATI80]. Then A might form an expanded message which contains K and other data, which could include an identification for A, a timestamp, a sequence number, a random number, etc. This added material is needed for A to authenticate himself to B in realtime, and thus prevent replays. For example, Needham and Schroeder [NEED78] suggest a threeway handshake protocol: First of all A may send to B the message C = EB(RA,IDA), where EB is B's public transformation, IDA is the identification of A, and RA is a random number. Now B can decrypt C and obtain IDA. Now B generates a random number RB and sends C' = EA(RA,RB) to A. Upon decryption of C', A can verify in real time that B has received RA, since only B could decrypt C. Finally A sends C" = EB(RB) to B; when B decrypts C" he can verify in real time that A has received RB, since only A could decrypt C'. Thus A and B are authenticated to each other in real time; i.e., each knows that the other is really there.Ô ________\/________       compute (RA,RB) = DA(M')  /______ send M' to A  __________________________ \ ___________________     _______\/______ ________\/_________   _____\   verify RA  /\ / receive M" from A  ________________  ____________________       _________\/_________  _________\/__________       compute M" = EB(RB)    compute RB = DB(M")  _____________________  ______________________Ôspectively. These contain EA and EB (or equivalently, the public components of A and B) as noted in section 2.3.1. We may assume that A and B have cached CERTA and CERTB, respectively. If A has exchanged certificates with B previously, A and B may have each other's certificates cached. If not, then there are two ways in which A could obtain B's certificate. The simplest is for A to request B's certificate directly from B; this is explored in the next section. The advantage of this simple approach is that online access to a central authority is avoided. On the other hand, if A requests B's certificate directly from B, or obtains it from a directory listing, security and integrity considerations arise. For example, the certificate A obtains may have been recently invalidated. Thus A may wish to access B's certificate through the CA, assuming that the latter is online. In this event A requests CERTA and CERTB from S. We recall that each CERT has the form DS(M) where M contains an E. Thus when A receives the requested certificates, he can validate CERTA by computing ES(CERTA) and recovering EA. This validates the source of the certificates, thus validating CERTB as well. Hence A may retrieve a duly authenticated EB from CERTB. The disadvantage is the requirement of an online central node; the advantage is that A is assured of the instantaneous validity of theÔnnels with excellent security. A second advantage is that distribution of certificates by a central authority assures that certificates are valid at time of receipt. A prerequisite for the proper functioning of such a key management system is the existence of a system for binding user public keys and identities. Such a system requires distributed trust. A disadvantage of this mode of management is that as in section 2.1, the central authority may be a bottleneck. The severity is mitigated by the fact that a secure channel is not needed, but the essential problem is similar. A more significant disadvantage arises from the concentration of trust in one entity [KLIN79]. The security of the central authority might be compromised, e.g., by penetration. The fact that the central authority does not generally access users' private components means that existing messages are not compromised, as might be the case in a secretkey system [DIFF82]. However, if an intruder accesses the central authority's private component, the intruder could forge certificates. Some scenarios for intrusions of this sort, explorations of consequences, and means for minimizing damage are explored in [DENN83b] and [DIFF88]. Merkle [MERK82b] has suggested a treestructured system as a means of coping with the compromise of a central authority. However, this scheme is not practical for large networks since the tree must be restructured each time the user population changes. 2.5.2 Decentralized management. Users may be responsible for managing their own certificates. In this event the protocol is much simpler. When A wishes to initiate communication (e.g., exchange of a secret key) with B, he sends a message to B containing A's certificate, A's identification, and other information such as a date, random number etc. as described in the protocol in the previous section. This message also requests B's certificate. Upon completion of the certificate exchange, employing some protocol such as the handshake above, A and B will possess each other's authenticatedÔheme is clearly in question [KLIN79]. Phonebook entries might contain errors, or entries could be altered. 3. Digital signatures and hash functions. Digital signatures were introduced by Diffie and Hellman [DIFF76b]; for surveys see, e.g., [AKL83],[POPE79],[RABI78]. A digital signature is the electronic analogue of a handwritten signature. A common feature is that they must provide theÔryptography by Diffie and Hellman [DIFF76b]. As we note below, hash functions are useful auxiliaries in this context, i.e., in validating the identity of a sender. They can also serve as cryptographic checksums (i.e., errordetecting codes), thereby validating the contents of a message. Use of signatures and hash functions can thus provide authentication and verification of message integrity at the same time. Numerous digital signature schemes have been proposed. As notedÔ not have a unique signature. This scheme is intended to deflect adaptive chosentext attacks, in which an attacker is permitted to use a signer as an oracle. In such an attack, the attacker specifies a sequence of messages to be signed, and is able to study all previous signatures before requesting the next. In the GMR scheme, it can be proved that an attacker can gain no information by studying any number of signatures no matter how they are generated. However, this security gain is offset to some extent by data expansion (high ratio of signature to message size) and a negative effect on nonrepudiation. As in the case of the onetime schemes discussed earlier, the signatures generated in nondeterministic publickey schemes tend to be large in comparison to signatures produced by deterministic publickey schemes (i.e., those which produce a unique signature for a given message). Adjudication of disputes is made difficult by increased bookkeeping and the necessity of storing large databases of messages and their signatures. In the following we discuss only deterministic publickey signature schemes, in which a message has a unique signature. 3.1 Publickey implementation of signatures. We have noted previously that, like secretkey systems, publicÔ. In the simplest case, A simply signs a document M by sending S = DA(M) to B. If a hash function H is used, A computes S = DA(H(M)) and sends both M and S to B. B validates A's signature S by computing H(M) = EA(S). We also noted earlier that because EA is a trapdoor one way function, it should not be possible for an intruder to find S' such that H(M) = EA(S') for a given message M. Thus A's signature cannot be forged. Also, if A attempts to repudiate the M sent to B above, B may present M and S to a judge. The judge can access EA and hence can verify H(M) = EA(S); assuming the trapdoor DA is indeed secret, only A could have sent S. Thus a priori we have nonrepudiation (but see below). For both authenticity and secrecy, A could send M' = EB(M,DA(H(M))) to B; B computes (M,DA(H(M))) = DB(M') and then verifies that H(M) = EA(DA(H(M))).Ô    ________\/_________  _________\/_________       send M' to B    verify H' = H(M)  ____________________  _____________________     \/________________\ / Figure 5. A Protocol for Signing with Hash Function and Secrecy For nonrepudiation in the last case, B retains DB(M') = (M,DA(H(M))). A judge can apply EA to DA(H(M)) and compare to H(M). This again assumes common domains for the E's and D's; in section 4.1 we will note an example of how this point may be treated in practice. In passing we remark that the preceding schemes satisfy another desirable property: in the adjudication process, they do not compromise security by exposing private components to a judge. 3.1.2 The issue of nonrepudiation. Nonrepudiation, i.e., preventing senders from denying they have sent messages, is contingent upon users keeping their private components secret (e.g., [NEED78],[POPE79]). In the above, if DA should be compromised, then A might be able to repudiate messages sent even before the compromise. On the other hand, as in the case of lost or stolen credit cards, A may still be held liable for messages signed before the compromise was reported to a centralÔs a header m = identifying information. c. U computes S2 = DU(m,S1). d. U sends m and S2 to A. e. A applies EU to S2 and checks the identifying information in m, thereby verifying the origin of M. f. A computes M' = (m,S1,timestamp). g. A computes S' = DA(M'). h. A sends S' to R. As noted above, a copy of S' may also be sent to U. As noted in [POPE78], this type of scheme violates a desirable criterion for network protocols, namely pointtopoint communication. It also requires trusted software, which is undesirable. In [BOOT81] the use of a central authority is suggested for this purpose. In this scheme, the receiver of a message sends a copy to the central authority. The latter can attest to the instantaneous validity of the sender's signature; i.e., that it has not been reported that the sender's private component has been compromised at the time of sending. The value of such testimony is mitigated by the necessity of users rapidly reporting key compromise to the central authority. Also, the central authority becomes a bottleneck. Another partial solution involves timestamps ([DENN81], [MERK82b]). This again may involve a network of automated arbitrators, but very simple in nature, since they need merely timestamp messages. In contrast to the notary publics above, however, in [MERK82b] it is suggested that receivers obtain timestamps. If a receiver needs to be sure of the validity of a signature, he may check the validity of the sender's private component by checking with a central authority. As long as the received message is timestamped before the validity check, theÔlidity checks and timestamps, which may again create bottlenecks. Furthermore, such schemes require a networkwide clock and are vulnerable to forgery of timestamps, as noted in [BOOT81]. If users are permitted to change their components, a central authority should retain past components for use in disputes which may arise later. Neither compromise nor change of components of a user should cause catastrophic problems in practice, since credit card systems have established precedents for protocols, both administrative and legal. For example, as noted above, conventions have been established for treatment of cases of lost or stolen credit cards; presumably analogous procedures could be established for component compromise. 3.1.3 The issue of proof of delivery. The literature on publickey protocols concentrates on the issues of validity of signatures and the effects of key compromise on nonrepudiation. However, DeMillo and Merritt [DEMI83] note that the inverse of a signature, namely protection against the recipient of a message denying receipt, may also be a desired feature of a system. It is mentioned as an optional security service in [ISO 87]. Both nonrepudiation and proof of delivery must be implemented via adjudicable protocols, i.e., protocols which can be verified later by a third party. In [DEMI83] it is noted that nonarbitrated adjudicable reception protocols are difficult to design. A simple handshaking protocol might proceed as follows: a. A computes X = EB(DA(M)). b. A sends X to B. c. B computes M = EA(DB(X)). d. B computes Y = EA(DB(M)). e. B acknowledges receipt of M by sending Y to A. If this protocol is standard procedure then A can assume nonreception unless he receives acknowledgement from B. However, to serve as an adjudicable proofofreception protocol, B is required to acknowledge anything A sends. Then an intruder C couldÔ Y to A. c. A thinks that this is a legitimate message from C, unrelated to his communication with B. Following protocol: c.1. A computes M' = EC(DA(Y)). c.2. A computes Z = EC(DA(M')). c.3. A acknowledges receipt of M' by sending Z to C. d. C computes EB(DC(EA(DC(Z)))) = EB(DC(M')) = EB(DA(Y)) = M. This of course occurs because of step c, in which A is required by protocol to acknowledge M' = gibberish. This shows that such an automatic protocol may be undesirable. On the other hand, selective acknowledgement might have an adverse effect on adjudicability. 3.2 Hash functions and message digests. We noted that publickey systems generally encrypt more slowly than conventional ciphers such as DES. Other digital signature schemes are also relatively slow in general. Furthermore, some schemes produce signatures comparable in size to, and in some cases larger than, the messages they sign. This results in data expansion and effectively lower bandwidth of transmission. Thus it is usually not desirable to apply a digital signature directly to a long message. On the other hand, we remarked that the entire message must be signed. This is seemingly contradictory, but a heuristic solution can be obtained by using a hash function as an intermediary. A hash function H accepts a variablesize message M as input and outputs a fixedsize representation H(M) of M, sometimes called a message digest [DAVI80]. In general H(M) will be much smaller than M; e.g., H(M) might be 64 or 128 bits, whereas M might be a megabyte or more. A digital signature may be applied to H(M) in relatively quick fashion. That is, H(M) is signed rather than M. Both M and the signed H(M) may be encapsulated in another message which may then be encrypted for secrecy. The receiver may validate the signature on H(M) and then apply the public function H directly to M and check to see that it coincides with the forwarded signed version of H(M). This validates both the authenticity and integrity of M simultaneously. If H(M) were unsigned only integrity would be assured.Ôhe same digest as a given message. Thus, altering a message will change the message digest. This is important to avoid forgery. In many settings this minimal requirement is regarded as too weak. Instead, the requirement is added that it should not be possible to find any two strings which hash to the same value. We return to the distinction between these two criteria in section 3.2.3. 3.2.1 Usage of hash functions. In a publickey system augmented by a hash function H, A might send a message M to B as follows: for simplicity ignore secrecy considerations. Then A sends M and S = DA(H(M)) to B. The latter uses EA to retrieve H(M) from S, then computes H(M) directly and compares the two values for authentication. For nonrepudiation, B retains M, H(M) and S. If A attempts to repudiate M, a judge can use the three items to resolve the dispute as before: he computes H(M) = EA(S) and recomputes H(M) from M. If B could find M' with H(M') = H(M), B could claim A sent M'. A judge receiving M', H(M)Ôs well. For example, we noted earlier that the security of public key systems depends on the fact that the public transformations are trapdoor oneway functions. Trapdoors permit decoding by recipients. In contrast, hash functions are oneway functions which do not have trapdoors. The concept of (nontrapdoor) oneway functions originated in connection with login procedures ([WILK68] p. 91): Needham noted that if passwords were stored encrypted under a oneway function, a list of encrypted passwords would be of no use to an intruder since the original passwords could not be recovered. When a user logged in, the string entered would be encrypted and compared to the stored version for authenticity. Essentially the same system was rediscovered later in [EVAN74]. Usage of oneway functions to produce message digests or encrypt passwords is very different from use of trapdoor oneway functions to generate encryption functions {EA} in a publickey cryptosystem. In the latter, (d) above becomes a dichotomy: it is computationally infeasible for anyone except A to find M from C = EA(M); but it is easy for A, the unique holder of the trapdoor DA, to compute M = DA(C). Ôn is amenable to further refinement. 3.2.3 Weak and strong hash functions. The security of hash functions can be refined further: we may distinguish between weak and strong hash functions. A function satisfying (a)  (e) of the previous section may be termed a weak hash function. Property (e) characterizes weak hash functions; it states that a cryptanalyst cannot find a second message producing the same message digest as a fixed message. On the other hand, H may be termed a strong hash function if (a)  (d) still hold, but (e) is modified as follows: it is computationally infeasible to find any {x1,x2} with H(x1) = H(x2). Strong and weak functions may often be obtained from the same class of functions. Strong functions are then characterized by larger message digests, which reduce the probability of collisions. Strong functions are thus more secure, but the longer message digests are likely to increase time needed to hash. Although the two definitions above are superficially similar, computationally they are quite different. For example, suppose H is a hash function with an 80bit output. Suppose a cryptanalyst starts with a fixed message M and wishes to find a second message M' with H(M) = H(M'). Assuming that the 280 outputs of H are totally random, any candidate M' has a probability of only 280 of meeting the required condition. More generally, if the cryptanalyst tries k candidates, the probability that at least one candidate satisfies H(M) = H(M') is 1(1280)k which is about 280k by the binomial theorem if the latter is small. For example, the cryptanalyst will probably have to compute H for about k = 274 = 1022 values of M' to have even one chance in a million of finding one M' which collides with M. Thus H is secure in the weak sense. Suppose for the same H the cryptanalyst merely seeks any values {M1,M2} with H(M1) = H(M2). By example F.1, if he examines H(M) for at least 1.17 * 240 < 2 * 1012 random values of M, the probabilityÔllision exceeds 1/2. A supercomputer could probably find M1 and M2 with H(M1) = H(M2) in at most a few days. Thus H is not secure in the strong sense. The latter attack is called a birthday attack (app. F). It should be noted that finding a collision H(x) = H(y) gives the cryptanalyst no valuable information if x and y are random bit strings. For a purpose such as forgery an adversary may need to generate a large number (e.g. 1012 above) of variations of a message to find two which collide. Inclusion of timestamps or sequence numbers in messages, according to a fixed format, may make it computationally infeasible to find a collision of use to an adversary. 3.3 Digital signatures and certificatebased systems. We previously noted that digital signatures can be employed for authentication in the process of distributing public components in publickey systems. In particular, if the system is certificate based, the central issuing authority can sign certificates containing public components. The notion of a central authority can be extended to a hierarchical (tree) structure. The central authority serves as the root of the tree; leaves represent users. Intermediate nodes may also be users. Typically the intermediate nodes will be arranged in several levels representing, e.g., organizations and organizational units. Each node of the tree is responsible for authenticating its children. Thus an authentication path is created for each node, ending at the root. For example, the central authority may certify an organization; the organization may certify a unit; the unit may certify an individual user. Certification may be accomplished by having a parent node sign a certificate for the child node. To validate another user's certificate, a user may request the entire authentication path. It is also possible for the tree to be replaced by a forest. For example, in a multinational system there may be a different tree for each country. In this event the roots must certify each other. An authentication path may then pass through two or more roots. More generally, an authentication structure can be an arbitrary directed graph, with a directed edge from A to B if A certifies B. Then authentication paths may be constructed by conjoining directed paths from two users to a common trusted node; an example of this more complex structure is given in section 5.3. 4. Examples of publickey systems and hash functions. Ôlman exponential exchange scheme (sec. 2.2), public key distribution is supported but authentication is not. Such systems may need augmentation by a system which supports signatures. The only wellknown system discovered to date which is secure, practical and suitable for both secrecy and authentication is described in section 4.1. Category (b.2.3) above could in theory be further subdivided into systems with relatively low and high bandwidths, but there are no wellknown examples with high bandwidths. There does not exist a secure, practical system suitable for key distribution and digital signatures, and with high enough bandwidth to support bulk data encryption. Prospects for creating radically new systems seem dim; in fact, as noted in [DIFF88], most of the extant systems are based on a small number of hard mathematical problems:Ôhis has generated systems (e.g. sec. 2.2) suitable for key distribution, and others suitable for signatures (e.g. sec. 4.2.2). Exploitation of the difficulty of factoring has proven to be the most versatile approach to design of publickey systems. Factoring is widelyregarded as very difficult. If a modulus has unknown factorization, various problems in modular arithmetic become difficult. For example, discrete logarithm ((b.2) above) is difficult, as is taking roots (b.3) and deciding quadratic residuosity (b.4). These problems have generated the most widely known publickey system (sec. 4.1) and various others. We remark in passing that the probabilistic scheme mentioned in section 3 and appendix P are based on (b.4); more generally, quadratic residuosity forms the basis of many zeroknowledge schemes.Ô n, D(C) = Cd mod n. In the above, M and C are in [0,n1]. As in section 1.5 we have D(E(M)) = M and E(D(C)) = C; i.e. D and E are inverses. Since d is private, so is D; and since e and n are public, so is E. This constitutes a cryptosystem which can be used for both secrecy and authentication. That is, for secrecy, A sends EB(M) to B as usual; for authentication, A sends DA(M) as usual. For both secrecy and authentication, suppose first that message digests are not employed. Assuming nA ÀÀ nB, A computes C = EB(DA(M)) and sends C to B. Then B recovers M as usual by M = EA(DB(EB(DA(M)))). This process is illustrated below: Ô This implementation only works because the range of DA is a subset of the domain of EB; i.e. [0,nA1] is a subset of [0,nB1]. In the event that nA ÀÀ nB, Kohnfelder [KOHN78b] notes that A can instead transmit C' = DA(EB(M)). Then B can recover M as M = DB(EA(DA(EB(M)))). This works since the range of EB is a subset of the domain of DA. For adjudication of possible disputes, B must retain C' and M. Then to prove that A sent M, the judge can compute EA(C') and EB(M) and test for equality. However, in [DAVI83] and [DENN83b] it is noted that there is aÔtion holds, compute the Jacobi symbol (a/b) (app. J). Both GCDs and Jacobi symbols are easy to compute via wellknown algorithms (app. H,J). Now check to see if (a/b) ÀÀ a(b1)/2 (mod b). If b is not prime, this check will fail with probability at least 1/2 (app. L). Thus, if 100 random a's are tested and all pass the above test, the probability of b not being prime is about 1 in 2100. Hence it is possible to test in polynomial time whether b is probably a prime. The probability of b being prime is about 1 in 115; hence repeated applications of the preceding algorithm will probably quickly yield b which is probably a prime. This can be taken to be p; a second application of the algorithm will yield q. The Solovay/Strassen algorithm is discussed further in appendix L, which also mentions alternative algorithms of Lehman [LEHM82] and Miller and Rabin ([MILL76],[RABI80]). The advantage of such probabilistic algorithms is that the algorithms run in polynomial time. They do not guarantee a correct answer, but the possibility of error is negligible as noted above. If absolute certainty were required, deterministic algorithms for primality testing could be used ([ADLE83],[COHE87],[COHE84]). These guarantee primality, but have runtimes of the formÔumber of modular multiplications are needed. The condition GCD(e,m) = 1 presents no problem; in fact the probability that two random numbers are relatively prime is about 3/5 ([KNUT81] p. 324). Now d can be found in polynomial time; however, d may be large. Hence a version of the Chinese Remainder Theorem is employed for decryption (app. M). There are some restrictions on p and q in addition to the size specification mentioned above. Some of these are noted in section 4.1.3.1. Also, the time and space requirements of RSA are considerably larger than, e.g., DES. Storage for each of p, q, and d will require at least 300 bits; n is about 600 bits. Only e can be chosen to be small. Exponentiation mod n is a relatively slow operation for large n, especially in software. Efficient algorithms for computing products mod n have been given, e.g., in [BLAK83], [BRIC82], [MONT85] and [QUIS82]. In particular, [BRIC82] shows how multiplication mod n can be done in m+7 clock pulses if n is m bits. In [MONT85] it is shown how modular multiplication can avoid division. At the present time RSA decryption (encryption is slower) with a 508bit modulus has been performed at about 225 Kbits/sec in hardware [SHAN90]. Decryption with a 512bit modulus has been effected at about 11 Kbits/sec in software [DUSS90]. 4.1.3 Security of RSA. The security of the private components in the RSA cryptosystem depends on the difficulty of factoring large integers. No efficient algorithms are known for this problem. Consequently, knowing n = Ôcks are equivalent to taking roots modulo a composite number with unknown factorization, i.e. solving C = Me mod n for M. This is probably about as difficult as discrete logarithms, even in the case of square roots (e.g., [ADLE86]). In fact (lem. N.3.2; cf. [KNUT81] p. 389, [RABI79]), taking square roots modulo such n is, loosely speaking, as hard as factoring n. It should be noted that the security of RSA is not provably equivalent to the difficulty of factoring or the other problems mentioned here. Also, security of RSA or other publickey systems does not preclude breaking specific protocols for their use; see e.g. [MOOR88] or [DOLE81]. An example of a protocol failure is given in [MOOR88]: suppose two users use a common modulus n and encryption exponents e and e' with GCD(e,e') = 1. If the same message M is sent to both, then let C = Me mod n and C' = Me' mod n. If both C and C' are intercepted, an intruder can find (app. H) r and s with r * e + s * e' = 1; now M = Cr * C's mod n. 4.1.3.1 Restrictions on p and q. There are two major restrictions on p and q in order to foil attempts at factoring n = p * q: a. p and q should be about the same length. b. p and q should be at least 75 digits in length. Present factoring methods will be foiled by such a choice. For longerterm security, p and q should be, e.g., around 100 digits. Condition (a) is needed against the elliptic curve method (see below). An attempt to predict the period of time for which a given modulus length will remain secure is necessarily guesswork. Intelligent guesses are the best that can be hoped for by implementors; these are connected with the status of progress in factoring, which is highly dynamic. Ô sieve, Caron and Silverman [CARO87] factored 90digit integers in several weeks on a network of several dozen Sun3's. Recently, 106digit integers have been factored on a larger network [LENS89], using the multiple polynomial variant of the quadratic sieve. Recent announcements of work in progress indicate that integers of around 116 digits may be factored shortly, using the same network used in the 106digit case and another variant of the quadratic sieve. Pomerance, Smith and Tuler [POME88] discuss a prototype of a special pipelined architecture, optimized for the quadratic sieve, which they claim is extensible to a machine which might factor 125 digit integers in a year. However, this presents no threat to 200 digit moduli, since all of the best generalpurpose factoring algorithms known, including the quadratic sieve, run in time roughly exp(((log n)(log log n))1/2). The fastest present computers only execute on the order of 1010 operations per second, at a cost of $10 million or more. Even if a future computer reached 1012 operations per second (and presumably a cost exceeding $100 million) it would take on the order of 1000 years to factor a 200digit number using existing algorithms. The strongest results on factoring obtained to date have utilized networks of computers. The power of such networks is more difficult to extrapolate than for supercomputers, since they are expandable and the power of personal computers and workstations has been rising at a higher rate than at the supercomputer level. In theory it would be preferable to know that a cryptosystem would be immune to an attack by an assemblage of every computer in the universe. It seems difficult to estimate the total amount of computing power this would bring to bear; furthermore, the question in practice is what fraction of this total amount can be realistically allotted to a given factoring problem (cf. app. B). It follows that implementors may have a high level of confidence in 200digit moduli at the present. An interesting issue at the time of this writing is whether a modulus with a length between 150 and 200 digits will provide security for a given length of time. It seems certain that 154digit (i.e., 512bit) integers will be factored eventually, but the question is when. If the preceding runtime estimate is used, the conclusion is that 154 digits is likely to be secure until the late 1990s, barring major algorithmicÔ is oriented to integers whose secondlargest prime factor is considerably smaller than the largest prime factor. This motivates the condition that an RSA modulus should have factors roughly equal in size. A recent algorithm, the number field sieve [LENS90], applies to integers of the form rd + s or rd  s where r and s are small. Again this will not affect properlychosen RSA moduli. 4.1.4 Lowexponent versions of RSA. A priori the encryption exponent e in the RSA scheme is arbitrary. However, it need not be random. It has been suggested that e be chosen to have a common value by all users of an RSA based system. Using e = 2 is not feasible per se, since 2 is not relatively prime to p1 or q1. However, extensions of this type have been made. These are of some theoretical interest, since Rabin [RABI79] and Williams [WILL80] have noted modifications of RSA with exponent 2 for which successful ciphertextonly attacks are essentially as difficult as factoring the modulus (app. N). The exponent 3 can be used directly with RSA. It has the advantage of greatly simplifying the encryption (but not the decryption) process. In fact Knuth [KNUT81], Rivest [RIVE84] andÔn1,n2,n3} is generated as a product of two random primes, the probability of duplicates among the 6 primes used is near zero. Hence it may be safely assumed that the {ni} are pairwise relatively prime. Let Ci = M3 mod ni. Suppose all 3 {Ci} are intercepted. Using the Chinese Remainder Theorem (app. I), the intruder can find x in [0,n'), n' = n1 * n2 * n3, with x ÀÀ Ci (mod ni), i = 1,2,3. Thus x ÀÀ M3 (mod n'). But M3 < n', so M3 = x, so M = x1/3 (ordinary cube root). Hence the plaintext M can be easily recovered from the three ciphertexts. Thus the use of e = 3 or other small exponents makes RSA vulnerable to ciphertextonly attacks. The sender may attempt to modify M for each recipient to deflect this attack, but Hastad shows that more generally, a low exponent is vulnerable to linear dependencies in portions of messages. 4.2 Other publickey systems. Several publickey systems other than RSA have been proposed. These are briefly surveyed here. As noted earlier, most of these are either insecure, of questionable practicality, or limited to one of signatures/secrecy but not both. In some cases their security and/or practicality has not been established. None of these systems rivals RSA if a combination of versatility, security and practicality is the criterion. However, this does not preclude the use of the secure systems for specific applications such as digital signatures. 4.2.1 Knapsack systems. These were proposed by Merkle and Hellman [MERK78b]. However, the essence is the use of NPcomplete problems (e.g., [GARE79],[HORO78]) which had been suggested for use in designing publickey systems in [DIFF76b]. The Merkle/Hellman approach was to employ a superincreasing sequence {ai}, i.e., a sequence of positive integers for which Ô the present context the {Mi} are binary; thus the above reduces to sumof subsets. Solving the above is easy for superincreasing {ai}; in fact the solution is unique. However, even deciding existence of a solution of sumofsubsets, or more generally integer programming, is NPcomplete ([GARE79], pp. 223, 245). Now for any w and u satisfying u > a1 + ... + an, GCD(u,w) = 1, a disguised knapsack problem may be produced from {ai} by defining bi = w * ai mod u. Then the associated knapsack problem C = b1 * M1 + ... + bn * Mn appears to a cryptanalyst to be hard since the {bi} appear random. In actuality, it is easily solved using the connection with the {ai}: since GCD(w,u) = 1, there exists W (app. H) such that w * W ÀÀ 1 (mod u). Then W * C ÀÀ a1 * M1 + ... + an * Mn (mod u). Since 0 ÀÀ Mi ÀÀ 1, Ôn (Appendix E). It should also be noted that even if a knapsack approach proves to be secure and practical, such schemes are generally limited to support for either secrecy or authentication but not both. In contrast to RSA, the encryption and decryption functions are not inverses, although D(E(M)) = M. A trivial example suffices to show this: suppose E(M) = 2M1 + 3M2. To be invertible a function must be both injective and surjective. However, E is not surjective (onto). For example there is no M such that E(M) = 1; hence D(1) is undefined. Thus we could not employ D for signatures as in RSA, since, e.g., 1 could not be signed by computing D(1). 4.2.2 The ElGamal signature scheme. Ô A: B: ____________________ _________________   _____\   choose k  /\ / receive (M,r,s)  ____________________  _________________       _________\/__________  __________\/___________       find I*k ÀÀ 1 mod p1    compute C = a**M mod p  ______________________  ________________________       __________\/___________  _________\/_________       compute r = a**k mod p    compute C' = yA**r  ________________________   * r**s mod p    _____________________       __________\/___________  Ôbe chosen for each M; using any k twice determines x(A) uniquely. The security of the method then depends mainly on the difficulty of computing discrete logarithms in GF(p): suppose an intruder intercepts M, r and s; a and p are public. Let d = ar mod p and u * rs ÀÀ 1 (mod p). Then the intruder knows aM ÀÀ y(A)r * rs (mod p). Hence u * aM ÀÀ y(A)r (mod p). Thus dx(A) ÀÀ (ax(A))r ÀÀ y(A)r (mod p). Finally dx(A) ÀÀ u * aM (mod p). Finding x(A), which permits the intruder to masquerade as A, is thus equivalent to the above discrete logarithm problem. It is easy to solve this problem if p1 has only small factors [POHL78], hence p1 should have a large prime factor as in RSA. An alternative approach is to seek k and m satisfying M = r * x(A) + s * k + (p1) * m,Ôon; it could also turn out that no substantial advantage is gained by varying r and s simultaneously). The use of messagedependent portions of components is a plus and minus: it increases bookkeeping, and makes it more difficult for a third party to adjudicate a dispute. On the other hand it may produce greater security against certain types of attacks. In fact the k above could be chosen differently for different blocks of one message. In passing we note that, like knapsacks, this scheme goes in one direction only: we have in effect M = E(r,s) = (x(A) * r + k * s) mod (p1). This maps the ordered pair (r,s) to a unique M. The condition GCD(k,p1) = 1 guarantees that an (r,s) can always be found; i.e., E is surjective. But it is not injective (onetoone): e.g., if p = 7, k = 5, x(A) = 5, then E(1,2) = E(2,1) = 3. Thus text M cannot be represented uniquely by a pair (r,s), which would lead to ambiguity in an attempt to use this scheme in two directions. Also, ElGamal notes that extension to GF(pn) (app. G) is feasible. However, it is not clear that extensions to finite fields are desirable (cf. sec. 1.5); gains in efficiency may be offset by lower security for comparable key sizes. Ôons are keyless; keys needed for DES are generated from the message to be hashed. The hash functions are precertified in the sense that their security can often be proven to be the same as that of the underlying conventional function. Merkle assumes that encryption in a system such as DES defines a function EK, where K is a key, which produces a random output. This is technically impossible, and in fact DES is not a random function since it is a permutation. Nonetheless, small deviations from randomness may be tolerable. Another requirement is that for a given key/plaintext (or ciphertext) pair, the ciphertext (or plaintext) returned will not vary with time. Normally a cryptosystem would meet this criterion. Assume that a function EK(M) is available which satisfies these requirements. In deference to the potential use of DES to define E, assume K is 56 bits, M is 64 bits, and EK(M) is 64 bits. Since E may be assumed to be an encryption function, it may be assumed that there exists a decryption function with EK(DK(C)) = C. This is undesirable in producing oneway hash functions. This problem may be mitigated as follows: given a 120bit input x, write x = CAT(K,M) where CAT denotes concatenation, K is the first 56 bits of x, and M is the last 64 bits. Let f(x) = EK(M) XOR M, where XOR is exclusiveor. Then f hashes 120 bits to 64 bits. Furthermore, Merkle claims that f produces a random output even if x is chosen nonrandomly. A strong oneway hash function, as defined in section 3.2.3, meets this criterion. Thus f might be termed a fixedsize strong oneway hash function, with "fixed size" referring to the fact that f does not accept arbitraryÔhe probability of collisions produced when hashing becomes significant when the number of items hashed is around the square root of the total number of hash function values. In section 3.2.3 we noted how such attacks affect the security of hash functions. For example, a 64bit output (i.e., 264 hash values) would be vulnerable to an attack using only 232 = 4 billion messages. On the other hand, a 112bit output would require exhaustive search of on the order of 256 values, producing a security level comparable to DES. Merkle discusses several constructions for producing an output exceeding 64 bits from f. Only the simplest construction will be discussed here. Given an input x of 119 bits, let CAT(f(CAT("0",x)),f(CAT("1",x))) = CAT(y,z), where y is 112 bits. Then define F0(x) = y. In the above, " " denotes constant bit string. We note that F0 hashes 119 bits to 112 bits. This is not very efficient, but the 112bit output will deter a birthday attack. The latter would require 256 = 7*1016 messages, which is computationally infeasible; more precisely, adequate computing power to effect a birthday attack would also break DES, thereby obliterating DESbased hash functions. This produces F0 which is also a fixedsize strong oneway hash function. Finally F0 is extended to a oneway hash function F accepting inputs of arbitrary size by cascading copies of F0. Given an input x, suppose x = CAT(x1,...,xn), where n is arbitrary and each xi is 7 bits (pad x with a few zeroes if need be). Let R0 = 0, Ri = F0(CAT(Ri1,xi)) (1 ÀÀ i ÀÀ n), where in the first equation the right side is a string of 112 zeroes. Let F(x) = Rn. Ôe the claim is true for n. Suppose zi = CAT(x1,...,xi) (1 ÀÀ i ÀÀ n+1), x = zn+1, zi' = CAT(x1',...,xi') (1 ÀÀ i ÀÀ n+1), x ' = zn+1', Ri = F0(CAT(Ri1,xi)) (1 ÀÀ i ÀÀ n+1), Ri' = F0(CAT(Ri1',xi')) (1 ÀÀ i ÀÀ n+1), where each xi and xi' is 7 bits. Suppose x ÀÀ x' but F(x) = F(x'), i.e., Rn+1 = Rn+1'. Let y = CAT(Rn,xn+1) and y' = CAT(Rn',xn+1'). Then F0(y) = F0(y'). If xn+1 ÀÀ xn+1' then y ÀÀ y' and F0 is broken. Suppose xn+1 = xn+1'. Then Rn = Rn'; but zn ÀÀ zn' since x ÀÀ x'. Now we observe that by definition Ri = F(zi) and Ri' = F(zi'). Hence F(zn) = F(zn'). By the induction hypothesis, F0 can be broken, completing the proof. A disadvantage of this F is that it hashes 7 bits per stage of the cascade, and each stage involves two DES calculations. Thus 3.5 bits are hashed per DES calculation. Merkle gives other constructions which are more complicated but hash up to 17 bits per application of DES. 4.3.2 Coppersmith's attack on Rabintype functions. The Merkle metamethod is an attempt to use a conventional system as a generator for hash functions. This type of approach has its origin in some predecessors which have been broken by combinations of birthday attacks and meetinthemiddle attacks as formulated by Coppersmith [COPP85]. An early attempt to construct a hash function in support of signature schemes was given by Rabin [RABI78]. Let H0 be random (Rabin uses 0) and suppose a message M is divided into fixedsize blocks M1,...,Mn. Suppose E(K,N) represents encryption of block N with key K using a conventional system such as DES. For i = 1,..,nÔeach X he computes a trial Hn1 of the form H(n1,X) = E(X,Hn2). He sorts these 232 values and stores them. Now he generates 232 trial values Y. For each Y he computes a trial Hn1 of the form H'(n1,Y) = D(Y,Hn), where D is the decryption function corresponding to E. We note that H(n1,X) is the value that Hn1 would have if Mn1 = X, and H'(n 1,Y) is the value Hn1 would have if Mn = Y. Each time the opponent tries a Y he searches through the sorted Hlist (about 32 operations per search) and tries to find an X and Y with H(n1,X) = H'(n1,Y). By the birthday phenomenon (app. F), the probability of finding X and Y is at least 1/2. If X and Y are found, the opponent has obtained a bogus message with the proscribed hash value; furthermore this takes at most about 233 encryptions, 232 storage and 64 * 232 comparison operations. This effectively breaks the scheme. Actually Coppersmith's attack was directed against a refinement by Davies and Price [DAVI80]; Rabin's original scheme had been broken earlier. 4.3.3 Quadratic congruential hash functions. Another attempt to create hash functions, differing from both Merkle and Rabintype constructions, was made by Jueneman [JUEN82]. Unlike the Merkle metamethod this uses no external system as an adjunct. It is not keyless; an initialization vector is used. This limits the scope of usage; in particular, such a function is useless for signatureonly schemes. Nonetheless, quadratic congruential constructions are simple and efficient, and hence would be useful in some contexts if secure. Unfortunately it seems as though Coppersmith's attack applies to these as well.Ô (2311). Then the hash value is Hn. Coppersmith broke this first scheme. A revised scheme was proposed in [JUEN86]. The text is split into 128bit blocks, which are further divided into 4 words. Recent results suggest that this scheme may be insecure also. This is especially unfortunate in light of the fact that a hash function given in Annex D of X.509 [CCIT87] is defined similarly, via Hi+1 = Mi + Hi2 mod n. Recent work calls this into question as well. 4.4 Hardware and software support. As noted earlier, RSA and similar exponentiationbased algorithms suffer from relatively low bandwidths. At a minimum this implies that supporting software needs to be carefully designed; hardware support is probably a necessity in many settings. As noted by Sedlak [SEDL87], bandwidths of less than 64 kbps (kilobits per second) will degrade performance in many networks. Furthermore, arithmetic modulo numbers of an adequate number of bits (at least 512) should be supported. Essentially the requirement is a chip (or chip set) that can quickly compute quantities such as a mod b, ai mod b, and perhaps multiplicative inverses or greatest common divisors. As Sedlak notes further, a single chip is preferable for security reasons. Since offchip communication is slower than on chip, singlechip implementations should also yield higher bandwidths. 4.4.1 Design considerations for RSA chips. Some general tradeoffs in such design schemes are discussed by Rivest [RIVE84]. He classifies architectures as serial (S), serial/parallel (S/P), or parallel/parallel (P/P). He then notes the following time and hardware costs: Ô) gates on an S/P. 3. O(k log k) time and O(k2) gates on a P/P. c. Key generation, kbit primes: 1. O(k4) time and O(1) gates on an S. 2. O(k3) time and O(k) gates on an S/P. 3. O(k2 log k) time and O(k2) gates on a P/P. This is a somewhat oversimplified version of [RIVE84] presented only for comparison purposes. Also, there are two basic assumptions used above: exponentiation is an inherently sequential process; and the 100 or so primality tests used in key generation are done sequentially. The first assumption seems intrinsic. However, the second is pragmatic: the tests all use the same hardware, and replicating the latter 100fold for parallel execution would be highly costineffective. Rivest uses the above to give some sample timings: a. Decryption rate, 200digit modulus: 1. 0.005 kbps on an S. 2. 1.3 kbps on an S/P. 3. 95 kbps on a P/P. b. Key generation, 100digit primes: 1. 1,200,000 ms = 20 minutes on an S. 2. 5,000 ms = 5 seconds on an S/P. 3. 70 ms on a P/P. It may be seen that reasonably high bandwidths can be achieved,Ôal ciphering units, in 1.5 um CMOS. He also claims a key generation time of 2 seconds. A 5,000transistor, 5 um CMOS prototype has been realized. In [BRIC89] it is noted that chips capable of up to 450 kbps are being designed. 5. Implementations of publickey cryptography. We examine here some existing implementations of publickey cryptography, some implementations which are in progress, and some which have been proposed. 5.1 MITRENET. One of the earliest implementations of publickey cryptography was in the MEMO (MITRE Encrypted Mail Office) system, a secure electronic mail system for MITRENET ([SCHA82],[SCHA80]). MITRENET is a broadband cable system with a bandwidth of 1 mbps. It uses a carrier sense protocol (e.g., [TANE81]); i.e., each station can sense transmissions of all other stations. In fact the protocol requires all parties to monitor all communication, in effect requiring passive eavesdropping. A priori this provides no secrecy, authentication or integrity services. Furthermore it employs distributed switching, creating a potential for active intrusion. This is a good setting for a privacy enhancement testbed. The MEMO system is a hybrid public/private cryptosystem. DES is used for data encryption. The Diffie/Hellman exponential key exchange of section 2.2 is used for establishment of secret keys.Ô the system. Each user workstation establishes secure communication with the Public Key Distribution Center. A session begins with the user requesting the file of public keys from the PKDC. The request is honored if it passes an identification test involving the user's private component. The file of public keys is then downloaded to the user's workstation, encrypted with DES to ensure integrity. When the user sends a message to another user, the workstation generates a random document key. The latter is used to DESencrypt the message. The public key of the recipient is used to generate a keyencrypting key which is used to DESencrypt the document key. There is no provision for lost keys. Some provision is made for detecting modifications to messages, using checksums. However, the use of Diffie/Hellman alone does not permit authentication to be introduced. 5.2 ISDN. In [DIFF87] a testbed secure Integrated Services Digital Network terminal developed at BellNorthern Research is described. It can carry voice or data at 64 kbps. Publickey cryptography is used for both key exchange and authentication. Reference to the Diffie/Hellman exponential key exchange is made. Evidently it is used in conjunction with DES. The article also alludes to signatures, but implementation is unclear. As noted in [DIFF88], the use of publickey in conjunction with DES provides good security. In particular, the exponential key exchange permits a session key unique to each call. Thus if long term keys are compromised, recordings of calls made prior to compromise cannot be decoded. In conventional systems the compromise of a longterm key may compromise communications made previously with derived keys. Public key computations in the terminal are implemented via a DSP (digital signal processing) chip, while an offtheshelf integrated circuit implements DES, which is used for data encryption. Key management involves keys installed in phones,Ôtronically. Each BNR terminal incorporates a Northern Telecom M3000 Touchphone. 5.2.1 Keys. A public/private component pair is embedded in the phone; this pair is called the intrinsic key. The private component is contained in a tamperresistant compartment of the phone. The public component serves as the name of the phone. These cannot be altered. A second longterm public key stored in the phone is the owner key. This is used to authenticate commands from the owner. It can be changed by a command signed with the current owner key, thus permitting transfer to a new owner. A third longterm public key in the phone is the network key. This identifies the network with which the phone is associated. It validates commands signed with the private component of the network's key management facility. It can authenticate calls from network users. It can be changed by a command signed by the owner key. A shortterm component pair stored in the phone is the working pair. These are embodied in a certificate signed by the key management facility. During the setup process for a call, phones exchange certificates. The network key is used to authenticate certificates. This permits stationtostation calls. Further information is needed for authenticated personto person calls. This information is contained on a hardware "ignition key" which must be inserted into the phone. This key contains the user's private component encrypted under a secret password known only to the user. It also contains a certificate signed by the KMF which contains the user's public component and identifying information. The latter is encrypted as well. Decryption of the information on the ignition key is effected via a password typed on the telephone touchpad. Further certificates authorizing users to use particular phones are acquired by the phone from the key management facility; these are cached and replaced in FIFO fashion. 5.2.2 Calling. A persontoperson call begins as follows: the caller inserts his ignition key and dials the number. The phone interrogates the ignition key to check the caller's identity. The phone then checksÔhowever, it is specified in [CCIT87] that a cryptosystem should be usable for both secrecy and authenticity. That is, the encryption and decryption transformations should be inverses, as is the case with RSA. Multiple cryptosystems and hash functions may be used in the system. A user must possess a distinguished name. Naming Authorities are responsible for assigning unique names. The crux of the authentication framework is the binding of user names and public components. Assuming for the moment that such binding has occurred, subsequent authentication in the ISO framework consists of locating a chain of trusted points within the Directory. Such a chain exists if there is a common point of trust between two authenticating parties. 5.3.1 Use of certificates.Ôhis can be cached; e.g., a component pair could be stored on a smart card along with the user's certificate and the CA's certificate. Additionally, certificates are entered in the Directory. The user may place a copy of the certificate in the Directory, or the CA may be authorized to do this. A user's Directory entry may contain multiple certificates. A CA's entry in the DIT contains the certificates issued for it by other CAs, as well as certificates it issues for other nodes. Semiformally a certificate may be defined as follows: certificate ::= { signature algorithm identifier; issuer name; validity period; subject name; subject information } validity period ::= { start date; finish date } subject information ::= { subject public key;Ôtended by recursion: in a certification path A1,...,An, knowing the public component of Ai permits recovery of the public component of Ai+1 from the certificate for Ai+1 issued by Ai. For a user A to obtain B's certificate involves finding a common trusted point, i.e., a node which has certification paths to the two users individually. Joining these two paths produces a certification path between A and B. The paths, if they exist, may be obtained from the Directory. Although there is no restriction placed on the structure of the authentication graph, an important special case is when it is tree structured. In this event the CAs are arranged hierarchically; hence each node (except the root) has a unique CA (its parent in the tree). Then each CA stores the certificate obtained from its superior CA, as well as various certificates issued by it. The common trusted point for a pair of users is the root of the DIT. A user A may cache the certificates of nodes along the path from A to the root. The other half of the path to another user B is obtained by conjoining the path from the root to B. More generally, a user A who communicates frequently with users certified by a particular CA could store paths to and from that CA (these may be different in the nonhierarchical case). Then to communicate with a given user B certified by that CA, A need only consult the directory entry for the CA and obtain the certificateÔanother's certificate to its directory entry. 5.3.3 Expiration and revocation of certificates. When a certificate expires it should be removed from the Directory. Expired certificates should be retained by the issuing CAs for a period of time in support of the nonrepudiation service. Revocation of certificates may occur because of component compromise involving either the user or the issuing CA. Revocation may also be necessary for administrative reasons, e.g., when a CA is no longer authorized to certify a user. A CA keeps a time stamped list of revoked certificates which the CA had issued, and a list of revoked certificates issued by other CAs certified by the first CA. Entries for CAs in the Directory should contain revocation lists for users and CAs. 5.3.4 Authentication protocols. Suppose A wishes to engage in communication with an authenticated B. Suppose further that A has obtained a certification path from A to B, e.g., by accessing the Directory, and has utilized the path to obtain B's public component. Then A may initiate one, two, or threeway authentication protocols. Oneway authentication involves a single communication from A to B. It establishes the identities of A and B and the integrity of any communicated information. It also deflects replay in communication of authentication information. Twoway authentication adds a reply from B. It establishes that the reply was sent by B and that information in the reply had integrity and was not replayed. It also establishes secrecy of the two communications. Both oneway and twoway authentication use timestamps. Threeway authentication adds a further message from A to B, and obviates the necessity of timestamps. Let ÔB, RA = random number generated by A, RB = random number generated by B, CA = certification path from A to B. Identities refer to the distinguished names of A and B. A timestamp included in a message M includes an expiration date for M. Optionally, it also may include the time of generation of M. Random numbers may be supplemented with sequence numbers; they should not be repeated within the expiration period indicated by a timestamp in the same communication. The oneway protocol is as follows: a. A: 1. generates an RA. 2. constructs message M = (TA,RA,IB,) where is arbitrary. The latter may include data encrypted under EB for secrecy, e.g., when A is sending a data encrypting key to B. 3. sends (CA,DA(M)) to B. b. B: 1. decrypts CA and obtains EA. Also checks certificate expiration dates. 2. uses EA to decrypt DA(M), verifying both A's signature and the integrity of the signed information. 3. checks the IB contained in M for accuracy.Ô      _________\/__________  _________\/_________       compute M' =    compute (TA,RA,IB)   DA(TA,RA,IB)    = EA(M')  ______________________  _____________________       ________\/________  _________\/_________       send (CA,M') to B    verify TA,RA,IB  ___________________  _____________________     \/________________\ / Figure 8. OneWay Authentication Protocol The twoway protocol is: a. as above. b. as above. c. B:Ôn. 3. checks the IB contained in M for accuracy. 4. optionally, checks the RA in M for replay. 5. generates an RB. 6. constructs M' = (TB,RB,IA,RA,) where RA was obtained previously; TB may be zero. 7. sends DB(M') to A. Ômessages to prevent replays and forgery. Annex C of [CCIT87] mentions RSA as an example of a publickey system. A recommendation of a 512bit modulus is made. It is also recommended that a common public exponent of e = 216 + 1 be used (the fourth Fermat number). In particular it is noted that aÔting all conceivable services would be inappropriate. One approach to the design of a generic structure is layered, with a kernel consisting of the most basic services and outer layers added as desired. This is the paradigm we adopt here. The sample proposal presented here is not unique, and is intended for illustration purposes only. A hybrid of publickey cryptography and conventional cryptography presents advantages. The former is used for signatures and for distribution of secret keys used in the latter; the latter is used for bulk data encryption. In addition, a hash function is needed so that only a compressed form of long text need be signed. We do not endorse specific publickey systems or hash functions. The conventional system could be taken to be DES.ÔOSI model, encryption can occur at various levels, including application, presentation, network or transport. As noted in [ISO87], the appropriate level depends on desired granularity of protection. In particular, high granularity refers to separate keys for each application or user and assurance of integrity. For this granularity the presentation or application layers are most appropriate. These two layers will be assumed here. In particular, integration at the application layer gives the individual user complete control over the algorithms used. 6.2 Security threats. Some basic security threats (cf. ann. A of [CCIT87]) include: a. masquerade b. replay c. interception of data d. manipulation of messages Ôipt) of a message. The kernel of a proposed system would include basic support for the above services. This kernel could be standardized to a large extent. However, outer layers of an implementation would need to interface with various external frameworks as well. For example, a system is needed to bind user public components and user identities; this forms an important part of the authentication service. Also, support for nonrepudiation is a complex matter as we have noted. A publickey signature system implements basic nonrepudiation of sending automatically, but does not a priori protect against repudiation of sending due to compromised private components; nor does it provide proof of receipt. Thus (4) is an example of a service which relies heavily on an interface with an external system which most likely would be implementation dependent, since its structure depends on considerations such asÔ in conjunction with authentication implements integrity. Signature refers to application of private components to message digests (output of hash functions); it implements authentication and basic nonrepudiation, in concert with an authentication framework. The form of the latter is implementationdependent. For example, a directory service might be provided, along with "hot lists" of compromised keys. The four mechanisms above may be regarded as the kernel of an implementation. Various other mechanisms which could be provided are noted, e.g., in [ISO87]. For example, to guard against replay, timestamps using synchronized clocks might be provided. Another possibility is the addition of a handshaking protocol. For enhancement of the basic nonrepudiation mechanism (the signature), a notary system could be used. Again these auxiliary services are best added at the discretion of implementors. For example, synchronized clocks may not be present, and notaries violate the desirable feature of pointtopoint communication, and hence should not be included in standard specifications. Ô communicate with other equipment designed to provide the same security mechanisms or functions. 6.5.1 Security. The first and foremost criterion is of course security. It may take 5 years or more for a given method to be thoroughly cryptanalyzed, starting from the time it receives widespread public exposure. One subcriterion in this regard is that a system should be published in an outlet such as a refereed journal with a reasonably large circulation, or a book or conference proceeding which isÔcterized by low bandwidths. Exponentiation based methods such as RSA and the Diffie/Hellman exponential key exchange are examples. Other systems suffer from large data expansion, large key size or long key generation time. There seem to be some inherent tradeoffs in this regard. That is, it does not seem possible to construct a system which is secure and also scores well on all numeric counts. The classic example is key size; e.g., small key size in RSA would produce a high bandwidth, but would also produce insecurity. That is, in this case high bandwidth would produce low cryptanalysis time. Data expansion seems to have a similar impact. For example, in appendix E it is noted that Shamir's knapsack attack runs in time which rises as nd where d = expansion factor. Again high bandwidth produced insecurity. It would be interesting to know whether this trade off notion could be formalized. 6.5.3 Other criteria. Versatility is an important criterion. The RSA system is distinguished in this regard since it supports both key distribution and signatures. All other major systems are limitedÔibed in this section is compatible with a subset of [CCIT87]. Public components of receivers are used as keyencrypting keys; private components of senders are used to encrypt message digests. Dataencrypting keys are generated for individual sessions. These may be associated to an arbitrary conventional cryptosystem; DES is a possibility. The public and private components may be associated to different publickey systems if different algorithms are used for key encryption and signatures. Certificatebased key management is proposed. Since we are focusing on localarea networks, a simple tree structure is proposed, consisting of a root and one additional level containing all users. In particular, the root issues all certificates. Certification paths are thus trivial. 6.7.2 Component generation and storage. It is proposed that users generate their own public/private component pairs, using trusted software or hardware supplied by the system. Key pairs could be stored on smart cards [HAYK88] or tokens, along with the user's certificate. Such kernel mechanismsÔdjusted for parity. Data encrypting keys can be produced dynamically by pseudorandom number generators which are timevariant. An example of a generator for dataencrypting keys, as well as initializing vectors, is given in appendix C of [ANSI85]. Let E(K,Y) be encryption by DEA (essentially equivalent to DES) with key K. Let K be a DEA key reserved for usage in key generation and let V0 be a 64bit secret seed. Let T be a date/time vector, updated on each key or IV generation. Let Ri = E(K,E(K,Ti) XOR Vi), Vi+1 = E(K,Ri XOR E(K,Ti)). Then Ri may be employed as an IV. To obtain a DEA key from R, reset every eighth bit to odd parity. Routines for generating DES keys are supplied with various products. Schemes for pseudorandom number generation include [AKL 84], [BLUM84],[BRIG76]. The last gives a pseudorandom bit generator whose security is equivalent to discrete logarithm. 6.7.4 Issuance and distribution of certificates. Public components are registered with the root. The root generates a certificate containing the user's public component and identifying information, and a validity period. Distribution of certificates by users is recommended; certificates may be cached. This eliminates the necessity of having the root be online. Ôattempted repudiation. 6.7.5 Compromised or invalidated certificates. Assuming that certificates are cached, the root must periodically issue hot lists of invalidated certificates. This kernel service may be augmented in various ways to provide more current validity information. Again, however, additional mechanisms have drawbacks. As noted above, a central directory service could provide realtime validity checks, but it must be online. Furthermore, such checks a priori do not account for compromised private components, during the period following compromise but before a report is filed with the root. Even if users are required to report known compromises within a specified time period, a compromise may not become known to the user until later. As we noted, this creates an administrative/legal problem, since a user could disavow a signature on the basis of the latter type of compromise. A notary system can be used to add a layer of validity by having secondary signatures attest to the validity of senders' signatures, but this violates the desired criterion of pointto point communication. This is clearly an area in which solutions must be customized to some degree. For example, authentication in a system used for financial transactions may require more stringent controls than a kernel provides. The root should maintain a timestamped list of revoked certificates. 6.7.6 Authentication. A hash function is used to produce a message digest. This is signed with the private component of the sender. Timestamps and random numbers may also be included to prevent replay. If more than one hash function is permitted, identification of the function usedÔent of the root, which is assumed to be known to all users. Then B forwards his certificate to A, who validates it. Each may cache the certificate of the other. Now A and B may communicate securely. If A sends a message to B, B uses A's validated public component, extracted from A's certificate, to decipher the message digest. Then B may decrypt the key used for data encryption, using B's private component. Now B may decrypt the message text using this session key, then re compute the message digest and compare to the transmitted form. Appendix A. Mathematical and computational aspects. We discuss here some issues related to the computational complexity of publickey cryptography. The foundation of the security of such systems is the computational infeasibility of performing cryptanalysis, in contradistinction to the relative ease of encryption/decryption. We analyze some of the issues which arise in this context. Also included is some background theoretical computer science needed to discuss the issue of computational complexity of cryptography and cryptanalysis, as well as zero knowledge proofs and related schemes. This discussion may aid in understanding the security basis of publickey cryptography. It may also shed some light upon the more practical matter of choosing key sizes, i.e., the number of bits in private and public components. This section may safely be skipped by readers who do not wish to gain an indepth understanding of such issues. A.1 Computational complexity and cryptocomplexity. An ideal cryptosystem would have the property that encryption and decryption are easy, but cryptanalysis is computationally infeasible. In practice, this is commonly interpreted (e.g., [DIFF76b]) to mean that encryption/decryption should be executable in polynomial time, while ideally cryptanalysis should take exponential time. More generally, cryptanalytic time should be an exponential function of encryption/decryption time. Unfortunately, it is difficult to determine when this criterion holds in practice. This is because it is usually very difficult to determine a nonpolynomial lower bound for the time required forÔdless of n. The class NP is (loosely) the class of decision problems solvable in polynomial time via a nondeterministic algorithm. Perhaps the single most important problem in computer science is to decide whether P = NP. The NPcomplete problems are the hardest subclass of NP, having the property that if one instance of the subclass is in P then P = NP. Many classical combinatorial search problems can be given NPcomplete formulations. Traveling salesman and knapsack are examples (see [GARE79] for a long list). The class of NPhard problems are those problems, decision or otherwise, which are at least as hard as NPcomplete problems. Some NPhard problems are so hard that no algorithm will solve them; they are undecidable. Such problems cannot be in NP. An example is the halting problem (e.g., [HORO78]). Ô (e.g., [GROL88]). An early characterization was suggested by Shamir [SHAM79], who quantifies this notion by defining a complexity measure C(n,a) for algorithms as follows: C(n,a) is a measure of an algorithm if at least a fraction a of problem instances of size n can be solved by the algorithm in time C(n,a). For example, an algorithm for finding one factor of n could have complexity C(n,1/2) = O(1), since n has a 50% chance of being even. However, such investigations have thus far failed to produce a comprehensive framework, although they may be useful in a few special instances. Another simple example illustrates the difference between worst case and averagecase complexity: as noted in [RABI76], algorithms to sort n items are often predicated on the assumption that the items are arranged in random order; i.e., all n! arrangements are equally likely. If the file has a realworld origin it is more likely that the file is already partially sorted. An optimized algorithm might anticipate this and utilize an adaptive strategy. In practice, a cryptosystem for which cryptanalysis has an averagecase polynomial complexity is generally worthless; in fact this remains true if any measurable fraction of all instances permits polynomialtime cryptanalysis (this is difficult to make precise, since the fraction may vary with key size). Thus there is no a priori connection between the breaking of a system and the difficulty of the underlying problem, since the latter is characterized in terms of worstcase complexity. For example, often there exists a heuristic technique which yields an approximateÔ instead. It would be interesting to know if such systems could be made practical. A.4 Probabilistic algorithms. Another important distinction between the classical theory of complexity and cryptocomplexity is that the classical theory of algorithms does not encompass probabilistic algorithms (e.g., [RABI76]), which again may produce rapid solutions to problems in many instances but not even terminate in a few instances. They may also produce answers which are probably but not necessarily correct. Such algorithms are inappropriate in many contexts, e.g., realtime control settings in which a response must be guaranteed in a fixed period of time, or where provable solutions are required. However, they are powerful tools in both cryptography and cryptanalysis. As noted in [RABI76], probabilistic algorithms cannot be measured by classical criteria, which focus on worstcase runtime. Instead, a probabilistic algorithm may involve a tradeoff between execution time and confidence. For example, most numbers have all small factors. If an algorithm exploits this fact it may terminate quickly for most inputs but take exponential time when large primes appear as factors. Gill [GILL77] models probabilistic computation by extending the classical Turing machine model (e.g., [HORO78]) to the probabilistic Turing machine (app. D). This has proven valuable in the analysis of cryptographic systems, and probabilistic encryption schemes in particular. A.5 Status of some relevant problems. The security of several major cryptosystems mentioned herein depends on the hardness of problems whose complexity status is unresolved. This includes factoring and discrete logarithm. The importance of the subclass of NPcomplete problems emerges in this regard: if a problem is known to be in NP but is not known to be NPcomplete, a solution to the problem in polynomial time (placing the problem in P) would not imply that problems such as traveling salesman are in P. The latter proposition is widely disbelieved. A second relevant class is coNP, the complements of problemsÔhm exists, even probabilistic. If e = 2 the complexity is essentially equivalent to factoring n (lem. N.3.2). If e > 2 the status is less clear; as a consequence it is not clear that the security of RSA is equivalent to factoring. Brassard [BRAS79] has shown that the discrete logarithm has an associated decision problem which lies in the intersection of NP and coNP. Thus, if either factoring or taking discrete logarithms is NPhard, it follows from the definition of this class that the associated decision problem is NPcomplete and in coNP. In turnÔng at present is siliconbased. Thus all estimates of achievable computer performance are geared to this technology. The question arises as to whether a radically different technology such as superconductivity or optical computing will make siliconbased performance standards obsolete, and if so, when this might occur. We have no idea, and hence we ignore these. Gallium arsenide technology is another matter. It has already been integrated into some existing supercomputers. Some of the differences between GaAs and silicon VLSI are (e.g., [MILU88]): a. GaAs gates have a higher switching speed. b. Offchip communication in GaAs pays a relatively higher penalty. c. GaAs chips have lower density.Ô hierarchies; these may not carry over mutatis mutandis to GaAs. We conclude that at the moment, GaAs technology does not present a real threat to silicon performance standards. Furthermore, it does not appear likely that problems such as yield and integration will be solved in the near future. Thus, for the remainder of appendix B we assume no radical change in technology from the present. B.2. Computing modes. Classically, computing was dominated by the Von Neumann model, with a single processor executing a single instruction scheme on a single data stream. This paradigm reached its peak with computers such as the Cray1 [CRAY80] and CYBER 205 [CONT80]. However, the performance of a single processing unit is limited by its clock speed. It does not seem feasible to reduce major cycles much below 1 ns with silicon technology. Furthermore, at these speeds memory access becomes a bottleneck, not to mention I/O. Thus it is not likely that uniprocessors will exceed 109 operations per second, barring radical new technologies. Two alternatives to the Von Neumann model are parallel and distributed computing (e.g., [HWAN84]). Parallel computing generally refers to processors in one box; distributed means each processor is in its own box. Parallel computers may (loosely) be subdivided into sharedmemory, in which all processors share a common address space, and distributedmemory, in which each processor has its own address space. These modes remove the restriction on the number of instruction and/or data streams whichÔsystems. The Denelcor HEP (e.g., [KOWA85]), Floating Point TSeries [HAWK87] and ETA10 [STEI86] are examples of parallel systems which have not proven to be commercially successful. Also, Cray and other supercomputer manufacturers have been reluctant to expand into largescale parallelism, partially because of costrelated concerns. This creates an interesting situation from a cryptographic point of view: there may be cases where a computer powerful enough to break a given system could be built in theory. Security of the system might then rest on the assumption that no one will spend the money to build it, or that the only units built will belong to wealthy government agencies and be subject to tight controls. Even if computers with 1000 or more powerful processors are constructed, the question arises as to whether such a configuration can achieve computing power in proportion to the number of processors, i.e., linear speedup. The mode of interconnecting the processors and memories is critical. If the sharedmemory configuration is used, with a collection of processors accessing common memory partitioned into modules, interference in paths through the network or in simultaneous attempts to access a module will cause a bottleneck if a lowcost, lowbandwidth network such as a bus is used. If a highbandwidth network such as a crossbar is used (i.e., with concurrent data transfers possible between many processors and memory modules), the number of units interconnected is limited by cost which rises as the square of the number of processors. Thus such systems seem to be inherently limited in the extent to which they can improve on uniprocessor performance. An alternative is to connect processor/memory pairs using a network such as a hypercube [SEIT85]. Machines of this type with up to 65,536 weak processing elements (e.g., the Connection Machine [HILL85]) or up to 1024 powerful processors (e.g., the NCUBE/10 [HAYE86]) have been constructed, and systems with up to 32,000 Cray1 level processors have been proposed. There is debate (and some controversy) over the speedups which such distributedmemory machines can achieve. The latter consideration is related to cost effectiveness, which requires nearlylinear speedup. Also, the cost of interconnection in a hypercubebased system rises as O(n log n),Ôs and architectures, but also the greatest amount of computing power which might realistically be brought to bear against a given task. B.3 Some relevant algorithms and implementation. Most of the powerful algorithms for factoring and discrete logarithm are fairly new. As we have noted, most of them have not been fully analyzed for runtimes. Nonetheless, some standards have emerged in this regard. The best guess for the future can only amount to anticipation of improvements in the present algorithms. B.3.1 Quadratic sieve factoring algorithm. The quadratic sieve [POME84] provides an alternative to the earlier continued fraction factorization algorithm [MORR75]. As noted in [DAVI83b], the continued fraction approach usesÔapabilities may be nontrivial. Hence it is not clear to what extent the preceding efficiency can be maintained as the degree of parallelism grows. An alternative is distributed computing: Silverman [SILV87] has used the quadratic sieve implemented via a network of 9 SUN 3 workstations to factor numbers up to 80 digits in 8 weeks. Recently another network was used to factor 106digit numbers [LENS89]. It should be noted that the results obtained via the quadratic sieve are directly relevant cryptanalytically, since the integers factored are general. Integers of up to 155 digits, but with special forms, have been factored, also by use of networks [SIAM90]. However, these results are only indirectly relevant to systems such as RSA, assuming moduli are properly chosen. B.3.2 Computations in finite fields. This is a subject which has been explored fairly thoroughly (e.g., [BART63]), and we do not review it here. Multiplication of elements in GF(m) has classically been implemented at the circuit level using linear feedback shift registers. However, Laws [LAWS71] has noted the potential for using cellular arrays. These are highly amenable to VLSI implementation. A pipeline architecture for multiplication and inverses is proposed in [WANG85]. One class of algorithms of particular interest is for discrete logarithms in GF(pn). Still more particularly, the case n = 2 has been explored considerably ([BLAK84],[BLAK84b],[COPP84]). Since finite logarithms are easy to compute in GF(m) if m has only smallÔnced by implementation efficiency. B.3.3 Other algorithms. Many of the most fundamental operations in this setting seem to be characterized by inherent sequentiality. An example is exponentiation; computing the nth power seems to take log n steps regardless of the number of processors available. Another classical example is greatest common divisor. Although some partial results are noted in [ADLE86], major improvement over Euclid does not seem forthcoming regardless of advances in architecture. Many of the powerful factoring algorithms are highly parallelizable (e.g., [SCHN84]). The main requirement is existence of appropriate architectures. B.4. Applicationspecific architectures. Generalpurpose architectures such as the Cray are of interest in this setting because of their immediate availability. At the other extreme, architectures closely matching the algorithms of interest could be constructed, but their overspecialized nature would virtually preclude their commercial distribution. In between are classes of architectures which are more versatile but not truly generalpurpose. We note several examples of partlyspecific architectures and a proposed highlyspecific machine. B.4.1 Systolic and wavefront arrays. The notion of systolic arrays ([KUNG82],[KUNG78]) is an extension of pipelining. The idea is to have a collection of processors operate on data which is pulsed rhythmically through the array. If the original requirement of a synchronous mode of operation is relaxed, the result is a wavefront array [KUNG82b]. Both types were originally targeted at applications such as signal processing which are computeintensive and involve repetitions of operations on many operands. Ông algorithms are noted in [BREN83b]. It would be of interest to know what a more generalpurpose linear systolic array such as the Warp [ANNA87] (which curiously more closely resembles a wavefront array) could accomplish on some of the problems discussed in this paper, and factoring in particular. The Warp is already in production. B.4.2 Proposal for a quadratic sieve machine. Pomerance et al. [POME88] describe a pipeline architecture which would efficiently execute the quadratic sieve. This notion is of considerable interest to anyone implementing an algorithm such as RSA, since such a machine could presumably factor numbers beyond the reach of presentday supercomputers. Costeffectiveness is carefully analyzed, as is critical for an applicationspecific architecture. They speculate that a $50,000 version of the architecture should factor 100digit numbers in about 2 weeks; or 140 digits in a year on a $10 million version; or 200 digits in 1 year on a $100 billion version. It should be noted that the last is clearly predicated on the notion that the architecture and algorithm will scale linearly with the number of processing units; we noted earlier that various bottlenecks such as interprocessor communication and memory access make this somewhat dubious. Nonetheless the possibility arises that moduli approaching 200 digits may be necessary in RSA because of the potential existence of machines such as these. The crux of the architecture are the pipe and pipe I/O units. These should be custom and should be able to handle variable strides without the considerable loss of efficiency which usually accompanies nonconstant stride. The two units should be chained together. The pipe should consist of stages, all of which are bus connected to the pipe I/O unit. The cycle time of memory should be the same as the processing elements. It is interesting to note that this architecture bears a close resemblance to a linear systolic array. B.4.3 Massively parallel machines. An alternative to pipelined machines is to configure a large number of primitive processing elements in an array and have them execute the same instruction stream synchronously, processing a large quantity of data in parallel (SIMD mode). Such machines areÔ consisting of a control unit and a tape. At any time M is in some state, and the read/write head of the tape is over some symbol on the tape. If D(q,a) = (p,b) then initially the head is scanning aÔ M = (K,S,D,s) such that for any w in W, the configuration (s,#w,#,e) yields (h,#u,#,e), i.e., u is the output of M on input w, and furthermore u = f(w). Then f is said to be computed by M. Suppose alphabet A does not contain #, Y or N. Suppose L is a language in A* and X is its characteristic function, i.e., for w in A*, X(w) = Y if w is in L, X(w) = N otherwise. If X is computed by Turing machine M then M is said to decide (or recognize) L. Conversely, if X is the characteristic function of a language L and X is Turingcomputable, i.e., there exists a Turing machine which computes X, then L is said to be Turingdecidable. Ôterministic machines, which are merely special cases of the more general nondeterministic case. It is also true (but not as trivial) that any language accepted by a nondeterministic Turing machine is also accepted by a deterministic Turing machine. That is, nondeterminism does not increase the power of Turing machines insofar as the class of languages is concerned. Similar extensions hold for decidable languages. C.3 Computational complexity. The time complexity of Turing machines is measured by the number of steps taken by a computation. If T is a function on the nonnegative integers, a deterministic Turing machine M is said to decide language L in time T if it decides in time T(n) or less whether w is or is not in L, where w has length n. If T is a polynomial then L is said to be decided in polynomial time. If a language is decidable in polynomial time on a multitape deterministic Turing machine then it is decidable in polynomialÔgs a and b is written ab. If A and B are subsets of S*, AB is the set of strings formed by concatenating elements from A and B. C.1 Turing machines. A (onetape, deterministic) Turing machine is a quadruple (K,S,D,s) where: a. S is an alphabet which contains a blank = #, but not the symbols L or R which are reserved for tape movement to the left or right. b. K is a set of states which does not include the halt state = h, which signals an end to computation. c. s = initial state; it is in K. d. D : K x S > (K + {h}) x (S + {L,R}) where + denotes union. A Turing machine = M may be interpreted semiphysically asÔst nonblank symbol to the right of the head position. This gives the configuration a unique description. In particular, if the input to M is w then the initial configuration of M is (s,#w,#,e). M is said to halt on input w if some halted configuration (state = h) is reached from (s,#w,#,e) in a finite number of steps; then it is said that (s,#w,#,e) yields a halted configuration. If M halts on input w, M is said to accept w. The language accepted by M is the set of strings w accepted by M. Conversely, a language is said to be Turingacceptable if it is accepted by some Turing machine. Suppose S is an alphabet, T and W are subsets of S, and f: W > T. Suppose there exists a Turing machine M = (K,S,D,s) such that for any w in W, the configuration (s,#w,#,e) yields (h,#u,#,e), i.e., u is the output of M on input w, and furthermore u = f(w). Then f is said to be computed by M. Suppose alphabet A does not contain #, Y or N. Suppose L is a language in A* and X is its characteristic function, i.e., for w in A*, X(w) = Y if w is in L, X(w) = N otherwise. If X is computed by Turing machine M then M is said to decide (or recognize) L. Conversely, if X is the characteristic function of a language L andÔa relation on (K x S) x ((K + {h}) x (S + {L,R})). That is, D is now multiplevalued, so that the next configuration is no longer uniquely determined by the present. Instead, in a given number of steps a configuration may yield a number of configurations. Consequently an input may yield many outputs. A sequence of steps starting from a given input defines a computation; in general many computations are possible on one input. A nondeterministic machine is said to accept an input if there exists a halting computation on it. Again the language accepted by a machine is the set of strings accepted by it. Trivially any language accepted by nondeterministic machines is also accepted by deterministic machines, which are merely special cases of the more general nondeterministic case. It is also true (but not as trivial) that any language accepted by a nondeterministic Turing machine is also accepted by a deterministic Turing machine. That is, nondeterminism does not increase the power of Turing machines insofar as the class of languages is concerned. Similar extensions hold for decidable languages. C.3 Computational complexity. The time complexity of Turing machines is measured by the number of steps taken by a computation. If T is a function on the nonnegative integers, a deterministic Turing machine M is said to decide language L in time T if it decides in time T(n) or less whether w is or is not in L, where w has length n. If T is aÔic Turing machine is denoted by P. The class of languages acceptable in polynomial time on some nondeterministic Turing machine is denoted by NP. It is not known whether P = NP. Appendix D. The theory of probabilistic computing. Probabilistic algorithms are employed as adjuncts in cryptosystems for purposes such as finding primes. They have also produced virtually all major practical cryptanalytic algorithms for factoring, discrete logarithm etc. Here we review an extension of the classical theory of computation which incorporates probabilistic computing. This extension has proven particularly valuable in the study of probabilistic cryptosystems. An ordinary deterministic multitape Turing machine may be considered to have an input tape, an output tape, and readwrite worktapes. A modification of the ordinary model (e.g., [GILL77]) is the probabilistic Turing machine. It has a distinguished state called the cointossing state, which permits the machine to make random decisions. In terms of languages recognized, these have the same power as deterministic machines. However, time considerations are more subtle. In particular, a notion of probabilistic run time is needed, rather than measures such as maximum run time used for ordinary machines. A probabilistic Turing machine operates deterministically, except when it is in a special cointossing state (or states). In such a state the machine may enter either of two possible next states. The choice between these is made via the toss of an unbiased coin. The sequence of coin tosses may be considered to constitute the contents of an auxiliary readonly input tape, the random tape, which contains a binary string. Thus a computation by a probabilistic machine is a function of two variables, the ordinary input tape and the random tape. If the random tape is unspecified, the output of the computation of probabilistic machine M, M(x), is a random variable (e.g., [MCEL77]): M produces output y with probability Pr{M(x) = y}. For a given input x, there may exist a y such that Pr{M(x) = y} > 1/2.Ôes such as RSA as well as zeroknowledge schemes, probabilistic encryption etc., is whether either of these inclusions is proper. Appendix E. Breaking knapsacks. We give a brief account of the demise of the Merkle/Hellman trapdoor knapsack publickey system and some of its variants. A much more complete discussion is given in [BRIC88]. We recall from section 4.2.1 that the security of this approach rests on the difficulty of solving knapsack problems of the form C = b1 * M1 + ... + bn * Mn, ÔDLE82] to break the Shamir/Graham knapsack, and by Brickell [BRIC84] to break the iterated Merkle/Hellman knapsack. The multiplicative version was broken by Odlyzko [ODLY84]. In fact all major proposed knapsacks based on modular disguises have been broken using this approach. It should be noted that the lowdensity attacks ([BRIC83],[LAGA83]) are successful where finding trapdoors fails. These use a measure of density for a knapsack with coefficients b1,...,bn defined by density = n/(log max {bi}). This type of attack is independent of whether the knapsack is a disguised version of another. Trapdoors, in contrast, are easiest to find for high density knapsacks. The concept of density is related to two important parameters of cryptosystems, namely information rate and expansion factor d. In [LAGA84] the information rate is defined to be the ratio of the size of plaintext to the maximum size of the ciphertext. This is the reciprocal of d, i.e., ciphertext/plaintext. Information rate is essentially the same as density, although for the above knapsack and modulus u it is defined slightly differently, namely as n/(log nu). Both definitions are derived from approximations to the actual ciphertext size, which is log(b1 * M1+...+bn * Mn). Lagarias notes that the attack in [SHAM84b] runs in time O(P(n)*nd) for a polynomial P. Hence the attack is feasible if d is fixed but not if the expansion factor d is large. This illustrates the interrelation between security and practicality. Appendix F. Birthday attacks. In section 4 we noted several usages of birthday attacks against hash functions. Here we give a brief summary of the relevant mathematics. Suppose H is a function which has m possible outputs. Whenever H outputs a value it is totally random and independent of any previous values which have been output. If H is evaluated k times, each output is akin to an object placed in one of m cells corresponding to the range of H. Since the k values of H are independent, any object could be placed in anyÔFor n > 1 let Zn* = {x À À Zn : x > 0 and GCD(x,n) = 1}. For example, Z10* = {1,3,7,9}. That is, Zn* consists of the nonzero elements of Zn which are relatively prime to n. If a À À Zn* let a * Zn* = {a * x mod n : x À À Zn*}. For example, 2 * Z10* = {2,6,14,18} mod 10 = {2,6,4,8}, 3 * Z10* = {3,9,21,27} mod 10 = Z10*. We have: LEMMA G.1. Suppose n > 1 and a À À Zn*. Then a. For any x and y: a * x ÀÀ a * y ( mod n ) iff x ÀÀ y (mod n). b. a * Zn* = Zn*. c. a has a multiplicative inverse modulo n; i.e. there exists b À À Zn* such that b * a ÀÀ 1 (mod n). Proof: if x ÀÀ y (mod n) then trivially a * x ÀÀ a * y (mod n). Conversely, suppose a * x ÀÀ a * y (mod n). Then n  (a * (x  y)). But GCD(a,n) = 1, so n  (x  y), i.e. x ÀÀ y (mod n). Thus (a) holds. For (b): if x À À Zn* then GCD(x,n) = 1, so GCD(a*x,n) = 1. Thus a * x mod n À À Zn*. Hence a * Zn* is contained in Zn*. By (a), if a * x ÀÀ a * y (mod n), then x ÀÀ y (mod n). Thus a * Zn* consists of n distinct elements, and cannot be a proper subset of Zn*; (b)Ô + p1 + Zn*. Then (b) follows. QED. G.2 The EulerFermat Theorem. LEMMA G.2.1 (Euler's Theorem). Suppose n > 0 and a À À Zn*. Then aÀÀ(n) ÀÀ 1 (mod n). Proof: if Zn* = {r1,...,rm} then a restatement of (b) of lemma G.1 is ÔGalois fields, and denoted GF(pn). We have already noted that GF(p) = Zp is defined by doing arithmetic modulo p. The elements of Zp are called the residues modulo p; i.e., each integer x has a unique representation x = q * p + r where r À À Zp. To define GF(pn) we choose an irreducible polynomial f(x) of degree n in the ring of polynomials modulo p (e.g., [DENN83] p. 49). Now arithmetic may be defined on this ring of polynomials, modulo f(x); i.e., write g(x) ÀÀ h(x) iff f(x) is a divisor of g(x)  h(x). Each polynomial g(x) has a unique representation g(x) = q(x)f(x) + r(x) for some polynomial r(x) of degree at most n1. The residues modulo f(x) are the elements of GF(pn). These consist of polynomials of degree ÀÀ n 1 with coefficients from Zp. Each of the n coefficients of a residue has p possible values, accounting for the pn element count for GF(pn). Appendix H. Euclid's algorithm. On a number of occasions we referred to Euclid's algorithm, which can be used to find greatest common divisors and multiplicative inverses. We give some versions of it here. These versions are recursive, and minimize storage requirements. Suppose x and y are arbitrary positive integers. Their greatest common divisor GCD(x,y) can be computed in O(log max{x,y}) steps by recursively employing GCD(s,t) = GCD(s,t mod s). This is Euclid's algorithm: function GCD(x,y) returns integer; /* return greatest common divisor of x > 0 and y > 0 */ s := x; t := y; Ôn of GCD yields the multiplicative inverse of x modulo n, i.e., u with x * u ÀÀ 1 (mod n). With [y] denoting the largest integer ÀÀ y, the extended Euclid algorithm to find u is: function INVERSE(n,x) returns integer; /* for n > 0 and x À À Zn* return u À À Zn* with u * x ÀÀ 1 (mod n) */ procedure Update(a,b); temp := b; b := a  y * temp; a := temp; end Update; g := n; h := x; w := 1; z := 0; v := 0; r := 1; while (h > 0) do y : = [g/h]; Update(g,h); Update(w,z); Update(v,r); end while; return(v mod n); end INVERSE; For example, for n = 18, x = 7, this gives the values g: 18 7 4 3 1 h: 7 4 3 1 0 w: 1 0 1 1 2 z: 0 1 1 2 7 v: 0 1 2 3 5 r: 1 2 3 5 18 y: 2 1 1 3 Finally u = 5 mod 18 = 13 is returned. This is equivalent to finding the sequence 7/18, 2/5, 1/3, 1/2, 0/1 in which eachÔm*log max{xi}) time. Appendix I. The Chinese Remainder Theorem. The Chinese Remainder Theorem is useful for purposes such as simplifying modular arithmetic. In particular we note in a later appendix that its use increases the efficiency of decryption in RSA. We begin with a special case: with Zn as in appendix G, we have LEMMA I.1. Suppose p and q are primes and p < q. Then: a. For arbitrary a À À Zp and b À À Zq, there exists a unique x À À Zpq with x ÀÀ a (mod p), x ÀÀ b (mod q). b. If u * q ÀÀ 1 (mod p), the x in (a) is given by x = (((a  b) * u) mod p) * q + b. Ôx via a and b, i.e., the residues of x modulo p and q, respectively. Although the most general case of the Chinese Remainder Theorem is not used in this exposition, we remark that the above can be extended: THEOREM I.1. Given pairwise relatively prime moduli {p1,...,pn} and arbitrary {a1,...,an}, there exists a unique x À À [0,p1*..*pn) satisfying x ÀÀ ai (mod pi) for each i. Proof: a straightforward generalization of the above (e.g.,Ô2 is prime. Let s = (p1)/2. Then a. The elements of Sp are precisely the quadratic residues modulo p. b. There are s quadratic residues modulo p. c. There are s quadratic nonresidues modulo p. Proof: as noted above, Sp is a subset of the set of quadratic residues modulo p. Furthermore, if x2 ÀÀ y2 (mod p) then p  x2y2; hence p  xy or p  x+y. If x and y are in (0,s] then 1 < x+y < p; thus p  xy; hence x = y. It follows that Sp contains distinct elements. QED. Now suppose a is a quadratic residue, x2 ÀÀ a (mod p), and x À À Zp*. We note (p  x)2 ÀÀ p2  2 * p * x + x2 ÀÀ a (mod p). Since 0 < x < p, either x or p  x is in (0,s]. It follows that a À À Sp. Thus the set of quadratic residues modulo p is contained in S. Hence the two sets are identical, establishing (a). Since Sp = s, (b) follows. Also, the complement of Sp in Zp* is the set of quadratic nonresidues modulo p. Since Zp* = 2s, the complement of Sp also has cardinality s; (c) follows. QED. J.2 The Jacobi symbol. If p is a prime > 2 and 0 < a < p, the Legendre symbol (a/p) is a characteristic function of the set of quadratic residues modulo p (e.g., [RADE64]): a. (a/p) = 1 if a is a quadratic residue mod p. b. (a/p) = 1 if a is a quadratic nonresidue mod p. More generally, if k > 1 is odd and h is in Zk*, the Jacobi symbol (h/k) may be defined as follows: a. The Jacobi symbol (h/p) coincides with the Legendre symbol if p is prime. b. If k = p1*...*pm with pi prime, (h/k) = (h/p1)*...*(h/pm). Ô, which is Gauss' law of quadratic reciprocity (e.g., [RADE64]). The above shows that the Jacobi symbol (a/n) can be computed in O(log n) steps. J.3 Square roots modulo a prime. Regarding solutions of x2 ÀÀ a (mod p), i.e., the square roots of a modulo p, we have: LEMMA J.3.1. Suppose p > 2 is prime. Let s = (p1)/2. Suppose a is a quadratic residue modulo p. Then a. a has exactly two square roots modulo p in Zp*. One of these lies in (0,s] and the other in (s,p1]. b. the square roots of a modulo p can be found in probabilistic polynomial time. Proof: by lemma J.1.1 we know that a À À Sp as defined in J.1; hence there exists a unique x in (0,s] with x2 ÀÀ a (mod p). Then y = p  x satisfies y2 ÀÀ a (mod p), and y is in (s,p1]. Conversely, suppose y is in (s,p1] and y2 ÀÀ a (mod p). Then x = p  y is in (0,s], and x2 ÀÀ a (mod p). Hence y is unique. Thus we have (a). For (b) we invoke a probabilistic polynomialtime algorithm for finding square roots modulo a prime (e.g., [PERA86] or p. 22 of [KRAN86]). QED. Ôuence modulo p has at most s solutions (e.g., [RADE64] p. 21). Thus all quadratic nonresidues b must have ep(b) = p  1. QED. Also, ep can be evaluated in O(log p) time. Thus quadratic residuosity mod p can be decided in O(log p) time. Appendix K. Primitive roots and discrete logarithms. The use of primitive roots was noted in sections 2.2 and 4.2.2. We also observed that the security of exponentiationbased cryptosystems depends in part on the difficulty of computing discrete logarithms. Here we briefly explore these topics. Let Zp* be as in appendix G. Suppose p is a prime and a À À Zp*. Suppose m > 0, am ÀÀ 1 (mod p), but ar !ÀÀ 1 (mod p) for any r with 0 < r < m. Then we say that a belongs to the exponent m modulo p. The existence of m is guaranteed by the Euler/Fermat Theorem (cor. G.2.1), which shows m < p. Let Cp(a) = {ax mod p : 0 ÀÀ x < m}. Then we have Ô subset of Zp*. The result follows from lemma K.1, which shows Cp(g) = p  1 = Zp*. QED. The x in lemma K.2 is the discrete logarithm, or index, of y modulo p with base = g. However, the range of the logarithm can be any interval of length p  1. We have used [0,p2], but, e.g., we could also take x to lie in [1,p1]. A restatement of lemma K.2 is that the cyclic subgroup generated by the primitive root g modulo p is the whole group Zp*. Thus g is a generator of Zp*. LEMMA K.3. Suppose p > 2 is prime and p1 has k distinct prime factors which are known. Then: a. The number of primitive roots modulo p is ÀÀ(p1), where ÀÀ is the Phi function (app. G.1). 2. Testing a given a to determine if it is a primitive root modulo p can be done in time O(k * log p) = O((log p)2). Ô. Thus gs ÀÀ 1 (mod p). For (b): suppose x2 ÀÀ g (mod p). Now x ÀÀ gr (mod p) for some r; hence g2r ÀÀ g (mod p), and g2r1 ÀÀ 1 (mod p). Thus 2r  1 ÀÀ 0 (mod p 1), impossible since p  1 is even. QED. Appendix L. Primality testing. Testing large integers to determine whether they are prime plays a major role in key generation in RSA and other publickey systems. We give a few examples of algorithms to effect this. It is wellknown (e.g., [KNUT81] p. 366) that if the number of primes between 1 and x is f(x), then with ln denoting natural logarithm (to base e = 2.718..), f(x) = x/(ln x) + O(x/(ln x)2). Ôoint, more efficient algorithms are desirable. Thus, probabilistic tests may be used in practice to make an "educated guess" as to whether a candidate is prime. Often a Monte Carlo approach is employed. In this event there is a slight possibility of an erroneous conclusion; however, the error probability can be made arbitrarily small. Typically, a sequence of "witnesses" attest to the primality or compositeness of a number. Agreement among a group of about 100 witnesses is generally sufficient to reach a conclusion beyond any reasonable doubt, although evidently the legality of this procedure has not been tested in the courts. L.1 The Solovay/Strassen test. One example of a probabilistic polynomialtime primality test is the Solovay/Strassen test [SOLO77] mentioned in section 4.1.1 (although this approach is commonly attributed to Solovay and Strassen, it was noted implicitly by Lehmer [LEHM76]; cf. [LENS86]). If n is an odd positive integer and a À À Zn*, with theÔ e(b,n) (mod n). That is, e is also multiplicative. It follows that G is a subgroup of Zn*. The order of G must divide the order of Zn* (e.g., [HERS64] p. 35). Thus if G ÀÀ Zn*, G has cardinality at most (n 1)/2. Solovay and Strassen showed that indeed G ÀÀ Zn* if n is composite. Hence if n is composite and a is chosen at random, the probability that a is in G is at most 1/2. We thus test as follows: function Solovay_Strassen(a,n) returns charstring; /* for n > 2, n odd, a À À Zn, decides probabilistically whether n is prime */ if (GCD(a,n) > 1) return("composite") else if ((a/n) = e(a,n)) return("prime") else return("composite"); end Solovay_Strassen;Ôobability of error is at most 2100. L.3 The Miller/Rabin test. Another Monte Carlo test was noted by Miller [MILL76] and Rabin [RABI80]. If n  1 = u * 2k where u is odd and k > 0, let exp(i) = 2i, 0 ÀÀ i ÀÀ k  1. If a ÀÀ Zn* then a is a witness to the compositeness of n if au !ÀÀ 1 (mod n) and au*exp(i) !ÀÀ 1 (mod n), 0 ÀÀ i ÀÀ k  1. Again, e.g., 100 witnesses may be tested; if noneÔ y mod n. Then a = Cd mod p, b = Cd mod q.Ôctability of which forms the basis for RSA. This was exploited by Rabin (cf. sec. 4.1.4) to obtain a modification of RSA which is provably equivalent to factoring. Essentially his scheme was to encrypt via EN(x) = x2 mod N. Let ZN* be as in appendix G. N.1 Characterizing quadratic residues. The basic extension of quadratic residuosity modulo a prime to the composite modulus case is: LEMMA N.1.1. If N = p * q, p and q primes > 2, then: a. Suppose z À À ZN*. Then z is a quadratic residue modulo N iff z mod p is a quadratic residue modulo p and z mod q is a quadratic residue modulo q. b. A quadratic residue z modulo N has exactly four square roots of the form {x,Nx,y,Ny} in ZN*. c. If z is a quadratic residue modulo N, and p and q are known, then the square roots of z modulo N can be found in probabilistic polynomial time. Proof: suppose z À À ZN*, z mod p is a quadratic residue modulo p, and z mod q is a quadratic residue modulo q. Then for some r and t in Zp* and Zq*, respectively, we have r2 ÀÀ z (mod p) and t2 ÀÀ z (mod q). By the Chinese Remainder Theorem (app. I) there exists w in ZN with w ÀÀ r (mod p) and w ÀÀ t (mod q). Then w2 ÀÀ z (mod p or q), so w2 ÀÀ z (mod N). Thus z is a quadratic residue modulo N. This proves one direction of (a). Now suppose z is a quadratic residue modulo N. Let zp = z mod p and zq = z mod q. Then z À À ZN*, and hence zp À À Zp* and zq À À Zq*. Also, w2 ÀÀ z (mod N) for some w in ZN*. Thus w2 ÀÀ z (mod p or q) and henceÔ1,2). The Chinese Remainder Theorem shows that w is uniquely determined in ZN by a given i and j; hence z has at most four square roots modulo N in ZN*. Conversely, by the Chinese Remainder Theorem once again, w can be found for each (i,j) pair. Thus z has exactly four square roots modulo N in ZN*. Let x denote one root. Then N  x is another. If y is a third, then N  y is the fourth. This proves (b). By lemma J.3.1, {xi} and {yj} can be found in probabilistic polynomial time; the corresponding w's can then be found in polynomial time. This proves (c). QED. COROLLARY N.1.1. Suppose N = p * q, p and q primes > 2. Then: a. EN is a fourtoone function. b. If p and q are known and z is a quadratic residue modulo N, the four values of x for which EN(x) = z can be found in probabilistic polynomial time. Proof: immediate from the previous lemma. QED. N.2 The Jacobi symbol once more. Suppose N = p * q where p and q are primes > 2. Then for x in ZN*, the Jacobi symbol (x/N) is given by (x/N) = (x/p)(x/q). If the Jacobi symbol (x/N) = 1, then (x/p) or (x/q) = 1. Hence x mod p and x mod q are quadratic nonresidues modulo p and q, respectively. By lemma N.1.1, x is a quadratic nonresidue modulo N. Since (x/N) can be evaluated in O(log N) time, (x/N) = 1 is a deterministic polynomialtime test for quadratic nonresiduosity of x modulo N, N = p * q. The interesting case is (x/N) = 1, whence no conclusion can be drawn regarding quadratic residuosity of x modulo N. To study this further, ZN* may be partitioned into four subclasses, according to the Jacobi symbols (x/p) and (x/q): ÔQ00(N) is the set of quadratic residues modulo N; the other Q's contain nonresidues. c. For i = 0 or 1 and j = 0 or 1, Qij(N) = (p1)(q1)/4. Proof: (a) is trivial, and (b) is immediate from lemma N.1.1. For (c), let g and h be generators for Zp* and Zq*, respectively. For w À À ZN*, suppose w ÀÀ gr (mod p) and w ÀÀ hs (mod q), where 0 ÀÀ r < p  1 and 0 ÀÀ s < q  1. Then r and s are unique. Conversely, any such pair (r,s) uniquely determines w, by the Chinese Remainder Theorem. Let f(w) = (r,s). Then f is a bijection from ZN* to Zp x Zq. Also, if f(w) = (r,s) then (w/p) = (gr/p) = (g/p)r, (w/q) = (hs/q) = (h/q)s. By lemma K.4, g and h are quadratic nonresidues modulo p and q, respectively. Thus (w/p) = (1)r and (w/q) = (1)s. Let i = r mod 2 and j = s mod 2. Then (w/p) = (1)i and (w/q) = (1)j. Hence w is in Qij(N). For k = 0,1 let Zpk and Zqk be the subsets of Zp* and Zq*, respectively, which contain elements = k (mod 2). Then for i = 0,1 and j = 0,1, f is a bijection from Qij(N) to Zpi x Zqj. The latter has cardinality (p1)(q1)/2; this gives (c). QED. Thus exactly half of the elements of ZN* have (x/N) = 1; these are nonresidues modulo N. The other half have (x/N) = 1. Of the latter, half (i.e., Q00(N)) are quadratic residues and half (i.e., Q11(N)) are nonresidues. The quadratic residuosity conjecture is that determining which of the elements of ZN* with (x/N) = 1 are quadratic residues modulo N is not solvable in probabilisticÔc residue and a nonresidue is a nonresidue. Proof: suppose x À À Qij(N) and y À À Qrt(N). Then (x/p) = (1)i, (x/q) = (1)j, (y/p) = (1)r, (y/q) = (1)t. Hence (x*y/p) = (1)i+r and (x*y/q) = (1)j+t. Now x * y mod N will be a residue if and only if i = r and j = t. This gives (a). In particular, x * y mod N is a residue if both are in Q00(N), yielding (b). If x is a residue and y a nonresidue, x is in Q00(N) but y is not; (c) follows. QED. Thus the quadratic residues modulo N form a subgroup of ZN*. N.3 Quadratic residuosity and factoring. We note the connection between quadratic residuosity and factoring observed by Rabin [RABI79]. LEMMA N.3.1. Suppose N = p * q, p and q prime, x and y are in ZN*, x2 ÀÀ y2 (mod N), and y !ÀÀ x or x (mod N). Then possession of x and y permits factoring N in deterministic polynomial time. Proof: we have x  y !ÀÀ 0 (mod N) and x + y !ÀÀ 0 (mod N), so GCD(N,y+x) < N and GCD(N,yx) < N. Now x2  y2 ÀÀ (xy)(x+y) ÀÀ 0 (mod N). Hence (xy)(x+y) ÀÀ 0 (mod p). Thus p  yx or p  y+x; also p  N. If p  yx, p  GCD(N,yx) < N, so p = GCD(N,yx). The latter can be found via Euclid's algorithm (app. H). If p  y+x, p  GCD(N,y+x) < N, so p = GCD(N,y+x). QED. LEMMA N.3.2. Suppose N = p * q, p and q prime. Suppose thereÔbility of factoring N is at least 1/4. If this procedure is repeated m times, the probability of success is at least 1  (3/4)m. Also, the problem size is log N, so m is a polynomial in the problem size. QED. COROLLARY N.3.2. If N = p * q, p and q prime, and the factorization of N is computationally intractable, then the Blum encryption function EN above is a trapdoor oneway function, with (p,q) forming the trapdoor. Proof: by the previous theorem, an algorithm to invert EN would yield an algorithm to factor N. QED. N.4 Quadratic residuosity and Blum integers. Suppose N = p * q where p ÀÀ 3 (mod 4) and q ÀÀ 3 (mod 4). Then N is called a Blum integer (normally p and q are specified to have roughly the same size). For example, N = 77 is used in appendix O. LEMMA N.4.1. If p,q ÀÀ 3 (mod 4) then (1/p) = (1/q) = 1. Proof: in lemma J.4.1 take a = 1. We recall that (1/p) = 1 if and only if 1 is a quadratic residue modulo p. Thus (1/p) = ( 1)(p1)/2 (mod p) and similarly (1/q) = (1)(q1)/2 (mod q). The result follows. QED. LEMMA N.4.2. If N = p * q is a Blum integer then (x/p) =  (x/p), (x/q) = (x/q), (1/N) = 1, and (x/N) = (x/N). Proof: the first two are immediate from the previous lemma; also (1/N) = (1/p)(1/q). QED. Ô, i = 0,1, j = 0,1. Proof: let {x,Nx,y,Ny} be the square roots of z in ZN*. Since Nx ÀÀ x (mod p), by lemma N.4.2, (Nx/p) = (x/p). Similarly (N x/q) = (x/q), so if x À À Qij(N), Nx À À Q1i,1j(N); similarly for y and Ny. Now x2 ÀÀ y2 (mod N) and y !ÀÀ x or x (mod N). Since by lemma N.4.3, (y/N) = (x/N), y cannot be in the same Q as x. By lemma N.4.2, ((Ny)/N) = (y/N), so Ny cannot be in the same Q as x. Thus y and Ny must be in Qi,1j(N) and Q1i,j(N) in some order. QED. For Blum integers we can restrict the function EN to Q00(N); i.e., let BN : Q00(N) > Q00(N) by BN(x) = x2 mod N. Then we have LEMMA N.4.5. If N = p * q is a Blum integer then: a. BN is a permutation on Q00(N), i.e., on the set of quadratic residues modulo N. b. If the factorization of N is computationally intractable then BN is a trapdoor oneway permutation, with (p,q) constituting the trapdoor. Proof: by corollary N.1.1 we know that if p and q are known and y is in Q00(N), the equation EN(x) = y has exactly four solutions which can be found in probabilistic polynomial time. By lemma N.4.4, exactly one of these, x00, lies in Q00(N); x00 is easily extracted from the set of four since only it satisfies (x/p) = (x/q) = 1. Hence x00 is the unique solution of BN(x) = y. Thus BN is a permutation on Q00(N) whose inverse may be computed in probabilistic polynomial time with knowledge of the trapdoor (p,q). On the other hand, lemma N.3.2 shows that an algorithm to invert BN can be converted to an algorithm to factor N. QED.Ômod p) in n tries is 2n. Hence a can be found in probabilistic polynomial time (in n = length of p). Now (a/p) = 1. Similarly, find b with (b/q) = 1, also in probabilistic polynomial time. Use the Chinese Remainder Theorem to find y in ZN* with y ÀÀ a (mod p) and y ÀÀ b (mod q), in polynomial time (in length of N). QED. Appendix O. An introduction to zeroknowledge. The notion of zeroknowledge proofs was introduced in [GOLD89]. The essence of zeroknowledge is that one party can prove something to another without revealing any additional information. In deference to the depth and scope of this area, we give only an illustrative example in this section. However, there is a close connection between zeroknowledge schemes and probabilistic public key encryption. Furthermore, some zeroknowledge schemes which have drawn attention because of applicability to smart card implementations, such as the one used as the basis of the example in this section, use Shamir's notion of identitybased publickey systems. Thus the reader desiring a more formal introduction to these topics may wish to skip to appendix P. Suppose that Alice knows a fact P. She wants to convince Bob that she knows P, but she does not trust Bob. Thus, Alice does not want to reveal any more knowledge to Bob than is necessary. What Alice needs is a zeroknowledge proof of P. For example, suppose that Alice wants to prove to Bob that she really is Alice. Suppose for convenience that there is some authority which verifies identities. One possibility is that the authority could issue Alice an identification. If this were contained on a device such as a smart card, Alice could simply show it to Bob. However, if Alice and Bob are communicating over a network, then Alice's identifying information would have to be transmitted to Bob over the network. Upon receiving it, Bob could use it to impersonate Alice. Even if Bob were trusted, an eavesdropper such as Alice's adversary Carol could do the same. This situation also arises commonly in computer access control: Bob might then be a host computer or network server, and Alice's identification might be a password. If Alice uses her password toÔays she is. He does this by checking that 362 * 580 * 671 ÀÀ 53 (mod 77), 622 * 581 * 670 ÀÀ 37 (mod 77), 472 * 581 * 671 ÀÀ 60 (mod 77). The original numbers {53,37,60} that Alice sent reappear. Actually, this doesn't really prove Alice's identity; she could have been an impersonator. But the chances of an impersonator succeeding would have only been 1 in 64. In an actual system, the number N would have been much larger (e.g., 160 digits). Also, Alice would have been assigned an ID consisting of more numbers, e.g., 4, by the authority, with a secret also consisting of 4 numbers. Furthermore, Alice would have generated more random numbers, e.g., 5, to send to Bob. The ID numbers, secret numbers, and random numbers would have been about as large as N. This would have reduced an impersonator's chances of cheating successfully to about 1 in a million (more precisely 220) if 4 and 5 are the parameters, which certainly would have convinced Bob of Alice's identity. Why does this work? Because the authority chose {58,67} and {9,10} so that 92 * 58 ÀÀ 1 (mod 77), 102 * 67 ÀÀ 1 (mod 77). This says that 92 and 58 are multiplicative inverses modulo 77, as are 102 and 67. Thus 362 * 580 * 671 ÀÀ 192 * 92*0 * 580 * 102*1 * 671 ÀÀ 192 * (92 * 58)0 * (102 * 67)1 ÀÀ 192 ÀÀ 36 (mod 77), 622 * 581 * 670 ÀÀ 242 * 92*1 * 581 * 102*0 * 670 ÀÀ 242 * (92 * 58)1 * (102 * 67)0 ÀÀ 242 ÀÀ 37 (mod 77), 472 * 581 * 671 ÀÀ 512 * 92*1 * 581 * 102*1 * 671Ô92 and 102 are the multiplicative inverses of 58 and 67, respectively, modulo 77. To see this, suppose Carol tries to convince Bob that she is really Alice; i.e., Carol pretends that {58,67} is her own ID. For simplicity, suppose Carol tries to identify herself as Alice by generating the same random {19,24,51}. Then she sends {53,37,60} to Bob. Again for simplicity suppose Bob generates the same E and sends it to Carol. Now Carol is in trouble; she doesn't know the numbers 9 and 10, and can only guess them. The protocol requires Carol to send three numbers, say {x,y,z}, to Bob. Then Bob will check: x2 * 580 * 671 ÀÀ 53 (mod 77), y2 * 581 * 670 ÀÀ 37 (mod 77), z2 * 581 * 671 ÀÀ 60 (mod 77). Carol will have succeeded in her masquerade if she chose {x,y,z} to make these checks come out right. But 671 ÀÀ 102 ÀÀ 23 (mod 77) and 581 ÀÀ 92 ÀÀ 4 (mod 77), so x2 ÀÀ 53 * 23 ÀÀ 64 (mod 77), y2 ÀÀ 37 * 4 ÀÀ 71 (mod 77) and z2 ÀÀ 60 * 23 * 4 ÀÀ 53 (mod 77). Could Carol solve these quadratic equations to find, e.g., x = 36, y = 62, z = 47? For a small value of N such as N = 77, she could indeed. However, if N is a product of two appropriatelychosen large primes (e.g., each 80 digits or more), and if these primes are kept secret by the authority, then the answer is no. That is, computing square roots modulo a composite is computationally infeasible (app. N). Thus, anyone who does not know Alice's secret ({9,10} in the above) cannot impersonate her when N is large. Another possibility is that Alice's interaction with Bob might give Bob information which could allow impersonation of Alice, at least on one occasion, by replay. Suppose Bob tries to convince Carol that he is really Alice. Bob might try to imitate Alice by sending (53,37,60} to Carol to start the protocol. Now Carol doesn't necessarily select the E above. Suppose she selects 1 1 F = 0 0 . 0 1 Ô trouble; he might try to imitate Alice again by sending {36,62,47} to Carol. Then Carol will check 362 * 581 * 671 ÀÀ 71 (mod 77). Since 71 ÀÀ 53 (mod 77), Carol knows Bob is a fraud even without the other two checks. Can Bob send some {r,s,t} instead of {36,62,47} ? This will only work if r2 * 581 * 671 ÀÀ 53 (mod 77), s2 * 580 * 670 ÀÀ 37 (mod 77), t2 * 580 * 671 ÀÀ 60 (mod 77). As before, this gives r2 ÀÀ 581 * 671 * 53 ÀÀ 25 (mod 77), and similarly s2 ÀÀ 37 (mod 77), t2 ÀÀ 71 (mod 77). As above, Bob can solve these quadratic equations to find r,s,t because N = 77 is small, but could not do so if N were large. Also, in the above there is one chance in 64 that Carol would choose F = E, in which case Bob's deception would go unmasked; but for larger parameters such as 4 and 5 instead of 2 and 3, this would again be improbable (one chance in a million (220) instead of 64). Another possibility is that when Alice identified himself to Bob, she may have inadvertently revealed some information which could enable Bob to learn his secret, i.e., {9,10}, which would permit impersonation. For this protocol to be zeroknowledge this should not be possible. Can Bob deduce the numbers {9,10} from the two sets of numbers {53,37,60} and {36,62,47}, and E? He knows that Alice started with three numbers {a,b,c}, but he doesn't know these were {19,24,51}. He knows that Alice's secret is {u,v} but doesn't know these are {9,10}. He knows that the authority computed u and v from u2 ÀÀ 581 ÀÀ 4 (mod 77), v2 ÀÀ 671 ÀÀ 23 (mod 77). He also knows that Alice computed a2 ÀÀ 53 (mod 77), b2 ÀÀ 37 (mod 77), c2 ÀÀ 60 (mod 77),Ôsolved when N is large. This shows informally that the above protocol works: a. It identifies Alice by proving that she possesses the secret {9,10}. b. It identifies Alice uniquely: anyone who doesn't know this secret cannot impersonate Alice. c. Alice's secret is not revealed in the process of proving she possesses it. Actually, (a) means that the possessor of {9,10} is identified as the system user who has ID = {58,67} assigned by the authority. Also, no matter how many times Alice proves her identity, her secret will not be revealed (if N is sufficiently large); i.e., (c) states loosely that the protocol is zeroknowledge. All of this depends on the assumption that equations of the form x2 ÀÀ y (mod N) cannot be solved if N is the product of two large primes which are not known, but can be solved easily if the primes are known (app. N). Such equations lie at the heart of most concrete zeroknowledge schemes. The formal definition of zeroknowledge is more complicated (see [GOLD89]), but the above example demonstrates its essence in a context which has been proposed as a candidate for actual implementation in smartcard based identification schemes. Appendix P. Alternatives to the Diffie/Hellman model. The text of this treatise has been based on the work of Diffie and Hellman [DIFF76b]. This model of publickey cryptography includes two characteristics which have received some criticism: a. Security of Diffie/Hellman type systems is generally established empirically, i.e., by failure of cryptanalysis. b. Security of Diffie/Hellman type systems is dependent uponÔome provable sense. For example, it is difficult to guarantee that partial information about plaintext (e.g., its least significant bit) cannot be recovered from the corresponding ciphertext even when the entire plaintext cannot be found. In section 5 we noted some examples of authentication frameworks (e.g., use of certificates) which bind user IDs and public keys. Without such a superstructure a publickey system is useless, since a user would not be certain that he was employing the correct public key for encryption or decryption. The security of the publickey system thus depends on proper functioning of the authentication framework, which is a priori unrelated to the underlying cryptosystem. In this section we briefly examine two modifications of the basic Diffie/Hellman model. In one case the goal is to incorporate the binding between a user ID and public key directly into the cryptosystem, thereby eliminating the separation between the cryptosystem and the authentication framework. The other scheme addresses the subject of knowledge concealment; it is closely related to zeroknowledge proofs. Both schemes have received considerable attention not only because of possibly enhanced security, but also because of their potential relevance to smart card implementations of publickey cryptography. P.1 Probabilistic encryption. Goldwasser and Micali [GOLD84] note that the publickey systems of Diffie and Hellman are not provably secure. They observe that use of a trapdoor function f to generate such systems does not exclude the possibility that f(x) = y may be solvable for x without the (original) trapdoor under certain conditions. Also, even if x cannot be found from f(x), it may be possible to extract partial information about x. One problem is that such trapdoor systems proceed block by block. This makes it difficult to prove security with respect to concealment of partial information such as least significant bit. In [GOLD84] Goldwasser and Micali suggest an alternative to trapdoorbased publickey systems. Their procedure is to encrypt bit by bit. They call this probabilistic encryption. It introduces several advantages, namely uniformly difficult decoding and hiding of partial information. Their scheme has the following properties: Ôe1,...,ek), which B sends to A. To decode e, A sets mi = 1 if ei is a quadratic residue modulo N, and mi = 0 otherwise. This can be effected by A in polynomial time since A knows p and q (lemmas J.4.1, N.1.1). It is correct because y * zi, the product of a quadratic nonresidue and residue, is a quadratic nonresidue modulo N (lemma N.2.2). The security of partial information follows from the fact that each bit of the message m is encoded independently. A disadvantage of the technique is data expansion: if N = n, then n bits are transmitted for each bit of a message. One application is coin flipping by telephone: A randomlyÔhich a ciphertext for a given plaintext is randomly chosen from a set of possible ciphertexts. Rivest and Sherman also develop a classification for such schemes. A major aspect of randomized schemes is often significant data expansion. For example, the Goldwasser/Micali scheme would probably have ciphertext around 512 times as large as the plaintext. On the other hand, probabilistic schemes may be much faster than their deterministic counterparts, an attractive feature for smartcard implementations. P.2 Identitybased schemes. In [SHAM84], Shamir suggests yet another modification of traditional publickey systems. In Shamir's framework a user's public key coincides with his system ID. This eliminates the need for any superstructure for distribution of public keys. It also trivializes the authentication of public keys. However, unlike a traditional publickey scheme this modification requires a trusted key generation center. The center issues a smart card to each user, containing the user's private key. Thus the "private" key is really a shared secret key. A card can generate the user's digital signature. The center does not maintain a database of keys; in fact it need not even keep information beyond a list of user IDs (needed to ensure that there are no duplicate IDs). Ô A weakness in such a scheme is that anyone (intruder or insider) possessing the trapdoor information can forge the signature of any user. This is in contradistinction, e.g., to a creditcard scheme in which a transaction is generally valid only if accompanied by a user's physical signature. Also, the center is not required to maintain any information on lost or stolen cards; thus the loss of a card is disastrous since the possessor can forge the legitimate user's signature indefinitely. Furthermore, the center may find itself involved in litigation produced by any such security problems, since it is providing the means by which users generate signatures. Again this in contrast to the creditcard situation: if a credit card is stolen, the thief cannot forge the legitimate holder's physical signature, providing a means of distinguishing between legal and illegal usage of the card. Use of passwords (PINs) with cards could largely eliminate the problems accruing from lost or stolen cards, but compromise of the trapdoor would still be disastrous. Shamir's notion was later ([FEIG87],[FIAT86]) incorporated into zeroknowledge schemes. One of these was used as the basis for the example in appendix O. REFERENCES [ADLE79] L. Adleman, "A subexponential algorithm for the discrete logarithm problem with applications to cryptography," in 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 2931, 1979, pp. 5560. Silver Spring, MD: IEEE Computer Society Press, 1979. [ADLE82] L. M. Adleman, "On breaking the iterated MerkleHellman publickey cryptosystems," in D. Chaum, R. L. Rivest, and A. T. Sherman, Eds., Advances in Cryptology: proceedings of CRYPTO 82, a Workshop on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, August 2325, 1982, pp. 303308. New York: Plenum Press, 1983. [ADLE86] L. M. Adleman and K. S. McCurley, "Open problems in number theoretic complexity," in D. S. Johnson, T. Nishizeki, A. Nozaki, and H. S. Wilf, Eds., Discrete Algorithms and Complexity,Ôhaum, Eds., Lecture Notes in Computer Science Vol. 196: Advances in Cryptology: Proceedings of CRYPTO 84, a Workshop on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, August 1922, 1984, pp. 7382. Berlin/New York: SpringerVerlag, 1985. [BLAK83] G. R. Blakley, "A computer algorithm for calculating the product AB modulo M," IEEE Transactions on Computers, Vol. C32, No. 5, May 1983, pp. 497500. [BLUM84] M. Blum and S. Micali, "How to generate cryptographicallyÔrickell, "A fast modular multiplication algorithm with application to two key cryptography," in D. Chaum, R. L. rivest, and A. T. Sherman, Eds., Advances in Cryptology: proceedings of CRYPTO '82, a Workshop on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, August 2325, 1982, pp. 5160. New York: Plenum Press, 1983. [BRIC83] E. F. Brickell, "Solving low density knapsacks," in D. Chaum, Ed., Advances in Cryptology: proceedings of CRYPTO 83, a Workshop on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, August 2224, 1983, pp. 2537. New York: Plenum Press, 1984. [BRIC84] E. F. Brickell, "Breaking iterated knapsacks," in G. R. Blakley and D. Chaum, Eds., Lecture Notes in Computer Science Vol. 196: Advances in Cryptology: Proceedings of CRYPTO 84, a Workshop on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, August 1922, 1984, pp. 342358. Berlin/New York: SpringerVerlag, 1985.Ô987, pp. 103121. [COHE84] H. Cohen and H. W. Lenstra, Jr., "Primality testing and Jacobi sums," Mathematics of Computation, Vol. 42, No. 165, January 1984, pp. 297330. [CONT80] Control Data Corporation, CDC CYBER 200 Model 205 Computer System. Minneapolis, MN, 1980. [COPP84] D. Coppersmith, "Fast evaluation of logarithms in fields of characteristic two," IEEE Transactions on Information Theory, Vol. IT30, No. 4, July 1984, pp. 587594. [COPP85] D. Coppersmith, "Another birthday attack," in H. C. Williams, Ed., Lecture Notes in Computer Science Vol. 218: Advances in Cryptology  CRYPTO '85, proceedings of a Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, CA, August 1822, 1985, pp. 1417. Berlin/New York: Springer Verlag, 1986. [COPP87] D. Coppersmith, "Cryptography," IBM Journal of Research and Development, Vol. 31, No. 2, March 1987, pp. 244248. [COPP86] D. Coppersmith, A. M. Odlyzko, and R. Schroeppel, "Discrete logarithms in GF(p)," Algorithmica, Vol. 1, No. 1, 1986, pp. 115. [CRAY80] Cray Research, Inc., Cray 1S Series Hardware Reference Manual. Mendota Heights, MN, June 1980. [CRAY85] Cray Research, Inc., Cray XMP Series of Computer Systems.Ôeth, N. Cot, and I. Ingemarsson, Eds., Lecture Notes in Computer Science Vol. 209: Advances in Cryptology: Proceedings of EUROCRYPT 84, a Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 9 11, 1984, pp. 183215. Berlin/New York: SpringerVerlag, 1985. [DEMI83] R. DeMillo and M. Merritt, "Protocols for data security," Computer, Vol. 16, No. 2, February 1983, pp. 3951. [DENN79] D. E. Denning, "Secure personal computing in an insecure network," Communications of the ACM, Vol. 22, No. 8, August 1979, pp. 476482. [DENN83b] D. E. Denning, "Protecting public keys and signature keys," Computer, Vol. 16, No. 2, February 1983, pp. 2735. [DENN81] D. E. Denning and G. M. Sacco, "Timestamps in key distribution protocols," Communications of the ACM, Vol. 24, No. 8, August 1981, pp. 533536. [DENN83] D. E. R. Denning, Cryptography and Data Security. Reading, MA: AddisonWesley, 1983. [DESM83] Y. Desmedt, J. Vandewalle, and R. J. M. Govaerts, "A critical analysis of the security of knapsack public key algorithms," IEEE Transactions on Information Theory, Vol. IT30, No. 4, July 1984, pp. 601611. [DIFF82] W. Diffie, "Conventional versus public key cryptosystems," in G. J. Simmons, Ed., Secure Communications and Asymmetric Cryptosystems, pp. 4172. Boulder, CO: Westview Press, 1982. [DIFF84] W. Diffie, "Network security problems and approaches," Proceedings of the National Electronics Conference, Vol. 38, 1984, pp. 292314. Ôontvale, NJ: AFIPS Press, 1976. [DIFF76b] W. Diffie and M. E. Hellman, "New directions in cryptography," IEEE Transactions on Information Theory, Vol. IT22, No. 6, November 1976, pp. 644654. [DIFF79] W. Diffie and M. E. Hellman, "Privacy and authentication: an introduction to cryptography," Proceedings of the IEEE, Vol. 67, No. 3, March 1979, pp. 397427. [DIFF87] W. Diffie, B. O'Higgins, L. Strawczynski, and D. Steer, "An ISDN secure telephone unit," Proceedings of the National Communications Forum, Vol. 41, No. 1, 1987, pp. 473477. [DIXO81] J. D. Dixon, "Asymptotically fast factorization of integers," Mathematics of Computation, Vol. 36, No. 153, January 1981, pp. 255260. [DOLE81] D. Dolev and A. C. Yao, "On the security of public key protocols," in 22nd Annual Symposium on Foundations of Computer Science, Nashville, TN, October 2830, 1981, pp. 350357. Silver Spring, MD: IEEE Computer Society Press, 1981. [DUSS90] S. R. Dusse and B. S. Kaliski, Jr., "A cryptographic library for the Motorola DSP 56000," presented at EUROCRYPT '90, Aarhuis, DEnmark, May 2124, 1990. [EHRS78] W. F. Ehrsam, S. M. Matyas, C. H. Meyer, and W. L. Tuchman, "A cryptographic key management scheme for implementing the Data Encryption Standard," IBM Systems Journal, Vol. 17, No. 2, 1978, pp. 106125. [ELGA85] T. ElGamal, "A public key cryptosystem and a signature scheme based on discrete logarithms," IEEE Transactions on Information Theory, Vol. IT31, No. 4, July 1985, pp. 469472. [ELGA85b] T. ElGamal, "On computing logarithms over finite fields," in H. C. Williams, Ed., Lecture Notes in Computer Science Vol. 218: Advances in Cryptology  CRYPTO '85, proceedings of a Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, CA, August 1822, 1985, pp. 396402. Berlin/New York: SpringerVerlag, 1986.Ôugust 1974, pp. 437442. [FEIG87] U. Feige, A. Fiat, and A. Shamir, "Zero knowledge proofs of identity," in Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, New York, NY, May 2527, 1987, pp. 210 217. New York: ACM, 1987. [FIAT86] A. Fiat and A. Shamir, "How to prove yourself: practical solutions to identification and signature problems," in A. M. Odlyzko, Ed., Lecture Notes in Computer Science Vol. 263: Advances in Cryptology  CRYPTO '86, proceedings of a Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, CA, August 1115, 1986, pp. 186194. Berlin/New York: Springer Verlag, 1987. [FLYN78] R. Flynn and A. S. Campasano, "Data dependent keys for a selective encryption terminal," in S. P. Ghosh and L. Y. Liu, Eds., AFIPS Conference Proceedings Vol. 47: National Computer Conference, Anaheim, CA, June 58, 1978, pp. 11271129. Montvale, NJ: AFIPS Press, 1978. [GARE79] M. R. Garey and D. S. Johnson, Computers and Intractability. New York: W. H. Freeman, 1979. [GILL77] J. Gill, "Computational complexity of probabilistic Turing machines," SIAM Journal on Computing, Vol. 6, No. 4, December 1977, pp. 675695. [GOLD84] S. Goldwasser and S. Micali, "Probabilistic encryption," Journal of Computer and System Sciences, Vol. 28, No. 2, April 1984, pp. 270299. [GOLD89] S. Goldwasser, S. Micali, and C. Rackoff, "The knowledge complexity of interactive proof systems," SIAM Journal on Computing, Vol. 18, No. 1, February 1989, pp. 186208. [GOLD88] S. Goldwasser, S. Micali, and R. L. Rivest, "A digital signature scheme secure against adaptive chosenmessage attacks," SIAM Journal on Computing, Vol. 17, No. 2, April 1988, pp. 281308. [GORD84b] J. Gordon, "Strong RSA keys," Electronics Letters, Vol. 20, No. 12, June 7, 1984, pp. 514516. [GORD84] J. A. Gordon, "Strong primes are easy to find," in T. Beth, N. Cot, and I. Ingemarsson, Eds., Lecture Notes in Computer Science Vol. 209: Advances in Cryptology: Proceedings of EUROCRYPT 84, a Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 911, 1984, pp. 216223. Berlin/New York: SpringerVerlag, 1985. [GROL88] J. Grollman and A. L. Selman, "Complexity measures forÔ Architecture, 1987. [JUEN82] R. R. Jueneman, "Analysis of certain aspects of output feedback mode," in D. Chaum, R. L. Rivest, and A. T. Sherman, Eds., Advances in Cryptology  proceedings of CRYPTO 82, a Workshop on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, August 2325, 1982, pp. 99127. New York: PlenumÔys (for VLSI)," in I. S. Duff and G. W. Stewart, Eds., Sparse Matrix Proceedings, pp. 245282. Philadelphia: SIAM, 1978. [KUNG82b] S. Y. Kung, K. S. Arun, R. J. GalEzer, and D. V. B. Rao, "Wavefront array processor: language, architecture, and applications," IEEE Transactions on Computers, Vol. C31, No. 11, November 1982, pp. 10541066. [LAGA84] J. C. Lagarias, "Performance analysis of Shamir's attack on the basic MerkleHellman knapsack system," in J. Paredaens, Ed., Lecture Notes in Computer Science Vol. 172: Automata, Languages and Programming: 11th Colloquium, Antwerp, Belgium, July 1620, 1984, pp. 312323. Berlin/New York: SpringerVerlag, 1984.Ôasse, "Factoring by electronic mail," to appear in proceedings of EUROCRYPT '89. [LENS83] H. W. Lenstra, Jr., "Integer programming with a fixed number of variables," Mathematics of Operations Research, Vol. 8, No. 4, November 1983, pp. 538548. [LENS86] H. W. Lenstra, Jr., "Primality testing," in J. W. de Bakker et al., Eds., Mathematics and Computer Science, CWI Monographs, I, pp. 269287. Amsterdam/New York: NorthHolland, 1986. [LENS87] H. W. Lenstra, Jr., "Factoring integers with elliptic curves," Annals of Mathematics, Vol. 126, 1987, pp. 649673. [LEWI81] H. R. Lewis and C. H. Papadimitriou, Elements of the Theory of Computation. Englewood Cliffs, NJ: PrenticeHall, 1981. [LINN89] J. Linn and S. T. Kent, "Privacy for DARPAInternet mail," in Proceedings of the 12th National Computer Security Conference, Baltimore, MD, October 1013, 1989, pp. 215229. Ôtions and DES," preprint. [MERK78b] R. C. Merkle and M. E. Hellman, "Hiding information and signatures in trapdoor knapsacks," IEEE Transactions on Information Theory, Vol. 24, No. 5, September 1978, pp. 525530. [MILL76] G. L. Miller, "Riemann's hypothesis and tests for primality," Journal of Computer and System Sciences, Vol. 13, No. 3, December 1976, pp. 300317. [MILU88] V. M. Milutinovic, Computer Architecture: Concepts and Systems. New York: NorthHolland, 1988. [MONT85] P. L. Montgomery, "Modular multiplication without trial division," Mathematics of Computation, Vol. 44, No. 170, April 1985, pp. 519521. [MOOR88] J. H. Moore, "Protocol failures in cryptosystems," Proceedings of the IEEE, Vol. 76, No. 5, May 1988, pp. 594602. [MORR75] M. A. Morrison and J. Brillhart, "A method of factoring and the factorization of F7," Mathematics of Computation, Vol. 29, No. 129, January 1975, pp. 183205. [NATI77] National Bureau of Standards, Federal InformationÔings of EUROCRYPT 84, a Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, April 911, 1984, pp. 224314. Berlin/New York: Springer Verlag, 1985. [ORTO86] G. A. Orton, M. P. Roy, P. A. Scott, L. E. Peppard, and S. E. Tavares, "VLSI implementation of publickey encryption algorithms," in A. M. Odlyzko, Ed., Lecture Notes in Computer Science Vol. 263: Advances in Cryptology  CRYPTO '86, proceedings of a Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, CA, August 1115, 1986, pp. 277301. Berlin/New York: SpringerVerlag, 1987. [PATT87] W. Patterson, Mathematical Cryptology for Computer Scientists and Mathematicians. Totowa, NJ: Rowman & Littlefield, 1987. [PERA86] R. C. Peralta, "A simple and fast probabilistic algorithm for computing square roots modulo a prime number," IEEE Transactions on Information Theory, Vol. 32, No. 6, November 1986, pp. 846847. [POHL78] S. C. Pohlig and M. E. Hellman, "An improved algorithm for computing logarithms over GF(p) and its cryptographic significance," IEEE Transactions on Information Theory, Vol. IT24, No. 1, January 1978, pp. 106110. [POME84] C. Pomerance, "The quadratic sieve factoring algorithm," in T. Beth, N. Cot, and I. Ingemarsson, Eds., Lecture Notes in Computer Science Vol. 209: Advances in Cryptology: proceedings of EUROCRYPT 84, a Workshop on the Theory and Application ofÔg, Vol. 17, No. 2, April 1988, pp. 387403. [POPE78] G. J. Popek and C. S. Kline, "Encryption protocols, public key algorithms and digital signatures in computer networks," in R. A. DeMillo, D. P. Dobkin, A. K. Jones, and R. J. Lipton, Eds., Foundations of Secure Computation, pp. 133153. New York: Academic Press, 1978. [POPE79] G. L. Popek and C. S. Kline, "Encryption and secure computer networks," ACM Computing Surveys, Vol. 11, No. 4, December 1979, pp. 331356. [QUIN87] M. J. Quinn, Designing Efficient Algorithms for Parallel Computers. New York: McGrawHill, 1987. [QUIS82] J.J. Quisquater and C. Couvreur, "Fast decipherment algorithm for RSA publickey cryptosystem," Electronics Letters, Vol. 18, No. 21, October 14, 1982, pp. 905907. [RABI76] M. O. Rabin, "Probabilistic algorithms," in J. F. Traub, Ed., Algorithms and Complexity: New Directions and Recent Results, proceedings of a Symposium, Pittsburgh, PA, April 79, 1976, pp. 2139. New York: Academic Press, 1976. [RABI78] M. O. Rabin, "Digitalized signatures," in R. A. DeMillo, D. P. Dobkin, A. K. Jones, and R. J. Lipton, Eds., Foundations of Secure Computation, pp. 155168. New York: Academic Press, 1978. [RABI79] M. O. Rabin, "Digitalized signatures and publickey functions as intractable as factorization," MIT Laboratory for Computer Science, Technical Report LCS/TR212, January 1979. [RABI80] M. O. Rabin, "Probabilistic algorithms for testing primality," Journal of Number Theory, Vol. 12, 1980, pp. 128138. [RADE64] H. Rademacher, Lectures on Elementary Number Theory. New York: Blaisdell, 1964. [RIVE84] R. L. Rivest, "RSA chips (past/present/future)," in T. Beth, N. Cot, and I. Ingemarsson, Eds., Lecture Notes in Computer Science Vol. 209: Advances in Cryptology: proceedings of EUROCRYPT 84, a Workshop on the Theory and Application of CryptographicÔm," February 1990. [RIVE78] R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and publickey cryptosystems," Communications of the ACM, Vol. 21, No. 2, February 1978, pp. 120127. [RIVE82] R. L. Rivest and A. T. Sherman, "Randomized encryption techniques," in D. Chaum, R. L. Rivest, and A. T. Sherman, Eds., Advances in Cryptology: Proceedings of CRYPTO 82, a Workshop on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, August 2325, 1982, pp. 145163. New York: Plenum Press, 1983. [SIAM90] "Number field sieve produces factoring breakthrough," SIAM News, Vol. 23, No. 4, July 1990. [SALO85] Salomaa, "Cryptography," in A. Salomaa, Encyclopedia of Mathematics and its Applications Vol. 25: Computation and Automata, pp. 186230. Cambridge, UK: Cambridge University Press, 1985. [SCHA82] B. P. Schanning, "Applying public key distribution to local area networks," Computers & Security, Vol. 1, No. 3, November 1982, pp. 268274. [SCHA80] B. P. Schanning, S. A. Powers, and J. Kowalchuk, "MEMO: privacy and authentication for the automated office," in proceedings of the 5th Conference on Local Computer Networks, Minneapolis, MN, October 67, 1980, pp. 2130. Silver Spring, MD: IEEE Computer Society Press, 1980. [SCHN84] C. P. Schnorr and H. W. Lenstra, Jr., "A Monte Carlo factoring algorithm with linear storage," Mathematics of Computation, Vol. 43, No. 167, July 1984, pp. 289311. [SEDL87] H. Sedlak, "The RSA Cryptography Processor," in D. Chaum and W. L. Price, Eds., Lecture Notes in Computer Science Vol. 304: Advances in Cryptology  EUROCRYPT '87, a Workshop on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 1315, 1987, pp. 95105. Berlin/New York: SpringerVerlag, 1988. [SEIT85] C. L. Seitz, "The Cosmic Cube," Communications of the ACM, Vol. 28, No. 1, January 1985, pp. 2233. [SHAM79] A. Shamir, "On the cryptocomplexity of knapsack systems," in proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, Atlanta, GA, April 30  May 2, 1979, pp. 118129. New York: ACM, 1979. [SHAM84b] A. Shamir, "Identitybased cryptosystems and signatureÔ Society Press, 1986. [TANE81] A. S. Tanenbaum, Computer Networks. Englewood Cliffs, NJ: PrenticeHall, 1981. [WAGN84] N. R. Wagner and M. R. Magyarik, "A publickey cryptosystem based on the word problem," in G. R. Blakley and D. Chaum, Eds., Lecture Notes in Computer Science Vol. 196: Advances in Cryptology  Proceedings of CRYPTO 84, a Workshop on the Theory and Applications of Cryptographic Techniques, Santa Barbara, CA, August 1922, 1984, pp. 1936. Berlin/New York: SpringerVerlag, 1985. Brought to you
