How would you break a very weak RSA key? In my example, I had the public key given:
N = 965210800519627751
e = 162419
The task is to break the public key by calculating the corresponding private key (d).
I used the open source tool YAFU (http://sourceforge.net/projects/yafu/) to factorize the modulus N:
# ./yafu "factor(965210800519627751)" fac: factoring 965210800519627751 fac: using pretesting plan: normal fac: no tune info: using qs/gnfs crossover of 95 digits div: primes less than 10000 fmt: 1000000 iterations Total factoring time = 0.0410 seconds ***factors found*** P9 = 982451429 P9 = 982451419 ans = 1
Now you know that p = 982451429 and q = 982451419 or the other way around. With this knowledge, the RSA key is basically broken!
With some Java, you can easily calculate the corresponding private key d:
BigInteger e = new BigInteger("162419"); BigInteger N = new BigInteger("965210800519627751"); BigInteger p = new BigInteger("982451429"); BigInteger q = new BigInteger("982451419"); BigInteger phi = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE)); BigInteger d = e.modInverse(phi); System.out.println(d.toString());
By knowing d, you are in possession of the private key and able to act as the real key owner. Of course, this approach is limited to (very) weak RSA keys since factoring a big number is very hard and takes exponentially much time.