Table of Contents
RSA encryption is a widely used method for securing digital communication. It involves generating a pair of keys and using them to encrypt and decrypt messages. Understanding the practical calculations behind RSA helps in grasping how data security is maintained.
Key Generation Process
The first step in RSA is selecting two large prime numbers, typically denoted as p and q. These primes are used to compute the modulus n, which is part of the public and private keys.
Calculate n by multiplying p and q: n = p × q. Then, compute Euler’s totient function, φ(n) = (p – 1) × (q – 1). Choosing an encryption exponent e that is coprime with φ(n) is essential. Common choices for e include 3 or 65537.
The private key exponent d is calculated as the modular inverse of e modulo φ(n). This means solving for d in the equation: d × e ≡ 1 (mod φ(n)).
Message Encryption and Decryption
To encrypt a message, convert it into a numerical format m, where 0 ≤ m < n. The ciphertext c is then computed using the public key (n, e): c = m^e mod n.
Decryption involves using the private key d to recover the original message: m = c^d mod n. This process ensures that only someone with the private key can decrypt the message.
Practical Calculation Example
Suppose p = 61 and q = 53. Calculate n = 61 × 53 = 3233. Then, φ(n) = (61 – 1) × (53 – 1) = 60 × 52 = 3120. Choose e = 17, which is coprime with 3120.
Find d such that d × 17 ≡ 1 (mod 3120). The value of d is 2753. The public key is (n=3233, e=17), and the private key is (n=3233, d=2753).
To encrypt a message m = 65, compute c = 65^17 mod 3233, resulting in c = 2790. To decrypt, compute m = 2790^2753 mod 3233, which yields the original message 65.