Patent ID: 7860242

Claim:
A method of securely implementing a public-key cryptography algorithm in a microprocessor-based system, the public key being composed of an integer n that is a product of two large prime numbers p and q, and of a public exponent e, said method determining a set E comprising a predetermined number of prime numbers e i that can correspond to the value of the public exponent e, and comprising the following steps: a) choosing a value e i from the values of the set E; b) if Φ(p)=Φ(q), where Φ(n), Φ(p), and Φ(q) are functions giving the number of bits encoding respectively the number n, the number p, and the number q, testing, in a processor of the microprocessor-based system, whether the chosen e i value satisfies the relationship: (1 −e i ·d )modulo n<e i ·2 (Φ(n)/2)+1 or said relationship as simplified: (− e i ·d )modulo n<e i ·2 (Φ(n)/2)+1 c) if the test relationship applied in the preceding step is satisfied, defining e=e i , and storing e in a memory of the microprocessor-based system; otherwise, reiterating the preceding steps while choosing another value for e i from the set E until an e i value can be attributed to e and, if no e i value can be attributed to e, then indicating that the computations of said cryptography algorithm using the value of e cannot be performed; and d) performing a cryptographic operation on data using the stored value for e.