Message generation for a cryptographic key generation test

Abstract

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.Math.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: 1n1, where =a mod p and =b mod q, the first or second search being performed during the primality test.

Claims

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 w1=2.sup.sr, 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 1cw1, calculating the number y as c.sup.2.sup.s1.sup.r in order to save system resources, comparing said number y with the number w1, and selecting said number c as generator of the multiplicative group of integers modulo w, zero being excluded, when y=w1 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: 1yn1 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 p1 and q1, 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.sup.(w1)/q1 mod w, with a.sup.w1=1 mod w, said verification being effected for a set of divisors q of w1.

3. The method as claimed in claim 2, wherein said verification is effected for a set of prime divisors q of w1.

4. The method as claimed in claim 3, wherein, for said divisors q, the value a.sup.(w1)/q is calculated by modular exponentiation.

5. The method as claimed in claim 2, wherein, for said divisors q, the value a.sup.(w1)/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 w1.

7. The method as claimed in claim 1, wherein said test of the primality is carried out in accordance with a probabilistic algorithm.

Description

(1) Other advantages, objects and features of the present invention emerge from the following detailed description given by way of nonlimiting example with reference to the appended drawings, in which:

(2) FIG. 1 illustrates a key generation integrity test;

(3) FIG. 2 illustrates a message generation method for a key generation integrity test;

(4) FIG. 3 illustrates a method of determination of a generator of a multiplicative group;

(5) FIG. 4 illustrates diagrammatically embodiments of a device.

(6) Embodiments are described hereinafter. However, in a preliminary manner, there is described a cryptographic key pair generation integrity test method. This test method may be used for cryptographic keys used in encryption and/or digital signature mechanisms. This method may therefore be used even before the subsequent use of the pair of keys generated is known.

(7) It is assumed that a public cryptographic key (e, n) and a private cryptographic key (d, n) are generated such that: n=p.Math.q, with p and q being prime numbers, 1<e<(n) and e and (n) are mutually prime (gcd(e, (n))=1), with (n)=(p1).Math.(q1) ( being the Euler indicator function or totient), and d.Math.e=1 mod (n), (n) being the lowest common multiple between p1 and q1 ((n)=1 cm(p1, q1)).

(8) Then, as shown in FIG. 1, during a first step 100 a message m (m belonging to Z.sub.n, the multiplicative group of integers modulo n), is encrypted with the public exponent e so as to obtain a first encrypted message c=m.sup.e mod n. Then, during the step 102, the encrypted message c is decrypted with the private key d so as to obtain a decrypted message m=c.sup.d mod n.

(9) It is then verified during a step 103 if the initial message m and the decrypted message are the same (m=m). If this is not the case (NOK), it is determined during the step 104 that the generated key pair has no integrity. If on the other hand the initial message m and the decrypted message are the same (OK), the decrypted message m is encrypted, during a step 105, with the public exponent e so as to obtain a second encrypted message c=(m).sup.e mod n.

(10) It is then verified during a step 106 if the first encrypted message c and the second encrypted message c are the same (c=c). If such is the case (OK), it is determined during the step 107 that the integrity test has succeeded. If not (NOK), it is determined during the step 108 that the generated key pair has no integrity.

(11) Some key pairs with no integrity may successfully pass integrity tests like that described above or other prior art tests.

(12) For example, if, instead of generating the private exponent d, a number d is generated such that: d.Math.e=1 mod (n)/, 1, divides (n),
it can happen that for messages the pair of keys with the numbers d and e successfully passes the test but an error has occurred in the private exponent d.

(13) In addition to being a source of errors for a cryptographic system using the keys, this can be a source of attacks by malicious third parties.

(14) For example, the number d may be generated in error if the calculation of the lowest common multiple of p1 and q1 (which should normally give (n)) is erroneous. The number d may be calculated using the Euclid algorithm. The integers a and b are calculated so that e.Math.a+b.Math.(n)/=1 (Bezout's identity). The number d is then obtained as d=a mod (n)/. Under these conditions, it is indeed the fact that d.Math.e=1 mod (n)/.

(15) By causing the determination of the number d instead of the number d, a hacker can therefore retrieve one of the secret factors (p and q) of the number n such that n=p.Math.q.

(16) In fact, assuming that the integer divides the number

(17) $\frac{\left(q-1\right)}{\gcd \left(p-1,q-1\right)}$
but not the number then

(18) $\frac{\left(p-1\right)}{\gcd \left(p-1,q-1\right)},$
then denoting by t the number such that

(19) $t=\frac{\left(q-1\right)}{.Math.\gcd \left(p-1,q-1\right)},$
we obtain d=e.sup.1 mod t.Math.(p1).

(20) Therefore, the private exponent is the inverse of the public exponent in the ring Z.sub.t.Math.(p1) instead of the ring Z.sub.(n). Then, for a random message m: (m.sup.d).sup.e=m mod n, and also (m.sup.d).sup.e=m mod p.

(21) A multiple of the factor p can therefore be obtained as (m.sup.d).sup.em mod n.

(22) A hacker can therefore interfere with the generation of keys and request the signing of random messages. For some messages m, the signature s obtained is such that gcd(s.sup.em,n) gives a factor of n.

(23) Assume that the lowest common multiple of p1 and q1 is calculated as follows:

(24) $\left(n\right)=\frac{\left(p-1\right).Math.\left(q-1\right)}{\gcd \left(p-1,q-1\right)},$
with gcd(p1, q1) being the greatest common divisor of p1 and q1. If the calculation of this greatest common divisor gives .Math.gcd(p1, q1) (the product of by gcd(p1, q1)) instead of gcd(p1, q1), d is calculated instead of calculating d.

(25) The inventors have noted that the integrity tests currently used could fail to detect some key pair generation errors, notably during attacks as referred to above.

(26) A hacker can cause errors in the calculation of the private exponent by auxiliary channel observation of the operation of the device executing the key generation and then by physically attacking the device to interfere with this operation. The hacker can for example use lasers to interfere with the device or to interfere with its electrical power supply.

(27) By way of illustration, if an error (as referred to above) is introduced such that the number divides the value k.Math.(n)/ (k being an integer) and such that instead of the number d a number d is determined such that d.Math.e=1+k.Math.(n)/ then an integrity test as defined for example in the FIPS 140-2 standard executed on a message m of order s does not make it possible to detect the error if s divides k.Math.(n)/ but does make it possible to detect it if s does not divide k.Math.(n)/. It must be remembered that the order s of the message m in the multiplicative group is the number of times that the message m must be multiplied to obtain 1.

(28) In fact, let e, p and q be RSA parameters with n=p.Math.q. If d=e.sup.1 mod (n)/ is the erroneous exponent, the correct exponent being d=e.sup.1 mod (n), if d is different from d then mZ.sub.n* such that (m.sup.e).sup.d m mod n. Moreover if mZ.sub.n* we have (m.sup.e).sup.d=m mod n then d=d. It is possible to demonstrate this, but in the interests of conciseness this is not done here.

(29) Methods are described hereinafter making it possible to render the integrity tests sensitive to this type of errors. The integrity tests may be employed during generation of the keys.

(30) As discussed above with reference to FIG. 1, the detection of an erroneous key is sensitive to the value of the order of the message m used for the test. If the order s of the message m divides k.Math.(n)/ (k is an integer and divides (n)) the error is not detected.

(31) It is then advantageous to generate messages the order of which makes it possible to detect the error, in particular messages the order of which does not divide k.Math.(n)/.

(32) For example, messages of order (n) are good candidates.

(33) There is described hereinafter with reference to FIG. 2 a method of generation of messages of order (n) for use in integrity test methods. This method is based on the algorithm described by Menenzes et al. in Handbook of Applied Cryptography (method 4.83 in that document).

(34) During a step 200, a number p is generated at random. It is then verified during the step 201 whether the number p is prime. If this is not the case (NOK), the step 200 is repeated. If p is prime (OK), a number q is generated at random during the step 202. It is thereafter verified during the step 203 whether the number q is prime. If this is not the case (NOK), the step 202 is repeated. If q is prime (OK), the product n of the numbers p and q (n=p.Math.q) is calculated during the step 204.

(35) During the primality tests, the generators a and b of the additive groups Z.sub.p* of integers modulo p (0 being excluded) and Z.sub.q* of the integer modulo q (0 being excluded) are calculated.

(36) For example, the generator a is calculated during the primality test for the integer p and the generator b is calculated for the integer q.

(37) A number is then calculated during the step 205, such that 1n1 with =a mod p and =b mod q.

(38) The number calculated in this way is then utilized (step 206) as the message for the integrity test of the cryptographic keys generated from p and q.

(39) To calculate the integer number , the Gauss algorithm (2.121 in the above-mentioned document) may be used.

(40) The cryptographic keys may be generated in a process (not shown) during which the public key is generated with the calculation of the public exponent e such that: 1<e<(n) and e and (n) are mutually prime (gcd(e, (n))=1), with (n)=(p1).Math.(q1) ( being the Euler indicator function or totient).

(41) During this process, the private key may be generated with the calculation of the number d such that d.Math.e=1 mod (n), (n) being the lowest common multiple in p1 and q1.

(42) The search for the generators a and b as proposed in the prior art, in particular in the above-mentioned document, necessitates the factorization of the integers p1 and q1. Now, in cryptographic applications, the integers p and q are generally strong integer numbers, i.e. the integers p1 and q1 each have a large divisor (for example of the order of 160 bits). For example, in the FIPS 180-3 and ANSI X9.31 standards p and q are generated such that p1, p+1, q1 and q+1 are divisible by a large prime number.

(43) It is therefore somewhat unrealistic to use the prior art methods.

(44) It is proposed here that it is advantageous to determine these integers during the primality test effected during the generation of the integers p and q. It is therefore possible to find the generators a and b knowing that the integers p and q are strong prime numbers.

(45) As already referred to above, the primality test may for example be a probabilistic test (for example of the Miller-Rabin type).

(46) The method described with reference to FIG. 3 may be used to calculate the generator(s) a and/or b.

(47) In a first step 300, a candidate integer w, verifying w1=2.sup.sr1 is generated.

(48) An integer c is then selected in the step 301 such that 1cw1. A number y=C.sup.2.sup.s1.sup.r is calculated from this integer during the step 302.

(49) Then, if this number y is equal to w1 modulo w (test of the step 303), this number is chosen as generator of the multiplicative group Z.sub.w* of integers modulo w (0 being excluded). This may therefore be the number for the multiplicative group Z.sub.p* and/or the number b for the multiplicative group Z.sub.q*.

(50) An algorithm for generating the generators a and b is given in appendix A. It is based on the Miller-Rabin algorithm. The algorithm illustrates the search for the generator a, the latter being transposable to the search for the generator b.

(51) A variable y is initialized with the value a.sup.r mod w. The value a.sup.2jr mod w is then calculated iteratively by squaring the variable y in each step j, with 0js1.

(52) If the iterative loop terminates with j=s1 and y=w1, then the base a is probably a generator of the multiplicative group Z.sub.w* of integers modulo w (0 being excluded).

(53) The algorithm given in appendix A can deliver a plurality of generators but is designed so that it always returns the last one.

(54) The multiplicative group Z.sub.p* of integers modulo p (0 being excluded) has a number ((p)) of generators ( being the Euler indicator function or totient). The probability for the algorithm to return a generator of Z.sub.p* (p being prime) is ((p))/(p), i.e. (p1)/(p1). The iterative loop being repeated t times, the probability of finding a generator among the t random executions is t. (p1)/(p1).

(55) The generator search algorithm can return false positives, i.e. elements of the multiplicative group Z.sub.w* of integers modulo w (0 being excluded) that are not in fact generators. However, as soon as =2 (it must be remembered that a is a divisor of (n) and that the search is for messages the order whereof does not divide k.Math.(n)/), these false generators can be used anyway to detect the erroneous exponents d.

(56) In fact, let us assume: that g.sub.p is a generator of the subgroup G included in the multiplicative group Z.sub.p* of integers modulo p (0 being excluded) of order o(g.sub.p)=2.sup.s.Math.p.sub.1.sup.e.sup.1 . . . p.sub.i.sup.e.sup.i . . . p.sub.t.sup.e.sup.t, avece.sub.i<e.sub.i but not a generator of Z.sub.p* that g.sub.q is a generator of the subgroup G included in the multiplicative group Z.sub.q* of integers modulo q (0 being excluded) of order o(g.sub.p)=q1=2.sup.r.Math.p.sub.1.sup.f.sup.1 . . . p.sub.j.sup.f.sup.j . . . p.sub.t.sup.f.sup.t.sup.2, whilst not being a generator of Z.sub.q* and that g is the gaussian recombination of g.sub.p and g.sub.q, which is an element of Z.sub.n* of order 1 cm (o (g.sub.p), o(g.sub.q)).

(57) By definition we have:

(58) $\begin{array}{c}\left(n\right)=\mathrm{lcm}\left(p-1,q-1\right)\\ =\frac{\left(p-1\right).Math.\left(q-1\right)}{\gcd \left(p-1,q-1\right)}\\ =2^s.Math.p_1^{e_1}\mathrm{.Math.}{p}_t^{e_t}.Math.2^{r-m_0}.Math.p_1^{f_1-m_1}\mathrm{.Math.}{p}_t^{f_t-m_t}\end{array}$
with m.sub.j=min (e.sub.j, f.sub.j) for j=1 . . . t and m.sub.0=min (r, s).

(59) We also have:

(60) $\begin{array}{c}o\left(g\right)=\mathrm{lcm}\left(o\left(g_p\right),o\left(g_q\right)\right)\\ =2^s.Math.p_1^{e_1}\mathrm{.Math.}{p}_i^{e_t^{}}\mathrm{.Math.}{p}_t^{e_t}.Math.2^{r-m_0}.Math.p_1^{f_1-m_1}.Math.p_i^{f_i-m_i^{}}.Math.p_j^{f_j^{}-m_j^{}}\mathrm{.Math.}{p}_t^{f_t-m_t}\end{array}$
with m.sub.i=min (e.sub.i, f.sub.i) less than or equal to m.sub.i and m.sub.j=min (e.sub.i, f.sub.i) less than or equal to m.sub.i and i less than or equal to j.sup.3.

(61) The effect of the primality test (g.sup.ed=g mod n) on such an element g is considered hereinafter.

(62) By virtue of the definition of the erroneous exponent d, we have: e.Math.d=1+k.Math.(n)/.

(63) If d is different from d (otherwise d would be a correct exponent), does not divide k, therefore divides (n). If =2, then

(64) $\frac{\left(n\right)}{}=2^{s-1}.Math.p_1^{e_1}\mathrm{.Math.}{p}_t^{e_t}.Math.2^{r-m_0}.Math.p_1^{f_1-m_1}\mathrm{.Math.}{p}_t^{f_t-m_i}$
and therefore

(65) $g^{k\frac{\left(n\right)}{}}1$
because the order o(g) of g does not divide (n)/.

(66) In fact, we have

(67) $\frac{\left(n\right)/}{o\left(g\right)}=2^{-1}.Math.p_i^{e_i-e_i^{}}.Math.p_i^{m_i^{}-m_i}.Math.N$
which in the end implies that g.sup.ed is different from g modulo n. This means that the primality test rejects the generated key, which will be considered as erroneous.

(68) In the situation =2 it is therefore possible to use the generators stemming from false positives of the algorithm described above. In fact, this can be generalized for other values of , for example, in the set (2, 3, 5, 7).

(69) An algorithm, also based on the Miller-Rabin algorithm, utilizing such values of is therefore given in appendix B. The algorithm given in appendix B utilizes the following property (property 4.38 in the documents cited above).

(70) If w is an integer greater than or equal to 3, then w is a prime number if and only if there exits an integer satisfying:

(71) (i) a.sup.w1=1 mod w and

(72) (ii) a.sup.(w1)/q1 mod w for any prime divisor q of w1.

(73) The appendix B algorithm is similar to that of appendix A and adds the test of the above condition (ii).

(74) The implicit factorization effected in line 19 and in the test of line 21 is described hereinafter.

(75) The factorization of w1 on the base T of small prime numbers less than B is an available method known in the prior art, for example in the document Granville, Smooth numbers: Computational number theory and beyond, Proc. MSRI Conf. Algorithmic Number Theory: Lattices, Number, Fields, Curves and Cryptography, Berkeley 2000, Cambridge University Press.

(76) For the test of line 21, instead of calculating and testing if a.sup.(w1)/qi1 mod w for each divisor q.sub.i of w1 there is rather a test whether a.sup.(2.sup.s1.sup..r)/q.sup.i1 mod w for each prime divisor q.sub.i of w1. Account is therefore taken of the fact that a.sup.(2.sup.s1.sup..r) is not calculated in the Miller-Rabin algorithm.

(77) For this same test, it is necessary to calculate q.sub.i.sup.th modular roots for each prime integer q.sub.i. This operation is relatively costly in terms of resources.

(78) The algorithm given in appendix C makes it possible to transform a q.sub.i.sup.th modular root calculation into a modular exponentiation by q.sub.i. The intermediate value
y.sub.0=a.sup.2.sup.s1.Math.q.sub.1.sup.u.sup.1.sup.1. . . q.sub.m.sup.u.sup.m.sup.1.Math.v
is calculated in line 2 which makes it possible to calculate more easily the values a.sup.(2.sup.s1.sup..Math.r)/q.sup.i as

(79) 0$y_0^{{.Math.}_{ji}{q}_j}=a^{2^{s-1}.Math.q_1^{u_1}\mathrm{.Math.}{q}_i^{u_i-1}\mathrm{.Math.}{q}_m^{v_m}.Math.v}\mathrm{mod}$
which includes only modular exponentiations of y.sub.0 by a product of small prime integers.

(80) In order to optimize the calculations when using the appendix C algorithm, the Miller-Rabin algorithm may be modified to calculate and to store the intermediate value y.sub.0 to avoid calculating two costly exponentiations, namely
y.sub.0=a.sup.2.sup.s1.Math.q.sub.1.sup.u.sup.1.sup.1. . . q.sub.m.sup.u.sup.m.sup.1.Math.v
and
y.sub.0=a.sup.2.sup.s1.sup..r=y.sub.0.sub.j.sup.q.sup.j.

(81) A modified algorithm is given in appendix D. This algorithm yields an element g of the group Z.sub.w* the partial factorization of which of the order (of the element g) on the base T is the same as the factorization of a generator of Z.sub.w*.

(82) To summarize, the primality test used for the generation of the cryptographic keys is modified to make possible the generation of messages of maximum order in addition to the keys that make it possible to optimize the integrity verification. The keys are therefore correctly generated with a lower error rate because this strengthens the integrity tests.

(83) Computer programs for executing methods in accordance with embodiments of the invention can be produced by a person skilled in the art after examining FIGS. 1 to 3, appendices A to D and the present detailed description. FIG. 4 illustrates diagrammatically embodiments of a device.

(84) The FIG. 4 device 40 includes a memory unit (MEM) 41. This memory unit includes a random-access memory for temporary storage of calculation data used during the execution of a method in accordance with diverse embodiments of the invention. The memory unit further includes a non-volatile memory (for example of the EEPROM type) to store a computer program, for example, in accordance with one embodiment, for its execution by a processor (not represented) of a processing unit (PROC) 41 of the device.

(85) The device moreover includes a communication unit (COM) 43, for example for exchanging data with a device in accordance with other embodiments. Data may be exchanged between the devices using the APDU (Application Protocol Data Unit) protocol as defined in ISO standard 7816 part 4.

(86) The communication unit can therefore include an input/output interface able to exchange data in accordance with this protocol. Data may be exchanged by means of APDU commands and responses to this type of commands.

(87) A device in accordance with embodiments may conform to the ISO standard 7816. It may for example be a smartcard or a secured element.

(88) A device in accordance with embodiments is for example an integrated circuit.

(89) The present invention has been described and illustrated in the present detailed description with reference to the appended figures. The present invention is not limited to the embodiments described, however. Other variants, embodiments and combinations of features may be deduced and implemented by a person skilled in the art after reading the present description and examining the appended figures.

(90) In the claims, the term include does not exclude other elements or other steps. The indefinite article a or an does not exclude the plural. A single processor or a plurality of other units may be used to implement the invention. The various features described and/or claimed may advantageously be combined. Their presence in the description or in different dependent claims does not in fact exclude the possibility of combining them. The reference signs should not be understood as limiting the scope of the invention.

Appendix A

(91) Algorithm 1: Miller-Rabin probabilistic test modified to find a generator for =2

(92) Input: the integer w under test, a security parameter t

(93) Output: a response Prime or Composite to the question: is w prime?, and a generator g of Z.sub.w* if w is prime.

(94) TABLE-US-00001 1: y 0 2: g 0 3: Write w 1 = 2.sup.sr such that r is odd 4: for i = 1 to t do t is a security parameter 5: Pick randomly a in [2, w 2] 6: Compute y = a.sup.r mod w 7: if y 1 and y w 1 then 8: j 1 9: while j s 1 and y w 1 do 10: Compute y y.sup.2 mod w 11: if y = 1 then return (Composite) 12: end if 13: j j + 1 14: end while 15: if y w 1 then return (Composite) 16: end if 17: if j = s 1 then 18: g a a has an order equal to w 1, keep it in g ! 19: end if 20: end if 21: end for 22: return (Prime, g)

Appendix B

(95) Algorithm 2: Miller-Rabin probabilistic test modified to find a generator for any

(96) Input: the integer w under test, a security parameter t

(97) Output: a response Prime or Composite to the question: is w prime?, and a generator g of Z.sub.w* if w is prime.

(98) TABLE-US-00002 1: y 0 2: g 0 3: isAGenerator false 4: Write w 1 = 2.sup.s r such that r is odd 5: for i = 1 to t do t is a security parameter 6: Pick randomly a in [2, w 2] 7: Compute y = a.sup.r mod w 8: if y 1 and y w 1 then 9: j 1 10: while j s 1 and y w 1 do 11: Compute y y.sup.2 mod w 12: if y = 1 then return (Composite) 13: end if 14: j j + 1 15: end while 16: if y w 1 then return (Composite) 17: end if 18: if j = s 1 then a.sup.w1 1 mod w 19: Let {q.sub.1,... ,q.sub.m} T be the small prime divisors of w 1 20: for i = 1 to m do 21: if a.sup.(w1)/q, 1 mod w then 22: continue a.sup.(w1)/q, 1 mod w 23: else 24: isAGenerator false; 25: break; Leave the For-loop 26: end if 27: end for 28: if isAGenerator then 29: g a 30: end if 31: end if 32: end if 33: end for 34: return (Prime, g)

Appendix C

(99) Algorithm 3: test of generator on base T

(100) Input: the element a under test as generator, the first candidate prime number w under Miller-Rabin test, a base {2, q.sub.1, . . . , q.sub.m} included in T for partial factorization.

(101) Output: a response isAGenerator or isNotAGenerator to the question is a generator of Z.sub.w*?

(102) TABLE-US-00003 1: Let w 1 = 2.sup.s .Math. q.sub.1.sup.u1 . . . q.sub.m.sup.u.sup.m .Math. v be the partial prime factorisation of w 1 on basis T. 2: Compute y.sub.0 a.sup.2.sup.s1.Math. q.sub.1.sup.u.sup.1.sup.1 . . . q.sub.m.sup.u.sub.m.sup.1 .Math. v 3: if y.sub.0 1 mod w then return isNotAGenerator 4: end if 5: for i = 1 to m do 6: Compute y.sub.i y.sub.0.sup.jiqj mod w 7: if y.sub.i 1 mod w then return isNotAGenerator 8: end if 9: end for 10: return isAGenerator

Appendix D

(103) Algorithm 4: Miller-Rabin probabilistic test optimized to find a generator for any

(104) Input: the integer w under test, a security parameter t, a base T of prime numbers smaller than B.

(105) Output: a response Prime or Composite to the question: is w prime?, and a generator g of Z.sub.w* if w is prime.

(106) TABLE-US-00004 1: y 0 2: g 0 3: isAGenerator false 4: Write w 1 = 2.sup.s .Math. q.sub.1.sup.u.sup.1...q.sub.m.sup.u.sup.m .Math. v 5: for i = 1 to t do t is a security parameter 6: Pick randomly a in [2, w 2] 7: Compute y.sub.0 = a.sup.q.sup.1.sup.u.sup.1.sup.1.sup....q.sup.m.sup.u.sup.m1.Math.v mod w 8: Compute y = (y.sub.0).sup.q.sup.1.sup....q.sup.m mod w 9: if y 1 and y w 1 then 10: j 1 11: while j s 1 and y w 1 do 12: Compute y y.sup.2 mod w 13: Compute y.sub.0 y.sub.0.sup.2 mod w 14: if y = 1 then return (Composite) 15: end if 16: j j + 1 17: end while 18: if y w 1 then return (Composite) 19: end if 20: if j = s 1 then a.sup.w1 1 mod w 21: Let {q.sub.1,... ,q.sub.m} T be the small prime divisors of w 1 22: for i = 1 to m do 23: if y.sub.0.sup.jiqj 1 mod w then a.sup.(w1)/q.sup.1 1 mod w 24: continue 25: else 26: isAGenerator false; 27: break; Leave the For-loop 28: end if 29: end for 30: if isAGenerator then 31: g a 32: end if 33: end if 34: end if 35: end for 36: return (Prime, g)