RSA > Key Generation


 General Example 1 Example 2 Example 3 (64-bit)
1. choose large p1, p2 ∈ ℙ

Must p1 and p2 be distinct?		 p1 = 7
p2 = 11		 p1 = 61
p2 = 53		 p1 = 9551156224924043759
p2 = 1870011662606093473
2. μ = (p1)(p2)
think "modulus"
semi-prime		 μ = (p1)(p2)
μ = (7)(11)
μ = 77		 μ = (p1)(p2)
μ = (61)(53)
μ = 3233		 μ = (p1)(p2)
μ = (9551156224924043759)(1870011662606093473)
μ = 17860773531980750341058100301096285007

0x 0D6FDC1F9F46BD9E53C526E77D23F34F
3. φ(μ)

In order to determine this number, you have to know the factorization of μ.		 φ(μ) = φ(77)
φ(μ) = 60		 φ(μ) = φ(3233)
φ(μ) = 3120		 φ(μ) = φ(17860773531980750341058100301096285007)
φ(μ) = 17860773531980750329636932413566147776

0x 0D6FDC1F9F46BD9DB5450338F4CEDCC0
4.
pick any ε where:
(1) 1 < ε < φ(μ)
(2) gcd(ε, φ(μ)) = 1 must be coprime
 1 < ε = 17 < 60 1 < ε = 17 < 3120 17860773531980750329636932413566147776

(2^64 - 3)
0x FFFFFFFFFFFFFFFD
5. Public Key: μ, ε μ = 77
ε = 17		 μ = 3233
ε = 17		 μ = 17860773531980750341058100301096285007
ε = 18446744073709551613
6. δε ≡ 1 (mod φ(μ))
Find the modular multiplicative inverse		 (δ)(17) ≡ 1 (mod 60) (δ)(17) ≡ 1 (mod 3120) (δ)(18446744073709551613) ≡ 1 (mod 17860773531980750329636932413566147776)
0x 083D3D2D32E2C3E2A62486350E458155
7. Private Key: δ δ = 53 δ = 2753 δ = 10951794882651480131062190390917824853
A common practice in modern RSA implementations is to choose a standard, small public exponent like e=65537 (which is a prime number, 2 16 +1)