October 1, 2012 by Nakul
All of us have heard of cryptography. We are familiar with several algorithms. But how many of us have tried to break those algorithms? Have we ever put ourselves in the place of an attacker? Have we tried to extract data without knowledge of the key? In this article you will acquire a basic idea about the different techniques used and the challenges faced in breaking an algorithm.
Wikipedia defines cryptanalysis as the art and science of analyzing information systems in order to study the hidden aspects of the systems. The aim is to be able to extract the data from encrypted systems without the knowledge of the key. Cryptanalysis has proved to be a very important tool throughout history including the two world wars.
One of the simplest categories of ciphers is the substitution ciphers. Let us see how mono-alphabetic ciphers are broken. In all languages, certain letters are used more often than others. In English, the most frequently used alphabet is ‘e’. The frequencies of different letters are as shown.
In substitution ciphers, even though the letters are jumbled up the frequencies of those letters are not affected. So, we have to perform frequency analysis of the cipher text. We can conclude that the letter having the highest frequency must be ‘e’ and so on. Once a few letters are obtained, it is possible to get the entire message by guessing.
The same technique holds good for polyalphabetic ciphers also. If we consider digraphs, we shall have to perform frequency analysis for a pair of letters. In the English language, ‘th’ has the highest frequency. One disadvantage of this method is that we require quite a large amount of ciphertext for performing frequency analysis. We cannot expect accurate results if frequency analysis is applied to short sentences.
Such techniques exist for all known encryption algorithms from the Vigenere cipher to DES. A detailed explanation of these would probably serve no use here, however I will try to give a
general idea. The basic idea for breaking the Vigenere cipher is that certain letters are often followed by particular letters. For example ‘q’ is almost certainly followed by ‘u’. Also, the key length is finite. So the key will be repeated for a long message. If sufficient amount of ciphertext is available, it is possible to determine the length of the key and that greatly simplifies things.
No cipher, with the exception of a one-time pad, is unbreakable. However in case of one-time pad the problem is with the key distribution. So modern cryptography focuses not on designing unbreakable ciphers, but to make the ciphers so hard to decrypt that either the cost outweighs the advantage gained by breaking the algorithm or it would take an extremely long time to break it(in the range of years).
The evolution of cryptography and cryptanalysis is like a cat and mouse game. The cryptographers come up with an algorithm and the cryptanalysts break it. So the cryptographers come up with a stronger algorithm and this has been going on from the advent of cryptography. But there is one important difference between cryptographers and cryptanalysts. A person who comes up with a fairly good algorithm is applauded and receives lots of honors. But if you break the toughest of the tough algorithms usually the matter remains classified. Say, a person breaks an algorithm that is being used for global communication. Any country would greatly benefit from intercepting communications between other countries. So we rarely hear about breaking of algorithms until they go out of use.
There are some very interesting cryptographic problems that a curious reader might find intriguing. One such example that you would probably find very interesting is the Beale Ciphers. It consists of a set of three ciphertexts, two of which remain unencrypted. You could easily find the details regarding this with a little help from Google. For anyone who is interested in cryptography, ‘The Code Book’ by Simon Singh is a must read. It is an amazing book with cryptography explained in a very non-technical way.
Auhtor: Nakul Rao I