Question 1.
x = 6   (mod 17) x = 3   (mod 7) x = 9   (mod 11)
First we check that gcd(17, 7) = 1, gcd(17,11) = 1 and gcd{7.11) = 1, therefore we can use the Chinese remainder theorem.
Let's denote the numbers from the assignment as a\ = 6, ni\ = 17, a<i = 3,       = 7, «3 = 9, — 11.
We have three integers mi, and 7713 st gcd(mi,rrij) — 1 if i ^ j and integers ai>aa, 03 st 0 < a-i < m-i, 1 < i < 3. The system of congruences
x = a,   mod 771 j ? 1 < z < 3
has the solution x = ajMjNj, where M = fli=l m^       = ^>      = ^fT* m°d      and the
solution is unique up to the congruence modulo M. Since we are looking for 0 < x < M, we can do the computation of x — 5Zf=i <H^i^i mod M.
First we compute Af — m\ - ma ■      — 17-7-11 — 1309. Then we can compute Mim.
1309     17-7-11     , „ „
1309     17 ■ 7 11
M2 =-=-= 17 -11 = 187
7 7 1309     17-7-11     1rT _
M3 =-=-= 17 - 7 = 119
11 11
Now we need the inverses of Mt.
A'l = Mi 1   mod rai = 77_1   mod 17 = 9"1   mod 17 = 2   mod 17
We found the last equation simply, since 2 ■ 9 — IS — 1 mod 17.
1
Ni = M2     mod m'i = 187"1   mod 7 = 5_1   mod 7 = 3   mod 7
Again we simply find the last equation, since 3 ■ 5 = 15 = 1  mod 7.
iVj = M^1   mod m3 = 119"1   mod 11 = 9*   mod 11 = (-2)-1   mod 11 = 5   mod 11
Again -2 ■ 5 = -10 = 1 mod 11. Now we can compute the x:
3
x = y] aiMiNi   mod M = i=i
= S ■ 77-2 + 3 ■ 187-3 + 9 ■ 119-5   mod 1309 = = 924 + 1683 + 5355   mod 1309 = = 7962   mod 1309 = = 108
So we have the result x = 108. We can easily check that 108 = 6 mod 17, 108 = 3 mod 7 and finally 108 = 9 mod 11.
2
Question 2.
I'm gonna use Eulers criterion:
u-i     I 1   mod p     if there is an integer x such that a = zr   mod p, a 2   = <
I —1   mod p   if there is no such integer. Let's look at the number {1...., 10}:
8009-1 1 2		2^4001 _	1	mod p
8009-1 2 i	=	24004 _	1	mod p
8009-1 3 2	=	3*004 —	- 1	mod p
8909-1 4 s	=	4^004 =	1	mod p
8009-1 5 2		54004 _	1	mod p
8000-1 6 2	=	g4004 _	-:	mod p
S909-1 7 2	=	^4004 _	l	mod p
8909-1 8 =	=	g4004 _	l	mod p
8009-1 9 2	=	g4004 _	l	mod p
8009-1 10 =	=	io4004 =	= l	mod p
So numbers 1,2,4,5,7,8,9,10 are quadratic residm modulo 8009, and number 3,6 are not.
3
Question 3.
(a) Rabin cryptosystem
n = 698069 = 887 ■ 787
Encryption: Since id = 456556 and w < n:
c=w2   (mod n) = 4565562 = 675805   (mod 698069)
Decryption:
The formula is w = -Jc (mod n). Firstly we use Chinese remainder theorem:
ujp ee 675805   (mod 887) wq ee 675805   (mod 787)
3 -            ,         ,          , 7 '
wp = 675805 4"   (mod 887) wg = 675805^"   (mod 787)
ujp ee 675805222   (mod 887) wq ee 675805197   (mod 787)
ujp ee 249   (mod 887) wg = 96   (mod 787)
Secondly we hare to find yp and yq (can be found as Bezout's coefficients) for p = 887 and q = 787:
Vp = P^1    (m°d l) Vq = <7~1   (mo(i P)
yp = 887-1   (mod 787) yq = 787-1   (mod 887)
Kp e: -181   (mod 787) y„ ee 204   (mod 887)
Lastly we calculate four possible solutions as follows:
wt ee ±wp ■ q- yq±wq- p- yp   (mod n)
wi =   249 ■ 787 ■ 204 + 96 ■ 887-(-181)= 131525 (mod 698069)
il'2 ee   249 ■ 787-204 - 96-887-(-181)ee 241513 (mod 698069)
ws ee -249 ■ 787 ■ 204 + 96 ■ 887-(-181)= 456556 (mod 698069)
il'4 ee -249 ■ 787 ■ 204 - 96 ■ 887-(-181)ee 566544 (mod 698069)
The original message is W3.
4
(b) El GamaL cryptosystem
p = 567899 9 = 2
x = 12345
r = 938
Encryption:
Firstly, we need y = qx (mod p) = 212345 = 22 2 5 88 (mod 567899). Now we can encrypt tie message w = 456556 as follows:
r
M)
(f   (mod p)
r,938
h
b
w ■ yr   (mod p)
456556 ■ 222588'
a
201104   (mod 567899)
b
325068   (mod 567899)
The encrypted message is (201104, 325068)
Question 4.
To show this, we prove that the discrete logarithm problem is reducible to finding two collisions, i.e. we can solve the discrete logarithm by finding two colliding messages.
First we find the two colliding messages m = x + yq and m' = x1 H- y'q. We want to find / such that l°Sa   = I mod p (or 3 = op mod p).
Because the messages m.m' have the same hash value, it holds that ax3y = oF ft* mod p. We replace 3 with       crc(a^)y = ar (a^)y mod p axaly = cxx aly mod p Qx+fji = Qs:'+V mod p
x + ly = x' + lyf mod p — 1 (for exponents we use modulus order of a = p — 1)
l(y' -y)= (x - x') mod pi
We can replace p — 1 = 2q and get l{y! — y) = (x — x') mod 2q We can solve this using these two equations and CRT:
l(y' - y) = (x - x') mod i
l(y' -y)= (x - x') mod 2
For the first one we have to show that inversion of y' — y exists, i.e. t/ — y ^ 0 (mod g). If y 7^ y\ it holds that y' — y ^ 0 (mod g) because 0 < y\ y < q — 1.
If y = j/ it holds that a1 = a1 (mod p) (becanse h{m) = h{m!)), x = x! (mod p — 1), x = x! (mod 2g) and because 0 < xfix < g — 1 that means x = x', but that breaks the condition m ^ m' - contradiction. Therefore y ^ y'.
For the first equation we have one solution I = (x — x') * (yf — y)-1 (mod q)
For the second equation we have two different solutions (because we are using modulus 2) and we can try both without changing the complexity to get the final value of I (there is only one because a is primitive root).
We showed that we can solve the discrete logarithm problem by finding two colliding messages and therefore finding two colliding messages is at least as hard as solving the discrete logarithm problem.
5
Question 5,
(a) Probability that at least two people were born on the same day of the week is easier to calculate with complementary probability - everyone was born on different day of the week and subtract it from 1. (variation without repetition, how many ways to pick 5 digits from 7 numbers, order is important)!
(b) The probability that exactly two people (couple) were born on the same day of the week (and three other people in different days) is: How many ways can we select a pair, couple - two from five people each person from pair was bom on the same (one) day from seven possible days.
(c) the probability for at least three people were born on the same day of the week is equal to probability that exactly two people were born on the same day of the week (prob. from (b)) subtracted from probability that at least two people were born on the same day of the week (prob. from (a)). We have to be careful and don't forget to subtract also the probability of two pairs, because (6) is probability of exactly one pair. So we have to choose two from five people - first pair and two from three people - second pair now assign two from seven days to each pair and finally assign last day from 5 residual days to last the person:
, divided by all possible outcomes
6
Question 6.
First, we will show that there are exactly two decryptions Xi, Xj of even parity and. exactly two decryptions ijt, x\ of odd parity, where i ^ j ^ k ^ I.
The decryptions are in the following form:
x\ =       mp ■ q • yq +       mq ■ p ■ yp mod n
3t2 =       mp ■ q ■ yq + (- m^) ■ p ■ yp mod n
x-3 = (- mp) -q-yq+       mq ■ p ■ yp mod n
x± = (— mp) ■ q - yq + (-        ■ p ■ yp mod ti
where mp = ^/c mod p; m? = ^/c mod g; ?/p = p 1 mod q and y? = g_1 mod p.
Since p, q are prime numbers such, that p = q = S mod 4, then p and ij are odd prime numbers.
Since p is an odd prime number and — mp = p — mp (mod p), then mp is of opposite parity from —mp.
This holds also for mq and —mq - i.e. since q is an odd prime number and —mq = q— mq (mod q). then mq is of opposite parity from —mq.
Let nip and mq have the same parity. Then — mp and — mq aiso have the same parity (opposite from mp and mq).
Then the decryption x\ can be written as:
x\ = mp ■ q ■ yq + mq ■ p ■ yp
= - ((-mp) ■ qyq+ (-mq) ■ p ■ yp)
= n — x.i
And the decryption x% can be written as:
x-2 = mp ■ q ■ yq + (—mg) ■ p ■ yp mod n
= - {{-mp) ■ q ■ yq + mq ■ p ■ yp) mod n
= — x% mod n.
= n — 13 mod 7i
mod n mod h mod » mod ?i
7
Since n = p ■ q is an odd number, the decryptions xi and x4 are clearly of opposite parity And so are the decryptions x2 and 13.
Second, we "will show that for each pair xs, xi of decryptions of the same parity, where s ^ f, the value of Jacobi symbol modulo n of xs is opposite from the Jacobi symbol modulo n of xt.
The Jacobi symbols modulo n for the decryption xi is as follows: Imp ■ q ■ yq + mq-p- yp\ _ {     ■ q ■ yQ + mq ■ p ■ yp
V ■ <J
m-p ■ q ■ yg + m, ■ P ■ yP\   (m?-q- Vq + mq ■ p ■ yp
( ( (
(?)('
mv-q-yq\   (mq -p-yp \ 9
And in an analogous way we get the Jacobi symbol modulo n for the decryption x% (mv-qyq + (-mq) -p-y^
For the decryption X3:
/ (-'"?) ■ g ■ Vq + ™g  p- Vy
And for the decryption 24:
-(
P )   V 9
'(— mp) ■ q ■ yQ + (—mq) ■ p ■ yp\ _ f-m„\   (-mq^\ _ f—l\   (rrip\   (—\~\   Im,
VI   \ q )   \ q
Since gcd(mp,p) = gcd(mg,<j) = 1 none of the Jacobi symbols modulo n for any decryption will be equal to zero.
This implies that the Jacobi symbols modulo n are the same for the decryptions x\ and t4 (which are of opposite parity)
And also for the decryptions x2 and x% (again of opposite parity) the Jacobi symbols modulo n are the same (and they have an opposite value from the Jacobi symbols modulo n for i\ and x4).
Therefore, we can see that each of the four possible decryptions xi, X2. 2:3 and Xi of ciphertext c is uniquely determined by two bits of information - its parity and Jacobi symbol.
8