Fast real-time public key cryptography

• US 4,399,323 A
• Filed: 02/09/1981
• Issued: 08/16/1983
• Est. Priority Date: 02/09/1981
• Status: Expired due to Fees

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Inventors: Henry, Paul S.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): NOT, DEFINED
• Application Number:
  US06/233,034
• Time in Patent Office: 918 Days
• Field of Search: 178/22.13, 178/22.14
• US Class Current: 380/30
• 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: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

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_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_E, S_E). The doubly enciphered message is deciphered using the private deciphering key alone to recover the original data message.

Claims

1. 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_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₁ ,-,a_k) represented as natural numbers, second enciphering means (21) for transforming the first enciphered message (S_H) using the private enciphering key into a second enciphered message (S_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^-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

View Dependent Claims (2, 3, 4)

2. The system as defined in claim 1 wherein the first enciphered message is a k-dimensional vector of individual elements represented as binary numbers (s_H,l ,-,s_H,k) and the second enciphering means includes means (40, 41) responsive to individual elements of the first enciphered message and to individual private enciphering key elements for generating an enciphered message S_E in accordance with a prescribed criterion so that ##EQU6## and means (42) responsive to the first integer for filtering the enciphered message to generate the second enciphered message S_E.

3. The system as defined in claim 2 wherein the first integer is a modulus M and the filtering means (42) is a reduction modulo-M circuit for generating the second enciphered message S_E according to a prescribed criterion as follows, S_E =S_E (modulo-M).

4. The system as defined in claim 3 wherein the generating means of the second enciphering means includes means (40) responsive to each individual element of the first enciphered message for selectively inhibiting transmission of each corresponding private enciphering key element and an accumulator (41) for summing together individual private enciphering key elements transmitted from the selectively inhibiting means to generate the enciphered message S_E.

5. A receiver adapted for use in a public key cryptographic system (FIG. 1) for transforming a first enciphered message (S_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₁,-,a_k) represented as natural numbers, second enciphering means (21) for transforming the first enciphered message (S_H) using the private enciphering key into a second enciphered message (S_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^-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

View Dependent Claims (6, 7, 8)

6. The receiver as defined in claim 5 wherein the first enciphered message is a k-dimensional vector of individual elements represented as binary numbers (s_H,l,-,s_H,k) and the second enciphering means includes means (40, 41) responsive to individual elements of the first enciphered message and to individual private enciphering key elements for generating an enciphered message S_E in accordance with a prescribed criterion so that ##EQU7## and means (42) responsive to the first integer for filtering the enciphered message to generate the second enciphered message S_E.

7. The receiver as defined in claim 6 wherein the first integer is a modulus M and the filtering means (42) is a reduction modulo-M circuit fir generating the second enciphered message S_E according to a prescribed criterion as follows, S_E =S_E (modulo-M).

8. The receiver as defined in claim 7 wherein the generating means of the second enciphering means includes means (40) responsive to each individual element of the first enciphered message for selectively inhibiting transmission of each corresponding private enciphering key element and an accumulator (41) for summing together individual private enciphering key elements transmitted from the selectively inhibiting means to generate the enciphered message S_E.