Cryptographic method comprising secure modular exponentiation against hidden-channel attacks, cryptoprocessor for implementing the method and associated chip card
View Patent ↗A cryptographic method carries out a modular exponentiation of the type C=A<B1> mod N, where A is an operand, B1 is a first exponent, N is a modulus and C is a result. The method includes the steps of masking the operand A by a number s, carrying out a modular exponentiation of the masked operand by the exponent B1, and demasking the result of the exponentiation, by removing a contribution from the random number s from the result of the exponentiation. During the step of masking the operand A, the operand A is multiplied by a parameter of the form K<s.B2>, where K is a constant and B2 is a second exponent such that B1.B2=1 mod N. The method is implemented preferably by using a Montgomery multiplier. The preferred choice for the constant K is K=2 p , p being an integer lying between 0 and n, n being an upper bound of the size of the modulus N and conventionally depending on the choice of implementation of the Montgomery multiplication.
1. Cryptographic method during which, in order to carry out a modular exponentiation of type C=A B1 mod N, where A is an operand comprising a message on which a cryptographic operation is being performed, B1 is a first exponent, N is a modulus, and C is a result, comprising the following steps:
masking, by a cryptographic device, the operand A by a random number s,
carrying out, by the cryptographic device, a modular exponentiation of the masked operand by the exponent B1, then
demasking, by the cryptographic device, the result of the exponentiation, by removing a contribution from the random number s from the result of the exponentiation, to thereby obtain a signed, encrypted or decrypted version of said message,
wherein during the step of masking the operand A, the operand A is multiplied by a parameter in the form K s.B2 , where K is a constant and B2 is a second exponent such that B1.B2=1 mod φ(N).
2. Method according to claim 1 , wherein the step of masking the operand A comprises the following substeps:
carrying out, by the cryptographic device, a first Montgomery exponentiation of the constant K by the result of multiplying the random number s by the second exponent B2, then
carrying out, by the cryptographic device, a Montgomery multiplication of the result of the first Montgomery exponentiation by the operand A to produce a masked operand A′ (A′=K s.B2 ).
3. Method according to claim 2 , wherein the exponentiation step comprises the following substep:
carrying out, by the cryptographic device, a second Montgomery exponentiation of the masked operand A′ by the first exponent B1 to produce a masked result C′.
4. Method according to claim 3 , wherein the step of demasking the result of the exponentiation comprises the following substeps:
carrying out, by the cryptographic device, a third Montgomery exponentiation to calculate the parameter K −s ,
carrying out, by the cryptographic device, a Montgomery multiplication of the masked result C′ by K −s .
5. Method according to claim 2 , wherein the constant K is equal to 2 p , p being an integer between 0 and n, n being an upper bound of the size of the modulus N.
6. Method according to claim 5 , wherein the constant K is equal to 2 n .
7. Method according to claim 5 , comprising the following steps and subsets:
initialisation:
choosing an integer j and calculating the constant K=R/2 j ,
choosing a random number s and multiplying it by B2 to obtain s1,
calculating R 2 , R being a Montgomery constant equal to 2 n ,
masking A as A′,
calculating the mask K s1
calculating T1=Mgt(K,R 2 ,N)=K*R mod N
calculating U1=MgtExp(T1,s1,N)=K s1 *R mod N
masking A as A′
calculating M1=Mgt(U1,A,N)=K s1 .A mod N
calculating C′=A′ B1 mod N
calculating M2=Mgt(M1,R2,N)=K s1 .A.R mod N
calculating U2=MgtExp(M1,B1,N)=A B1 .K s .R mod N
finding C based on C′
calculating K −s
calculating I1=Mgt(N−2 j ,N−1,N)=Mgt(2 j ,1,N)=K −1 mod N
calculating I2=Mgt(I1,R 2 ,N)=K −1 .R mod N
calculating V=MgtExp(I2,S,N)=K −s .R mod N
calculating C=C′.K −s
calculating U3=Mgt(U2,V,N)=A B1 .R mod N
calculating U4=Mgt(U3,1,N)=A B1 mod N.
8. Method according to claim 6 , comprising the following steps and substeps:
initialisation
choosing the random number s and calculating s1=s.B2+1
calculating R 2 ,
masking A as A′
calculating the mask R s1
calculating U1=MgtExp(R 2 ,S1,N)=R s1 .R mod N
masking A as A′
calculating M1=Mgt(U1,A,N)=R s1 *A mod N=R s.B2 .A.R mod N
calculating C′=A′ B1 mod N
calculating U2=Mgt(M1,B1,N)=A B1 .R s .R mod N
finding C based on C′
calculating R −(s+1)
calculating V=MgtExp(1,s+1,N)=R −(s+1) .R mod N
calculating C=C′.K −(s+1)
calculating U3=Mgt(U2,V,N)=A B1 mod N.
9. Method according to claim 1 , wherein the steps of masking, modular exponentiation and demasking are modified as follows:
masking, by the cryptographic device, the operand A (A′=K u.B2 *A) by a number u equal to twice the number s, multiplying the operand A by a parameter K u.B2 ;
carrying out, by the cryptographic device, a modular exponentiation of the operand masked by the exponent B1, broken down according to the Chinese Remainder Theorem into the following substeps:
Cp=(A mod p) BP 1 mod p,
C1=(A mod 1) B q1 mod q
C=Cq+q*(Iq*(Cp−Cq) mod p) mod N
damasking, by the cryptographic device, the result of the exponentiation (C′), multiplying the result of the exponentiation (C′) by K −2s mod N,
where p and q are two integers which multiplied give the result of N (p*q=N), Bp1 is equal to B1 modulus p−1, Bq1 is equal to B1 mod q−1, Iq is equal to q −1 mod p.
10. Method according to claim 9 , wherein K is equal to 2r, where r is the largest size from among the size of p and the size of q.
11. A cryptoprocessor device comprising a Montgomery multiplier configured to implement a method to carry out a modular exponentiation of type C=A B1 mod N, where A is an operand comprising a message on which a cryptographic operation is being performed, B1 is a first exponent, N is a modulus, and C is a result, comprising the following steps:
masking the operand A by a random number s,
carrying out a modular exponentiation of the masked operand by the exponent B1,
then demasking the result of the exponentiation, by removing a contribution from the random number s from the result of the exponentiation, to thereby obtain a signed, encrypted or decrypted version of said message,
wherein during the step of masking the operand A, the operand A is multiplied by a parameter in the form K s.B2 , where K is a constant and B2 is a second exponent such that B1.B2=1 mod φ(N),
wherein the step of masking the operand A comprises the following substeps:
carrying out a first Montgomery exponentiation of the constant K by the result of multiplying the random number s by the second exponent B2, then
carrying out a Montgomery multiplication of the result of the first Montgomery exponentiation by the operand A to produce a masked operand A′(A′=K s.B2 ).
12. The cryptoprocessor device of claim 11 wherein the cryptoprocessor device is comprised within a Chip card.
13. Method according to claim 1 , wherein the cryptographic device is a chip card.