Your cart is currently empty!
1. (20 pts) The composite number n is the product of two large primes, namely p and q. Assume that nobody knows the factorization of n. Consider the following function H(x) = x2 (mod n). H(x) is one-way function since it is difficult to compute the square root of x modulo a composite…
Assume that nobody knows the factorization of n. Consider the following function
H(x) = x2 (mod n).
H(x) is one-way function since it is difficult to compute the square root of x modulo a composite number when the factorization is not known.
Explain your answer using on the example, where n = 15, i.e. p = 3 and q = 5. (10 pts)
510199234220351635769753579003640646511269683368666689283064468492360
478957885883733073466895536294535102461614047593850516003701938960081
2468312274731287 q =
104677858040236631540811598909166707511976842840505964536630741129499
224685702253698304193500442968305523686358763901573500616740416774094
79215017880761471 e1 = 65537
e2 = 65539 c=
493463293694628543632717824483152110996815144346405999746218546713924
271393716352103453630314731535994643483208423227406355539606429535108
951960692292587865368917490218414372006590261848443504441655164271774
042488924390494483343994111890450561851024227047380917594733133111636
25490140702356058569205275317138
where c is the ciphertext as a result of the double RSA encryption with e1 and e2. Find the equivalent decryption key d3 and decrypt the ciphertext with a single modular exponentiation operation. (20 pts)
59300007034639909939573758056469081496649095362931218335710263559636829
49146321467539965430945424841886131424498862624434038656427479869937122
47102261785731001793506234552406777422807558593883968273003074115213087
25481313615050599976223074746012316066224478374065904742491869819255200
529839123356150617924773 e: 65537
Consider also the following ciphertext,
c:
47446751200838582684511548326026682588511648894181169756283983741637372
57124292706175418868061694959118427768504557806807530086853543168186753
32535950686037380945832344300200185984794110431027225082969830503309495
98947760334702343661636595593088242435796182825602462354582903741935054
242424335737738087473281,
which is the encryption of my PIN of four digits. The textbook RSA without padding is used. Find my PIN.
N:
140551657748123311843904632833471669259677424177527429472076641459146
867906661942068298379563181123587514898171198345842702518087577996533
400370831952801883330035838563895672878817032429070070491801818686348
972449259014970161691017147789125584023630380720107022841065881140401
317726964037566281222748970712203 e: 65537
c:
107370145208181012882157035957831285007639861193502148958526088911145
111312354857879651315298430491706057927363584703699650832365083149730
388058817716227351580643780596923032021272650197705800013301435840379
066513203705883311188119667109083477935129425038367472101389436165688
559837901078746430028139353590988
The instructor (accessible via erkays@sabanciuniv.edu) is the oracle that you can submit your queries c’ ¹ c via e-mail. Your queries must be in the following form
c’ = int(“your query here as an integer”)
I challenge you to find m. (20 pts)
Notes:
def egcd(a, b):
x,y, u,v = 0,1, 1,0 while a != 0:
q, r = b//a, b%a
m, n = x-u*q, y-v*q
b,a, x,y, u,v = a,r, u,v, m,n
gcd = b
return gcd, x, y
def modinv(a, m):
gcd, x, y = egcd(a, m)
if gcd != 1:
return None # modular inverse does not exist
else:
return x % m