CRYPTOGRAPHIC MESSAGE SIGNATURE METHOD HAVING STRENGTHENED SECURITY, SIGNATURE VERIFICATION METHOD, AND CORRESPONDING DEVICES AND COMPUTER PROGRAM PRODUCTS

• US 20110064216A1
• Filed: 09/15/2010
• Published: 03/17/2011
• Est. Priority Date: 09/15/2009
• Status: Abandoned Application

• Current Assignee: Compagnie Industrielle et Financiere D'Ingenierie "Ingenico"
• Original Assignee: Compagnie Industrielle et Financiere D'Ingenierie "Ingenico"
• Inventors: Pointcheval, David, Naccache, David, Polechtchouk, Pavel
• Application Number:
  US12/882,838
• Publication Number:
  US 20110064216A1
• Time in Patent Office: Days
• US Class Current: 380/44
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A cryptographic message signature method are provided, which have strengthened security. The method implements two sets of signature algorithms SA1={K1, S1, V1} and SA2={K2, S2, V2}, where Ki, Si and Vi are key generation algorithms, signature generation algorithms and signature verification algorithms, respectively. The method includes: a step of generating permanent keys using the algorithm K1, delivering a pair of private and public keys {sk1, pk1}; and, for at least one message m to be signed: a signature step including sub-steps. The sub-steps include: receipt of the message m to be signed; generation of an ephemeral key pair {sk2,pk2} using the algorithm K2; calculation, by the signature algorithm S2, of the signature s2 of the message m by the private key sk2; calculation, by the signature algorithm S1, of the signature c1 of the public key pk2 by the private key sk1; and providing the strengthened signature {s2, c1, pk2}.

Claims

1. A cryptographic message signature method having strengthened security, comprising:

implementing two sets of signature algorithms SA1={K1, S1, V1} and SA2={K2, S2, V2}, where K1 and K2 are key generation algorithms, S1 and S2 are signature generation algorithms and V1 and V2 are signature verification algorithms, and wherein the step of implementing includes;

a step of generating permanent keys using the algorithm K1, delivering a pair of private and public keys {sk1, pk1};

and, for at least one message m to be signed;

a signature step including the following sub-steps;

receipt of said message m to be signed;

generation of an ephemeral key pair {sk2,pk2} using the algorithm K2, where sk2 is a private key and pk2 is a public key;

calculation, by the signature algorithm S2, of a signature s2 of the message m by the private key sk2;

calculation, by the signature algorithm S1, of a signature c1 of the public key pk2 by the private key sk1; and

providing the strengthened signature {s2, c1, pk2}.

2. The cryptographic message signature method having strengthened security of claim 1, wherein said signature step is implemented for each message m to be signed, or periodically according to a desired level of security.

3. The cryptographic message signature method having strengthened security of claim 1, wherein said signature algorithm S2 implements a hash function and said providing step provides at least one random number r, which is used by said hash function.

4. The cryptographic message signature method having strengthened security of claim 1, wherein the algorithms K1 and K2, S1 and S2 and/or V1 and V2 are identical in pairs.

5. The cryptographic message signature method having strengthened security of claim 1, wherein SA1 and/or SA2 include algorithms of the RSA type (for “

Rivest Shamir Adleman”

).

6. The cryptographic message signature method having strengthened security of claim 1, wherein SA1 and/or SA2 include algorithms of the DSA type (for “

Digital Signature Algorithm”

).

7. The cryptographic message signature method having strengthened security of claim 3, wherein the method includes a step of generating a pair of public and secret keys {skh, pkh} by a generation algorithm Kh implemented by one of the verification algorithms V1 or V2, and said signature step implements a hash function H, known by the verification algorithms V1 and V2, such that h=Hpkh(m;

r), where r is a random number.

8. The cryptographic message signature method having strengthened security of claim 7, wherein said hash function is of the “

chameleon”

type.

9. The cryptographic message signature method having strengthened security of claim 8, wherein said strengthened signature corresponds to triplet (S2(h), c1, pk2).

10. A cryptographic message signature verification method having strengthened security, wherein the method comprises:

implementing two signature verification algorithms V1 and V2, and a joint verification phase for signatures generated according to the cryptographic message signature method having strengthened security according to claim 1,

said verification phase including the following steps for a signed message m to be verified;

receipt of a strengthened signature triplet {s2, c1, pk2};

verification, using said verification algorithm V2 and said public key pk2, of the signature s2 of the message m, thereby delivering a first positive or negative result;

verification, using said verification algorithm V1 and a public key pk1, of the signature c1 of the public key pk2, thereby delivering a second positive or negative result;

delivering a positive result if the first and second results are positive.

11. The cryptographic message signature verification method having strengthened security of claim 10, wherein said receiving step further includes the receipt of at least one random number r.

12. A cryptographic message signature device having strengthened security, wherein the device comprises:

means for implementing two sets of signature algorithms SA1={K1, S1, V1} and SA2={K2, S2, V2}, where K1 and K2 are key generation algorithms, S1 and S2 are signature generation algorithms and V1 and V2 are signature verification algorithms, and wherein the means for implementing comprises;

means for generating permanent keys, using the algorithm K1, thereby delivering a pair of private and public keys {sk1, pk1};

and, for at least one message m to be signed;

signature means including;

means for receiving of said message m to be signed;

means for generating of an ephemeral key pair {sk2,pk2} using the algorithm K2, where sk2 is a private key and pk2 is a public key;

means for calculating, by the signature algorithm S2, a signature s2 of the message m by the private key sk2;

means for calculating, by the signature algorithm S1, a signature c1 of the public key pk2 by the private key sk1;

means for providing the strengthened signature {s2, c1, pk2}.

13. A cryptographic message signature verification device having strengthened security, wherein the device comprises:

means for implementing two signature verification algorithms V1 and V2, and joint verification means for signatures generated by the cryptographic message signature device having strengthened security of claim 12, said means for implementing comprising, for a signed message m to be verified;

means for receiving a strengthened signature triplet {s2, c1, pk2}};

means for verifying the signature s2 of the message m, using said verification algorithm V2 and said public key pk2, thereby delivering a first positive or negative result;

means for verifying the signature c1 of the public key pk2, using said verification algorithm V1 and a public key pk1, thereby delivering a second positive or negative result;

means for delivering a positive result if the first and second results are positive.

14. A cryptographic message signature verification system having strengthened security, which includes a cryptographic signature device of claim 12 and a cryptographic signature verification device of claim 13.

15. A computer program product recorded on a computer readable medium and executable by a processor, wherein the product includes program code instructions for implementing a cryptographic message signature method having strengthened security, wherein the method comprises:

implementing two sets of signature algorithms SA1={K1, S1, V1} and SA2={K2, S2, V2}, where K1 and K2 are key generation algorithms, S1 and S2 are signature generation algorithms and V1 and V2 are signature verification algorithms, and wherein the step of implementing includes;

a step of generating permanent keys using the algorithm K1, delivering a pair of private and public keys {sk1, pk1};

and, for at least one message m to be signed;

a signature step including the following sub-steps;

receipt of said message m to be signed;

generation of an ephemeral key pair {sk2,pk2} using the algorithm K2, where sk2 is a private key and pk2 is a public key;

calculation, by the signature algorithm S2, of a signature s2 of the message m by the private key sk2;

calculation, by the signature algorithm S1, of a signature c1 of the public key pk2 by the private key sk1; and

providing the strengthened signature {s2, c1, pk2}.

16. A computer program product recorded on a computer readable medium and executable by a processor, wherein the product includes program code instructions for implementing a cryptographic message signature verification method having strengthened security, wherein the method comprises:

implementing two signature verification algorithms V1 and V2, and a joint verification phase for signatures generated according to cryptographic message signature method,

said verification phase including the following steps for a signed message m to be verified;

receipt of a strengthened signature triplet {s2, c1, pk2}, where pk2 is a public key, s2 is a signature of the message m using a private key sk2, c1 is a signature of public key pk2 by a private key sk1;

verification, using said verification algorithm V2 and said public key pk2, of the signature s2 of the message m, thereby delivering a first positive or negative result;

verification, using said verification algorithm V1 and a public key pk1, of the signature c1 of the public key pk2, thereby delivering a second positive or negative result;

delivering a positive result if the first and second results are positive.