{"id":33,"date":"2018-07-21T09:08:18","date_gmt":"2018-07-21T09:08:18","guid":{"rendered":"http:\/\/csp11.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=33"},"modified":"2018-12-27T09:48:40","modified_gmt":"2018-12-27T09:48:40","slug":"substitution-cipherand-cryptanalysis","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp11\/chapter\/substitution-cipherand-cryptanalysis\/","title":{"rendered":"Substitution Cipherand Cryptanalysis"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n\u00d8\u00a0 To know the substitution cipher in classical cryptography\r\n\r\n\u00d8\u00a0\u00a0 To learn about the mono alphabetic substitution cipher\r\n\r\n\u00d8\u00a0\u00a0 To learn about the poly alphabetic substitution cipher\r\n\r\n\u00d8\u00a0\u00a0 Cryptanalysis of substitution cipher\r\n\r\n \r\n\r\n3.1 Introduction<\/strong>\r\n\r\n \r\n

Humans could encode their own documents, but computers do it faster and more efficiently. To do this, the computer at each end uses a document called an \"SSL Certificate\" containing character strings that are the keys to their secret \"codes.<\/p>\r\n \r\n

In cryptography, <\/a>a transposition cipher is a method of encryption by which the positions held by units of plaintext <\/a>are shifted according to a regular system, so that the ciphertext <\/a>constitutes a permutation <\/a>of the plaintext. That is, the order of the units is changed. Mathematically a bijective <\/a>function is used on the characters' positions to encrypt and an inverse function <\/a>to decrypt. So let\u2019s know about the terminologies and concepts behind the cryptography which acts as a base behind our day today online transactions.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n3.2 Substitution Cipher<\/strong>\r\n\r\n \r\n

Substitution cipher is a method of encoding <\/a>in which units of plaintext are replaced with ciphertext, <\/a>according to a fixed system. The \"units\" may be single letters (the most common), pairs of letters, triplets of letters, and mixtures of the above. The receiver deciphers the text by performing the inverse substitution.In substitution ciphers, we replace the plaintext letters with other letters<\/p>\r\n \r\n\r\n\u2013\u00a0 The resulting text is the ciphertext\r\n\r\n\u2013\u00a0 The substitution rule is the key\r\n\r\n \r\n\r\n \r\n

It Corresponds to Shannon\u2019s principle of confusion. The letters of plaintext are replaced by other letters or by numbers or symbols. Plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns.The simple substitution cipher is a cipher that has been in use for many hundreds of years. It basically consists of substituting every plaintext character for a different ciphertext character. It differs from the Caesar cipher <\/a>in that the cipher alphabet is not simply the alphabet shifted, it is completely jumbled.The simple substitution cipher offers very little communication security, and it will be shown that it can be easily broken even by hand, especially as the messages become longer (more than several hundred ciphertext characters).<\/p>\r\n \r\n\r\n \r\n\r\nExample\r\n\r\n \r\n

Here is a quick example of the encryption and decryption steps involved with the simple substitution cipher. The text we will encrypt is 'defend the east wall of the castle'.<\/p>\r\n \r\n

Keys for the simple substitution cipher usually consist of 26 letters (compared to the caeser cipher's single number). An example key is:<\/p>\r\n \r\n

plain alphabet : abcdefghijklmnopqrstuvwxyz<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0 cipher alphabet: phqgiumeaylnofdxjkrcvstzwb<\/span>\r\n\r\n \r\n\r\nAn example encryption using the above key:\r\n\r\n \r\n\r\nplaintext : defend the east wall of the castle<\/span>\r\n\r\n \r\n\r\nciphertext: giuifg cei iprc tpnn du cei qprcni<\/span>\r\n\r\n \r\n

It is easy to see how each character in the plaintext is replaced with the corresponding letter in the cipher alphabet. Decryption is just as easy, by going from the cipher alphabet back to the plain alphabet. When generating keys it is popular to use a key word, e.g. 'zebra' to generate it, since it is much easier to remember a key word compared to a random jumble of 26 characters. Using the keyword 'zebra', the key would become:<\/p>\r\n \r\n\r\ncipher alphabet: zebracdfghijklmnopqstuvwxy<\/span>\r\n\r\n \r\n\r\n \r\n

This key is then used identically to the example above. If your key word has repeated characters e.g. 'mammoth', be careful not to include the repeated characters in the cipher alphabet<\/p>\r\n \r\n\r\n3.3 Caesar Cipher<\/strong>\r\n\r\n \r\n\r\n \r\n

The Caesar cipher is one of the earliest known and simplest ciphers. It is a type of substitution cipher in which each letter in the plaintext is 'shifted' a certain number of places down the alphabet. For example, with a shift of 1, A would be replaced by B, B would become C, and so on. The method is named after Julius Caesar, who apparently used it to communicate with his generals. It is used until 16th century and it replaces each letter by 3rd letter.<\/p>\r\n \r\n\r\nexample:\r\n\r\n \r\n\r\nmeet me after the toga party\r\n\r\nPHHW PH DIWHU WKH WRJD SDUWB\r\n\r\ncan define transformation as:\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0 a b c d e f g h i j k l m n o p q r s t u v w x y z\r\n\r\nD E F G H I J K L M N O P Q R S T U V W X Y Z A B C\r\n\r\n \r\n\r\nmathematically give each letter a number\r\n\r\n \r\n\r\na b c d e f g h i j k l m n o p q r s t u\u00a0 v w x y z\r\n\r\n0\u00a0\u00a0\u00a0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25\r\n\r\n \r\n\r\nIt can be easily depicted using the following\u00a0\u00a0 Caesar cipher :\r\n\r\n \r\n\r\nc = E(p) = (p + k) mod (26)\r\n\r\np = D(c) = (c \u2013 k) mod (26)\r\n\r\n \r\n\r\n \r\n\r\n3.3.1 Cryptanalysis Of Caesar Cipher<\/strong>\r\n\r\n\u00d8\u00a0 only have 26 possible ciphers\r\n\r\n \r\n

\u00a7\u00a0\u00a0\u00a0 A maps to A,B,..Z<\/p>\r\n \r\n\r\n\u00d8\u00a0\u00a0 could simply try each in turn a brute force search\r\n\r\n\u00d8\u00a0\u00a0 given ciphertext, just try all shifts of letters\r\n\r\n\u00d8\u00a0\u00a0 do need to recognize when have plaintext\r\n\r\n\u00d8\u00a0\u00a0 eg. break ciphertext \"GCUA VQ DTGCM\"\r\n\r\n \r\n

The Caesar cipher is probably the easiest of all ciphers to break. Since the shift has to be a number between 1 and 25, (0 or 26 would result in an unchanged plaintext) we can simply try each possibility and see which one results in a piece of readable text. If you happen to know what a piece of the ciphertext is, or you can guess a piece, then this will allow you to immediately find the key.<\/p>\r\n \r\n\r\n \r\n\r\n3.4 Simple Substitution Cipher<\/strong>\r\n\r\n \r\n\r\n\u00d8\u00a0 rather than just shifting the alphabet\r\n\r\n\u00d8\u00a0\u00a0 could shuffle (jumble) the letters arbitrarily\r\n\r\n\u00d8\u00a0\u00a0 each plaintext letter maps to a different random ciphertext letter\r\n\r\n\u00d8\u00a0\u00a0 hence key is 26 letters long\r\n\r\n<\/div>\r\n

\r\n

A monoalphabetic substitution cipher, also known as a simple substitution cipher, relies on a fixed replacement structure. That is, the substitution is fixed for each letter of the alphabet. Thus, if \"a\" is encrypted to \"R\", then every time we see the letter \"a\" in the plaintext, we replace it with the letter \"R\" in the ciphertext.<\/p>\r\n \r\n

A simple example is where each letter is encrypted as the next letter in the alphabet: \"a simple message\" becomes \"B TJNQMF NFTTBHF\". In general, when performing a simple substitution manually, it is easiest to generate the ciphertext alphabet first, and encrypt by comparing this to the plaintext alphabet. The table below shows how one might choose to, and we will, lay them out for this example.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

The ciphertext alphabet for the cipher where you replace each letter by the next letter in the alphabet. There are many different monoalphabetic substitution ciphers, in fact infinitely many, as each letter can be encrypted to any symbol, not just another letter.<\/p>\r\n \r\n

The history of simple substitution ciphers can be traced back to the very earliest civilisations, and for a long time they were more than adequate for the purposes for which they were needed. By today's standards they are very weak, and incredibly easy to break, but they were a very important step in developing.<\/p>\r\n \r\n\r\n \r\n\r\n3.4.1 Simple Substitution Cipher Security<\/strong>\r\n\r\n \r\n\r\nMonoalphabetic ciphers are not very secure and can be easily broken by statistical means\r\n\r\n\u00d8 now have a total of 26! = 4 x 1026 keys\u00a0\u00a0 HY6JIN9YI66inj\r\n\r\n\u00d8\u00a0\u00a0 with so many keys, might think is secure\r\n\r\n\u00d8\u00a0\u00a0 but would be !!!WRONG!!!\r\n\r\n\u00d8\u00a0\u00a0 problem is language characteristics\r\n\r\n<\/div>\r\n \r\n

\r\n\r\n3.5 Cryptanalysis<\/strong>\r\n\r\n\u00d8\u00a0 Statistical analysis\r\n

o\u00a0\u00a0 Statistics might reveal info about key<\/p>\r\n\u00d8\u00a0 Ciphertext should appear random\r\n\r\n\u00d8\u00a0\u00a0 But randomness is not easy\r\n

o\u00a0\u00a0 Difficult to define random (entropy)<\/p>\r\n\u00d8\u00a0 Human languages are redundant\r\n\r\n\u00d8\u00a0 A strong familiarity with a language includes a grasp of the language's redundancy.\r\n\r\n \r\n

Redundancy means that every language contains more characters or words than are actually needed to convey information. The rules of the English language create redundancy. For example, no English word will begin with the letters \"ng.\" English also relies heavily on a small number of words. Words like \"the,\" \"of,\" \"and,\" \"to,\" \"a,\" \"in,\" \"that,\" \"it,\" \"is,\" and \"I\" account for more than one quarter of the text of an average message written in English.<\/p>\r\n \r\n

Knowing the redundant qualities of a language makes a cryptanalyst's task much easier. No matter how convoluted the cipher is, it follows some language's rules in order for the recipient to understand the message. Cryptanalysts look for patterns within ciphers to find common words and letter pairings.<\/p>\r\n \r\n

One basic technique in cryptanalysis is frequency analysis. Every language uses certain letters more often than others. In English, the letter \"e\" is the most common letterin English E is by far the most common letter<\/p>\r\n\r\n