Method of verifying integrity of a pair of cryptographic keys and cryptographic device

Abstract

Disclosed is a method of verifying integrity of a pair of public and private cryptographic keys within the additive group of the integers modulo N, with N being the product of two primary numbers p and q, the method including: calculating a candidate private exponent d′ corresponding to a private exponent d of the private key; and executing a test of integrity. The test of integrity includes a step for verifying the coherence of the candidate private exponent d′ with respect to a public exponent e of the public key and to the numbers p and q, the verification step involving a first multiple modulo of the public exponent e of the public key and a second multiple modulo of the public exponent e of the public key.

Claims

1. A verification method of verifying integrity of a pair of public and private keys within a group of integers, the groups of integers being an additive group of integers modulo N, with N being the product of two primary numbers p and q, the method comprising: calculating an exponent that is a candidate private exponent d′ corresponding to an exponent d, the exponent d being a private exponent of said private key; executing a test of integrity comprising processing an initial test data value using one of: (i) a public exponent e of the public key and (ii) the candidate private exponent d′ to obtain a first result, processing the first result using the other of: (i) the public exponent e of the public key and (ii) the candidate private exponent d′ to obtain a second result, comparing the initial test data value with the second result, and verifying coherence of the candidate private exponent d′ with respect to the public exponent e of said public key and the numbers p and q, the verifying using a first multiple of the public exponent e of the public key, the first multiple being modulo (p−1), and a second multiple of the public exponent e of the public key, the second multiple being modulo (q−1); and determining, using the first multiple of the public exponent e of the public key and the second multiple of the public exponent e of the public key, that the pair formed with the public key and the private key having the candidate private exponent d′ is corrupted.

2. The verification method according to claim 1, wherein the verifying includes: verifying that the product modulo (p−1) of (i) the candidate private exponent d′ and (ii) the public exponent e of the public key is equal to 1, and verifying that the product modulo (q−1) of (i) the candidate private exponent d′ and (ii) the public exponent e of the public key is equal to 1.

3. The verification method according to claim 1, wherein the calculating the candidate private exponent d′ comprises: calculating a first value d.sub.p using the public exponent e of the public key modulo p and calculating a second value d.sub.q involving the public exponent e of the public key modulo q, and the verifying comprises: verifying that the candidate private exponent d′ modulo (p−1) is congruent to the first value d.sub.p, verifying that the candidate private exponent d′ modulo (q−1) is congruent to the second value d.sub.q, verifying that the product modulo (p−1) of: (i) the first value d.sub.p and (ii) the public exponent e of the public key is equal to 1, and verifying that the product modulo (q−1) of: (i) the second value d.sub.q and (ii) the public exponent e of the public key is equal to 1.

4. A testing method of testing security of an electronic device with regard to an attack, the testing method comprising: the verification method according to claim 1, said device implementing generation of the public key and the private key within the additive group of the integers modulo N, such that: 1<e<Φ(N), with e and Φ) (N) being mutually primary and Φ(N)=(p−1).Math.(q−1), and d.Math.e=1 mod λ(N), λ(N) being the least common multiplier between p−1 and q−1; and perturbation of calculation of the value λ(N) to obtain, in place of the value λ(N), a value λ′(N)=λ(N)/α, with α dividing λ(N), said perturbation leading to calculating the candidate private exponent d′, in place of the private exponent d, such that d′.Math.e=1 mod λ(N)/α.

5. A non-transitory computer-readable medium on which is stored a computer program comprising instructions to carry out the verification method according to claim 1 when the computer program is loaded and executed by a processor of a device.

6. A device comprising: a processor configured to implement the verification method according to claim 1.

7. A portable electronic entity comprising: the device according to claim 6.

8. A testing method of testing security of an electronic device with regard to an attack, the testing method comprising: the verification method according to claim 2, said device implementing generation of the public key and the private key within the additive group of the integers modulo N, such that: 1<e<Φ(N), with e and Φ(N) being mutually primary and Φ(N)=(p−1).Math.(q−1), and d.Math.e=1 mod λ(N), λ(N) being the least common multiplier between p−1 and q−1; and perturbation of calculation of the value λ(N) to obtain, in place of the value λ(N), a value λ′(N)=λ(N)/α, with α dividing λ(N), said perturbation leading to calculating the candidate private exponent d′, in place of the private exponent d, such that d′.Math.e=1 mod λ(N)/α.

9. A testing method of testing security of an electronic device with regard to an attack, the testing method comprising: the verification method according to claim 3, said device implementing generation of the public key and the private key within the additive group of the integers modulo N, such that: 1<e<Φ(N), with e and Φ(N) being mutually primary and Φ(N)=(p−1).Math.(q−1), and d.Math.e=1 mod λ(N), λ(N) being the least common multiplier between p−1 and q−1; and perturbation of calculation of the value λ(N) to obtain, in place of the value λ(N), a value λ′(N)=λ(N)/α, with α dividing λ(N), said perturbation leading to calculating the candidate private exponent d′, in place of the private exponent d, such that d′.Math.e=1 mod λ(N)/α.

10. A non-transitory computer-readable medium on which is stored a computer program comprising instructions to carry out the verification method according to claim 2 when the computer program is loaded and executed by a processor of a device.

11. A non-transitory computer-readable medium on which is stored a computer program comprising instructions to carry out the verification method according to claim 3 when the computer program is loaded and executed by a processor of a device.

12. A non-transitory computer-readable medium on which is stored a computer program comprising instructions to carry out the verification method according to claim 4 when the computer program is loaded and executed by a processor of a device.

13. A non-transitory computer-readable medium on which is stored a computer program comprising instructions to carry out the verification method according to claim 8 when the computer program is loaded and executed by a processor of a device.

14. A non-transitory computer-readable medium on which is stored a computer program comprising instructions to carry out the verification method according to claim 9 when the computer program is loaded and executed by a processor of a device.

15. Cryptographic A device comprising: a processor configured to implement the verification method according to claim 2.

16. A device comprising: a processor configured to implement the verification method according to claim 3.

17. A device comprising: a processor configured to implement the verification method according to claim 4.

18. A device comprising: a processor configured to implement the verification method according to claim 8.

19. A device comprising: a processor configured to implement the verification method according to claim 9.

Description

BRIEF DESCRIPTION OF THE FIGURES

(1) Other features and advantages of the invention will furthermore become apparent in the description hereinafter, illustrated by the appended figures which illustrate non-limiting exemplary embodiments of it. In the figures:

(2) FIG. 1 illustrates a method of verifying integrity of keys according to a first embodiment of the invention;

(3) FIG. 2 illustrates a method of verifying integrity of keys according to a second embodiment of the invention; and

(4) FIG. 3 illustrates schematically a device according to embodiments of the invention.

DETAILED DESCRIPTION OF THE INVENTION

(5) FIG. 1 illustrates a method of verifying integrity of keys according to a first embodiment of the invention.

(6) In this example, a public cryptographic key (e, N) and a private cryptographic key (d, N) are generated such that: N=p.Math.q, with p and q being primary numbers, 1<e<Φ(N) and e and Φ(N) are mutually primary (gcd(e, Φ(N))=1), with Φ(N)=(p−1).Math.(q−1) (Φ being the Euler's totient function, or just “totient”), and d.sub.p=e.sup.−1 mod p and d.sub.q=e.sup.−1 mod q; and d=CRT(d.sub.p,d.sub.q), where CRT is the result of the application of the ‘Chinese Remainder Theorem’.

(7) During a first step 100, a message m (m belonging to Z.sub.N, the additive group of the integers modulo N) is encrypted with the public exponent e so as to obtain a first encrypted message c=m.sup.e mod N.

(8) Subsequently, during a step 102, the encrypted message c is decrypted with the private exponent d so as to obtain a decrypted message m′=c.sup.d mod n.

(9) It is subsequently verified, during a step 103, whether the initial message m and the decrypted message are the same (m′=m).

(10) If this is not the case (NOK), it is determined during the step 104 that the pair of keys generated is corrupted.

(11) If, on the other hand, the initial message m and the decrypted message are the same (OK), the decrypted message m′ is encrypted, during a step 105, with the public exponent e so as to obtain a second encrypted message c′=(m′).sup.e mod n.

(12) It is subsequently verified, during a step 106, whether the first encrypted message c and the second encrypted message c′ are the same (c′=c).

(13) If this is not the case (NOK), it is determined, during the step 107, that the pair of keys generated is corrupted.

(14) If, on the other hand, the first encrypted message c and the second encrypted message c′ are the same (OK), two other tests are implemented (step 108), in order to check that the private exponent d and the public exponent e verify the following relationships:
d.Math.e mod(p−1)=1, and
d.Math.e mod(q−1)=1.

(15) According to the well-known Chinese remainder theorem, the relationship d.Math.e=1 mod λ(N) is equivalent to the system of equations tested at the step 108, as long as the values p−1 and q−1 are uncorrupted, which is the case at this stage of the method because the corruption of these values would have been detected during the preceding steps 100 to 107.

(16) This system of equations allows a situation in which a bad private exponent d′=e.sup.−1 mod (λ(N)/α) has been calculated in place of the private exponent d=e.sup.−1 mod λ(N) to be detected. Indeed, since the value α divides λ(N), the product of the value α and the largest common divisor between p−1 and q−1 do not divide both p−1 and q−1. Thus, at least one of the relationships in the step 108 is not verified when d′ is calculated in place of d. It is noted here that the order of the tests carried out in the step 108 does not matter.

(17) If these two relationships are verified (OK), it is determined, during the step 109, that the test of integrity is positive.

(18) Otherwise (NOK), it is determined, during the step 110, that the pair of keys generated is corrupted.

(19) This first embodiment allows the method to approach a detection rate of 100% by means of only two additional modular multiplications with respect to the modular multiplications implemented during a test of integrity according to the standard FIPS 140-λ. Thus, the efficiency of this solution is 10,000 times better than that of the solution described in the patent FR 1362833 where the test of integrity of the standard FIPS 140-2 is repeated several times, and which therefore requires many more modular multiplications in order to achieve a satisfactory detection rate.

(20) FIG. 2 illustrates a method of verifying integrity of keys according to a second embodiment of the invention.

(21) The steps 100 to 107 are identical to the steps of the first embodiment.

(22) If the test 106 reveals that the first encrypted message c and the second encrypted message c′ are the same (c′=c), then the method continues with a step 208 during which four tests are implemented, in order to verify that the value of the private exponent d and the public exponent e verify all of the following relationships:
d mod(p−1)=d.sub.p
d mod(q−1)=d.sub.q
d.sub.p.Math.e mod(p−1)=1, and
d.sub.q.Math.e mod(q−1)=1.

(23) It is noted here that the order of the tests carried out during the step 208 does not matter.

(24) If these relationships are verified (OK), it is determined during the step 209 that the test of integrity is positive.

(25) Otherwise (NOK), it is determined, during the step 210, that the pair of keys generated is corrupted.

(26) This second embodiment allows the coherence between d.sub.p(respectively d.sub.q) and e immediately after having generated them to be tested, thus allowing the elimination of the value of e from the memory prior to generating the values N and d. The use of the memory is therefore optimized.

(27) In addition, just like the first embodiment, this second embodiment allows the method to approach a detection rate of 100% by means of only two additional modular multiplications with respect to the modular multiplications implemented during a test of integrity according to the standard FIPS 140-λ. Thus, the efficiency of this solution is 10,000 times better than that of the solution described in the patent FR 1362833, where the test of integrity of the standard FIPS 140-2 is repeated several times and hence requires many more modular multiplications in order to achieve a satisfactory detection rate.

(28) FIG. 3 illustrates schematically a device according to embodiments.

(29) The device 30 in FIG. 3 comprises a memory unit 31 (MEM). This memory unit comprises a RAM memory for temporarily storing calculation data used during the implementation of a method according to the invention, according to various embodiments. The memory unit furthermore comprises a non-volatile memory (for example of the EEPROM type) for storing for example a computer program, according to one embodiment, for its execution by a processor (not shown) of a processing unit 32 (PROC) of the device.

(30) The device furthermore comprises a communications unit 33 (COM), for example for exchanging data with another device according to embodiments. The exchanges of data between devices may take place according to the APDU (acronym for “Application Protocol Data Unit”) protocol such as defined in the standard ISO 7816 part 4.

(31) The communications unit may thus comprise an input/output interface capable of exchanging data according to this protocol. The data may be exchanged via APDU commands and responses to this type of command.

(32) A device according to embodiments may conform to the standard ISO7816. This device may for example be a smart card or a secure element.

(33) A device according to embodiments is for example an integrated circuit.

(34) The present invention has been described and illustrated in the present detailed description with reference to the appended figures. However, the present invention is not limited to the embodiments presented. Other variants, embodiments and combinations of features may be deduced and implemented by those skilled in the art upon reading the present description and the appended figures.

(35) For example, according to embodiments, the steps 108 and subsequent steps, respectively 208 and subsequent steps, may be implemented subsequent to the following signature verification steps: the message m is signed with the private key so as to obtain a signature s=(m).sup.d mod N, (or alternatively s=(H(m)).sup.d, H being a hash function), a value h′ is calculated as h′=s.sup.e mod N, and it is verified that the value h′ thus calculated and the message m are the same (or alternatively that the value h′ and the condensate of the message by the hash function are the same (h′=H(m))).

(36) According to embodiments, the steps 108 and subsequent steps or 208 and subsequent steps are implemented following the test of integrity described in the US standard FIPS 140-2 published by NIST (acronym for “National institute of Standards and Technology”), and such as presented for example in the document “Donald L Evans et al.: “FIPS PUB 140-2: SECURITY REQUIREMENTS FOR CRYPTOGRAPHIC MODULES”, FEDERAL INFORMATION PROCESSING STANDARDS PUBLICATION, 12 Mar. 2002”.

(37) These embodiments allow a detection rate of 100% to be approached by means of only a few additional modular multiplications with respect to the modular multiplications implemented during a test of integrity according to the standard FIPS 140-λ. Thus, the efficiency of this solution is much better than in a solution of the prior art consisting in repeating the test of integrity of the standard FIPS 140-2 numerous times.

(38) For example, the tests in the step 108 or 208 come after: at least a first step implementing one of the private or public keys and an initial test data value, said first step allowing a first result to be generated, at least a second step implementing at least said first result and the key not used during the at least a first step, said second step allowing a second result to be generated, and a comparison of said second result and of said initial test data value, the comparison being followed by the series of tests provided in the step 108 or 208.

(39) According to one particular example, the tests in the step 108 or 208 come after: at least a first step (for example one of the steps 100 or 102) for modular exponentiation of an initial test data value by one of the private or public keys, said first step allowing a first result to be generated, at least a second step (for example one of the steps 102 or 105) for modular exponentiation of said first result by the key not used during the at least a first step, said second step allowing a second result to be generated, and a comparison (for example either of the steps 103 or 106) of said second result and of said initial test data value, the comparison being followed by the series of tests provided at the step 108 or 208. In the claims, the term “comprising” does not exclude other elements or other steps. The indefinite article “a” does not exclude the plural. A single processor or several other units may be used for implementing the invention. The various features presented and/or claimed may be advantageously combined. Indeed, their presence in the description, or in different dependent claims, does not exclude the possibility of combining them. The reference signs should in no way be understood as limiting the scope of the invention.