# 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

287532292932372879703525070780346255116531323425007823617604162686051800343049289698776664399791425930664802923762707111240626602385730983871566174637661131860411739121001910243228116797931789015405819449969144179348998152310599080937309469616599904977763317572563733615817880241008696559706598126527764336908522188995771198297376483163153574768137712709809567962915615167714189337797270262953499220005367303949444652343328971205045868721401215816266425589413461with a modulus of…