Foundations of Blockchain

RSA parameter generation

Before looking at encryption and decryption using RSA, we need to consider the RSA parameter generation process. Here are the steps involved in this process:

1. Select two distinct large prime numbers, p, and q.
2. Compute n = p*q and φ(n) = (p − 1)*(q − 1).
3. Choose a random integer e, such that 1 < e < φ(n) and gcd (e, φ(n)) = 1, that is, integer e and φ(n), are coprime.
4. Find d ≡ e^-1 (mod φ(n)), where e^-1 is the modular multiplicative inverse of e.

A modular multiplicative inverse of an integer a is an integer x, such that the product ax is congruent to 1 with respect to the modulus m.

More clearly, find d such that d*e ≡ 1 (mod φ(n)), meaning find a value d such that d*e has a remainder of 1 when divided by φ(n).