Breaking Weak RSA Keys

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.

Free Book about HTTP and Networking Performance

If you’re a web developer, the foundation of your technology stack is the Web and the myriad of networking protocols it rides on: TCP, TLS, UDP, HTTP, and many others. Each of these protocols has its own performance characteristics and optimizations, and to build high performance applications you need to understand why the network behaves the way it does.

Link: High Performance Browser Networking