EE418 Assignment 3 Solved

1. [Com](Public Key Cryptosystem, 10 pts) Suppose that m > 2 users want to communicate securely and confidentially. Suppose further that each of the m users wants to be able to communicate with every other user without the remaining m − 2 users being able to listen on their conversation. How many distinct keys are needed if we are using:

• A symmetric key cryptosystem, where two users use a shared secret key to communicate,
• A public key cryptosystem, where every user i has a public key, PKi and a private (secret)

  key, SKi.
  How many keys are needed in each of the above cryptosystems if m = 1000?

  2. [Pro](RSA Decryption, 5pts × 3 = 15 pts) A sample of RSA ciphertext presented in Table 1 is generated using the following steps.

(I) First alphabetic characters are “encoded” as the elements in Zn, where each element of Zn rep- resents three alphabetic characters as in the following examples:

DOG CAT ZZZ

→3×262 +14×26+6

→2×262 +0×26+19 →25×262 +25×26+25

=2398 =1371 =17575

i.e., Each three letter plaintext block (mi for i = 1,2,…) is “encoded” as in the above to get corresponding encoded-text block (ei for i = 1, 2, . . .).

(II) Then each encoded-text block ei is encrypted using RSA public key b to get ciphertext, ci = (ei)b mod n.

Follow the steps given below to decrypt the ciphertext blocks ci given in Table 1 assuming RSA Cryptosystem is using modulo base n = 31313 and public key b = 4913.

1. (a)  Write a Python/MATLAB code to factor the n and compute the RSA private key a from φ(n). (Hint: Since n is small you can use brute-force approach to factor n here. In such an approach

   you will need to check which prime number p in the range of [2, floor( n)] will divide n)

2. (b)  Write a Python/MATLAB code to implement SQUARE-AND-MULTIPLY ALGORITHM in Al-

   gorithm 1. This algorithm implements exponentiation in modulo n in a computationally efficient

   way. It assumes that the exponent a is represented in binary notation, say a = 􏰃l−1 ai2i, where

ai =0or1,0≤i≤l−1whencomputinge=ca modn.

i=0

(c) Write a Python/MATLAB code to decode any given ei, encoded message blocks using the tech- nique described in Step (I). and the use the Python/MATLAB functions you produced in part (a), part (b) and part(c) to decrypt the ciphertext given in Table 1.

Algorithm 1 Computationally efficient exponentiation in modulo n

√

1: 2: 3: 4: 5: 6: 7: 8: 9:

10:

functionSQUARE-AND-MULTIPLY(c,a,n) e←1

fori←(l−1) downto 0do e←e2 modn
if ai =1then

e=(e×c) modn end if

end for

return e end function

2

6340 8309

                               14010
                               24996
                               4517
                               23901
                               2149
                               5314
                               4685
                               25809
                               27106
                               9917
                               8635
                               2149
                               27705
                               16087
                               7553
                               25234
                               29413
                               30989

3. [Com] (Chinese Remainder Theorem, 5 pts × 2 = 10 pts) Solve the following system of congruences. (a)

23614
27584
25774
 7908
 4082
15698
 1417
12437
23005
15930
27486
18154
 2149
19554
 3183
 6000
25973

 7135
14999
 7647
 8635
11803
30317
26905
 1108
 8267
29748
 9741
22319
16975
23614
17347
31280
 4477

 8936
30590
12146
 7372
 1908
 107
14696
28347
18743
 7994
23645
29329
20321
14600
 4734
 4595
 2066

27358
27570
29421
25774
22076
 7359
30388
26277
24144
 9694
11738
2149
23254
27705
 8091
21498
 369

25023
26486
26439
18436
 7372
22470
8671
 7897
10685
 2149
24591
5501
13624
19386
23973
 6360
23204

16481 25809 30388 9395

1606 17881 12056 13547 8686 1304

7372 22827 29956 15705 20240 21519 25234 30155 10042 27705 20240 27212 14015 30155 3249 5443

7325 26277 14015 107 19837 8463

8425 7792 Table 1: RSA cipher text for Question 2

x ≡ 12 mod25 x ≡ 9 mod26 x ≡ 23 mod27

13x ≡ 4 mod99 15x ≡ 56 mod 101

(b)

4. (RSA protocol failure, 5 pts × 2 = 10 pts) This exercise exhibits what is called a protocol failure. It provides an example where ciphertext can be decrypted by an opponent, without determining the key, if a cryptosystem is used in a careless way. (Since the opponent does not determine the key, it is not accurate to call it cryptanalysis.) The moral is that it is not sufficient to use a “secure” cryptosystem in order to guarantee “secure” communication.

Suppose ”B” has an RSA Cryptosystem with a large modulus n for which the factorization cannot be found in a reasonable amount of time. Suppose ”A” sends a message to Bob by representing each alphabetic character as an integer between 0 and 25 (i.e., A ↔ 0, B ↔ 1, etc.), and then encrypting each residue modulo 26 as a separate plaintext character.

(a) Describe how an eavesdropper ”E” can easily decrypt a message which is encrypted in this way.

(b) [Pro] Write a Python/MATLAB code to illustrate this attack by decrypting the following cipher- text (which was encrypted using an RSA Cryptosystem with n = 18721 and public key b = 25) without factoring the modulus:

365, 0, 4845, 14930, 2608, 2608,0 3

(HINT: For part (b) use the Extended Euclidean Algorithm and then apply the Chinese remainder theorem)

Note: For the Questions 5, 6, 7, and 8 use the following fact.
Ifx2 ≡y2 modnandx̸≡±y modn,thengcd(x−y,n)isanontrivialfactorofn.

5. [Com] (Factorization, 10 pts) Let n = 642401. Suppose you discover that, 5161072 ≡ 7 mod n

and that

1877222≡22·7 modn

Use this information to factor n.
6. (Factorization, 5 pts × 2 = 10 pts) Suppose you discover that

8805252 ≡ 2 mod 2288233, 20572022 ≡ 3 mod 2288233, 6686762 ≡ 77 mod 2288233

6485812 ≡ 6
(a) How would you use this information to factor 2288233 ? Clearly, explain what are the steps you

would do, but do not perform the hand calculations in this part.

(b) [Pro] Write a Python/MATLAB script to find the factors of 2288233 using the steps you provided for part (a).

7. [Pro] (Factorization, 5 pts × 2 = 10 pts) Write Python/MATLAB scripts to perform the following tasks.

1. (a)  Let n = 537069139875071. Suppose you know that
   859753244431662 ≡ 4624361062612 mod n

   Use this information to factor n.

2. (b)  Let n = 985739879 × 1388749507. Note that numbers 985739879 and 1388749507 are prime numbers. CanyouFindxandywithx2 ≡y2 modnbutx̸≡±y modn.
   (Hint: Note such x and y will satisfiy one or both of the following properties:

   • gcd(x − y, n) is a nontrivial factor of n

   • gcd(x + y, n) is a nonttivial factor of n You may have to try different x and y values.)

8. [Com] (ElGamal Public Key Cryptosystems, 10 pts) Consider the ElGamal encryption scheme. “A” chooses a prime p and a primitive element α of Zp. “A” also chooses a private key a and computes β = αa. Then public key is PK = (p,α,β) and the private key is SK = a.

If “B” wants to send a message m to “A”, “B” uses public key P K and encrypts a message m as follows. Choose a secret random number k,1 ≤ k ≤ p − 2. The encryption of m is EPK(m,k) = c = (y1,y2) where y1 = αk mod p and y2 = mβk mod p. “A” performs the decryption of c = (y1,y2) as DSK (c) = y2(y1a)−1 = m mod p.

“B” chooses two messages m1 and m2 and secret random numbers k1 and k2.“ B” encrypts m1 using k1 and obtains EP K (m1, k1) = (y1, y2) and encrypts m2 using k2 and obtains EP K (m2, k2) = (y3, y4). “B” then transmits c = (y1y3 mod p, y2y4 mod p) to “A”. What is the plaintext that “A” obtains after decrypting c? Show your steps.

Awards under this announcement will be made only to U.S. institutions of higher education which award degrees in science, engineering or mathematics. U.S. non-profit organizations operating primarily for scientific and educational services may also submit proposals. The principal investigator of a proposal must be a U.S. citizen, national or permanent resident (on the date proposals are due), holding a

4

mod 2288233

first or second full-time tenure-track or tenure-track-equivalent faculty position at that university, and has received his/her doctorate or equivalent degree within the past seven years. See solicitation for eligibility dates. The term ”national” of the United States includes a native resident of a possession of the United States, such as American Samoa.

9. [Pro](ElGamal Decryption, 15 pts) Write a Python/MATLAB code to decrypt the ElGamal ciphertext presented in Table 2 assuming groups of three alphabetic characters are encoded using the technique described in Question 2, Step (I) before encrypting using the ElGamal public key (α,β,p). The parameters of ElGamal public key cryptosystem is given as α = 5, β = 18074, p = 31847, and private key a = 7899.

(3781, 14409) (54000, 31486) (31590, 26470) (16160, 3129) (30555, 24611) (1616, 14170) (14130, 22010) (26004, 25056) (29538, 5408) (1777, 8737) (23258, 3468) (8836, 25898) (10422, 5552) (25115, 10840) (23418, 22058) (198886, 22344) (21563, 7891) (24271, 8480) (30499, 14423) (24875, 17641) (3576, 4630) (3149, 7400) (21541, 19004) (17561, 11884) (26521, 5803) (28327, 19237)

(31552, 3930) (19936, 721) (3781, 14409) (301, 17252) (20501, 2922) (4294, 2307) (25910, 19663) (5400, 31486) (3149, 7400) (26117, 14251) (26052, 20545) (8794, 17358) (1777, 8737) (14130, 22010) (24139, 9580) (21600, 25505) (28250, 21321) (26592, 25457) (5839, 24179) (1777, 8737) (26664, 27572) (8951, 29435) (5865, 29526) (2209, 6107) (14884, 14280) (15313, 28649)

(27214, 15442) (27765, 29284) (15898, 30844) (24689, 7776) (13659, 5015) (2320, 29174) (19557, 10145) (9526, 3019) (9396, 3058) (7129, 18195) (21958, 5713) (1777, 8737) (3780, 16360) (16081, 16414) (173, 17075) (27119, 19921) (28327, 19237) (9660, 7939) (12846, 6598) (18825, 19671) (27011, 29164) (2059, 3977) (10536, 6941) (10422, 5552) (4328, 8635)

(5809, 30274)

(29820, 7710) (19048, 12914) (28856, 15720) (5740, 31233) (3036, 20132) (18899, 27609) (12962, 15189) (27149, 20535) (25302, 10248) (346, 31194) (25038, 12483) (11685, 133) (28580, 20845) (2016, 18131) (23312, 16906) (15313, 28649) (10267, 20623) (9284, 27858) (31306, 11929) (22763, 8992) (16258, 30341) (1777, 8737) (19371, 21005) (28250, 21321)

Table 2: ElGamal cipher text for Question 9

5