=========================preview======================
(comp170)[2006](f)mid2~PPSpider^_10151.pdf
Back to COMP170 Login to download
======================================================
COMP 170 C Fall 2006
Midterm 2 Solution

Q1. Bob is constructing an RSA key-pair. He .rst chooses p = 11, q = 23. He then calculates a private key d and a public key e. After choosing d he calculates e = 147. His public key is then the pair (n, e) where n = pq = 253.
Alice wants to send Bob some message M (where M is a positive integer < 253). She en-crypts the message using the public key pair (n, e)=(253,147). The encrypted message she sends to Bob is the value M. =5. What is the value M that Bob reads after he de-crypts the message?
To decrypt the encrypted message M. to get M, we need the private key d, which is the multi-plicative inverse of e = 147 in ZT , where T = (p . 1)(q . 1) = 220. In other words, we need d such that
ed mod T = 147d mod 220 = 1.

To decrypt the encrypted message M. to get M, we need the private key d, which is the multi-plicative inverse of e = 147 in ZT , where T = (p . 1)(q . 1) = 220. In other words, we need d such that
ed mod T = 147d mod 220 = 1.

Calculating this inverse, e.g., using the extended GCD algorithm, gives d =3. M can then be computed as:
M =(M.)d mod n =53 mod 253 = 125.

Q2. Consider the equations

x mod27 = 5
x mod68 = 3

1. How many x Z1836 solve both equations? Justify your answer.
Q2. Consider the equations

x mod27 = 5
x mod68 = 3

1. How many x Z1836 solve both equations? Justify your answer.
Since gcd(27, 68) = 1, the Chinese Remainder Theorem guarantees that there exists a unique so-lution for x Z1836 (1836 = 27 68).
2. Give an x Z1836 that solves both equations.

2. Give an x Z1836 that solves both equations.
Let m = 27, n = 68, a =5 and b =3. We denote the multiplicative inverse of m in Zn by m and that of n in Zm by n. The constructive proof for the Chinese Remainder Theorem taught in class gives the solution for x as
x = y mod 1836,

where
y = ann + bmm.

We can use the extended GCD algorithm to .nd r, s Z that satisfy the following equation:
mr + ns = 27r + 68s = gcd(27, 68) = 1.

Since r = .5 and s =2 satisfy the equation, the inverses can be computed as
m = r mod n =(.5) mod 68 = 63 n = s mod m = 2 mod 27 = 2.
We can use the extended GCD algorithm to .nd r, s Z that satisfy the following equation:
mr + ns = 27r + 68s = gcd(27, 68) = 1.

Since r = .5 and s =2 satisfy the equation, the inverses can be computed as
m = r mod n =(.5) mod 68 = 63 n = s mod m = 2 mod 27 = 2.
Hence we have
y =5 68 2+3 27 63 = 5783

and
x = 5783 mod 1836 = 275.
3. Give an x such that x solves both equations and 3000 x 5000.
3. Give an x such that x solves both equations and 3000 x 5000.
275 + k1836 is a solution to the equation for all k. Letting k =2 gives x +2 1836 = 3947, which is in the range 3000 x 5000.
Q3. Answer the following questions. For parts (1)-(3) do not forget to justify your answers. For part (4) do not forget to show your calculations.
1. Is (92100 mod 31)