Solved-Cryptography Homework 3 -Solution

Description

Notes:

0. • Note that there are three attached files: “RSA_OAEP.py” for Question 1, “ElGamal.py” for Question 2, and “DSA.py” for Bonus Question.

0. • You are expected to submit your answer document as well as two Python codes for Questions 1, 2 and 3, respectively.

0. • Winzip your programs and add a readme.txt document (if necessary) to explain the programs and how to use them.

0. • Name your winzip file as “cs411_507_hw04_yourname.zip”

0. (30 pts) Consider the RSA-OAEP implementation given the file “RSA_OAEP.py”, in which the random number R is an 8-bit unsigned integer. Using the public key

(e, N) = (65537,

70212284026476551287497867344660173062242619935306997607985987428352

052911293)

I encrypted my 4 decimal digit PIN and the resulting ciphertext is

3. =

60400943706823506830284280114139818288715016023417103465230780522075862

090739

What is my PIN? Submit your code used in finding my PIN.

2. (30 pts) Consider the ElGamal encryption algorithm implemented in the file “ElGamal.py”, which contains flaw. I used this implementation to encrypt a message using the following parameters:

q = 1331165794223730998214479682055290809139803703979 p = 15798526536523392606339408870250277547741169980745044091677540594725796 45748135029937498157701289733382892855161541090880434763143314443972153 58170585840641049172791477662283893716386808139204949694492602287891654 76714852286788193704615730161226643191202346299154076598693846801494696 9764702086638496649455657

g = 13506595604002954289133561458045824841600225029520439514675403629969068 29177892897165834647364258168679651849139471799974686507564147290193311 83463002574881956749358833871584578559474520218159551812002168419391427 22952287994862937927536192962206647014837543628741653234840706583671124 9965189758444892419490190

public key (h) = 65369531380434811091013169285144074654274264126019340876116721977646567

CS 411-507 Cryptography

45310844143947658061413114101871121703918315944733970349864572309970933

13100350016070503357404368252229384210531259359860240305661205857146822

25125302549720107383365077208839310065478286374555114097276440333388769

523316671044117487454589

And the resulting ciphertext is

18. =

36032169644425073570328427142654913561401061701260122712492737824987810

62854993590551963255079610858746338241608699542316440867356686210833642

81601595244890540839091779710540890021439859180686924557245365290222297

11162933532847371564973218717503016150130093952097139288475679032477430

33867199791859981117263

t=

42244680577489180150438247901105682607063917920969521526593784819134087

33761717162443465848326282188055945272315168573124840030020549530341444

75930796914614370187694754794376852744464747852209669396707112060640762

36087750024913718835564780638938635976122622009741305316868203434730711

663863398065249173925645

Can you find my message?

3. (20 pts) In Kerberos, the Ticket Granting Server includes the identity of the server ( ) in its

response to client: ( , ). What would happen if the identity of the server were not included? Does it lead to an attack?

Answer: If there are more than 1 server, or servers that are connected to each other, then you may want to include the identity of the server(S). This is important because unconstrained delegation/privilege may be granted to the user that allows a server to authenticate and access resources on another server on behalf of the user. In addition, the

encryption ( , ) must be done with respect to the ID number of the server because Cliff and Simon generate a shared key. If there are multiple servers, and encryption is done

without the unique ID number of the server, then the user may be able to access multiple servers with the same key.

4. (20 pts) Alice and Bob wants to establish a secure channel to communicate securely. Suppose Alice and Bob have long term RSA public and private key pairs: ( , ) and ( , ), respectively. They can use both the RSA signature and encryption algorithms and they know each other’s long term public keys. Show how Alice and Bob can achieve forward secrecy.

Answer: Forward secrecy is true only if the compromise of long term keys does not compromise past session keys, and this is achieved with station-to-station protocols. Alice and Bob can achieve forward secrecy with RSA signature and encryption algorithms by following the steps below. Alice can send a random R to Bob. Bob creates a new key pair, new public and secret key ( ′ , ′ ) used for encryption. A new signed S is created by signing the hash of the message R|| ′ , with . Bob sends ||S to Alice, who verifies

CS 411-507 Cryptography

the signature S with respect to for R|| ′ . Alice generates a random symmetric session key K, which is encrypted using ′ to produce X. The message M is encrypted using K to produce ciphertext C, and sends X||C to Bob. Bob can decrypt X using ′ to produce the key, K. Then, it is able to decipher C with key K, getting message M.

Bonus Question

5. (20 pts) Consider the DSA scheme implemented in the file “DSA.py”. The public parameters and public key are:

q = 897434149680309024926610536586679400252190817513 p = 97223004199266313523049166053330029092380541300786138924873181088471438 70545379404637091434559243236805927129454410272278795731083779730465094 30698205202875498266302306176257925262147992064864445546072751570317428 08122667064876655138748567945051878459968434840972135354745893868660267 009794876094057307360271

g = 46214972100579356123719885117119325103613181156099809788532369843145617 39819039313271820105098638480214293876477070872723831493769268422441714 87601439695456713666558346129313879250210049818171460576161508867009880 80166256173098608586829571972652947373953621679759300976489589724244798 80194787709852371142579

public key (beta): 45720223092558820344769930028614803638859051907129501277880999062740852 11488961037789403952097305384717414495555262717426606193932357718468172 82811568127366031229992622099530012382294391081176774238575412718410043 09469066208083385254271589636542160767902921803860270699359911081346969 522186114311390226677995

You are given two signatures for two different message as follows:

(message1, ₁, ₁) = (b”He who laugh last didn’t get the joke”, 867552604169477346883674422144796797059303863627, 243861349833858115605937030382497401412336608822)

(message2, ₂, ₂) = (b”Ask me no questions, and I’ll tell you no lies” 686145019080375810998084468514665120375929537329, 774583422188330317252601038183072854135396118762)

Also, you discovered that ₂ = 2 ₁ mod . Show how you can find the secret key .

Fall 2019