Cracking RSA for Fun and Profit
You may use RSA (or other public key crypt method) every day without even noticing it or actually bothering 'whats under the hood'. But for one day, you might ask, "what's actually under the hood anyway?"
Recently I've been reading a new book about algorithms -- Algorithms. In the Chap 1 Algorithms with numbers, the authors give a very good view of the underlying theory and smoothly outline the elegant algorithm. You never truly understand an algorithm until you get your feetWhands wet and actually code a working implementation.
So here's a small RSA skeleton implemented in haskell, which contains all bits including: Fermat's testing, getting random large primes, calculating mod inverse (extended-Euclid), the cipher functions and a simple test. Cracking RSA is actually very easy: just factorizing a very large number n = p * q (p, q are primes). No, i'm kidding. It's very hard, as factorizing large numbers has no efficient algorithm (so far). And it's actually what RSA's security comes from: you just cant easily (quickly) factorize a large number.
But what if the number is not so large? There's an algorithm called Pollard's rho heuristic. It's a Las Vegas algorithm, which means the algorithm may never terminate (what??) but if it does, it's 100% correct. In practice, the rho algorithm normally runs in O(n0.25) for a composite n. Here's my toy rho implementation.
Just for fun, you can try cracking a small-scale RSA or testing your code against this one. The online judge has no haskell or python support, i instead used java for its BigInteger class. To avoid rho running into an infinite loop, you might do some extra work (primality test, steps limit, random iterate function, etc.). Java BigInteger has provided the isProbablePrime function. To implement one, you can use the Rabin-Miller algorithm. It's a Monte Carlo algorithm, which means it may not be 100% correct but the more time you run it, the more correct it is.
To have more fun, I encrypted the src code for the above two problems: crack rsa and prime test. Though the keys in the original problem are less than 264, to make it a little harder for you, i used a slightly larger key (291 ~ 292). Try deciphering the secret code, given the public key as (5, 3136682460441793638416097209). :)
PS, for algorithms, please never forget to refer to the book CLRS. Just FYI, the R in CLRS is also the R in RSA. =) Chap 31 has wonderful materials about various number theory algorithms.
