Public key cryptographic mechanism

• US 5,204,901 A
• Filed: 08/01/1991
• Issued: 04/20/1993
• Est. Priority Date: 08/01/1991
• Status: Expired due to Fees

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Ozarow, Lawrence H., Yarlagadda, Radha Krishna R., Hershey, John E.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US07/739,263
• Time in Patent Office: 628 Days
• Field of Search: 380/21, 380/29, 380/30, 380/28
• US Class Current: 380/285
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/0838 Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these network architectures or network communication protocols for key exchange in a packet data network H04L63/061
• CPC Class Codes: H04L 9/088 Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068

Abstract

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_-- A and vec_-- 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_-- A and vec_-- B with a received vector, denoted rec_-- B and rec_-- A, to generate respective vectors W_-- A and W_-- B. Parties A and B then generate all ##EQU1## vectors at a Hamming distance n from W_-- A and W_-- 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₁, 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₂.

Claims

1. A method for ensuring secure communications between two Parties, A and B, over an insecure, predetermined bandwidth communication channel between the parties by establishing a commonly held, electronically generated, private cryptographic keying variable between the parties, each party having both transmitting and receiving capability at its respective location, said method comprising the steps of:

a. establishing a publicly known keying variable K₁ for use by both parties;

b. Party a randomly generating an m-bit vector vec_-- a, storing said vector vec_-- A, copying said vector vec_-- A, corrupting the copied vector vec_-- A by inverting n bits thereof, and transmitting the corrupted vector vec_-- A, designated vector rec_-- A, over the communication channel to the location of Party B;

c. Party B randomly generating an m-bit vector vec_-- B, storing said vector vec_-- B, copying said vector vec_-- B, corrupting the copied vector vec_-- B by inverting n bits thereof, and transmitting the corrupted vector vec_-- B, designated vector rec_-- B, over the communication channel to the location of Party A;

d. Party A generating a vector W_-- A representing the Exclusive-Or combination of the stored vector vec_-- A with vector rec_-- B received from Party B;

e. Party B generating a vector W_-- B representing the Exclusive-Or combination of the stored vector vec_-- B with vector rec_-- A received from Party A;

f. Party A producing all ##EQU7## vectors that are n bits different from vector W_-- a, encrypting said ##EQU8## vectors with a Data Encryption Standard (DES) operated in the ECB/ENCRYPT mode and keyed by keying variable K₁, and producing Party A image vectors representing the Exclusive-Or combination of the ##EQU9## vectors with their encryptions, and transmitting the Party A image vectors in random order over the communication channel to Party B;

g. Party B producing all ##EQU10## vectors that are n bits different from vector W_-- B and encrypting said ##EQU11## vectors thus produced with a DES operated in the ECB/ENCRYPT mode and keyed by keying variable K₁, and producing Party B image vectors representing the Exclusive-Or combination of the ##EQU12## vectors with their encryptions, and transmitting the Party B image vectors in random order over the communication channel to Party A;

h. each one of Parties a and B thereafter searching the image vectors received from the other Party for exactly two matches with the image vectors transmitted by the one Party;

i. both parties ten determining a commonly held m-bit vector denoted X, equal to the bit-by-bit Exclusive-Or sum of vectors vec_-- A and vec_-- B and known only to the parties, for use in deriving a keying variable for a single key encryption algorithm to maintain security for exchanges of traffic;

j. establishing a second publicly known keying variable K₂ ;

k. both parties enciphering m-bit vector X using an encrypting algorithm keyed by said variable K₂ ; and

l. each one of Parties A and B then selecting a c-bit subset of m-bit vector X enciphered under keying variable K₂ as said private cryptographic keying variable.

2. The method for ensuring secure communications between two Parties, A and B, over an insecure communication channel between the parties, recited in claim 1, wherein n is 3, m is 64 and the c-bit subset comprises the first 56 of the m bits.

3. The method for ensuring secure communications between two Parties, A and B, over an insecure communication channel between the parties, recited in claim 1, wherein said encrypting algorithm is the DES.

4. A public key mechanism for ensuring secure communications between two Parties, A and B, by establishing a commonly held, electronically generated, private cryptographic keying variable between them, each party having means for both transmitting and receiving data over an insecure, predetermined bandwidth communication channel, said mechanism comprising:

a. first and second random bit vector generators respectively controlled by Parties A and B for randomly generating m-bit vectors denoted vec_-- A and vec_-- B;

b. first and second vector storage means for storing said vectors vec_-- A and vec_-- B respectively;

c. first and second modifying means, respectively, for copying said vectors vec_-- a and vec_-- B and corrupting said vectors vec_-- a and vec_-- B by bit-by-bit addition of noise sequences;

d. first and second communication means for exchanging between the Parties A and B the vectors modified by said first and second modifying means, respectively, received vectors being denoted as vectors rec_-- B and rec_-- A respectively, said first communication means including the transmitting means of Party A and the receiving means of Party B, and said second communication means including the transmitting means of Party B and the receiving means of Party A;

e. first and second Exclusive-Or means for respectively combining by bit-by-bit Exclusive-Or logic the stored m-bit vectors vec_-- A and vec_-- B, respectively, with the received vectors rec_-- B and rec_-- A, respectively, to generate respective vectors W_-- a and W_-- B;

f. first and second parallel recirculating memories for creating all ##EQU13## vectors at Hamming distance n from vectors W_-- A and W_-- B respectively, encrypting said ##EQU14## vectors and adding said ##EQU15## vectors to their encryptions to produce image vectors;

g. said first and second communication means allowing said Parties A and B to exchange with each other, in random order, said image vectors;

h. first and second match detector means for searching, for each respective party, for two matches between the image vectors transmitted by said respective party and the image vectors received by said respective party;

i. first and second means coupled, respectively to said first and second match detector means, respectively, for constructing vector X form the matches of image vectors, said vector X being a secret m-bit vector known only to Parties A and B when said two matches, and only said two matches, exist;

j. encryption means for enciphering the vector X using an encryption algorithm keyed by a publicly known key K₂ to generate an m-bit value; and

k. selecting means for selecting a predetermined c-bit subset of said m-bit value as said private cryptographic keying variable.

5. The public key mechanism of claim 4 further including thresholder means coupled to each of said parallel recirculating memories, respectively, for monitoring a randomly produced zero mean noise signal such that memory circulation is ceased and a randomly generated m-bit vector having three ones is read out when a predetermined threshold is exceeded by said signal.