ELEMENTARY CRYPTOGRAPHY: SUBSTITUTION CIPHER

ELEMENTARY CRYPTOGRAPHY: SUBSTITUTION CIPHER

Encryption is the process of encoding a message so that its meaning is not obvious; decryption is the reverse process, transforming an encrypted message back into its normal, original form. Alternatively, the terms encode and decode or encipher and decipher are used instead of encrypt and decrypt. That is, we say that we encode, encrypt, or encipher the original message to hide its meaning. Then, we decode, decrypt, or decipher it to reveal the original message. A system for encryption and decryption is called a crypto system.

The original form of a message is known as plaintext, and the encrypted form is called cipher text. For convenience, we denote a plaintext message P as a sequence of individual characters P = <p1, p2, …, pn>. Similarly, cipher text is written as C = <c1, c2, …,cm>.

Plain text	Encryption	Cipher text
Cipher text	Decryption	plain text

 

For instance, the plaintext message "I want cookies" can be denoted as the message string <I, ,w,a,n,t,c,o,o,k,i,e,s>. It can be transformed into cipher text<c1, c2, …,c14>, and the encryption algorithm tells us how the transformation is done.

We use this formal notation to describe the transformations between plaintext and cipher text.

For example:

we write C = E (P) and P = D(C), where C represents the cipher text, E is the encryption rule, P is the plaintext, and D is the decryption rule.

P = D (E(P)).

In other words, we want to be able to convert the message to protect it from an intruder, but we also want to be able to get the original message back so that the receiver can read it properly.

The cryptosystem involves a set of rules for how to encrypt the plaintext and how to decrypt the cipher text. The encryption and decryption rules, called algorithms, often use a device called a key, denoted by K, so that the resulting cipher text depends on the original plaintext message, the algorithm, and the key value. We write this dependence as C =E (K, P). Essentially, E is a set of encryption algorithms, and the key K selects one specific algorithm from the set.

There are many types of encryption. In the next sections we look at two simple forms of encryption: substitutions in which one letter is exchanged for another and transpositions, in which the order of the letters is rearranged.

Cryptanalyst: cryptanalyst is a person who studies encryption and encrypted message and tries to find the hidden meanings (to break an encryption).

Confusion: it is a technique for ensuring that ciphertext has no clue about the original message.

Diffusion: it increases the redundancy of the plaintext by spreading it across rows and columns.

Substitutions Cipher: It basically consists of substituting every plaintext character for a different cipher text character.

It is of two types-

I. Mono alphabetic substitution cipher II. Poly alphabetic substitution cipher

Mono alphabetic substitution cipher:

Relationship between cipher text symbol and plain text symbol is 1:1.

· Additive cipher:

Key value is added to plain text and numeric value of key ranges from 0 – 25.

Example:

Plain text(P)- H E L LO (H=7,E=4,L=11,L=11,O=14) Key (K)=15

Cipher text (C)= 7+15,4+15,11+15,11+15,14+15

= 22,19, 26,26,(29%26)=3

= W T A AD

 

·  Affine cipher:		C= (P+K) mod 26
It is the combination of additive and multiplicative cipher
		P= (C-K) mod 26
Let K1 and K2 are two		keys
	C= [(P x K1) + K2] mod 26
	P= [(C-K2) x K1-1] mod 26

Polyalphabetic substitution cipher

In polyalphabetic cipher each occurrence of a character may have different substitution. The relationship between characters in plain text and cipher text is 1 to many.

· Auto key cipher

· Playfair cipher

· Vigegeire cipher

· Hill cipher

Auto key cipher:

Ø In this cipher, key is stream of subkeys in which subkey is used to encrypt the corresponding character in the plain text.

Ø Here 1^st subkey is predefined and 2^nd subkey is the value of the 1^st character of the plain text 3^rd subkey is the value of the 2^nd plain text and so on.

Example:

A T 0 19

T A C 19 0 2

K

10

Key=12

 

12 0

19 19

0 2

Cipher text(C)= (12,19,38 19,2 12)%26

M T M T C M

 

Playfair cipher

In playfair cipher the secret key is made of 25 characters arranged in 5x5 matrix

Rules:-

Ø If 2 letters in a plaintext are located in the same row of the secret key then the corresponding encrypted character for each letter is next letter to the right.

Ø If 2 letters in a pair are in same column then the corresponding encrypted character is next below in the same column.

Ø If 2 letters are neither in same row or in same column then encrypted character is in its own row but in the same column as the other character.

Example:

L G  D  B A

 

Q M H E C

K= U R  N  I/J F

X V S  O K

Z Y  W  T P

Plain text= HELLO

It is then made as pair.

H E L X L O

H E L Q L B

 

E C X Z O X

 

Vigener cipher:

The key stream is the repetition of the initial secret key stream of length m. (1<=m<=26)

Example:

Plaintext- A B C D E F G H

Ks= 0, 5, 8

	A  B  C  D  E  F							G  H		(B=1 =>1+5=6=>G)
0			5	8	0	5	8	0	5
	0	6		10	3	9	13	6	12
	A  G  K D					J	N  G M			<= ciphertext
Transposition cipher:
A  transposition					cipher is			a	method  of  encryption by which  the positions held  by units

of plaintext (which are commonly characters or groups of characters) are shifted according to a regular system, so that the ciphertext constitutes a permutation of the plaintext. That is, the order of the units is changed.

The goal of substitution is confusion; the transposition method is an attempt to make it difficult i.e diffusion.

1. Keyless transposition cipher

There are two methods for permutation of characters

Ø Text is written into a table column by column and transmitted row by row Example: plaintext- meet me at the park

m e m a t e a k e t e t h p r

ciphertext- memateaketethpr

Ø Text is written into the table row by row and then transmitted column by column.

Example: m e e t m e a t t h e p a r k

ciphertext- mmtaeehreaekttp

2. Keyed transposition cipher

Plaintext is divided into groups and permutes the character in each group. Example: plaintext- “enemy attack at night”

keys:

encryption	3 1 4 5 2	decryption
	1 2 3 4 5
				appended to make a group of 5 characters
e n e m y   a t t a c	k a t n i  g h t y z		(Group of 5 characters)
encryption: e e m y n  t a a c t  t k n i k		t g y z h
decryption: e n e m y a t t a c k a t n i g h t y			z

3. Combining the two approaches:

Encryption and decryption is done in three steps.

· Text is written into a table row by row.

· Permutation is done by reordering the column.

· New table is read column by column