Cryptography Homework 3 Solution

Description

Notes:

0. • Note that there are four attached files: “rainbow_table.py” and “rainbowtable.txt”for

Question 2, “DeterministicRSA.py” for Question 3, and “RSA_Oracle.exe” for

Question 4.

0. • You are expected to submit your answer document as well as two Python codes for Questions 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_hw03_yourname.zip”

0. (20 pts) Consider GF(2⁸) used in AES with the irreducible polynomial p(x) = x⁸+x⁴+x³+x+1. a. (10 pts) Perform the following multiplication in GF(2⁸):

(x⁷+ x⁶+ x⁴+x³+x²+1) (x⁷+x⁵+ x³+ x²+x) = ?

1. 2. (10 pts) Show that the inverse of (x⁷+ x⁶+ x⁴+x³+x²+1) in GF(2⁸) is (x⁷+ x⁶+x⁵+x⁴+x³).

2. (20 pts) Consider ten digests in the attached file “rainbow_table.py”, each of which is the hash of a six-character password. Your mission is to find those passwords using the rainbow table given in the attached file “rainbowtable.txt”. Complete and submit the

Python code in the file “rainbow_table.py” such that it finds and prints out the ten passwords corresponding to the digests.

2. (30 pts) Alice encrypts the private factors of the modulus using her private key. In order to increase security, she multiplies them with a random integer k (a process called blinding). Namely, she performs the following operations

cp = (kp)^e mod n and cq = (kq)^e mod n,

where n = 747372949454149436885208416083388796678696614660453978803842554637072100 520257529287801060371877914368027907243785997943702721266897995181210414 436447625114963144567710657499895871810053836815755989208623348462365830 708027870223037926687241571308987100473209658964588388397741550650834797 600133480753332361960252483056771297158113234167358462869807973676092078 962617580524997867621533703954821281050382039213021452874845243976501484 112310918488081152746197006658899100043240377375004836827986722067874702 076704248425390275240331056024301758458530143367302003395305880941500202 5715734068685302158511640316340598416777

e = 65537

CS 411-507 Cryptography

1. 1. (10 pts) Explain why this is not secure as anyone who obtains cp or cq can factor n.

1. 2. (20 pts) Factor n assuming cp = 623709273628034036814389297524687970028057495682348345908982630083854 932669837119284112525665830142233550607128099003613496995843014009182 141394211099982801922370191453466049614518404943679323311752714171046 958785289657261290820594487492466610593599333927207251648998504889980 356327739000862539507880368510898071446637881456633664461204489565393 868010308825271004850404895261626033765746990442683462575675517882371 234316014652766041264278719895505051198414098623409581570370290847514 605529688221650404904264023473553280359297806211877728733226686711793 5272468491447326467928608953581142170727780193982988625594898212

cq = 679221645917832066313492211367261424413328679516720594038799416329512 194046450251657896476455819039058295595731908752792760635499527878700 282781025221660439360255161999705970638943772144410998611868725857155 877049112354280809889944907016443807025972530086743215515555247671544 507868976333418842880027255259634900700522283562378366824312439100797 954265757723208217862908610096370720071446943692881614227609372208093 718049504510338817487571007375349892232618914766099258256017975935431 335594246909080865158769385476074919202318233179709454365607098781565 4088544115591473666250129130603910045357579318640054232668524224

and decrypt the following ciphertext cm = 210547780095545635715450725818861745718973659325310166307414507495398 139524507102180675301027968087416805407288296667519512114345774662968 673635954941540154985236380959721011493440764457964432980295141843099 489696899655462728699778829510479626071565664175282653187620286822265 953911119368969058766576397047595428329856132671662949735571090303532 492178717111413590350400250611448928393379661128777750439840055949445 951939739725488726052683079672374888172304356021283333227271849867183 583784776012670787031359181758309039373688352316333848144246324188237 5466824267640258884419635167163135753490195544303858749215914789

and print out the plaintext message. For the solution of this question complete and submit the attached file “DeterministicRSA.py”.

4. (30 pts) Consider the following security game. Suppose that an attacker wants to decrypt the ciphertext c encrypted using the RSA algorithm and obtain the plaintext m, where c =

   13. ^e mod N. She knows neither the private key d nor the factorization of the modulus N.

However, she can query an oracle (e.g., a program) with a ciphertext c’ c, and receives the corresponding plaintext m’ = c’^d mod N.

1. 1. (10 pts) The attacker can decrypt c and recover m. Show how.

CS 411-507 Cryptography

2. (20 pts) Consider the following RSA parameters and a challenge ciphertext

N:

413105080470194761547414333064752004340942254255543889977200661958494

534011949464940412937181797972315194912124170337875272269953823057328

093111008990493716790723567095060040847336735549070359918268959251096

858672312347266354823678845903826815732607877891116752803838696450255

241260806010800776952451894277162217528982318247301802639309883561496

368306259480703690662603612912378956692729173285461990259772640312588

196857444617991899814097065255670996261112542559432923146658846703096

162046912513465456692329753804229233254440617551891667821068692593634

1811732104917605118575775329334829543752265141266783630832854187

2. 5. 65537

c:

286011333479246811807036978298499172055797623822007560823628330407176

989331751815848494737394310492374805419675958067102325270756298968875

428244016352736458046904203412669134207806910534413220489710408452767

455368567189168921003750345234473915004072109521598843246444074965165

007427386987929674642591506744871181356247565764232892236100024802851

129256309465367597958913617035234759551640734971193268573642824284719

009304086710729931481730871492097430958962565736552256356850187124726

045482360175673464358349365112652477377441584665739736701619949825887

312761535693506114283123294171040950993106172221548552046342629

The RSA oracle is implemented as a Windows exe file (RSA_Oracle.exe) provided in the assignment package. If you are unable to run the RSA oracle, you can send your query to Erkay Savaş (accessible via erkay.savas@sabanciuniv.edu)

I challenge you to find m corresponding to the ciphertext c. Note that m contains a meaningful message. Convert it to bytes to discover what it is.

Fall 2019