Question 1. (a) part a We know that p = 31, g = 37, n = pg = 31 * 37 = 1147, e = 11. (i) Encryption My UCO is 408367. We cannot use the whole UCO as a message, because it is of a higher value than n. Therefore, we divide UCO into two parts: mi = 408, ma = 367. Then we encrypt the messages in the following way: ci = mf mod n = 40811 mod 1147 = 149 c2 = m| mod n = 36711 mod 1147 = 564 Therefore, the encrypted UCO is 1495G4. (ii) Decryption To decrypt, we need d such that: e*d = 1 mod [(p-l)(q- 1)] 11 * d = 1 mod 1080 Therefore, d = 491. Then, we can decrypt the messages in the following way: mi = 4 mod n = 1494S1 mod 1147 = 408 m2 = 4 mod n = 5644fll mod 1147 = 367 (b) part b The last two digits of my UCO are 67, therefore in binary: 1000011. We encrypt the message w = (1,0,0,0,0,1,1) by computing X'w1', so the encryption is: X'uF =(393,396,140," 152,435,486,323) (1,0,0,0,0,1,1) = 1202 Then, let's decrypt. It is known that u = 131 and m = 521. (i) First, we compute 131_1 mod 521 = 175. 1 (b) part b The last two digits of my UCO are 67, therefore in binary: 1000011. We encrypt the message w = (1,0,0,0,0,1,1) by computing X'wT, so the encryption is: X'wT = (393,336,140,152,435,486,323) (1,0,0,0,0,1,1} = 1202 Then, let's decrypt. It is known that u = 131 and m = S21. (i) First, we compute 131-1 mod 521 = 175. (ii) Then, we compute: 175 * c mod 521 = 175 * 1202 mod 521 = 387. (iii) To be able to decrypt, we need X that we are able to compute from X'\ X* = u* (ii, X2,13,14,x$. xq. x?) mod m X' = 131 * (ri,x2.x3. x4, z$, z&,xy) mod 521 Therefore, X is equal to: X = (3,7,13,29,59, 127,257) (iv) Finally, we are able to decrypt in the following way: 387 > 257, therefore xt. 1 and our new value is 387 - 257 = 130 130 > 127, therefore x§: 1 and our new value is 130 - 127 = 3 3 < 59, therefore 13: 0 3 < 29, therefore 14: 0 3 < 13, therefore i3: 0 3 < 7, therefore ra: 0 3 = 3. therefore x±: 1 Therefore, the message after the decryption is: 1000011. Question 2. No, these moduli are not safe. We suppose that the device is not perfect and generates some primes more often then the others. Moduli axe then product of two primes, but there are some common primes, therefore the moduli can have the common prime as their gcd. We can easily for every pair (or generally tuple) of generated moduli compute gcd (using euclidean algorithm) and therefore factorize the moduli without bruteforce. We can check: gcd(65201327,134635439) = 8213, therefore we can easily compute 65201327/8219 = 7933 which gives us 65201327 =8219- 7933 and 134635439/S219 = 16381 which gives us 134635439 = 8219 ■ 16381. gcd(122176133,122237737) = 15401, therefore we can easily compute 122176133/15401 = 7933 which gives us 122176133 = 15401 ■ 7933 and 122237737/15401 = 7937 which gives us 122237737 = 15401 ■ 7937. gcd(122237737,99633161) = 7937, therefore we can easily compute 122237737/7937 = 15401 which gives us 122237737 = 15401 ■ 7937 (we already have this in the second step) and 99633161/7937 = 12553 which gives us 99633161 = 7937 ■ 12551 There: was no moduli with trivial common divisors with other moduli therefore there is no secure moduli (we were able to easily factoriz-e all of them). 2 Question 3. Solution: 633917 = 593 ■ 1069. Since n = pq and ^(n) = [p — l)(g — 1), we need to solve the following nonlinear system of two equations and two variables: 633917 = pq 633256= (p-l)(9-l) Prom the second equation, we can expressp asp = pq — q + 1 — 633256 = 633917 — q4-1 — 633256 = 662 — 5. Inserting this in the first equation we get (662 -q)-q = +633317 662 0 such that \x\^ < \gc(x)\ < \x\dc ■ for every randomized polynomial time algorithm .4, and any constant d > 0, there exists an m-d such that for \x\ = m > mj : Pr(A(gc(x)) £ g-1 (tjic{x))} < Furthermore we know that / is strongly one-way function, so we know following: ■ / can be computed in polynomial time — hence there is polynomial time algorithm F which computes / ■ there are d.e > 0 such that |i|e < \f(x)\ < \x\d ■ for every randomized polynomial time algorithm .4, and any constant d > 0, there exists an ru.l siu-li r]l;it ]■:■:■ ..-| = m > ru,; : Pr(A(f(x)) £ / 1 ■/(.»■))) < Let c € {0, 1}" be arbitrary: We will prove the first bullet, that is, we will show that gc can be computed in polynomial time. Consider following algorithm Gc: ■ input x is binary word of length 2n ■ split x into half, call these , x<% ■ compute -4 (13), call the result y ■ concatenate c and y, call the result z ■ return z We can see that this algorithm Gc computes gc and that it is polynomial time, because A is polynomial time and remaining operations are linear in size of input. Hence gc can be computed in polynomial time. 4 We will prove the second bullet, that is, we will find d^.tc > 0 such that < |gc{:r)| ^ l^l^-Notice that this is trivial by choice dc = ec = 1, because size of input and output of gc is 2rt, that is, \x\ = 2n and = 2rt, hence 2n = \x\^ < 2n = \gc(x}\ S |s|**e = 2n. Finally we will prove the third bullet, that is, we will show that for every randomized polynomial time algorithm A, and any constant d > 0, there exists an such that for \x\ = m > mj : We will prove this by reduction: Consider there is algorithm A such that it would not hold, that is, there is constant d > 0 and for all mj there exists \xm\ = m > mj such that Pr(.4(^(a:Tn)) £ 5c-1(gcW)) > ^j- Then consider following algorithm Fa- • input x is binary word of length n ■ concatenate c and x, call the result v ■ compute -4(y), call the result z ■ split z into half, call these z\. z mj there exists arm.lj^m.2 such that Xmri11^,2 = im and therefore Pr(A(gc(xTn)) € g~1{^c{xm))) = Pr(FJi{f(x-m.i)) £ f~ l{f{xm,l)}) > which contradicts our assumption that / is strongly oneway function. Hence there is no such algorithm A. That is, we have proven all three bullets, hence gc is strongly one-way function. 5 Question 5. ia) G' = SGP = ri o l o o l l' 110 0 10 1 0 0 0 0 1 1 1 0 10 10 11 (b) eK(vi, e) = wG" + e (1010) *G' = 1010100 1010100 + 0000100 = 1010000 which is our encoded word. (c) ci = cP~K Since P is orthogonal, it's the same as ci = cPT = (1100110) * PT = 1110010 110 110 0 10 110 10 0 1110 0 1 c\HT = (010)... corresponds to sixth column of H, so c = 1110000 = Since wj = wS. we need to find S~1 and compute ibj * S_1 to get w. wi = 1110 5-1 = 0 0 11 1111 10 10 110 1 (1110) * S 1 = 0110 which is the decoded cryptotext. Question 6. This is clearly some variation of the three-pass protocol, so after the second step, they should continue as follows: 3. Alice computes modular multiplicative inverse of ca: let's call it 4a such that d& * &a = 1 (mod 2™ - 1). Then she computes C,C = Bd^ in GF(2T>) and sends C to Bob. (C = mE=, because Alice now unlocked her "lock" on the message) 4. Bob computes modular multiplicative inverse of let's call it dg such that dg * = 1 (mod 2" - 1). Then he can get m by computing Cia in GF(2") = m. If m was. for example, some encryption key, now the two of them can begin encrypted communication using m. Proof: First, consider the case where rn > 0. All nonzero elements of GF[2n) form a multiplicative group of order 2" — 1. From Lagrange's theorem we know that the order of group element divides order of finite group. In our case this means that for some m in GF(2Ti) if £ is the smallest nonzero integer 6 IV054 2020 David Hofman (456229) Homework 5 such that mx = 1 in GF(2Ti) then z must divide 2n — 1. With the previous argument in mind, we also know that m2"-1 = 1 in GF{2"). It follows that ni'l7"1) = 1 in GF(2") as well, and that This implies that to get m from me in GF{'2?1) we need to find some integer d such that mcrf = mfc(y-l)+l -n gf^), so we want to satisfy the equation de = k(2n — 1) + 1. that is dc = 1 (mod 2™ — 1), in other words we need to find the modular multiplicative inverse of c with respect to modulus 2n — 1. This is exactly what we are doing in steps 3. and 4 when computing d& and d^. We can also be sure that in our case the modular multiplicative inverse of cA or cB with re-—"I i ■ -■ - r mi i. '2;' - 1 ;.lv.\:.v- exists, because \vc haw pnvi< .ii;^1y i-ui; ord t:k.f ;;■/!'.■ - 1 ■ = gcd{eB^ - 1) = 1. To show how it works in practice after the second step: ■ In the third step Alice knows ea and B = (meA)Cs = (mCBYA in GF(2n) She computes dA as described above, then computes C = BdA = [m*B)"AdA = (m^f'211"1^1 = mGB in GF(2"). ■ In fourth stop Bob knows arid C = m''li. he computes as dt-scribed above, then m = C^B = m£BdB = m*f2B-i)+i = m jn GF(2"). He successfully received m. Lastly, the case where m = 0 wasn't previously considered, but CP = 0 in trFfi^1) for any j > 0 , so in this case it works as well. 7