CS2050 L19 RSA Encryption
Overview
Abrahim Ladha explains RSA as an application of number theory that addresses the key-sharing problem in symmetric cryptography. The lecture builds RSA from two large primes, the modulus n = pq, Euler's totient, and modular inverses, then shows how modular exponentiation enables encryption and decryption while factoring n would reveal the private key. It also connects RSA to HTTPS hybrid encryption, discusses factoring and quantum-computing caveats, and introduces Diffie-Hellman key exchange based on the discrete-log problem.
Key takeaways
- RSA key generation makes the public modulus n = pq easy to compute but is designed to make recovering p and q from n computationally infeasible.
- The RSA public key consists of n and e, while the private exponent d is calculated as the inverse of e modulo φ(n), with φ(n) = (p − 1)(q − 1).
- Euler's theorem proves RSA decryption correctness for messages relatively prime to n; the algebraic correctness argument is separate from the unproven security assumption.
- Factoring n breaks RSA because p and q reveal φ(n), which lets an attacker compute d, but RSA security has not been proven equivalent to factoring hardness.
- Public-key cryptography is computationally slower than symmetric encryption, so HTTPS commonly uses it to establish a session key and then uses fast symmetric encryption for data.
- Diffie-Hellman lets Alice and Bob derive the same g^(xy) mod p from exchanged powers without sending x or y, relying on the assumed hardness of discrete logarithms.
Chapters
- RSA is named for Ron Rivest, Adi Shamir, and Leonard Adleman, and applies number-theoretic results to secure communication.
- The cryptographic model has Alice and Bob communicating while an adversary, Charlie, observes messages in transit.
- Security depends on the threat model: the example protects against an eavesdropper, not a malicious Alice or Bob.
- A symmetric scheme uses key generation G, encryption E, and decryption D, with Alice and Bob sharing the same key K.
- The adversary sees ciphertext C, while the desired security goal is to conceal the message M and the key K.
- Sharing K securely is the core difficulty: if a codebook or key leaks, an adversary may decrypt both past and future messages.
- AES is described as a fast symmetric cipher, motivating the search for a way to establish keys without meeting in secret.
- Public-key key generation outputs a paired public key PK and secret key SK; anyone can encrypt with PK, but only SK decrypts.
- Bob publishes PK, Alice encrypts a message with it, and Bob recovers the message using SK.
- The padlock analogy captures the asymmetry: anyone can close the lock, but only the key holder can open it.
- A public-key scheme must protect the message and secret key even though the adversary can observe PK and the ciphertext.
- RSA relies on the assumption that recovering large primes p and q from their product n = pq is computationally infeasible.
- The lecture distinguishes computational infeasibility from impossibility: a task is treated as infeasible when no polynomial-time algorithm is known.
- Many familiar number-theory operations, including GCD computation and modular arithmetic, are efficient, while factoring a product of two large primes is believed to be hard.
- The relationship between factoring hardness and RSA security is an assumption, not a proof that every way of attacking RSA requires factoring.
- For n = pq, at least one factor is at most √n, so a basic trial search could examine candidate divisors up to that bound.
- A roughly 4,000-bit n has a square root on the order of 2,000 bits, making exhaustive search astronomically large.
- Adding a bit to n roughly doubles a brute-force search range, creating a computational asymmetry between multiplying known primes and recovering them.
- Generate two large primes p and q, compute the public modulus n = pq, and calculate φ(n) = (p − 1)(q − 1).
- Choose e relatively prime to φ(n), then compute d as the modular inverse of e modulo φ(n).
- The public key is the pair (n, e); d is the secret key, and computing φ(n) from n is expected to require factoring n.
- The Extended Euclidean Algorithm can compute the modular inverse d once e and φ(n) are known.
- Represent a message M as a number and encrypt it as C = M^e mod n using the public key.
- Decrypt with the private exponent using M = C^d mod n.
- Repeated squaring computes large modular powers efficiently, avoiding a number of multiplications proportional to the exponent.
- Messages must fit the modulus encoding; practical systems handle longer data through encoding and hybrid-encryption techniques.
- Because ed ≡ 1 mod φ(n), there is an integer k such that ed = kφ(n) + 1.
- For messages relatively prime to n, Euler's theorem gives M^φ(n) ≡ 1 mod n, so decrypting M^e returns M modulo n.
- The proof has a condition: Euler's theorem directly applies when gcd(M, n) = 1, which is why message encoding and edge cases matter.
- Correct decryption establishes RSA's algebraic functionality, but it does not by itself establish security.
- If an adversary factors public n into p and q, they can calculate φ(n) = (p − 1)(q − 1).
- With φ(n) and public exponent e, the adversary computes d as e's inverse modulo φ(n), then decrypts ciphertexts.
- This shows that easy factoring breaks RSA, but the converse is not proven: RSA might have attacks that do not factor n.
- The practical security claim therefore rests on a hardness assumption rather than a theorem that RSA is unbreakable.
- Ladha inspects a browser certificate for gatech.edu and identifies an RSA public key represented by a modulus and exponent.
- The demonstrated certificate uses a small public exponent, e = 17, as an example of speeding up public-key operations.
- RSA is computationally slower than symmetric encryption, so modern communication commonly uses public-key cryptography to establish a session key, then AES or another symmetric cipher for data.
- The HTTPS example illustrates how certificate exchange and standardized parameters connect mathematical cryptography to browser security.
- RSA factoring challenges benchmark security by modulus size; the lecture contrasts sub-1,000-bit challenge numbers with commonly discussed RSA-2048 keys.
- A sufficiently capable fault-tolerant quantum computer running Shor's algorithm could factor RSA moduli, though building such a machine is a separate engineering challenge.
- Elliptic-curve cryptography changes the underlying group and relies on different hardness assumptions, often allowing smaller keys and ciphertexts.
- Post-quantum cryptography explores alternatives based on assumptions such as lattice problems rather than relying on RSA factoring.
- A finite group is cyclic when one generator's powers produce every group element; modulo 7, 3 generates the nonzero residues.
- The discrete-log problem asks for x given g, the modulus or group, and g^x; modular exponentiation is easy, while reversing it is assumed hard in suitable groups.
- In Diffie-Hellman, Alice and Bob exchange g^x mod p and g^y mod p, then independently compute the shared value g^(xy) mod p.
- An eavesdropper sees the public parameters and both exchanged powers, but recovering the shared secret is expected to require solving the discrete-log problem.
Transcript excerpt
0:04 Uh this is CS uh 2050. The topic of today is cryptography. Specifically an algorithm known as RSA. RSA stands for the three authors Rivist, Shamir and Adelman. This is like a foundational result. Um few things. one the why are we talking about this as number theory as you'll see the algorithms are just number theory they're just an application of number theory I've told the story already but I'll tell it again worrying Hardy was this mathematician and he was uh alive during World War I as a lot of mathematicians were and he had like uh a moral opposition to uh this war and so
0:54 like you know when you're pursuing mathematics you're like what do you want to go into And uh if you did something practical then you were you know basically forced to participate in the war in some way planning or something but if uh but number theory was a kind of domain of mathematics that was not practical actually it's kind of about um as we've done it I mean if you can think of the theorems we've done so far the Chinese remainder theorem for mats and oilers theorems what possible application could you find for those things maybe you can't find an application and for that reason it's interesting there's like an aesthetics value there it's just about the relationship that the divisibility of numbers has. But uh and so for 2,000 years math uh some of these theorems are very very old. We had no idea about how to apply these theorems to any kind of practical problem. They were purely
1:41 aesthetic. And of course, no ma field of math can ever remain purely unapplied. So RSA is one of the first real applications of number theory into like
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Abrahim Ladha.