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
Your goal is to factor N.
Let A be the arithmetic(算数) average of the two primes, that is A=2p+q. 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, we show below that:
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. You have now factored N !
Further reading: the method described above is a greatly simplified version of a much more general result on factoring when the high order bits of the prime factor are known.
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.
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 in the box below.
For completeness, let us see why A−N<1. This follows from the following simple calculation.
First observe that A2−N=(2p+q)2−N=4p2+2N+q2−N=4p2−2N+q2=(p−q)2/4.
Now, since for all x,y:(x−y)(x+y)=x2−y2 we obtain A−N=(A−N)A+NA+N=A+NA2−N=A+N(p−q)2/4
Since N≤A it follows that A−N≤2N(p−q)2/4=8N(p−q)2.
By assumption (*) we know that (p−q)2<4N and therefore A−N≤8N4N=1/2 as required.
deftask2(): #初始化大整数n n =gmpy2.mpz('6484558428080716696628242653467722787263437207069762630604390703787'+'9730861808111646271401527606141756919558732184025452065542490671989'+ '2428844841839353281972988531310511738648965962582821502504990264452'+'1008852816733037111422964210278402893076574586452336833570778346897 '+'15838646088239640236866252211790085787877') #初始化得到n的平方根的整数部分 A=gmpy2.isqrt(n)+1#A为整数部分 向上取整A^2>n #循环次数 max_count=pow(2,20) #得到x for i inrange(max_count): x,r=gmpy2.isqrt_rem(A**2-n) #得到p和q if r==0: p,q=A-x,A+x #检验p和q是否为素数且p*q=n if gmpy2.is_prime(p) and gmpy2.is_prime(q) and gmpy2.mul(p,q)==n: print('[!] Found it count=',i) print('p=',p) print('q=',q) break A+=1
if __name__ == '__main__': task2()
Factoring challenge #3:
The following modulus N is a product 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: first show that 6N is close to 23p+2q and then adapt the method in challenge #1 to factor N.
1 2 3 4 5
N =72006226374735042527956443552558373833808445147399984182665305798191 \ 63556901883377904234086641876639384851752649940178970835240791356868 \ 77441155132015188279331812309091996246361896836573643119174094961348 \ 52463970788523879939683923036467667022162701835329944324119217381272 \ 9276147530748597302192751375739387929
defisqrt(n): x = n y = (x + 1) // 2 while y < x: x = y y = (x + n // x) // 2 return x
deftask3(): n=720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929 getcontext().prec=350#设置精度 A=Decimal(isqrt(6*n))+Decimal(0.5) whileTrue: x=Decimal(A**2-6*Decimal(n)).sqrt() p=int(A-x) q=int(A+x) if p*q==6*n: if p%3==0and q%2==0: p//=3 q//=2 break if p%2==0and q%3==0: p//=2 q//=3 break A+=1 print(p) print(q) if __name__ == '__main__': task3()
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 PKCS.
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): 22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540
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)
1 2 3 4 5
公钥就是 N，e 而 私钥就是N，d 加密 m^e ≡ c (mod n) 解密 c^d ≡ m (mod n)