Question 1. Public key. in this subliminal channel, is the pair (n.h). We already know that n = 6050 and A- = 21. Since h = k~2 mod n h = (fc-1)2 mod n. we have to compute k~l. By using Euclide's algorithm, we have: 6059 = 288 x 21 + 11 21 = 1 x 11 + 10 11 = 1 x 10+ 1 We can deduce that 1 = 2 x 6059 - 577 x 21. which means that -577 x 21 = 1 mod 6059. and in extenso -577 = 21"' mod 6059 5482 = 21_1 mod 6059. Therefore, IT1 = 5482. Now we can compute h: h — (fc-1) mod n h = 54822 mod 6059 h = 5743 mod 6059 Now we will sign the message. In this case, two signatures (S|.S2) must be computed, according to the following scheme: Sj - A. + u^j mod n and S2 ■ |. (jj- — mod n. This can be rewrited S| = 2~l.(w'.w~l +w) mod n and Sj = Ar.2"'.(u''.u;_'-it1) mod n. This implies knowing 2_1 and W-1, Since 2 x 3030 = 6060 = 1 mod 6059, we can easily see that 2"1 = 3030 mod 6059, but for u; = 54. it is less obvious. We once again use Euclide's algorithm: 6059 = 112 x 54 + 11 54 = 4 x 11 + 10 11 = 1 x 10+ 1 Then, we have 1 = 5 x 6059 - 561 x 54. and thus we can deduce w~ = —561 mod 6059 = 5498 mod 6059. (liven that, we can compute S\ and So' Si = 2~ .(w'.w~ + w) mod n Si = 3030 x (2021 x 5498 + 54) mod 6059 Si = 3030 x 11111512 mod 6059 Si = 3030 x 5365 mod 6059 Si = 5712 mod 6059 S2 ^ k.2 1.(w'.w 1 — w) mod n S2 S 21 x 3030 x (2021 x 5498 - 54) mod 6059 S2 = 63630 x 11111404 mod 6059 S2 = 3040 x 5257 mod 6059 S2 a 3697 mod 6059 Now. we must prove that the signature is correct. To power this verification, w' = S2 - /iSf mod n must hold: 5f - fcSf mod n = 57122 - 5743 x 36972 mod 6059 s 57122 - 5743 x 36972 mod 6059 = 5288 - 5743 x 4764 mod 6059 = 5288 - 3267 mod 6059 = 2021 mod 6059 As we can see, w' = Sf — ft5| mod n: as a result, the signature is valid. We can now decrypt the message. To decrypt the message, we have to compute w ■ yjpig mod n. which is equivalent to w = v/.iSi + fc-152)-1 mod n. We have Si + k~lS2 = 5712 + 5482 x 3697 = 20272666 s 5311 mod 6059. Therefore, we have to calculate 5311 ~l mod 6059. and we will once again use the Euclide's algorithm: 6059 = 1 x 5311 + 748 5311 = 7 x 748 + 75 748 = 9 x 75 + 73 75 = 1 x 73 + 2 73 = 36 x 2 + 1 We obtain 1 = 2620 x 6059 - 2989 x 5311. Consequently. -2989 mod 6059 = 3070 mod 6059 s 5311 1 mod 6059. Finally, since we know all needed values, we can compute w: w = w'.(Si + fc_152)_1 mod n w = 2021 x 5311"1 mod 6059 w = 2021 x 3070 mod 6059 uj ee 54 mod 6059 We find the value of w given in the statement. Question 2. See excel table Question 3. From (mi,sig(mi)) we have 12d = 46 mod 1591. From (m-2, f>ig(m-2)) we have 33d = 1080 mod 1591 From the exercise book, we know that for the RSA signature scheme it holds: if 8\ and .s2 are signatures of messages m\ and 7712, we can easily compute the signature of the message m = mi*m2 mod n as s = s\ * .12 mod n. 77*3 = mi* m\ s3 — si * si niod 1591 .s3 = 525 Verify: 52513 mod 1591 = 144 771-1 = 777 1 * 777 2 s4 = s\ * S2 mod 1591 .s4 = 359 Verify: 35913 mod 1591 = 396 From the exercise book, we know that if ,s is a signature of a message m then .s_1 mod 77 is the signature of the message nz_1 mod 71. 7775 = 777 mod 1591 EE A for 359.1591 = 195 * 359 + (-44) * 1591 = 1 85 = 195 mod 1591 Verify: 19513 mod 1591 = 454 Question 4. For each message, we need a unique combination of the values from the secret key and match them with values in the public key for verification. For every n, we have 2n possible keys and we want to find bit size of messages, which give us the highest number of created messages. If we choose the bit length = 2n, there is only one possible message, as (2") = 1. However we know from the Pascal triangle, that the highest result of combination number is when k = n/2. if n is even, and k - n/2 + 1 or k = n/2 — 1 if 77 is odd. So the maximum number of distinct messages one can sign with such scheme for n is (2^) as 2n is always even. For 77 = 10 we are choosing 10 out of 20 t/,j. which give us: C{n,k) = = totJ^t = 184756 unique combinations (subsets) of the key values, so we can sign 184756 distinct message's with such scheme. Question 5. (a) We have the public key (p = 101, q — 27.y = 14). a message it' = 61 and the signature is (27,51). We verify if the Elgainal signature verification equality hulds : yaab mod n = 14272751 mod 101 yaab mod n = 40 q" mod 101 = 2761 mod 101 qw mod 101 = 40 The equality holds. yaab = qu motl ;i. which means the signature is valid. (b) We can observe that q = a = 27. As we have : a = qr mod p 27 = 27r mod p Then r can only be 1. Knowing that r = 1. we can easily compute x with the formula : x = (u> — r.6)a_1 mod (pi) x = (61 -51) x 27"1 mod 100 x = 630 mod 100 x = 30 We have x = 30. As an additional proof to verify this hypothesis, let us see if x = 30 works to compute b = 51 we were given : b= (w — x.a)r-1 mod (p — 1) 6 = (61 - 30 x 27) mod 100 6 = 51 We find the b that we were given, x = 30 seems to be valid. Question 6 (a) If the protocol is followed properly then l I II & "I = 11