The key to happiness is encrypted.

The RSA Algorithm

Fun Fact: The RSA Algorithm was named after its three inventors: Ron Rivest, Adi Shamir and Leonard Adleman, who first published the RSA method in 1977. There are three main phases of the public-key encryption system:

1. Key Generation: Whoever wants to receive secret messages creates a public key (published) and a private key (kept secret). The keys are generated in a way that conceals their construction and makes it ‘difficult’ to find the private key by only knowing the public key.
2. Encryption: A secret message to any person can be encrypted by their public key (that could be officially listed like phone numbers).
3. Decryption: Only the person being addressed can easily decrypt the secret message using the private key.

How do we implement this?

(1.) Generate a pair of keys.

• To generate a pair of keys, two large prime numbers p and q are chosen randomly.
• The product n = pq is calculated. Calculate φ(n)=(p-1)(q-1).
• Choose a private decryption key, d, such that (d, φ(n)) = 1.
• Find a public encryption key, e, so that e·d + φ(n)·f = 1.

(2.) Encrypt the message with the public key. To obtain the encrypted message C from plaintext message M, the following operation is performed:

C = M^e (mod n)

(3.) Decrypt the message with the private key.

To recover the original message from the encryption operation, we compute:

M = C^d (mod n)

Example:

Let p = 3 & q = 11. n = pq = 33

Calculate φ(n)=(p-1)(q-1) = (2)(10) = 20

Choose a private decryption key, d, such that (d, φ(n)) = 1.

Let d = 3

 Find a public encryption key, e, so that e·d + φ(n)·f = 1.

Find e, so that e·3 + 20·f = 1.

Let e = 7

Now, we want to send message “5”, so let M = 5.

C = M^e (mod n)

C = 5⁷ (mod 33) = 5² · 5² · 5² · 5 (mod 33)

≡ 25 · 25 · 25 · 5 (mod 33) = 25 · 25 · 125 (mod 33)

≡ (-8) (-8) (26) (mod 33) ≡ 64 · 26 (mod 33)

≡ (-2) · (-7) (mod 33) ≡ 14 (mod 33)

So our encrypted message C is 14.

Now, to recover the original message from the encryption operation, we compute:

M = C^d (mod n)

M = 14³ (mod 33) = 196 · 14 (mod 33)

≡ (-2) · 14 (mod 33) = -28 (mod 33)

≡ 5 (mod 33)

which is our original message, M.

Exam Time!

Choosing two primes: p=11 and q=13. Let the modulus n=p×q=143. Encrypt the message, M,  “3”, then decrypt it.

 

 

---

 

http://doctrina.org/How-RSA-Works-With-Examples.html