Private exponent d represents the inverse of exponent e, modulo (p−1)(q−1). Pair n and e represents the public key while pair n and d represents the private key. As a result, there exists an integer “d” such that product e*d is congruent to 1 modulo φ(n). Numbers p and q are selected so that numbers p−1 and q−1 are prime with a quantity “e”, called public exponent, the latter being then prime with the Euler indicator “φ(n)” of product n (φ(n)=(p−1)(q−1)).
The product of these prime numbers represents encryption modulus “n”. The generation of the pair of public and private keys requires the use of two different relatively prime numbers “p” and “q”, of relatively large size (typically, 1,024 or 2,048 bits).
The holder of the pair of keys may directly communicate the public key to the other party to enable it to process the data. However, the private key is reserved to the circuit having created the pair of keys. The public key is relatively widely accessible to enable the transmitter of the ciphered data or the receiver of the signed data to exploit these data. For an authentication, the private key is used by the transmitter to sign the data while the public key is used by the receiver to authenticate the signature. In ciphering/deciphering mode, the public key is used by a transmitter to cipher data to be confidentially communicated to a receiver, the latter using its private (or secret) key to decipher the data. It is based on the use of a pair of keys comprising a public key and a private key. This algorithm is used to cipher/decipher data or to sign data and enable them to be authenticated. The RSA algorithm is one of the most commonly used asymmetrical ciphering algorithms (with a public key). The present invention applies to any electronic circuit exploiting an algorithm exploiting a prime number factorization and, more specifically, to chip cards. The present invention more specifically relates to the protection, during the generation of prime numbers in an electronic circuit, against side channel attacks, for example, by statistical analysis of the power consumption of the circuit (SPA-simple power analysis) or of its electromagnetic signature, or against fault-injection attacks. The present invention generally relates to electronic circuits and, more specifically, to circuits executing RSA-type asymmetrical ciphering algorithms.
Primo.This application claims the priority benefit of French patent application number 09/53523, filed on May 28, 2009, entitled “PROTECTION OF A PRIME NUMBER GENERATION FOR AN RSA ALGORITHM,” which is hereby incorporated by reference to the maximum extent allowable by law. I believe these are Rabin-Miller pseudoprimes (which would be extremely unlikely to be composite), but if this is not suitable the output can be formally checked using e.g. If you want to find, say, the first 50 primes after $10^$. You can save some work by sieving, but you already know that. In effect, you look at $N+1,N+2,N+3,\dots$ until you find a prime. But there's no especially clever way to do it. People do this all the time, for example, here is a tabulation of the smallest prime exceeding $10^m$ for various values of $m$.
This is equivalent to, "given an integer $N$, find the smallest prime exceeding $N$." "The objective is: given a first prime, generate the $n$ next primes."
0 kommentar(er)
