Practice question · Put in order
Order the stages of the RSA idea.
- Encrypt a message by modular exponentiation mod n
- Choose two large secret primes p and q
- Publish their product n while keeping p and q secret
- Security holds because factoring n back into p and q is infeasible
- Decrypt using an exponent derived from p and q
Hints
- The keys must exist before anything can be encrypted with them.
- The security claim is a statement about the whole finished system, so it comes last.
Show the answer
- Choose two large secret primes p and q
- Publish their product n while keeping p and q secret
- Encrypt a message by modular exponentiation mod n
- Decrypt using an exponent derived from p and q
- Security holds because factoring n back into p and q is infeasible
Why
Primes first, then the public product, then encryption, then decryption using the private information, and finally the security argument. Every stage uses a tool from this unit: primes, modular exponentiation, inverses (via Fermat and Euler), and the hardness of factoring.
Practise Number Theory in Action
The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Number Theory in Action
- The infinite geometric series 1 + 1/2 + 1/4 + 1/8 + … has infinitely many positive terms and sums to exactly…
- An ISBN-10 has digits d1 through d10 and must satisfy: 1 x d1 + 2 x d2 + ... + 10 x d10 is congruent to 0 mod…
- A hash table has 13 slots and uses the hash function 'key mod 13'. Which slot does the key 1000 land in?
- Sort each application by the number-theoretic idea it chiefly rests on.
- Complete the source of RSA's security.
- Select every idea from this unit that RSA depends on.
- Zeno argued you can never cross a room: first half the distance, then half the rest, forever. Why does the…