Normally, in RSA, we select two prime numbers of equal length (\(p\) and \(q\)), and then multiply these to give a modulus (\(N=p.q\)). If these numbers have a small difference between them, we can use the Fermat's attack to factorize the modulus [1]. With this, we discover \(p\) and \(q\), and where it is then easy to crack RSA.
CTF Generator: Fermat’s attack |
RSA
If \(p\) and \(q\) are selected so that \(p-q < N^{\frac{1}{4}}\), the Fermat’s factoring algorithm can effiently factor \(N\). This is because:
\(N = pq = {(\frac{q-p}{2})}^2-{(\frac{p+q}{2})}^2 = x^2 - y^2\)
with:
\(x =\frac{q-p}{2}\\y =\frac{p+q}{2}\)
You can now clearly see that \(N\) can be factorized as such:
\(N = (x+y)(x-y)\)
Fermat’s algorithm to find one of the factors works as follows :
\( a = \sqrt{N}\\ b = a \times a-N\\ \textrm{While b is not a perfect square:}\\ \hspace{2em} a=a+1\\ \hspace{2em} b = a \times a-n\\ \textrm{return} \hspace{1em} a - \sqrt(b) \)
In Python, this case be coded as:
a = math.isqrt(n) b = a*a-n while (b<0): a = a+1 b = a \times a-n p = a-math.isqrt(b) q = n//p
This works because we can compute \(p\) and \(q\), and thus \(\phi\):
\(\phi=(p-1)(q-1)\)
With \(\phi\), we can compute the decryption value (\(d\)):
\(d=e^{-1} \pmod \phi\)
and then can decrypt to find the original message:
\(M=C^d \pmod N\)
Coding
The coding is here:
from Crypto.Util.number import * from Crypto import Random import Crypto import sys import math from sympy import isprime import random bits=60 if (len(sys.argv)>1): msg=str(sys.argv[1]) if (len(sys.argv)>2): bits=int(sys.argv[2]) e=65537 m= bytes_to_long(msg.encode()) p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes) q=p-random.randint(0, 1e6) while (isprime(q)==False): q=q-1 n=p*q a = math.isqrt(n) b = a*a-n while (b<0): a = a+1 b = a*a-n p = a-math.isqrt(b) q = n//p c=pow(m,e,n) print(f"Bob has used RSA to cipher a message to Alice. The cipher value is {c} with a modulus of {n} and using e={e}. His generator, though, has created the two primes numbers fairly near to each other. Using this information, find the original message.") print("\n\nAnswer:") print(f"C: ",c) print(f"N: ",n) print(f"Number of bits in p and q: ",bits) print(f"Number of bits in modulus (N): {2*bits}\n") print("p=",p) print("q=",q) PHI=(p-1)*(q-1) try: d=pow(e,-1,PHI) except: print("\n** M^e<N. Cannot decrypt, as message or e is too small. Try with e=65,537 **") sys.exit() m=pow(c,d,n) print(f"d=",d) print(f"PHI=",PHI) print(f"Message: {long_to_bytes(m)}")
A sample run for a modulus of 128 bits is:
Bob has used RSA to cipher a message to Alice. The cipher value is 163640244736475264288617605268290402562 with a modulus of 183141006746011742652247096424431158877 and using e=65537. His generator, though, has created the two primes numbers fairly near to each other. Using this information, find the original message. Answer: C: 163640244736475264288617605268290402562 N: 183141006746011742652247096424431158877 Number of bits in p and q: 64 Number of bits in modulus (N): 128 p= 13532960014202603137 q= 13532960014202989021 d= 162123817803326628624174300468312850433 PHI= 183141006746011742625181176396025566720 Message: b'hello'
A sample run for a modulus of 1,536 bits is:
Bob has used RSA to cipher a message to Alice. The cipher value is 173284951293572291250839186621487494049936207251738400377703956400168906610668033223270973958114360228834022350572338726702702027047550055772866993601387898138936380751535913574957680342278398243481299576877250472121525698039757340298771634758953016190864536835768628624237358660584646932011948497590655098498125696224434012881354567876714823929926426720784456838123369962212509208231932415266940535887883251868978995414924113231418528526155226044274542331397782 with a modulus of 929809185932964364118808947745483968960479912387119008303091543027739729519865921764510613412307228552529787614372220949004742592245391409478671282583683647459409097855890490585769559075614197001740003730776304685186387325988680410010404144046181433497286980907371670481907756315724145970698266494278076535569042617839696393566855968773364048376681915748790902841537355957232112833114482342941258990269297860844835373264344637445998914214834443977921401895403599 and using e=65537. His generator, though, has created the two primes numbers fairly near to each other. Using this information, find the original message. Answer: C: 173284951293572291250839186621487494049936207251738400377703956400168906610668033223270973958114360228834022350572338726702702027047550055772866993601387898138936380751535913574957680342278398243481299576877250472121525698039757340298771634758953016190864536835768628624237358660584646932011948497590655098498125696224434012881354567876714823929926426720784456838123369962212509208231932415266940535887883251868978995414924113231418528526155226044274542331397782 N: 929809185932964364118808947745483968960479912387119008303091543027739729519865921764510613412307228552529787614372220949004742592245391409478671282583683647459409097855890490585769559075614197001740003730776304685186387325988680410010404144046181433497286980907371670481907756315724145970698266494278076535569042617839696393566855968773364048376681915748790902841537355957232112833114482342941258990269297860844835373264344637445998914214834443977921401895403599 Number of bits in p and q: 768 Number of bits in modulus (N): 1536 p= 964266138539026145823374211375803019841139710487135946774809488030518307007440121143275342376019000710960332724667920224303356133314109195093717403426230258172366357273346917309394404204339143835960699510886198709837226870885635113 q= 964266138539026145823374211375803019841139710487135946774809488030518307007440121143275342376019000710960332724667920224303356133314109195093717403426230258172366357273346917309394404204339143835960699510886198709837226870885892023 d= 827516981062789149121225712119121159918182276421006307845864480067427181648614059519944619810178124109791490641675519649855800863297022212500762315932351436674931022943383503126419901310761085623700950571509063939040029503378881580819862678863086019450331301120761431674472769816453080351012279675598132115357975752980670186542769720223344846212905080397272084691308044561926354058525777420045314429412790401138317053930008157653742739620214906336090425439756817 PHI= 929809185932964364118808947745483968960479912387119008303091543027739729519865921764510613412307228552529787614372220949004742592245391409478671282583683647459409097855890490585769559075614197001740003730776304685186387325988680408081871866968129141850538558155765630799628335341452252421079290433241462520688800331289011641528854546852698599040841467142078636213318965769797305980653965998208544443575463242056026964586056965524599892442437024303467660123876464 Message: b'hello'
References
[1] De Weger, B. (2002). Cryptanalysis of RSA with small prime difference. Applicable Algebra in Engineering, Communication and Computing, 13(1), 17-28. [here].