“AN INTRODUCTION TO CRYPTOGRAPHY”

A Project Work Submitted

In The Partial Fulfilment For The Requirements

Of The Bachelor Degree of Science In Mathematics

By

RAJ PATEL

ROLL NO: S04523MTH004

SEMESTER-VI

Guided By:-
Dr. MRITYUNJAY MALIK
Assistant professor
Panchayat Degree college, Bargarh
 ACKNOWLEDGEMENT

Sincerely thank to Dr. Mrityunjay Malik Sir, Assistant professor of Mathematics, PCB
for his encourage and guidance in carrying out this project work on “An Introduction
to Cryptography” and for providing me an opportunity to do my project work. I would
be pleased to extend my thanks to all the staff of the Mathematics department and my
Freinds who have always had their helping hand during my time of need. Finally, I am
deeply thankful to my parents and teachers who helped and inspired me in completing
this project.

Raj Patel
 DECLARATION

I, Raj Patel, do hereby declare that the review entitled “An Introduction to
Cryptography” submitted to the Department of Mathematics, Panchayat College,
Bargarh has been carried out by me for the partial fulfilment of Bachelor degree of
science in Mathematics. To the best of my knowledge this project work has not been
submitted to any Institute/University for the award of any degree.

Raj Patel
 CERTIFICATE

(Dr. Shusanta Kumar Padhan)

Assistant Professor
Department of Chemistry
Panchayat College, Bargarh

ABSTRACT

Plastic waste pollution is a significant environmental concern due to its non-

biodegradable nature and widespread accumulation. One promising solution to
mitigate this issue is the conversion of plastic waste into fuel through thermochemical
processes such as pyrolysis, gasification, and hydrothermal liquefaction. This study
explores the feasibility of extracting fuel from plastic waste, analyzing its efficiency,
environmental impact, and economic viability. Pyrolysis, a widely used method,
involves heating plastic waste in the absence of oxygen to produce liquid fuel, syngas,
and char. The resulting fuel exhibits properties comparable to conventional fossil
fuels, making it a potential alternative energy source. However, challenges such as
process optimization, catalyst selection, and emissions control must be addressed to
enhance scalability and sustainability. This research highlights the potential of plastic-
to-fuel technology in waste management and energy production, emphasizing the need
for further advancements to improve efficiency and reduce environmental impact.
Key words: Plastics, Composition, Oil Extraction Methods, Maximum Yield,
Properties of Plastic Oil.

INTRODUCTION
Cryptography is the science of using mathematics to encrypt and decrypt data. In
the language of cryptography, where codes are called ciphers, the information to be
concealed is called plaintext. After transformation to a secret form, a message is called
ciphertext. The process of converting from plaintext to ciphertext is said to be
encrypting, whereas the reverse process of changing from ciphertext back to plaintext
is called decrypting.

Cryptography is an interdisciplinary subject, drawing from several fields

especially mathematics. Nowadays cryptography makes extensive use of technical
areas of mathematics, specifically those areas collectively known as discrete
mathematics. Modern cryptography relies heavily on concepts from number theory.

Cryptography makes secure web sites and electronic safe transmissions possible.
Due to the large number of commercial transactions on the internet, cryptography is
very key in ensuring security of transactions. Cryptography is also used in access
control to regulate access such as in cable TV and satellite. Without cryptography,
hackers could get into our e-mail, listen in on our phone conversations, or break into
banks/brokerage accounts. Hence in general, cryptography is an important way of
achieving confidentiality, data integrity, user authentication and non-repudiation
CHAPTER 1

SOME TOPICS IN ELEMENTARY NUMBER THEORY

In this section, we will be outlining several topics from number theory which we
will need in order to explore the mathematics behind the cryptographic ciphers.

1.1 Divisibility and the Euclidean algorithm:

Given integers 𝑎� and b with 𝑎�≠ 0, we say that 𝑎� divides b (or “b is divisible by
𝑎�”) and we write 𝑎�|b if there exists an integer d such that b=𝑎�d.

In that case we call 𝑎� a divisor of b. By a proper divisor of b, we mean a positive

divisor not equal to b itself, and by a non-trivial divisor of b, we mean a positive
divisor not equal to 1 or b.

Lemma 1.1.1:-

Suppose we have two integers 𝑎� and b with a common divisor d≠0. That is, d|𝑎� and
d|𝑏� ,then we will have d|(𝑟�𝑎�+𝑠�𝑏�) for any integers r and s. Proof. Because d is a
divisor of both 𝑎� and b, we can write a=𝑑�𝑗� and b=𝑑�𝑘� for some integers j and k.
Then r𝑎�+sb=𝑟�(dj)+s(dk)=d(rj+sk). Since (rj+sk) is an integer then it follows that
d|(ra+sb).

Proposition 1.1.1.
Given two non- negative integers a and b, with a≠0, there exists a pair
of unique integers q and r with 0≤ r < a such that b=aq+ r. We call q the
quotient and r the remainder when b is divided by a.
Greatest common divisor: Given two integers 𝑎� and b, not both zero, the
greatest common divisor of a and b, denoted g.c.d.(𝑎�,b) is the largest integer d
dividing both 𝑎� and b. If the greatest common divisor of a and b is 1, then we say that
a and b are relatively prime.
The Euclidean Algorithm:

Euclidean algorithm is useful for computing the g.c.d of two positive integers.
Suppose we have two positive integers 𝑎� and b, with 𝑎�>b. The Euclidean algorithm
works as follows. To find g.c.d.(𝑎�,b), we first divide b into a and write down the
quotient 𝑞�1 and the remainder r1: 𝑎�=q1 b+𝑟�1. Next, we perform a second division
with b playing the role of 𝑎� and 𝑟�1 playing the role of b; b=𝑞�2𝑟�1+𝑟�2. Next, we divide
r2 i𝑛�𝑡�𝑜� 𝑟�1:𝑟�1=𝑞�3𝑟�2+ 𝑟�3. We continue in this way, each time dividing the last
remainder into the second-to-last remainder, obtaining a new quotient and remainder.
When we finally obtain a remainder that divides the previous remainder, we are done:
that final nonzero remainder is the greatest common divisor of 𝑎� and b.

Example 1: Find g.c.d (1547,560).

Solution: 1547= 2. 560 + 427

560 = 1. 427 + 133

427 = 3. 133 + 28

133 = 4. 28 + 21

28 = 1. 21 + 7

Since 7/21, we are done: g.c.d(1547,560) = 7 .

Definition: A prime number is an integer greater than one which has no positive
divisors other than 1 and itself. A number is called composite if it has at least one non
trivial divisor.

Theorem 1.1.1–The Fundamental Theorem of Arithmetic :

Given any natural number n, n can be written uniquely (except for the order of
factors) as a product of prime numbers.
Example. 4200 = 23.3. 52.7

Proposition 1.1.2. Let d= g.c.d(𝑎�,b) where 𝑎�>𝑏�. Then there exist integers u and v
such that d= u𝑎�+bv. In other words, the g.c.d of two numbers can be expressed as a
linear combination of the numbers with integer coefficient.

Example 2. From example 1, g.c.d(1547,560) =7. Express 7 as a linear combination

of 1547 and 560.

Solution: To express 7 as a linear combination of 1547 and 560, we successively

compute:

7= 28 – 1. 21

= 28 – 1. (133 - 4. 28)

= 5. 28 – 1. 133

= 5. (427 – 3. 133) – 1. 133

= 5. 427 – 16. 133

= 5. 427 – 16. (560 – 1.427)

= 21. 427 – 16. 560

= 21. (1547 – 2. 560) – 16. 560

= 21. 1547 – 58. 560

Definition: We say that two integers 𝑎� and b are relatively prime (or “ 𝑎� is prime to
b”) if g.c.d(𝑎�, b) =1, i.e., if they have no common divisor greater than 1.

1.2 Congruences:
Given three integers 𝑎�, b and m, we say that “𝑎� is congruent to b modulo
m” and write 𝑎�≡ b mod m, if the difference 𝑎�−𝑏� is divisible by m. The following
properties are easily proved directly from the definition:
1. (i) 𝑎��≡ 𝑎��mod 𝑚�
 (ii)𝑎��≡ 𝑏��mod 𝑚� iff 𝑏��≡ 𝑎��mod 𝑚�
(iii) If 𝑎��≡ 𝑏��mod 𝑚� and 𝑏��≡ 𝑐��mod 𝑚�, then 𝑎��≡ 𝑐��mod 𝑚�.
2. If 𝑎� ≡ b mod 𝑚� and 𝑐�≡𝑑�mod𝑚�, then a ± 𝑐�� ≡ 𝑏�� ± 𝑑�� mod 𝑚� and 𝑎�𝑐�� ≡ 𝑏�𝑑��
mod 𝑚�. In other words, congruences with the same modulus can be added,
subtracted or multiplied.

3. If 𝑎��≡ 𝑏��mod 𝑚�, then 𝑎��≡ 𝑏��mod 𝑑� for any divisor d|𝑚�.

4. If 𝑎�� ≡ 𝑏�� mod 𝑚�, 𝑎�� ≡ 𝑏�� mod 𝑛�, and m and n are relatively prime, then 𝑎�� ≡ 𝑏��
mod 𝑚�𝑛�.

5. In property 1,(i)-(iii) mean that the congruence modulo m is an equivalence

relation. For fixed m, each equivalence class with respect to congruence modulo
m has one and only one representative between 0 and m-1. The set of equivalence
classes (called residue classes) will be denoted Z/mz. Any set of representatives
for the residue classes is called a complete set of residues modulo m.

Proposition 1.2.1. The elements of Z/mz which have multiplicative inverses are
those which are relatively prime to m, i.e., the numbers 𝑎� for which there exists b with
𝑎�𝑏��≡ 1 mod 𝑚� are precisely those 𝑎� with g.c.d(𝑎�,𝑚�)=1.

Proof: First, if d=g.c.d(𝑎�,m) were greater than 1, we could not have 𝑎�𝑏�� ≡ 1 mod 𝑚�
for any b, because that would imply that d divides 𝑎�b-1 and hence divides 1.
Conversely, if g.c.d(𝑎�,𝑚�)=1, then by property 5, we may suppose that 𝑎�<m�.

�Then� by� Proposition� 1.1.2,� there� exist� integers� u� and� v� for� which� u𝑎�+vm=1.�

Choosing�b=u,�we�see�that�m|1-u𝑎�=1-𝑎�𝑏�,�as�desired.�

Example:�Find�160−1�mod�841,�i.e.,�the�inverse�of�160�modulo�841.

�Solution:�By�Euclidean�algorithm,�we�have�

���������������������������������841=�5.�160�+�41�160

�����������������������������������������=�3.�41�+�37�41
�����������������������������������������=�1.�37�+�4�37

�����������������������������������������=�9.�4�+�1�

���������������Hence,� g.c.d(160,� 841)� =1� and� by� Proposition� 1.2.1,� inverse� of� 160�
modulo� 841� exists.� To� find� the� inverse,� we� express� 1� as� a� linear� combination� of�
160�and�841�as�follows:

���������������������������������������1=�37�–�9.�

������������������������������������������=�37�–�9.�(41�–�1.�37)

������������������������������������������=�10.�37-�9.�41�

������������������������������������������=�10.�(160�–�3.�41)�–�9.�41

������������������������������������������=�10.�160�–�39.�41

������������������������������������������=�10.�160�–�39.�(841�–�5.�160)

������������������������������������������=�205.�160�–�39.�841

�Hence�the�answer�is�205.

Proposition�1.2.2.�(Fermat’s�Little�Theorem):

�����������Let�p�be�a�prime.�Any�integer�𝑎��satisfies�𝑎�𝑃��≡�𝑎��mod�𝑝�,�and�any�integer�a�
not�divisible�by�p�satisfies�a𝑃�−1≡�1�mod�𝑝�.�

Proof:� First� suppose� that� p∤𝑎�.� We� first� claim� that� the� integers�
0𝑎�,1𝑎�,2𝑎�,3𝑎�,…(𝑝�−1)𝑎��are�a�complete�set�of�residues�modulo�p.�To�see�this,�we�
observe�that�otherwise�two�of�them�say�i𝑎��and�j𝑎�,�would�have�to�be�in�the�same�
residue�class,�i.e.,�𝑖�𝑎�≡𝑗�𝑎�mod𝑝�.�But�this�would�mean�that�p|(i�-�j)𝑎�,�and�since�𝑎��
is�not�divisible�by�p,�we�would�have�P|�(i�–�j).�Since�i�and�j�are�both�less�than�p,�the�
only� way� this� can� happen� is� if� i=j.� We� conclude� that� the� integers� ��
�,2𝑎�,…,(𝑝�−1)𝑎�� are� simply� a� rearrangement� of� 1,� 2,…,p-1� when� considered�
modulo�p.�Thus,�it�follows�that�the�product�of�the�numbers�in�the�first�sequence�is�
congruent�modulo�p�to�the�product�of�the�numbers�in�the�second�sequence,�i.e.,

����������������������������𝑎�𝑃�−1(p-1)!�≡�(𝑝�−1)!�𝑚�𝑜�𝑑���𝑝�.�

Thus,�p|(p-1)!�(𝑎�𝑃�−1−1).�

�������Since�(p-1)!�is�not�divisible�by�p,�we�have�p|(𝑎�𝑃�−1−1),�as�required.�Finally,�if�
we�multiply�both�sides�of�the�congruence�𝑎�𝑝�−1��≡�1�mod�𝑝��by�𝑎�,�we�get�𝑎�𝑃�≡�𝑎��
mod� 𝑝�� when� 𝑎�� is� not� divisible� by� p.� But� if� 𝑎�� is� divisible� by� p,� then� this�
congruence�𝑎�𝑃�≡�𝑎��mod�𝑝��is�trivial.�This�concludes�the�proof�of�the�proposition.�

Proposition�1.2.3.(Chinese�Remainder�Theorem):

�Suppose�that�we�want�to�solve�a�system�of�congruences�to�different�modulo;�

�����������������������������������x≡𝑎�1�𝑚�𝑜�𝑑��𝑚�1,�

�����������������������������������x≡𝑎�2�𝑚�𝑜�𝑑��𝑚�2,

�����������������������������������…..

����������������������������������x≡𝑎�𝑟��mod�𝑚�𝑟.�

���������Suppose� that� each� pair� of� moduli� is� relatively� prime;� g.c.d(𝑚�𝑖�,𝑚�𝑗�)=1� for�
𝑖�≠𝑗�.� Then� there� exists� a� simultaneous� solution� x� to� all� of� the� congruences,� and�
any�two�solutions�are�congruent�to�one�another�modulo�M=𝑚�1𝑚�2…𝑚�𝑟�.�

Proof:� First,� we� prove� uniqueness� modulo� M.� Suppose� that� x’� and� x’’� are� two�
solutions.� Let� x=� x’� –� x’’.� Then� x� must� be� congruent� to� 0� modulo� each� 𝑚�𝑖�,� and�
hence�modulo�M(�by�property�4�of�congruences).�We�next�show�how�to�construct�
a�solution�x.�

Define�𝑀�𝑖�=M∕m𝑖��to�be�the�product�of�all�of�the�moduli�except�for�the�𝑖�th.�Clearly�
g.c.d(𝑚�𝑖�,𝑀�𝑖�)=1,�and�so�there�is�an�integer�𝑁�𝑖��such�that�𝑀�𝑖�𝑁�𝑖�≡1�mod�𝑚�𝑖�.�Now�
set
�x=�∑i�𝑎�𝑖�𝑀�𝑖�𝑁�𝑖��.�Then�for�each�i,�we�see�that�terms�in�the�sum�other�than�the�𝑖�th�
term� are� all� divisible� by� 𝑚�𝑖�,� because� m𝑖�|� Mj� whenever� i� ≠� j.� thus� for� each� i,� we�
have�x≡�𝑎�𝑖�𝑀�𝑖�𝑁�𝑖��≡�𝑎�𝑖��mod�𝑚�𝑖�,�as�desired.

�Definition:�The�Euler�𝜙�-function,𝜙�(𝑛�),�is�defined�to�be�the�number�of�positive�
integers�less�than�or�equal�to�n�which�are�relatively�prime�to�n.

�Proposition� 1.2.4.� the� Euler� 𝜙�-function� is� multiplicative,� meaning� that�

𝜙�(𝑚�𝑛�)=𝜙�(𝑚�)⋅𝜙�(𝑛�)�whenever�g.c.d(m,n)=1.�

Proof:�we�must�count�the�number�of�integers�between�0�and�mn-1�which�have�no�
common�factor�with�mn.�For�each�j�in�that�range,�let�𝑗�1�be�its�least�non-negative�
residue� modulo� m� (i.e.� 0≤𝑗�1� <m� and� j� ≡� j1� � � mod� m)� and� let� 𝑗�2� be� its� least�
nonnegative�residue�modulo�n�(i.e.�0≤𝑗�2<n�and�j≡𝑗�2mod�n).�It�follows�from�the�
Chinese� reminder� theorem� that� for� each� pair� 𝑗�1,� 𝑗�2� there� is� one� and� only� one� j�
between� 0� and� mn� -1� for� which� j≡𝑗�1mod� m� and� j≡𝑗�2mod� n.� j� has� no� common�
factor� with� mn� iff� it� has� no� common� factor� with� m� which� is� equivalent� to� 𝑗�1�
having� no� common� factor� with� m� and� it� has� no� common� factor� with� n� which� is�
equivalent� to� 𝑗�2� having� no� common� factor� with� n.� thus� the� j’s� which� we� must�
count�are�in�one-to-one�

correspondence�with�the�pairs�𝑗�1,�𝑗�2�for�which�0≤𝑗�1<m,�g.c.d(𝑗�1,m)=1;�0≤𝑗�2<n�
and��

g.c.d�(𝑗�2,n)=1.�The�number�of�possible�𝑗�1′𝑠��is�𝜙�(𝑚�)�and�the�number�of�possible�
𝑗�2’s�is�𝜙�(𝑛�).�So�the�number�of�pairs�is�𝜙�(𝑚�)⋅𝜙�(𝑛�).�Hence�the�proof.��

Since�every�n�can�be�written�as�a�product�of�prime�powers,�each�of�which�has�no�
common�factors�with�the�others,�and�

since� we� know� the� formula� 𝜙�(𝑃�𝛼�)=𝑃�𝛼�(1−1/𝑝�),� we� can� use� the� above�
proposition�to�conclude�that�for��
n=𝑃�1𝛼�1 𝑃�2𝛼�2…�𝑃�𝑟�𝛼�𝑟�,
�

1 1 1
�𝜙�(𝑛�)=𝑃�1𝛼�1�(1− )�𝑃�2𝛼�2�(1− )�…�𝑃�𝑟�𝛼�𝑟��(1− )�
𝑃1 𝑃2 𝑃𝑟

���������=n∏� 𝑃�∕𝑛�(1−
𝑃
1
)

Proposition�1.2.5.�If�g.c.d(𝑎�,𝑚�)=1,�then�𝑎�𝜙�(𝑚�)≡1mod𝑚�.�

Proof:� We� first� prove� the� proposition� in� the� case� when� m� is� a� prime� power:�
m=𝑃�𝛼�.We�use�induction�on�𝛼�.�The�case�𝛼�=1�is�precisely�Fermat’s�little�theorem.�
Suppose� that� 𝛼�≥2,� and� the� formula� holds� for� the� (𝛼�−1)th� power� of� P.� Then�
𝛼−1 −𝑃 𝛼−2
𝑎𝑃 =�1�+�𝑃α−1 𝑏��for�some�integer�b,�by�the�induction�assumption.�Raising�
both�sides�of�this�equation�to�the�p-th�power�and�using�the�fact�that�the�binomial�
coefficients� in(1+𝑥�)𝑃�� are� each� divisible� by� p� (except� in� the� 1� and� 𝑥�𝑃�� at� the�
𝛼 −𝑃 𝛼−1
ends),� we� see� that�𝑎𝑃 is� equal� to� 1� plus� a� sum� with� each� term� divisible� by�
α)
𝑃�𝛼�.�That�is,𝑎�ϕ(𝑃 − 1�is�divisible�by�𝑃�𝛼�,�as�desired.�This�proves�the�proposition�
for�prime�powers.��

Finally,�by�the�multiplicativity�of�𝜙�,�it�is�clear�that�

𝑎ϕ(m)� ≡1�mod�𝑃�𝛼�.�Since�this�is�true�for�each�𝑃�𝛼��which�is�the�highest�power�of�p�
dividing� m,� and� since� the� different� prime� powers� have� no� common� factors� with�
one�another,�it�follows�by�property�4�of�congruences�that�𝑎ϕ(m)� ≡1�mod�𝑚�.

�Modular�exponentiation�by�repeated�squaring�method:�

�������A� basic� computation� one� often� encounters� in� modular� arithmetic� is� finding�
𝑏�𝑛�mod𝑚��when�both�m�and�n�are�very�large.�There�is�a�clever�way�of�doing�this�
that�is�much�quicker�than�repeated�multiplication�of�b�by�itself.�In�what�follows,�
we�shall�assume�that�b�by�itself.
�����In�what�follows,�we�shall�assume�that�b<𝑚�,�and�that�whenever�we�perform�a�
multiplication,�we�then�immediately�reduce�mod�m�(i.e.,�replace�the�product�by�its�
least�non�negative�residue).�In�that�way,�we�never�encounter�any�integers�greater�
than�𝑚�2.�We�now�describe�the�algorithm.�

�����Use�𝑎��to�denote�the�partial�product.�When�we�are�done,�we�will�have�𝑎��equal�
to�the�least�non�negative�residue�of�𝑏 𝑛�� mod�𝑚�.�We�start�out�with�𝑎�=1.�

������Let�𝑛�0,�𝑛�1,�…,�𝑛�𝑘�−1�denote�the�binary�digits�of�n,�i.e.�

�����������������n=𝑛�0+2𝑛�1+�4𝑛�2+…+2𝑘�−1�𝑛�𝑘�−1.�

Each�𝑛�𝑗��is�0�or�1.�If�𝑛0 =1,�change�𝑎��to�b.�Then�square�b,�and�set��𝑏�1=𝑏�2�mod�m�

(i.e.,�𝑏�1�is�the�least�non�negative�residue�of�𝑏�2�mod�m).�If�𝑛�1=1,�multiply�𝑎��by�𝑏�1�,�
otherwise�keep�a�unchanged.�Next�square�𝑏�1,�and�set�

�𝑏�2≡𝑏�12� mod� 𝑚�.� If� � 𝑛�2=1,� multiply� 𝑎�� by� 𝑏�2,� otherwise� keep� 𝑎�� unchanged.�
𝑗
Continue�in�this�way.�You�see�that�in�the�𝑗�th�step,�you�have�computed�𝑏�𝑗�≡�𝑏 2 mod�
m.�If�𝑛�𝑗�=1,�

i.e.,� if�2𝑗 �occurs� in� the� binary� expansion� of� n,� then� you� include� 𝑏�𝑗��in� the� product�
for�𝑎�.�After�(k-1)-st�step�you’ll�have�the�desired�𝑎�≡𝑏�𝑛��mod�𝑚�.
Chapter-2

CRYPTOGRAPHY
2.1 Preliminaries of Cryptography:
In this chapter provides the basic terms related to Cryptography.

Encoder
An encoder is an electronic device used to convert an analogue signal to a digital
signal.

Decoder
The decoder an electronic device that is used to convert digital signal to an
analogue signal.
Cipher Text
Cipher text is encrypted text. Plaintext is what you have before encryption, and
cipher text is the encrypted result. The term cipher is sometimes used as a synonym for
cipher text, but it more properly means the method of encryption rather than the result.
Cryptography
Cryptography is the study of methods to send and receive secret message. In
private key cryptography, the sender and receiver agree in advance on a secret code,
and then send message using the code. In public key cryptography, the encoding
method can be published. Each person has a public key used to encrypt message. The
original message is called the plain text. The encoded text is called Cipher text.

2.2 Types of Cryptography:

Cryptography is broadly classified into two. They are symmetric key
cryptography and asymmetric key cryptography.
2.2.1 Symmetric Key Cryptography
The cryptographic method in which same key is used for both encryption and
decryption of information is called symmetric key cryptography. Therefore, the sender
and the receiver will be having access for the key. Since both the parties have access to
the secret key, it is considered as a main drawback of the symmetric key encryption
compared to the public key encryption. Symmetric key Cryptography is commonly
used in today's internet. AES and DES are the common Encryption Algorithm used in
symmetric key cryptography. It is faster than asymmetric key cryptography.
Symmetric key encryption either uses stream cipher or block cipher. The stream cipher
encrypts digits or letters of a message there as block cipher consider bits as a single
unit and encrypt them as a whole. Payment applications, generation random number
generation or hashing are some if the applications of symmetric key cryptography.
2.2.2 Asymmetric Key Cryptography
Asymmetric key Cryptography is a public key cryptographic scheme which
requires two different keys. One key is used to the encryption process and other is use
for the decryption of the cipher text. One of the keys in the asymmetric key encryption
is a public key which is accessible to the public and the other is kept private which is
known as private key. Asymmetric key encryption is also known as public key
cryptography. The advantage of asymmetric Cryptography compared to symmetric key
cryptography is the non-Reliance on a single point of failure of key. Asymmetric key
Cryptography has an increase data security. Since asymmetric key encryption uses a
longer key for the encryption process, it results in a slower encryption speed. Digital
signature, TLS or SSL handshake, crypto currency are some of the applications of
asymmetric key cryptography.
2.2.3 Hashing
Hashing is the process of transforming any given key or a string of characters
into another value. Implementing hash tables is the most well-liked application of
hashing. Value and key pairs are kept in a list that can be accessed by a hash table's
index. The hash function would map the keys to the size of the table because value and
key pairs are infinite. The index for a given element is then changed to a hash value.
Hashing uses functions or algorithms to map object data to a representative integer
value. A hash can then be used to narrow down searches when locating these items on
that object data map.
2.3 Some Simple Cryptosystems:
Basic notions: Cryptography is the study of methods of sending messages in
disguised form so that only the intended recipients can remove the disguise and read
the message. The message we want to send is called the plaintext and the disguised
message is called ciphertext. The plaintext and ciphertext are written in some alphabet
(usually, but not always, they are written in the same alphabet) consisting of a certain
number N of letters. The term “letter” (or “character”) can refer not only to the
familiar A-Z, but also to numerals, blanks, punctuation marks, or any other symbols
that we allow ourselves to use when writing the messages (if we don‟t include a blank,
for example, then all of the words are run together, and the messages are harder to
read). The process of converting a plaintext to a ciphertext is called enciphering or
encryption, and the reverse process is called deciphering or decryption.

The plaintext and ciphertext are broken up into „message units‟. A message unit
might be a single letter, a pair of letters(digraph), a triple of letters(trigraph) or a block
of 50 letters. An enciphering transformation is a function that takes any plaintext
message unit and gives us a ciphertext message unit.
In other words, it is a map f from the set P of all possible plaintext message units
to the set C of all possible ciphertext message units. We shall always assume that f is a
1-to-1 correspondence, i.e., given a ciphertext message unit, there is one and only one
plaintext message unit for which it is the encryption. The deciphering transformation
is the map 𝑓�−1 which goes back and recovers the plaintext from the ciphertext. We can
represent the situation schematically by the diagram
f 𝑓 −1
P → 𝐶��→ 𝑃�

Any such set-up is called a „cryptosystem‟. The first step in inventing a

cryptosystem is to “label” all possible plaintext message units and all possible
ciphertext message units by means of mathematical objects from which functions can
be easily constructed. These objects are often simply the integers in some range. For
example, if our plaintext and ciphertext message units are single letters from the 26-
letter alphabet A-Z, then we can label the letters using the integers 0,1, 2, …,25, which
we call their “numerical equivalents”. Thus, in place of A we write 0, in place of S we
write 18, in place of X we write 23, and so on. As another example, if our message
units are digraphs (i.e. pair of letters) in the 27-letter alphabet consisting of A-Z and a
blank, we might first let the blank have numerical equivalent 26(one beyond Z), and
then label the digraph whose two letters correspond to x, y ∈� {0, 1, 2, …,26} by the
integer 27x + y ∈�{0, 1, …,728}.
 Thus, we view the individual letters as digits to the base 27 and we view the
digraph as a 2-digit integer to that base. For example, the digraph “NO” corresponds
to the integer 27. 13 + 14=365. Analogously, if we were using trigraphs as our
message units, we could label them by integers 729x +27y + z ∈� {0, 1, …,19682}. In
general, we can label blocks of k letters in an N-letter alphabet by integers between 0
and 𝑁�𝑘�−1 by regarding each such block as a k digit integer to the base N.

In some situations, one might want to label message units using other
mathematical objects besides integers-for example, vectors or points on some curve.
But we shall only consider integers throughout this section. Let us start with the case
when we take a message unit (of plaintext or ciphertext) to be a single letter in an N-
letter alphabet labeled by the integers 0, 1, 2, …, N-1. Then by definition, an
enciphering transformation is a rearrangement of these N integers.

2.3.2 Shift Transformation:

Suppose we are using the 26-letter alphabet A-Z with numerical equivalents
[Link] the letter P ∈� {0,1,2,…,25} stand for a plaintext message unit. Define a
function f from the set {0,1,2,…,25} to itself by the rule,
P + 3, if�x < 23
f(P) =�{
P − 3, if�x ≥ 23�
In other words, f simply adds 3 modulo 26: f(P)≡P+3 mod 26. Thus, with this
system, to encipher the word “YES” we first convert to numbers: 24 4 18, then add 3
modulo 26:1 7 21, then translate back to letters: “BHV”. To decipher a message, one
subtracts 3 modulo 26. For example, the ciphertext “ZKB” yields the plaintext
“WHY”. This cryptosystem was apparently used in ancient Rome by Julius Caesar,
who supposedly invented it himself.
Example given above can be generalized as follows. Suppose we are using an N-
letter alphabet with numerical equivalents 0, 1, 2, …, N-1. Let b be a fixed integer.
By a shift transformation we mean the enciphering function f defined by the rule C=
F(p)≡P+b mod N. Julius Caesar‟s cryptosystem was the case N=26, b=3. To decipher a
ciphertext message unit C∈{0,1,2,…,𝑁�−1}, we simply compute

P=𝑓�−1(𝐶�)≡C– b mod N.
2.3.3 Cryptanalysis:
Now suppose that you are not privy to the enciphering and deciphering
information, but you would nevertheless like to be able to read the coded messages.
This is called breaking the code, and the science of breaking codes is called
cryptanalysis.
In order to break a cryptosystem, one needs two types of information. The first is
the general nature (the structure) of the system. For example, suppose we know that
the cryptosystem uses a shift transformation on single letters of the 26-letter alphabet
A-Z with numerical equivalents 0-25 respectively. The second type of information is
knowledge of a specific choice of certain parameters connected with the given type of
cryptosystem. In our example, the second type of information one needs to know is the
choice of the shift parameter b. Once one has that information, one can encipher and
decipher by the formulas C≡P+b mod N and P≡C– b mod N.

We shall always assume that the general structural information is already known.
In practice, users of cryptography often have equipment for enciphering and
deciphering which is constructed to implement only one type of cryptosystem. Over a
period of time the information about what type of system they are using might leak
out. To increase their security, therefore, they frequently change the choice of
parameters used with the system. For example, suppose that two users of the shift
cryptosystem are able to meet once a year. At that time, they agree on a list of 52
choices of the parameter b, one for each week of the coming year. The parameter b
(more complicated cryptosystems usually have several parameters) is called a key, or
more precisely, the enciphering key.

Example: So suppose that we intercept the message “FQOCUDEM”, which we

know was enciphered using a shift transformation on single letters of the 26-letter
alphabet. It remains for us to find the b. One way to do this is by frequency analysis.
This works as follows. Suppose that we have already intercepted a long string of
ciphertext, say several hundred letters. We know that “E” is the most frequently
occurring letter in the English language. So it is reasonable to assume that the most
frequently occurring letter in the ciphertext is the encryption of E. Suppose that we
find that “U” is the most frequently occurring character in the ciphertext. That means
that the shift takes “E” =4 to “U” =20, i.e., 20≡4 + b mod 26, so that b=16. To
decipher the message, then, it remains for us to subtract 16 (working modulo 26) from
the numerical equivalent of “FQOCUDEM”: “FQOCUDEM” = 5 16 14 2 20 3 4 12
⟼

15 0 24 12 4 13 14 22

= “PAYMENOW”.

2.3.4 Affine Transformations:

In the case of a shift encryption of single letters of a 26-letter alphabet, it is not

even necessary to have a long string of ciphertext to find the most frequently occurring
letter. After all, there are only 26 possibilities for b, and one can simply run through all
of them. Most likely, only one will give a message that makes any sense, and that b is
the enciphering key.
Thus, this type of cryptosystem is too simple to be much good. It is too easy to
break. An improvement is to use a more general type of transformation of Z/NZ,
called an affine map: C≡𝑎�P + b mod N, where 𝑎� and b are fixed integers (together
they form the enciphering key). For example, working again in the 26-letter alphabet,
if we want to encipher our message “PAYMENOW” using the affine transformation
with enciphering key 𝑎�=7, b=12, we obtain:
15 0 24 12 4 13 14 22⟼ 13 12 24 18 14 25 6 10
= “NMYSOZGK”.
To decipher a message that was enciphered by means of the affine map C≡𝑎�P + b
mod N, one simply solves for P in terms of C, obtaining P≡𝑎�′𝐶�+𝑏�′ mod N, where 𝑎�′
is the inverse of 𝑎� modulo N and 𝑏�′ is equal to - 𝑎�−1𝑏�. Note that this works only if
g.c.d(𝑎�, N) =1; Otherwise we cannot solve for P in terms of C. If g.c.d(𝑎�, N)>1, then
it is easy to see that more than one plaintext letter will give the same ciphertext, so that
we cannot uniquely recover the plaintext from the ciphertext. For example, if we were
to encipher the message “PAYBACK” by means of the affine map C≡𝑎�P + b mod N
where 𝑎�=10, b=12, again in the 26-letter alphabet. Here g.c.d(𝑎�, N) =2>1 and we
observe that the plaintext units “P” and “C” corresponds to ciphertext unit “G”. By
definition, that is not an enciphering transformation: we always require that the map
be 1-to-1, i.e., that the plaintext be uniquely determined from the ciphertext. To
summarize, an affine cryptosystem in an N letter alphabet with parameters
𝑎�∈(Z/NZ)∗and b∈(Z/NZ) consists of the rules:
C≡𝑎�P + b mod N, P≡𝑎�′𝐶�+𝑏�′ mod N,
Where 𝑎�′=𝑎−1 in (Z/NZ)∗ , 𝑏�′= - 𝑎−1 𝑏�.
As a special case of the affine cryptosystems we can set 𝑎�=1, thereby obtaining
the shift transformations. Another special case is when b=0: P≡𝑎�C mod N, C≡𝑎−1 P
mod N. The case b=0 is called a linear transformation, meaning that the map takes a
sum to a sum, i.e., if 𝐶�1 is the encryption of 𝑃�1 and 𝐶�2 is the encryption of 𝑃�2, then
𝐶�1+𝐶�2 is the encryption of 𝑃�1+𝑃�2 (where, of course, we are adding modulo N).
Now suppose that we know that an intercepted message was enciphered using an
affine map of single letters in an N letter alphabet. We would like to determine the
enciphering key 𝑎�, b so that we can read the message. We need to know two bits of
information to do this.
Example 1. Still working in our 26-letter alphabet, suppose that we know the most
frequently occurring letter of ciphertext is “K”, and the second most frequently
occurring letter is “D”. It is reasonable to assume that these are the encryptions of “E”
and “T”, respectively, which are the two most frequently occurring letters in the
English language. Thus, replacing the letters by their numerical equivalents and
substituting for P and C in the deciphering formula, we obtain:
10𝑎�′+𝑏�′≡ 4 mod 26
3𝑎�′+𝑏�′≡19 mod 26.
We have two congruences with two unknowns, 𝑎�′ and 𝑏�′. The quickest way to
solve is to subtract the two congruences to eliminate 𝑏�′. We obtain 7𝑎�′≡11 mod 26,
and a′≡7−111≡9 mod 26. Finally, we obtain 𝑏�′ by substituting this value for 𝑎�′ in one
of the congruences: b′≡4−10𝑎�′≡18 mod 26. So, messages can be deciphered by means
of the formula P≡ 9C + 18 mod 26.
Example 2. If we try to cryptanalyze an affine enciphering transformation of single-
letter message units in a 37-letter alphabet. This alphabet includes the numerals 0-9,
which are labeled by themselves (i.e., by the integers 0-9). The letters A-Z have
numerical equivalents 10-35, respectively, and blank=36(indicated by an “_” for
understanding). You intercept the ciphertext “OH7F86BB46R3627O266BB9” (here
the O‟s are the letter “oh”, not the numeral zero). You know that the plaintext ends
with signature “007” (zero zero seven). What is the message?
From the given information, we know that “B” is the encryption for “0” (zero),
and “9” is the encryption for “7”.
Thus, replacing the letters by their numerical equivalents and substituting for P
and C in the deciphering formula, we obtain:
0≡11𝑎�′+𝑏�′ mod 37
7≡9 𝑎�′+𝑏�′ 𝑚�𝑜�𝑑�� 37
Subtracting the two congruences to eliminate 𝑏�′, we obtain:
2𝑎�′≡−7 mod 37, and
𝑎�′≡(−7)2−1≡15 mod 37
Finally, we obtain 𝑏�′ by substituting this value for 𝑎�′ in one of the congruences:
𝑏�′≡ 20 mod 37. Now, we can decipher the message by the formula P≡ 15C + 20 mod
26, which reads as follows: “AGENT_006_IS_DEAD__007.

2.3.5 Digraph Transformations:

We now suppose that our plaintext and ciphertext message units are two-letter
blocks, called digraphs. For example, if our plaintext is “HELP”, as a digraph it is
represented “HE LP”. This means that the plaintext is split up into two letter segments.
If the entire plaintext has an odd number of letters, then in order to obtain a whole
number of digraphs we add on an extra letter at the end; we choose a letter which is
not likely to cause confusion, such as a blank if our alphabet contains a blank, or else
“X” or “Q” if we are using just the 26-letter alphabet.
Each digraph is then assigned a numerical equivalent. The simplest way to do this
is to take xN+y, where x is the numerical equivalent of first letter in the digraph, y is
the numerical equivalent of the second letter in the digraph, and N is the number of
letters in the alphabet. Equivalently, we think of a digraph as a 2-digit base-N integer.
This gives a one-to-one correspondence between the set of all digraphs in the N-letter
alphabet and the set of all non-negative integers less than 𝑁�2.
Next, we decide upon an enciphering transformation, i.e., a rearrangement of the
integers {0, 1, 2,…, 𝑁�2−1}. Among the simplest enciphering transformations are the
affine ones, where we view this set of integers as Z/𝑁�2𝑍� and define the encryption of
P to be the nonnegative integer less than 𝑁�2 satisfying the congruence C≡𝑎�P + b mod
𝑁�[Link], as before, 𝑎� must have no common factor with N(which means it has no
common factor with 𝑁�2), in order that we have an inverse transformation telling us
how to decipher:
P≡𝑎�′𝐶�+𝑏�′ mod 𝑁�2, where 𝑎�′≡𝑎�−1mod 𝑁�2, b′≡ - 𝑎�−1𝑏� mod 𝑁�2.
We translate C into a two-letter block of ciphertext by writing it in the form
C=𝑥�′𝑁�+𝑦�′, and then looking up the letters with numerical equivalents 𝑥�′ and 𝑦� ′.
Example. Suppose we are working in the 26-letter alphabet and using the digraph
enciphering transformation c≡159𝑃�+580 mod 676. Then the digraph “NO” has
numerical equivalent 13. 26 + 14 = 352 and is taken to the ciphertext digraph 159. 352
+ 580≡ 440 mod 676, which is “QY” (since 440=16. 26 + 24). The digraph “ON” has
numerical equivalent 14. 26 + 13=377, and is taken to 159. 377 + 580≡359= “NV”.
Notice that the digraphs change as a unit, and there is no relation between the
encryption of one digraph and that of another one that has a letter in common with it
or even consists of the same letter in the reverse order.
To break a digraphic encryption system which uses an affine transformation
C≡𝑎�P + b mod 𝑁�2, we need to know the ciphertext corresponding to two different
plaintext message units. Since the message units are digraphs, a frequency analysis
means counting which two letter-blocks occur most often in a long string of ciphertext,
and comparing with the known frequency of digraphs in English language texts. For
example, if we use the 26-letter alphabet, statistical analyses seem to show that “TH”
and “HE” are the two most frequently occurring digraphs, in that order.
Example. You know that your adversary is using a cryptosystem with a 27-letter
alphabet, in which the letters A-Z have numerical equivalents 0-25, and blank=26.
Each digraph then corresponds to an integer between 0 and 728=27 2−1 according to
the rule that, if the two letters have numerical equivalents x and y, then the digraph has
numerical equivalent 27x + y, as explained earlier. Suppose that a study of a large
sample of ciphertext reveals that the most frequently occurring digraphs are “ZA”,
“IA”, and “IW”. Suppose that the most common digraphs in the English language are
“E_” (i.e., E blank), “S_”, “_T”. You know that the cryptosystem uses an affine
enciphering transformation modulo 729. Find the deciphering key, and read the
message “NDXBHO”. Also find the enciphering key.

Solution. We know that plaintexts are enciphered by means of the rule C≡𝑎�P + b mod
729, and that ciphertexts can be deciphered by means of the rule P≡𝑎�′𝐶�+𝑏�′ mod 729;
here 𝑎�, b form the enciphering key, and 𝑎�′, 𝑏�′ form the deciphering key. We first want
to find 𝑎�′ and 𝑏�′. We know how three digraphs are deciphered, and, after we replace
the digraphs by their numerical equivalents, this gives us the three congruences:

675𝑎�′+𝑏�′≡134 mod 729

216𝑎�′+𝑏�′≡512 mod 729

238𝑎�′+𝑏�′≡721 mod 729.

. If we try to eliminate 𝑏�′ by subtracting the first two congruences, we arrive at

459𝑎�′≡351mod729, which does not have a unique solution 𝑎�′ mod 729(there are 27
solutions). We do better if we subtract the third congruence from the first, obtaining
437𝑎�′≡142mod729.

To solve this we must find the inverse of 437 modulo 729. By way of review of
the Euclidean algorithm, lets go through that in detail:
 729=437 + 292

437=292 + 145

292= 2. 145 + 2

145 = 72. 2 + 1

And then

1=145 - 72. 2

=145 – 72(292 – 2. 145)

=145. 145 – 72. 292

=145(437 – 292) – 72. 292

=145. 437 – 217. 292

=145. 437 – 217(729 – 437)

≡362. 437 mod 729.

Thus, 𝑎�′ ≡362. 142≡374 mod 729, and then 𝑏�′ ≡134 – 675. 374 ≡647 mod 729.
Now applying the deciphering transformation to the digraphs “ND”, “XB” and “HO”
of our message-they correspond to the integers 354, 622 and 203, respectively- we
obtain the integers 365, 724 and 24. Writing 365= 13. 27 + 14, 724=26. 27 + 22, 24=0.
27 + 24, we put together the plaintext digraphs into the message “NO WAY”. Finally,
to find the enciphering key we compute 𝑎�≡ 𝑎�′−1≡374−1≡ 614 mod 729(again using
the Euclidean algorithm) and b≡ -𝑎�′−1 𝑏�′ ≡ - 614. 647≡47 mod 729.

Remark: Although affine cryptosystems with digraphs (i.e. modulo 𝑁�2) are better
than the ones using single letters (i.e. modulo N), they also have drawbacks. Notice
that the second letter of each ciphertext digraph depends only on the plaintext digraph.
This is because that second letter depends on the mod- N value of C≡𝑎�P + b mod 𝑁�2,
which depends only on P modulo N, i.e., only on the second letter of the plaintext
digraph. Thus, one could obtain a lot of information (namely, 𝑎� and b modulo N) from
a frequency analysis of the even-numbered letters of the ciphertext message.

2.4 Some Examples of Secrecy Systems

In this section a number of examples of ciphers is given.

[Link] Substitution Cipher:-

In this cipher each letter of the message is replaced by a fixed substitute usually
also a letter. Thus, the message, M= 𝑚�1𝑚�2𝑚�3𝑚�4….. , where 𝑚�1,𝑚�2,𝑚�3,.. are the
successive letters becomes:

E= 𝑒�1𝑒�2𝑒�3𝑒�4… = 𝑓�(𝑚�1) 𝑓�(𝑚�2) 𝑓�(𝑚�3)𝑓�(𝑚�4)… Where the function 𝑓�(m) is a

function with an inverse. The key is a permutation of the alphabet (when the
substitutes are letters). An example key is:

Plain alphabet:
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Cipher alphabet:
PHQGIUMEAYLNOFDXJKRCVSTZWB

An example encryption using the above key:

Plaintext:
DEFEND THE EAST WALL OF THE CASTLE

Ciphertext:
GIUIFG CEI IPRC TPNN DU CEI QPRCNI

[Link] (Fixed Period d):-

The message is divided into groups of length d and a permutation applied to first
group, the same permutation to the second group, etc. The permutation is the key and
can be represented by a permutation of the first d integers. Thus, for d=5, we might
have 2 3 15 4 as the permutation. This means that:

m1𝑚�2𝑚�3𝑚�4𝑚�5𝑚�6𝑚�7𝑚�8𝑚�9𝑚�10…
becomes 𝑚�2𝑚�3𝑚�1𝑚�5𝑚�4𝑚�7𝑚�8𝑚�6𝑚�10𝑚�9…

Sequential application of two or more transpositions will be called compound

transposition. If the periods are d1,𝑑�2,…,𝑑�𝑛� then the result is a transposition of period
d, where d is the least common multiple of d1,𝑑�2,…,𝑑�𝑛� .

[Link] Cipher:-

The most famous example of a polyalphabetic cipher (In a polyalphabetic cipher, a

plaintext has more than one ciphertext equivalent) was published by the French
cryptographer Blaise de Vigenere (1523-1596) in his Traicte de Chiffres of 1586.

To implement this system, the communicating parties agree on an easily

remembered word or phrase. With the standard alphabet numbered from A=00 to
Z=25, the digital equivalent of the keyword is repeated as many times as necessary
beneath that of the plaintext message. The message is then enciphered by adding,
modulo 26, each plaintext number to one immediately beneath it. The process may be
illustrated with the keyword READY; whose numerical version is 17 04 00 03 24.
Repetitions of this sequence are arranged below the numerical plaintext of the
message

“ATTACK AT ONCE”

to produce the array

00 19 19 00 02 10 00 19 14 13 02 04

17 04 00 03 24 17 04 00 03 24 17 04

When the columns are added modulo 26, the plaintext message is encrypted as

17 23 19 03 00 01 04 19 17 11 19 08
or, converted to letters, “RXTDAB ET RLTI”.

Notice that a given letter of plaintext is represented by different letters in the

ciphertext. The double “T” in the word “ATTACK” no longer appears as a double
letter when ciphered, while the ciphertext “R” first corresponds to “A” and then to “O”
in the original message.

In general, any sequence of n letters with numerical equivalents 𝑏�1,𝑏�2,…,𝑏�𝑖�

(00≤𝑏�𝑖�≤25) will serve as the keyword. The plaintext message is expressed as
successive blocks 𝑃�1𝑃�2…𝑃�𝑛� of n two-digit integers 𝑃�𝑖�, and then converted to
ciphertext blocks 𝐶�1𝐶�2…𝐶�𝑛� by means of the congruences 𝐶�𝑖�≡𝑃�𝑖�+𝑏�𝑖� mod 26 , 1≤ i ≤
n.

Decryption is carried out by using the relations P𝑖�≡ 𝐶�𝑖� - 𝑏�𝑖� mod 26, 1≤ i ≤ n.

4. Hills’s Cipher:-

This cipher was devised in 1929 by Lester Hill, an assistant professor of

mathematics at Hunter college. Hills‟s approach is to divide the plaintext message into
blocks of n letters (possibly filling out the last block by adding “dummy” letters such
as X‟s) and then to encrypt block by block using a system of n linear congruences in n
variables. In its simplest form, when n=2, the procedure takes two successive letters
and transforms their numerical equivalents 𝑃�1𝑃�2 into a block 𝐶�1𝐶�2 of ciphertext
numbers via the pair of congruences

�����������������������������������𝐶�1≡𝑎� 𝑃�1+𝑏�𝑃�2 mod 26

𝐶�2≡𝑐� 𝑃�1+𝑑�𝑃�2 mod 26

To permit decipherment, the four coefficients 𝑎�, b, c, d must be selected so

g.c.d(𝑎�d – bc, 26)=1.

To illustrate Hills‟s cipher, let us use the congruences

𝐶�1≡2 𝑃�1+3𝑃�2 mod 26

 𝐶�2≡5 𝑃�1+8𝑃�2 mod 26

To encrypt the message “BUY NOW”. The first block “BU” of letters is
numerically equivalent to 01 20. This is replaced by

2(𝑂�1)+3(20)≡62≡ 10 mod 26
5(𝑂�1)+8(20)≡165≡ 9 mod 26

Continuing two letters at a time, we find that the completed ciphertext is: 10 09 09
16 16 12 which can be expressed alphabetically as:

“KJJ QQM”.

Decipherment requires solving the original system of congruences for 𝑃�1 and 𝑃�2
in terms of 𝐶�1 𝑎�𝑛�𝑑� 𝐶�2. The plaintext block 𝑃�1𝑃�2 can be recovered from ciphertext
block 𝐶�1𝐶�2 by means of the congruence

𝑃�1≡ 8𝐶�1 - 3𝐶�2 mod 26

𝑃�2≡ -5𝐶�1 + 2𝐶�2 mod 26

From block 10 09 of ciphertext, we calculate

𝑃�1≡ 8(10) – 3(09) ≡ 53 ≡ 01 mod 26

𝑃�2≡ -5(10) + 2(09) ≡ -32≡ 20 mod 26

Which is the same as the letter “BU”. The remaining plaintext can be restored in a
similar manner.

[Link] Cipher:-

A Vigenere type system in which either the message itself or the resulting
cryptogram is used for the “key” is called an autokey cipher. The encipherment is
started with a “priming key” (which is the entire key in our sense) and continued with
the message or cryptogram displaced by the length of the priming key as indicated
below, where the priming key is “COMET”. The message used as key:
 Message: SENDSUPPLIES…

Key: COMETSENDSUP…

Cryptogram: USZHLMTCOAYH…

The cryptogram used as key:

Message: SENDSUPPLIES…

Key: COMETUSZHLMT...

Cryptogram: USZHLOHOSTSZ…
Chapter-3

PUBLIC KEY
3.1 The idea of Public Key Cryptography:
The term “cryptosystem” is more often used to refer to a whole family of 1-to-1
enciphering transformation f from a set P of all possible plaintext message units to a
set C of all possible ciphertext message units. Each transformation corresponds to a
choice of parameters. For example, for a fixed N-letter alphabet (with numerical
equivalents also fixed once and for all), we might consider the affine cryptosystem
which for 𝑎�∈ (Z/NZ)∗and b ∈� (Z/NZ) is the map P= Z/NZ to C= Z/NZ defined by
𝐶�≡𝑎�𝑃�+𝑏�� mod 𝑁�. In this example, the sets P and C are fixed, but the enciphering
transformation f depends on the choice of parameters 𝑎�, b. The values of the
parameters are called the enciphering key 𝑘�𝐸�. In our example, 𝑘�𝐸� is the pair (𝑎�, b).

In practice, we shall suppose that the algorithm is publicly known, i.e., the
general procedure used to encipher cannot be kept secret. However, the keys can easily
be changed periodically, and if one wants, kept secret. One also needs an algorithm
and a key in order to decipher, i.e., compute 𝑓�−1. The key is called the deciphering
key 𝑘�𝐷�. In our example of the affine cryptosystem family, deciphering is also
accomplished by an affine map, namely 𝑃�≡𝑎�−1𝑐�� −𝑎�−1𝑏� mod N, and so the
deciphering transformation uses the same algorithm as the enciphering transformation,
except with a different key, namely, the pair (𝑎�−1, −𝑎�−1𝑏�).

We shall always suppose that the deciphering and enciphering algorithms are
publicly known, and that it is the keys 𝑘�𝐸� and kD which can be concealed.

By definition, a public key cryptosystem has the property that someone who
knows only how to encipher cannot use the enciphering key to find the deciphering
key without a prohibitively lengthy computation. In other words, the enciphering
function f: P⟶C is easy to compute once the enciphering key 𝑘�𝐸� is known, but it is
very hard in practice to compute the inverse function 𝑓�−1: C⟶P. That is, from the
standpoint of realistic computability, the function f is not invertible (without some
additional information- the deciphering key 𝑘�𝐷�). Such a function is called trapdoor
function. That is, a trapdoor function is a function f which is easy to compute but
whose inverse 𝑓�−1 is hard to compute without having some additional auxiliary
information beyond what is necessary to compute.

There is a closely related concept of a one-way function. This is a function f which

is easy to compute but for which 𝑓�−1 is hard to compute and cannot be made easy to
compute even by acquiring some additional information. While the notion of a
trapdoor function apparently appeared for the first time in 1978 along with the
invention of RSA public key cryptosystem, the notion of a one-way function is
somewhat older.

With a public key system, it is possible for two parties to initiate secret
communications without ever having any prior contact, without having established any
prior trust for one another, without exchanging any preliminary information. All of the
information necessary to send an enciphered message is public.

3.2 Classical versus Public key :

By a classical cryptosystem (also called a private key cryptosystem or a
symmetrical cryptosystem), we mean a cryptosystem in which, once the enciphering
information is known, the deciphering transformation can be implemented in
approximately the same order of magnitude time as the enciphering transformation.
All of the cryptosystems in Chapter 2 are classical. Occasionally, it takes a little longer
for the deciphering-because one needs to apply the Euclidean algorithm to find an
inverse modulo N or one must invert a matrix- nevertheless the additional time
required is not prohibitive. However, in a private key cipher both the encryption key
and decryption key must be kept secret from those who are not part of the
communication at hand in order to ensure cipher‟s security. Because of this
encryption/decryption keys must be generated for pairs of people each time they wish
to communicate.
In contrast, public-key cryptosystem (also known as asymmetric cryptosystem) are
developed in such a way that knowledge of the encryption key gives no information as
to what the decryption key is. One advantage of public key cryptography is that, there
is an especially easy way to identify oneself in such a way that no one could be simply
pretending to be you. Let A(Alice) and B(Bob) be two users of the system let 𝑓�𝐴� be
the enciphering transformation with which any user of the system sends a message to
Alice and let 𝑓�𝐵� the same for Bob. For simply sitting, we shall assume that the set P of
all possible plaintext message units and the set C of all possible ciphertext message
units are equal, and are the same for all users. Let P be Alice‟s “signature” (perhaps the
time the message was sent etc.). It would not be enough for Alice to send Bob the
encoded message f𝐵�(P), since everyone knows how to do that, so there would be no
way of knowing that the signature was not forged. Rather, at the beginning (or end) of
the message Alice transmits 𝑓�𝐵� 𝑓�𝐴�−1(P). Then, when Bob deciphers the whole
message, including this part, by applying 𝑓�𝐵�−1 he finds that everything has become
plaintext except for a small section of jibberish, which is 𝑓�𝐴�−1(P). since Bob knows
that the message is claimed to be from Alice, he applies 𝑓�𝐴�(which he knows, since
Alice‟s enciphering key is public) and obtains P. Since no one other than Alice could
have applied the function 𝑓�𝐴�−1 which is inverted by 𝑓�𝐴�, he knows that the message
was from Alice.

3.3 RSA:
One of the most well-known and widely used publicly cryptosystem is the RSA
cryptosystem. It is named from the last names of the inventors Rivest, Shamir, and
Adleman. The success of the so called “RSA” cryptosystem, which is one of the oldest
and most popular public key cryptosystems is based on the tremendous difficulty of
factoring.
We now describe how RSA works. Each user first chooses two extremely large
prime numbers p and q (say of about 100 decimal digits each), and sets n=pq.
Knowing the factorization of q, it is easy to compute
𝜙�(𝑛�)= (p – 1)(q – 1) = n + 1 - p - q. Next, the user randomly chooses an integer e
between 1 and 𝜙�(𝑛�) which is prime to 𝜙�(𝑛�). Whenever we say “random” we mean
that the number was chosen with the help of a random number generator, i.e., a
computer program that generates a sequence of digits in a way that no one could
duplicate or predict, and which is likely to have all of the statistical properties of a
truly random sequence. In the RSA cryptosystem, we need a random number generator
not only to choose e, but also to choose the large primes p and q.
Thus, each user A chooses two primes 𝑝�𝐴� and 𝑞�𝐴� and a random number 𝑒�𝐴� which
has no common factor with (𝑝�𝐴�– 1)(𝑞�𝐴� – 1). Next, A computes 𝑛�𝐴�= 𝑝�𝐴� 𝑞�𝐴�, 𝜙�(
𝑛�𝐴�)= 𝑛�𝐴� + 1− 𝑝�𝐴�−𝑞�𝐴�, and also the multiplicative inverse of 𝑒�𝐴� modulo 𝜙�( 𝑛�𝐴�):
𝑑�𝐴�=𝑒�𝐴�−1 mod 𝜙�( 𝑛�𝐴�). We makes public the enciphering key 𝑘�𝐸�,𝐴�= ( 𝑛�𝐴�, 𝑒�𝐴�) and
conceals the deciphering key 𝑘�𝐷�,𝐴�=( 𝑛�𝐴�, 𝑑�𝐴�). The enciphering transformation is the
map from Z/ 𝑛�𝐴�Z to itself given by f(P)≡𝑃� 𝑒�𝐴� mod 𝑛�𝐴�. The deciphering
transformation is the map from Z/ 𝑛�𝐴�Z to itself given by 𝑓�−1(𝐶�)≡𝐶� 𝑑�𝐴� mod 𝑛�𝐴�.
These two maps are inverse to one another, because of our choice of 𝑑�𝐴�.
Namely, performing f followed by 𝑓�−1 or 𝑓�−1 followed by f means raising to the
𝑑�𝐴�𝑒�𝑎�th power. But because 𝑑�𝐴�𝑒�𝑎� leaves a reminder of 1 when divided by 𝜙�( 𝑛�𝐴�),
this is the same as raising to the 1-st power.
In practice, we would probably want to choose P and C uniformly throughout the
system. For example, suppose we are working in an N-letter alphabet. Then let k<𝑙� be
suitably chosen positive integers such that for example, 𝑁�𝑘� and 𝑁�𝑙� have
approximately 200 decimal digits. We take as our plaintext message units all blocks of
k-letters, which we regard as k- digit base N- integers, i.e., we assign them numerical
equivalents between 0 and 𝑁�𝑘� . We similarly take ciphertext message units to be
blocks of l-letters in our N-letter alphabet. Then each user must choose his/her large
primes 𝑝�𝐴� and 𝑞�𝐴� so that 𝑛�𝐴�= 𝑝�𝐴� 𝑞�𝐴� satisfies 𝑁�𝑘�< 𝑛�𝐴�<𝑁�𝑙�.Then any plaintext
message unit, i.e., integer less than 𝑁�𝑘�,corresponds to an element in Z/ 𝑛�𝐴�Z and since
𝑛�𝐴�<𝑁�𝑙�, the image f(P) ∈ Z/ 𝑛�𝐴�Z can be uniquely written as an l-letter block.
Example: For the benefit of simplicity in computation, we shall sacrifice realism and
choose most of our examples so as to involve relatively small integers. Choose N=26,
k= 3, l= 4. That is, the plaintext consists of trigraphs and the ciphertext consists of four
graphs in the usual 26-letter alphabet. To send the message “YES” to a user A with the
enciphering key
(𝑛�𝐴�, 𝑒�𝐴�)=(46927, 39423), we first find the numerical equivalent of “YES”, namely:
24.262+4.26+18=16346, and then compute 1634639423 mod 46927, which is
21166=1. 263+5. 262+8.26+2= “BFIC”. The recipient A knows the deciphering key,
(𝑛�𝐴�, 𝑑�𝐴�) = (46927,26767), and so computes 2116626767 mod 46927=16346= “YES”.
Let us see how use A generate her keys. First, she multiplied the primes 𝑝�𝐴�=281
and 𝑞�𝐴�=167 to get 𝑛�𝐴�; then she chose 𝑒�𝐴� at random [but subject to the condition that
g.c.d(𝑒�𝐴�, 280) = g.c.d(𝑒�𝐴�, 166)=1.
Then she found 𝑑�𝐴�=𝑒�𝐴�−1 mod 280.166. The numbers 𝑝�𝐴�, 𝑞�𝐴� and 𝑑�𝐴� remain secret.
Clearly, the most time-consuming step is modular exponentiation, eg. 16346 39423
mod 46927. But this can be done by repeated squaring method.
Example: Suppose that a message is to be sent to an individual whose listed public
key is (2701,47). The key was arrived at by selecting the two primes p=37 and q=73,
which in turn led to the enciphering modulus n=37.73=2701 and 𝜙� (𝑛�)=36.72=2592.
Because g.c.d(47,2592)=1, the integer k=47 was taken as the enciphering exponent.
The message to be encrypted and forwarded is “NO WAY TODAY”. It is first
translated into a digital equivalent using the previously indicated letter substitutions,
M=13 14 26 22 00 24 26 19 14 3 00 24.
This plaintext number is thereafter expressed as four-digit blocks: 1314 2622 0024
2619 1403 0024. The corresponding ciphertext numbers are obtained by raising each
block to the 47th power and reducing the results modulo 2701. In the first block,
repeated squaring produces the value 131447≡1241 mod 2701. The completed
encryption of the message is the list 1241 1848 0873 1614 2081 0873.
For the deciphering operation, the recipient employs the Euclidean algorithm to
obtain the equation 47.1103+2592(-20)=1, which is equivalent to 47.1103≡1 mod
2592. Hence, j=1103 is the recovery exponent. It follows that 1241 1103≡1314 mod
2701 and so on.
Remarks
1. In choosing p and q, user A should take care to see that certain conditions hold. The
most important are: that the two primes not be too close together, and p-1 and q-1 have
a fairly small g.c.d and both have at least one large prime factor.
2. While discussing authentication in a previous section, we assumed for simplicity
P=C. We have slightly more complicated set-up in RSA. Here is one way to avoid the
problem of different 𝑛�𝐴�‟s and different block sizes (k, the number of letters in a
plaintext message unit, being less than l, the number of letters in a ciphertext message
unit). Suppose that, Alice is sending her signature to Bob. She knows Bob‟s
enciphering key 𝑘�𝐸�,𝐵�=( 𝑛�𝐵�, 𝑒�𝐵�) and her own deciphering key 𝑘�𝐷�,𝐴�=( 𝑛�𝐴�, 𝑒�𝐴�). What
she does is send 𝑓�𝐵� 𝑓�𝐴�−1(P) is 𝑛�𝐴�< 𝑛�𝐵� or else 𝑓�𝐴�−1 𝑓�𝐵�(P) if 𝑛�𝐴�> 𝑛�𝐵�. That is, in the
former case she takes the least positive residue of P 𝑑𝐴 modulo 𝑛�𝐴� then regarding that
number modulo 𝑛�𝐵�, she computes 𝑃𝑒𝐴 modulo 𝑛�𝐵� and then, working modulo 𝑛�𝐴�,
she raises this to the 𝑑�𝐴�-th power. Clearly, Bob can verify the authenticity of the
message in the first case by raising to the 𝑑�𝐵�-th power mod 𝑛�𝐵� and then to the 𝑒�𝐴�-th
power mod 𝑛�𝐴�; in the second case he does the operation in the reverse order.
Chapter-4

APPLICATIONS
4.1 Cryptography in Everyday Life

Cryptography has been used in our daily life. Cryptography plays an

important role in each time when we make an online purchase, making an online
transaction, sending an email withdrawing money from ATM and so on. Cryptography
secures all the information that we transmit through the internet. Cryptographic
techniques like digital signature protects our information from forgeries and
fraudulent. It ensures authentication of identity, prevent document tampering and
establishes the trust between servers. Most of the communication platforms have been
encrypted. Social media like WhatsApp, Instagram, and Telegram has made use of the
idea of encryption for transmitting the messages and keeping it secure. Cryptography
also helps in encrypting company devices, protecting sensitive data, encrypting
databases and securing a website. Https or Secure Hypertext Transfer Protocol is used
for securing website.

4.1 Cryptography and ATM:

Authorized cardholders can withdraw cash and carry out other financial
operations at an ATM without having to go to a bank branch because to the convenient
and secure service it offers. A secure communications network, also known as
encryption, is used by banks to authorize each ATM transaction. This network encrypts
data so that only the sender and the intended recipient can decipher it.
4.1.1. Deficiency in Securities :
One typical ATM security flaw includes so-called phantom withdrawals, in
which money is withdrawn from a cardholder's account but neither the client nor the
bank acknowledges responsibility. Phantom withdrawals can occasionally be the
consequence of dishonest behavior on the part of the consumer, but ATMs can also be
made to accept phony, skimmed, or copied cards. Card issuers utilize an authorization
Request Cryptogram, a coded message generated by ATMs, to authenticate the card
and card data.
4.1.2 Data Encryption Standard (DES):
ATMs were the first to encrypt personal identifying numbers using a
mathematical formula or algorithm. The 56-bit encryption key used by DES to encrypt
data in 64-bit blocks was once an established Federal Information Processing Standard
in the United States. However, as personal computer processing power has increased,
DES has become less secure for ATM applications; ATMs utilizing DES have been
com-promised in less than a day.

Triple DES:- With Triple DES, the encryption key is essentially extended to 168 bits
by using two keys and three applications of the DES encryption method. Because it is
not practical to search the individual bits of the encryption key to crack the code,
Triple DES is much more secure than DES. Since 2002, triple DES encryption has
been required, according to the National Credit Union Administration, for all new
ATM installations.
4.1.3 Advanced Encryption Standard (AES):
The Advanced Encryption Standard, which was meant to replace DES, was
adopted in 2001, according to an announcement made by the National Institute of
Standards and Technology. Data is encrypted by AES using 128-bit blocks and a
variable-length encryption key with a length of 128, 192, or 256 bits. AES is
substantially more secure than DES or triples DES since the only way for an
unauthorized individual to decrypt data encrypted with it is by a method known as a
"brute force attack," which tests all possible combinations of the encryption key. The
commercial standard for encrypting sensitive digital information, such as the financial
data utilized by ATMs, was certified by the US government as the AES standard in
2003.
4.1.4. Electronic Money:

The definition of electronic money (also called electronic cash or digital cash) is
a term that is still evolving. It includes transactions carried out electronically with a
net transfer of funds from one party to another, which may be either debit or credit and
can be either anonymous or identified. Encryption is used in electronic money
schemes to protect conventional transaction data like account numbers and transaction
amounts, digital signature or a credit card authorization and public –key encryption
can provide confidentiality.
4.2 Cryptography and Email:
Email encryption is a method of authentication that stops messages from being
read by an unauthorized or unintended person. The original communication is
scrambled and put into an unintelligible or unreadable format. When sending sensitive
material over email, encryption is required.
In order to commit crimes like identity theft and fraud, hackers tar-get victims via
email and steal data, including personal information like names, addresses, and login
credentials. Additionally, while the majority of sent emails are encrypted during
transmission, the data is retained in clear text, allowing email providers to access the
content. End-to-end encryption is often not offered by well-known free email services,
making it simple for hackers to intercept delivered messages. Public-key cryptography
and digital signature technologies are used by email encryption solutions to encrypt
email messages. By following this procedure, you may be sure that only the intended
recipient will be able to open your emails.
You can encrypt emails when transmitting important information in them. When
text is encrypted for email, it is transformed from plain text to scrambled cipher text.
Only the receiver has access to the private key and this key will be used to decode the
email which enable to view it.
4.2.1 Pretty Good Privacy (PGP):
Using digital signatures and file encryption methods, the security tool PGP
encrypts and decrypts email messages. One of the first publicly accessible, free public-
key cryptography programs, the software was first made available in 1991. PGP is
currently widely used to safe-guard people and organizations, offering cryptographic
authentication and privacy to secure internet communication including email and text
messaging.
PGP encrypts data in motion by utilizing a variety of hashing algorithms, data
compression, symmetric and asymmetric key technology, and cryptography. It
provides a viewpoint on the public key infrastructure (PKI) strategy as well. When a
user sends a message using their public key, PGP encrypts the data and decrypts it
when the recipient unlocks it using their private key. In addition to using S/MIME and
TLS to encrypt email, you can also take advantage of encrypted PDFs and web portal
encryption.
4.2.2 Encrypted PDF:
You can offer consumers protected documents and attachments that they can
download to their computers using an encrypted PDF, zip, or Office file. Anyone
attempting to intercept and use the information in the email would only receive a
random collection of characters as a result. This indicates that all attachments and
documents are readable on all devices and arrive to their destinations unharmed. The
user can access the attachment later even while they are offline because they
downloaded it.
There are various types of email encryption, but some of the most common encryption
protocols are:

Open PGP - a type PGP encryption that utilizes a decentralized, distributed trust model
and integrates well with modern web email clients.

S/MIME – a type of encryption that is built into most apple devices and utilizes a
centralized authority to pick the encryption algorithm and key size.

4.2.3 Web Portal Encryption

To read an email that has been encrypted via a web gateway, the recipient must
visit a web page. Because the email is protected by a shared key before it is sent to the
web portal, this satisfies the definition of email encryption. The user's email
programme, such as Outlook, Mail-bird, etc., sends the encrypted email directly to the
web site. This prevents anyone without the website's login information from reading
the email. By reducing the amount of persons who have access to your company's
emails, this type of secure email encryption solution reduces your attack surface. Web
portal encryption is a reliable means to stop hackers from accessing critical
information sent over the internet, provided that the recipient's password is safe.

4.3 Authentication/Digital Signatures:

Authentication is any process through which one proves and verifies certain
information. Sometimes one may want to verify the origin of a document, the identity
of the sender, the time and date a document was sent and/or signed, the identity of a
computer or user, and so on. A digital signature is a cryptographic means through
which many of these may be verified. The digital signature of a document is a piece of
information based on both the document and the signer‟s private key. It is typically
created through the use of a hash function and a private signing function (algorithms
that create encrypted characters containing specific information about a document and
its private keys).

4.3.1 Importance of Digital Signature:

Digital signature is very important tool in cryptography.
Message authentication- The private key is sent to the sender. The public key can use
by the verifier of the sender to validate that the Digital signature was created by the
sender.
Data Integrity- If the data is attacked, there will be a discrepancy in the hash value and
won't match with the verification, Algorithm. Due to this, reject the message by the
receiver and declaring a data breach.
Non-repudiation- The signature key is only known to the signer so, naturally they are
the only one who can create a specific signature. On any occasion there is a dispute,
the data along with the Digital signature can be presented as evidence.

4.4 Other Applications:

4.4.1 HTTPS:
Hypertext Transfer Protocol Secure or https helps to set the information free on
a web. It is an everyday application of cryptography. It is a primary protocol which is
used to send data between a browser and a website. It is important to be encrypted as
uses transmit sensitive data such as details of bank account, email service and so on. A
website which requires login credential should use https. A browser which does not
use https is flagged as non-secure.
4.4.2 CRYPTOCURRENCY:
Cryptocurrency uses three different cryptographic methods for encryption.
Symmetric Encryption asymmetric Encryption and hashing has been used in Crypto
currencies. The Bitcoin network uses has function to ensure the security of blockchain
and immutability of the trans-mission. Cryptocurrencies use cryptography which make
the transactions anonymous secure and trustless. The identity of the person is not
needed for the transaction. Details of bank, Credit Card Company are not collected for
the transaction.

4.4.3 Time Stamping:

Time stamping is a technique that can certify that a certain electronic document
or communication existed or was delivered at a certain time. Time stamping uses an
encryption model called a blind signature scheme. Blind signature schemes allow the
sender to get a message receipted by another party without revealing any information
about the message to the other party. Possible applications include patent applications
copyright archives and contracts. Time stamping is a critical application that will help
make the transition to electronic legal documents possible.

4.4.4 Encryption in WhatsApp:

WhatsApp uses the „signal‟ protocol for encryption, which uses a combination of
asymmetric and symmetric key cryptographic algorithms. The symmetric key
algorithms ensure confidentiality and integrity whereas the asymmetric key algorithms
help in achieving the other security goals namely authentication and non-repudiation

Conclusion :
Cryptography and network security are the key technologies to ensure the security
of the information system. As we advance towards a society where automated
information resources are increased, cryptography will continue to rise in importance
as a security mechanism. In this project, we have aimed to identify some of the
mathematical concepts from elementary number theory behind classical and public
key cryptosystems. In the case of RSA, despite years of attempts, no one has been
known to crack the algorithm. Such a resistance to attack makes RSA secure in
practice. Hence RSA is a strong encryption algorithm that has stood a partial test of
time. Undoubtedly, such more sophisticated algorithm than RSA will continue to be
developed as mathematicians discover in more in the fields of number theory and
cryptanalysis.
REFERENCES
1. Neal Koblitz. A course in Number Theory and Cryptography. 2nd edition, Springer.
2. David M. Burton. Elementary Number Theory. 7th edition, McGraw-Hill.

3. C.E. Shannon, “Communication Theory of Secrecy Systems”, appeared in the report

“A Mathematical Theory of Cryptography” dated Sept. 1, 1946.

4. World Wide Web