Question 1. See tables in IS. Question 2. Using Chinese remainder theorem, which says that for our system of congruences: x = a\ (mod rri\) ~+ x = 8 (mod 17) x = Ci2 (mod m2) x = A (mod 19) x = 03 (mod 1713) a; = 19 (mod 23) there is one unique solution: x = ai&i&i +o,2''l2P? +«-3030.3 moa mimjmj), where b^ =-A b, is modular inverse 01 bf,-. mfe We also know that a;j/ = (mod n) y = z (mod n). Thus: bx = 19 * 23 = 437 ~* 43767J = 1 (mod 17) 1267J = 1 (mod 17) — 67J = 10 (*) b2 = 17 * 23 = 391 ~> 3916.7J = 1 (mod 19) 1167J = 1 (mod 19) 67 1 = 7 (*) 63 = 17 * 19 = 323 32367J = 1 (mod 23) ~* 67J = 1 (mod 23) -» 67J = 1 Then x = 8 * 437 * 10 + 4 * 391 * 7 + 19 * 323 (mod 7429) = 52045 (mod 7429) = 42. (*) - find these as Bczout coefficients using Extended Euclidian algorithm Or we could just write them out and see: 8 + 17&i ~» 8,25,42,... 4 + 19fc2 ~* 4,23,42,... 19 + 23fe ~* 19,42,... Question 3. (a) Kab = 9a{ta,sb) — a,A*TB + OA* SB = ((a * rA) + (b * sa)) *rD + ((b * rA) + (c* sA)) * Sb — (a * r \ * i'r) + (b * sa * r3) + (b * rA * sB) + (c * sA * sB) = ((a * rB) + (b * sB)) * rA + ((& * rB) + (c* sB)) * sA = (aB * rA) + (bB * sA) = 9B{rA,sA)) = KBA (b) In my opinion is this protocol less secure than the original protocol. au = (a + b * r'u) in the original protocol, wc can also see it as a\j = (a * 1 + b * ru) or arj = (a * (stj = 1) + b * tu) it means that gcd(su,ru) = 1 In this version ay — (a * r\j + b * S[/), so and ry are swapped and srj is not only 1, but some other number < p. I would say that the threat is when gcd(su,rrj) ^ 1 as aij,bu and also the key could be divided by the gcd, which is a security issue. Question 4. (a) We know that p = 3 mod 4 and q = 3 mod 4: therefore, = 3 mod 8 or p = 7 mod 8 and q = 3 mod 8 or g = 7 mod 8. Since p / ±? mod 8, if p = 3 mod 8, then q = 7 mod 8, and vice-versa. In our case, N — p x q. then by definition, A = 3 x 7 mod 8 = 21 mod 8 f-> JV = 5. As given here (https://en.wikipedia.org/wiki/Jacobi_symbol) in the statement 8 of the section /2, , ,.»£=1 fl if n = 1,7 (mod 8), properties, we have (-) = (—1) 8 = ^ I —1 if n = 3, 5 (mod 8). Since, in our case, N = 5 mod 8, we can deduce that (^) = —1. (b) The Jacobi symbols for x, N — x, 2x and N — 2x are respectively (f;), (NpfX)■ (77) and (A iv2x) - can rewrite some of them: N -x\ _ f-x + N\ _ f-x 2x\ _ ( 2 N-2x\ f-2x + N\ f-2x\ ( 2\ (-x since N = 1 mod 4 = — 1 x ( — I since A = 1 mod 4 Ary V N } \ N J \N) \N Therefore, if (§) = 1, then (^) = 1, and on the contrary (77) = -1 and (^r2) = -1 (and vice-versa). In such a case, neither 2x nor JV — 2x are square modulo A. Let us suppose that, for a given value of a;, (-^) = 1 (the demonstration is similar in the opposite case). This does not guarantee that x is a square modulo N because A is not a prime. Wc must decompose our symbols (-^) and (N^x): 2; Ar-,x'\ fN — x\ (N — x\ /—x + qp\ I—x + pq\ (— x\ (— x" If = 1 AND = 1. since p and (/ are primes, then a; is a square modulo p and modulo q, which implies that it is a square modulo N. However, if x is a square modulo N, then —x is not. As we can see, exactly 2 numbers among x, N — x, 2x and N — 2x have Jacobi symbols equal to 1: those who have not are not squares. Between the two numbers with a Jacobi number equal to 1, only one of them is actually a square modulo N. This is the proof that, VI < x < N, exactly one among x, N — x, 2x and N — 2x is & square modulo N. Question 5 (6 points, \ \ 2) Consider a cryptosystem where an intended recipient per-foriiLs the following: • Chooses n numbers Xi with gc<\(xi,x.j) — 1, z ^ j. • Chooses a prime number q such that Tl <7>IIX* • ChoOSeB a primitive root b modulo q. • Calculates Oj, 1 < i < n sueh that, Xi = bl (mod q). • The values Oj, 1 < i < n form the public key; q and b», 1 < i < n remain secret. To send an n-bit message (mi,...;,m») where raj € {0,1}, the sender calculates n «-1 mid sends A: to the recipient. (a) How does the intended recipient recover the message? Explain. (b) The security of this cryptosystem relies on which assumptions? Solution This is the Mcrklo-Ilcllinan multiplicative? version of knapsack, (a) The recipient calculates 77i = bk (mod q). Since bk = Y[{baiP = ] J x™' (mod q) t-i t-i and q > Y\7-o xi ^eu m-Ylx™' and r/ij = 1 iff x.i\m. (b) Discrete logarithm problem and knapsack problem. Question 6. (a) It is always an one-way function. If we add arbitrary padding such as 0 ... 0 to the output of a one-way function it does not affect its one-wayness because the zeros can be removed and the problem is same as solving the original preimage problem. If we duplicate the same one-way function we can split the encoded string to two parts and again obtain the same preimage problem as if we were solving the original. (b) It is not always a one-way function. Let's have a one-way function / that maps binary strings of length n to another binary strings of length n. We can construct a one-way function g that maps the binary strings of length n to binary strings of length 2n by using the output of one-way function / and adding padding of n zeros. This is still a one-way function because if we remove the padding zeros it is the same problem as finding preimage of the /. Now let's create another one-way function h that maps binary strings of length 2n to binary strings of length 2n. It returns 2n zeros if the first half of the string is all zeros and result of g other wise. We can clearly see that if we call the function h once on a input that has at least one non-zero digit in the first half it will return the result of the function g that returns the message with first half zeros and if we use that as an input of h the second application of that function we will obtain all zero result. Question 7. Eve might be capable of decrypting the original message to. In the RSA, n and e are the public key. We also know that 2511 < n < 2°12 and e = 3. Bob chunks the message into 64-bit long parts, which means 264 = 2192 values for the cipher message. This is considerably less than the modulus which is at minimum 2511 + 1. Therefore the modulo operation is never used and C{ = m|=3, so Eve could decrypt all chunks sent simply by computing mi = "=ffci- The only thing Eve has to manage is to identify all these chunks, but these are separated with the unique identifier # and therefore she can spot this recurrence and identify these chunks. Then she has to try to compute the root as shown above.