RSA is a public key cryptography method that lets people send secure messages without first sharing a secret password. Its security comes from a one-way math idea: multiplying two large primes is easy, but factoring their product is extremely hard when the primes are huge. This makes RSA a powerful example of number theory used in real digital communication.
It also shows why modular arithmetic is more than a classroom topic, since it helps protect bank transactions, messages, and software updates.
In RSA, a public key is used to encrypt a message, while a related private key is needed to decrypt it. The keys are built from two prime numbers p and q, their product n = pq, and Euler's totient phi(n) = (p - 1)(q - 1). A public exponent e is chosen so it shares no factors with phi(n), and the private exponent d is chosen so ed = 1 mod phi(n).
Encryption and decryption work because modular exponentiation has a special inverse structure when the key values are chosen correctly.
Understanding Math: Cryptography Math (RSA Basics)
A useful way to picture RSA is as a clock with a fixed number of positions. After reaching the final position, counting wraps back to zero. This is modular arithmetic.
Large powers would be impossible to write out in full, so computers repeatedly multiply, reduce by the clock size, then continue. A fast method called repeated squaring makes this practical.
It builds powers by squaring a number, reducing the result each time, then combining only the needed pieces. This means a computer can handle very large exponents without ever storing the enormous ordinary power.
The key relationship works because the encryption exponent and the private exponent are carefully matched. Their product leaves a remainder of one after division by the totient value. For message values that share no factor with the modulus, Euler's theorem shows that raising the message to this combined power returns the same remainder.
The full RSA proof handles the remaining message values by considering each prime separately. The Chinese remainder theorem is important here.
It says a result can be reconstructed from its remainders when divided by the two secret primes. This theorem helps explain why decryption succeeds, and it lets real systems decrypt faster by working with smaller numbers.
Messages are not usually turned directly into one giant number and encrypted with plain RSA. Plain RSA would give the same ciphertext whenever the same message is used with the same public key. That pattern would leak information.
Modern RSA encryption adds carefully chosen random padding before the mathematical operation. One common design is called OAEP. The padding makes equal messages produce different ciphertexts and blocks several known attacks.
RSA is often used only to protect a short random session key. The session key then encrypts the actual files, web page data, or video call traffic with a faster symmetric cipher.
RSA can protect identity as well as secrecy through digital signatures. In a signature system, the private key processes a short fingerprint of a document called a hash. Anyone with the public key can check that signature.
A valid check shows that the document has not changed since signing and that the holder of the private key approved it. Students meet this idea when a browser checks a secure website certificate or when a device verifies a software update. The mathematics is strong only when the implementation is careful.
Weak random number generation, reused primes, leaked private keys, or missing padding can defeat RSA even if the formulas are correct. When learning it, focus on the difference between a mathematical proof, an efficient algorithm, and a secure real-world system.
Key Facts
- RSA starts by choosing two primes p and q, then computing n = pq.
- For two distinct primes, Euler's totient is phi(n) = (p - 1)(q - 1).
- The public key is (n, e), where gcd(e, phi(n)) = 1.
- The private key uses d, where ed = 1 mod phi(n).
- Encryption uses c = m^e mod n, where m is the message number and c is the ciphertext.
- Decryption uses m = c^d mod n, which recovers the original message number.
Vocabulary
- Prime number
- A prime number is a whole number greater than 1 with exactly two positive factors, 1 and itself.
- Modular arithmetic
- Modular arithmetic studies remainders after division, such as 17 mod 5 = 2.
- Euler's totient
- Euler's totient phi(n) counts how many positive integers less than or equal to n are relatively prime to n.
- Public key
- A public key is the pair of numbers shared openly so others can encrypt messages for the key owner.
- Private key
- A private key is the secret number used to decrypt messages that were encrypted with the matching public key.
Common Mistakes to Avoid
- Using p and q that are not prime, which breaks the totient formula phi(n) = (p - 1)(q - 1) and makes the key construction invalid.
- Choosing e without checking gcd(e, phi(n)) = 1, which is wrong because e must have a modular inverse for a private key d to exist.
- Treating mod as ordinary division, which is wrong because a mod n means the remainder after division by n, not the quotient.
- Trying to encrypt a message number m that is greater than or equal to n, which is wrong in basic RSA because message blocks must satisfy 0 <= m < n.
Practice Questions
- 1 Let p = 5 and q = 11. Compute n, phi(n), and decide whether e = 3 is a valid public exponent.
- 2 For RSA with n = 33 and e = 3, encrypt the message m = 4 by computing c = 4^3 mod 33.
- 3 Explain why RSA can make the public key visible to everyone while still keeping the private key secret.