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:
