(a) Encrypt your LCO using the Rabin cryptosystem with n = 098009. Then calculate a]] four possible decryptions of the ciphcrtcxt you calculated, with the knowledge that n = 887 x 787.
Solution:
• Encryption: m = 150149 and m < n, therefore wc can compute the ciphcrtcxt
c = m2 = 45014S2 = 577578   mod G98009.
• Decryption: The decryption formula is m = yfc (mod n). Wc use Chinese remainder theorem to calculate the possible results.
x = 577578 mod 887 y = 577578 mod 78T
r = 577578*^   mod 887 _ y = 577578^!   mod m
x = 57757S232      mod 887 2,= 577578197      mod 787
, = m mod 887 B_3U mod7s7
We are looking for the Bezout's coefficients (k and I) for p = 887 and q = 787
204 ■ 787- 181 -887 = 1.
Therefore k = -181 and I = 204.
Finally we can calculate all four possible decryptions, using this statement ±i - l ■ q±y ■ k ■ p = mi   mod n.
mi=  231-204 ■ 787+ 311 - (-181) ■ 887 = 419782 mod 098009
m2 =  231-204 ■ 787 - 311 - (-181) ■ 887 = 456149 mod 098009
m3 =-231-204 ■ 787+ 311 - (-181) ■ 887 = 241S20 mod 098009
m, =-231 - 204 ■ 787 - 311 - (-181) ■ 887 = 278287 mod 0980G9
The original message is ma-
□
(b) Encrypt your UCO with the ElGamal cryptosystcm with p = 507899, q = 2. x = 12345 and random choice r = 938.
Solution: First of all, the part of public key is y = qT mod p. therefore y = 2123,15 = 222588 mod 507899.
Now wc are able to encrypt the message m = 45G149 The ciphcrtcxt is c = (a. &). where a = qT mod p and b = yrw mod p.
a = 2™ =201104   mod 507899
b = 2225S8938 ■ 456149 = 25233     mod 507899
The message m = 450149 is encrypted as (201104. 25233). □
1
Question 2.
q = 7.y = 505, p = 541
m = Vp^7! = v540 = 24 0 > i,j > 23:
j	0	1	2	3	4	5	G	i	8	9	10	11
q™1 (mod p)	1	110	198	140	252	129	124	115	207	48	411	307
j	12	13	14	15	1G	17	18	19	20	21	22	23
qmi (mod p)	228	194	241	1	110	198	140	252	129	124	115	207
L2-
i	0	1	2	3	4	5	6	7	8	9	10	11
y ■ q~' (mod p)	505	304	198	492	534	540	309	276	194	105	15	234
												
i	12	13	14	15	1G	17	18	19	20	21	22	23
y ■ q~' (mod p)	188	33G	48	316	277	426	370	3G2	129	173	102	401
Pairs with common second values, and resulting exponents:
(0,48), (14,48), si = 24 ■ 0 + 14 = 230 (mod 540) (5,129), (20,129), X2 = 24 ■ 5 + 20 = 140 (mod 540) (20,129), (20,129), x3 = 24 ■ 20 + 20 = 500 (mod 540) (13,194), (8,194), x4 = 24 ■ 13 + 8 = 320 (mod 540) (2,198), (2,198),     = 24 ■ 2 + 2 = 50 (mod 540) (17,198), (2,198), x6 = 24 ■ 17 + 2 = 410 (mod 540)
2
Question 3.
We assume that year has 3G5 days. People born on 20"1 of February usually celebrate birthday on the 28th anyway.
(a) The birthday co-incidence probabilit;' given by the birthday paradox equation is:
3G5!
~ 365"(365 - n}\
IV054 2019 Jan Pokorný (456195 (xpokorn3)) Homework 6
For n = 135, this gives:
3G5!
L-365^(3S5-la5),-0-fl"9^0 Meaning the probability is around 03.009009009060%, or. in other words, practically certain.
(b) Since the chance of some specific other student sharing birthday with me is       the chance of him not sharing is       the probability of all the 134 students other than me not sharing is and finally the probability of some other student sharing birthday is:
/3G4 ^365
134
1 - I ^ I     ~ 0.3076
Meaning the probability is around 30.70%.
3
Question 4.
Given problem is an equivalent to solving the birthday paradox for a year with 264 days. Let's consider the complementary event, that is that no collision occurred. The probability of such event considering n 2G4-bit hashes (by the pigeonhole principle n < 2G4) is equal to
^')=n(i-^)=ni(2M-i)=^
264|
264'    f_l02My '    2G4™ (2G4-ji)!
However as the size of hash is large, an approximation can be used. Assuming n < < 2G4 we will use the fact that for ln[\ — e) = — e for small positive e. We obtain:
Ti—l                 .          n—1                      1         /        1 \ 1 5
j , _ v-^     t          l    n[n — 1J 1 n
ln(P(A')) = J2 HI-^) = E-W=-^-      2^ ~ ~W'Y (f°r n) P(A') ks e"^
i=0 1=0
J*(.p(a'))
The probability P(A) of generating at least one collision in a set of n 2G4-bit hashes is at least | when P(A') < ^. Therefore we obtain:
e a-!b4 < -4
"2       , ,1, -——sj < ln{-)
n2 < _2.2e4-;-n(^) « 5.11452... ■ 10lfl n as 7.15150 ... ■ 10fl
At leas a: 7.15159... ■ 10° guesses must be made in order to obtain probability of a collision at leas
s
Question 5.
We are encrypting message :r = IHI2, so = 105 with parameters p = 11 and q = 43.
n — p x q — 473 si = 1052mod473 = 185 s2 = 1352moti473 = 169 s3 = 1692mod473 = 181 s4 = 1S12 mod 473, = 124 s5 = 1242 mod 473 = 240 a\(J2U-ia\ = llW(least significant bits of si, S3, S3. S4)
C =       X ffi (71(72^3^4) = (240,0001)
4
Question 6.
(a) The function is not negligible because if we set p(n) = n2 and suppose the inequality
ln(l + -) > \, then lim ln(l H—) * n2 = oo which is > 1 for at least most of n values, mean ins fin) < -r-^ can not hold "for almost all n" as the definition states.
(b) It is easy to see that for any polynomial p(m) — amnm + ■ ■ ■ + a-o the function rp(n) — E™o      * ™m produces greater values than the polynomial. Therefore, if f(n) <        - then
1
1
e   n < -
— rp(n)
*C /n(^m—r—i „m ) «     -      VEt=0 |ai|*™m '
^^-hUEEo hi)-■»•*"(")
—ln{n) '— n-hm —m(n)
From the reason similar as in (a), m is lower than at least most of n values for any polynomial, hence the function is negligible.
5
Question 7.
(a) Suppose you know a valid plaintext-ciphertext pair iuj = 457, (ai,ii) = (GG3, 2138). constructed using the ElGamal cryptosystem with public key p = GG61, q = 6, y = 6015, Also you know that instead of using a new random r to encrypt each new message, the sender just increments the previous one, i.e. ti = n + 1. With this knowledge decrypt the following cipher text (02,62) = (3078,14GG) without calculating discrete logarithms.
mod /;
we know that: ■wi = 457 ai = qr'  mod p
61 = yr) wi mod p ■if'i = Siaj"1 mod p and therefore af — tttj and we also knowr: f2 = rj. + 1 a.2 = qri = q
62 = yr'tU2 = yT1+1W2 mod p it's = &2«2 1 m°d V
To calculate w2 nowT we can use this knowledge
£>2
W2 — —~ mod p
b-2
62
b.
mod p mod j?
- mod p
= b2VJ\b~[xy~x      mod p
Now to actually decrypt w>]> we need to calculate frj-1 mod p and y-1 mod p (we can use for example extended cucklidean algorithm)
6r]
V
and now we can calculate uii w2 = ij^l&i" V1 = 146G ■ 457 ■ 4G4 ■ 4153 = '
(b) Show that the same attack is possible for any linear update function of the random seed, i.e. whenever r2 = kri + ( mod p — 1.
we know that: ai = qTl  mod p
bi = yTlwi mod p
u'i — b^a^1 mod p
and therefore af = uff^&i mod p
and we also know:
T2 = fcri + t mod p — 1
«2 = <7rs = q*^+l = a\ql modp
and therefore:
mod p mod p mod p mod p mod p mod p mod p
iu2 = &202
= b2(a?qct)-1 6
= b2K-t^)-1