Fast real-time public key cryptography
AssigneeBell Telephone Laboratories, Incorporated
InventorPaul S. Henry
Life of this patent
Estimating the term…
Abstract
In a public key cryptographic system (FIG. 1) for communicating securely over an insecure communication channel (3), a sender (1, 2) enciphers a data message (D) using a public enciphering knapsack key (H) to generate an enciphered message (S.sub.H). An authorized receiver (4 6, 7, 20, 21, 22) with knowledge of a private deciphering key (E), a modulus (M) and an integer multiplier (W) generates a private enciphering key (A) which is employed in further enciphering the received enciphered message to form a doubly enciphered message (S.sub.E, S.sub.E). The doubly enciphered message is deciphered using the private deciphering key alone to recover the original data message.
Claims8
A public key cryptographic system (FIG. 1) for communicating securely over an insecure communication channel (3), the system being of the type including a public enciphering knapsack key (H), a private deciphering key (E), first and second integers (M, W) related to each other and to the private deciphering key according to prescribed criteria wherein the first integer is a modulus M and the second integer is a multiplier W, first enciphering means (1) for transforming a data message (D) with the public enciphering knapsack key into a first enciphered message (S.sub.H), means (2) for transmitting the first enciphered message, and receiver means (4-7) for transforming the first enciphered message into the data message (D), the system characterized in that
- the receiver means includes means (20) responsive to the first and second integers for generating a private enciphering key (A), the private enciphering key is a k-dimensional vector of individual private enciphering key elements (a.sub.1 ,-,a.sub.k) represented as natural numbers, second enciphering means (21) for transforming the first enciphered message (S.sub.H) using the private enciphering key into a second enciphered message (S.sub.E), deciphering means (22) for transforming the second enciphered message using the private deciphering key into the data message (D), and the private enciphering key generating means includes an inverter means (30) responsive to the second integer for generating a multiplicative inverse W.sup.-1 therefor, and means (32, 33) responsive to the multiplicative inverse and to the modulus M for generating each individual private enciphering key element according to a prescribed criterion, so that
- a.sub.i =2.sup.i-1 W.sup.-1 (modulo M),
- for i=1,2, . . . , k.
A receiver adapted for use in a public key cryptographic system (FIG. 1) for transforming a first enciphered message (S.sub.H) into a data message (D), the receiver being of the type including a private deciphering key (E), first and second integers (M, W) related to each other and to the private deciphering key according to prescribed criteria wherein the first integer is a modulus M and the second integer is a multiplier W, the receiver characterized by
- means (20) responsive to the first and second integers for generating a private enciphering key (A), the private enciphering key is a k-dimensional vector of individual private enciphering key elements (a.sub.1,-,a.sub.k) represented as natural numbers, second enciphering means (21) for transforming the first enciphered message (S.sub.H) using the private enciphering key into a second enciphered message (S.sub.E), deciphering means (22) for transforming the second enciphered message using the private deciphering key into the data message (D), and the private enciphering key generating means includes an inverter means (30) responsive to the second integer for generating a multiplicative inverse W.sup.-1 therefor, and means (32, 33) responsive to the multiplicative inverse and to the modulus M for generating each individual private enciphering key element according to a prescribed criterion, so that
- a.sub.i =2.sup.i-1 W.sup.-1 (modulo M),
- for i=1,2,-,k.
Dependencies are inferred from the claim text.