Problems for Homework 1 MICS W202 - Cryptography
Problem 1. Alice wants to encrypt the number 13 using RSA and send it to Bob.
(a) If Bob’s public key e = 3, and N = 1081, what does Alice send to Bob?
(b) If Bob’s private key d = 675, show the steps Bob would perform to decrypt the message; does he get 13 as
expected?
Note: these numbers are small enough that you shouldn’tneed Sage for the calculations.
(a) 133 ≡ 2197 ≡ 35 (mod 1081).
(b) 35675 ≡ 13 (mod 1081) via wolframalpha, so yes!
Problem 2. In order to send text using RSA, it is necessary to perform some type of text-to-number encoding first.
For this question, we’ll use a simple 2-digt encoding scheme: a → 01, b → 02, c → 03, . . . , z → 26
So for example, the text ”hello” is encoded as 08 05 12 12 15, or 805,121,215 after removing spaces.
(a) Alice wants to encode the message “hi” so she can send it to Bob. What is the numeric encoding of ”hi” using
our simple scheme?
(b) Alice wants to send this encoded message to Bob using RSA. Bob’s public key e = 7, p = 1003001, and
q = 1000033. What does Alice send to Bob?
(c) What algorithm would Bob use to calculate his decryption key d?
(d) Bob calculates his decryption key d and gets d = 716451497143. Show Bob’s work, and decrypt the message
from Alice; did you get the encoded message that Alice made in part (a)?
Note: If the numbers are too big, try using wolframalpha
Note2: Remember, since the encoding gives each letter 2 digits, you may need to add a leading 0 to complete the
decoding.
(a) By our scheme, h → 08, and i → 09, so hi → 0809 = 809 .
(b) 8097 ≡ 253100088695 (mod 1003034099033). Note: 1003034099033 = 1003001 × 1000033.
(c) The Extended Euclidean Algorithm.
(d) 253100088695716451497143 ≡ 809 (mod 1003034099033) via wolframalha.
Since each character is encoded as 2 digits, we must be missing a leading 0 : 809 = 0809 → hi; so yes!
Problem 3. Explain in a few sentences (or equations) why ed ≡ 1 (mod (p − 1)(q − 1)) and not ed ≡ 1 (mod pq).
It’s not a typo! If we’re working (mod N ), exponents are reduced (mod φ(N )) as a result of the Euler-Fermat
theorem. Note that in RSA, e and d are exponents, so ed gets reduced (mod φ(N )). Since N = p × q, we know that
φ(N ) = (p − 1) × (q − 1). So ed is reduced (mod (p − 1)(q − 1)).
Another solution is that if ed ≡ 1 (mod N ), then it would be trivial to break private keys. Since e and N are
both public, an attacker can simply compute d ≡ e−1 (mod N ) and be able to read all their victim’s mail.
Page 1
Problems for Homework 1 MICS W202 - Cryptography
Problem 4. Prove that m is prime if and only if φ(m) = m − 1.
Taken from Hoffstein 1.21
Note: φ() is Euler’s Totient function.
Note: this is asking us to prove two statements:
(⇒) If m is prime, then φ(m) = m − 1, and
(⇐) If φ(m) = m − 1, then m is prime.
(⇒) Assume m is prime. That means that its only divisors are 1 and m. Therefore, m doesn’t share any
common factors with any numbers less than itself. That is, gcd(m, x) = 1 for 1 ≤ x ≤ (m − 1). Note that there are
m − 1 of these numbers. This is precicely what φ(m) is counting, so φ(m) = m − 1.
(⇐) Assume φ(m) = m − 1. The definition of φ(m) is the number of integers between 1 and (m − 1) that are
relatively prime to m. But there are only (m − 1) integers between 1 and (m − 1) in total, so m is relatively prime
to all integers less than itself. Since m has no common factors with any number between 1 and (m − 1), m must
be prime.
Problem 5. Compute the following values; show your work:
(a) φ(6)
(b) φ(9)
(c) φ(15)
(d) φ(17)
Taken from Hoffstein 3.4
(a) φ(6) = 2
(b) φ(9) = 6
(c) φ(15) = 8
(d) φ(17) = 16
Page 2