Public key cryptographic apparatus and method

• US 4,218,582 A
• Filed: 10/06/1977
• Issued: 08/19/1980
• Est. Priority Date: 10/06/1977
• Status: Expired due to Term

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Inventors: Merkle, Ralph C., Hellman, Martin E.
• Primary Examiner(s): Birmiel, Howard A.
• Application Number:
  US05/839,939
• Time in Patent Office: 1,048 Days
• Field of Search: 178/22
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A cryptographic system transmits a computationally secure cryptogram that is generated from a publicly known transformation of the message sent by the transmitter; the cryptogram is again transformed by the authorized receiver using a secret reciprocal transformation to reproduce the message sent. The authorized receiver'"'"'s transformation is known only by the authorized receiver and is used to generate the transmitter'"'"'s transformation that is made publicly known. The publicly known transformation uses operations that are easily performed but extremely difficult to invert. It is infeasible for an unauthorized receiver to invert the publicly known transformation or duplicate the authorized receiver'"'"'s secret transformation to obtain the message sent.

Claims

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

providing random numbers at the receiver;

generating from said random numbers a public enciphering key at the receiver;

generating from said random numbers a secret deciphering key at the receiver such that the secret deciphering key is directly related to and computationally infeasible to generate from the public enciphering key;

communicating the public enciphering key from the receiver to the transmitter;

processing the message and the public enciphering key at the transmitter and generating an enciphered message by an enciphering transformation, such that the enciphering transformation is easy to effect but computationally infeasible to invert without the secret deciphering key;

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

processing the enciphered message and the secret deciphering key at the receiver to transform the enciphered message with the secret deciphering key to generate the message.

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

authenticating the receiver'"'"'s identity to the transmitter by the receiver'"'"'s ability to decipher the enciphered message.

3. In a method of communicating securely over an insecure communication channel as in claim 2 wherein the step of:

authenticating the receiver'"'"'s identity includes the receiver transmitting a representation of the message to the transmitter.

4. In a method of providing a digital signature for a communicated message comprising the steps of

providing random numbers at the transmitter;

generating from said random numbers a public key at the transmitter;

generating from said random numbers a secret key at the transmitter such that the secret key is directly related to and computationally infeasible to generate from the public key;

processing the message to be transmitted and the secret key at the transmitter to generate a digital signature at said transmitter by transforming a representation of the message with the secret key, such that the digital signature is computationally infeasible to generate from the public key;

communicating the public key to the receiver;

transmitting the message and the digital signature from the transmitter to the receiver;

receiving the message and the digital signature at the receiver and transforming said digital signature with the public key to generate a representation of the message; and

validating the digital signature by comparing the similarity of the message to the representation of the message generated from the digital signature.

5. A method of providing a message digital signature receipt for a communicated message comprising the steps of:

providing random numbers at the transmitter;

generating from said random numbers a public key at the transmitter;

generating from said random numbers a secret key at the transmitter such that the secret key is directly related to and computationally infeasible to generate from the public key;

processing the message and the secret key at the transmitter and generating a message-digital signature at said transmitter by transforming a representation of the message with the secret key, such that the message-digital signature is computationally infeasible to generate from the public key;

communicating the public key to the receiver;

transmitting the message-digital signature from the transmitter to the receiver;

processing the message-digital signature and the public key at the receiver and transforming the message-digital signature with the public key; and

validating the transformed message-digital signature by checking for redundancy.

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

means for generating random information at the receiver;

means for generating from said random information a public enciphering key at the receiver, means for generating from said random information a secret deciphering key such that the secret deciphering key is directly related to and computationally infeasible to generate from the public enciphering key;

means for communicating the public enciphering key from the receiver to the transmitter;

means for enciphering a message at the transmitter having an input connected to receive said public enciphering key, having another input connected to receive said message, and serving to transform said message with said public enciphering key, such that the enciphering transformation is computationally infeasible to invert without the secret deciphering key;

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

means for deciphering said enciphered message at the receiver having an input connected to receive said enciphered message, having another input connected to receive said secret deciphering key and serving to generate said message by inverting said transformation with said secret deciphering key.

7. 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 a secret deciphering key at the receiver by generating an n dimensional vector a'"'"', the elements of vector a'"'"', being defined by ##EQU26## where n is an integer;

generating a public enciphering key at the receiver by generating an n dimensional vector a, the elements of vector a being defined by

space="preserve" listing-type="equation">a.sub.i =(w*a.sub.i '"'"' mod m)+km for i=1,2, . . . n

where m and w are large integers, w is invertible modulo m, and k is an integer;

transmitting the public enciphering key from the receiver to the transmitter;

receiving the message and the public enciphering key at the transmitter and generating an enciphered message by computing the dot product of the message, represented as a vector x with each element being 0 or 1, and the public enciphering key, represented as the vector a, to represent the enciphered message S being defined by

space="preserve" listing-type="equation">S=a*x

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

receiving the enciphered message and the secret deciphering key at the receiver and transforming the enciphered message with the secret deciphering key to generate the message by computing

space="preserve" listing-type="equation">S'"'"'=1/w*S mod m

and letting x_i =1 if and only if ##EQU27## and letting x_i =0 if ##EQU28## for i=n, n-1, . . . 1.

8. 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 a secret deciphering key at the receiver by generating an n dimensional vector a'"'"', the elements of vector a'"'"' being defined by ##EQU29## for i=1, 2, . . . n where l and n are integers;

generating a public enciphering key at the receiver by generating an n dimensional vector a, the elements of vector a being defined by

space="preserve" listing-type="equation">a.sub.i =(W*a.sub.i '"'"' mod m)+km for i=1, 2, . . . n

where m and w are large integers, w is invertible modulo m and k is an integer;

transmitting the public enciphering key from the receiver to the transmitter;

receiving the message and the public enciphering key at the transmitter and generating an enciphered message by computing the dot product of the message, represented as a vector x with each element being an integer between 0 and l, and the public enciphering key, represented as the vector a, to represent the enciphered message S being defined by

space="preserve" listing-type="equation">S=a*x;

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

receiving the enciphered message and the secret deciphering key at the receiver and transforming the enciphered message with the secret deciphering key to generate the message by computing

space="preserve" listing-type="equation">S'"'"'=1/w*S mod m

and letting x_i be the integer part of ##EQU30## for i=n, n-1, . . . 1.

9. 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 a secret deciphering key at the receiver by generating an n dimensional vector a'"'"', the elements of vector a'"'"' being relatively prime and n being an integer;

generating a public enciphering key at the receiver by generating an n dimensional vector a, the elements of vector a being defined by

space="preserve" listing-type="equation">a.sub.i =log.sub.b a.sub.i '"'"' mod m for i=1, 2 . . . n

where b and m are large integers and m is a prime number such that ##EQU31## transmitting the public enciphering key from the receiver to the transmitter;

receiving the message and the public enciphering key at the transmitter and generating an enciphered message by computing the dot product of the message, represented as a vector x, and the public enciphering key, represented as the vector a, to represent the enciphered message S being defined by

space="preserve" listing-type="equation">S=a*x;

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

receiving the enciphered message and the secret deciphering key at the receiver and transforming the enciphered message with the secret deciphering key to generate the message by computing

space="preserve" listing-type="equation">S'"'"'=b.sup.S mod m

and letting x_i =1 if and only if the quotient of S'"'"'/a_i is an integer and letting x_i =0 if the quotient of S'"'"'/a_i is not an integer.

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

means for generating a secret deciphering key at the receiver by generating an n dimension vector a'"'"', the elements of vector a'"'"' being defined by ##EQU32## where n is an integer;

11. means for generating a public enciphering key at the receiver by generating an n dimensional vector a, the elements of vector a being defined by

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

means for generating a secret deciphering key at the receiver by generating an n dimensional vector a'"'"', the elements of vector a'"'"' being defined by ##EQU35## where l and n are integers;

means for generating a public enciphering key at the receiver by generating an n dimensional vector a, the elements of vector a being defined by

space="preserve" listing-type="equation">a.sub.i =(w*a.sub.i '"'"' mod m)+km for i=1, 2 . . . n

where m and w are large integers, w is invertible modulo m, and k is an integer;

means for transmitting the public enciphering key from the receiver to the transmitter;

means, for enciphering a message at the transmitter, having an input connected to receive the public enciphering key, having another input connected to receive the message, and having an output that generates an enciphered message that is a transformation of the message with the public enciphering key by computing the dot product of the message, represented as a vector x with each element being an integer between 0 and l, and the public enciphering key, represented as the vector a, to represent the enciphered message S being defined by

space="preserve" listing-type="equation">S=a*x;

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

means for deciphering the enciphered message at the receiver, having an input connected to receive the enciphered message, having another input connected to receive the secret deciphering key, and having an output for generating the message by inverting the transformation with the secret deciphering key by computing

space="preserve" listing-type="equation">S'"'"'=1/w*S mod m

and letting x_i be the integer part of ##EQU36## for i=n, n-1, . . . 1.

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

means for generating a secret deciphering key at the receiver by generating an n dimensional vector a'"'"', the elements of vector a'"'"' being relatively prime and n being an integer;

means for generating a public enciphering key at the receiver by generating an n dimensional vector a, the elements of vector a being defined by

space="preserve" listing-type="equation">a.sub.i =log.sub.b a.sub.i '"'"' mod m for i=1, 2, . . . n

where b and m are large integers and m is a prime number such that ##EQU37## means for transmitting the public enciphering key from the receiver to the transmitter;

means, for enciphering a message at the transmitter, having an input connected to receive the public enciphering key, having another input connected to receive the message, and having an output that generates an enciphered message that is a transformation of the message with the public enciphering key by computing the dot product of the message, represented as a vector x with each element being 0 or 1, and the public enciphering key, represented as the vector a, to represent the enciphered message S being defined by

space="preserve" listing-type="equation">S=a*x;

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

means for deciphering the enciphered message at the receiver, having an input connected to receive the enciphered message, having another input connected to receive the secret deciphering key, and having an output for generating the message by inverting the transformation with the secret deciphering key by computing

space="preserve" listing-type="equation">S'"'"'=b.sup.S mod m

and letting x_i =1 if and only if the quotient of S'"'"'/a_i is an integer and letting x_i =0 of the quotient of S'"'"'/a_i is not an integer.

14. In an apparatus for enciphering a message that is to be transmitted over an insecure communication channel having an input connected to receive a message to be maintained secret, having another input connected to receive a public enciphering key, and having an output for generating the enciphered message, characterized by:

means for receiving the message and converting the message to a vector representation of the message;

means for receiving the public enciphering key and converting the public enciphering key to a vector representation of the public enciphering key; and

means for generating the enciphered message by computing the dot product of the vector representation of the message and the vector representation of the public enciphering key, having an input connected to receive the vector representation of the message, having another input connected to receive the vector representation of the public enciphering key, and having an output for generating the enciphered message.

15. 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 a secret deciphering key at the receiver;

generating a public enciphering key at the receiver, such that the secret deciphering key is computationally infeasible to generate from the public enciphering key;

transmitting the public enciphering key from the receiver to the transmitter;

processing the message and the public enciphering key at the transmitter by computing the dot product of the message, represented as a vector, and the public enciphering key, represented as a vector, to represent the enciphered message, such that the enciphering transformation is easy to effect but computationally infeasible to invert without the secret deciphering key;

transmitting the enciphered message from the transmitter to the receiver;

and processing the enciphered message and the secret deciphering key at the receiver and inverting said transformation by transforming the enciphered message with the secret deciphering key to generate the message.

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

means for generating a secret deciphering key at the receiver;

means for generating a public enciphering key at the receiver, such that the secret deciphering key is computationally infeasible to generate from the public enciphering key;

means for transmitting the public enciphering key from the receiver to the transmitter;

means for enciphering a message at the transmitter having an input connected to receive said public enciphering key and having another input connected to receive said message and serving to transform said message by computing the dot product of said message, represented as a vector, and said public enciphering key, represented as a vector, to represent said enciphered message, such that the enciphering transformation is computationally infeasible to invert without the secret deciphering key;

means for transmitting the enciphered message from the transmitter to the receiver;

and means for deciphering said enciphered message at the receiver, said means having an input connected to receive said enciphered message and having another input connected to receive said secret deciphering key and serving to generate said message by inverting the transformation with said secret deciphering key.

17. An apparatus for deciphering an enciphered message that is received over an insecure communication channel including

means for receiving the enciphered message that is enciphered by an enciphering transformation in which a message to be maintained secret is transformed with a public enciphering key, and means for receiving a secret deciphering key to generate the message by inverting the enciphering transformation;

means for generating the message having an input connected to receive the inverse of the enciphered message and an output for generating the message;

said secret deciphering key being computationally infeasible to generate from the public enciphering key, and said enciphering transformation being computationally infeasible to invert without the secret deciphering key in which

said means for inverting the enciphering transformation includes means for computing

space="preserve" listing-type="equation">S'"'"'=1/w*S mod m; and

said means for generating the message includes means for setting x_i equal to the integer part of ##EQU38## where m and w are large integers and w is invertible modulo m, where S'"'"' is the inverse of the enciphered message S being defined by the enciphering transformation

space="preserve" listing-type="equation">S=a*x

where the message is represented as an n dimensional vector x with each element x_i being an integer between 0 and l, where l is an integer, and where the public enciphering key is represented as an n dimensional vector a, the elements of a being defined by

space="preserve" listing-type="equation">a.sub.i =(w*a.sub.j '"'"' mod m)+km for i=1, 2, . . . n

where k and n are integers and the secret deciphering key is m, w and a'"'"', where a'"'"' is an n dimensional vector, the elements of a'"'"' being defined by ##EQU39##

18. An apparatus for deciphering an enciphered message that is received over an insecure communication channel including

means for receiving the enciphered message that is enciphered by an enciphering transformation in which a message to be maintained secret is transformed with a public enciphering key, and means for receiving a secret deciphering key to generate the messge by inverting the enciphering transformation;

means for generating the message having an input connected to receive the inverse of the enciphered message and an output for generating the message;

said secret deciphering key being computationally infeasible to generate from the public enciphering key, and said enciphering transformation being computationally infeasible to invert without the secret deciphering key in which

said means for inverting the enciphering transformation includes means for computing

space="preserve" listing-type="equation">S'"'"'=b.sup.S mod m; and

said means for generating the message includes means for setting x_i =1 if and only if the quotient of S'"'"'/a_i is an integer and setting x_i =0 of the quotient of S'"'"'/a_i is not an integer, where b and m are large integers and m is a prime number such that ##EQU40## where n is an integer and the secret deciphering key is b,m, and a'"'"', where a'"'"' is an n dimensional vector with each element aⁱ '"'"' being relatively prime, and where S'"'"' is the inverse of the enciphered message S being defined by the enciphering transformation

space="preserve" listing-type="equation">S=a*x

where the message is represented as an n dimensional vector x with each element x_i being 0 or 1, and the public enciphering key is represented as the n dimensional vector a, the elements of a being defined by

space="preserve" listing-type="equation">a.sub.i =log.sub.b a.sub.i '"'"' mod m for i=1, 2, . . . n