Public key cryptographic mechanism5204901Abstract A public key cryptographic mechanism provides a measurable degree of minimum security, in an ensemble sense, for two Parties, A and B, to establish a commonly held private cryptographic keying variable between them for establishing communications. Both parties randomly generate m-bit vectors vec.sub.-- A and vec.sub.-- B, store the vectors, then copy the vectors and add m-bit vectors containing n ones. The vectors thus modified are exchanged between the parties. Both parties then respectively bit-by-bit combine, by Exclusive-Or logic, their stored m-bit vectors vec.sub.-- A and vec.sub.-- B with a received vector, denoted rec.sub.-- B and rec.sub.-- A, to generate respective vectors W.sub.-- A and W.sub.-- B. Parties A and B then generate all ##EQU1## vectors at a Hamming distance n from W.sub.-- A and W.sub.-- B respectively. These ##EQU2## vectors are each bit-by-bit added, using Exclusive-Or logic, with their encryptions under a publicly known keying variable K.sub.1, forming image vectors. Both parties exchange their image vectors in random order. Both parties then determine the matches between the image vectors they have sent and received, allowing them to determine a commonly held m-bit vector X. Vector X is then used to derive a keying variable for a single key encryption algorithm by encrypting it under the DES ECB/ENCRYPT mode keyed by a publicly known keying variable K.sub.2. Claims Having thus described our invention, what we claim as new and desire to secure by Letters Patent is as follows: Description BACKGROUND OF THE INVENTION
______________________________________
PARTY A PARTY B
______________________________________
Picks a secret number X
Picks a secret number Y
Calculates r.sup.y mod p and sends it
Calculates r.sup.Y mod p and sends
to Party B it to Party A
Receives r.sup.x mod p and raises it
Receives r.sup.x mod p and raises
to the X power reducing result
it to the Y power reducing
mod p mod p
______________________________________
In the Diffie-Hellman system, p, a large prime number, is publicly known as well as r, a primitive root of p. After performing the steps outlined above, both Parties, A and B, possess r.sup.XY mod p (without either party knowing, or needing to know, the other's secret number). A passive interloper, i.e., a party monitoring only the exchanges between Parties A and B, could calculate r.sup.XY mod p if able to solve for either X or Y. The cryptosecurity strength of the Diffie-Hellman system is thus no stronger than the apparently significant asymmetric complexity between performing exponentiation (which is relatively easy) and solving the discrete logarithm problem (which is relatively hard) in various finite fields. Exponentiation requires O(log.sub.2 p) work. R. Merkle and L. Adleman have independently devised an algorithm that will compute discrete logarithms with work o(e.sqroot.k(lnp)(ln(lnp))) Thus, the ratio of work required to take logarithms to the work to exponentiate is extremely large providing that the Merkle/Adleman procedure is nearly optimal. See, for example, R. Merkle, Secrecy, Authentication, and Public Key Systems, Ph.D. dissertation, Department of Electrical Engineering, Stanford University (Jun., 1979), and L. Adleman, "A Subexponential Algorithm for the Discrete Logarithm with Applications to Cryptography", Proceedings of the 20th Annual Symposium on foundations of Computer Science (Oct. 29-31, 1979), both of which are incorporated herein by reference. To promote confidence in the discrete logarithm problem, p should be very large, perhaps hundreds of digits long. Execution of this particular public key system, and most public key systems, entails a large computational overhead. In addition, the minimum cost of performing the discrete logarithm problem is not known nor is it known that there is no attack better than by attempting to take the discrete logarithm. In the patented literature, the following U.S. patents are considered relevant prior art. U.S. Pat. No. 4,200,770 to Hellman et al. discloses a cryptographic apparatus and method. U.S. Pat. No. 4,218,582 to Hellman et al. discloses a public key cryptographic apparatus and method. U.S. Pat. No. 4,424,414 to Hellman et al. discloses an exponentiation cryptographic apparatus and method. U.S. Pat. No. 4,405,829 to Rivest et al. discloses a cryptographic communications system and method. The Rivest et al. patent discloses the so-called RSA (for Rivest, Shamir and Adleman, the inventors) algorithm, a well-known public-key algorithm. A discussion of the RSA and other public-key algorithms may be had by reference to C. Meyer and S. Matyas, Cryptography: A New Dimension in Computer Data Security, Wiley (1982). See also J. Hershey and R. Yarlagadda, Data Transportation and Protection, Plenum Press (1986). SUMMARY OF THE INVENTION It is therefore an object of the present invention to provide a public key cryptographic mechanism that will enable, in a practical way, communicating parties to quickly establish a mutually held keying variable through expending S units of work, on the average, but will require an interloper, on the average, to expend on the order of S.sup.2 such work units in order to determine the keying variable. This asymmetry in work can be translated to a time delay between the mutual establishment of the keying variable between the communicating parties and the interloper learning the keying variable. This delay may be required to be only on the order of a few seconds for some particular communications systems served by the public key encryption mechanism. The present invention also requires that the communicating parties have a large communications bandwidth between them. It is an another object of this invention to provide a system that can be used for privacy only, that is, a system which provides security for time sensitive material only, such as to be found in certain tactical communications scenarios. The invention contemplates a public key cryptographic system that is capable of providing a measurable degree of minimum security in an ensemble sense. The system enables two Parties, A and B, to establish a commonly held private cryptographic keying variable between them by first establishing publicly disclosed or known keying variables K.sub.1 and K.sub.2 for use by both parties. Both parties then randomly generate m-bit vectors, denoted vec.sub.-- A and vec.sub.-- B. In the preferred embodiment, m is 64. The generated vectors vec.sub.-- A and vec.sub.-- B are stored for later use. The parties then copy their vectors and randomly select and invert n bits of the copied vectors before exchanging them. In the preferred embodiment, n is 3. Each of the parties then respectively, bit-by-bit, employs Exclusive-Or logic to combine its stored m-bit vectors vec.sub.-- A and vec.sub.-- B with the vectors, denoted rec.sub.-- B and rec.sub.-- A, received from the other party, to generate respective vectors W.sub.-- A and W.sub.-- B. By consequence of the above steps, Party A's W.sub.-- A and Party B's W.sub.-- B vectors will both agree within three bits of X, which is vec.sub.-- A combined bit-by-bit with vec.sub.-- B through use of Exclusive-Or logic. Parties A and B then generate all ##EQU3## 64-bit vectors that are within three bits of vectors W.sub.-- A and W.sub.-- B, respectively. Each respective one of these 41,664 vectors is converted to an "image" vector by inputting it to a DES in electronic codebook (or ECB/ENCRYPT) mode keyed with publicly known keying variable K.sub.1 and combining the encrypted vector bit-by-bit with its unencrypted form using Exclusive-Or logic. (The electronic codebook is defined in Federal Information Processing Standards Publication number 81.) Both parties save the image vectors in a file which cross-references the image vectors to the specific three-bit pattern which was added to vector W.sub.-- A or W.sub.-- B. The parties then exchange all ##EQU4## of these image vectors. The parties transmit the image vectors in a random order. Upon receipt of the set of image vectors from Party B, Party A proceeds to search the set for the vectors that precisely match image vectors sent by Party A. Party B does likewise. To minimize the information that can be gleaned by an observer/interloper, and to make the system synchronous, both parties will exhaustively search the entire received set of image vectors. If the parties both find only two image vectors that match, they proceed; otherwise the process is mutually aborted and retried. It is mathematically clear that Party A can now discern the specific bits that Party B inverted in changing B to rec.sub.-- B and Party B can likewise determine the three bits that Party A inverted in changing vec.sub.-- A to rec.sub.-- A. Thus both parties can form X which is the bit-by-bit Exclusive-Or sum of vec.sub.-- A and vec.sub.-- B. BRIEF DESCRIPTION OF THE DRAWINGS The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which: FIG. 1 is a block diagram illustrating the process of generating the random sequences, denoted as vec.sub.-- A and vec.sub.-- B, storing these vectors for later use, corruption of the vectors by the bit-by-bit addition (selective inversion) of noise sequences, and exchanging of the corrupted vectors by Parties A and B. FIG. 2 is a block diagram depicting the process performed by Party A in forming all ##EQU5## image vectors and sending that set of image vectors to Party B. (Party B does the same thing.) FIG. 2A is a simplified block diagram of the process of forming the image vectors of FIG. 2. FIG. 3 is a block diagram illustrating the preferred embodiment for producing all ##EQU6## 64-bit vectors having exactly three ones. FIG. 4 is a block diagram showing the preferred generation of 56 random bits from the vector X using a publicly known key K.sub.2. FIG. 5 is a block diagram illustrating random selection of a vector having exactly three ones by Parties A and B. FIG. 6 is a graphical illustration of the thresholder shown in FIG. 5. FIG. 7 is a block diagram of a system for performing the process of the invention. DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT OF THE INVENTION FIG. 1 shows, in block diagram form, the initial processes which take place between and within Parties A and B. Using a random or pseudorandom bit generator, Party A generates a 64-bit random bit vector as depicted in step 10 and stores this vector as vec.sub.-- A as indicated at step 11. Next, Party A copies the stored vector vec.sub.-- A out of storage as indicated at step 12, and corrupts the copy of the vector by randomly selecting and inverting three bits as indicated at step 13. This corrupted vector is then sent to Party B, as indicated at step 14. Similarly, Party B uses a random or pseudorandom bit generator to generate a 64-bit random bit vector, as depicted in step 15, and stores this vector as vec.sub.-- B as indicated at step 16. Party B then copies the stored vector vec B out of storage, as indicated at step 17, and corrupts the copy of this vector by randomly selecting and inverting three bits as indicated at step 18. This corrupted vector is then sent to Party A, as indicated at step 19. In both cases, the random selection of the bits to be inverted can be accomplished with a suitable random or pseudorandom bit generator that provides an essentially equiprobable selection from all possibilities. Both parties receive the respective 64-bit corrupted versions of vectors vec.sub.-- A and vec.sub.-- B, which are respectively denoted as vectors rec.sub.-- A and rec.sub.-- B. FIG. 2 depicts this process for Party A. As both Parties are executing the same process, the process will be detailed for Party A only. The receipt of vector rec.sub.-- B is indicated at step 21. Party A then employs Exclusive-Or logic to combine vector rec.sub.-- B bit-by-bit with its stored (uncorrupted) vector vec.sub.-- A to form a 64-bit vector W.sub.-- A. This is indicated at step 22. Party A then forms all 64-bit vectors that are within three bits of vector W.sub.-- A. Those skilled in the profession might say that Party A forms all 64-bit vectors that are within Hamming distance three of W.sub.-- A. This is indicated at step 23. Parties A and B can accomplish the production of all 64-bit vectors that are a Hamming distance three vector from W.sub.-- A in a number of ways. One way is to simply successively add, by bit-by-bit Exclusive-Or, all 64-bit vectors that have exactly three ones (or "Hamming weight" 3) to vector W.sub.-- A. Algorithms that are capable of producing all m-bit vectors having a given number of ones are available. See, for example, "Efficient Generation of the Binary, Reflected Gray Code and its Applications" by J. Bitner, G. Ehrlich and E. Reingold published in Communications of the ACM, Vol. 19, pp. 517-521 (1976), which is herein incorporated by reference. Another way, and the preferred embodiment as shown in FIG. 3, is to build a parallel, recirculating memory 31 of all 64-bit vectors that have exactly three ones in order to implement step 23 of FIG. 2. Party A then inputs all of the vectors formed at step 23 of FIG. 2 into a DES operated in the ECB/ENCRYPT mode keyed with the publicly disclosed (known) keying variable K.sub.1. Each output vector is bit-by-bit combined with its unencrypted form, using Exclusive-Or logic, to form an "image vector" as indicated at step 24. All of the image vectors are sent in random order to Party B as indicated at step 25. Both parties retain the correspondence between each image vector and the particular 64-bit, Hamming weight 3 vector, used in producing it. A simplified block diagram corresponding to this process is shown in FIG. 2A. Both parties then search the image vectors received from each other. One of two outcomes is guaranteed: (1) Exactly vectors will match or (2) many vectors will match. The probability of the first outcome is slightly greater than 78%. It is this outcome that is favorable. If outcome (2) obtains, both parties automatically reset, through a higher level communications protocol, and repeat the entire procedure until outcome (1) obtains. When outcome (1) obtains, both parties know what the secret 64-bit vector, denoted by X, between them should be. From their retained correspondence between each image vector and the particular Hamming weight 3 vector used to produce it, both parties are able to produce the two Hamming weight 3 vectors that are associated with the two image vectors that match. For each party, one of these vectors will be the 64-bit, Hamming weight 3 vector that they used in corrupting their particular vector, vec.sub.-- A or vec.sub.-- B, to produce vector rec.sub.-- A or rec.sub.-- B, respectively. The other vector will be the 64-bit, Hamming weight 3 vector that the other party used in corrupting its particular vector, vec.sub.-- B or vec.sub.-- A, to produce vector rec.sub.-- B or rec.sub.-- A, respectively. From this knowledge, both parties create vector X, which is the bit-by-bit Exclusive-Or sum of vectors vec.sub.-- A and vec.sub.-- B. Once the Parties have determined vector X, they derive a common keying variable for a "classical" one key cryptosystem, such as the DES, as opposed to a two key public key cryptosystem. The DES requires a 64-bit keying variable. Eight of these keying-variable bits are odd parity check sum bits on 56 random bits. The preferred embodiment for generating the 56 random bits is to use the ECB/ENCRYPT mode of the DES with a publicly known keying variable K.sub.2 to encrypt vector X and use a c-bit subset, where c comprises the first 56 bits of the 64-bit cipher result, as indicated in the simplified block diagram of FIG. 4. Regarding the selection of the bits to be inverted (described with reference to FIG. 1), as shown in FIG. 5 for Party A (Party B mirrors the function), Party A may use its recirculating memory 53 of FIG. 5 (identical to memory 31 of FIG. 3), with other componentry to randomly select the three bits of vector vec.sub.-- A to be inverted. The memory is circulated and stopped at a random spot. The particular 64-bit vector having exactly three ones is thus randomly selected for bit-by-bit combination with vector vec.sub.-- A by use of Exclusive-Or logic. The random stopping can be accomplished in any one of a variety of ways. In a preferred embodiment of the invention, a thresholder 52 monitors a randomly produced zero mean noise signal, such as that produced by a capacitive coupling 54 to a back-biased diode 51. When a suitably chosen threshold is exceeded, the memory circulation is ceased and the randomly picked 64-bit vector having exactly three ones is read out. This process is illustrated graphically in FIG. 6, with readout of the randomly picked 64-bit vector having exactly three ones occurring at the same instant t.sub.A when the random zero mean noise signal 55 produced by random noise source 51 of FIG. 5 exceeds a predetermined threshold. A suitably chosen threshold is one for which the probability distribution of the chosen vectors is approximately uniform. FIG. 7 is a block diagram of a system which performs the process of the invention. A 64-bit random bit vector generator 60 is employed at the location of Party A, while another 64-bit random bit vector generator 61 is situated at the Party B location. Vectors generated by random bit generators 60 and 61, respectively, are stored in storage means 62 and 63, respectively, at the Party A and Party B locations. Vector modifying means 64 and 65, respectively, situated at the Party A and Party B locations, respectively, copy vectors vec.sub.-- A and vec.sub.-- B, respectively, from storage means 62 and 63, respectively, and corrupt these vectors by bit-by-bit addition of noise sequences thereto. Vector modifying means 64 also supplies a modified vector rec.sub.-- A to vector modifying means 65, while vector modifying means 65 supplies a modified vector rec.sub.-- B to vector modifying means 64. Vectors vec.sub.-- A and rec.sub.-- B are encrypted by vector modifying means 64 using publicly known keying variable K.sub.1, while vectors vec.sub.-- B and rec.sub.-- A are encrypted by vector modifying means 65 using the same keying variable K.sub.1. Thus the vector outputs of vector modifying means 64, comprising vectors vec.sub.-- A and rec.sub.-- B are supplied to an Exclusive-Or means 66, while vector modifying means 65 supplies vector vec.sub.-- B, along with vector rec.sub.-- A received from vector modifying means 65, to an Exclusive-Or means 67. Exclusive-Or means 66 combines, by bit-by-bit Exclusive-Or logic, vectors vec.sub.-- A and rec.sub.-- B to generate a vector W.sub.-- A, while Exclusive-Or means 67 combines, by bit-by-bit Exclusive-Or logic, vectors vec.sub.-- B and rec.sub.-- A to generate a vector W.sub.-- B. Each of vector creating means 68 at the Party A location and vector creating means 69 at the Party B location comprises a parallel recirculating memory, such as memory 31 illustrated in FIG. 3. Thus, vector creating means 68 at the Party A location produces all 64-bit vectors that are within Hamming distance three of vector W.sub.-- A, while vector creating means 69 at the Party B location produces all 64-bit vectors that are a Hamming distance three from vector W.sub.-- B. The vector output signals produced by vector creating means 68 and 69 represent a Hamming weight three output vector and an image vector, as described in conjunction with the process shown in FIG. 2. Vector match detectors 82 and 83, respectively, situated at the Party A and Party B locations, respectively, receive the image vector from vector creating means 69 at the Party B location and vector creating means 68 at the Party A location, respectively. In addition, the image vectors transmitted by vector creating means 68 and 69, respectively, are also supplied to vector match detectors 82 and 83, respectively, which search at each Party's location, respectively, for two matches between the image vectors transmitted and the image vectors received. If many vectors match, the procedure is repeated, as has been previously described. However, if exactly two vectors match, then Party A and Party B each knows what the secret 64-bit vector X between them should be. At this juncture, encryption means 84 and 85, respectively, at the location of Party A and Party B, respectively, is used to encrypt vector X with a publicly known keying variable K.sub.2. Each respective encrypted vector X is supplied to a c-bit subset selector 86 and 87, respectively, at the location of Party A and Party B, respectively, allowing each c-bit subset selector to select a c-bit subset of the 64-bit vector from the respective one of encryption means 84 and 85 for use as a keying variable mutually held by the parties. While only certain preferred features of the invention have been illustrated and described herein, many modifications and changes will occur to those skilled in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.
|
Same subclass Same class Consider this |
||||||||||