0
30kviews
Substitution Cipher in Cryptography
1
485views

Monoalphabetic Ciphers

1. Caesar Cipher/Shift Cipher/Additive:

Assume that the plaintext consists of letters A to Z and that the ciphertext also consists of letters A to Z. To apply the mathematical operations on the plaintext and the ciphertext, we assign numerical values to each letter as shown in the figure below.

For eg.

If Plaintext = CNS IS MY FAV SUBJECT and Key = 3

then, by applying the numerical equivalent of each letter algorithm

Ciphertext = FQV LV PB IDY VXEMFS

Algorithm for the numerical equivalent of each letter

A=0

B=1

C=2

.

.

.

Z=25

So,

Encryption algorithm for the above example is

C = E(K,P)=(P+K) mod 26

where K = 1 to 25

and

Decryption algorithm for the above example is

P=D(K,C)=(C-K) mod 26

where, P = Plaintext

C= Ciphertext

K= Key

Consider another example where

Ciphertext=PHHW PH is given and plaintext needs to be found using the decryption algorithm but no key is given.

Key not given we have to calculate it & get the plaintext for which we need to check it with all 26 keys available set of keys with us ( A= 0 to Z= 25) till a meaningful message is obtained.

Decryption:

With Key 0

Plaintext = PHHW PH , which is not meaningful so take next key

for Key 1, Plaintext= nffu nf , which is again not meaningful so take next key

for Key 2, Plaintext = meet me , which makes some meaning

So Plaintext = MEET ME with Key = 2

Example:

To encrypt the message " NOTSECURE" with Key = 07

So, Ciphertext is "UVAZLJBYL"

2. Multiplicative Cipher: In multiplicative cipher, the encryption algorithm specifies the multiplication of the plaintext with the key and the decryption algorithm specifies the division of the ciphertext by the key as shown in the figure below.

Multiplicative cipher has a key set ( Key Domain) of 12 members: 1,3,5,7,9,11,15,17,19,21,23,25.

Encryption algorithm : C = E(K,P)=(P*K) mod 26

where Key Domain = 1,3,5,7,9,11,15,17,19,21,23,25.

and

Decryption algorithm : P=D(K,C)=(C*$K^{-1}$) mod 26

Example:

encrypt the message "HELLO" using multiplicative cipher with key = 7

So, the ciphertext is " XCZZU"

3. Affine Cipher: Affine cipher is the combination of additive and multiplicative ciphers with a pair of keys K1, K2. The first key is used with the multiplicative cipher and the second key is used with the additive cipher. the figure below shows the affine cipher algorithm.

Example:

Encrypt the message "HELLO" using Affine Cipher with key pair (7,2)

So, the ciphertext is " ZEBBW"

Polyalphabetic Ciphers

1. Playfair: In playfair cipher the secret key is made of 26 alphabet letters which are arranged in 5x5 matrix(letters I and J are considered the same while encrypting).Different arrangements of the letters in the matrix can create many different keys.

Example:

The secret key is shown in the following arrangement. In this arrangement, the letters in the matrix are dropped diagonally starting from the top right-hand corner.

$$\begin{bmatrix} L & G & D & B & A \\ Q & M & H & E & C \\ U & R & N & I/J & F \\ X & V & S & O & K \\ Z & Y & W & T & P \end{bmatrix}$$

Before encryption following basic rules are to be followed:

1. Group the letters of the plaintext in two-character pairs.

2. If 2 letters in a pair are the same, a bogus character letter is added to separate them.

3. If after adding a bogus character, the number of characters in plaintext is odd, one extra character is added at the end to make the number of characters even.

Three rules for encryption:

1) If the 2 letters in a pair are located in the same row of the secret key, the corresponding encrypted character for each letter is the next letter to the right in the same row(if the plaintext letter is the last character in the row wrap it with the letter beginning of the row).

2) If the 2 letters in a pair are located in the same column of the secret key, the corresponding encrypted character for each letter is the letter beneath/below it in the same column( if the plaintext letter is the last character in the column wrap it with the letter beginning of the column).

3) If the 2 letters in a pair are not in the same row & the column of secret key, corresponding encrypted character for each letter is letter that is in its own row but in the same column as the other letter.

Eg. Plaintext "hello"

Step 1: group letter in pair of two, he ll o, applying Basic Rules, we get pair as he lx lo

Step 2: he in the same row of the secret key so by Rule 1 of encryption he becomes ec

Step 3: lx in the same column so by Rule 2 of encryption, lx becomes qz

Step 4: lo not in the same row and not in the same column of the secret key so by Rule 3 of encryption lo becomes bx

Plaintext = "hello"

After making pairs: he ll o

After applying basic rules: he lx lo

After applying encryption rules: ec qz bx

So Ciphertext = "ecqzbx"

2. Vignere Cipher: It uses a strategy to create the key stream. The key stream is a repetition of an initial key stream of length say m, where m must be greater than 1 and less than or equal to 26.

Eg. She is listening and Keyword (PASCAL) .Numeric value for PASCAL is (15,0,18,2,0,11)

Step 1: group the letters of plaintext in 6-character pairs(as the length of keyword is 6)

Step 2: Calculate the numeric values for these group of plaintext

Step 3: add keystream to the plaintext groups

Step 4: after step 3 we get ciphertext values for corresponding groups of plaintext

Step 5: Get the alphabet letters corresponding to the ciphertext values using mod 26

$\phantom{Example: She is listening, Key}$

s h e i s l i s t e n i n g
P's value 18 07 04 08 18 11 08 18 19 04 13 08 13 06
Key stream 15 00 18 2 0 11 15 0 18 2 0 11 15 00
C's value 7 7 22 10 18 22 23 18 11 6 13 19 02 06
Cipher H H W K S W X S L G N T C G

3. Hill Cipher:

Hill cipher.

Encryption: To encrypt a message using the Hill cipher.

• We must first turn our keyword into a key matrix ( a $\ 2 \times 2$ matrix for working with digraphs, a $3 \times 3$ matrix for working with trigraphs, etc)

• We also turn the plain text into digraphs or trigraphs and each of these into a column vector.

• We then perform matrix multiplication modulo the length of the alphabet i.e. 26 on each vector.

• These vectors are then converted back into letters to produce the ciphertext.

Example:

1] plain-text : ‘ACT’ (n = 3)

Key : ‘G Y B N Q K U R P’

SOLUTION:

Step 1: $n \times n$ key matrix.

Step 2: Plain-text message ‘ACT’ is written in vector.

$\begin{bmatrix}0 \\ 2 \\ 19 \\\end{bmatrix}$

Step 3: Encrypted vector is given as

$C = [K] [P] mod \ 26$

\begin{aligned} &= \begin{bmatrix}6 \times 0 + 24 \times 2 + 1 \times 19 \\ 13 \times 0 + 16 \times 2 + 10 \times 2 \\ 20 \times 0 + 17 \times 2 + 15\times 19 \\\end{bmatrix} mod \ 26 \\ &= \begin{bmatrix}67 \\ 222 \\ 319 \\\end{bmatrix} mod \ 26 \\ &= \begin{bmatrix}15 \\ 14 \\ 07 \\\end{bmatrix} \\ i.e, C &= \begin{bmatrix}P \\ O \\ H \\\end{bmatrix} \end{aligned}

Example 2.

Plain text = “short example”

Keyword = “hill” and a $2 \times 2$ matrix.

Steps:

To turn the keyword into a matrix, if the keyword was longer than the 4 letters needed, we would only take the first 4 letters and if it was shorter, we would fill it up with the alphabet in order.

• The keyword written as a matrix as

$= \begin{bmatrix}H & I \\ L & L \\\end{bmatrix}$

• With the keyword in a matrix, we need to convert this into a key matrix. We do this by converting each letter into a number by its position in the alphabet (starting at 0), So, A = 0, B = 1, C = 2, D = 3, etc.

$= \begin{bmatrix}7 & 8 \\ 11 & 11 \\\end{bmatrix}$

The key matrix (each letter of the keyword is converted to number)

• Now, we split the plain text into digraphs and write these as column vectors, that is the first column vector we write the first plain text letter at the top and the second letter at the bottom. Then we move to the next column vector, where the third plain text letter goes at the top and the fourth at the bottom. This continues for the whole plain-text.

$\begin{bmatrix}s \\ h \\\end{bmatrix} \begin{bmatrix}o \\ r \\\end{bmatrix} \begin{bmatrix} t \\ e \\\end{bmatrix} \begin{bmatrix}x \\ a \\\end{bmatrix} \begin{bmatrix}m \\ p \\\end{bmatrix} \begin{bmatrix}l \\ e \\\end{bmatrix}$

The plain text “short example” split into the column vectors.

• Now, we convert the plain text column vectors in the same way that we converted the keyword into the key matrix. Each letter is replaced by its appropriate number.

$\begin{bmatrix}18 \\ 7 \\\end{bmatrix} \begin{bmatrix}14 \\ 17 \\\end{bmatrix} \begin{bmatrix} 19 \\ 4 \\\end{bmatrix} \begin{bmatrix}23 \\ 0 \\\end{bmatrix} \begin{bmatrix}12 \\ 15 \\\end{bmatrix} \begin{bmatrix}11 \\ 04 \\\end{bmatrix}$

The plain text converted into number column vectors.

• Next step is to perform matrix multiplication. We multiply the key matrix by each column vector in turn. We write the key matrix first, followed by the column vector.

\begin{aligned} \begin{bmatrix}7 & 8 \\ 11 & 11 \\\end{bmatrix} \begin{bmatrix}18 \\ 7 \\\end{bmatrix} \ mod \ 26 & = \begin{bmatrix}7 \times 18 + 8 \times 7 \\ 11 \times 18 + 11 \times 7 \\\end{bmatrix} \ mod \ 26 \\ &= \begin{bmatrix}182 \\ 275 \\\end{bmatrix} mod \ 26 \\ &= \begin{bmatrix}0 \\ 15 \\\end{bmatrix} mod \ 26 \\ \end{aligned}

Finally, we have to convert these numbers back to letters, so ‘o’ becomes ‘A’ and ‘15’ becomes ‘p’ and our first two letters of the ciphertext are AP

Thus,

$\begin{bmatrix}H & I \\ L & L \\\end{bmatrix} \begin{bmatrix}S \\ H \\\end{bmatrix} = \begin{bmatrix} 7 & 8 \\ 11 & 11 \\\end{bmatrix} \begin{bmatrix}18 \\ 7 \\\end{bmatrix} = \begin{bmatrix} 182 \\ 275 \\\end{bmatrix} = \begin{bmatrix}0 \\ 15 \\\end{bmatrix} \ mod \ 26 \ = \begin{bmatrix} A \\ P \\\end{bmatrix}$

Follow the same procedure for the next column vectors of plain text.

The final ciphertext is “A P A D J T F T W L F J”

Decryption:

$P \ = \ [C] \ [K^{-1}] \ mod \ 26$

$k^{-1} \ = \ \frac{1}{|d|} \ adj \ [k]$

Key = k = $\begin{bmatrix} H & I \\ L & L \\\end{bmatrix}$ = $\begin{bmatrix}7 & 8 \\ 11 & 11 \\\end{bmatrix} = 11 \times 7 - 88$

= - 11 mod 26

D = 15

We want $\frac{1}{D}$ i.e. $d \times d^{-1} = 1 \ mod \ 26$

\begin{aligned} 15 * x &= 1 \ mod \ 26 \\ d^{-1} &= 7 \\ &= adj \begin{bmatrix} a & b \\ c & d \\\end{bmatrix} = \begin{bmatrix} d & -b \\ -c & a \\\end{bmatrix} \\ &= \begin{bmatrix} 11 & -8 \\ -11 & 7 \\\end{bmatrix} = \begin{bmatrix} 11 & 18 \\ 15 & 7 \\\end{bmatrix} mod \ 26 \\ & = \ 7 \times \begin{bmatrix} 11 & 18 \\ 15 & 7 \\\end{bmatrix} = \begin{bmatrix} 77 & 126 \\ 165 & 49 \\\end{bmatrix} mod \ 26 \\ \end{aligned}

$\Rightarrow \ k^{-1} = \begin{bmatrix} 25 & 22 \\ 1 & 23 \\\end{bmatrix}$

\begin{aligned} \Rightarrow \ P & = \begin{bmatrix} 25 & 22 \\ 1 & 23 \\\end{bmatrix} \begin{bmatrix} A \\ P \\\end{bmatrix} \\ &= \begin{bmatrix} 25 & 22 \\ 1 & 23 \\\end{bmatrix} \begin{bmatrix} 0 \\ 15 \\\end{bmatrix} \\ & = \ \begin{bmatrix} 25 \times 0 + 22 \times 15 \\ 1 \times 0 + 23 \times 15 \\\end{bmatrix} \ \begin{bmatrix} 330 \\ 345 \\\end{bmatrix} \\ & = \ \begin{bmatrix} 18 \\ 7 \\\end{bmatrix} \ mod \ 26 \\ &= \begin{bmatrix} S \\ H \\\end{bmatrix} \\ \end{aligned}

Follow the same procedure for the next column vectors of ciphertext.

So the final plaintext is short example