Absolute public key cryptographic system and method surviving private-key compromise with other advantages
First Claim
1. In a system for sending messages over a network between first and second computing units, method comprising the following steps:
- (a). computing r components of encrypting key e.sub.1, e.sub.2, . . . , e.sub.r and r components of decrypting key d.sub.1, d.sub.2, . . . , d.sub.r according to the following relations;
(e.sub.1).(d.sub.1)+(e.sub.2).(d.sub.2)+ . . . +(e.sub.r).(d.sub.r)=(k.sub.1).(p−
1).(q−
1)+1 and (d.sub.1)+(d.sub.2)+ . . . +(d.sub.r)=(k.sub.2).(p−
1).(q−
1), where;
p and q are two prime numbers;
k.sub.1 and k.sub.2 are suitable integers; and
encrypting a message M into r cipher versions M.sub.1, M.sub.2, . . . , M.sub.r using the r blinded components of the encrypting key e.sub.1+t, e.sub.2+t, . . . ,e.sub.r+t as follows;
M.sub.1=(M.sup.(e.sub.1+t)) mod n M.sub.2=(M.sup.(e.sub.2+t)) mod n . . . M.sub.r=(M.sup.(e.sub.r+t)) mod n, where;
n=p.q;
t is a random number generated on encrypting unit and discarded after encryption is complete;
mod represents the remainder left when left hand operand is divided by right hand operand;
or computing the key components e.sub.1, e.sub.2, . . . , e.sub.r and d.sub.1, d.sub.2, . . . , d.sub.r according to the following relation and conditions;
(e.sub.1).(d.sub.1)+(e.sub.2).(d.sub.2)+ . . . +(e.sub.r).(d.sub.r)=(k.sub.1).(p−
1).(q−
1)+1 and each of the values (e.sub.1), (e.sub.2), . . . , (e.sub.r) has a common factor with (p−
1).(q−
1), but there is no common factor for all (e.sub.1), (e.sub.2), . . . , (e.sub.r), (p−
1).(q−
1), where;
p and q are prime numbers;
k.sub.1 is a suitable integer; and
encrypting a message M into r cipher versions M.sub.1, M.sub.2, . . . , M.sub.r using the r components of the encrypting key, e.sub.1, e.sub.2 . . . , e.sub.r as follows;
M.sub.1=M.sup.(e.sub.1) mod n M.sub.2=M.sup.(e.sub.2) mod n . . . M.sub.r=M.sup.(e.sub.r) mod n, where;
n=p.q;
p and q are two prime numbers;
(b). delivering all the cipher versions of the message individually to the destination unit in source routing mode, or hop-by-hop routing mode with a small time gap between every two consecutive cipher versions;
(c). collecting all the cipher versions at the destination unit;
(d). computing r number of values N.sub.1, N.sub.2, . . . , N.sub.r using r components d.sub.1, d.sub.2, . . . , d.sub.r of decrypting key, where;
N.sub.1=((M.sub.1).sup.(d.sub.1)) mod n N.sub.2=((M.sub.2).sup.(d.sub.2)) mod n . . . N.sub.r=((M.sub.r).sup.(d.sub.r)) mod n, where;
n is the same composite number as used for encryption;
(e). reproducing the original message M as follows;
M=(N.sub.1).(N.sub.2) . . . (N.sub.r) mod n, where;
n is the same composite number as used for encryption.
4 Assignments
0 Petitions
Accused Products
Abstract
The present invention presents a public key cryptographic system and method called Absolute Public Key Cryptography that survives private key compromise and offers two-way communication security. Communications are secured even when the private key is revealed. It provides security to the private-to-public side communications and also allows short keys to be used with mobile devices that have low processing power. The system uses keys with two or more components and encrypts a message into the same number of cipher versions. The cipher versions are delivered to the destination in source routing mode, or hop-by-hop routing mode with a small time gap. The recipient performs certain mathematical operations on all the cipher versions and obtains the original message. All the versions are necessary for obtaining the original message. Even a single version missing leads to produce a junk for an attacker. As an attacker at an intermediary IP router can not have all the cipher versions available, he can not obtain the original message even when he knows the private key. This is why the system is called Absolute Public Key Cryptography. The robustness against private key compromise is achieved by blinding the public key through adding a random number to each of its components before encryption. When the encryption process is complete, the random number is discarded and the cipher versions are delivered to the recipient. The effect of blinding is made void by the actual intended recipient, who has all the cipher versions available. Robustness is also achieved another way, that is, by choosing the encrypting key such that each of its components has a common factor with Euler Totient Function of the key modulus, and there is no common factor among all the components. This makes it harder for an attacker to decrypt a single cipher version of the message into the original message and thereby allows smaller keys to be used for mobile communications. Communication in both directions is secured by using two different key pairs, one for public-to-private-side and the other for private-to-public-side communications.
-
Citations
15 Claims
-
1. In a system for sending messages over a network between first and second computing units, method comprising the following steps:
-
(a). computing r components of encrypting key e.sub.1, e.sub.2, . . . , e.sub.r and r components of decrypting key d.sub.1, d.sub.2, . . . , d.sub.r according to the following relations;
(e.sub.1).(d.sub.1)+(e.sub.2).(d.sub.2)+ . . . +(e.sub.r).(d.sub.r)=(k.sub.1).(p−
1).(q−
1)+1and (d.sub.1)+(d.sub.2)+ . . . +(d.sub.r)=(k.sub.2).(p−
1).(q−
1), where;
p and q are two prime numbers;
k.sub.1 and k.sub.2 are suitable integers; and
encrypting a message M into r cipher versions M.sub.1, M.sub.2, . . . , M.sub.r using the r blinded components of the encrypting key e.sub.1+t, e.sub.2+t, . . . ,e.sub.r+t as follows;
M.sub.1=(M.sup.(e.sub.1+t)) mod n M.sub.2=(M.sup.(e.sub.2+t)) mod n . . . M.sub.r=(M.sup.(e.sub.r+t)) mod n, where;
n=p.q;
t is a random number generated on encrypting unit and discarded after encryption is complete;
mod represents the remainder left when left hand operand is divided by right hand operand;
or computing the key components e.sub.1, e.sub.2, . . . , e.sub.r and d.sub.1, d.sub.2, . . . , d.sub.r according to the following relation and conditions;
(e.sub.1).(d.sub.1)+(e.sub.2).(d.sub.2)+ . . . +(e.sub.r).(d.sub.r)=(k.sub.1).(p−
1).(q−
1)+1and each of the values (e.sub.1), (e.sub.2), . . . , (e.sub.r) has a common factor with (p−
1).(q−
1), but there is no common factor for all (e.sub.1), (e.sub.2), . . . , (e.sub.r), (p−
1).(q−
1), where;
p and q are prime numbers;
k.sub.1 is a suitable integer; and
encrypting a message M into r cipher versions M.sub.1, M.sub.2, . . . , M.sub.r using the r components of the encrypting key, e.sub.1, e.sub.2 . . . , e.sub.r as follows;
M.sub.1=M.sup.(e.sub.1) mod n M.sub.2=M.sup.(e.sub.2) mod n . . . M.sub.r=M.sup.(e.sub.r) mod n, where;
n=p.q;
p and q are two prime numbers;
(b). delivering all the cipher versions of the message individually to the destination unit in source routing mode, or hop-by-hop routing mode with a small time gap between every two consecutive cipher versions;
(c). collecting all the cipher versions at the destination unit;
(d). computing r number of values N.sub.1, N.sub.2, . . . , N.sub.r using r components d.sub.1, d.sub.2, . . . , d.sub.r of decrypting key, where;
N.sub.1=((M.sub.1).sup.(d.sub.1)) mod n N.sub.2=((M.sub.2).sup.(d.sub.2)) mod n . . . N.sub.r=((M.sub.r).sup.(d.sub.r)) mod n, where;
n is the same composite number as used for encryption;
(e). reproducing the original message M as follows;
M=(N.sub.1).(N.sub.2) . . . (N.sub.r) mod n, where;
n is the same composite number as used for encryption. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 15)
-
-
13. A system for sending messages over a communications channel, comprising any of the following two options:
-
(a). an encoder to transform a message M into two or more cipher versions M.sub.1, M.sub.2, . . . , M.sub.r as follows;
M.sub.1=(M.sup.(e.sub.1+t)) mod n M.sub.2=(M.sup.(e.sub.2+t)) mod n . . . M.sub.r (M.sup.(e.sub.r+t)) mod n, where;
t is a random number generated on encrypting machine;
e.sub.1, e.sub.2, . . . , e.sub.r are encrypting key components computed according to the relations;
(e.sub.1).(d.sub.1)+(e.sub.2).(d.sub.2)+ . . . +(e.sub.r).(d.sub.r)=(k.sub.1).(p−
1).(q−
1)+1and (d.sub.1)+(d.sub.2)+ . . . +(d.sub.r)=(k.sub.2).(p−
1).(q−
1);
p and q are prime numbers, and n=p.q;
k.sub.1 and k.sub.2 are suitable integers;
(d.sub.1), (d.sub.2), . . . , (d.sub.r) are components of the other key used by the recipient for decrypting the cipher versions into the original message;
a decoder coupled to receive the cipher versions M.sub.1, M.sub.2, . . . , M.sub.r from the communications channel and to transform them back to the original message M, where M is a function of M.sub.1, M.sub.2, . . . , M.sub.r and computed as follows;
N.sub.1=((M.sub.1).sup.(d.sub.1)) mod n N.sub.2=((M.sub.2).sup.(d.sub.2)) mod n . . . N.sub.r=((M.sub.r).sup.(d.sub.r)) mod n M=(N.sub.1).(N.sub.2) . . . (N.sub.2) mod n. (b). an encoder to transform a message M into two or more cipher versions M.sub.1, M.sub.2, . . . , M.sub.r as follows;
M.sub.1=M.sup.(e.sub.1) mod n M.sub.2=M.sup.(e.sub.2) mod n . . . M.sub.r=M.sup.(e.sub.r) mod n, where;
e.sub.1, e.sub.2, . . . , e.sub.r are encrypting key components computed according to the following relation and conditions;
(e.sub.1).(d.sub.1)+(e.sub.2).(d.sub.2)+ . . . +(e.sub.r).(d.sub.r)=(k.sub.1).(p−
1).(q−
1)+1 and each of the values (e.sub.1), (e.sub.2), . . . , (e.sub.r) has a common factor with (p−
1).(q−
1), but there is no common factor for all the values (e.sub.1), (e.sub.2), . . . , (e.sub.r), and (p−
1).(q−
1), where;
p and q are two prime numbers;
n=p.q;
k.sub.1 is a suitable integer; and
(d.sub.1), (d.sub.2), . . . , (d.sub.r) are decrypting key components used by the recipient for decrypting the cipher versions into the original message;
a decoder coupled to receive the cipher versions M.sub.1, M.sub.2, . . . , M.sub.r from the communications channel and to transform them back to the original message M, where M is a function of M.sub.1, M.sub.2, . . . , M.sub.r and computed as follows;
N.sub.1=((M.sub.1).sup.(d.sub.1)) mod n N.sub.2=((M.sub.2).sup.(d.sub.2)) mod n . . . N.sub.r=((M.sub.r).sup.(d.sub.r)) mod n M=(N.sub.1).(N.sub.2) . . . (N.sub.r) mod n.
-
-
14. A computer-readable medium having computer-executable instructions causing the computer to compute the following:
key components (e.sub.1), (e.sub.2), . . . , (e.sub.r) and (d.sub.1), (d.sub.2), . . . , (d.sub.r) according to the relations as follows;
(e.sub.1).(d.sub.1)+(e.sub.2).(d.sub.2)+ . . . +(e.sub.r).(d.sub.r)=(k.sub.1).(p−
1).(q−
1)+1 and(d.sub.1)+(d.sub.2)+ . . . +(d.sub.r)=(k.sub.2).(p−
1).(q−
1), where;
p and q are prime numbers; and
k.sub.1 and k.sub.2 are suitable integers;
cipher versions of the original message M as follows;
M.sub.1=(M.sup.(e.sub.1+t)) mod n M.sub.2=(M.sup.(e.sub.2+t)) mod n . . . M.sub.r=(M. sup.(e.sub.r+t))mod n, where;
t is a random number generated on encrypting machine and discarded after encryption is complete. original message as follows;
N.sub.1=((M.sub.1).sup.(d.sub.1)) mod n N.sub.2=((M.sub.2).sup.(d.sub.2)) mod n . . . N.sub.r=((M.sub.r).sup.(d.sub.r)) mod n M=(N.sub.1).(N.sub.2) . . . (N.sub.r) mod n
Specification