LORDS Institute of Engineering and Technology

(Autonomous), Hyderabad, Telangana, INDIA.

Approved by AICTE, affiliated to OSMANIA UNIVERSITY /Estd.2002.

Accredited by NAAC with ‘A’ grade & Accredited by NBA.

CRYPTOGRAPHY AND
NETWORK SECURITY (CNS)

Course Code: PC 604 CS

III B. Tech VI Semester – OU BE (CSE)

Subject Coordinator:
Dr Sunil VK Gaddam
Professor of CSE &
DEAN – CSE and Allied Departments

Page 1 of 52
 COURSE OBJECTIVES & COURSE OUTCOMES
CONTENTS

Course Objectives:
 Understand security concepts, Ethics in Network Security
 Obtain knowledge on mechanisms to encounter threats
 Appreciate and apply relevant cryptographic techniques
 Comprehend computer network access control and ethics in network security

Course Outcomes: At the end of the course the students will be able to –
 Develop familiarity with cryptography and security techniques
 Master fundamentals of secret and public cryptography
 Utilize the master protocols for security services
 Identify network security threats and counter-measures
 Propose network security designs using available secure solutions

UNIT-1: BASIC PRINCIPLES:

1. Security Goals,
2. Cryptographic Attacks,
3. Services and Mechanisms,
4. Mathematics of Cryptography.

UNIT- 2: SYMMETRIC ENCRYPTION

1. Mathematics of Symmetric Key Cryptography
2. Introduction to Modern Symmetric Key Ciphers
3. Data Encryption standard (DES)
4. Advanced Encryption Standard (AES)

UNIT- 3: ASYMMETRIC ENCRYPTION

1. Mathematics of Asymmetric Key Cryptography
2. Asymmetric Key Cryptography

Page 2 of 52
UNIT- 4: DATA INTEGRITY, DIGITAL SIGNATURE SCHEMES & KEY MANAGEMENT
1. Message Integrity and Message Authentication
2. Cryptographic Hash Functions
3. Digital Signatures
4. Key Management

UNIT-5: NETWORK SECURITY

1. Security at Application Layer (PGP and S/MIME)
2. Security at Transport Layer (SSL and TLS)
3. Security at Network Layer (IPSec, System Security)

UNIT – 1
Basic Principles

 Introduction
 First, it is essential to know:
– What we are trying to protect?
– What are the various dangers when we use computers, computer networks and
internet?
– What can happen if we do not set up the right security policies, framework and
technology implementations?
 This Unit will provide answers to these basic questions.
– Computer data often travels from one computer to another, leaving the safety of its
protected physical surroundings.
– Once the data is out of hand, people with bad intention could modify or forge your
data, either for amusement or for their own benefit.
– Cryptography can reformat and transform our data, making it safer on its trip
between computers.
– The technology is based on the essentials of secret codes, augmented by modern
mathematics that protects our data in powerful ways.
– Computer Security - generic name for the collection of tools designed to protect data
and to thwart (prevent) hackers.
– Network Security - measures to protect data during their transmission.
– Internet Security - measures to protect data during their transmission over a
Page 3 of 52
 collection of interconnected networks.
 In Network Security and Cryptography, we mainly focus on two broad areas:
1. Cryptographic algorithms and protocols, which have a broad range of applications
2. Network and Internet security, which rely heavily on cryptographic techniques.
 Computer Security
– The protection afforded to an automated information system in order to attain the
applicable objectives of preserving the Confidentiality, Integrity and Availability of
information system resources (includes hardware, software, firmware, information
/data, and telecommunications) NIST 1995 (National Institute of Standards &
Technology)

1. Basic Principles: Security Goals

 Key Security Objectives/ Goals (The CIA triad)

 Confidentiality
– The principle of confidentiality specifies that only the sender and the intended
recipients should be able to access the contents of a message.
– No other person is allowed to access the content.
– Interception causes loss of message confidentiality.
 Integrity
– The assurance that data received are exactly same as sent by an authorized entity (i.e.
without any modification, insertion, deletion or replay).
– When the contents of a message are changed after sender sends it, but before it reaches
the intended recipient, we say that integrity is lost.
– Modification causes loss of message integrity.
 Availability
– States that resources (i.e. information) should be available to authorized parties at
all time.
– Interruption puts the availability of resources in danger.

Page 4 of 52
 Security Objectives/ Goals: CIA Triad and Beyond

 Levels of impact of security attack

– Low: The loss will have a limited impact, e.g., a degradation in mission or minor
damage or minor financial loss or minor harm.
– Moderate: The loss has a serious effect, e.g., significance degradation on mission or
significant harm to individuals but no loss of life or threatening injuries.
– High: The loss has severe or catastrophic adverse effect on operations,
organizational assets or on individuals (e.g., loss of life).
 Challenges of Computer Security
1. Computer security is not simple
2. One must consider potential (unexpected) attacks
3. Procedures used are often counter-intuitive
4. Must decide where to deploy mechanisms
5. Involve algorithms and secret info (keys)
6. A battle of intellects between attacker / admin
7. Current security technologies and best practices are not effective
8. Requires constant monitoring
9. Too often an after-thought (not integral)
10. DDoS attacks have increasingly popular with attackers
 The OSI Security Architecture
– To assess the security needs of an organization effectively, the manager responsible for
security needs some systematic way of defining the requirements for security and
characterization of approaches to satisfy those requirements.
Page 5 of 52
 – The OSI security architecture focuses on security attacks, mechanisms, and services.
 The OSI Security Architecture
– OSI Security Architecture focuses on these concepts.
– Security Attack.
– Security mechanism: A security mechanism is a means of protecting a system, network,
or device against unauthorized access, tampering, or other security threats.
– Security Service.

Figure: Classification of OSI Security Architecture

– Security attack – Any action that compromises the security of information owned by
an organization.
– Security mechanism – A mechanism that is designed to detect, prevent or recover
from a security attack.
– Security service – A service that enhances the security of the data processing
systems and the information transfers of an organization. The services are intended to
counter security attacks and they make use of one or more security mechanisms to
provide the service.
 Threats and Attacks (RFC 2828)
– Threat: A potential for violation of security, which exists when there is a circumstance,
capability, action, or event that could breach (crack) security and cause harm. That is, a
threat is a possible danger that might exploit a vulnerability.
– Attack: An assault on system security that derives from an intelligent threat; that is, an
intelligent act that is a deliberate attempt (especially in the sense of a method or
technique) to evade security services and violate the security policy of a system.

Page 6 of 52
2. Basic Principles: Security Attacks
 Security Attacks
– Security Attacks: Three goals of security – confidentiality, integrity and availability –
can be threatened by security attacks.
– Security attacks can be classified in terms of Passive attacks and Active attacks as
per X.800 and RFC 2828
– X.800  ITU-T recommendation for OSI security architecture
– ITU-T  International Telecommunication Union – Telecommunication
– RFC 2828 Internet Security Glossary (dictionary)

 Taxonomy of Attacks with relation to Security Goals

 Attacks threatening Confidentiality

– Snooping refers to unauthorized access to or interception of data.
– Traffic Analysis refers to obtaining some other type of information by monitoring
online traffic.
 Attacks threatening Integrity
– Modification means that the attacker intercepts the message and changes it.
– Masquerading or Spoofing happens when the attacker impersonates somebody else.
– Replaying means the attacker obtains a copy of a message sent by a user and later
tries to replay it.
– Repudiation means that the sender of the message might later deny that he/she has
sent the message; the receiver of the message might later deny that he/she has
received the message.

Page 7 of 52
 Attacks threatening Availability
– Denial of Service (DoS) is a very common attack. It may slow down or totally interrupt
the service of s system.
 Categorization of Passive & Active Attacks

 Active Attacks Vs Passive Attacks

Active Attacks Passive Attacks
Active attacks involve some modification of the Passive attacks do not involve any
data stream or the creation of a false stream. alteration of the data.
Active attacks are very easy to detect Passive attacks are very difficult to detect

Ex: Masquerade, Ex: The release of message contents

Replay, Traffic Analysis
Modification of messages, and
Denial of service.
In active attack emphasis is on detection. Emphasis in dealing with passive attacks
is on prevention rather than detection.
Active Attack is danger for Integrity as well as Passive Attack is danger for
availability. Confidentiality.
Due to active attack, system is always damaged. Due to passive attack, there is no harm to
the system.

 Classification of Attacks
– A passive attack attempts to learn or make use of information from the system but
does not affect system resources.
– An active attack attempts to alter system resources or affect their operation.

 Active Attacks
– Active attacks involve some modification of the data stream or the creation of a
false stream and can be subdivided into four categories:
1. Modification (of messages)
2. Masquerading (or Spoofing)
3. Replaying
4. Repudiation
5. Denial of service
Page 8 of 52
 Modification (of messages)
– Modification of messages simply means that some portion of a legitimate message is
altered, or that messages are delayed or reordered, to produce an unauthorized
effect.
– For example, a message meaning “Allow John Smith to read confidential file
accounts” is modified to mean “Allow Fred Brown to read confidential file accounts”.

 Masquerading/ Spoofing
– A Masquerade takes place when one entity pretends to be a different entity.
– Give a different appearance in order to conceal one’s identity.

Page 9 of 52
 Replaying
– Replay involves the passive capture of a data unit and its subsequent retransmission
to produce an unauthorized effect.

 Repudiation
– Repudiation defined as one party participating in a transaction or communication,
and later claiming that the transaction or communication never took place.
– This type of attack is different from others because it is performed by one of the two
rties in the communication: either sender or receiver.

Figure: Non-Repudiation of Origin and Non-Repudiation of Emission for Banks

Page 10 of 52
  Denial of Service (DoS)
– The denial of service prevents or inhibits the normal use or management of
communication facilities.
– This attack may have a specific target; for example, an entity may suppress all
messages directed to a particular destination (e.g., the security audit service).
– Another form of service denial is the disruption of an entire network, either by
disabling the network or by overloading it with messages so as to degrade
performance.

 Passive Attacks
– Passive attacks are in the nature of eavesdropping on, or monitoring of, transmissions.
– The goal of the opponent is to obtain information that is being transmitted.
– Two types of passive attacks are:
1. Snooping/ The release of message contents and
2. Traffic analysis.
 Snooping/ The release of message contents
– Snooping refers to unauthorized access to or interception of data.
– The release of message contents is easily understood.
– A telephone conversation, an electronic mail message, and a transferred file may
contain sensitive or confidential information.
– We would like to prevent an opponent from learning the contents of these
transmissions.

Page 11 of 52
  Traffic Analysis
– A second type of passive attack, traffic analysis, is indirect.
– Suppose that we had a way of masking the contents of messages or other information
traffic so that opponents, even if they captured the message, could not extract the
information from the message.
– The common technique for masking contents is encryption.

 Different Kinds of Attacks

1. Interruption
2. Interception
3. Modification
4. Fabrication
Page 12 of 52
 Interruption
– An Asset of the system is destroyed or becomes unavailable or unusable.
– It is an attack on availability.

Examples:
1. Destruction of some hardware
2. Jamming wireless signal
3. Disabling file management system
 Interception
– An Unauthorized party gains access to an asset.
– It is an attack on confidentiality.

Examples:
1. Wiretapping to capture data in a network
2. Illegal copying of data or programs
3. Eavesdropping (Secret listening to private conversation)
 Modification
– An unauthorized party gains access and tampers an asset.
– Attack is on Integrity.

Page 13 of 52
 Examples:
1. Changing data file
2. Altering a program and the contents of a message
 Fabrication
– An unauthorized party inserts a counterfeit object into the system. Also called
impersonation.
– Attack on Authenticity.

Examples:
1. Hackers gaining access to a personal email and sending message.
2. Insertion of records in data files
3. Insertion of spurious messages in a network
 Different Kinds of Attacks

Page 14 of 52
  Handling Attacks
– Passive attacks – focus on Prevention
1. Easy to stop
2. Hard to detect
– Active attacks – focus on Detection and Recovery
1. Hard to stop
2. Easy to detect

 Summary of Attacks

Attack Category Attack on Service

Interruption Active Availability

Interception Passive Confidentiality

Modification Active Integrity

Fabrication Active Authentication

3. Basic Principles: Security Services & Mechanisms

 Security Services (X.800)
– The International Telecommunication Union – Telecommunication (ITU-T)
Standardization Sector (X.800) has defined five services related to the security Goals
and Attacks, which we have discussed earlier.

– Data Confidentiality – protection of data from unauthorized disclosure

– Data Integrity - assurance that data received is as sent by an authorized entity
Page 15 of 52
– Authentication - assurance that communicating entity is the one claimed
 have both peer-entity & data origin authentication
– Access Control - prevention of the unauthorized use of a resource
– Non-Repudiation - protection against denial by one of the parties in a communication
– Availability – resource accessible/usable
 Data Confidentiality
– The protection of transmitted data from passive attacks
 Broadest service protects all user data transmitted between two users over a
period of time
 Narrower forms of service include the protection of a single message or even
specific fields within a message
– The protection of traffic flow from analysis
 This requires that an attacker not be able to observe the source and destination,
frequency, length, or other characteristics of the traffic on a communications
facility
 Data Integrity
– Can apply to a stream of messages, a single message, or selected fields within a
message
– Connection-oriented integrity service, one that deals with a stream of messages,
assures that messages are received as sent with no duplication, insertion, modification,
reordering, or replays
– A connectionless integrity service, one that deals with individual messages without
regard to any larger context, generally provides protection against message
modification only
 Authentication
– Concerned with assuring that a communication is authentic
 In the case of a single message, assures the recipient that the message is from
the source that it claims to be from
 In the case of ongoing interaction, assures the two entities are authentic and
that the connection is not interfered with in such a way that a third party can
masquerade as one of the two legitimate parties
– Two specific authentication services are defined in X.800:
 Peer entity authentication
 Data origin authentication
 Non-repudiation
– Prevents either sender or receiver from denying a transmitted message
– When a message is sent, the receiver can prove that the alleged sender in fact sent the
message

Page 16 of 52
 – When a message is received, the sender can prove that the alleged receiver in fact
received the message
 Access Control
– The ability to limit and control the access to host systems and applications via
communications links
– To achieve this, each entity trying to gain access must first be identified, or
authenticated, so that access rights can be tailored to the individual

 Security Mechanisms
– As known as control
– Feature designed to detect, prevent, or recover from a security attack
– No single mechanism that will support all services required
– However, one particular element underlies many of the security mechanisms in use:
 cryptographic techniques

 Security Mechanisms (X.800)

– The International Telecommunication Union – Telecommunication (ITU-T)
Standardization Sector (X.800) has also recommended some Security Mechanisms to
provide the security services defined in earlier section.
 Specific security mechanisms:
– Encipherment
– Data integrity
– Digital signatures
– Authentication exchange
– Traffic padding
– Routing control
– Notarization
– Access controls
 Pervasive security mechanisms:
– Trusted functionality
– Security labels
– Event detection
– Security audit trails
– Security recovery

Page 17 of 52
 Specific security mechanisms
– Encipherment - Involve mathematical algorithms to transform the original message
into unreadable format.
– Data integrity – To assure the integrity of the data unit
– Digital signatures – Data appended to, or a cryptographic transformation of a data
unit to prove the source and integrity of the data unit and protect against forgery.
– Authentication exchange - To ensure the identity of an entity by means of
information exchange.
– Traffic padding - Insertion of bits into gaps in a data stream to frustrate traffic
analysis attempts.
– Routing control – Secure routes for certain data and allows route changes, especially
when a breach of security is suspected.
– Notarization – Use of trusted third party to assure certain properties of a data
exchange.
– Access controls – Access rights to resources.
 Pervasive security mechanisms
– Trusted functionality - That which is perceived to be correct with respect to some
criteria as established by security policy.
– Security labels – Holograms, Barcodes, QR codes
– Event detection – Detection of security relevant events
– Security audit trails – An independent review and examination of system records and
activities.
– Security recovery – Recovery actions

Page 18 of 52
 Techniques
– The mechanisms we have discussed are only theoretical recipes to implement security.
– The actual implementation of security goals needs some techniques.
– Two techniques are prevalent today: one is very general (Cryptography), and the other
one is specific (Steganography).
o Cryptography (general)
o Steganography (specific)

 Cryptography
– Cryptography (Greek origin) means “Secret Writing”.
– It means the art of transforming the messages to make them secure and immune to
attacks.
– It involves both Encryption and Decryption of messages using secret keys.
– There are three distinct mechanisms involved:
o Symmetric-key encipherment
o Asymmetric-key encipherment
o Hashing

Page 19 of 52
 A Model for Network Security
– A message is to be transferred from one party to another across some sort of internet.
– The two parties must cooperate for the exchange to take place.
– A logical information channel is established by defining a route through the internet
from source to destination.
– Security aspects come into play when it is necessary to protect the information
transmission from an opponent who may present a threat to confidentiality and
integrity.
– A trusted third party may be needed to achieve secure transmission.
– A third party may be responsible for distributing the secret information to the two
principals.
– A third party may be needed to resolve disputes between the two principals
concerning the authenticity of message transmission.

Figure: Network Security Model

 Using this model requires us to:
1. Design a suitable algorithm for the security transformation
2. Generate the secret information (keys) used by the algorithm
3. Develop methods to distribute and share the secret information
4. Specify a protocol enabling the principals to use the transformation and secret
information for a security service

Page 20 of 52
 Symmetric Key Encipherment

 Symmetric-key encipherment (sometimes it is also called as secret-key encipherment

or secret-key cryptography or private-key encryption).
 The steps involved in the Symmetric-key encipherment as follows:
1. An entity (Alice) can send a message to another entity (Bob) over an insecure
channel with an assumption that an adversary (Eve) can not understand the
contents of the message by simply eavesdropping over the channel.
2. Alice encrypts the message using an encryption algorithm.
3. Bob decrypts the message using a decryption algorithm.
4. Symmetric-key encipherment uses as single secret-key for both encryption and
decryption.
5. Encryption/ decryption can be thought of as an electronic locking.
6. In symmetric-key enciphering Alice puts the message in a box and locks the box
using the shared secret key.
7. Bob unlocks the box with the same key and takes out the message.

 Asymmetric Key Encipherment

 Asymmetric-key encipherment (sometimes it is also called as public-key
encipherment or public-key cryptography or public-key encryption).
 In an Asymmetric encipherment also, we have the same situation as the symmetric-key
encipherment, with a few exceptions:
1. There are two keys instead of one: Public key and Private key
2. To send a secured message to Bob, Alice first encrypts the message using Bob’s
public key.
3. To decrypts the message, Bos uses his own private key.
– The following figure shows an Asymmetric-key encipherment.
Page 21 of 52
 Asymmetric Key Encipherment

 Hashing

Page 22 of 52
  In hashing, a fixed-length message digest is created out of a variable-length message.
 The digest is normally mush smaller than the message.
 To be useful, both the message and the digest must be sent to Bob.
 Hashing is used to provide check values which will be used in relation to provide data
integrity.
 Steganography
– Steganography (Greek origin) means “Covered Writing”.
– Cryptography means concealing the contents of a message by enciphering.
– Whereas, Steganography means concealing the message itself by covering it with
something else.
– Steganography is the technique of hiding secret data within an ordinary, non-secret,
file or message in order to avoid detection; the secret data is then extracted at its
destination.
– Steganography can be used to conceal almost any type of digital content, including text,
image, video or audio content; the data to be hidden can be hidden inside almost any
other type of digital content.
– The use of steganography can be combined with encryption as an extra step for hiding
or protecting data.

 Different Types of Steganography

 From a digital perspective, there are five main types of steganography. These are:
1. Text steganography
2. Image steganography
3. Audio steganography
4. Video steganography
5. Network steganography

Page 23 of 52
  Text steganography
– Text steganography involves hiding information inside text files. This includes
changing the format of existing text, changing words within a text, using context-free
grammars to generate readable texts, or generating random character sequences.
 Image steganography
– This involves hiding information within image files. In digital steganography, images
are often used to conceal information because there are a large number of elements
within the digital representation of an image, and there are various ways to hide
information inside an image.
 Audio steganography
– Audio steganography involves secret messages being embedded into an audio signal
which alters the binary sequence of the corresponding audio file. Hiding secret
messages in digital sound is a more difficult process compared to others.
 Video steganography
– This is where data is concealed within digital video formats. Video steganography
allows large amounts of data to be hidden within a moving stream of images and
sounds. Two types of video steganography are:
 Embedding data in uncompressed raw video and then compressing it later
 Embedding data directly into the compressed data stream
 Network steganography
– Network steganography, sometimes known as protocol steganography, is the
technique of embedding information within network control protocols used in data
transmission such TCP, UDP, ICMP, etc.

 Steganography vs. Cryptography

Factors Steganography Cryptography

It's a method to conceal the It's a method for making
Explanation
fact that communication is information unintelligible
taking place
Maintain communication Enable data protection
Aim
security
Optional, but increases Necessary prerequisite
Key
security when utilized
No Yes
Data Visibility
Once hidden information is You can recover the original
Failure
decoded, the data can be message from the ciphertext
used by anyone if you can access the
decryption key
Does not modify the data's Modifies the overall data
Data Structure
general structure structure

Page 24 of 52
 – Steganography and cryptography share the same goal – which is to protect a message
or information from third parties – but they use different mechanisms to achieve it.
– It's fair to say that steganography and cryptography aim to shield messages and data
from prying eyes at their most fundamental level. However, they employ an alternative
means of security.
– Information is converted into unintelligible ciphertext in cryptography. Someone
intercepting this message could tell immediately that encryption was used. In contrast,
steganography hides a message without altering its original format.

 A Model for Network Access Security

Figure: Network Access Security Model

 To protect information system from:
1. Unwanted access
2. Information access threats
3. Service threats

 Model for Network Access Security

 Using this model requires us to implement:
1. Authentication
– select appropriate gatekeeper functions to identify users
2. Authorization
– implement security controls to ensure only authorized users access designated
information or resources
 Trusted computer systems may be useful to help implement this model

 Hacker Vs Intruder
 Hacker: Who attempt to penetrate systems that can be accessed over a network.
– The hacker can be someone who, with no malign intent, simply gets satisfaction from
breaking and entering a computer.
 Intruder: A person attempts to violate security by interfering with system availability,
data integrity and confidentiality.

Page 25 of 52
 – The intruder can be a dissatisfied employee who wishes to do damage, or a criminal
who seeks to exploit computer assets for financial gain.

 Virus & Worm

 The Worm use computer networks to spread itself while viruses spread to different
systems through executables files.
 The Virus needs human action to replicate whereas worm don’t.
 Spreading speed of worm is faster than virus.

 Unwanted Access
 Placement in a computer system of logic that exploits vulnerabilities in the system and
that can affect application programs as well as utility programs such as editors and
compilers.
 Programs can present two kinds of threats:
 Information access threats
– Intercept or modify data on behalf of users who should not have access to that
data
 Service threats
– Exploit service flaws in computers to inhibit use by legitimate users

 Applications of Cryptography:
 Cryptography has a wide range of applications in modern-day communication,
including:
 Secure online transactions: Cryptography is used to secure online transactions,
such as online banking and e-commerce, by encrypting sensitive data and protecting
it from unauthorized access.
 Digital signatures: Digital signatures are used to verify the authenticity and
integrity of digital documents and ensure that they have not been tampered with.
 Password protection: Passwords are often encrypted using cryptographic
algorithms to protect them from being stolen or intercepted.
 Military and intelligence applications: Cryptography is widely used in military and
intelligence applications to protect classified information and communications.

 Challenges of Cryptography:
 While cryptography is a powerful tool for securing information, it also presents several
challenges, including:
 Key management: Cryptography relies on the use of keys, which must be managed
carefully to maintain the security of the communication.
 Quantum computing: The development of quantum computing poses a potential
threat to current cryptographic algorithms, which may become vulnerable to
attacks.
Page 26 of 52
  Human error: Cryptography is only as strong as its weakest link, and human error
can easily compromise the security of a communication.

 Advantages
1. Access Control: Cryptography can be used for access control to ensure that only
parties with the proper permissions have access to a resource. Only those with the
correct decryption key can access the resource thanks to encryption.
2. Secure Communication: For secure online communication, cryptography is crucial. It
offers secure mechanisms for transmitting private information like passwords, bank
account numbers, and other sensitive data over the internet.
3. Protection against attacks: Cryptography aids in the defense against various types of
assaults, including replay and man-in-the-middle attacks. It offers strategies for
spotting and stopping these assaults.
4. Compliance with legal requirements: Cryptography can assist firms in meeting a
variety of legal requirements, including data protection and privacy legislation.

4. Basic Principles: Mathematics of Cryptography

 Mathematics of Cryptography
 Cryptography is the science of using mathematics to hide data behind encryption.
 It involves storing secret information with a key that people must have in order to
access the raw data.
 Without cracking the cipher, it’s impossible to know what the original is.
 While cryptography is also used in the science of securing data, cryptanalysis is also
important to understanding the mathematics side of encrypting and decrypting data.
 Integer Arithmetic
 In integer arithmetic, we use a set and a few operations. You are familiar with this set
and the corresponding operations, but they are reviewed here to create a background
for modular arithmetic.
 Contents/ Topics:
 Set of Integers
 Binary Operations
 Integer Division
 Divisibility
 Set of Integers: The set of integers, denoted by Z, contains all integral numbers (with no
fraction) from negative infinity to positive infinity. The set of integers z,

 Binary Operations : In cryptography, we are interested in three binary operations

applied to the set of integers. A binary operation takes two inputs and creates one output.
 Three binary operations for the set of integers.
Page 27 of 52
  Example: The following shows
the results of the three binary operations on two integers. Because each input can be either
positive or negative, we can have four cases for each operation.

 Integer Division: In integer arithmetic, if we divide a by n, we can get q

and r. The relationship between these four integers can be shown as:
a=q×n+r

Dividend = Quotient × Divisor + Remainder

 Example: Assume that a = 255 and n = 11. We can find q = 23 and R = 2 using the division
algorithm. Finding the quotient and the remainder:

255 = 23*11+2

Page 28 of 52
 Common divisors of two integers

 Greatest Common divisors (GCD) of two integers: gcd(36,60)

 Subtraction Method: Calculate gcd(66,24)

Operations a=66 b=24

a=a-b b=b 42 24
a=a-b b=b 18 24
a=a b=b-a 18 6
a=a-b b=b 12 6
a=a-b b=b 6 6

gcd(66,24) = 6

 Division Method: Calculate gcd(66,24)

Operations a=66 b=24 Quotient

a=b b=a%b 24 18 2
a= b b=a%b 18 6 1
a=b b=a%b 6 0 3

gcd(66,24) = 6

Page 29 of 52
 Greatest Common Divisor:
 The greatest common divisor of two positive integers is the largest integer that can divide
both integers.
 Euclidean Algorithm
Fact 1: gcd (a, 0) = a
Fact 2: gcd (a, b) = gcd (b, r), where r is
the remainder of dividing a by b
 An efficient way to find the GCD(a,b)
 Uses theorem that:
 GCD(a,b) = GCD(b, a mod b)
 Euclidean Algorithm to compute GCD(a,b) is:
Euclid(a,b)
if (b=0) then return a;
else return Euclid(b, a mod b);
 Example:
If a=78 & b=24
gcd(a,b)=gcd(78,24) = gcd(24,6)
gcd(78,24)=6
gcd(24,6)=6
 Euclid Algorithm, part a: Process and part b: Algorithm

 Relatively Prime Numbers: When gcd (a, b) = 1, we say that a and b are relatively prime.
 Example: gcd (401, 700) = 1
we say that 401 and 700 are relatively prime.

Page 30 of 52
 Example GCD(1970,1066)

 Example: GCD(1160718174, 316258250)

 Example: Greatest Common Divisor of 2740 and 1760.

GCD(2740, 1760) = 20.

Page 31 of 52
  Example: Greatest Common Divisor of 25 and 60.
GCD(25, 60) = 5.

 Extended Euclidean Algorithm: Given two integers a and b, we often need to

find other two integers, s and t, such that

 The extended Euclidean algorithm can calculate the gcd (a, b) and at the same time
calculate the value of s and t.
 Example: gcd(888,54) using extended Euclidean Algorithm

888 = 54(16) + 24
54 = 24(2) + 6
24 = 6(4) + 0

Page 32 of 52
  Example: gcd(1180,482) using extended Euclidean Algorithm

1180 = 482(2)+216
482 = 216(2)+50
216 = 50(4)+16
50 = 16(3)+2
16 = 2(8)+0

 Extended Euclid Algorithm, part a: Process and part b: Algorithm

Page 33 of 52
  Example: Given a = 161 and b = 28, find gcd (a, b) and the values of s and t.

r = r1 – q X r2 s = s1 – q X s2 t = t1 – q X t2

We get gcd (161, 28) = 7, s = −1 and t = 6.

 Example: Given a = 17 and b = 0, find gcd (a, b) and the values of s and t.

r = r1 – q X r2 s = s1 – q X s2 t = t1 – q X t2

We get gcd (17, 0) = 17, s = 1, and t = 0.

 Example: Given a = 0 and b = 45, find gcd (a, b) and the values of s and t.

r=r –qXr s=s –qXs t=t –qXt

1 2 1 2 1 2

We get gcd (0, 45) = 45, s = 0, and t = 1.

 MODULAR ARITHMETIC
 The division relationship (a = q × n + r) discussed earlier has two
inputs (a and n) and two outputs (q and r). In modular arithmetic, we
are interested in only one of the outputs, the remainder r.
 Modulo Operator: The modulo operator is shown as mod. The second
input (n) is called the modulus. The output r is called the residue.

a mod n = r

Page 34 of 52
 Figure: Division algorithm and modulo operator

 Modular Arithmetic

– Several important cryptosystems make use of modular arithmetic. This

is when the answer to a calculation is always in the range 0 – (m-1)
where m is the modulus.

– To calculate the value of n mod m, you take away as many multiples of

m as possible until you are left with an answer between 0 and (m-1).

– If n is a negative number then you add as many multiples of m as

necessary to get an answer in the range 0 – (m-1).

– Examples:
 17 mod 5 = 2  7 mod 11 = 7
 20 mod 3 = 2  11 mod 11 = 0
 -3 mod 11 = 8  -1 mod 11 = 10
 25 mod 5 = 0  -11 mod 11 = 0

– Examples: Find the result of the following operations:

i. 27 mod 5 iii. −18 mod 14
ii. 36 mod 12 iv. −7 mod 10

– Solutions:
i. Dividing 27 by 5 results in r = 2
ii. Dividing 36 by 12 results in r = 0.
iii. Dividing −18 by 14 results in r = −4. After adding the modulus r = 10
iv. Dividing −7 by 10 results in r = −7. After adding the modulus to −7, r = 3.

Page 35 of 52
 Modular Division
What is 5 ÷ 3 mod 11?
We need to multiply 5 by the inverse of 3 mod 11
When you multiply a number by its inverse, the answer is 1.
Thus the inverse of 2 is ½ since 2* ½ = 1
The inverse of 3 mod 11 is 4 since 3*4=1 mod 11
Thus 5 ÷ 3 mod 11 = 5*4 mod 11 = 9 mod 11

– A good thing about modular arithmetic is that the numbers you are
working with will be kept relatively small.

– At each stage of an algorithm, the mod function should be applied.

– Thus, to multiply 39 * 15 mod 11 we first take mods to get

 39 mod 11 = 6 and 15 mod 11= 4
 The multiplication required is now
 6*4 mod 11 = 24 mod 11 = 2

 Set of Residues

– The modulo operation creates a set, which in modular arithmetic is

referred to as the set of least residues modulo n, or Z n.

Figure: Some Z sets

n

 Congruence

– Congruences are an important and useful tool for the study of

divisibility.

– If a and b are integers and n > 0, we write: a ≡ b mod n

to mean n|(b − a). We read this as “a is congruent to b modulo (or
mod) n”.

– i.e., Two numbers a and b are said to be “congruent modulo n” if (a

mod n) = (b mod n)  a ≡ b(mod n)

Page 36 of 52
– The difference between a and b will be a multiple of n.
So a-b = kn for some value of k

– Example:
-5  -2  1  4  7 mod 3
4  9  14  19  -1  -6 mod 5
73  4(mod 23) 21  -9(mod 10)
If a  0 (mod n), then n|a.

– In cryptography, we often used the concept of congruence instead of

equality.

– Mapping from Z to Zn is not one to one.

– Infinite members of Z can map to one member of Z n.

– To show that two integers are congruent, we use the congruence

operator ( ≡ ).

– We add the phrase (mod n) to the right side of the congruence to define
the value of modulus that makes the relationship valid.

Figure: Concept of congruence

Page 37 of 52
 Residue Classes

– A residue class [a] or [a]n is the set of integers congruent modulo n.

– For example, if n=5, we have five sets [0],[1],[2],[3] and [4] as shown
below:

 Least Residue modulo n

– The integers in the set [0] are all reduced to 0 when we apply the
modulo 5 operation on them.

– The integers in the set [1] are all reduced to 1 when we apply the
modulo 5 operation on them and so on.

– In each set, there is one element called the least (non-negative) residue.

– In the set [0], this element is 0.

– In the set [1], this element is 1 an so on…

– The set of all these least residues is Z5={0,1,2,3,4}

– The set Zn is the set of all least residue modulo n.

 Exponentiation

– Exponentiation is done by repeated multiplication, as in ordinary

arithmetic.

To find (117 mod13) do the followings

112 121  4(mod13)
114 (112 ) 2  42  3(mod13)
117 11 4  3  132  2(mod13)
Page 38 of 52
– Example: Calculate 7^256 mod 13

– Example: Calculate 5117mod 19

Divide 117 into powers of 2 by writing it in binary:

Page 39 of 52
 5^117 mod 19 = 1

 Properties

Page 40 of 52
 Properties of mod operator

Page 41 of 52
– Examples:

– Example:

– Example:

Page 42 of 52
 Inverses

– When we are working in modular arithmetic, we often need to find the

inverse of a number relative to an operation.

– We are normally looking for an additive inverse (relative to an addition

operation) or a multiplicative inverse (relative to a multiplication
operation).
 Additive Inverse

– In Zn, two numbers a and b are additive inverses of each other if

– Note: In modular arithmetic, each integer has an additive inverse. The

sum of an integer and its additive inverse is congruent to 0 modulo n.

– Example: Find all additive inverse pairs in Z10.

The six pairs of additive inverses are (0, 0), (1, 9), (2, 8), (3, 7), (4,
6), and (5, 5).
 Multiplicative Inverse

– In Zn, two numbers a and b are the multiplicative inverse of each other if

– Note: In modular arithmetic, an integer may or may not have a

multiplicative inverse. When it does, the product of the integer and its
multiplicative inverse is congruent to 1 modulo n.

– Example: Find the multiplicative inverse of 8 in Z 10.

There is no multiplicative inverse because gcd (10, 8) = 2 ≠ 1. In
other words, we cannot find any number between 0 and 9 such that
when multiplied by 8, the result is congruent to 1.

– Example: Find all multiplicative inverses in Z10.

There are only three pairs: (1, 1), (3, 7) and (9, 9). The numbers 0,
2, 4, 5, 6, and 8 do not have a multiplicative inverse.

Page 43 of 52
 – Example: Find all multiplicative inverse pairs in Z 11.
We have seven pairs: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 5), and
(10, 10).

– Note: The extended Euclidean algorithm finds the multiplicative

inverses of b in Zn when n and b are given and gcd (n, b) = 1. The
multiplicative inverse of b is the value of t after being mapped to Z n.
 Multiplicative Inverse using extended Euclidean algorithm

Figure: Using extended Euclidean algorithm to find multiplicative inverse

– Example: Find the multiplicative inverse of 11 in Z 26.

Page 44 of 52
 – Example: Find the multiplicative inverse of 23 in Z100.

– Example: Find the inverse of 12 in Z26.

 Addition and Multiplication Tables

Page 45 of 52
  Different Sets

– Note: We need to use Zn when additive inverses are needed; we need to

use Zn* when multiplicative inverses are needed.
 Two More Sets

Cryptography often uses two more sets: Zp and Zp*. The modulus in
these two sets is a prime number.

 MATRICES
 In cryptography we need to handle matrices.
 Although this topic belongs to a special branch of algebra called linear
algebra, the following brief review of matrices is necessary
preparation for the study of cryptography.
 Definition: In mathematics, a matrix (plural matrices) is
a rectangular array or table of numbers, symbols, or expressions, arranged
in rows and columns, which is used to represent a mathematical object or a
property of such an object.
 Example:

It is a matrix with two rows and three columns. This is often referred to
as a "two by three matrix", a “2 x 3 matrix” or a matrix of dimension 2 x 3.

Page 46 of 52
 Example:

 Examples of Matrices:

 Addition and Subtraction of Matrices

Page 47 of 52
 Product of Two Matrices
– Example: The product of a row matrix (1 × 3) by a column matrix (3 ×
1) is shown in the figure. The result is a matrix of size 1 × 1.

Figure: Multiplication of a row matrix by a column matrix

– Example: The following figure shows the product of a 2 × 3 matrix by a

3 × 4 matrix. The result is a 2 × 4 matrix.

– Example: The following figure shows an example of scalar

multiplication

Page 48 of 52
 Determinant
– The determinant of a square matrix A of size m × m denoted as det (A) is
a scalar calculated recursively as shown below:

– Note: The determinant is defined only for a square matrix.

– Example: The following figure shows how can we calculate the
determinant of a 2 × 2 matrix based on the determinant of a 1 × 1
matrix.

Figure: Calculating the determinant of a 2 x 2 matrix

Example: The following figure shows the calculation of the determinant

of a 3 × 3 matrix.

Figure: Calculating the determinant of a 3 x 3 matrix

 Matrix Inverse or Inverse of a Matrix: Inverse matrix is obtained by

dividing the adjugate of the given matrix by the determinant of the given
matrix.
– Note: Multiplicative inverses are only defined for square matrices.
Page 49 of 52
– Example: Inverse of 2X2 Matrix

Example: Inverse of 3X3 Matrix

Page 50 of 52
Adj(A)=Transpose of Co-factor Matrix

Page 51 of 52
 Residue Matrices
– Cryptography uses residue matrices
– matrices where all elements are in Zn. A residue matrix has a
multiplicative inverse if gcd (det(A), n) = 1.
– Example: A residue matrix and its multiplicative inverse for Z26.

Figure: A residue matrix and its multiplicative inverse for Z 26

Page 52 of 52