- Prime Number Selection:
Two large prime numbers, let's call them "P" and "Q," are carefully chosen. They should be distinct from each other and ideally have a similar number of digits in their binary representation.
-
Computation of N: These prime numbers are multiplied together to form a new, even larger number, which we'll refer to as "N." This number serves as a cornerstone for both the public and private keys.
-
Totient Calculation: A special value called the "totient" of N, denoted by the Greek letter phi (𝜑), is calculated using the formula: 𝜑(𝑛) = (P-1) * (Q-1). This totient plays a crucial role in finding the private key.
-
Choosing the Public Exponent: An integer called "E" is selected as the public exponent. It must meet two conditions: It must be coprime with the totient 𝜑(𝑛), meaning they have no common divisors other than 1. It must be greater than 1 but less than N.
-
Determining the Private Exponent: The private exponent, denoted by "D," is calculated using a special relationship with the public exponent E and the totient 𝜑(𝑛). The formula for finding D is: D * E ≡ 1 (mod 𝜑(𝑛)). This means that D, when multiplied by E and divided by 𝜑(𝑛), leaves a remainder of 1.
-
Key Pair Formation: Now, the public key and private key are established: The public key consists of the pair (E, N). The private key consists of the pair (D, N).