0%

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 N^{1/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 = Ax and q = A + x. But then > > $> N = pq = (A − x)(A + x) = A^2 − x^2 >$ > > and therefore > > $> x = sqrt(A^2 -N) >$ > > Now, given x and A you can find the factors p and q of N since p = Ax 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 N^{1/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|< 2^{11}N^{1/4}$$  . Find the smaller of the two factors and enter it as a decimal integer. > > Hint: in this case $$A−N < 2^{20}$$ 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|< N^{1/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$

## 问题3

$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}$