Sunday, August 09, 2009

A new approach to cracking RSA...

I've spent 10 years tinkering with RSA factoring algorithms. Everybody needs a hobby, eh? I've tried many, many different approaches in solving the problem more efficiently than is currently practiced.

RSA factoring is plain stupidly simply. Find two prime numbers that are the factors of one very large number.

For example,

16347336458092538484431338838650908598417836700330923121
81110852389333100104508151212118167511579

× 19008712816648221131268515739354139754718967899685154936
66638539088027103802104498957191261465571

= 31074182404900437213507500358885679300373460228427275457
20161948823206440518081504556346829671723286782437916272
83803341547107310850191954852900733772482278352574238645
4014691736602477652346609


So far I've explored Russian Peasant division, bit multiplication shortcutting, bit reversal with vector unit multiplication, and traditional sieving and plain bruteforce. A few years back I happened across a new method - but it was only reliable in some cases. The fantastic news is that it when it did work - it was incredibly fast. I was able to factor 384 bit numbers in a few minutes, rather than hours.

I've lost the code, but I finally remembered the basic algorithm. And it occurred to me that perhaps it was simply a rounding error in my path decision algorithm.

Anyway - my "project rotation" is upon me again, and hopefully this time I will finally succeed.