cryptography

Homework 6: Security of Public Key Cryptography

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.

Content Objectives - Module 6

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

1. apply Shanks’s Babystep-Giantstep algorithm to solve the discrete log problem, and

2. apply Pollard’s p − 1 factorization algorithm or other techniques to factor RSA moduli

Proficiency Problems

1. (Obj. 1) Use Shanks’s babystep-giantstep method to solve the discrete log problem 2x ≡ 83 mod 107. You may use computing technology as you see fit to expedite the process; just include whatever code you use as part of your solution.

2. (Obj. 1) Use Shanks’s babystep-giantstep method to solve the discrete log problem 156x ≡ 116 mod 593. You may use computing technology as you see fit to expedite the process; just include whatever code you use as part of your solution.

3. (Obj. 2) Use Pollard’s p − 1 method to factor n = 220459. You may use computing technology as you see fit to expedite the process; just include whatever code you use as part of your solution.

4. (Obj. 2) Use Pollard’s p − 1 method to factor n = 12637211 using a = 15 (instead of a = 2). You may use computing technology as you see fit to expedite the process; just include whatever code you use as part of your solution.

5. (Obj. 2) Say N = 25777. Compute the values of N + 12, N + 22, N + 32, N + 42, . . . until you find a value N + Y 2 that is a perfect square X2. Use the values of X and Y to factor N.

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.

6. Suppose that p is a prime. Define a public-key scheme with the encryption function ek(m) = m e

mod p for a public key k = (e, p) and a plaintext message m with 1 ≤ m < p. Give the private key and the decryption function. Show that this scheme is insecure.

7. Write a program that inputs an odd composite number n > 3 and a positive integer a and applies Pollard’s p − 1 factorization algorithm. Use your program to factor 1575409999.

8. Write a program that inputs values of g, h, and N and applies Shanks’s babystep-giantstep algorithm to solve gx ≡ h mod N. Use your program to solve 650x ≡ 2213 mod 3571.