Cryptographic apparatus and method

• US 4,200,770 A
• Filed: 09/06/1977
• Issued: 04/29/1980
• Est. Priority Date: 09/06/1977
• Status: Expired due to Term

• Current Assignee: Stanford University
• Original Assignee: Stanford University
• Inventors: Hellman, Martin E., Merkle, Ralph C., Diffie, Bailey W.
• Primary Examiner(s): Birmiel, Howard A.
• Application Number:
  US05/830,754
• Time in Patent Office: 966 Days
• Field of Search: 178/22, 340/149 R
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys

Abstract

A cryptographic system transmits a computationally secure cryptogram over an insecure communication channel without prearrangement of a cipher key. A secure cipher key is generated by the conversers from transformations of exchanged transformed signals. The conversers each possess a secret signal and exchange an initial transformation of the secret signal with the other converser. The received transformation of the other converser'"'"'s secret signal is again transformed with the receiving converser'"'"'s secret signal to generate a secure cipher key. The transformations use non-secret operations that are easily performed but extremely difficult to invert. It is infeasible for an eavesdropper to invert the initial transformation to obtain either conversers'"'"' secret signal, or duplicate the latter transformation to obtain the secure cipher key.

Claims

1. A secure key generator comprising:

a first input connected to receive an applied first signal;

a second input connected to receive an applied second signal;

a first output;

a second output; and

means for generating at the first output a third signal, that is a transformation of said first signal and which transformation is infeasible to invert, and for generating at the second output a fourth signal, that is a transformation of said second signal with said first signal, which represents a secure key and is infeasible to generate solely with said second signal and said third signal.

2. In a method of communicating securely over an insecure communication channel of the type which communicates a message from a transmitter to a receiver, the improvement characterized by:

generating and transforming, in a manner infeasible to invert, a first signal at the transmitter to generate a transformed first signal;

generating and transforming, in a manner infeasible to invert, a second signal at the receiver to generate a transformed second signal;

transmitting said transformed first signal from the transmitter to the receiver;

transmitting said transformed second signal from the receiver to the transmitter;

transforming said transformed second signal with said first signal at the transmitter to generate a third signal, representing a secure cipher key, that is infeasible to generate solely with said transformed first signal and said transformed second signal;

transforming said transformed first signal with said second signal at the receiver to generate a fourth signal that is identical to the third signal and represents said secure cipher key;

enciphering the message with said secure cipher key at the transmitter;

transmitting the enciphered message from the transmitter to the receiver; and

deciphering the enciphered message with said secure cipher key at the receiver.

3. In a method of communicating securely over an insecure communication channel as in claim 2, further comprising:

authenticating the receiver'"'"'s identity at the transmitter from the receiver'"'"'s ability to generate the fourth signal, representing the secure cipher key.

4. A method of generating a secure cipher key between a transmitter and receiver comprising the steps of:

generating and transforming, in a manner infeasible to invert, a first signal at the transmitter to generate a transformed first signal;

generating and transforming, in a manner infeasible to invert, a second signal at the receiver to generate a transformed second signal;

transmitting said transformed first signal from the transmitter to the receiver

transmitting said transformed second signal from the receiver to the transmitter;

transforming said transformed second signal with said first signal at the transmitter to generate a third signal, representing a secure cipher key, that is infeasible to generate solely with said transformed first signal and said transformed second signal; and

transforming said transformed first signal with said second signal at the receiver to generate a fourth signal that is identical to the third signal and represents said secure cipher key.

5. An apparatus for generating a secure cipher key comprising:

a first secure key generator having a first input connected to receive an applied first signal, having a second input connected to receive a second signal, having a first and second outputs, and having a means for generating at the first output a third signal, that is a transformation of said first signal and which transformation is infeasible to invert, and for generating at the second output a fourth signal, that is a transformation of said second signal with said first signal, which represents a secure key and is infeasible to generate solely with said second signal and said third signal; and

a second secure key generator having a first input connected to receive an applied fifth signal, having a second input connected to receive said third signal, having a first and second outputs, and having a means for generating at the first output said second signal, that is a transformation of said fifth signal and which transformation is infeasible to invert, and for generating at the second output a sixth signal, that is a transformation of said third signal with said fifth signal, which represents the secure key and is infeasible to generate solely with said second signal and said third signal.

6. A method of generating a secure cipher key between a transmitter and receiver comprising the steps of:

transforming, in a manner infeasible to invert, a first signal at the transmitter to generate a transformed first signal wherein transforming said first signal is performed by raising a first number to a power represented by said first signal, modulo a second number;

transforming, in a manner infeasible to invert, a second signal at the receiver to generate a transformed second signal, wherein transforming said second signal is performed by raising the first number to a power represented by said second signal, modulo the second number;

transmitting said transformed first signal from the transmitter to the receiver;

transmitting said transformed second signal from the receiver to the transmitter;

transforming said transformed second signal with said first signal at the transmitter to generate a third signal, representing a secure cipher key, that is infeasible to generate solely with said transformed first signal and said transformed second signal, wherein transforming said transformed second signal with said first signal is performed by raising a number represented by said transformed second signal to a power represented by said first signal, modulo the second number; and

transforming said transformed first signal with said second signal at the receiver to generate a fourth signal, representing said secure cipher key, that is infeasible to generate solely with said transformed first signal and said transformed second signal, wherein transforming said transformed first signal with said second signal is performed by raising a number represented by said transformed first signal to a power represented by said second signal, modulo the second number.

7. An apparatus for generating a secure cipher key comprising:

a first secure key generator having a first input connected to receive an applied first signal, having a second input connected to receive a second signal, having first and second outputs, and having a means for generating at the first output a third signal, that is a transformation of said first signal in which said transformation includes raising a first number to a power represented by said first signal, modulo or second number, and for generating at the second output a fourth signal, that is a transformation of said second signal with said first signal which transformation includes raising a number represented by said second signal to a power represented by said first signal, modulo the second number, which represents a secure key and is infeasible to generate solely with said second signal and said third signal; and

a second secure key generator having a first input connected to receive an applied fifth signal, having a second input connected to receive said third signal, having a first and second outputs, and having a means for generating at the first output said second signal, that is a transformation of said fifth signal in which said transformation includes raising a first number to a power represented by said fifth signal, modulo the second number, and for generating at the second output a sixth signal, that is a transformation of a said third signal with said fifth signal which transformation includes raising a number represented by said third signal to a power represented by said fifth signal, modulo the second number, which represents the secure key and is infeasible to generate solely with said second signal and said third signal.

8. An apparatus for generating a secure cipher key comprising:

a first secure key generator having a first input connected to receive an applied first signal, having a second input connected to receive a second signal, having a first and second outputs, and having a means for generating at the first output a third signal, said third signal Y_i being described by

space="preserve" listing-type="equation">Y.sub.i =a.sup.x.sbsp.i mod q

where

q=a large prime number

a=a random number, such that 1≦

a≦

q-1

x_i =the first signal which represents a random number, such that 1≦

X_i ≦

q-1

a transformation of said first signal which is infeasible to invert, and for generating at the second output a fourth signal, said fourth signal K_ij being described by

space="preserve" listing-type="equation">K.sub.ij =Y.sub.j.sup.X.sbsp.i mod q

where

Y_j =the second signal

a transformation of said second signal with said first signal, which represents said secure cipher key and is infeasible to generate solely with said second signal and said third signal; and

a second secure key generator having a first input connected to receive an applied fifth signal, having a second input connected to receive said third signal, having a first and second outputs, and having a means for generating at the first output a second signal, said second signal Y_j being described by

space="preserve" listing-type="equation">Y.sub.j =a.sup.X.sbsp.j mod q

where

X_j =the fifth signal which represents a random number, such that 1≦

X_j ≦

q-1

a transformation of said fifth signal which is infeasible to invert, and for generating at the second output a sixth signal, said sixth signal K_ij being described by

space="preserve" listing-type="equation">K.sub.ij =Y.sub.i.sup.X.sbsp.j mod q

a transformation of said third signal with said fifth signal, which represents the secure key and is infeasible to generate solely with said second signal and said third signal.