Performance analysis of Substitution Cipher Based Cryptographic Algorithm Mihir Sanghavi
11MCA48, Student, MCA Programme, Institute of Technology, Nirma University, Ahmadabad

Email: 11MCA48@nirmauni.ac.in

Abstract
Cryptography is the study of Encryption techniques related to aspects of information security, such as confidentially or privacy, data integrity and entity authentication. Today’s world, for secure data transmission via Internet or any public network, there is no alternative to cryptography. The role of Cryptography is most important in the field of network security. The main goal of cryptography is Confidentiality, Integrity, Authentication, Non repudiation. Cryptography is widely used by governmental and intelligence agencies around the world to safe transmission of any format of messages online or offline. In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with cipher text, according to a regular system; the "units" may be single letters, pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing an inverse substitution. Caesar cipher is an example of substitution cipher method. In this paper substitution cipher based cryptography algorithms are compared and performance is evaluated.

Keywords
Cryptography, substitution cipher, cryptanalysis, Caesar cipher, monoalphabetic cipher and Polyalphabetic cipher.

Introduction
A substitution cipher is a method of encryption by which units of plaintext are replaced with cipher text, according to a regular system; the "units" may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing an inverse substitution. Substitution ciphers can be compared with transposition ciphers. In a transposition cipher, the units of the plaintext are rearranged in a different and usually quite complex order, but the units themselves are left unchanged. By contrast, in a substitution cipher, the units of the plaintext are retained in the same sequence in the cipher text, but the units themselves are altered.

There are a number of different types of substitution cipher. If the cipher operates on single letters, it is termed a simple substitution cipher; a cipher that operates on larger groups of letters is termed polygraphic. A monoalphabetic cipher uses fixed substitution over the entire message, whereas a Polyalphabetic cipher uses a number of substitutions at different positions in the message, where a unit from the plaintext is mapped to one of several possibilities in the cipher text and vice versa.

Key findings from literature survey: Monoalphabetic Cipher
If the substitution cipher operates on single letters, it is termed as monoalphabetic cipher. There are various types of monoalphabetic cipher i.e. Caesar cipher, pigpen cipher, ADFGVX cipher. In monoalphabetic cipher shifting is done by value K. If we think in terms of the numbers 0 through 25 representing the letters A through Z, the enciphering process may be viewed mathematically as C = M + K (mod 26), where C is the cipher text letter, M is the plaintext letter, and K is the key. The “mod 26” part (short for “modulo 26”) simply means that if the sum M + K is greater than or equal to 26, we subtract 26 from this number to get our result. The key space (defined as the set of possible choices for K) has 25 elements, since the identity K = 0 leaves the message unchanged, as does K = 26. Only values strictly between 0 and 26 offer distinct decipherments. A longer key phrase may be used to determine the order of the substitutions. If a letter is repeated, simply ignore it when it reappears, 7 as you write the cipher alphabet out. Key phrases may be chosen that contain all of the letters of the alphabet. i.e. 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 plaintext THEQUICKBROWNFXJMPSVALZYDG Richard Lederer provides several shorter phrases using all 26 letters:  Pack my box with five dozen liquor jugs (32 letters)  Jackdaws love my big sphinx of quartz. (31 letters)  How quickly daft jumping zebras vex. (30 letters)  Quick wafting zephyrs vex bold Jim. (29 letters)  Waltz, nymph, for quick jigs vex Bud. (28 letters)  Bawds jog, flick quartz, vex nymphs. (27 letters)  Mr. Jock, TV quiz Ph.D., bags few lynx. (26 letters – a minimum) A few devices have been invented to ease translation from plaintext to cipher text and back again.

The manner in which this disk can be used to encrypt and decrypt should be immediately clear and require no explanation. The inner alphabet is on a separate disk that may be rotated with respect to the larger disk in order to form other substitutions.

Caesar Cipher
The earliest known use of a substitution cipher, and the simplest, was by Julius Caesar. The Caesar cipher involves replacing each letter of the alphabet with the letter standing three places further down the alphabet. The Caesar cipher is named after Julius Caesar, who, according to Suetonius, used it with a shift of three to protect messages of military significance. While Caesar's was the first recorded use of this scheme, other substitution ciphers are known to have been used earlier. For example: Plain: meet me after the toga party Cipher: PHHW PH DIWHU WKH WRJD SDUWB

We can define the transformation by listing all possibilities, as follow:

Plain: 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 Cipher: D 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 Let us assign a numeric equivalent to each letter: Then the algorithm can be expressed as follows. For each plaintext letter p, substitute the cipher letter C: C = E (p) = (P+3) mod (26) A shift may be of any amount, so that the general Caesar algorithm is

C = E (p) = (p+k) mod (26) Where, k takes on a value in the range 1 to 25. The decryption algorithm is simply P = D(C) = (C-k) mod (26)

Cryptanalysis
    Only have 25 possible ciphers. A maps to B up to Z. Given cipher text, just try all shifts of letters. Do need to recognize when we have plain text.

Pigpen cipher
It is variation on letter substitution; here alphabets are arranged as follows:

X Y Z

W

W=

X=

Y=

Z=

Alphabets will be represented by this symbols but it is a weak cipher.

ADFGVX cipher:
This is a variation on substitution cipher and is a strong cipher.

A A D F G V X 8 L 7 J X 9

D P T K U S E

F 3 4 B 6 V Y

G D O C W I 0

V 1 A 5 G R F

X N H Z M 2 Q

Remove spaces and punctuation marks from message For each letter or number substitute the letter pair from the column and row heading Next, use a transposition operation on the pair of letters using a key word (which the receiver knows) Rearrange the columns of the new arrangement in alphabetical order Finally, arrange the letters from consecutive columns E.g., Message = SEE ME IN MALL VD XD XD GX XD VG AX GX DV DA DA Keyword: INFOSEC ARRANGE LEVEL 1 CIPHER IN A GRID. AND THEN ARRANGE IT IN ALPHABETICAL ORDER. FRESH GRID:

I V X G

N D X X

F X D D

O D V V

S X G D

E D A A

C G X V

ORDERED GRID: C G X V E D A A F X D D I V X G N D X X O D V V S X G D

Cipher text is: GXVDAAXDDVXGDXXDVVXGD Recipient reverses the process using the same keyword and gets the plaintext Reason for this cipher using the name ADFGVX is that in Morse code these characters all have dissimilar patterns of dots and dashes.

Cryptanalysis:
The ADFGVX cipher is not hard to spot, but this is a very difficult cipher to break. Let us consider the problems that are faced when crypt analyzing the ADFGVX ciphers. First, consider a message that was encrypted once with a Caesar cipher and then again with columnar transposition. Frequency analysis will show a shifted alphabet, but, after shifting the cipher text letters back by the key that was determined from frequency analysis, the message will still not be plain text. Frequency analysis would indicate plaintext, but the message would not be plaintext. That indicates a transposition cipher, and the remaining cipher text would be attacked as a transposition cipher. Similarly, consider a message that was encrypted once with a simple substitution cipher with a randomly generated permutation and then again with a columnar transposition. Frequency analysis will show a simple substitution cipher. The cryptanalyst might begin by assuming that the most frequent cipher text letter corresponds to plaintext e, etc., but the transposition would complicate this analysis. The ADFGVX cipher is even worse The ADFGVX cipher is even worse. If only the substitution portion of the cipher were done, it would not be difficult to break. Even if the cryptanalyst knew nothing about the ADFGVX cipher, the fact that only six letters appear in the cipher text and every cipher text message has even length would suggest that a checkerboard was used for substitution. Suspecting this, the message could be broken into

digraphs and the frequency of the digraphs could be analyzed to determine the corresponding plaintext letters as is done for any simple substitution cipher. The devil is the transposition. Every plaintext letter is substituted by a digraph. When placed into the rectangular array for columnar transposition, the first letter of the digraph will lie in one column and the second letter of the digraph will lie in another column. After transposition, these letters will be separated – the plaintext frequencies will be “fractionated.” This is the strength of the ADFGVX cipher and similar ciphers. Single-letter characteristics are scattered.

Polyalphabetic Cipher: • • • • In monoalphabetic cipher the problem was that each character was substituted by a single character. Cryptanalysts are helped by the fact that they have to see what character would correspond in plaintext for a given cipher text character Polyalphabetic cipher’s goal is to make this process difficult

In Polyalphabetic cipher, each plaintext character may be replaced by more than one character • Since there are only 26 alphabets this process will require using a different representation than the alphabets • Alphabets ‘A’ through ‘Z’ are replaced by 00, 01, 02, .., 25 • We need two digits in this representation since we need to know how to reverse the process at the decryption side The most common methods used are Vigenère cipher, Beale cipher, Vernam cipher.

Vigenère cipher
• • • Vigenère cipher starts with a 26 x 26 matrix of alphabets in sequence. First row starts with ‘A’, second row starts with ‘B’, etc. Like the ADFGVX cipher, this cipher also requires a keyword that the sender and receiver know ahead of time Each character of the message is combined with the characters of the keyword to find the cipher text character

ABCDEFGHIJKLMNOPQRSTUVWXYZ AABCDEFGHIJKLMNOPQRSTUVWXYZ B B A B C D E F G H I J K L M N O P Q R S T U V W X YA CCDEFGHIJKLMNOPQRSTUVWXYZAB DDEFGHIJKLMNOPQRSTUVWXYZABC EEFGHIJKLMNOPQRSTUVWXYZABCD FFGHIJKLMNOPQRSTUVWXYZABCDE GGHIJKLMNOPQRSTUVWXYZABCDEF HHIJKLMNOPQRSTUVWXYZABCDEFG IIJKLMNOPQRSTUVWXYZABCDEFGH JJKLMNOPQRSTUVWXYZABCDEFGHI KKLMNOPQRSTUVWXYZABCDEFGHIJ LLMNOPQRSTUVWXYZABCDEFGHIJK MMNOPQRSTUVWXYZABCDEFGHIJKL NNOPQRSTUVWXYZABCDEFGIJKLM OOPQRSTUVWXYZABCDEFGIJKLMN PPQRSTUVWXYZABCDEFGIJKLMNO QQRSTUVWXYZABCDEFGIJKLMNOP RRSTUVWXYZABCDEFGIJKLMNOPQ SSTUVWXYZABCDEFGIJKLMNOPQR TTUVWXYZABCDEFGIJKLMNOPQRS UUVWXYZABCDEFGIJKLMNOPQRST VVWXYZABCDEFGIJKLMNOPQRSTU WWXYZABCDEFGIJKLMNOPQRSTUV XXYZABCDEFGIJKLMNOPQRSTUVW YYZABCDEFGIJKLMNOPQRSTUVWX ZZABCDEFGIJKLMNOPQRSTUVWXY

For example: Message = SEE ME IN MALL Take keyword as INFOSEC Vigenère cipher works as follows:

SEEMEI NMALL INF OSEC I NFO -------------------------------ARJAWMPUNQZ To decrypt, the receiver places the keyword characters below each cipher text character. Using the table, choose the row corresponding to the keyword character and look for the cipher text character in that row, plaintext character is then at the top of that column. Decryption of cipher text:

ARJAWMPUNQZ INF OSEC I NFO --------------------------------

SEEMEI NMALL Best feature is that same plaintext character is substituted by different cipher text characters (i.e., Polyalphabetic) Cryptanalysis: The Vigenère cipher might first have been broken by the English mathematician Charles Babbage (1792 – 1871); Kahn quotes Babbage as saying “an indistinct glimpse of defeating it presented itself vaguely to my imagination.” But, if Babbage had a solution, he never published it. Babbage apparently had the tendency to never be satisfied with a work and to continue to refine things; so, he might never have been satisfied enough with his solution to publish it. Friedrich Kasiski (1805 – 1881) is credited with breaking the Vigenère cipher in 1863. From the Sixteenth Century until the Nineteenth Century the cipher was generally considered to be secure. We will use Kasiski’s technique to determine the length of the keyword. In the Twentieth Century, William Frederick Friedman (1891 – 1969), the dean of American cryptologists, developed a statistical method to estimate the length of the keyword.

Beale cipher:
It is also known as book cipher. Keyword is taken as the first few words of a book that is agreed upon by sender and receiver. Everything else works like the Vigenère cipher.

Vernam cipher:
U.S. Army Major Joseph Mauborgne and AT&T’s Gilbert Vernam developed a cipher in 1917 Uses a onetime arrangement of a key string that is as long as the plaintext Plaintexts are assumed to be short Also known as One-Time Pad cipher Key is used only once but characters in key may not be distinct. E.g., Plaintext: HELLO Key: KTBXZ Cipher text: RXMIN (using addition mod 26) Key: KTBXZ Received: RXMIN Plaintext: HELLO (using subtraction mod 26) Cryptanalysis: If a truly random key as long as the message is Used, the cipher will be secure - One-Time pad • E.g., a random sequence of 0’s and 1’s XORed toPlaintext, no repetition of keys

• Unbreakable since cipher text bears no statistical relationship to the plaintext • For any plaintext, it needs a random key of the same length Hard to generate large amount of keys. • Have problem of safe distribution of key

Conclusion
Based on the network requirements and the other criteria the substitution cipher cryptography algorithms are used .The cryptanalysis of these algorithms are used to compare the various types. And based on it the new algorithms are invented by taking care of the disadvantages of their predecessors.

References
1. http://en.wikipedia.org/wiki/Monoalphabetic_cipher 2. http://en.wikipedia.org/wiki/Monoalphabetic_cipher#Polygraphic_substitution 3. http://en.wikipedia.org/wiki/Cipher 4. http://www.nku.edu/~christensen/section%2012%20vigenere%20cryptanalysis.pdf 5. http://math.boisestate.edu/~liljanab/MATH509Spring2012/CryptanalysisSubstitutionCiphe r.pdf 6. http://www.rimtengg.com/iscet/proceedings/pdfs/misc/20.pdf 7. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.89