DreamMX Weblogs

A simple concept on cracking RSA

The security of RSA is based on a math problem. For 2 huge(1000 bits) prime numbers p and q. We have n = p * q. Agreement on that: knowing n, calculating p and q is impossible right now.

But if p and q are close together (close means |p-q| < 1,000,000,000), the we’ve got a change

n = p*q = (p+q / 2)^2 – (p-q / 2)^2

Denotes T = √(p+q / 2)^2 and S = √(p-q/ 2)^2

if p and q are close

then S is close to 0

and T is close to √n

now start look at the following numbers

⌈√n⌉,⌈√n⌉+1,⌈√n⌉+2,⌈√n⌉+3,…

stop when we find a n that make t^2 – n is a perfect square number

and we’ve got the value of p and q.

Fun