RSA key-pair generation

Edit online

RSA key-pair generation is determined based on user input of the modulus bit length, public exponent, and key type.

The output is based on creating primes p and q in conformance with ANSI X9.31 requirements as follows:
  • prime p bit length = ((modulus_bit_length +1)/2)
  • prime q bit length = modulus_bit_length - p_bit_length
  • p and q are randomly chosen prime numbers
  • p > q
  • The Rabin-Miller Probabilistic Primality Test is iterated 8 times for each prime. This test determines that a false prime is produced with probability no greater then 1/4c, where c is the number of iterations. Refer to the ANSI X9.31 standard and see the section entitled Miller-Rabin Probabilistic Primality Test.
  • Primes p and q are relatively prime with the public exponent.
  • Primes p and q are different in at least one of the first 100 most significant bits, that is, |p-q| > 2(prime bit length - 100). For example, when the modulus bit length is 1024, then both primes bit length are 512 bits and the difference of the two primes is |p-q| > 2412.
  1. For each key generation, and for any size of key, the PKA manager seeds an internal FIPS-approved, SHA-1 based psuedo random number generator (PRNG) with the first 24 bytes of information that it receives from three successive calls to the random number generator (RNG) manager's PRNG interface.
  2. The RNG manager can supply random number in two ways, but with the CCA Support Program only one way is used, namely, the PRNG method. The PKA manager seeds an internal FIPS-approved, SHA-1 based PRNG with 24 bytes obtained.

    The RNG manager can respond to requests for random numbers from other processes with such responses interspersed between responses to PKA manager requests. An RSA key is generated from random information obtained from two cascaded SHA-1 PRNGs.

  3. An RSA key is based on one or more 24-byte seeds from the RNG manager source, depending on the dynamic mix of tasks running inside the coprocessor.

There exists a system RNG manager (ANSI X9.31 compliant) that is used as the source for pseudo random numbers. The PKA manager also has a PRNG that is DSA compliant for generating primes. The PKA manager PRNG is re-seeded from the system RNG manager, for every new key pair generation, which is for every generation of a public/private key pair.