Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Guidelines to be followed
CSI3002
Applied Cryptography and Network Security 1. Be on time for class.
2. Be attentive and clarify your doubts immediately.
3. Don’t indulge in other actives when the class is in progress.
By,
Dr.Swetha.N.G., 4. Complete the Assignments/Quiz within the deadline provided.
Assistant Professor Senior, 5. Maintain a dedicated notebook in class.
Department of Analytics,
School of Computer Science and Engineering,
Vellore Institute of Technology, Vellore.

Email: [email protected] Mobile: 8903580808 Cabin: PRP 217-16

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Why This Course? Security and Privacy – Why It Matters?

• Foundation for Digital Security ❖Hackers gaining access to baby monitors or smart locks
• Every time you use a password, send an email, shop online, or use a messaging app
— cryptography is working behind the scenes to keep your data secure. ❖Smart TVs spying on user behavior
• Understanding how encryption, authentication, and secure communication work is ❖Ransomware attacks on hospitals’ IoT-based systems
essential for protecting digital assets in today’s connected world.
• Rising Threat Landscape ❖Privacy leakage from fitness trackers or smart meters
• Cyber attacks are growing in frequency and sophistication. • These real-world cases show how digital systems, if not secured, can
• Governments, businesses, and individuals need professionals who can detect,
prevent, and respond to attacks. become threats instead of assets.
• Analytical and Problem-Solving Skills • This course will guide you to build secure digital systems that are
• Cryptography is rooted in mathematics, logic, and computer science. both resilient and respectful of user privacy.
• Students develop critical thinking, algorithmic design, and ethical reasoning skills.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 1 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Course Objectives Course Outcomes

1. To learn the emerging concepts of cryptography and algorithms On completion of this course, students should be able to:
2. To defend the security attacks on information systems using secure CO 1: Infer the need of security to introduced strong cryptosystems.
algorithms and Authentication process CO 2: Analyze the cryptographic algorithms for information security.
3. To categorize and analyze the key concepts in network and CO 3: Identify the authentication schemes for membership authorization.
wireless security CO 4: Identify computer and network security threats, classify the threats
and develop a security model for detect and mitigate the attacks.
CO 5: Identify the requirements for secure communication and challenges
related to the secure web services
CO 6: Identify the need of ethical and professional practices, risk
management using emerging security solutions.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Modules Books
Module 1: Introduction to Cryptography Recommended Text Book
1. W. Stallings, Cryptography and Network Security: Principles and Practice, 7th
Module 2: Symmetric Key Cryptography Ed.Pearson Publishers, 2017.
Module 3: Asymmetric Key Cryptography 2. Behrouz A. Forouzan, Cryptography and Network Security:6th Ed. McGraw-
Hill, 2017.
Module 4: Hash Functions and Authentication Reference Books
Module 5: Basic Applied Cryptography 1. Kaufman, Perlman and Speciner. Network Security: Private Communication in a
Public World., 2nd edition, Pearson Publishers, 2002.
Module 6: Advanced Applied cryptography 2. Menezes, van Oorschot, and Vanstone, The Handbook of Applied Cryptography,
20th Edition, WILEY, 2015
Module 7: Web and Wireless Security 3. H. Silverman, A Friendly Introduction to Number Theory, 4th Ed. Boston:
Pearson, 2012.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 2 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Job Opportunities Internal Assessment Pattern

Job Roles Companies that offer these roles Internal Component Total Mark Mark Mode of Conduct
Consolidation
• Security Analyst • Google
• Cybersecurity Engineer • Cisco Case Study 1 (Before FAT) 10 10 Case Study or Analytical Problem

• Security Consultant • IBM Quiz 1 (Before CAT 1) 10 10 Offline (During theory class)

• Cryptographic Software Developer • Microsoft Quiz 2 (Before CAT 2) 10 10 Offline (During theory class)
• Research Scientist in Quantum or • Banking Sectors under IT Wing CAT 1 50 15 Offline Mode by COE
DNA Cryptography • Research Lab CAT 2 50 15 Offline Mode by COE
• Cybersecurity Firms (Palo Alto, Total Internal Marks 60
Certification Details FireEye, CrowdStrike)
•Certified Information Systems Security Professional (CISSP)
•Certified Ethical Hacker (CEH)
•GIAC Security Essentials (GSEC)
•CompTIA Security+

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Additional Assignments WhatsApp Group

Additional Eligibility to Attend Total Marks of Components in which Mode of Conduct
Assignment Evaluation the marks will be • B1 and B2 Slot
added • Join the Whatsapp group using the invite link provided in the google
Improvement 1# Common to all 2 Quiz 1/ DA 1/ DA 2 Google Classroom classroom.
students
Remedial 1* Less than 15 in CAT 1 5 Quiz 1/ DA 1/ DA 2 Google Classroom +
Remedial 2* (Debarred students
will not be included)
Offline Classes
• Google Classroom
Remedial 3* • Will be created and the link will be sent after add and drop of the course.
Remedial 4* Less than 15 in CAT 2 5 Quiz 1/ DA 1/ DA 2 Google Classroom +
Remedial 5* (Debarred students Offline Classes
will not be included)

* - Will be conducted only upon instructions from dean academics

# - Will be conducted only when the class average for any one internal component is
below 6 Dr.Swetha.N.G., Assistant Professor Senior, SCOPE, VIT, Vellore.
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 3 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Module 1 - Introduction to Cryptography Computer Security

Security trends, Security attacks, Security mechanism, Elementary • National Institute of Standards and Technology
number theory, Pseudorandom bit generation. Basic security services: • NIST Definition of Computer Security
confidentiality, integrity, availability, nonrepudiation, privacy. • The protection afforded to an automated information system in order to
(3 hours) attain the applicable objectives of preserving the integrity, availability, and
confidentiality of information system resources (includes hardware, software,
firmware, information/data, and telecommunications).
• Three Key Objectives
• Confidentiality
• Integrity CIA Triad
• Availability

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of

Analytics, SCOPE, VIT, Vellore.

Confidentiality Integrity
• Preserving authorized restrictions on information access and • Guarding against improper information modification or destruction,
disclosure, including means for protecting personal privacy and including ensuring information nonrepudiation and authenticity.
proprietary information. • Non-repudiation is the assurance that someone cannot deny the validity of
something.
• A loss of confidentiality is the unauthorized disclosure of information. • Eg: Signing a document
• Two Concepts • Authenticity is the quality of being true.
• Data Confidentiality • A loss of integrity is the unauthorized modification or destruction of
• Assures that private or confidential information is not made available or information.
disclosed to unauthorized individuals. • Two Concepts
• Privacy • Data Integrity
• Assures that individuals control or influence what information related to • Assures that information and programs are changed only in a specified and authorized
manner.
them may be collected and stored and by whom and to whom that • System Integrity
information may be disclosed. • Assures that a system performs its intended function in an unimpaired manner, free
from deliberate or inadvertent unauthorized manipulation of the system.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 4 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Availability Additional Objectives of Security

• Assures that systems work promptly and service is not denied to • Authenticity
authorized users. • The property of being genuine and being able to be verified and trusted;
• Ensuring timely and reliable access to and use of information. • Confidence in the validity of a transmission, a message, or message
originator.
• A loss of availability is the disruption of access to or use of • According to FIPS 199 includes authenticity under integrity. [Federal
information or an information system. Information Processing Standards]
• Accountability
• The security goal that generates the requirement for actions of an entity to
be traced uniquely to that entity.
• This supports nonrepudiation, deterrence, fault isolation, intrusion detection
and prevention, and after-action recovery and legal action.

Levels of impact
Low Medium High
The loss could be expected to The loss could be expected to The loss could be expected to
have a limited adverse effect. have a serious adverse effect. have a severe or catastrophic
adverse effect.
Examples for CIA Triad Cause a degradation in mission
capability.
Cause a significant degradation
in mission capability
Cause a severe degradation in or
loss of mission capability
Result in minor damage to Result in significant damage to Result in major damage to
organizational assets organizational assets organizational assets
Result in minor financial loss Result in significant financial loss Result in major financial loss
Result in minor Result in significant harm Result in severe or catastrophic
harm to individuals. to individuals that does not harm to individuals involving
involve loss of life or serious, loss of life or serious life-
life-threatening injuries. threatening injuries.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 5 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Examples for Confidentiality Examples for Integrity

• Student Grade Information • Patient Allergy information
• Only Students, Parents and staff must access the information. • If a non authorized person changes this information it results in a huge damage to
the individual and the hospital.
• High Confidentiality is required. • High need of data Integrity
• Student Enrolment • Web site that offers a forum for discussion
• Results in less damage if disclosed. • A hacker can falsify the data put up as a part of the forum
• Moderate Confidentiality • When the site is only for entertainment purpose then it only brings in a small loss of
data and time.
• List of Faculty, List of departments in Web Site • Moderate need of data Integrity
• Low Confidentiality • Anonymous online poll
• This information has to be known by a vast range of people to increase the • Just used as statistics
credits of the university. • Inaccuracy and unscientific nature of these polls are well known
• Low need of data Integrity

Challenges in Computer Security

• Mechanisms used to meet the CIA requirements can be quite complex, and understanding them
Examples of Availability may involve rather subtle reasoning.
• In developing a particular security mechanism or algorithm, one must always consider potential
attacks on those security features which is complex.
• Authentication services for critical systems, applications, and devices • It is not obvious from the statement of a particular requirement that such elaborate measures are
• Interruption of service results in the inability for customers to access computing needed.
resources and staff to access the resources they need to perform critical tasks. • It is only when the various aspects of the threat are considered that elaborate security mechanisms make sense.
• Leads to a large financial loss. • Deciding where to use the security mechanisms is complex. (Both physical placement and logical
• High level of Availability is required. sense)
• Security mechanisms typically involve more than a particular algorithm or protocol.
• Public Website for a University • Participants might be involved with some secret information.
• Not a critical part of universities information system. • So transmission and holding this secret information is questionable.
• But unavailability causes embarrassment • It is the duty of the designer to identify and eliminate all the weakness in the system which is again
• Moderate level of Availability complex.
• Online telephone directory lookup • Security requires regular, even constant, monitoring, and this is difficult in today’s short-term,
overloaded environment.
• There are other ways to access the information.
• Security is not made as the integral part of the design which makes it even more challenging.
• Low level of availability.
• Many users and even security administrators view strong security as an impediment to efficient and
user-friendly operation of an information system.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 6 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Computer Security Terminology Difference between Risk, Threat, Vulnerability

Terminology Description
Adversary An entity that attacks, or is a threat to, a system. Vulnerability Threat Risk
Attack An intelligent act that is a deliberate attempt to evade security services and violate The weakness in hardware, Take advantage of vulnerabilities in The potential for loss or
the security policy of a system. software, or designs the system and have the potential destruction of data is caused by
to steal and damage data. cyber threats.
Countermeasure An action, device, procedure, or technique that reduces a threat, a vulnerability, or an attack by
eliminating or preventing it, by minimizing the harm it can cause, or by discovering and Can be controlled. Generally, can’t be controlled. Can be controlled.
reporting it so that corrective action can be taken. Vulnerability management is a Can be blocked by managing the Reducing data transfers,
Risk An expectation of loss expressed as the probability that a particular threat will exploit a process of identifying the vulnerabilities. downloading files from reliable
particular vulnerability with a particular harmful result. problems, then categorizing them, sources, updating the software
prioritizing them, and resolving the regularly, hiring a professional
Security Policy A set of rules and practices that specify or regulate how a system or organization provides vulnerabilities in that order. cybersecurity team to monitor
security services to protect sensitive and critical system resources. data, developing an incident
System Resource (Asset) Data contained in an information system; or a service provided by a system; or a system management plan, etc. help to
capability, such as processing power or communication bandwidth; or an item of system lower down the possibility of cyber
equipment (i.e., a system component— hardware, firmware, software, or documentation); or a risks.
facility that houses system operations and equipment. Penetration testing and Anti-virus software and threat Identifying mysterious emails,
Threat A threat is a possible danger that might exploit a vulnerability. Vulnerability Scanners detection logs. suspicious pop-ups, observing
Vulnerability A flaw or weakness in a system’s design, implementation, or operation and management that unusual password activities, a
could be exploited to violate the system’s security policy. slower than normal network

Threats and Attacks

Security Violations
Threat Consequences Attack
Unauthorized disclosure 1. Exposure
• The security of a system can be threatened via two violations: • threat to confidentiality • Sensitive data are directly released to an unauthorized entity by
• Threat: an authorized person.
• A program that has the potential to cause serious damage to the system. 2. Interception
• Attack: • An unauthorized entity directly accesses sensitive data traveling
between authorized sources and destinations.
• An attempt to break security and make unauthorized use of an asset.
• Using LAN
3. Inference
• Adversary is able to gain information from observing the pattern
of traffic on a network.
• Gets useful information from the analysis.
4. Intrusion
• An unauthorized entity gains access to sensitive data by
circumventing a system’s security protections.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 7 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Threats and Attacks Threats and Attacks

Threat Consequences Attack
Threat Consequences Attack
Disruption 1.Incapacitation
Deception 1.Masquerade
• A circumstance or • Prevents or interrupts system operation by disabling a
• A circumstance or • An unauthorized entity gains access to a system or
event that interrupts system component.
event that may result in performs a malicious act by posing as an authorized
or prevents the correct • Attack on system availability.
an authorized entity entity.
operation of system • Physical destruction of or damage to system hardware
receiving false data • Eg: Unauthorized user has learned another user’s logon ID
services and functions. • Trojan horses, viruses, or worms
and believing it to be and password
• Threat to availability or 2.Corruption
true. 2. Falsification system integrity • Undesirably alters system operation by adversely
• Threat to Integrity • This refers to the altering or replacing of valid data or the
modifying system functions or data.
introduction of false data into a file or database.
• Attack on system integrity
• For example, a student may alter his or her grades on a
school database. 3. Obstruction
• A threat action that interrupts delivery of system services
3. Repudiation
by hindering system operation.
• A user either denies sending data or a user denies
• Eg: By disabling communication links or altering
receiving or possessing the data.
communication control information.

Threats and Attacks Homework – Match the given Attack with its
appropriate Threat
Threat Consequences Attack
Attack Meaning Threat
Usurpation 1.Misappropriation Eavesdropping Unauthorized interception of information 1. Unauthorized Disclosure
• Unauthorized entity • This can include theft of service. 2. Deception
Passive wiretapping Snooping in which a network is monitored
controls the system • The malicious software makes unauthorized use of 3. Disruption
functionality processor and operating system resources. Modification or Unauthorized change of information 4. Usurpation
alteration
• Threat to system 2. Misuse
Active wiretapping Data moving across a network is altered
integrity • Misuse can occur by means of either malicious logic
or a hacker that has gained unauthorized access to a Repudiation of origin False denial that an entity sent (or created) something
system. Denial of receipt False denial that an entity received some information
• In either case, security functions can be disabled or or message
thwarted. Delay A temporary inhibition of a service
Denial of service A long-term inhibition of service

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 8 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Types of Attack
• Active Attack Active Attacks - Illustration
• Modification in the Data Stream
• Types
• Replay
• Passive capture of a data unit and its subsequent retransmission to produce an unauthorized effect.
• Masquerade
• One entity pretends to be a different entity (Impersonation)
• Modification of messages
• Some portion of a legitimate message is altered.
• Denial of service
• Inhibits the normal use or management of communication facilities.
• Disabling the network or by overloading it with messages so as to degrade performance.
• Passive Attack
• Eavesdropping on, or monitoring of, transmissions.
• Goal: Obtain the information that is being transmitted
• Types:
• Release of message contents
• Traffic analysis
• Gathering the data from the packet
• Very difficult to detect the attack.

Active Attacks - Illustration Passive Attacks - Illustration

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 9 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Taxonomy of Service Attacks Summary of Attacks

1.Malware
Common Types of Attacks • Malware uses a vulnerability to breach a network -> install malicious software
• Deny access to the critical components of the network
• Obtain information by retrieving data from the hard drive
1. Malware • Disrupt the system or even render it inoperable
2. Phishing • Common Types of Malware
• Viruses
3. Man-in-the-Middle (MitM) Attacks • Infect applications attaching themselves to the initialization sequence
4. Denial-of-Service (DOS) Attack • Replicates itself, infecting other code in the computer system
• Trojans
5. SQL Injections • Program hiding inside a useful program with malicious purposes
6. Zero-day Exploit • Trojan doesn’t replicate itself and it is commonly used to establish a backdoor to be exploited
• Worms
7. Password Attack • Self-contained programs that propagate across networks and computers
8. Cross-site Scripting • installed through email attachments, sending a copy of themselves to every contact in the infected computer email
list
9. Rootkits • DoS Attack
• Ransomware
10. Internet of Things (IoT) Attacks • Denies access to the victim data, threatening to publish or delete it unless a ransom is paid.
11. DNS Tunneling • Spyware
• Program installed to collect information about users, their systems or browsing habits, sending the data to a remote
user.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 10 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

2. Phishing
• Phishing is the practice of sending fraudulent communications that appear
to come from a reputable source, usually through email.
• Link -> appears to be legit -> once clicked, the personal data
(Authentication information is extracted)
• Types
• Email Phishing
• Register a fake domain that mimics a genuine organization and sends thousands of generic
requests.
• Spear phishing
• Targeted attacks directed at specific companies and/or individuals. (Some information about
the victim is already with them)
• Whaling
• Attacks targeting senior executives and stakeholders within an organization.
• Smishing and vishing
• Smishing involves criminals sending text messages
• Vishing involves telephonic conversations
• Angler phishing
• Fake URLs; cloned websites, posts, and tweets; and instant messaging
• Pharming
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of • Capture user credentials through a fake login landing page
Analytics, SCOPE, VIT, Vellore.

3. Man-in-the-Middle (MitM) Attacks 4. Denial-of-Service (DOS) Attack

• DoS attacks work by flooding systems, servers, and/or
• Also known as eavesdropping attacks networks with traffic to overload resources and
bandwidth.
• Occur when attackers insert themselves
into a two-party transaction. • The system will be unable to process and fulfill
legitimate requests.
• Two common points of entry for MitM • Types
attacks: • Application-layer Flood
• An attacker simply floods the service with requests from a
• On unsecure public Wi-Fi, attackers can insert spoofed IP address in an attempt to slow or crash the service
themselves between a visitor’s device and the • Distributed Denial of Service Attacks (DDoS)
network. Without knowing, the visitor passes • Requests are sent from many clients.
all information through the attacker. • DDoS attacks often involve many "zombie" machines which send
massive amounts of requests to a service to disable it.
• Once malware has breached a device, an • Once service is disabled another attack to steal the data can be
attacker can install software to process all of initiated.
the victim’s information. • Other Attacks DOS Attack
• TCP SYN flood attack, teardrop attack, smurf attack, ping-
of-death attack, and botnets.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 11 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

5. SQL Injections
• Attacker inserts malicious code into a 7. Password Attack
server using server query language
(SQL) forcing the server to deliver
protected information. • By accessing a person’s password, an attacker
• An attacker could carry out a SQL can gain entry to confidential or critical data
injection simply by submitting and systems, including the ability to
malicious code into a vulnerable manipulate and control said data/systems.
website search box. • Password attackers use a myriad of methods to
identify an individual password,
6.Zero-day exploit • Social engineering
• Gaining access to a password database
• Testing the network connection to obtain
• A zero-day exploit hits after a network unencrypted passwords
vulnerability is announced but before • Simply by guessing
a patch or solution is implemented. • Brute-force attack – All possible combinations
• Dictionary attack - When the attacker uses a list of
• Attackers target the disclosed common passwords to attempt to gain access to a
vulnerability during this window of user’s computer and network.
time.

9.Rootkits
8. Cross-site Scripting
• Rootkits are installed inside legitimate software, where they can gain
remote control and administration-level access over a system.
• A cross-site scripting
attack sends malicious • The attacker then uses the rootkit to steal passwords, keys,
scripts into content from credentials, and retrieve critical data.
reliable websites.
• The malicious code joins
the dynamic content that 10. IOT Attacks
is sent to the victim’s
browser. • The interconnectedness of things makes it possible for attackers to
• Usually, this malicious breach an entry point and use it as a gate to exploit other devices in
code consists of Javascript
code executed by the the network.
victim’s browser, but can
include Flash, HTML, and
XSS.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 12 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

11. DNS Tunneling Security Services

• DNS is like a phonebook for the internet, helping to translate between • International Telecommunication Union-Telecommunication
IP addresses and domain names. Standardization Sector (ITU-T) provides security services and mechanism
for implementing them.
• DNS tunneling takes advantage of this fact by using DNS requests to • Security services and mechanisms are closely related because a mechanism
implement a command and control channel for malware. or combination of mechanisms are used to provide a service.
• Inbound DNS traffic can carry commands to the malware, while • A mechanism can be used in one or more services.
outbound traffic can exfiltrate sensitive data or provide responses to • Types
the malware operator’s requests. • X.800
• Service provided by a protocol layer of communication
• RFC 2828
• Communication service that is provided by a system to give a specific kind of protection to
system resources.

Security Services (Contd…)

Security Services
• ITU-T (X.800) has defined five services related to the security goals
and attacks we defined in the previous sections.
(Contd…)
Protection against
unauthorized
access to data.

• Protect data from

disclosure attack,
snooping and traffic • Designed to protect • Peer entity authentication: Proof of the origin:
analysis attack. data from Authentication of the sender or The receiver of the data can later prove the
• Defined by X.800 - modification, insertion, receiver -connection identity of the sender if denied.
deletion, and establishment. Proof of delivery:
encompasses
replaying. • Data origin authentication: Sender of data can later prove that data were
confidentiality of the • Protect the whole
Authenticates the source of the delivered to the intended recipient.
whole message or part message or part of the data
of a message. message.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 13 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Security Mechanism
Incorporated into the appropriate protocol layer in order to Mechanisms that are not specific to any particular
Relationship between Security Services and
provide some of the OSI security services. Security Mechanism OSI security service or protocol layer.
Security Mechanism
Specific Security Mechanism Pervasive Security Mechanism

Encipherment: Mathematical algorithms to transform data.

Trusted Functionality: That which is perceived to be
Digital Signature: To prove the source and integrity of the correct with respect to some criteria.
data unit and protect against forgery
Access Control: Enforce access rights to resources. Security Label: Designates the security attributes of that
resource.
Data Integrity: Assure the integrity of a data unit or stream
of data units. Event Detection: Detection of security-relevant events.
Authentication Exchange: Ensure the identity of an entity
by means of information exchange. Security Audit Trail: Data collected and potentially used
Traffic Padding: The insertion of bits into gaps in a data to facilitate a security audit, which is an independent
stream. review and examination of system records and activities.
Routing Control: Selection of particular physically secure
routes. Security Recovery: Deals with requests from mechanisms,
Notarization: Trusted third party to assure certain properties such as event handling and management functions, and
of a data exchange takes recovery actions.

Random Bit Generation The Use of Random Numbers

• An important cryptographic function is the generation of random bit • A number of network security algorithms and protocols based on
streams. cryptography make use of random binary numbers. For example,
• Random bits streams are used in a wide variety of contexts, including key • Key distribution
generation and encryption. • Session Key Generation
• There are two fundamentally different strategies for generating random • Generation of Keys for RSA
bits or random numbers.
• Generation of Bit Stream for symmetric encryption
• Strategy 1:
• Computes bits deterministically using algorithm.
• Pseudorandom number generators (PRNGs) or Deterministic random bit generators
(DRBGs)
• Strategy 2:
• Produce bits non-deterministically using some physical source that produces some sort of
random output.
• True random number generators (TRNGs) or non-deterministic random bit generators
(NRBGs). Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 14 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Requirements for Sequence of Random

Pseudorandom numbers
Numbers
1. Randomness • Cryptographic applications typically make use of algorithmic
• The sequence of numbers be random in some well-defined statistical sense. techniques for random number generation.
• The following two criteria are used to validate that a sequence of numbers is
random: • These algorithms are deterministic and therefore produce
• Uniform distribution: sequences of numbers that are not statistically random.
• The distribution of bits in the sequence should be uniform; that is, the frequency of occurrence of
ones and zeros should be approximately equal.
• However, if the algorithm is good, the resulting sequences will pass
• Independence:
• No one subsequence in the sequence can be inferred from the others. many tests of randomness.
2. Unpredictability • Such numbers are referred to as pseudorandom numbers.
• The successive members of the sequence are unpredictable.
• With “true” random sequences, each number is statistically independent of other
numbers in the sequence and therefore unpredictable.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Random and Pseudorandom Number Generators PRNG Requirements

Entropy source Fixed Value • Basic requirement is that an adversary who does not know the seed is unable to
Drawn from the Mostly generated by TRNG determine the pseudorandom string.
physical
environment of the
1. Randomness
computer
• Generated bit stream appear random even though it is deterministic.
• Keystroke
• Characteristics
• Uniformity : occurrence of a zero or one is equally likely, that is, the probability of each is exactly 1/2.
timing patterns • Scalability: If a sequence is random, then any such extracted subsequence should also be random.
• Disk electrical • Consistency: The behavior of a generator must be consistent across starting values (seeds).
activity • Test for randomness
• Mouse • No single Test
movements • Apply a sequence of tests to the PRNG
• Instantaneous • If the PRNG exhibits randomness on the basis of multiple tests, then it can be assumed to satisfy the
values of the randomness requirement.
• Frequency test:
system clock. • Number of ones and zeros in a sequence is approximately the same
#Bits produced is different • Runs test:
• 0111110 – Run
• Determine whether the number of runs of ones and zeros of various lengths is as expected for a random
sequence.
• Maurer’s universal statistical test:
• Detect whether or not the sequence can be significantly compressed without loss of information.
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 15 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

PRNG Requirements (Contd…) PRNG Requirements (Contd…)

2. Unpredictability 3. Seed Requirement
• A stream of pseudorandom numbers should exhibit two forms of • The seed that serves as input to the
unpredictability: PRNG must be secure.
• Forward unpredictability • Because the PRNG is a deterministic
• If the seed is unknown, the next output bit in the sequence should be unpredictable in algorithm, if the adversary can deduce
spite of any knowledge of previous bits in the sequence. the seed, then the output can also be
• Backward unpredictability determined.
• It should also not be feasible to determine the seed from knowledge of any generated • Seed – must be random in nature.
values.
• The same set of tests for randomness also provide a test of unpredictability.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

1. Pseudorandom Number Generators - Linear

PRNG Algorithms
Congruential Generators (Purpose Built)
• Two Categories • A widely used technique for pseudorandom number generation is an
• Purpose-built algorithms algorithm first proposed by Lehmer which is known as the linear
• These are algorithms designed specifically and solely for the purpose of generating congruential method.
pseudorandom bit streams.
• Algorithms based on existing cryptographic algorithms
• Cryptographic algorithms have the effect of randomizing input data.
• Thus, cryptographic algorithms can serve as the core of PRNGs.
• Any of these approaches can yield a cryptographically strong PRNG.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 16 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Linear Congruential Generators Test to evaluate Random Number Generators

• The selection of values for a, c, and m is critical in developing a good • T1: The function should be a full-period generating function. That is,
random number generator. the function should generate all the numbers from 0 through m - 1
before repeating.
• T2: The generated sequence should appear random.
a c m X0 Sequence • T3: The function should implement efficiently with 32-bit arithmetic.
1 1 - - Not Satisfactory
To achieve full period the following 3 conditions must be satisfied:
7 0 32 1 {7,17,23,1,7,…} → 4 Unique values → Period 4 1.c and m are relatively prime
Not Satisfactory 2.a−1 must be divisible by all prime factors of m
5 0 32 1 {5, 25, 29, 17, 21, 9, 13, 1, 5, ….} → Period 8 3.If m is divisible by 4, then a−1 must also be divisible by 4 (Special
Case -> It prevents cycling between only even or only odd values.)
Value of m – very large – potential to produce long series of distinct numbers
m=2
Prepared by: Dr.Swetha.N.G., 31 Prof Senior, Dept of
Asst Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Disadvantages of Linear Congruential

Testing Linear Congruential Generators
Generators
• If m is prime and c=0 for certain values of a, the period length is m-1 • If an opponent knows that the linear congruential algorithm is being
with only 0 missing. used and if the parameters are known (e.g., a = 75, c = 0, m = 231 - 1),
• The generated sequence appears random in most of the cases. then once a single number is discovered, all subsequent numbers are
known.
• The arithmetic operation is close to 32 bits as the value of m is 231.
• Even if the opponent knows only that a linear congruential algorithm
is being used, knowledge of a small part of the sequence is sufficient
• Hence, the test for random number generation is a clear pass. to determine the parameters of the algorithm.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 17 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

2. Blum Blum Shub Generator (Purpose Built) BBS Generator (Contd …)

• A popular approach to generating secure pseudorandom numbers is
known as the Blum Blum Shub (BBS) generator.
n = 192649 = 383 * 503
• First, choose two large prime numbers, p and q, that both have a s = 101355
remainder of 3 when divided by 4.
• Let n = p * q
• Next, choose a random number s, such that s is relatively prime to n.
• Then the BBS generator produces a sequence of bits Bi according to
the following algorithm,

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Pseudorandom Number Generation Using

PRNG Using Block Cipher Modes of Operation
A Block Cipher
• Use a symmetric block cipher as the heart of the PRNG mechanism. • If encrypt is AES-128
• For any block of plaintext, a symmetric block cipher produces an then key is 128 bits
output block that is apparently random. and V is 128 bits.
• That is, there are no patterns or regularities in the ciphertext that • If encrypt is DES,
provide information that can be used to deduce the plaintext. key is 56 bits and V is
64 bits.
• Thus, a symmetric block cipher is a good candidate for building a
pseudorandom number generator.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 18 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Elementary number theory

• Divisibility and the Division Algorithm
• The Euclidean Algorithm
• Modular Arithmetic
• Prime Numbers
• Fermat’s and Euler’s Theorems
• Testing for Primality
• The Chinese Remainder Theorem
• Discrete Logarithms

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Introduction to Number Theory –

Set of Integers
Integer Arithmetic
• In integer arithmetic, we use a set and a few operations. • The set of integers, denoted by Z, contains all integral numbers (with
• You are familiar with this set and the corresponding operations, but they no fraction) from negative infinity to positive infinity.
are reviewed here to create a background for modular arithmetic.
Topics discussed in this section:
• Set of Integers
• Binary Operations
• Integer Division
• Divisibility
• Euclidean Algorithm
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 19 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Binary Operations Binary Operations

• In cryptography, we are interested in three binary operations applied • The following shows the results of the three binary operations on two
to the set of integers. integers.
• A binary operation takes two inputs and creates one output. • Because each input can be either positive or negative, we can have
four cases for each operation.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Integer Division Integer Division

• In integer arithmetic, if we divide a by n (a/n), we can get q and r. • Assume that a = 255 and n = 11.
• The relationship between these four integers can be shown as, • We can find q = 23 and r = 2 using the division algorithm.

a=q×n+r

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 20 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Integer Division / Division Algorithm Integer Division

• Division algorithm for integers • Assume that a = -255 and n = 11.
• We can find q = -23 and r = -2 using the division algorithm.
-

-
+
-
-

-
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Integer Division Integer Division

• Assume that a = -255 and n = 11. • Assume that a = -255 and n = 11.
• We can find q = -23 and r = -2 using the division algorithm. • We can find q = -23 and r = -2 using the division algorithm.
- - To convert a negative reminder into non
negative reminder do the following,
- -
+ + 1. Decrement the value of q by 1.
- -
2. Add the value of n to r to make r
- - positive.

Reminder must be non q = q-1

- negative !!! - r = r+n
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 21 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Integer Division
Integer Division
• Assume that a = -255 and n = 11.
• We can find q = -23 and r = -2 using the division algorithm.
- Conversion:
q = q-1
- r = r+n
+
-
q=-23 ➔ -23-1 = -24
- r= -2 ➔ -2+11 = 9

a = (q x n) + r
-
-255 = (-24 x 11) + 9
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Divisibility Divisibility Example

• If a is not zero and we let r = 0 in the division relation, we get • 32/4 • 42/8
• a=32 • a=42
• n=4 • n=8
a=q×n
• Relationship: 32= (8 x 4) + 0 • Relationship: 42= (5 x 8) + 2
• q=8; r=0 • q=5; r=2
• If the remainder is zero, n|a
• Representation: 4|32 • Representation: 8 | 42
• If the remainder is not zero, n|a • 4 divides 32 • 8 does not divide 42
NOTE • 4 is a divisor of 32 • 8 is not a divisor of 42
• n|a
• n divides a
• n is a divisor of a

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 22 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Properties of Divisibility Properties of Divisibility

1. Divisor of 1 is either +1 or -1.
2. A number divides itself (+ or -)
3. 0 has no divisor but 0 is a divident of all
numbers.
▪ 25/0 ➔ not defined
▪ 0/25 ➔ 0
▪ 25|0
4. 11|66 and 66|198
▪ 11|198

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Common divisors of two integers

Divisibility
Greatest Common Divisor (GCD)

Fact 1: The integer 1 has only one divisor, itself.

Fact 2: Any positive integer has at least two divisors, 1

and itself (but it can have more).

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 23 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Greatest Common Divisor (GCD) Greatest Common Divisor (GCD)

• The greatest common divisor of two positive integers is the largest integer • More formally, the positive integer c is said to be the greatest
that can divide both integers. common divisor of a and b if
• GCD (a,b) of a and b is the largest integer that divides evenly into both a • c is a divisor of a and of b.
and b. • any divisor of a and b is a divisor of c.

eg GCD(60,24) = 12
• Mathematical Definition
• gcd(a, b) = max[k, such that k|a and k|b]
• We define gcd(0, 0) = 0
• we require that the greatest common divisor be positive,
• We define gcd(a,0) = |a| • gcd(a,b) = gcd(a,-b) = gcd(-a,b) = gcd(-a,-b)
• When gcd(a,b)=1, it implies that there are no common divisor except 1. • In general, gcd(a,b) = gcd(|a|,|b|)
• So, a and b are said to be relatively prime to each other. • Eg: gcd(60,-24) = gcd(60,24) = 12
• Eg: gcd(8,15)=1 • gcd (a, b) = gcd (b, r), where r is the remainder of dividing a by b
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Euclidean Algorithm Euclidean Algorithm

• Find the greatest common divisor of 25 and 60.

q r1 r2 r
Divide 25/60 = 0.4166
0 25 60 25
q=0
r = 25 (0.416*60)

When gcd (a, b) = 1, we say that a and b are

relatively prime.
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 24 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Euclidean Algorithm Euclidean Algorithm

• Find the greatest common divisor of 25 and 60. • Find the greatest common divisor of 25 and 60.

q r1 r2 r q r1 r2 r
Divide 60/25 = 2.4 Divide 25/10 = 2.5
0 25 60 25 0 25 60 25
q=2 q=2
2 60 25 10 2 60 25 10
r = 10 (0.4*25) r = 5 (0.5*10)
2 25 10 5

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Euclidean Algorithm Euclidean Algorithm

• Find the greatest common divisor of 25 and 60. • Find the greatest common divisor of 25 and 60.

q r1 r2 r q r1 r2 r
Divide 10/5 = 2 When r2=0
0 25 60 25 0 25 60 25
q=2 Stop
2 60 25 10 2 60 25 10
r=0
2 25 10 5 2 25 10 5
2 10 5 0 2 10 5 0
5 0

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 25 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Euclidean Algorithm Euclidean Algorithm

• Find the greatest common divisor of 25 and 60. • Find the greatest common divisor of 2740 and 1760.

q r1 r2 r
0 25 60 25
2 60 25 10 GCD(25,60)=5
2 25 10 5
2 10 5 0
5 0

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Euclidean Algorithm
Euclidean Algorithm
• gcd(1160718174, 316258250)=?
• Find the greatest common divisor of 2740 and 1760.

q r1 r2 r
1 2740 1760 980
1 1760 980 780 GCD(2740,1760)=20
1 980 780 200
3 780 200 180
1 200 180 20
9 180 20 0
20 0
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 26 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Euclidean Algorithm • gcd(1160718174, 316258250)=?

q r1 r2 r
Homework
3 1160718174 316258250 211943424
1 316258250 211943424 104314826
• GCD(1970,1066) = ? Answer: 2
2 211943424 104314826 3313772
31 104314826 3313772 1587894
2 3313772 1587894 137984
11 1587894 137984 70070
1 137984 70070 67914
1 70070 67914 2156
31 67914 2156 1078
2 2156 1078 0
1078 0
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Extended Euclidean Algorithm Extended Euclidean Algorithm

• For given integers a and b, the extended Euclidean algorithm not only
calculates the greatest common divisor d but also two additional
integers s and t that satisfy the following equation.
a.s + b.t = d = gcd(a, b)
• s and t will have opposite signs.
• Eg: gcd (161, 28) = 7, s = −1 and t = 6

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 27 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Extended Euclidean Algorithm Extended Euclidean Algorithm

• Given a = 161 and b = 28, find gcd (a, b) and the values of s and t.

q r1 r2 r s1 s2 s t1 t2 t a=161 b=28
------------------------------------
5 161 28 21 1 0 1 0 1 -5 161/28 = 5.75
q= 5
r= 21
------------------------------------
s=s1-(q*s2)
s=1-(5*0)
s=1
-------------------------------------
t=t1-(q*t2)
t=0-(5*1)
t=-5
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Extended Euclidean Algorithm Extended Euclidean Algorithm

• Given a = 161 and b = 28, find gcd (a, b) and the values of s and t. • Given a = 161 and b = 28, find gcd (a, b) and the values of s and t.

q r1 r2 r s1 s2 s t1 t2 t a=28 b=21 q r1 r2 r s1 s2 s t1 t2 t a=21 b=7

------------------------------------ ------------------------------------
5 161 28 21 1 0 1 0 1 -5 28/21 = 1.333 5 161 28 21 1 0 1 0 1 -5 21/7 = 3
1 28 21 7 0 1 -1 1 -5 6 q= 1 1 28 21 7 0 1 -1 1 -5 6 q= 3
r= 7 r= 0
3 21 7 0 1 -1 4 -5 6 -23
------------------------------------ ------------------------------------
s=s1-(q*s2) s=s1-(q*s2)
s=0-(1*1) s=1-(3*-1)
s=-1 s=4
------------------------------------- -------------------------------------
t=t1-(q*t2) t=t1-(q*t2)
t=1-(1*-5) t=-5-(3*6)
t=6 t=-23
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 28 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Extended Euclidean Algorithm Extended Euclidean Algorithm

• Given a = 161 and b = 28, find gcd (a, b) and the values of s and t. • Given a = 17 and b = 0, find gcd (a, b) and the values of s
and t.
q r1 r2 r s1 s2 s t1 t2 t Stop when r2 becomes 0
-----------------------------------
5 161 28 21 1 0 1 0 1 -5 GCD(161,28)=7
1 28 21 7 0 1 -1 1 -5 6 And the two integers are as
follows,
3 21 7 0 1 -1 4 -5 6 -23
7 0 -1 4 6 -23 s=-1
t=6
-------------------------------------
s*a + t*b = GCD(a,b)
(-1*161)+(6*28) = 7
-161+168 = 7
7=7
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Extended Euclidean Algorithm Extended Euclidean Algorithm

• Given a = 17 and b = 0, find gcd (a, b) and the values of s • Given a = 0 and b = 45, find gcd (a, b) and the values of s
and t. and t.
q r1 r2 r s1 s2 s t1 t2 t Stop when r2 becomes 0 q r1 r2 r s1 s2 s t1 t2 t a=0 b=45
----------------------------------- -------------------------------------
17 0 1 0 0 1 GCD(17,0)=17 0 0 45 0 1 0 1 0 1 0 0/45 = 0
And the two integers are as q=0
follows, r=0
-------------------------------------
s=1 s=s1-(q*s2)
t=0 s=1-(0*0)
------------------------------------- s=1
s*a + t*b = GCD(a,b) --------------------------------------
(1*17)+(0*0) = 17 t=t1-(q*t2)
17+0 = 17 t=0-(0*1)
17 = 17 t=0
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 29 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Extended Euclidean Algorithm Homework

• Given a = 0 and b = 45, find gcd (a, b) and the values of s
and t. • Given a = 1759 and b = 550, find gcd (a, b) and the values of x and y.
Stop when r2 becomes 0 • Answer: GCD(1759,550) = 1; x= -111; y=355
q r1 r2 r s1 s2 s t1 t2 t
-----------------------------------
0 0 45 0 1 0 1 0 1 0 GCD(0,45)=45
45 0 0 1 1 0 And the two integers are as
follows,

s=0
t=1
-------------------------------------
s*a + t*b = GCD(a,b)
(0*0)+(1*45) = 45
0+45 = 45
45 = 45
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Modular Arithmetic Modulo Operator

• The division relationship (a = q × n + r) discussed in the previous section • The modulo operator is shown as mod.
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 • The second input (n) is called the modulus.
remainder r. • The output r is called the residue.
• Topics discussed in this section:
• Modular Operator
• Set of Residues
• Congruence
• Operations in Zn
• Addition and Multiplication Tables
• Different Sets
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore.
Division algorithm and modulo operator
Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 30 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Modulo Operator Modulo Operator

• Find the result of the following • Find the result of the following
operations: operations:
• 27 mod 5 = ? • 27 mod 5 = 2
• 27/5 = 5.4
• q=5
• r=(5.4-5)*5=2

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Modulo Operator Modulo Operator

• Find the result of the following • Find the result of the following
operations: operations:
• 27 mod 5 = 2 • 27 mod 5 = 2
• 27/5 = 5.4 • 27/5 = 5.4
• q=5 • q=5
• r=(5.4-5)*5=2 • r=(5.4-5)*5=2
• 36 mod 12 = ? • 36 mod 12 = 0
• 36/12 = 3 ➔ r=0

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 31 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

• −18 mod 14 = ? • −18 mod 14 = 10

Modulo Operator Modulo Operator • -18/14= -1.2857
• q= -1
• Find the result of the following • Find the result of the following • r= (-1.2857+1)*14 = -4
operations: operations: • Decrement q by 1 and add n to r.
• 27 mod 5 = 2 • 27 mod 5 = 2 q=-2 ; r= -4+14 = 10
• 27/5 = 5.4 • 27/5 = 5.4
• q=5 • q=5
• r=(5.4-5)*5=2 • r=(5.4-5)*5=2
• 36 mod 12 = 0 • 36 mod 12 = 0
• 36/12 = 3 ➔ r=0 • 36/12 = 3 ➔ r=0

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

• −18 mod 14 = 10 • −18 mod 14 = 10

Modulo Operator • -18/14= -1.2857
Modulo Operator • -18/14= -1.2857
• q= -1 • q= -1
• Find the result of the following • r= (-1.2857+1)*14 = -4 • Find the result of the following • r= (-1.2857+1)*14 = -4
operations: • Decrement q by 1 and add n to r. operations: • Decrement q by 1 and add n to r.
• 27 mod 5 = 2 q=-2 ; r= -4+14 = 10 • 27 mod 5 = 2 q=-2 ; r= -4+14 = 10
• 27/5 = 5.4 • −7 mod 10 = ? • 27/5 = 5.4 • −7 mod 10 = 3
• q=5 • q=5 • -7/10 =- 0.7
• r=(5.4-5)*5=2 • r=(5.4-5)*5=2 • q= 0
• 36 mod 12 = 0 • 36 mod 12 = 0 • r= (-0.7*10)= -7
• Decrement q by 1 and add n to r.
• 36/12 = 3 ➔ r=0 • 36/12 = 3 ➔ r=0
q=-1 ; r= -7+10 = 3

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 32 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Set of Residues Congruence

• The modulo operation creates a set, which in modular arithmetic is • Congruence: The quality or state of agreeing, coinciding
referred to as the set of least residues modulo n, or Zn. • Two integers a and b are said to be congruent modulo n, if
(a mod n) = (b mod n)
• This is written as a ≡ b (mod n)

Some Zn sets

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Congruence Properties of Congruences

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 33 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Operation in Zn Operation in Zn
• The three binary operations that we discussed for the set Z can also Perform the following operations (the inputs come from Zn):
be defined for the set Zn. • Add 7 to 14 in Z15
• The result may need to be mapped to Zn using the mod operator.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Operation in Zn Operation in Zn
Perform the following operations (the inputs come from Zn): Perform the following operations (the inputs come from Zn):
• Add 7 to 14 in Z15 • Add 7 to 14 in Z15
• (7+14) mod 15 = 21 mod 15 = 6 • (7+14) mod 15 = 21 mod 15 = 6
• Subtract 11 from 7 in Z13

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 34 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Operation in Zn Operation in Zn
Perform the following operations (the inputs come from Zn): Perform the following operations (the inputs come from Zn):
• Add 7 to 14 in Z15 • Add 7 to 14 in Z15
• (7+14) mod 15 = 21 mod 15 = 6 • (7+14) mod 15 = 21 mod 15 = 6
• Subtract 11 from 7 in Z13 • Subtract 11 from 7 in Z13
• (7-11) mod 13 = -4 mod 13 = 9 mod 13 = 9 • (7-11) mod 13 = -4 mod 13 = 9 mod 13 = 9
• Multiply 11 by 7 in Z20

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Operation in Zn Operation in Zn
Perform the following operations (the inputs come from Zn): Properties
1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
• Add 7 to 14 in Z15
• (7+14) mod 15 = 21 mod 15 = 6 2. [(a mod n) – (b mod n)] mod n = (a – b) mod n
3. [(a mod n) x (b mod n)] mod n = (a x b) mod n
• Subtract 11 from 7 in Z13
• (7-11) mod 13 = -4 mod 13 = 9 mod 13 = 9
Example
• Multiply 11 by 7 in Z20 1. [(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2 ; (11 + 15) mod 8 = 26 mod 8 = 2
• (11*7) mod 20 = 77 mod 20 = 17 2. [(11 mod 8) – (15 mod 8)] mod 8 = –4 mod 8 = 4 ; (11 – 15) mod 8 = –4 mod 8 = 4
3. [(11 mod 8) x (15 mod 8)] mod 8 = 21 mod 8 = 5 ; (11 x 15) mod 8 = 165 mod 8 = 5

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 35 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Operation in Zn Inverses
• In arithmetic, we often need to find the remainder of powers of 10 • When we are working in modular arithmetic, we often need to find
when divided by an integer. 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).

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Inverses: Additive Inverses: Additive

• In Zn, two numbers a and b are additive inverses of each other if • Find all additive inverse pairs in Z10.

Solution:
• Z10 = {0,1,2,3,4,5,6,7,8,9}
• Consider ‘0’ the additive inverse is itself ‘0’ [0+0] ≡ 0 mod 10
In modular arithmetic, each integer has an additive inverse.
The sum of an integer and its additive inverse is congruent to • ‘1’ additive inverse is ‘9’, [1+9] ≡ 0 mod 10
0 modulo n. • 2 additive inverse is 8, [2+8] ≡ 0 mod 10
• The six pairs of additive inverses are
(0, 0), (1, 9), (2, 8), (3, 7), (4, 6), and (5, 5).
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 36 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Inverses: Multiplicative
Inverses: Multiplicative • Find all multiplicative inverses in Z10.

• In Zn, two numbers a and b are the multiplicative inverse of each Solution
other if • Z10 = {0,1,2,3,4,5,6,7,8,9}
• 0 * NA ≡ 1 mod 10
• 0 has no multiplicative inverse under modulo 10.
• 1*? ≡ 1 mod 10
• 1*1 ≡ 1 mod 10
In modular arithmetic, an integer may or may not • The multiplicative inverse of 1 is 1 under modulo 10.
have a multiplicative inverse. • 2*? ≡ 1 mod 10
• 2 has no multiplicative inverse under modulo 10.
When it does, the product of the integer and its
• 3*? ≡ 1 mod 10
multiplicative inverse is congruent to • 3*7 ≡ 1 mod 10
1 modulo n. • The multiplicative inverse of 3 is 7 under modulo 10.
• There are only three pairs: (1, 1), (3, 7) and (9, 9).
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of • The numbers 0, 2, 4, 5, 6, and 8by:do
Prepared not have
Dr.Swetha.N.G., a Senior,
Asst Prof multiplicative
Dept of inverse.
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Inverses: Multiplicative Inverses: Multiplicative

• Find the multiplicative inverse of 8 in Z10.
The extended Euclidean algorithm finds the
Solution multiplicative inverses of b in Zn when n and b are
• Multiplicative inverse for a number only exists if the number and given and
the modulo operator are relatively prime to each other. gcd (n, b) = 1.
• There is no multiplicative inverse because gcd (10, 8) = 2 ≠ 1. The multiplicative inverse of b is the value of t after
being mapped to Zn.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 37 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Inverses: Multiplicative Inverses: Multiplicative

• Using extended Euclidean algorithm to find multiplicative inverse • Find the multiplicative inverse of 11 in Z26.
• Solution

• The gcd (26, 11) is 1; the inverse of 11 is -7 or 19

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Inverses: Multiplicative Inverses: Multiplicative

• Find the multiplicative inverse of 23 in Z100. • Find the inverse of 12 in Z26.
• Solution
• Solution

• The gcd (100, 23) is 1; the inverse of 23 is -13 or 87. • The gcd (26, 12) is 2; the inverse does not exist.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 38 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Addition and Multiplication Tables Different Sets

We need to use Zn when additive inverses are

needed;
we need to use Zn* when multiplicative inverses are
needed.
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Primes PRIMES: Definition

• Asymmetric-key cryptography uses primes extensively. • Three groups of Positive Integers

Topics discussed in this section:

• Definition
• Checking for Primes
• Fermat’s Little Theorem
• Euler’s Phi-Function
• Euler’s Theorem
A prime is divisible only by itself and 1.
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 39 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

PRIMES: Definition PRIMES: Checking for Primes

• What is the smallest prime? • Given a number n, how can we determine if n is a prime?
Solution
• The smallest prime is 2, which is divisible by 2 (itself) and 1.
• The answer is that we need to see if the number is divisible by all
primes less than
• List the primes smaller than 10.
Solution
• There are four primes less than 10: 2, 3, 5, and 7.
• It is interesting to note that the percentage of primes in the range 1 to 10 is • We know that this method is inefficient, but it is a good start.
40%.
• The percentage decreases as the range increases.
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

PRIMES: Checking for Primes PRIMES: Checking for Primes

• Is 97 a prime?
Solution
• The floor of √97 = 9. The primes less than 9 are 2, 3, 5, and 7. We need to
see if 97 is divisible by any of these numbers. It is not, so 97 is a prime.

• Is 301 a prime?
Solution
• The floor of √301 = 17. We need to check 2, 3, 5, 7, 11, 13, and 17. The
numbers 2, 3, and 5 do not divide 301, but 7 does. Therefore 301 is not a
prime.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 40 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

PRIMES: Checking for Primes Fermat’s (Little) Theorem

• First Version ap − 1 ≡ 1 mod p
• Multiply by a on both sides: Second Version ap ≡ a mod p
• where p is prime and gcd(a,p)=1

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Fermat’s (Little) Theorem Fermat’s (Little) Theorem

• Find the result of 610 mod 11. • Multiplicative Inverses: [First version/a]
Solution ap − 1 ≡ 1 mod p
• We have 6 mod 11 = 1.
10
a−1 mod p = a p − 2 mod p
• This is the first version of Fermat’s little theorem where p = 11.
----------------------------------------------------------------------------------------------
• The answers to multiplicative inverses modulo a prime can be found
• Find the result of 312 mod 11.
Solution
ap ≡ a mod p without using the extended Euclidean algorithm:

• Here the exponent (12) and the modulus (11) are not the same. With
substitution this can be solved using Fermat’s little theorem.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 41 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Euler’s Phi-Function Euler’s Phi-Function

• Euler’s phi-function, (n), which is sometimes called the Euler’s • We can combine the above four rules to find the value of (n).
totient function plays a very important role in cryptography. • For example, if n can be factored as
n = p1e × p2e × … × pke
1 2 k

• we combine the third and the fourth rule to find (n)

The difficulty of finding (n) depends on the difficulty

of finding the factorization of n.
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Euler’s Phi-Function Euler’s Phi-Function

• What is the value of (13)? • What is the value of (240)?
Solution Solution
• Because 13 is a prime, (13) = (13 −1) = 12. • We can write 240 = 24 × 31 × 51. Then
•  (240) = (24 −23) × (31 − 30) × (51 − 50) = 64
• What is the value of (10)? -----------------------------------------------------------------------------------------------------
Solution • Can we say that (49) = (7) × (7) = 6 × 6 = 36?
Solution
• We can use the third rule: (10) = (2) × (5) = 1 × 4 = 4, because 2
and 5 are primes. • No. The third rule applies when m and n are relatively prime. Here 49 = 72.
• We need to use the fourth rule: (49) = 72 − 71 = 42.
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 42 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Euler’s Phi-Function Euler’s Theorem

• What is the number of elements in Z14*? • First Version a(n) ≡ 1 (mod n)
Solution
• The answer is (14) = (7) × (2) = 6 × 1 = 6. The members are 1, 3, 5, • Second Version
9, 11, and 13.
a k × (n) + 1 ≡ a (mod n)
Interesting point: If n > 2, the value of (n) is even.
The second version of Euler’s theorem is used in the
RSA cryptosystem

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Euler’s Theorem Euler’s Theorem

• Find the result of 624 mod 35.
a(n) ≡ 1 (mod n) Multiplicative Inverses:
Solution • Euler’s theorem can be used to find multiplicative inverses modulo a
• We have 624 mod 35 = 6(35) mod 35 = 1. composite.
----------------------------------------------------------------------------------------------
• Find the result of 2062 mod 77.
a k × (n) + 1 ≡ a (mod n) a−1 mod n = a(n)−1 mod n
Solution
• If we let k = 1 on the second version, we have
• 2062 mod 77 = (20 mod 77) (20(77) + 1 mod 77) mod 77
• = (20)(20) mod 77 = 15.
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 43 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

Euler’s Theorem a−1 mod n = a(n)−1 mod n Homework

• The answers to multiplicative inverses modulo a composite can be • Find (1200)
found without using the extended Euclidean algorithm if we know the
factorization of the composite:

11*17

(2^2)*(5^2)

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Modular Exponentiation
• If the base and the modulus are closer to each other, convert the base
into a negative number.
• Choose whichever is the smallest to operate on.
Additional Input • If the exponent is greater, then divide the exponent into smaller
numbers and get the result. Finally combine all the answers obtained.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 44 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

1. 233 mod 30 2. 31500 mod 30 887 mod 187

23-30= -7 31-30= 1 882 * 882 * 882 * 881 (mod 187)

77 * 77 * 77 * 88 (mod 187)
233 mod 30=(-7)3 mod 30 31500 mod 30=1500 mod 30 66 * 88 (mod 187)
= -13 =1 11
= 17

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Successive Squaring 1113 mod 53

111 mod 53 = 11
• Find the answer in terms of squares, 112 mod 53 = 15
• a1, a2, a4, a8, a16, a32, a64, …… 114 mod 53 = 13
• Finally combine the required powers to get the answer.
118 mod 53 = 10

1113 mod 53 = 118 * 114 * 11 (mod 53)

= 10 * 13 * 11 (mod 53)
= 52

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 45 of 46
 Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore.

413 mod 497=?

Memory Efficient Method 41 mod 497 = (1*4) mod 497 = 4
42 mod 497 = (4*4) mod 497 = 16
• Find the answer by increment the exponent by 1 every time, 43 mod 497 = (16*4) mod 497 = 64
• a1, a2, a3, a4, a5, a6, …. aexponent 44 mod 497 = (64*4) mod 497 = 256
• This saves memory internally as only one variable is used. 45 mod 497 = (256*4) mod 497 = 30
46 mod 497 = (30*4) mod 497 = 120
47 mod 497 = (120*4) mod 497 = 480
48 mod 497 = (480*4) mod 497 = 429
49 mod 497 = (429*4) mod 497 = 225
410 mod 497 = (225*4) mod 497 = 403
411 mod 497 = (403*4) mod 497 = 121
412 mod 497 = (121*4) mod 497 = 484
413 mod 497 = (484*4) mod 497 = 445
Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

5117 mod 19
Fast Modular Exponentiation Binary Equivalent of 117= 1 1 1 0 1 0 1
26 25 24 22 20
• ab mod m
5117 mod 19= 51 * 54* 516 * 532 * 564 (mod 19)
• Find the binary equivalent of b.
= 5 * 17 * 16 * 9 * 5 (mod 19)
• Replace each 1 in the equivalent with 2Position.
=1
• Raise a to the power of each 2Position.
• Solve it to get the answer.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of Prepared by: Dr.Swetha.N.G., Asst Prof Senior, Dept of
Analytics, SCOPE, VIT, Vellore. Analytics, SCOPE, VIT, Vellore.

Prepared by: Dr.Swetha.N.G., Asst Prof Senior, SCOPE, VIT, Vellore. Page 46 of 46