c. q divides p - 1. This prime generation scheme starts by using the SHA-1 and a user supplied SEED to construct a prime, q, in the range 2159 < q < 2160. Once this is accomplished, the same SEED value is used to construct an X in the range 2L-1 < X < 2L. The prime, p, is then formed by rounding X to a number congruent to 1 mod 2q as described below. An integer x in the range 0 £ x < 2g may be converted to a g-long sequence of bits by using its binary expansion as shown below: x = x1*2g-1 + x2*2g-2 + ... + xg-1*2 + xg -> { x1,...,xg }. Conversely, a g-long sequence of bits { x1,...,xg } is converted to an integer by the rule { x1,...,xg } -> x1*2g-1 + x2*2g-2 + ... + xg-1*2 + xg. Note that the first bit of a sequence corresponds to the most significant bit of the corresponding integer and the last bit to the least significant bit. Let L - 1 = n*160 + b, where both b and n are integers and 0 £ b < 160. Step 1. Choose an arbitrary sequence of at least 160 bits and call it SEED. Let g be the length of SEED in bits. Step 2. Compute U = SHA-1[SEED] XOR SHA-1[(SEED+1) mod 2g ]. Step 3. Form q from U by setting the most significant bit (the 2159 bit) and the least significant bit to 1. In terms of boolean operations, q = U OR 2159 OR 1. Note that 2159 < q < 2160. Step 4. Use a robust primality testing algorithm to test whether q is prime1. Step 5. If q is not prime, go to step 1. Step 6. Let counter = 0 and offset = 2. Step 7. For k = 0,...,n let Vk = SHA-1[(SEED + offset + k) mod 2g ]. 1
A robust primality test is one where the probability of a non-prime number passing the test is at most 2-80.
14
14
