A toy RSA
Build RSA with your own hands. You are given two primes p and q and a public exponent e coprime to φ = (p − 1)(q − 1). The public key is the pair (N = p·q, e), the secret key is the number d, the inverse of e modulo φ. Find N and d and encrypt the messages: the cipher of a number x is xe mod N.
Real RSA takes primes a thousand bits long and always mixes the message with random bytes before encrypting; here the numbers are small and the scheme is a textbook one. But the arithmetic is exactly the same.
Input
The first line holds p, q, e and the number of messages k (p, q are distinct primes less than 2³¹; 3 ≤ e < φ; 1 ≤ k ≤ 20,000). The second holds k messages, integers from 0 to N − 1.
Output
The first line holds N and d (0 < d < φ). Then k lines: the ciphers of the messages in order.
Examples
Example 1
61 53 17 3 65 0 3232
3233 2753 2790 0 3232
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 5 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
How do you find the inverse of e modulo φ? Will Fermat’s little theorem, which the article used to compute an inverse, do?
2Hint 2
If you write in Go: N can be almost 2⁶², and x·x mod N requires multiplying two such numbers. Does the product fit in 64 bits?
3The idea
The inverse modulo φ is given by the extended Euclidean algorithm. Fermat will not do here: φ = (p−1)(q−1) is even and certainly not prime. Encryption is fast exponentiation modulo N. Why decryption cd returns the message is explained by Euler’s theorem: e·d = 1 + k·φ, and xed ≡ x (mod N).
4Walkthrough
Compute N and φ, then d by extended Euclid, and bring it into the range from 0 to φ − 1 (the algorithm may return a negative coefficient). Raise each message to the power e modulo N.
In Python pow(x, e, N) is enough: integers can be arbitrarily long. In Go the product of two remainders modulo N ≈ 2⁶² takes up to 124 bits, so multiply with bits.Mul64, which returns the high and low 64 bits of the product, and take the remainder with bits.Div64. The same technique works in any language with 64-bit integers.
The Python reference solution also checks that cd mod N returns the original message: a good way to make sure d was found correctly.
4+Solution
5Complexity
O(log φ) for the extended algorithm and O(log e) multiplications per message: with e = 65,537 that is 19 multiplications, 17 squarings and 2 extra ones. O(k log e) in all.
6Common mistakes
- The inverse by Fermat. eφ−2 mod φ is the inverse only for a prime modulus. The very first example catches it.
- Overflow in Go.
a * b % nfor 62-bit numbers silently loses the high bits, and the ciphers come out wrong on the large tests. - A negative d. Extended Euclid may give a negative coefficient; it has to be reduced modulo φ.