Cryptography Homework #2 Solution

(20 pts) Consider the following modulus: n=939239898295368386454257928783918841858520900150470969283254956807
35077974573254200941142654635659889069058397106827931666572379715390977




19986173062295693497645667236532793240467126595225167687394644118349823

12322385289785140165924807414291336465904667368386284745379274841151463

06435052269979805285188280829




Consider also the following number:




y=569447780950260645088033205573241948282176043580025848609939831272462

57172572625621288924208876440674553832158479040031724187898214806257072

82396616835234960661153736217701847786032842029574125560248551274952317

68758619888643277232670079591128187448318843774948004643049766898511829

57989115066715277845807162




The integer y is a quadratic residue modulus n, and its square roots are known:




{

11539293044780349664317193739835099161008802876501927386196632728052884

86457071353220342763943110690181368461236858334836627848090394205820290

38970046491030557432857518959706904266096947598325119760350627655865274




04034628524567695175048634551582051994897593554954834163440853023500476

963332472457537871514030,




65462078929074573896561682473134429960343753900612807859205872292206976

67376676479563868864251525057291006528153746980252046514530119307032029

50803240249666774951224266896062048302455238692324439395393870291836518

68429281477875679397889633306037656227303018935833418527282673149878942

564121394686954099450002,




28461910900462264748864110405257454225508336114434289069119623388528101

30080648940530245401212040931615899311556935812914610723441419790687956

66502989319682989615499386383261998410204283824444300069017964690475803






70099697036140913082851795827608934239433819692641119400201441996427492

488148585118331088830827,




82384696784756488981108599138556785024843287138545169542128862952682193

11000254066873771501520455298725537378473824458330029389881144891899695

78336183078319207133866134319617142446562574918443619704061207326447048

34494349989448897305692794582064538471839245073519703764043262122805958

088937507347747316766799




}




Factor n.

(20 pts) Consider the group 46∗.



How many elements are there in the group 46∗? List the elements of 46∗. (5 pts)



Find all the generators in the group 46∗. (5 pts)



How many elements are there in the group 46∗? The group 46∗ consists of all residues in 46∗, which are relatively prime to 46. List the elements of 46∗. (5 pts)
Find the generators in 46∗. (5 pts)



(30 pts) Consider the following numbers:



p=

12997110888321186459316436989724265349460712629389513072528028592113

49992754931553520927567347008982230373355213726438110126392805826019

0003283395786606613




q=

12208677561088985820124024567796306546470708824672729385334541873189




39879463365005233532430971148076391902849072776428860469422008793314

8985261608483250761




n=p×q




m=

10450838352783190882303686938664826175340681976411643293757703902133

48484538714692972539143948801213556080672371890885302410647091183100

89323613713098921642285063603825756456138538154719968501891170428872

54615084192691202705357722526411190331450509121790329499844817869229




5392732881494063202944747727969714684 e = 67





Compute c me mod n (Hint: you can use pow(m, e, n) function of Python) . (5 pts)



Compute the number such that e d 1 mod (n), compute m’ cd mod n, and show that m = m’. (5 pts)



Compute cd mod n using Chinese Remainder theorem and p and q. You are allowed to perform exponentiation operation only in mod p and mod q. List also



the following values: cp = c mod p, cq = c mod q, dp = d mod (p-1), dq = d mod(q-1), p-1 mod q, q-1 mod p, cpdp mod p, and cqdq mod q. (15 pts)




Measure the execution times of the exponentiation methods in (b) and (c) using the Python function as follows:



import timeit

import time




…




iter = 100

t1 = time.clock()

for i in range(0, iter):

pow(c, d, n)

t2 = time.clock()




print t2-t1




Which one is faster? (Warning: In exponentiation with CRT, you should not include the execution times of values that can be precomputed, such as p-1 mod q and q-1 mod p)




(15 pts) Solve the following equations of the form ax b mod n and find all solutions for x if a solution exists. In case there is no solution, your answer must be “NO SOLUTION”, and explain why there is no solution.






n = 120032070747790791430008804988 a = 7211941535834517096225500817



b = 102092299425228521972149597163 (5 pts)




n = 120032070747790791430008804988
a = 44575693167043501900449109190

b = 84664078284205068314514580089 (5 pts)




n = 120032070747790791430008804988 a = 404



b = 2124884389680246530198080982220 (5 pts)











5. (15 pts) Consider the following two polynomials over GF(2) :




p1(x) = x6 + x + 1

p2(x) = x6 + x2 + 1




Are they irreducible over GF(2)? Explain your answer. (5 pts)



Are they primitive over GF(2)? You need to show whether the roots of these



polynomials generate all nonzero elements of the field GF(26) which has 64 elements. (10 pts)