Description
Notes:
-
-
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.
-
-
You are expected to submit your answer document as well as two Python codes for Questions 2 and 3, 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_hw03_yourname.zip”
-
-
(20 pts) Consider GF(28) used in AES with the irreducible polynomial p(x) = x8+x4+x3+x+1. a. (10 pts) Perform the following multiplication in GF(28):
(x7+ x6+ x4+x3+x2+1) (x7+x5+ x3+ x2+x) = ?
-
-
(10 pts) Show that the inverse of (x7+ x6+ x4+x3+x2+1) in GF(28) is (x7+ x6+x5+x4+x3).
-
-
(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.
-
(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
Fall 2019
-
-
(10 pts) Explain why this is not secure as anyone who obtains cp or cq can factor n.
-
-
-
(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”.
-
(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 =
-
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.
-
-
(10 pts) The attacker can decrypt c and recover m. Show how.
-
Fall 2019
-
(20 pts) Consider the following RSA parameters and a challenge ciphertext
N:
413105080470194761547414333064752004340942254255543889977200661958494
534011949464940412937181797972315194912124170337875272269953823057328
093111008990493716790723567095060040847336735549070359918268959251096
858672312347266354823678845903826815732607877891116752803838696450255
241260806010800776952451894277162217528982318247301802639309883561496
368306259480703690662603612912378956692729173285461990259772640312588
196857444617991899814097065255670996261112542559432923146658846703096
162046912513465456692329753804229233254440617551891667821068692593634
1811732104917605118575775329334829543752265141266783630832854187
-
-
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