[SOLVED] CS411-507 Cryptography Homework #4

• Note that there are three attached files: “py” for Question 1, “ElGamal.py” for Question 2, and “DSA.py” for Bonus Question.
• You are expected to submit your answer document as well as two Python codes for Questions 1, 2 and 5, respectively.
• Winzip your programs and add a readme.txt document (if necessary) to explain the programs and how to use them.
• Name your winzip file as “cs411_507_hw04_yourname.zip”

1. (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

c =

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 45310844143947658061413114101871121703918315944733970349864572309970933

13100350016070503357404368252229384210531259359860240305661205857146822 25125302549720107383365077208839310065478286374555114097276440333388769

523316671044117487454589

And the resulting ciphertext is

r =

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?

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:

Firstly, Alice picks a random number R and sends it to Bob.

Secondly, Bob generates a new RSA key pair (p_tb [public key], s_tb [private key]) for encryption, and letting RSA signing the hash of the message (R||p_tb) using 𝑠𝑘_𝐵, giving the signature S. Afterwards, Bob sends (p_tb || S) to Alice.

Then after Alice gets p_tb and S, she verifies that S is a valid signature with respect to

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 𝑎.