Cryptography Homework #4 Solution

(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 number when the factorization is not known.




a. Explain why H(x) is not a good cryptographic hash function by discussing the properties of cryptographic hash functions. (Hint: Discuss non-invertibility, weak and strong collision resistance.) (10 pts)




b. Explain why H(x) is not even a good hash function by demonstrating its output is biased. Explain your answer using on the example, where n = 15, i.e. p = 3 and q = 5. (10 pts)




(30 pts) In order to increase security, Bob chooses the modulus n and two encryption
exponents, e1 and e2. He asks Alice to perform double encryption, i.e. to encrypt her




message m to him by first computing c1 me1 (mod N), then encrypting c1 to get c2 c1e2 (mod N). Alice then sends c2 to Bob.




The double encryption does not increase security over single encryption and in fact is equivalent to single encryption with a private key e3. Explain why? (10 pts)



Consider the following p = 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)




(20 pts) Consider the following RSA parameters:



N:

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.




(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 =




me 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 running on a remote server) with a ciphertext c’ c, and receives the corresponding plaintext m’ = c’d mod N.




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



Consider the following RSA parameters and a challenge ciphertext



N:

140551657748123311843904632833471669259677424177527429472076641459146

867906661942068298379563181123587514898171198345842702518087577996533

400370831952801883330035838563895672878817032429070070491801818686348




972449259014970161691017147789125584023630380720107022841065881140401

317726964037566281222748970712203




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:




You can use the Python function pow(m, e, N) to compute modular exponentiation.
You can use the following two Python functions to compute gcd and modular inverse



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