06-factoring

Factoring challenges

The goal of this exercises is to break RSA when the public modulus is generated incorrectly. This serves 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 by choosing a random number and scanning for a prime close by. The second prime is generated by scanning for some other random prime also close to R. We can show that the resulting RSA modulus can be easily factored.

Problem 1

N_string = '179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581'

• Given the N above which is a product of two primes p and q such that

| p - q | < 2 * fourth_root_of(N)

• Find p and q

Problem 2

N_string = '720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929'

• Given the N above which is a product of two primes p and q such that

| 3p - 2q | <  fourth_root_of(N)

• Find p and q

Problem 3

N_string = '648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877'

• Given N which is a product of two primes p and q such that

| p - q | < 2 ^ 11 * fourth_root_of(N)

• Find p and q

Solution

$ python script.py
-----------------
CHALLENGE # 1
-----------------

N =
   179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212
   982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935
   288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086
   340742855278549092581

p =
   134078079299425970995740249982058461274793658205923933777235614437217640300736627688911116143623
   26998675040546094339320838419523375986027530441562135724301

q =
   134078079299425970995740249982058461274793658205923933777235614437217640300737785609803489305577
   50569660049234002192590823085163940025485114449475265364281

-----------------
CHALLENGE # 2
-----------------

N =
   720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187
   663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119
   174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597
   302192751375739387929

p =
   219098495924755330922739885315839558989821760933449290300994235841272120781261500447211025709578
   12665127475051465088833555993294644190955293613411658629209

q =
   328647743887132996384109827973759338484732641400173935451491353761908181171892400358258164949547
   11821626076210364113848440012285863311027426121370050758081

-----------------
CHALLENGE # 3
-----------------

N =
   648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061
   417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504
   990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236
   866252211790085787877

p =
   254647961469961834380088165639739422293414542685241578463285819278857779699852228351438510732495
   73454107384461557193173304497244814071505790566593206419759

q =
   254647961469961834380088165639739422293414542685241578463285819278857779701063980544912465269708
   14167632563509541784734741871379856682354747718346471375403