A demo for Stanford's Cryptography I course on cousera progrmming assignment

Your goal in this project is to break RSA when the public modulus N is generated incorrectly. This should serve as yet another reminder not to implement crypto primitives yourself.

Normally, the primes that comprise an RSA modulus are generated independently of one another. But suppose a developer decides to generate the first prime p by choosing a random number R and scanning for a prime close by.

The second prime q is generated by scanning for some other random prime also close to R. We show that the resulting RSA modulus N=pq can be easily factored.

Suppose you are given a composite N and are told that N is a product of two relatively close primes p and q, namely p and q satisfy |p−q|<2N1/4 (*) Your goal is to factor N.

Let A be the arithmetic average of the two primes, that is A=p+q2. Since p and q are odd, we know that p+q is even and therefore A is an integer.

To factor N you first observe that under condition (*) the quantity N−−√ is very close to A. In particular A−N−−√<1 as shown below. But since A is an integer, rounding N−−√ up to the closest integer reveals the value of A. In code, A=ceil(sqrt(N)) where "ceil" is the ceiling function. Visually, the numbers p,q,N−−√ and A are ordered as follows:

Since A is the exact mid-point between p and q there is an integer x such that p=A−x and q=A+x. But then N=pq=(A−x)(A+x)=A2−x2 and therefore x=A2−N−−−−−−√ Now, given x and A you can find the factors p and q of N since p=A−x and q=A+x.

question 1: Factoring challenge #1: The following modulus N is a products of two primes p and q where |p−q|<2N1/4. Find the smaller of the two factors and enter it as a decimal integer. N = 17976931348623159077293051907890247336179769789423065727343008115
77326758055056206869853794492129829595855013875371640157101398586
47833778606925583497541085196591615128057575940752635007475935288
71082364994994077189561705436114947486504671101510156394068052754
0071584560878577663743040086340742855278549092581

question 2: Factoring challenge #2: The following modulus N is a products of two primes p and q where |p−q|<211N1/4. Find the smaller of the two factors and enter it as a decimal integer. Hint: in this case A−N−−√<220 so try scanning for A from N−−√ upwards, until you succeed in factoring N. N = 6484558428080716696628242653467722787263437207069762630604390703787
9730861808111646271401527606141756919558732184025452065542490671989
2428844841839353281972988531310511738648965962582821502504990264452
1008852816733037111422964210278402893076574586452336833570778346897
15838646088239640236866252211790085787877

quesion 3: Factoring challenge #3: (extra credit) The following modulus N is a products of two primes p and q where |3p−2q|<N1/4. Find the smaller of the two factors and enter it as a decimal integer. Hint: use the calculation below to show that 6N−−−√ is close to 3p+2q2 and then adapt the method above to factor N. N = 72006226374735042527956443552558373833808445147399984182665305798191
63556901883377904234086641876639384851752649940178970835240791356868
77441155132015188279331812309091996246361896836573643119174094961348
52463970788523879939683923036467667022162701835329944324119217381272
9276147530748597302192751375739387929

question 4: The challenge ciphertext provided below is the result of encrypting a short secret ASCII plaintext using the RSA modulus given in the first factorization challenge. The encryption exponent used is e=65537. The ASCII plaintext was encoded using PKCS v1.5 before the RSA function was applied, as described in Lecture 11.4.

Use the factorization you obtained for this RSA modulus to decrypt this challenge ciphertext and enter the resulting English plaintext in the box below. Recall that the factorization of N enables you to compute φ(N) from which you can obtain the RSA decryption exponent.

Challenge ciphertext (as a decimal integer): 22096451867410381776306561134883418017410069787892831071731839143676135600120538004282 32965047350942434394621975151225646583996794288946076454204058156474898801373486412045 23252293201764879166664029975091887299716905260832220677716000193292608700095799937240 77458967773697817571267229951148662959627934791540

After you use the decryption exponent to decrypt the challenge ciphertext you will obtain a PKCS1 encoded plaintext. To undo the encoding it is best to write the decrypted value in hex. You will observe that the number starts with a '0x02' followed by many random non-zero digits. Look for the '0x00' separator and the digits following this separator are the ASCII letters of the plaintext. (note: the separator used here is '0x00', not '0xFF' as stated in the lecture)