Exponentiation cryptographic apparatus and method

• US 4,424,414 A
• Filed: 05/01/1978
• Issued: 01/03/1984
• Est. Priority Date: 05/01/1978
• 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: Hellman, Martin E., Pohlig, Stephen C.
• Primary Examiner(s): Cangialosi, Sal
• Application Number:
  US05/901,770
• Time in Patent Office: 2,073 Days
• Field of Search: 178/22, 178/22.1, 178/22.11, 178/22.14, 179/1.5 R
• US Class Current: 380/30
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

A cryptographic system transmits a computationally secure cryptogram that is generated from a secret transformation of the message sent by the authorized transmitter; the cryptogram is again transformed by the authorized receiver using a secret reciprocal transformation to reproduce the message sent. The secret transformations use secret cipher keys that are known only by the authorized transmitter and receiver. The transformations are performed with nonsecret operations, exponentiation, that are easily performed but extremely difficult to invert. It is computationally infeasible for an eavesdropper either to solve known plaintext-ciphertext pairs for the secret cipher keys, or to invert the nonsecret operations that are used to generate the cryptogram.

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 by enciphering the message with a secret enciphering key at the transmitter, transmitting the enciphered message from the transmitter to the receiver, and deciphering the enciphered message with a secret deciphering key at the receiver, the improvement characterized by:

generating the secret deciphering key as the multiplicative inverse, in modular arithmetic, of the secret enciphering key;

generating the enciphered message by exponentiating, in modular arithmetic, the message with the secret enciphering key;

deciphering the enciphered message by exponentiating, in modular arithmetic, the enciphered message with the secret deciphering key, wherein the step of;

generating the secret deciphering key is performed by generating a secret deciphering key D, such that

space="preserve" listing-type="equation">D=K.sup.-1 (mod q-1)

where 1≦

D≦

q-2, q is a prime number, and the secret enciphering key K is an independent random number chosen uniformly from the set of integers (1, 2, . . . q-2) which are relatively prime to q-1;

generating the enciphered message is performed by generating an enciphered message C, such that

space="preserve" listing-type="equation">C=P.sup.K (mod q)

where P is the message; and

deciphering the enciphered message is performed by generating the message P, where

space="preserve" listing-type="equation">P=C.sup.D (mod q).

2. In an apparatus for communicating securely over an insecure communication channel of the type which communicates a message from a transmitter to a receiver comprising means for enciphering the message with a secret enciphering key at the transmitter, means for transmitting the enciphered message from the transmitter to the receiver, and means for deciphering the enciphered message with a secret deciphering key at the receiver, the improvement characterized by:

means for generating the secret deciphering key as the multiplicative inverse, in modular arithmetic, of the secret enciphering key;

means for generating the enciphered message by exponentiating, in modular arithmetic, the message with the secret enciphering key, having an input connected to receive the secret enciphering key, having another input connected to receive the message, and having an output that generates the enciphered message, and

means for deciphering the enciphered message by exponentiating, in modular arithmetic, the enciphered message with the secret deciphering key, having an input connected to receive the secret deciphering key, having another input connected to receive the enciphered message, and having an output that generates the message,

wherein said means for generating the secret deciphering key includes means for generating a secret deciphering key D, such that

space="preserve" listing-type="equation">D=K.sup.-1 (mod q-1)

where ≦

D≦

q-2, q is a prime number, and the secret enciphering key K is an independent random number chosen uniformly from the set of integers (1, 2, . . . , q-2) which are relatively prime to q-1;

wherein said means, for generating the enciphered message by exponentiating, includes means for generating an enciphered message C, such that

space="preserve" listing-type="equation">C=P.sup.K (mod q)

where P is the message; and

wherein said means, for deciphering the enciphered message by exponentiating, includes means for generating the message P, where,

space="preserve" listing-type="equation">P=C.sup.D (mod q).