Fast real-time public key cryptography

Claim 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 1 ,-,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 a.sub.i =2.sup.i-1 W.sup.-1 (modulo M), for i=1,2, . . . , k.