Message generation for a cryptographic key generation test
Generation of a message m of order λ(n) for a test of the integrity of the generation of a pair of cryptographic keys within the multiplicative group of integers modulo n=p·q, including: —key pair generation including, to generate p and q: a random selection of candidate integers; and a primality test; —a first search of the multiplicative group of integers modulo p for a generator a; —a second search of the multiplicative group of integers modulo q for a generator b; —a third search for a number y, as message m, verifying: 1≤γ≤n−1, where γ=a mod p and γ=b mod q, the first or second search being performed during the primality test.
1. A method, performed by a processor of a cryptographic system, of detecting errors when cryptographically generating a message, the method including:
generating a pair of public and private cryptographic keys from a multiplicative group of integers modulo n, with n being the product of the two prime numbers p and q, said generating including performing the following for generating the two prime numbers p and q used to generate the public and private cryptographic keys:
a random drawing of candidate integers for p and q, and
an test of the primality of said candidate integers including:
a first step of searching for a generator a of the multiplicative group of integers modulo p, zero being excluded,
a second step of searching for a generator b of the multiplicative group of integers modulo q, zero being excluded,
wherein the generator a or b is selected via the following process:
selecting a candidate integer w as p or q when w satisfies w−1=2 s r, wherein s is an integer and r is an odd integer,
selecting a number c as a candidate generator for generators a or b such that 1≤c≤w−1,
calculating the number y as c 2 s−1 r in order to save system resources,
comparing said number y with the number w−1, and
selecting said number c as generator of the multiplicative group of integers modulo w, zero being excluded, when y=w−1 mod w,
rejecting p or q when p or q fails the test of their primality and generating another candidate integer for p or q upon which to perform an additional test for primality;
performing an integrity test of the generated public and private cryptographic keys by encrypting a number y, as message m, using the generated public and private cryptographic keys, wherein the message satisfies: 1≤y≤n−1 with y=a mod p and γ=b mod q, and the message m is of order λ(n), wherein λ(n) is the lowest common multiple between p−1 and q−1, in order to optimize integrity verification by decreasing the error rate at which the public and private cryptographic keys are generated.
2. The method as claimed in claim 1 , further including an additional step to the test of the primality to verify when a (w−1)/q ≠1 mod w, with a w−1 =1 mod w, said verification being effected for a set of divisors q of w−1.
3. The method as claimed in claim 2 , wherein said verification is effected for a set of prime divisors q of w−1.
4. The method as claimed in claim 3 , wherein, for said divisors q, the value a (w−1)/q is calculated by modular exponentiation.
5. The method as claimed in claim 2 , wherein, for said divisors q, the value a (w−1)/q is calculated by modular exponentiation.
6. The method as claimed in claim 5 , including an initialization of said modular exponentiation with an initial variable calculated from the factorization in prime numbers of the number w−1.
7. The method as claimed in claim 1 , wherein said test of the primality is carried out in accordance with a probabilistic algorithm.