Method for enhancing security of public key encryption schemas
View Patent ↗There exist numerous public key probabilistic encryption algorithms. Most of these algorithms do not have a maximum security level against someone capable of chosen ciphertext attacks. The disclosed method provides a construct to enhance the security of any public key probabilistic or deterministic encryption algorithm to achieve an optimal security level.
1. A public key encryption method comprising the following steps:
a) generating a random number r,
b) Applying a hash function F to a message M and to the random number r in order to obtain a first bit string s;
c) Applying a hash function H to s and performing an Exclusive OR of the result with r in order to obtain a second bit string t;
d) Defining an intermediate message w=s∥t, where ∥ denotes the concatenation of two bit strings;
e) Applying a public key probabilistic encryption algorithm EP to the intermediate message w and to a random number u in order to obtain a first encrypted item c1, using a public key pk;
f) Applying a hash function G to w and c1 in order to obtain a key k;
g) Applying a secret key encryption algorithm ES to the message M using the key k in order to obtain a second encrypted item c2; and
h) Generating the encrypted message C=c1∥c2.
2. A public key decryption method corresponding to the public key encryption method according to claim 1 , comprising the following steps:
i) Splitting the encrypted message C into c1 and c2;
j) Applying to c1 a decryption algorithm EP −1 corresponding to the encryption algorithm EP, using a private key sk that corresponds to the public key pk, in order to obtain the intermediate message w=s∥t,
k) Applying the hash function G to w and c1 in order to obtain k;
l) Applying the decryption algorithm ES −1 corresponding to the encryption algorithm ES to the encrypted message c2 using the key k in order to obtain the message M;
m) Applying the hash function H to s and performing an Exclusive OR with t in order to obtain r,
n) Applying the hash function F to the message M and to the random number r in order to obtain s′;
o) Verifying that s′=s;
If s′ and s are different, rejecting the encrypted message C;
Otherwise, going to step p;
p) Returning the plain text message M.
3. A method according to claim 1 , wherein step d comprises calculating w=i∥s∥t or w=s∥i∥t or w=s∥t∥i, where i is any value which contains useful information.
4. A method according to claim 1 , implemented in a portable electronic object of the smart card type.
5. The method of claim 3 , wherein i contains information regarding the binary size of the message M.
6. The method of claim 3 , wherein i contains information regarding the identity of the entity which encrypted M and sent the message C.
7. A public key encryption method comprising the following steps:
generating a random number r;
Applying a hash function F to a message M and to the random number r in order to obtain a first bit string s;
Applying a hash function H to s and performing an Exclusive OR of the result with r in order to obtain a second bit string t;
Defining an intermediate message w=s∥t, where ∥ denotes the concatenation of two bit strings;
Applying a public key deterministic encryption algorithm EP to the intermediate message w in order to obtain a first encrypted item c1, using a public key pk;
Applying a hash function G to w and c1 in order to obtain a key k;
Applying a secret key encryption algorithm ES to the message M using the key k in order to obtain the a second encrypted item c2; and
Generating an encrypted message C=c1∥c2.
8. A public key decryption method corresponding to the public key encryption method according to claim 7 , comprising the following steps:
i) Splitting the encrypted message C into c1 and c2;
j) Applying to c1 a decryption algorithm EP −1 corresponding to the encryption algorithm EP, using a private key sk that corresponds to the public key pk, in order to obtain the intermediate message w=s∥t;
k) Applying the hash function G to w and c1 in order to obtain k;
l) Applying the decryption algorithm ES −1 corresponding to the encryption algorithm ES to the encrypted message c2 using the key k in order to obtain the message M;
m) Applying the hash function H to s and performing an Exclusive OR with t in order to obtain r;
n) Applying the hash function F to the message M and to the random number r in order to obtain s′;
o) Verifying that s′=s;
If s′ and s are different, rejecting the encrypted message C;
Otherwise, going to step p;
p) Returning the plain text message M.
9. A method according to claim 7 , wherein step d comprises calculating w=i∥s∥t or w=s∥i∥t or w=s∥t∥i, where i is any value which contains useful information.
10. The method of claim 9 , wherein i contains information regarding the binary size of the message M.
11. The method of claim 9 , wherein i contains information regarding the identity of the entity which encrypted M and sent the message C.
12. A method according to claim 9 , implemented in a portable electronic object of the smart card type.
13. A method comprising the following steps:
a) generating a random number r;
b) Applying a hash function F to a message M and to the random number r in order to obtain a first bit string s;
c) Applying a hash function H to s and performing an Exclusive OR of the result with r in order to obtain a second bit string t;
d) Defining an intermediate message w=s∥t, where ∥ denotes the concatenation of two bit strings;
e) Applying a public key probabilistic encryption algorithm EP to the intermediate message w and to a random number u in order to obtain a first encrypted item c1, using a public key pk;
f) Applying a hash function G to w and c1 in order to obtain a key k;
g) performing an Exclusive OR operation between the message M to be encrypted and the key k, in order to obtain a second encrypted item c2; and
h) Generating the encrypted message C=c1∥c2.
14. A public key encryption method comprising the following steps:
generating a random number r;
Applying a hash function F to a message M and to the random number r in order to obtain a first bit string s;
Applying hash function H to s and performing an Exclusive OR of the result with r in order to obtain a second bit string t;
Defining an intermediate message w=s∥t, where ∥ denotes the concatenation of two bit strings;
Applying a public key deterministic encryption algorithm EP to the intermediate message w in order to obtain a first encrypted item c1, using a public key pk;
Applying a hash function G to w and c1 in order to obtain a key k;
performing an exclusive OR operation between the message M to be encrypted and the key k, in order to obtain a second encrypted item c2; and
Generating an encrypted message C=c1∥c2.
15. A method according to claim 14 , implemented in a portable electronic object of the smart card type.