RSA encryption and decryption

Symbolics

• p and q are two very large primes
• n = p * q : Modulus
• phi = (p-1) * (q-1) : Totient
• e Public Key: is the prime number chosen in the range [3, phi(n)]
• d Secret Key

Calculate d and Encrypt the message

1. using extended-Euclid's algorithm to find the resulting equation when gcd = 1: it should always look like this:
2. 1 = (a) * phi + (b) * e
3. And d = phi * k - b (k is any integer that could make d > 0)
4. To verify: e * d = 1 mod phi, this could be done easily
5. Encrypt the message using public key e and n:
6. M ^ e mod n
7. the result C is the encrypted message

Decrypt C using a private key

1. M = c ^ d mod n
2. Sometimes it's being called the signature sign

---

Last update: February 20, 2022