RSA Encryption & Signing by Hand

TL;DR

This guide shows you how to perform RSA encryption and digital signatures manually using small numbers. It’s for understanding the *process*, not practical security – real-world RSA uses huge numbers! We’ll cover key generation, encryption, decryption, signing, and verification.

Key Generation

1. Choose two prime numbers: Let’s pick p = 11 and q = 13. Keep these secret!
2. Calculate n: This is the modulus, found by multiplying your primes: n = p * q = 11 * 13 = 143.
3. Calculate φ(n) (Euler’s totient): This is (p-1) * (q-1). So, φ(143) = (11-1) * (13-1) = 10 * 12 = 120.
4. Choose an integer e: This is the public exponent. It must be between 1 and φ(n), and have no common factors with φ(n). Let’s pick e = 7 (it shares no factors with 120).
5. Calculate d: This is the private exponent. It’s the modular multiplicative inverse of e modulo φ(n). In other words, find a number d such that (e * d) % φ(n) = 1. We need to solve (7 * d) % 120 = 1. Using the Extended Euclidean Algorithm or trial and error, we find d = 103.
6. Public Key: (n, e) = (143, 7). You can share this with anyone.
7. Private Key: (n, d) = (143, 103). Keep this *absolutely secret*.

Encryption

1. Get the message: Let’s encrypt the message M = 5.
2. Encrypt using the public key: Calculate C = M^e % n. So, C = 5⁷ % 143 = 78125 % 143 = 98.
3. Ciphertext: The encrypted message is C = 98.

Decryption

1. Get the ciphertext: We have C = 98.
2. Decrypt using the private key: Calculate M = C^d % n. So, M = 98¹⁰³ % 143. This is a bit tricky to do by hand! You’ll need modular exponentiation (repeated squaring). The result will be 5.
3. Original Message: The decrypted message is M = 5.

Digital Signature

1. Get the message: Let’s sign the message M = 5 again.
2. Sign using the private key: Calculate S = M^d % n. So, S = 5¹⁰³ % 143 = 97. This is our signature.
3. Signature: The digital signature is S = 97.

Verification

1. Get the message and signature: We have M = 5 and S = 97.
2. Verify using the public key: Calculate V = S^e % n. So, V = 97⁷ % 143 = 5.
3. Check Verification: If V equals the original message M, the signature is valid! In our case, 5 = 5, so the signature is verified.

Important Notes

• This example uses very small numbers for simplicity. Real-world RSA uses primes hundreds of digits long to prevent attacks.
• Modular exponentiation (calculating things like M^d % n) is done efficiently using algorithms like repeated squaring.
• The security of RSA relies on the difficulty of factoring large numbers.