cryptography

Homework 5: RSA

Purpose

This homework is designed to do several things:

• The proficiency problems may become part of your portfolio that demonstrates meeting the content objectives of the course.

• Doing challenge problems and submitting them (and their revised version(s)) demonstrates some of our overall objectives.

• Submitting your check in memo and homework problems are an opportunity to get feedback from Dr. Bolkema.

Instructions

Do as many of the proficiency problems as you feel necessary to meet the objectives. The challenge problems are optional but encouraged. Recall that you can submit up to three problems per week for direct feedback from Dr. Bolkema.

Submit a check-in memo by Friday at noon (under the check in memos tab on Blackboard) by Friday at noon that describes your progress on these problems (and some other things). There are specific questions to answer there. This goes privately to Dr. B who will then give you feedback.

Content Objectives - Module 5

By doing this homework you will demonstrate that you are able to

1. apply Fermat’s Little Theorem and Euler’s Theorem to solve congruencies modulo pq, and

2. implement RSA encryption and decryption for given values.

Proficiency Problems

1. (Obj. 1) Solve the following congruences.

(a) x19 ≡ 36 mod 97. (b) x137 ≡ 428 mod 541 (c) x73 ≡ 614 mod 1159 (d) x751 ≡ 677 mod 8023 (e) x38993 ≡ 328047 mod 401227 (Hint: 401227 = 607 · 661.)

2. (Obj. 1) For each of the given values of N = pq and (p− 1)(q − 1), determine p and q. (a) N = pq = 352717, and (p− 1)(q − 1) = 351520 (b) N = pq = 77083921, and (p− 1)(q − 1) = 77066212. (c) N = pq = 109404161, and (p− 1)(q − 1) = 109380612. (d) N = pq = 172205490419, and (p− 1)(q − 1) = 172204660344.

3. (Obj. 2) Consider an RSA cryptosystem with modulus N = 427 and public exponent e = 5.

(a) Encrypt m = 100.

(b) Factorize N and determine the private key d.

(c) Decrypt the ciphertext and check that the result is m = 100.

4. (Obj. 2) Alice publishes her RSA public key: modulus N = 2038667 and exponent e = 103.

(a) Bob wants to send Alice the message m = 892383. What ciphertext does Bob send to Alice?

(b) Alice knows that her modulus factors into a product of two primes, one of which is p = 1301. Find a decryption exponent d for Alice.

(c) Alice receives the ciphertext c = 317730 from Bob. Decrypt the message.

Challenge Problems

Recall you can submit as many drafts as you want of a challenge problem. Justify your answers with complete sentences explaining your reasoning.

5. Suppose that it is desired to create an RSA cryptosystem using the two primes p = 67 and q = 37.

(a) Determine the smallest encryption exponent that is greater than 1000 and could be used for such an encryption exponent. Use it to encrypt the plaintext message P = 2012.

(b) What is the decryption exponent d for the RSA system of part (a)? Decrypt the ciphertext message C = 2095.

6. Bob’s RSA public key has modulus N = 12191 and exponent e = 37. Alice sends Bob the ciphertext c = 587. Unfortunately, Bob has chosen too small a modulus. Help Eve by factoring N and decrypting Alice’s message. (Hint: N has a factor smaller than 100.)

7. The Euler phi function φ(N) is the function that counts the number of positive integers less than N and relatively prime to N; that is,

φ(N) =| {0 ≤ k < N : gcd(k,N) = 1} | .

(a) Evaluate φ(6), φ(9), φ(15), and φ(17).

(b) If p is prime, what is the value of φ(p)?

(c) Prove that aφ(N) ≡ 1 mod N

for all integers satisfying gcd(a,N) = 1. (Try to follow the structure of the proof of Fermat’s Little Theorem we went through in class!)