03

Simple ciphers explained

If u havcme dis far rdng dis buk, vblveuwudfind dis txtprtyez 2 read. So was that really that tough to understand? We hope not. After all, we do it everyday – saving characters in our text messages on mobile phones and during chat to type faster. But it’s not a new concept. The current generation can’t take credit for this invention; it’s not our invention. Our forefathers used it in telegrams. Back when sending telegrams was charged per character, they’d try to squeeze up characters to form another word which could easily be related to the word that it was meant to replace – much the same way we abbreviate text messages today.

SIMPLE CIPHERS EXPLAINED

Starting off with the basics, we take you through the elementary types of ciphers out there

If u havcme dis far rdng dis buk, vblveuwudfind dis txtprtyez 2 read. So was that really that tough to understand? We hope not. After all, we do it everyday – saving characters in our text messages on mobile phones and during chat to type faster. But it’s not a new concept. The current generation can’t take credit for this invention; it’s not our invention. Our forefathers used it in telegrams. Back when sending telegrams was charged per character, they’d try to squeeze up characters to form another word which could easily be related to the word that it was meant to replace – much the same way we abbreviate text messages today.

But does that hide the message? Not at all. After all, you did understand the first sentence of this chapter, didn’t you? So did the cipher fail to do its job? Well, no, it didn’t; it wasn’t a cipher at all. It was a code.

Codes

History is full of stories of encryption. It doesn’t matter if you’re a fan of Sir Arthur Conan Doyle or Dan Brown or think you were a World War II hero in your past life, the fact that you’re reading this generates a high probability that you already know about ciphers to some extent.

If you refer to day-to-day references, you can easily alter your focus and blur the line between codes and ciphers, seeing them as one and that wouldn’t be all that wrong. Changing the names of your friends to “Vampire”, “Sun” and “Scooter” is a common practice among those who want to hide the numbers of their friends from other unwanted users by confusing them. If you’ve used such a technique, chances are that you would recommend it to close friends as well.

 

But were you actually successful in keeping the identities hidden? Maybe, maybe not! Let’s assume that you actually have those names in your phone’s address book. What are the chances someone else could understand what “Vampire”, “Sun” and “Scooter” stood for? If you’re a fan of the (in)famous ‘Twilight’ series of books, Vampire could be a very special friend. If you have a friend who eats a lot of non-vegetarian food you might use the same name for him. If your friend’s real name is Sunny, ‘Sun’ would obviously be in reference to him. Scooter too, in the same manner can be related to someone with that nickname which stuck with them due to an incident, or maybe it was an accidental pet name you discovered in childhood.

 

The question that remains unanswered is “What’s the probability that someone else could understand it?” If you paid attention, you’d notice that all the names were changed based on the real life experiences. Obviously then, close friends/family would be curious to know which name in your phonebook referred to which friend, and if they were good enough sleuths, they’d figure it out.

 

Now, let’s get into the technicality of the subject and bring up a few terms. While we won’t talk about “plaintext” and “ciphertext” again, it’s noteworthy that when working with codes, the terms are “decoded” (or “plaintext”, again) and “encoded” in that order.

 

Another term when it comes to coding in the context of cryptography is“codebooks”. In the simple case that we just presented, your life history serves as a codebook. To help you better understand, here’s another simple example:

 

Ethan and Fabio want to communicate with each other. But there’s a problem – Ethan knows only English while Fabio knows only French and can’t speak or understand English. Ethan too can’t understand French. In this case, Ethan would require a French->English dictionary so that when Fabio speaks in French, he could look up the words in the dictionary and find their meanings in English. Similarly, Fabio will need an English->French dictionary so that when Ethan speaks in English, he can lookup the words in the dictionary and understand their meanings in French. In this case, both the dictionaries serve as codebooks, using which one can find the “decoded” form of an “encoded” word. Technically, a codebook is a simple mapping of encoded-to-decoded words. If you were to transform all names in your phonebook in a way that no one could easily find out what name stood for which person, you might need a codebook other than your life history.

 

That was one form of encoding. The other form of encoding is called a “one-time” code. This form of code, as the name suggests, is used once only. One of the best examples of such code would be the military’s use of code-names for teams of soldiers. Let’s again consider an example: Assume that there’s a military general with three teams of soldiers. On the first day, he assigns names as: Team 1 => Alpha, Team 2 => Bravo and Team 3 => Charlie. Then he sends them out for patrol. The teams communicate using wireless radio devices whose signals can be intercepted. So when Team 1 has to talk to Team 2, a person from Team 1 says “Alpha to Bravo” to signal that the message is meant for Team 2 from Team 1. Though Team 3 also gets the message, they understand that the message is not for them. The next day, names are changed and Team 1 => Zebra, Team 2 => Delta and Team 3 => Tango. If Team 1 once again wants to convey a message to Team 2, they would say “Zebra to Delta”. If these messages were also being intercepted by enemy soldiers, they wouldn’t be able to determine the total number of teams (notice the first naming was done in alphabetical order, while the

second was random). Such usage of codes is an example of a one-time code. One-time codes are utilized only once (depending on what is defined as “once”) and are often used for messages which are to be “broadcasted”and then “delivered” directly to the destination. These codes are discarded after their use and a new code is formed. Also, all parties who are to use the code must know the code and its meaning before the scheduled (or expected) broadcast of the message.

 

Till now we’ve spoken about condensed text messages, examples of codebooks and one-time codes. You still don’t know what a cipher is though, and where do you draw the line between ciphers and codes?

Codes and Ciphers – the difference

Ciphers are a way to scramble messages so that other people don’t understand them. They differ from codes in multiple ways. Let’s list them:

1. Codes work on larger chunks, usually words. Ciphers work on lower levels. Classical ciphers work with individual letters while modern ciphers work with individual bits.

2. while ciphers are algorithms. Codes involve mapping from one language to another (encoded to decoded) and vice versa. On the other hand, ciphers are mathematical algorithms, often very complex. As such, codes would need a codebook while ciphers won’t.

 

3. Cryptanalysis is usually not possible for wisely encoded messages. Since there’s no mathematical algorithm involved, it might not be possible to find patterns in the code. For example, a code might specify that “all words starting with a vowel are to be discarded first before beginning the actual decoding process.” Such a mechanism makes it nearly impossible to guess the second step involved while still containing a fully valid message (using a codebook where all encoded words begin with a consonant). Cryptanalysis depends on analyzing scrambled messages, but that’s not possible with codes since they may not be broken using techniques of cryptanalysis.

 

4. Codes depend on the person who compiles the code and the codebook itself. The strength of the code depends on the technique he utilizes as well as his intelligence. If the code designer wasn’t intelligent enough, the code’s strength would be weak. On the other hand, ciphers depend on already designed mathematical procedures and their design doesn’t rely, time and again, on humans.

 

Above all those differences is the fact that all ciphers require at least one key, while codes don’t. While some may say that the encoding-decoding process also requires a codebook which is analogous, they’re not similar enough to be compared. The process of coding is based on mapping– you have an encoded word and you have a decoded word and they’re in a one to- one relationship based on a codebook. The process of ciphering is based on calculation– you have mathematical algorithms which can scramble and unscramble messages which would require the correct key. Modern day ciphers which work on bits didn’t just come out of the blue. They were based on previous research, which in turn was based on even older research.

Simple Ciphers

Substitution Cipher

This is one of the simplest ciphers possible. The process is simple and apparent from the name - you substitute things. “But what things?” is a more important question. The most common ‘thing’ to be substituted is a single letter. One of the most common methods substitution ciphers use is called ROT13. Here you rotate the alphabets by 13. So ‘A’ becomes ‘N’, ‘B’ becomes ‘O’ and so on until ‘M’ becomes ‘Z’. Since the English alphabet has only 26 letters, ROT13 makes the mapping easily reversible - i.e. ‘N’ becomes ‘A’, ‘O’ becomes ‘B’ until ‘Z’ becomes ‘M’.

Using the cipher, the word ‘HELLO’ becomes ‘URYYB’ and ‘DIGIT’ becomes ‘QVTVG’. Notice that ‘T’ was substituted with ‘G’ because ROT13 utilizes the same algorithm for encrypting as well as decrypting the message. Thus, it provides almost no security against analysis.

 

One can however utilize other rotation techniques too for substitution for single letters which may include rotation techniques other than ROT13 - for example by rotating only 3 times instead of 13. That would map ‘A’ to ‘D’, ‘B’ to ‘E’ until ‘W’ becomes ‘Z’ and again ‘X’ becomes ‘A’. Another method that can be used is random mapping of letters, something like:

ROT13 mapping

 

In such a scene, the word ‘HELLO’ becomes ‘UZJJC’ and ‘DIGIT’ becomes ‘MALAW’. While this is better than ROT13 where same function could be used for encrypting as well as decrypting the message, it still doesn’t provide enough security against cryptanalysis because simple patterns of usage of words can easily signal the ciphering.

 

If in case it slipped your eye, the ‘random’ substitution cipher we just devised above is not much of a cipher but closer to a code. The reason resides in the fact that the mapping is completely random and for ciphering or deciphering (well, we should already call it encoding and decoding), the table must be present. A person receiving a message ciphered using the map presented in the table would not be able to decipher it without the complete table available with them. Why do we present it if it’s just a code? Well, we do so to show the fine line which separates coding from encryption. We do so because we think it’s fascinating to witness how organizing a random shuffle using a simple number turns a code into a ciphering technique; how it starts to involve calculations instead of maps!

 

What we demonstrated is a simple substitution cipher which involves rotating the alphabets by a number. However this is just one example of how substitution ciphers can work. There are other ways in which substitutions can be done. One of the more complicated ciphers is Vigenère cipher which utilizes a table of substitutions.

Vigenere square diagram

 

This cipher is known as a type of ‘polyalphabetic’ cipher as a single letter in plaintext can take multiple values in ciphertext. It utilizes the rotation technique we just described. As you can see, the table contains 26 rows each for each character in the alphabet where the position of the alphabet determines the number of rotations done for the row. The way to use this cipher follows:

 

1. First get the plaintext. Let it be “ILOVEDIGITMAGAZINE”.

2. Decide a keyword which will be used to encrypt the plaintext. Let’s use ‘TRACK’ as our keyword.

3. Now we begin the encryption process:

a. Take the first letter of the plaintext: ‘I’.

b. Take the first letter of the keyword: ‘T’.

c. Find the corresponding of letter for ‘I’ in the row beginning with ‘T’. It is ‘B’.

Now you have to repeat the process again from step 3.a to 3.c. This time you would take the second letter of the plaintext and find its corresponding alphabet in the row marked by the second letter in the keyword. Hence, the letter to be encrypted is ‘L’ and the row you have to see its replacement in is ‘R’. The result is ‘C’.

 

Now, the keyword is 5 characters long but the plaintext is longer than the keyword. So how do you encrypt the 6th character? Well, you use the first character of the keyword again. To encrypt the 7th character of the plaintext, you use the 2nd character of the keyword and so on. Hence, the letters of the keyword are used in a cyclic manner. Hence if you were to encrypt the complete plaintext using the given keyword, it would become: BCOXOWZGKDFRGCJBEE. So? Is the ciphertext now traceable back to the original plaintext? Well, no. Not at least without the keyword. This brings us to two interesting conclusions:

 

The strength of the keyword would determine how the encrypted text turns out. For example, if we chose a small keyword such as ‘HIM’ or ‘ME’, it would be much more easier to track it back to the original plaintext. Not only the length of the keyword but also the randomness of the characters in the keyword improve the strength of the cipher. For example, if we used a keyword such as ‘DDDDDD’, would it increase the strength of the cipher?

 

No, it would actually weaken the cipher as it would just boil down to ‘D’ being used as a keyword which would directly translate to a rotation of 3 on the alphabet – pretty weak, isn’t it? On the other hand, if we use “CRAZYFOX” as the keyword, it strengthens the cipher because it’s longer and has no repeating characters. To use “XARCZYFO” would be even better because this makes the keyword itself gibberish and more difficult to predict. These principles (longer keyword, random character distribution in keyword and

non-dictionary keywords) still happen to be important factors governing the strength of the encryption.

 

Spaces in the plaintext could make the ciphertext weaker. If you notice, our plaintext didn’t have any white-spaces between them. If they had, the ciphertext would contain spaces too, or some other character to represent white spaces which make the text more guessable than when it does not.

Transposition Cipher

The word says it all – it uses transposition techniques to encrypt the plaintext. The word ‘transposition’ means to change the position. This cipher, however doesn’t work on character level, but on the word level. In this case we do not change the letters themselves but the way we read them. Let’s take our previous example with “I LOVE DIGIT MAGAZINE” as our plaintext (alright, we added spaces). When we write the same sentence backwards, it becomes “ENIZAGAM TIGID EVOL I”. This is certainly more difficult to figure out than the plaintext but breaking it’s not a big deal by any means. If we were to eliminate the spaces, it would be “ENIZAGAMTIGIDEVOLI”, making it a bit more difficult. There are other more popular transposition ciphers which include:

Rail fence cipher: We basically write the plaintext in a way which creates linear patterns in a spiral way. For example: if you have a look at your (US english) keyboard, you would see that the character sequence “QAZSEDCFTGBHUJMKOL” are in a spiral sequence. But when you read them in order the letters appear in rows from top to bottom, it becomes “QETUOASDFGHJKLZCBM”. Now we use the same technique to encrypt “ILOVEDIGITMAGAZINE”. It would look like:

Reading it on rows, it becomes “IEIGNLVDGTAAIEOIMZ”. In this case, the key is ‘3’ as we are using 3 rows to do the transformation. Try to do it with key of ‘4’ and you would find that the ciphertext changes. Route Cipher: In this case, the plaintext is laid out in a grid and then written as a sequence of characters which is derived from a visible sequence over the grid. Let’s assume the same plaintext and lay it in vertical columns on a 6 x 3 grid:

 

Now read it “inward spiral beginning top right corner”. The ciphertext becomes “IGTIVILODIAZENAMGE”. However, if you’re using a grid of 5 x 4, the grid would become like:

The last two cells on the lower rows remain empty. Those can be filled with any nonsense which the interpreter on the other end can easily understand and discard. In this case the width of the grid can serve as the key for the encryption. The number of rows can be calculated using simple mathematics given the padding was done.

Columnar Transposition: This technique is a bit similar to the router cipher. Here too we lay out the plaintext in columns but the way we would convert that grid into ciphertext differs from the route cipher technique.

The process is as follows:

1. We first select a keyword. Let the selected keyword be “DUFFER”.

2. Now, we remove the repeating letters from the keyword. Now, the keyword becomes “DUFER”.

3. Next we re-arrange the letters of the keyword we obtained in the previous step. It becomes: “DEFRU”.

4. We give each letter a number in sequence. D -> 1, E -> 2, F -> 3, R -> 4, U -> 5.

5. Now we take the keyword from step 2 and replace the letters with numbers we got in step 4 (last step). So the keyword now becomes “1 5 3 2 4”.

6. We now lay out a table with 5 columns. The number sequence we obtained in the last step are placed in the top row serving as heads.

7. We then lay out our message in the table linearly. The table would look like: Please do note that ‘X’ in the last row serves as padding to avoid irregularities in the encryption. When decrypting the ciphertext on the other end, it would be easily detectable and thus can be discarded.

 

8. Next we write the text in the column number 1 (from top to bottom) followed by text in column number 2 (again from top to bottom). The ciphertext comes out as: “IDMIVIAXOGGEETZXLIAN”.

 

The keyword “DUFFER” can still be used to decrypt the message. Try doing that yourself if you want to put your grey matter through its paces. With that we round up the simple ciphers and will now try to figure out more modern techniques which provide higher protection than these classical and simple (and also weak) ciphers provide. Nonetheless they are important because they help us understand how we have progressed so far to a place and time where clever cryptanalysis techniques combined with superfast computers fail to get back the plaintext within any practically meaningful time limits.

Modern Ciphers

We’ve spoken about some of the simple ciphers till now which worked by substituting or shuffling the letters from the alphabet. It’s time we now move on to the digital age where machines do the difficult calculations required to encrypt and decrypt messages, while the work of us mortals has been reduced to figuring out the techniques which would produce stronger ciphers. One of the biggest differences between traditional or classical ciphers, and modern ciphers, lies in the smallest unit which they can operate on. Classical methods had a single letter as the smallest unit, while the modern methods have a single bit as the smallest operable unit.

As machines evolved and the need to communicate between machines grew, standardisation of protocols could not have been avoided for too long. ASCII emerged as the most popular text encoding technique. It worked by treating every number as an integer (and that is a type of simple coding technique again, but was meant to be open) and the integers in turn could be represented as a sequence of bits – hence the modern techniques (which are mostly developed for computers) can work with bits.

 

Modern techniques of ciphering and deciphering heavily depend on numbers (all text is actually numbers in ASCII, remember?) and can be classified into two broad categories: symmetric and asymmetric. Symmetric algorithms: A method in which the same key is used for encrypting as well as decrypting the text is called symmetric algorithm.

All the classical ciphers we’ve illustrated thus far would fall under this category because you would always use the same key to encrypt as well as decrypt the message. Some of the better known examples of symmetric algorithms are DES, 3DES (or Triple DES), AES and Blowfish.

Asymmetric algorithms: A method in which the key used for encrypting the message cannot be used to decrypt the message. The key which is to be used for decrypting the message has to be different from the key used to encrypt the message and the relationship between the two keys is complex enough that the second key cannot be derived from the first key. The most popular example of this breed is ‘RSA’. If you ever check the SSL certificates of websites you visit, chances are you’ve read it, unless of course you already know about RSA.

Asymmetric algorithms gain importance over symmetric algorithms because of the fact that symmetric algorithms depend on the same key for encryption as well as for decryption. Since the key is also to be transmitted to the receiver, any person who is able to intercept the encrypted message as well as the key would be able to decrypt the message, thus rendering encryption completely useless. Since with Asymmetric algorithms, the key used for encryption cannot be used for decryption, it’s safe to transmit the public key (the one which is to be used to encrypt the message). Any person who wants to send back a secure message can encrypt the message using your public key and you would be able to decrypt it using the private key!

DES

There is no way we can explain DES in detail within the limits of this book. Hence we would provide you with an introductory explanation of his algorithm. DES is actually an acronym for Data Encryption Standard. DES is a block cipher which works by running an operation for 16 rounds on blocks of 64 bits. On each round, it takes the second half of the plaintext (32 bits) and transforms it into different text using a pre-designed algorithm. It then does an XOR operation of the result with the first half of the plaintext. The result of the XOR operation is processed by the algorithm (denoted as ‘F’ in the diagram) in the next step, while the second half is XORed with the result of the ‘F’ function in the next step. The method to get the plaintext is to reverse the procedure – togo from ‘FP’ towards ‘IP’ and reverse the algorithm.

RSA

The algorithm was designed by Ron Rivest, Adi Shamir and Leonard Adleman and it’s their last names which make up the name of the algorithm. The RSA algorithm is given in following steps:

1. Two prime numbers p and q are taken.

2. A new number n is calculated by multiplying p and q n = pq

3. Another number ϕ(n) is generated by using the formula: ϕ(n) = (p - 1)(q - 1)

4. Another integer e is to be found such that e lies between 1 and ϕ(n). Also, e and ϕ(n) must be coprimes. Mathematically

1 < e <ϕ(n) where gcd(e, ϕ(n) ) = 1 (gcd = Greatest Common Divisor)

5. Another number d is to be found such that de % mod(ϕ(n)) = 1 i.e. When the product of d and e is divided by mod(ϕ(n)), the remainder should be 1.

The numbers ‘e’ and ‘n’ make up the public key, while ‘d’ and

Overall DES Algorithm

‘n’ make up the private key. The calculation is given as follows (‘m’ is the message to be encrypted and ‘c’ is the ciphertext produced after encryption):

For encryption:

c = m^e (mod n)

For decryption:

m = c^d (mod n)

Note: the character ^ refers to the power operator as in 2^2 = 4 and 2^3 = 8

Now, this is applicable for numbers and messages are not always numbers. However, with digital messages it’s different because any and everything is represented in binary form which can be directly translated to a number. The strength of the cipher depends on how difficult it’s to guess the numbers p and q. Once p and q are known, it would not take too much effort to find the rest of the numbers. Since the product of p and q is n and n is a part of public key which is used for encryption and can be well known by third

parties, the only way to know p and q is to find out the factors of n. Interestingly enough, n can have only 4 factors: 1, n, p and q. The first two are applicable for any number and thus one has to find p and q. The strength of RSA, as such, depends on p and q. Hence they both should be very large prime numbers. This makes the factorization of n extremely difficult (since there are no easy ways known to factorize the products of large prime numbers).

 

Algorithms are what protect the secrecy of the message and the strength of the cipher depends on two things: the key used and the algorithm used. If either of them is weak, the message can be intercepted by third parties. While specially designed algorithms were used as way back as ancient Rome, they wouldn’t work today as they would be too simple. In the modern world, it all boils down to the strength of the keys used, and millions if not billions are spent on military grade encryption, for financial institutions, software and more.