Method of and apparatus for determining a key pair and for generating RSA keys

A method of generating keys for an RSA encryption system, comprising the steps of:

• selecting two prime numbers;
• computing the product of the prime numbers;
• determining a pair of numbers comprising a first number and a second number, the second number being the multiplicative inverse with respect to a modulus of the first number, said modulus being equal to the product of a first prime number and a second prime number, step of determining method comprising the steps of:
• selecting the first number;
• computing a first sub-number for the second number as a multiplicative inverse of the first number with respect to a first sub-modulus that is equal to the first prime number minus 1 divided by the greatest common divisor of the first prime number minus 1 and the second prime number minus 1;
• computing a second sub-number for the second number as multiplicative inverse of the first number with respect to a second submodulus that is equal to the second prime number minus 1, with said first sub-modulus and said second sub-modulus being relatively prime;
• and
• determining the second number using the first sub-number and the second sub-number by means of the Chinese remainder theorem;
• outputting the product of the prime numbers and the first number of said pair of numbers as public key;
• and
• storing the second number as private key.

An apparatus for determining a pair of numbers comprising a first number and a second number, the second number being the multiplicative inverse with respect to a modulus of the first number, said modulus being equal to the product of a first prime number and a second prime number, said apparatus comprising:

• a means for selecting the first number;
• a means for computing a first sub-number for the second number as a multiplicative inverse of the first number with respect to a first sub-modulus that is equal to the first prime number minus 1 divided by the greatest common divisor of the first prime number minus 1 and the second prime number minus 1;
• a means for computing a second sub-number for the second number as multiplicative inverse of the first number with respect to a second sub-modulus that is equal to the second prime number minus 1, with said first sub-modulus and said second sub-modulus being relatively prime;
• a means for determining the second number using the first sub-number and the second sub-number by means of the Chinese remainder theorem;
• a means for storing the second number as a private key;
• and
• means for outputting at least one of the first and second numbers for use as a key in a cryptosystem.

An apparatus for generating keys for an RSA encryption system, comprising:

• a means for selecting two prime numbers;
• a means for computing the product of the prime numbers;
• a means for determining a pair of numbers comprising a first number and a second number, the second number being the multiplicative inverse with respect to a modulus of the first number, said modulus being equal to the product of a first prime number and a second prime number, said means for determining comprising:
• a means for selecting the first number;
• a means for computing a first sub-number for the second number as a multiplicative inverse of the first number with respect to a first sub-modulus that is equal to the first prime number minus 1 divided by the greatest common divisor of the first prime number minus 1 and the second Prime number minus 1;
• a means for computing a second sub-number for the second number as multiplicative inverse of the first number with respect to a second sub-modulus that is equal to the
• second prime number minus 1, with said first sub-modulus and said second sub-modulus being relatively prime;
• and
• a means for determining the second number using the first sub-number arid the second sub-number by means of the Chinese remainder theorem;
• a means for outputting said product and the first number of said pair of numbers as public key;
• and
• a means for storing the second number as private key.