RSA


 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 < ε = 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


Encryption / Decryption
8. message_hash = hash(message) 65 = hash("hello world") 65 = hash("hello world") 2793 = hash("sample text")
9. encrypt(message_hash)
= message_hashε(mod μ)
= ciphertext
Message hash cannot be larger than the modulus.		 encrypt(65)
= 6517(mod 77)
= 32		 encrypt(65)
= 6517(mod 3233)
= 2790
10. decrypt(ciphertext)
= ciphertextδ(mod μ)
= message_hash		 decrypt(32)
= 3253(mod 77)
= 65		 decrypt(2790)
= 27902753(mod 3233)
= 65


Digitally Signed Document
11. sign()
⇒ message_hashδ (mod μ)
⇒ signature		 sign()
⇒ 6553 (mod 77)
⇒ 32		 sign()
⇒ 652753 (mod 3233)
⇒ 588		 sign()
⇒ 12469746642430673414839836874600900068
    0x 096195F9FCD2DD5615035979C83465E4
12. verify()
⇒ signatureε (mod μ)
⇒ message_hash		 verify()
⇒ 3217 (mod 77)
⇒ 65		 verify()
⇒ 58817 (mod 3233)
⇒ 65		 
Q1. Is the bit size the modulus or public key?
A1. 2048 bits Modulus (μ)
     112 bits Exponent (ε)
    2160 bits Public Key section of the Certificate
     * ε < μ always
     * Yes, the bit size is the modulus
     * Messages being encrypted using RSA public-key cryptography must be shorter than the modulus of the public key.