One point out of 40 on the inal will be assigned for your pdf upload being organized and easy to read (for example, the question numbers should be clearly indicated and should be in consecutive order 1, 2, ...).

1. Assume Bob,s RsA modulus is N = 119 = 7 . 17 and his encryption exponent is e = 91.

a. compute Bob,s secret decryption exponent d using the Extended Euclidean Algorithm. show your work. (Express your inal answer d as a positive number.)

b. How many steps will it take for Bob to recover Alice,s secret message using the Fast power- ing Algorithm, if computing a product modulo N counts as one step?

2. Assume Eve knows an RsA modulus N and an encryption, decryption pair e and d. Describe in as much detail as possible the procedure for using this information to eficiently factor N.

3. For each of the tasks below, identify the computation it requires as well as the fast algorithm used for performing that computation.  some computations and algorithms may be used more than once, and some may not be used. No justiication is necessary.

Steps in the RSA algorithm.

1. Bob chooses e relatively prime to Ψ(N). (Assume Bob knows Ψ(N) already.) 2. Alice computes c = 从e  mod N.

3. Bob computes d such that e . d 三 1 mod Ψ(N). (Assume Bob knows Ψ(N) already.) 4. Bob computes 从 from d and 从e  mod N.

computation.

a. gcd

b. factorization into primes

c. e-th root modulo m (for some modulus m)

d. modular exponentiation

e. discrete logarithm

f. multiplicative inverse modulo m (for some modulus m)

Algorithm.

i. Fast powering Algorithm (also called square-and-Multiply)

ii. Euclidean Algorithm

iii. Extended Euclidean Algorithm

iv. No known fast algorithm

4. Give three examples of computations (like what is described in the “computations” list above) that are relevant to Math 173A and for which there is no known fast algorithm.  (For example, for which we would not expect a modern computer to be able to perform that calculation on a general 500-bit input.) For each of your three examples, say in a few wordshow it is relevant to Math 173A.

7. In the context of RSA, which one of the following is typically easy to compute (meaning it could

be completed quickly on a computer)? Briely explain why that computation is easy.

i. Given N (but not its factorization N = p . q), ind Ψ(N), where Ψ denotes the Euler phi- function.

ii. Given N (but not its factorization N = p . q), inde such that gcd(e, Ψ(N)) = 1. iii. Given N (but not its factorization N = p . q),e, and x, ind xe  mod N.

iv. Given N (but not its factorization N = p . q) and e, indd such that ed 三 1 mod Ψ(N).

8. Assume N = pq is an RSA modulus, assume a2  三 b2  mod N, and assume a 三 — bmod N. what can you say about gcd(a 十 b, N)? Explain your answer.