Question 1. (a) Number we want to encrypt must be lower then n, therefore we can divide w = 445620 into two parts, u 29 = xs Xf, = 29 > 36 - 29 = 7 = x3 We have the third and fifth bit equal to 1. Therefore w — 0010100. Question 2. (a) We need to solve the following system of two equations with two variables: 10812= (p- l)(q- 1) 11021 =pg We can do this by expressing p from the first equation p = pq — 10812 — q + 1 = 11021 — 10812 — g+l = 210 — q. Plugging this into the second equation we get the quadratic equation q2 — 2105+11021 = 0. The two possible solutions iji = 107 and 52 = 103 correspond to the fact that p and q are interchangeable and so we obtain the unique factorization 11021 = 107 ■ 103. (b) In order to factor n — 53916647, it is enough to test x > *Jn until x is found such that 2 2 x — n = y . ,/rI = 7342,8 For x = 7343, x2 — n is not a square. For x = 7344, x2 - n — 17689 = y2 is a square. From there p + q = 2x and p — q = 2y. Therefore p = x + y = 7344 + 133 = 7477 9 = x-t/ = 7344 - 133 = 7211 Question 3. Because we know that the corresponding private key was not carefully chosen let's assume that u is x\ . Due to this assumption we can calculate X by ux^ = x\ mod m, so X = (1,5,7,15,31,63,125,251,524,1111). When we want to decrypt the ciphertext (3867, 2085, 2688, 5301. 7390), so we need to compute u~' mod m. To find the inverse we use the extended Euclidean Algorithm and Bczout's identity for u and in, so w_1=67. By multiplying cryptotcxts with u~l and modulo m we get new cryptotext C"=(1377, 1635, 618, 813, 415). First we solve the problem for dt = 1377. 1377 > 1111 = 110 110 = 1111 > 1377 - 1111 = 266 > 251 = xs 266 - 251 = 15 = x4 We have the tenth, eighth and fourth bit equal to 1. Therefore = 0001000101. d2 = 1635. 1635 > 1111 = 110 xw = 1111 > 1635 - 1111 = 524 = x9 We have the tenth and ninth bit equal to 1. Therefore w2 = 0000000011. d3 = 618. 618 > 524 = xg j9 = 618 > 618 - 524 = 94 > 63 = x6 94 - 63 = 31 = zs We have the ninth, sixth and fifth bit equal to 1. Therefore ws = 0000110010. c!A = 813. 813 > 524 = xs x9 = 813 > 813 - 524 = 289 > 251 = x8 xe = 63 > 289 - 251 = 38 > 31 = .r5 W4 = 15 > 38 - 31 = 7 = X'i We have the ninth, eighth, fifth and third bit equal to 1. Therefore «j4 = 0010100110. Cg = 415. 415 > 251 = xa arg = 251 > 415 - 251 = 164 > 125 = x7 xa = 63 > 164 - 125 = 39 > 31 = ao5 x4 = 15 > 39- 31 = 8 > 7 = x3 i2 = 5>8 — 7 = 1 = ^1 We have the eighth, seventh, fifth and third and first bit equal to 1. Therefore vj% = 1010101100. And, in the binary form, solutions B of equations XBT = c' have the form (0001000101, 0000000011, 0000110010, 0010100110, 1010101100). In order to decrypt an English cryptotext, we first decode by 5-bit numbers. Therefore, the resulting plaintext is: BE CAREFUL. Question 4. Since vf = c mod n, we can see that (w\W<2)e — w\ x m| = C\ x mod n. Thus product of (wo plaintexts encrypts to product of ciphertexts of the corresponding plaintexts. Since 321 x 562 = 323 mod 1147 and 321 x 1081 x 562 = 475 mod 1147, wc conclude that the plaintext for 323 is 21 x 33 mod 1147 = 693, and the plaintext for 475 is 21 x 29 x 33 mod 1147 = 598. Question 5. Since /(m) = m + Xjj=i QjPj ant^ ro°ts °f P-) are also roots of QjP} as Q3(...) X 0 = 0, Alice performs the decryption by taking the polynomial received from Bob and evaluating it for v. This yields: I I I f(ra)(v) = m + £ Qj{v)Pj (v) = m + ^ Qj{v) x0 = ra + ^0 = m j=i j=i j=i The trapdoor here is the valuation v. Finding roots for a System of polynomials is NP-HARD, so the attacker can't find it easily. The randomly chosen polynomials Q arc added by Bob so the attacker can't simply subtract. P to get the result. Question 6. First we express n = 22 ■ 1749 +1, so s — 2 and d — 1749, re {0,1,2}. Now we determine whether the required condition xd 5* 1 (mod n) A W, 0 < r < a: xrd ^ -1 (mod n) holds for some x. If it does, n is not a prime. (i) x = 2101 21011749 = 6996 = -1 (mod 6997) 21012 1749 ee 1 (mod 6997) C(2101) does not hold. (ii) x = 3035 C(3035) does not hold. (iii) x = 6101 61011749 = g201 (mod q99v) ^ C(6101) does not hold. (iv) x = 30 3Qi749 _ j ^mod 6g97) ^ c(6101) does not hold. Based on the Rabin Miller's Monte Carlo algorithm, 6'997 is a prime with probability of error equal to 2~4 , that is 6,25%. 5.7 Alice, Bob, and Charlie use the RSA cryptosystem to communicate. Alice has public key £a = 29, n = 20453, Bob's public key is ey — 61, n — 20453, and Charlie has ec — 97, n — 20453. Bob sent the same message m to both Alice and Charlie. Eve intercepted cryptotexts cb->a = 3968 and cb-vc = 6390 sent from Bob to Alice and to Charlie, respectively. Can Eve, who is not using any brute force methods, determine the secret message? Omit the fact that the numbers are small. If your answer is yes, determine m. Justify your reasoning. Solution: We know that m29 = 3968 mod 20453 (1) and m57 = 6390 mod 201.53. (2) First of all wc calculate r)cd{e&, ec) by Extended Euclid algorithm 0ed(29,97) = 1 equal to the sum of all previous elements increased by 1. We obtain a Super-increasing vector X - (1,1 + 1 = 2,1 + 2 + 1 = 4,1 + 2 + 4 = 8,...) (that is X, = 2<_1 for 1 < % < ri). We can see that the last and the biggest element xn = 2" . After we plug this in the equation for the density of a vector, we obtain MX) = U = n = " lo xn and therefore d{X ) < d(X),