# Public Key Encryption from Trapdoor Permutations – Integer Factorization

RSA的大整数分解。

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 | < 2 N1/4

Your goal is to factor N.

Let A be the arithmetic average of the two primes, that is. 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 given above the quantity N is very close to A. In particular

A – sqrt(N) < 1

as shown below. But since A is an integer, rounding sqrt(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, sqrt( N) and A are ordered as in figure 1.

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

In the following challenges, you will factor the given moduli using the method outlined above. To solve this assignment it is best to use an environment that supports multi-precision arithmetic and square roots. In Python you could use the gmpy2 module. In C you can use GMP.

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

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 AN < 220 so try scanning for A from N upwards, until you succeed in factoring N.

N = 6484558428080716696628242653467722787263437207069762630604390703787
9730861808111646271401527606141756919558732184025452065542490671989
2428844841839353281972988531310511738648965962582821502504990264452
1008852816733037111422964210278402893076574586452336833570778346897
15838646088239640236866252211790085787877

Factoring challenge #3: 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 sqrt(6N)  is close to  (3p+2q)/2 and then adapt the method above to factor N. Also note that   (3p+2q)/2 may not be an integer, which is a significant property for you to use.

N = 72006226374735042527956443552558373833808445147399984182665305798191
63556901883377904234086641876639384851752649940178970835240791356868
77441155132015188279331812309091996246361896836573643119174094961348
52463970788523879939683923036467667022162701835329944324119217381272
9276147530748597302192751375739387929

## 问题1和2

A为p和q的中点，有：
$$A = \frac{p+q}{2}$$

$$n = pq = (A-x)(A+x) = A^2 – x^2$$

$$x = \sqrt{A^2-n}$$

$$2A = p + q \geq 2\sqrt{pq} = 2\sqrt{n}$$

$$A \geq \sqrt{n}$$

## 问题3

$$A = \frac{3p+2q}{2}$$

$$A = \frac{6p+4q}{2}$$

$$2A = 6p + 4q \geq 2\sqrt{6p4q} = 2\sqrt{24n}$$

$$A \geq \sqrt{24n}$$

$$24n = 6p 4q = (A-x)(A+x) = A^2 – x^2$$

$$x= \sqrt{A^2-24n}$$