Key Generation in RSA Algorithm Cryptography | Steps For RSA Key Generation

computational steps for key generation are

1. Generate two different primes p and q

2. Calculate the modulus n = p×q 3. Calculate the totient φ(n) = (p−1)×(q−1) 4. Select public exponent an integer such that1 < e < φ(n) and gcd(φ(n),e) = 1

5. Calculate for the private exponent a value for d such that d = e−1 mod φ(n)

6. Public Key = [e,n]

7. Private Key = [d,n]

• The next three subsections elaborate on these computational steps.

Computational Steps for Selecting the Primes p and q in RSA Cryptography

• You first decide upon the size of the modulus integer n. Let’s say that your implementation of RSA requires a modulus of size B bits.

• To generate the prime integer p; – Using a high-quality random number you first generate a random number of size B/2 bits.

– You set the lowest bit of the integer generated by the above step; this ensures that the number will be odd.

– You also set the two highest bits of the integer; this ensures that the highest bits of n will be set. 

– Using the Miller-Rabin algorithm  you now check to see if the resulting integer is prime. If not, you increment the integer by 2 and check again. This becomes the value of p.

 You do the same thing for selecting q. You start with a randomly generated number of size B/2 bits, and so on.

• In the unlikely event that p = q, you throw away your random number generator and acquire a new one.

• For greater security, instead of incrementing by 2 when the MillerRabin test fails, you generate a new random number.

Choosing a Value for the Public Exponent e

• Recall that encryption consists of raising the message integer M to the power of the public exponent e modulo n. This step is referred to as modular exponentiation.

• The mathematical requirement on e is that gcd(e, φ(n)) = 1, since otherwise e will not have a multiplicative inverse mod φ(n). Since n = p × q, this requirement is equivalent to the two requirements gcd(e, φ(p)) = 1 and gcd(e, φ(q)) = 1. In other words, we want gcd(e, p−1) = 1 and gcd(e, q−1) = 1.

• For computational ease, one typically chooses a value for e that is prime, has as few bits as possible equal to 1 for fast multiplication, and, at the same time, that is cryptographically secure in the sense described in the next bullet. Typical values for e are 3, 17, and 65537 (= 216 + 1).

 Each of these values has only two bits set, which makes for fast modular exponentiation. But don’t forget the basic requirement on e that it must be relatively prime to p−1 and q −1 simultaneously. Whereas p is prime, p−1 definitely is not since it is even. The same goes for q−1. 

So even if you wanted to, you may not be able to use a small integer like 3 for e.

•  Small values for e, such as 3, are considered cryptographically insecure. Let’s say a sender A sends the same message M to three different receivers using their respective public keys that have the same e = 3 but different values of n. Let these values of n be denoted n1, n2, and n3. Let’s assume that an attacker can intercept all three transmissions. The attacker will see three ciphertext messages: C1 = M3 mod n1, C2 = M3 mod n2, and C3 = M3 mod n3. Assuming that n1, n2, and n3 are relatively prime on a pairwise basis, the attacker can use the Chinese Remainder Theorem (CRT) to reconstruct M3 modulo N = n1 ×n2 ×n3. (This assumes that M3 < n1n2n3, which is bound to be true since M < n1, M < n2, and M < n3.) Having reconstructed M3, all that the attacker has to do is to figure out the cube-root of M3 to recover M. Finding cube-roots of even large integers is not that hard. 

• Having selected a value for e, it is best to double check that we indeed have gcd(e, p − 1) = 1 and gcd(e, q − 1) = 1 (since we want e to be coprime to φ(n), meaning that we want e to be coprime to p−1 and q −1 separately). If either p or q is found to not meet these two conditions on relative primality of φ(p) and φ(q) vis-a-vis e, you must discard the calculated p and/or q and start over. (It is faster to build this test into the selection algorithm for p and q.) When e is a prime and greater then 2, a much faster way to satisfy the two conditions is to ensure

25

Computer and Network Security 

p mod e 6= 1 q mod e 6= 1

• To summarize the point made above, you give priority to using a particular value for e – such as a value like 65537 that has only two bits set. Having made a choice for the encryption integer e, you now find the primes p and q that, besides satisfying all other requirements on these two numbers, also satisfy the conditions that the chosen e would be coprime to the totients    φ(p) and φ(q).