Substitution Algorithm

Caesar Cipher in Cryptography

• The Caesar cipher is a simple encryption technique that was
used by Julius Caesar to send secret messages to his allies. It
works by shifting the letters in the plaintext message by a certain
number of positions, known as the “shift” or “key”.
• The Caesar Cipher technique is one of the earliest and simplest
methods of encryption technique. It’s simply a type of
substitution cipher, i.e., each letter of a given text is replaced by
a letter with a fixed number of positions 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 apparently named after
Julius Caesar, who apparently used it to communicate with his
officials.
• Thus to cipher a given text we need an integer value, known as
a shift which indicates the number of positions each letter of the
text has been moved down.
The encryption can be represented using modular arithmetic by
first transforming the letters into numbers, according to the
scheme, A = 0, B = 1,…, Z = 25. Encryption of a letter by a
shift n can be described mathematically as.
• For example, if the shift is 3, then the letter A would be replaced
by the letter D, B would become E, C would become F, and so
on. The alphabet is wrapped around so that after Z, it starts back
at A.
• Here is an example of how to use the Caesar cipher to encrypt
the message “HELLO” with a shift of 3:
 1. Write down the plaintext message: HELLO
2. Choose a shift value. In this case, we will use a shift of 3.
3. Replace each letter in the plaintext message with the letter that
is three positions to the right in the alphabet.
H becomes K (shift 3 from H)

E becomes H (shift 3 from E)

L becomes O (shift 3 from L)

L becomes O (shift 3 from L)

O becomes R (shift 3 from O)

4.The encrypted message is now “KHOOR”.

• To decrypt the message, you simply need to shift each letter

back by the same number of positions. In this case, you would
shift each letter in “KHOOR” back by 3 positions to get the
original message, “HELLO”.

(Encryption Phase with shift n)

(Decryption Phase with shift n)

Examples :
Text : ABCDEFGHIJKLMNOPQRSTUVWXYZ
Shift: 23
Cipher: XYZABCDEFGHIJKLMNOPQRSTUVW

Text : ATTACKATONCE
Shift: 4
Cipher: EXXEGOEXSRGI
Advantages:
• Easy to implement and use thus, making suitable for beginners
to learn about encryption.
• Can be physically implemented, such as with a set of rotating
disks or a set of cards, known as a scytale, which can be useful
in certain situations.
• Requires only a small set of pre-shared information.
• Can be modified easily to create a more secure variant, such as
by using a multiple shift values or keywords.
Disadvantages:
• It is not secure against modern decryption methods.
 • Vulnerable to known-plaintext attacks, where an attacker has
access to both the encrypted and unencrypted versions of the
same messages.
• The small number of possible keys means that an attacker can
easily try all possible keys until the correct one is found, making
it vulnerable to a brute force attack.
• It is not suitable for long text encryption as it would be easy to
crack.
• It is not suitable for secure communication as it is easily broken.
• Does not provide confidentiality, integrity, and authenticity in a
message.
Features of caesar cipher:
1. Substitution cipher: The Caesar cipher is a type of substitution
cipher, where each letter in the plaintext is replaced by a letter
some fixed number of positions down the alphabet.
2. Fixed key: The Caesar cipher uses a fixed key, which is the
number of positions by which the letters are shifted. This key is
known to both the sender and the receiver.
3. Symmetric encryption: The Caesar cipher is a symmetric
encryption technique, meaning that the same key is used for
both encryption and decryption.
4. Limited keyspace: The Caesar cipher has a very limited
keyspace of only 26 possible keys, as there are only 26 letters
in the English alphabet.
5. Vulnerable to brute force attacks: The Caesar cipher is
vulnerable to brute force attacks, as there are only 26 possible
keys to try.
 6. Easy to implement: The Caesar cipher is very easy to implement
and requires only simple arithmetic operations, making it a
popular choice for simple encryption tasks.
Rules for the Caesar Cipher:
1. Choose a number between 1 and 25. This will be your “shift”
value.
2. Write down the letters of the alphabet in order, from A to Z.
3. Shift each letter of the alphabet by the “shift” value. For
example, if the shift value is 3, A would become D, B would
become E, C would become F, and so on.
4. Encrypt your message by replacing each letter with the
corresponding shifted letter. For example, if the shift value is 3,
the word “hello” would become “khoor”.
5. To decrypt the message, simply reverse the process by shifting
each letter back by the same amount. For example, if the shift
value is 3, the encrypted message “khoor” would become
“hello”.
The Caesar Cipher is a type of shift cipher. Shift Ciphers work by
using the modulo operator to encrypt and decrypt messages. The
Shift Cipher has a key K, which is an integer from 0 to 25. We will
only share this key with people that we want to see our message.

How to Encrypt:
For every letter in the message M :

1. Convert the letter into the number that matches its order in the
alphabet starting from 0, and call this number X.
( A=0, B=1, C=2, ...,Y=24, Z=25)

2. Calculate: Y = (X + K) mod 26

3. Convert the number Y into a letter that matches its order in the
alphabet starting from 0.

(A=0, B=1, C=2, ...,Y=24, Z=25)

For Example: We agree with our friend to use the Shift Cipher
with key K=19 for our message.
We encrypt the message "KHAN", as follows:

So, after applying the Shift Cipher with key K=19 our message text
"KHAN" gave us cipher text "DATG".

We give the message "DATG" to our friend.

How to decrypt:
For every letter in the cipher text C :

1. Convert the letter into the number that matches its order in the
alphabet starting from 0, and call this number Y.
(A=0, B=1, C=2, ..., Y=24, Z=25)

2. Calculate: X= (Y - K) mod 26

3. Convert the number X into a letter that matches its order in the
alphabet starting from 0.
(A=0, B=1, C=2, ..., Y=24, Z=25)

Our friend now decodes the message using our agreed upon key
K=19. As follows:
So, after decrypting the Shift Cipher with key K=19 our friend
deciphers the cipher text "DATG" into the message text "KHAN".

Why is the Shift Cipher insecure?

A cipher should prevent an attacker, who has a copy of the cipher
text but does not know the key, from discovering the contents of the
message. Since we only have 26 choices for the key, someone can
easily try all of the 26 keys, one by one, until they recover the
message. This type of attack is called a brute force attack.
Playfair Cipher with Examples
The scheme was invented in 1854 by Charles Wheatstone but was named
after Lord Playfair who promoted the use of the cipher. In playfair cipher
unlike traditional cipher we encrypt a pair of alphabets(digraphs) instead of
a single alphabet.
It was used for tactical purposes by British forces in the Second Boer War
and in World War I and for the same purpose by the Australians during
World War II. This was because Playfair is reasonably fast to use and requires
no special equipment.

Encryption Technique
For the encryption process let us consider the following example:

The Playfair Cipher Encryption Algorithm:

The Algorithm consists of 2 steps:

1. Generate the key Square(5×5):

 • The key square is a 5×5 grid of alphabets that acts as the
key for encrypting the plaintext. Each of the 25 alphabets
must be unique and one letter of the alphabet (usually J) is
omitted from the table (as the table can hold only 25
alphabets). If the plaintext contains J, then it is replaced by
I.

• The initial alphabets in the key square are the unique

alphabets of the key in the order in which they appear
followed by the remaining letters of the alphabet in order.

2. Algorithm to encrypt the plain text: The plaintext is split into

pairs of two letters (digraphs). If there is an odd number of letters,
a Z is added to the last letter.
For example:

PlainText: "instruments"
After Split: 'in' 'st' 'ru' 'me' 'nt' 'sz'
1. Pair cannot be made with same letter. Break the letter in single and add a
bogus letter to the previous letter.
Plain Text: “hello”
After Split: ‘he’ ‘lx’ ‘lo’
Here ‘x’ is the bogus letter.
2. If the letter is standing alone in the process of pairing, then add an extra
bogus letter with the alone letter
Plain Text: “helloe”
AfterSplit: ‘he’ ‘lx’ ‘lo’ ‘ez’
Here ‘z’ is the bogus letter.
Rules for Encryption:

• If both the letters are in the same column: Take the letter below
each one (going back to the top if at the bottom).
For example:

Diagraph: "me"
Encrypted Text: cl
Encryption:
m -> c
e -> l
•
 •
• If both the letters are in the same row: Take the letter to the right
of each one (going back to the leftmost if at the rightmost position).
For example:

Diagraph: "st"
Encrypted Text: tl
Encryption:
s -> t
t -> l
•

•
 • If neither of the above rules is true: Form a rectangle with the
two letters and take the letters on the horizontal opposite corner of
the rectangle.
For example:

Diagraph: "nt"
Encrypted Text: rq
Encryption:
n -> r
t -> q
•

•
For example:

Plain Text: "instrumentsz"

Encrypted Text: gatlmzclrqtx
Encryption:
i -> g
n -> a
s -> t
t -> l
r -> m
u -> z
m -> c
e -> l
n -> r
t -> q
s -> t
z -> x
Vigenère Cipher
Vigenere Cipher is a method of encrypting alphabetic text. It uses a simple
form of polyalphabetic substitution. A polyalphabetic cipher is any cipher
based on substitution, using multiple substitution alphabets. The encryption
of the original text is done using the Vigenère square or Vigenère table.
• The table consists of the alphabets written out 26 times in
different rows, each alphabet shifted cyclically to the left
compared to the previous alphabet, corresponding to the 26
possible Caesar Ciphers.
• At different points in the encryption process, the cipher uses a
different alphabet from one of the rows.
• The alphabet used at each point depends on a repeating keyword.
Example:
Input : Plaintext : GEEKSFORGEEKS
Keyword : AYUSH
Output : Ciphertext : GCYCZFMLYLEIM
For generating key, the given keyword is repeated
in a circular manner until it matches the length of
the plain text.
The keyword "AYUSH" generates the key "AYUSHAYUSHAYU"
The plain text is then encrypted using the process
explained below.
Encryption:
The first letter of the plaintext, G is paired with A, the first letter of the key.
So use row G and column A of the Vigenère square, namely G. Similarly, for
the second letter of the plaintext, the second letter of the key is used, the
letter at row E, and column Y is C. The rest of the plaintext is enciphered in
a similar fashion.
Table to encrypt – Geeks

Decryption:
Decryption is performed by going to the row in the table corresponding to
the key, finding the position of the ciphertext letter in this row, and then
using the column’s label as the plaintext. For example, in row A (from
AYUSH), the ciphertext G appears in column G, which is the first plaintext
letter. Next, we go to row Y (from AYUSH), locate the ciphertext C which is
found in column E, thus E is the second plaintext letter.
A more easy implementation could be to visualize Vigenère algebraically
by converting [A-Z] into numbers [0–25].
Encryption
The plaintext(P) and key(K) are added modulo 26.
Ei = (Pi + Ki) mod 26

Decryption
Di = (Ei - Ki) mod 26
Note: Di denotes the offset of the i-th character of the plaintext. Like offset
of A is 0 and of B is 1 and so on.
Autokey Cipher | Symmetric Ciphers
Autokey Cipher is a polyalphabetic substitution cipher. It is closely related
to the Vigenere cipher but uses a different method of generating the key. It
was invented by Blaise de Vigenère in 1586. In general, more secure than
the Vigenere
cipher.

Example-1:
Plaintext = "HELLO"
Autokey = N
Ciphertext = "ULPWZ"
Example-2:
Plaintext = "GEEKSFORGEEKS"
Autokey = P
Ciphertext = "VKIOCXTFXKIOC"
In this cipher, the key is a stream of subkeys which is used to encrypt the
corresponding character in the
plaintext.

As shown, the autokey is added at the first of the subkeys.

Let's explain Example 1:

Given plain text is : H E L L O

Key is : N H E L L

Let's encrypt:

Plain Text(P) : H E L L O
Corresponding Number: 7 4 11 11 14
Key(K) : N H E L L
Corresponding Number: 13 7 4 11 11
---------------------
Applying the formula: 20 11 15 22 25

Corresponding
Letters are : U L P W Z

Hence Ciphertext is: ULPWZ

Let's decrypt:

Cipher Text(C) : U L P W Z
Key(K) : N H E L L
---------------------
Applying the formula: H E L L O

Hence Plaintext is: HELLO

Vernam Cipher or One Time Pad
Algorithm
One Time Pad algorithm is the improvement of the Vernam Cipher, proposed by
An Army Signal Corp officer, Joseph Mauborgne. It is the only available algorithm
that is unbreakable(completely secure). It is a method of encrypting alphabetic
plain text. It is one of the Substitution techniques which converts plain text into
ciphertext. In this mechanism, we assign a number to each character of the Plain-
Text.
The two requirements for the One-Time pad are
• The key should be randomly generated as long as the size of the message.
• The key is to be used to encrypt and decrypt a single message, and then it
is discarded.
So encrypting every new message requires a new key of the same length as the
new message in one-time pad.
The ciphertext generated by the One-Time pad is random, so it does not have any
statistical relation with the plain text.
The assignment is as follows:
A B C D E F G H I J

0 1 2 3 4 5 6 7 8 9

K L M N O P Q R S T

10 11 12 13 14 15 16 17 18 19

U V W X Y Z

20 21 22 23 24 25

The relation between the key and plain text: In this algorithm, the length of the key
should be equal to that of plain text.
Examples:
Input: Message = HELLO, Key = MONEY
Output: Cipher – TSYPM, Message – HELLO
Explanation: Part 1: Plain text to Ciphertext Plain text — H E L L O ? 7 4 11 11
14 Key — M O N E Y ? 12 14 13 4 24 Plain text + key ? 19 18 24 15 38 ? 19 18
24 15 12 (= 38 – 26) Cipher Text ? T S Y P M Part 2: Ciphertext to
Message Cipher Text — T S Y P M ? 19 18 24 15 12 Key — M O N E Y? 12 14
13 4 24 Cipher text – key ? 7 4 11 11 -12 ? 7 4 11 11 14 Message ? H E L L
O Input: Message = SAVE, Key = LIFE Output: Cipher – DIAI Message – SAVE
Security of One-Time Pad
• If any way cryptanalyst finds these two keys using which two plaintext
are produced but if the key was produced randomly, then the
cryptanalyst cannot find which key is more likely than the other. In fact,
for any plaintext as the size of ciphertext, a key exists that produces that
plaintext.
• So if a cryptanalyst tries the brute force attack(try using all possible
keys), he would end up with many legitimate plaintexts, with no way of
knowing which plaintext is legitimate. Therefore, the code is
unbreakable.
• The security of the one-time pad entirely depends on the randomness of
the key. If the characters of the key are truly random, then the characters
of the ciphertext will be truly random. Thus, there are no patterns or
regularities that a cryptanalyst can use to attack the ciphertext.
Advantages
• One-Time Pad is the only algorithm that is truly unbreakable and can be
used for low-bandwidth channels requiring very high security(ex. for
military uses).
Disadvantages
• There is the practical problem of making large quantities of random keys.
Any heavily used system might require millions of random characters on
a regular basis.
• For every message to be sent, a key of equal length is needed by both
sender and receiver. Thus, a mammoth key distribution problem exists.
Hill Cipher

D
DamanAnand

• Read

• Discuss

• Courses

• Practice
Hill cipher is a polygraphic substitution cipher based on linear algebra.Each
letter is represented by a number modulo 26. Often the simple scheme A = 0, B =
1, …, Z = 25 is used, but this is not an essential feature of the cipher. To encrypt a
message, each block of n letters (considered as an n-component vector) is
multiplied by an invertible n × n matrix, against modulus 26. To decrypt the
message, each block is multiplied by the inverse of the matrix used for
encryption.
The matrix used for encryption is the cipher key, and it should be chosen
randomly from the set of invertible n × n matrices (modulo 26).
Examples:

Input : Plaintext: ACT

Key: GYBNQKURP
Output : Ciphertext: POH

Input : Plaintext: GFG

Key: HILLMAGIC
Output : Ciphertext: SWK

Encryption
We have to encrypt the message ‘ACT’ (n=3).The key is ‘GYBNQKURP’ which can
be written as the nxn matrix:
The message ‘ACT’ is written as vector:

The enciphered vector is given as:

which corresponds to ciphertext of ‘POH’

Decryption
To decrypt the message, we turn the ciphertext back into a vector, then simply
multiply by the inverse matrix of the key matrix (IFKVIVVMI in letters).The
inverse of the matrix used in the previous example is:
For the previous Ciphertext ‘POH’:

which gives us back ‘ACT’.

Assume that all the alphabets are in upper case.
Below is the implementation of the above idea for n=3.
Implementation of Affine Cipher
The Affine cipher is a type of monoalphabetic substitution cipher, wherein
each letter in an alphabet is mapped to its numeric equivalent, encrypted
using a simple mathematical function, and converted back to a letter. The
formula used means that each letter encrypts to one other letter, and back
again, meaning the cipher is essentially a standard substitution cipher with
a rule governing which letter goes to which.
The whole process relies on working modulo m (the length of the alphabet
used). In the affine cipher, the letters of an alphabet of size m are first
mapped to the integers in the range 0 … m-1.
The ‘key’ for the Affine cipher consists of 2 numbers, we’ll call them a and b.
The following discussion assumes the use of a 26 character alphabet (m =
26). a should be chosen to be relatively prime to m (i.e. a should have no
factors in common with m).

Encryption
It uses modular arithmetic to transform the integer that each plaintext letter
corresponds to into another integer that correspond to a ciphertext letter.
The encryption function for a single letter is
E ( x ) = ( a x + b ) mod m
modulus m: size of the alphabet
a and b: key of the cipher.
a must be chosen such that a and m are coprime.
Decryption
In deciphering the ciphertext, we must perform the opposite (or inverse)
functions on the ciphertext to retrieve the plaintext. Once again, the first
step is to convert each of the ciphertext letters into their integer values. The
decryption function is
D ( x ) = a^-1 ( x - b ) mod m
a^-1 : modular multiplicative inverse of a modulo m. i.e., it
satisfies the equation
1 = a a^-1 mod m .
To find a multiplicative inverse
We need to find a number x such that:
If we find the number x such that the equation is true, then x is the inverse
of a, and we call it a^-1. The easiest way to solve this equation is to search
each of the numbers 1 to 25, and see which one satisfies the equation.
[g,x,d] = gcd(a,m); % we can ignore g and d, we dont need them
x = mod(x,m);
If you now multiply x and a and reduce the result (mod 26), you will get the
answer 1. Remember, this is just the definition of an inverse i.e. if a*x = 1
(mod 26), then x is an inverse of a (and a is an inverse of x)
Example:
 Transposition

Rail Fence Cipher – Encryption and

Decryption
• Read

• Discuss

• Courses

• Practice
Given a plain-text message and a numeric key, cipher/de-cipher the given text
using Rail Fence algorithm.
The rail fence cipher (also called a zigzag cipher) is a form of transposition
cipher. It derives its name from the way in which it is encoded.
Examples:

Encryption
Input : "GeeksforGeeks "
Key = 3
Output : GsGsekfrek eoe
Decryption
Input : GsGsekfrek eoe
Key = 3
Output : "GeeksforGeeks "

Encryption
Input : "defend the east wall"
Key = 3
Output : dnhaweedtees alf tl
Decryption
Input : dnhaweedtees alf tl
Key = 3
Output : defend the east wall

Encryption
Input : "attack at once"
Key = 2
Output : atc toctaka ne
Decryption
Input : "atc toctaka ne"
Key = 2
Output : attack at once
Encryption
In a transposition cipher, the order of the alphabets is re-arranged to obtain the
cipher-text.

• In the rail fence cipher, the plain-text is written downwards and

diagonally on successive rails of an imaginary fence.
• When we reach the bottom rail, we traverse upwards moving
diagonally, after reaching the top rail, the direction is changed again.
Thus the alphabets of the message are written in a zig-zag manner.
• After each alphabet has been written, the individual rows are combined
to obtain the cipher-text.
For example, if the message is “GeeksforGeeks” and the number of rails = 3 then
cipher is prepared as:

.’.Its encryption will be done row wise i.e. GSGSEKFREKEOE

Decryption
As we’ve seen earlier, the number of columns in rail fence cipher remains equal
to the length of plain-text message. And the key corresponds to the number of
rails.

• Hence, rail matrix can be constructed accordingly. Once we’ve got the
matrix we can figure-out the spots where texts should be placed (using
the same way of moving diagonally up and down alternatively ).
• Then, we fill the cipher-text row wise. After filling it, we traverse the
matrix in zig-zag manner to obtain the original text.
Implementation:
Let cipher-text = “GsGsekfrek eoe” , and Key = 3

• Number of columns in matrix = len(cipher-text) = 13

 • Number of rows = key = 3
Hence original matrix will be of 3*13 , now marking places with text as ‘*’ we get

* _ _ _ * _ _ _ * _ _ _ *
_ * _ * _ * _ * _ * _ *
_ _ * _ _ _ * _ _ _ * _
Given a plain-text message and a numeric key, cipher/de-cipher the given
text using Columnar Transposition Cipher
The Columnar Transposition Cipher is a form of transposition cipher just
like Rail Fence Cipher. Columnar Transposition involves writing the
plaintext out in rows, and then reading the ciphertext off in columns one by
one.
Examples:
Encryption
Input : Geeks for Geeks
Key = HACK
Output : e kefGsGsrekoe_
Decryption
Input : e kefGsGsrekoe_
Key = HACK
Output : Geeks for Geeks

Encryption
Input : Geeks on work
Key = HACK
Output : e w_eoo_Gs kknr_
Decryption
Input : e w_eoo_Gs kknr_
Key = HACK
Output : Geeks on work
Encryption
In a transposition cipher, the order of the alphabets is re-arranged to obtain
the cipher-text.
1. The message is written out in rows of a fixed length, and then read
out again column by column, and the columns are chosen in some
scrambled order.
2. Width of the rows and the permutation of the columns are usually
defined by a keyword.
3. For example, the word HACK is of length 4 (so the rows are of
length 4), and the permutation is defined by the alphabetical order
of the letters in the keyword. In this case, the order would be “3 1
2 4”.
4. Any spare spaces are filled with nulls or left blank or placed by a
character (Example: _).
5. Finally, the message is read off in columns, in the order specified
by the keyword.
 Decryption
1. To decipher it, the recipient has to work out the column lengths by
dividing the message length by the key length.
2. Then, write the message out in columns again, then re-order the
columns by reforming the key word.