Modular inversion that is protected against espionage
View Patent ↗In methods for determining, in a way that is protected against spying, the modular inverse b of a value a in relation to a module n for a cryptographic application, an auxiliary value β and an auxiliary module δ are determined at least depending on the value a, the module n and at least one masking parameter r, an auxiliary inverse β′ is determined as the modular inverse of the auxiliary value β in relation to the auxiliary module δ, and the modular inverse b is determined at least depending on the auxiliary inverse β′, the at least one masking parameter r, and the auxiliary value β and/or the auxiliary module δ. A computer program product and a portable data carrier have corresponding features. The invention provides a method for modular inversion, secured against spying, which is suitable for applications where security is critical, such as, e.g. cryptographic calculations on a portable data carrier.
1. A method for determining, in a way that is protected against spying, the modular inverse b of a value a in relation to a module n for a cryptographic application, comprising the steps:
a) determining an auxiliary value β and an auxiliary module δ, which are relatively prime to each other, at least depending on the value a, the module n and at least one masking parameter r in such a way that at least one of the following holds:
the auxiliary value β differs from the value a, and
the auxiliary module δ differs from the module n,
b) determining an auxiliary inverse β′ as the modular inverse of the auxiliary value β in relation to the auxiliary module δ, and
c) determining the modular inverse b at least depending on the following values:
the auxiliary inverse β′,
the at least one masking parameter r, and
at least one of the auxiliary value β and the auxiliary module δ,
wherein the modular inverse b is used to generate a secret private key for executing an RSA method, the secret private key being stored in a portable data storage.
2. The method according to claim 1 , wherein the at least one masking parameter r is randomly chosen.
3. The method according to claim 1 , wherein at least one of the value a and the module n is multiplied by the masking parameter r, and wherein the thereby obtained product has some influence on the calculation of at least one of the auxiliary value β and the auxiliary module δ.
4. The method according to claim 1 , wherein the determining of the auxiliary value β and the auxiliary module δ further takes place depending on at least one auxiliary parameter s, which has at the most an indirect influence on determining the inverse b.
5. The method according to claim 4 , wherein the at least one auxiliary parameter s is randomly chosen.
6. The method according to claim 4 wherein the auxiliary value β and the auxiliary module δ are determined in such a way that the equations ra=αn+β and sn=γa+δ are fulfilled for predetermined values α and γ.
7. The method according to claim 6 , wherein the inverse b is determined by evaluating the equation b=β′r+δ′γ mod n with δ′=(ββ′−1)/δ.
8. The method according to claim 4 , wherein the auxiliary value β and the auxiliary module δ are determined in such a way that the equations ra=αn+β and sn=γa+δ are fulfilled for values α and γ calculated in connection with the determining of the auxiliary value β and the auxiliary module δ.
9. The method according to claim 8 , wherein the inverse b is determined by evaluating the equation b=β′r+δ′γ mod n with δ′=(ββ′−1)/δ.
10. The method according to claim 4 , wherein the auxiliary value β and the auxiliary module δ are determined in such a way that the equations ra=αn+δ and sn=γa β are fulfilled for predetermined values α and γ.
11. The method according to claim 10 , wherein the inverse b is determined by evaluating the equation b=−(δ′r+β′γ) mod n with δ′=(ββ′−1)/δ.
12. The method according to claim 4 , wherein the at least one auxiliary parameter s has the same order of magnitude as the value a.
13. The method according to claim 4 , wherein the auxiliary value β and the auxiliary module δ are determined in such a way that the equations ra=αn+δ and sn=γa+β are fulfilled for values α and γ calculated in connection with the determining of the auxiliary value β and the auxiliary module δ.
14. The method according to claim 13 , wherein the inverse b is determined by evaluating the equation b=−(δ′r+β′γ) mod n with δ′=(ββ′−1)/δ.
15. The method according claim 4 , wherein at least one of the auxiliary value β and the auxiliary module δ is determined by a division with remainder in each case, so that at least one of the inequations 0≦β<n and 0≦δ<a is fulfilled.
16. The method according to claim 1 , wherein the at least one masking parameter r has the same order of magnitude as the module n.
17. The method according to claim 1 , wherein the cryptographic application is a key pair determination in one of an RSA encoding method and an RSA signature method.
18. The method according to claim 1 , wherein the portable data storage is one of a smart card and a chip module.
19. A computer-readable storage medium having a computer program stored thereon, the computer program including program commands to cause a processor to determine, in a way that is protected against spying, the modular inverse b of a value a in relation to a module n for a cryptographic application, the computer program causing the processor to implement functions of:
a) determining an auxiliary value β and an auxiliary module δ, which are relatively prime to each other, at least depending on the value a, the module n and at least one masking parameter r in such a way that at least one of the following properties holds:
the auxiliary value β differs from the value a, and
the auxiliary module δ differs from the module n,
b) determining an auxiliary inverse β′ as the modular inverse of the auxiliary value β in relation to the auxiliary module δ, and
c) determining the modular inverse b at least depending on the following values:
the auxiliary inverse β′,
the at least one masking parameter r, and
at least one of the auxiliary value β and the auxiliary module δ,
wherein the modular inverse b is used to generate a secret private key for executing an RSA method, the secret private key being stored in a portable data storage.
20. The computer-readable storage medium according to claim 19 , wherein the at least one masking parameter r is randomly chosen.
21. The computer-readable storage medium according to claim 19 , wherein the at least one masking parameter r has the same order of magnitude as the module n.
22. The computer-readable storage medium according to claim 19 , wherein at least one of the value a and the module n is multiplied by the masking parameter r, and wherein the thereby obtained product has some influence on the calculation of at least one of the auxiliary value β and the auxiliary module δ.
23. The computer-readable storage medium according to claim 19 , wherein the determining of the auxiliary value β and the auxiliary module δ further takes place depending on at least one auxiliary parameter s, which has at the most an indirect influence on determining the inverse b.
24. The computer-readable storage medium according to claim 23 , wherein the at least one auxiliary parameter s is randomly chosen.
25. The computer-readable storage medium according to claim 23 , wherein the at least one auxiliary parameter s has the same order of magnitude as the value a.
26. The computer-readable storage medium according claim 23 , wherein at least one of the auxiliary value β and the auxiliary module δ is determined by a division with remainder in each case, so that at least one of the inequations 0≦β<n and 0≦δ<a is fulfilled.
27. The computer-readable storage medium according to claim 19 , wherein the cryptographic application is a key pair determination in one of an RSA encoding method and an RSA signature method.
28. A portable data storage which is equipped with program instructions for determining, in a way that is protected against spying, the modular inverse b of a value a in relation to a module n for a cryptographic application, the program instructions comprising:
a) program instructions for determining an auxiliary value β and an auxiliary module δ, which are relatively prime to each other, at least depending on the value a, the module n and at least one masking parameter r in such a way that at least one of the following properties holds:
the auxiliary value β differs from the value a, and
the auxiliary module δ differs from the module n,
b) program instructions for determining an auxiliary inverse β′ as the modular inverse of the auxiliary value β in relation to the auxiliary module δ, and
c) program instructions for determining the modular inverse b at least depending on the following values:
the auxiliary inverse β′,
the at least one masking parameter r, and
at least one of the auxiliary value β and the auxiliary module δ,
wherein the modular inverse b is used to generate a secret private key for executing an RSA method, the secret private key being stored in the portable data storage.
29. The portable data storage according to claim 28 , wherein the portable data storage is one of a smart card and a chip module.
30. The portable data storage according to claim 28 , wherein the at least one masking parameter r is randomly chosen.
31. The portable data storage according to claim 28 , wherein the cryptographic application is a key pair determination in one of an RSA encoding method and an RSA signature method.