Friday, April 15, 2011

RSA-Cryptography in Clojure

I've been playing around with some simple RSA cryptography in Clojure. It was inspired by this problem on Programming Praxis.

The problem is to create a working RSA key generator. Then, functions need to be made that take these generated keys and use them to encrypt and decrypt messages.

Clojure is a great tool for this project; Java's BigInteger library seems to be made specifically for cryptography. The function probablePrime() is especially awesome- I didn't have to do any work for prime generation or checking. Here is my find-prime function:

Using Java libraries in Clojure looks slightly ugly, but it works great once you've figured it out. And since Clojure is a Lisp, I can abstract out the ugliness into a macro and keep it far from my computation code.

I was playing around with running messages round-trip (encrypt, decrypt, and compare), and I noticed that they often didn't match up. I thought I had a huge bug, and made a questioning post on this tutorial. Turns out that I was missing the little fact that the message (m) must be less than the modulus (n). This makes a lot of sense in hindsight, but I racked my brain for a while on that problem.

Now that I've confirmed that my math is working, I've started working on ways to attack the algorithm. The standard way to determine decrypt key D is to factor modulus N. This doesn't use any of the code I just wrote, so I've been attacking by using sequential D's to decrypt a ciphertext with a known message. If the decrypted message matches what we started with, I know D is a potential decrypt key. This attack is easily parallelized in Clojure.

The source for solving the Programming Praxis problem is here. There's a README that should get you started playing around with your own RSA crypto. The next step would be to add some padding for security or conversion to/from ASCII text.

    No comments:

    Post a Comment