US 5,204,901 A · Public key cryptographic mechanism

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.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.

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.sub.1 for use by both parties;
b. Party a randomly generating an m-bit vector vec.sub.-- a, storing said vector vec.sub.-- A, copying said vector vec.sub.-- A, corrupting the copied vector vec.sub.-- A by inverting n bits thereof, and transmitting the corrupted vector vec.sub.-- A, designated vector rec.sub.-- A, over the communication channel to the location of Party B;
c. Party B randomly generating an m-bit vector vec.sub.-- B, storing said vector vec.sub.-- B, copying said vector vec.sub.-- B, corrupting the copied vector vec.sub.-- B by inverting n bits thereof, and transmitting the corrupted vector vec.sub.-- B, designated vector rec.sub.-- B, over the communication channel to the location of Party A;
d. Party A generating a vector W.sub.-- A representing the Exclusive-Or combination of the stored vector vec.sub.-- A with vector rec.sub.-- B received from Party B;
e. Party B generating a vector W.sub.-- B representing the Exclusive-Or combination of the stored vector vec.sub.-- B with vector rec.sub.-- A received from Party A;
f. Party A producing all ##EQU7## vectors that are n bits different from vector W.sub.-- a, encrypting said ##EQU8## vectors with a Data Encryption Standard (DES) operated in the ECB/ENCRYPT mode and keyed by keying variable K.sub.1, 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.sub.-- B and encrypting said ##EQU11## vectors thus produced with a DES operated in the ECB/ENCRYPT mode and keyed by keying variable K.sub.1, 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.sub.-- A and vec.sub.-- 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.sub.2 ;
k. both parties enciphering m-bit vector X using an encrypting algorithm keyed by said variable K.sub.2 ;
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.sub.2 as said private cryptographic keying variable.

10 more elements

Public key cryptographic mechanism

Life of this patent

Public key cryptographic mechanism

Life of this patent

Abstract

Claims5