Book Chapter 1

# Introduction to Cryptography¶

## Chapter 1 : An Overview of Subject¶

### Motivation¶

Throughout history, we could see that efficient communication is a matter of great concern to govern the nation and command the armies. At the same time, they are well aware of the consequences of their messages falling into the wrong hands, revealing precious secrets to rival nations and betraying vital information to opposing forces.[2] This threat motivated the development of codes and ciphers: techniques for disguising a message so that only the intended recipient can read it.[2]

### Introduction¶

Cryptography is the art of secret communication. Authentication and integrity are the important aspects of cryptography. Authentication allows receiving parties to make sure that the communication come from the genuine sender[1]. Integrity ensures that the message received is not altetred.
Figure 1.1 The figure illustrates a basic cryptosystem.
The characters in the figure are Dspboy, Jarvis and hacker. The hackers try to break the code and may manipulate the information conveyed. So to ensure a reliable transfer of original message, Dspboy has to convert the original message (plain text) to secret code (cipher text). The conversion of original plain text to cipher text is called encryption. At the receiver side Jarvis will decrypt the cipher text to original message. Encryption and decryption are done using a key. So this means the sender and receiver should know the key.
With the advent of high speed computers extremely complicated cryptosystems can be implemented, but at the same time hackers can use powerful computing tools to break the cryptosystems. There is always an intellectual battle between code makers and code breakers. This is very evident from history. So Cryptography or Cryptology is an ever challenging area. This is because a code is useful only till the code breakers find a way to break the code. Then the code either becomes extinct or evolves into a new stronger code. This continues forever.
Now the interesting question is: Where do we implement cryptosystems?
Cryptosystems can be implemented on any alphabet. An Alphabet is any finite set of symbols. For example 26 uppercase English letters {A,B,C,D,...,Z} is a alphabet. Binary alphabet are represented as {0,1}. Any ordered sequence of letters from a alphabet is called string. For example SHANNON is a string of length 7. Binary strings (also called as bit strings) are strings from the binary alphabet {0,1}. For example, 101001 is a bit string of length 6. Each individual digit in a binary string is called bit.
There are several algorithms developed from time to time to accomplish the encryption and decryption process. In the coming section we will take a journey through the evolution of codes.

### Coding Exercise¶

Converting Strings of Digits to/from Vectors
• Integer Vector to Lower-Case String
In [1]:
function  Int2LCText(Vec)
#str = Int2LCText(Vec)
#Input: Vec =  A vector of non negative integers in the range(0,1,2,...,25)
#Output: str = a string of corresponding Lower case Text (alphabet: a, b,...,z)
#0 => a, 1 => b...., 25 =>z
x= 1;
y = 'a';

+(x::Integer,y::Char);
if (minimum(Vec) < 0 || maximum(Vec)> 25)
println("Error!!Input Integer components must between 0 and 25")
else
str=[];
for i = 1: length(Vec)
str =push!(str,Vec[i]+ y)
end
end
return str
end

Out[1]:
Int2LCText (generic function with 1 method)
In [2]:
str = Int2LCText([1,2,3,4,5,6,7,8,9,10])

Out[2]:
10-element Array{Any,1}:
'b'
'c'
'd'
'e'
'f'
'g'
'h'
'i'
'j'
'k'
• Convert Integer Vector to Upper Case Text
In [3]:
function  Int2UCText(Vec)
#str = Int2LCText(Vec)
#Input: Vec =  A vector of non negative integers in the range(0,1,2,...,25)
#Output: str = a string of corresponding Upper case Text (alphabet: A, B,...,Z)
#0 => A, 1 => B...., 25 =>Z
x= 1;
y = 'A';

+(x::Integer,y::Char);
if (minimum(Vec) < 0 || maximum(Vec)> 25)
println("Error!!Input Integer components must between 0 and 25")
else
str=[];
for i = 1: length(Vec)
str =push!(str,Vec[i]+ y)
end
end
return str
end

Out[3]:
Int2UCText (generic function with 1 method)
In [4]:
Int2UCText([1 2 3 4 5 6 7 8 9 25])

Out[4]:
10-element Array{Any,1}:
'B'
'C'
'D'
'E'
'F'
'G'
'H'
'I'
'J'
'Z'
• Convert Lower Case Text to Integers
In [5]:
function LCTEXT2Int(str)
#Vec = LCTEXT2Int(str)
#Input: str = a string of corresponding Lower case Text (alphabet: a, b,...,z)
#0 => a, 1 => b...., 25 =>z
#Output: Vec = A vector of non negative integers in the range(0,1,2,...,25)

x= 1;
y = 'a';

+(x::Integer,y::Char);
if (minimum(str) < 'a' || maximum(str)> 'z')
println("Error!!Input alphabet components must between a and z")
else
Vec =[];
for i = 1: length(str)
Vec =push!(Vec,Int(str[i]) - Int(y))
end
end
return Vec
end

Out[5]:
LCTEXT2Int (generic function with 1 method)
In [6]:
str =['a','c','d','e','f','g','h','i','j','k','l'];
LCTEXT2Int(str)

Out[6]:
11-element Array{Any,1}:
0
2
3
4
5
6
7
8
9
10
11
• Convert Lower Case text with spaces to integers
In [7]:
function  LCTextWithSpaces2Int(str)
# Vec = LCTextWithSpaces2Int(str)
# Input: str = a string of lowercase text with spaces
# Output:  Vec = the vector of nonnegative integers in the range (0, 1, ..., 25, 26)
# under the standard correspondence:
# 0 <-> a,  1 <-> b, ..., 25 <-> z, 26 <-> space

Vec =[];
for i = 1:length(str)
if Int(str[i]) > 32
Vec = push!(Vec,Int(str[i]) - Int('a'));
else
Vec = push!(Vec,26);
end
end
return Vec
end

Out[7]:
LCTextWithSpaces2Int (generic function with 1 method)
In [8]:
str = "earth is beautiful"
LCTextWithSpaces2Int(str)

Out[8]:
18-element Array{Any,1}:
4
0
17
19
7
26
8
18
26
1
4
0
20
19
8
5
20
11
• Convert Upper Case Text to Integers
In [9]:
function UCTEXT2Int(str)
#Input: str = a string of corresponding Upper case Text (alphabet: A, B,...,Z)
# Output :Vec = A vector of non negative integers in the range(0,1,2,...,25)
x= 1;
y = 'A';

+(x::Integer,y::Char);
if (minimum(str) < 'A' || maximum(str)> 'Z')
println("Error!!Input Alphabet components must between A and Z")
else
Vec =[];
for i = 1: length(str)
Vec =push!(Vec,Int(str[i]) - Int(y))
end
end
return Vec
end

Out[9]:
UCTEXT2Int (generic function with 1 method)
In [10]:
str = "IAM"
UCTEXT2Int(str)

Out[10]:
3-element Array{Any,1}:
8
0
12
• Convert Upper Case Text to Lower Case Text
In [11]:
function UCText2LCText(str)
#Input: str = a string of corresponding Upper case Text (alphabet: A, B,...,Z)
#Output:  #Output: str = a string of corresponding Lower case Text (alphabet: a, b,...,z)
str = Int2LCText(UCTEXT2Int(str));
end

Out[11]:
UCText2LCText (generic function with 1 method)
In [12]:
str ="MOTHER"
UCText2LCText(str)

Out[12]:
6-element Array{Any,1}:
'm'
'o'
't'
'h'
'e'
'r'
• Convert Lower case text to upper case text
In [13]:
function  LCText2UCText(str)
str = Int2UCText(LCTEXT2Int(str))
end

Out[13]:
LCText2UCText (generic function with 1 method)
In [14]:
str = "nature"
LCText2UCText(str)

Out[14]:
6-element Array{Any,1}:
'N'
'A'
'T'
'U'
'R'
'E'

### Evolution of Codes¶

#### The Cipher of Mary Queen of Scots¶

Figure1.2 Mary Queen of Scots(Source: Wikipedia)
Mary wanted to assassinate Queen Elizabeth I in order to take the English crown for herself.She began exchanging messages with her co-conspirators. But unfortuntely Mary's messages were captured by Elizabeth's spies and Mary was put on trial for treason. But Mary had the hope that she will not be charged for treason. This was because their messages enciphered, so that they could not be read if they fell into the wrong hands.
But her fate was already sealed by the breaking of the codes by Elizabeth's cheif code breaker.
Figure 1.3 Ciphers used by Mary Queen of Scots(Source:http://www.nationalarchives.gov.uk/education/resources/elizabeth-monarchy/ciphers-used-by-mary-queen-of-scots/)
Each letter from A to Z was substituted by a cipher alphabet. The cipher also contains some code symbols for the most common words, and some more sophisticated symbols.
Substitution cipher is simply a mapping from a plaintext alphabet to a unique ciphertext alphabet.
Example : Let the plaintext be the set of lowercase letters P = {a, b, c,...,z} and the ciphertext be the set of uppercase letters P = {A,B,C,....,Z}.
Plaintext letters: abcdefghijklmnopqrstuvwxyz
Ciphertext letters: QWERTYUIOPASDFGHJKLZXCVBNM
Using this key, every plaintext letter a would be replaced by ciphertext Q, every plaintext letter q by J, etc.
One of the earliest descriptions of encryption by substitution appears in the Kama-sutra. The Kama-sutra recommends that women should study sixty-four arts. Number forty-five on the list is mlecchita-vikalpa, the art of secret writing, recommended in order to help women conceal the details of their liaisons.

#### The Caesar Cipher¶

Figure1.4a Caesar Cipher(Source: https://ehistory.osu.edu/biographies/gaius-julius-caesar)
Caesar replaced each letter in the message with the letter that is three places further down the alphabet. When the plain alphabet is placed above the cipher alphabet, it is clear that the cipher alphabet has been shifted by three places, and hence this form of substitution is often called the Caesar shift cipher, or simply the Caesar cipher.
Figure1.4b Caesar Cipher

### Coding Exercise¶

• Implement Shift Encryption Cipher
In [15]:
function ShiftCrypt(str,kappa)
# Vec = LCTextWithSpaces2Int(str)
# Input: str = a string of lowercase text with spaces
# Output:  Vec = the vector of nonnegative integers in the range (0, 1, ..., 25, 26)
# under the standard correspondence:
# 0 <-> a,  1 <-> b, ..., 25 <-> z, 26 <-> space

Vec = LCTEXT2Int(str);
VecOut = mod(Vec + kappa, 26);
StrOut = Int2UCText(VecOut)
end

Out[15]:
ShiftCrypt (generic function with 1 method)
In [16]:
str ="abcdz"
kappa = 3;
ShiftCrypt(str,kappa)

Out[16]:
5-element Array{Any,1}:
'D'
'E'
'F'
'G'
'C'

#### Vigenere Cipher¶

Vigenere Cipher requires a key and Vigenere Tableau. We will understand Vigenere Cipher with an example.
Plaintext = nature
keyword = MOTHER
Now we need Vigenere Tableau to encode
Figure1.5 Vigenere Tableau
Steps to encode
Plaintext = nature
keyword = mother
Step 1 : Consider the first elements of plaintext and keyword i.e n and m respectively.
Step 2 : Locate the column corresponding to the first element of plaintext i.e n from the Vigenere Tableau.
Step 3 : Locate the row corresponding to the first element of keyword i.e m from the Vigenere Tableau.
Step 4 : The intersection of the row and column will be letter. This letter will be the first element of ciphertext.
Step 5 : Repeat the above steps for the remaining letters.
Note: The length of plaintext and keyword has to be same.
Note: The intersection of column corresponding to theith element of plaintext and row corresponding to ith element of keyword is used to get the ith element of ciphertext.
ciphertext : ZOMBVV

### Coding Exercise¶

• Implement Vigenere Cipher
In [17]:
function vigener_crypt(str, keystr)
#Inputs: str = a string of lower case text (alphabet: a, b, ..., z)
#keystr = a string of lower case text (alphabet: a, b, ..., z)
#Output: StrOut = a string of corresponding Upper-Case ciphertext (alphabet: A, B, ..., Z):
#resulting from encrypting str using the Vigenere cipher with key ke
if length(str) == length(keystr)
return Int2UCText(mod(LCTEXT2Int(str) + LCTEXT2Int(keystr), 26));
else
error("Plain text and the key word should have the same length");
end
end

Out[17]:
vigener_crypt (generic function with 1 method)
In [18]:
str = "nature"
keystr = "mother";
vigener_crypt(str, keystr)

Out[18]:
6-element Array{Any,1}:
'Z'
'O'
'M'
'B'
'V'
'V'
• Implement Vigenere Cipher Decryption
In [19]:
function VigenereDecrypt(str,keystr)
Vec = LCTEXT2Int(keystr);
keylength = length(keystr);
LCSTR = Int2LCText(UCTEXT2Int(str));
StrOut = [];
for i = 1:length(str)
ishift  = mod(i,keylength);
if ishift == 0
ishift = keylength;
end
StrOut = push!(StrOut,ShiftCrypt(LCSTR[i],-Vec[ishift]));
end

# StrOut = Int2LCText(UCTEXT2Int(StrOut));
return StrOut
end

Out[19]:
VigenereDecrypt (generic function with 1 method)
In [20]:
str = "ZOMBVV"
keystr = "mother";
VigenereDecrypt(str,keystr)

Out[20]:
6-element Array{Any,1}:
Any['N']
Any['A']
Any['T']
Any['U']
Any['R']
Any['E']
• Implement Random Integer Generation
In [21]:
function RandIntGen(mini,maxi,len)
#Vec = RandIntGen(min, max, length)
# Inputs:  min, max, length, where, min < max are integers, and length is a positive integer.
#Output:  Vec, a vector with length components that are
#radomly generated integers in the range min <= k <= max
Vec = mini + floor((maxi + 1 - mini)*rand(1,len));
end

Out[21]:
RandIntGen (generic function with 1 method)
In [22]:
mini = 1;
maxi = 5;
len = 10
RandIntGen(mini,maxi,len)

Out[22]:
1×10 Array{Float64,2}:
1.0  1.0  1.0  5.0  1.0  4.0  3.0  4.0  2.0  4.0

### Reference¶

[1] Stanoyevitch, Alexander. Introduction to Cryptography with mathematical foundations and computer implementations. CRC Press, 2010.
[2] Singh, Simon. The code book: the secret history of codes and code-breaking. Fourth Estate, 2000.