How To Crack The Near Impossible When There’s a Weakness … Meet Fermat’s Attack on RSA
How To Crack The Near Impossible When There’s a Weakness … Meet Fermat’s Attack on RSA
With RSA, we generate two random prime numbers (p and q) with the same number of bits. This produces a modulus (N). If the modulus is 512 bits and more, it will take a long time to factorize the modulus, and is extremely expensive. But, there is an attack that is possible when the two prime numbers are fairly close to each other. This is Fermat’s attack, and is useful in creating CTF (Capture The Flag) examples, as using a normal factorization engine will likely not produce any results.
So here is a seemly extremely difficult challenge [here]:
Bob has used RSA to cipher a message to Alice. The cipher value is 287532292932372879703525070780346255116531323425007823617604162686051800343049289698776664399791425930664802923762707111240626602385730983871566174637661131860411739121001910243228116797931789015405819449969144179348998152310599080937309469616599904977763317572563733615817880241008696559706598126527764336908522188995771198297376483163153574768137712709809567962915615167714189337797270262953499220005367303949444652343328971205045868721401215816266425589413461 with a modulus of 1199400985302706265222161595178675143597094696047150991985843113203639218764011563617487234021128746235426459035930465501328178740120922022019451893401213830131519540649877584758261928670213322128486828328305824855552790113880630428870123372557007094548472161020046395010001668193139259640986734611568373598806014035766588117058105895837400359124315535840066927385728318424264025882748240865712881708613391630197064217280549357939589651829596174562112658554721561 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.
In this case, we have used 738 bit prime numbers, and so the modulus is 1,476 bits long — and should be almost impossible to crack. But, wait, there’s a clue:
His generator, though, has created the two primes numbers fairly near to each other. Using this information, find the original message.
And, so the prime numbers are relatively close to each other. In this case, we can use the Fermat Attack. If p and q are selected so that:
the Fermat’s factoring algorithm can effiently factor N. This is because:
with:
You can now clearly see that N can be factorized as such:
Fermat’s algorithm to find one of the factors works as follows:
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
The coding is here:
A sample run for a modulus of 128 bits is [here]:
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 [here]:
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'
This works because we can compute p and q, and thus ϕ:
With ϕ, we can compute the decryption value (d):
and then can decrypt to find the original message:
Conclusions
And, there you go. Now, solve this:
Bob has used RSA to cipher a message to Alice. The cipher value is 2193142991553525386966025798296206679718682541000136589325235700282315210030055026357167574396232704589021839463138650023062338173987193509527734523946881528479033837712127630516445580421215397978391688532028046864405822924907599508725183106421244054462761398538768070186155762480683026292405503543490167381 with a modulus of 63516691247915478206509100272138016907279781505674400855008902016204926545984143321956727701590244043367323552181831128896778067085753219835450315507674342590085884237473603353949718166558024007970004125598083604740246488804470224848050812578229983018181177020776207001057998638666483539708818442047173223551 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.
Here is the code: