RSA
Generating an RSA key pair on small numbers (n, totient, e, d), encrypting and decrypting by modular exponentiation, telling what is public from what stays secret, and understanding why factoring protects the encryption.
- 29 cards
- 7 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- The steps
- Scenarios
- Understand
A few cards from the deck
Public-key cryptography: what is it?
Show the answer
A system where each person holds two linked keys: one, given to everyone, is used to write to them; the other, kept by them alone, is used to read.
It removes the need to share a secret in advance: Bob publishes his public key, and anyone can send him a message that only he can decrypt.
We pick p = 7 and q = 13. What is φ(n) for n = p × q?
72719120
Show the answer
72φ(n) = (p − 1)(q − 1) = 6 × 12 = 72. 91 is n itself, 20 is p + q, and 71 comes from n − p − q, which forgets the +1 of n − p − q + 1.
With the public key (n, e), a message m is encrypted by computing c = m… mod n; with the private exponent d, it is recovered by m = … mod n.
Show the answer
With the public key (n, e), a message m is encrypted by computing c = m^e mod n; with the private exponent d, it is recovered by m = c^d mod n.
Both operations are modular exponentiations: raising to the power e then d amounts to raising to e × d, which is 1 modulo the totient, so we get m back.
Euler's totient: what is it?
Show the answer
The number of integers from 1 to n that are coprime with n; for n = p × q with p and q prime, it equals (p − 1)(q − 1).
For p = 3 and q = 11, n = 33 and it equals 2 × 10 = 20. It is easy to compute when you know p and q, not when you only know n.