RSA: Hacking and Cracking

Military commanders and diplomatic figures have relied upon codes and encryption for hundreds of years. Now in the Information Technology era the strongest encryption techniques are not just accessible to the those who historically were the main users, but to businesses and even to the home user on his personal computer.

The battle between codemaker and codebreaker was revolutionised by the advent of computers, and their power over numbers. At first it seemed that the codebreakers had the advantage. Enormous key-spaces could be searched in a manner impossible for manual labour. But the codemakers fought back to make longer keys and more complicated systems. Who will be the eventual winner?

One great impact on cryptography was when mathematicians became interested in the subject. Simon Singh's book The Code Book mentions the breakthrough made by Polish mathematician Marian Rejewski in finding the flaw in the infamous Enigma code used by the Germans in World War II. It was number theorists who gave the codemaker camp a boost with the invention of public key cryptography in the 70s.

Although many of the encryption schemes used today and in the past are each worthy of study, this report concentrates on RSA. Public key cryptosystems make use of special mathematical functions known as trapdoor one way functions. It is easy to encrypt (one-way) but extremely difficult to get the decrypted message. That is unless you know the secret information that lets you use the trapdoor. This secret can be used to quickly reverse the encryption and get the original message. One of the aims of this report is to investigate the possibilities that the RSA system is not as secure as it was once predicted.

Mathematica, a powerful programming tool, has been predominantly used (or will be), but I have (will) also included several java applets to allow those without that resource to see some of the systems working.

Please note that a log of the work in progress is available. The final report will be published on its own.

Ronan Killeen
Back to home.