CNS Unit I

File Downloaded From www.Bustudymate.
in
BCA: III SEM: VI

CRYPTOGRAPHY & NETWORK
SECURITY
Dr.T.LOGESWARI
DEPT OF COMPUTER SCIENCE
File Downloaded
Cryptography NEW HORIZON COLLEGE
From www.Bustudymate.in
& Network Security - Behrouz
A. Forouzan
1
File Downloaded From www.Bustudymate.in
UNIT - I
Introduction
Dr.T.Logeswari
File Downloaded
Cryptography From www.Bustudymate.in
2
A. Forouzan
Objectives
 To define three security goals
 To define security attacks that threaten security
goals
 To define security services and how they are
related to the three security goals
 To define security mechanisms to provide security
services
 To introduce two techniques, cryptography and
steganography, to implement security mechanisms.
File Downloaded
3
A. Forouzan
INTRODUCTION
• 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.
File Downloaded
4
A. Forouzan
• 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 frustrate hackers
• Network Security - measures to protect data
during their transmission
• Internet Security - measures to protect data
during their transmission over a collection of
interconnected networks
File Downloaded
5
A. Forouzan
Cryptography
• Cryptography is the science of writing in
secret code so that no other person except
the intended recipient could read
File Downloaded
6
A. Forouzan
SECURITY GOALS
•Data Privacy(confidentiality)
•Data Authenticity(it came from where it claims)
•Data integrity(it has not been modified on the way) in
the digital world
File Downloaded
7
A. Forouzan
Continued
Figure 1.1 Taxonomy of security goals
File Downloaded
8
A. Forouzan
Confidentiality
• Confidentiality is probably the most common aspect of

information security.
• An organization needs to guard against those malicious
actions that endanger the confidentiality of its
information.
• The meaning of a message is concealed by encoding it
• The sender encrypts the message using a cryptographic
key
• The recipient decrypts the message using a cryptographic
key that may or may not be the same as the one used by
the sender
File Downloaded
9
A. Forouzan
Integrity
• Information needs to be changed constantly.

• Integrity means that changes need to be done only by
authorized entities and through authorized mechanisms.
(Bank Transaction)
File Downloaded
10
A. Forouzan
Availability
• The information created and stored by an organization

needs to be available to authorized entities.
• Information needs to be constantly changed, which
means it must be accessible to authorized entities.
File Downloaded
11
A. Forouzan
Security Attacks, Services and

Mechanisms
• 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.
• One approach is to consider three aspects of
information security:
File Downloaded
12
A. Forouzan
• 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.
File Downloaded
13
A. Forouzan
Cryptographic Attacks
• They are broadly classified as

– Cryptanalytic attacks
– Non Cryptanalytic attacks
File Downloaded
14
A. Forouzan
Types of Cryptanalytic Attacks

• ciphertext only
– only know algorithm / ciphertext, statistical, can identify
plaintext
• known plaintext
– know/suspect plaintext & ciphertext to attack cipher
• chosen plaintext
– select plaintext and obtain ciphertext to attack cipher
• chosen ciphertext
– select ciphertext and obtain plaintext to attack cipher
• chosen text
– select either plaintext or ciphertext to en/decrypt to attack
cipher File Downloaded
A. Forouzan
15
Non Cryptanalytic Attacks
The three goals of securityconfidentiality, integrity,

and availabilitycan be threatened by security attacks.
• Attacks Threatening Confidentiality

• Attacks Threatening Integrity
• Attacks Threatening Availability
• Passive versus Active Attacks
File Downloaded
16
A. Forouzan
Figure 1.2 Taxonomy of attacks with relation to security goals
File Downloaded
17
A. Forouzan
Attacks Threatening Confidentiality
• Interception an unauthorized party gains

access to an asset. This is an attack on
confidentiality.
• Unauthorized party could be a person, a
program or a computer .e.g., wire tapping to
capture data in the network, illicit copying of
files
File Downloaded
18
A. Forouzan
Attacks Threatening Confidentiality
Snooping refers to unauthorized access to or interception of

data.
• Data transferred through internet may be intercepted by
unauthorized entity and content may be used for self benefit
Traffic analysis refers to obtaining some other type of

information by monitoring online traffic.
File Downloaded
19
A. Forouzan
Attacks Threatening Integrity
• Modification an unauthorized party not only

gains access to but tampers with an asset.
• This is an attack on integrity. e.g., changing
values in data file, altering a program,
modifying the contents of messages being
transmitted in a network
File Downloaded
20
A. Forouzan
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 sender of the message might later

deny that she has sent the message; the receiver of the
message might later deny that he has received the message.
File Downloaded
21
A. Forouzan
Attacks Threatening Availability
• Interruption an asset of the system is destroyed

or becomes unavailable or unusable.
• This is an attack on availability
• e.g., destruction of piece of hardware, cutting
of a communication line or Disabling of file
management system.
File Downloaded
22
A. Forouzan
Attacks Threatening Availability
Denial of service (DoS) is a very common attack. It may

slow down or totally interrupt the service of a system.
File Downloaded
23
A. Forouzan
Attacks Threatening Authenicity
• Fabrication an unauthorized party inserts

counterfeit objects into the system. This is an
attack on authenticity. e.g., insertion of
spurious message in a network or addition of
records to a file.
File Downloaded
24
A. Forouzan
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.
• Passive attacks are of two types:
– Release of message contents
– Traffic analysis
File Downloaded
25
A. Forouzan
• Release of message contents: A telephone

conversation, an e-mail message and a
transferred file may contain sensitive or
confidential information.
• We would like to prevent the opponent from
learning the contents of these transmissions.
File Downloaded
26
A. Forouzan
• Traffic analysis: If we had encryption

protection in place, an opponent might still be
able to observe the pattern of the message.
• The opponent could determine the location and
identity of communication hosts and could
observe the frequency and length of messages
being exchanged.
• This information might be useful in guessing
the nature of communication that was taking
place.
File Downloaded
27
A. Forouzan
Active attacks
• Masquerade – One entity pretends to be a

different entity.
• Replay – involves passive capture of a data
unit and its subsequent transmission to produce
an unauthorized effect.
• Modification of messages – Some portion of
message is altered or the messages are delayed
or recorded, to produce an unauthorized effect.
File Downloaded
28
A. Forouzan
• Denial of service – Prevents or inhibits the

normal use or management of communication
facilities.
• Another form of service denial is the
disruption of an entire network, either by
disabling the network or overloading it with
messages so as to degrade performance.
File Downloaded
29
A. Forouzan
Passive Versus Active Attacks
Table 1.1 Categorization of passive and active attacks
File Downloaded
30
A. Forouzan
SERVICES AND MECHANISMS
ITU-T provides some security services and some

mechanisms to implement those services. Security
services and mechanisms are closely related because a
mechanism or combination of mechanisms are used to
provide a service..
• Security Services
• Security Mechanism
• Relation between Services and Mechanisms
File Downloaded
31
A. Forouzan
Security Services
Figure 1.3 Security services
File Downloaded
32
A. Forouzan
• The classification of security services are as

follows:
• Confidentiality: Ensures that the information
in a computer system and transmitted
information are accessible only for reading by
authorized parties. E.g. Printing, displaying
and other forms of disclosure.
• Authentication: Ensures that the origin of a
message or electronic document is correctly
identified, with an assurance that the identity is
not false.
File Downloaded
33
A. Forouzan
• Integrity: Ensures that only authorized parties

are able to modify computer system assets and
transmitted information.
– Modification includes writing, changing status,
deleting, creating and delaying or replaying of
transmitted messages.
• Non repudiation: Requires that neither the
sender nor the receiver of a message be able to
deny the transmission.
File Downloaded
34
A. Forouzan
• Access control: Requires that access to

information resources may be controlled by or
the target system.
• Availability: Requires that computer system
assets be available to authorized parties when
needed.
File Downloaded
35
A. Forouzan
Security Mechanism
Figure 1.4 Security mechanisms
File Downloaded
36
A. Forouzan
• Encipherment
– It is hiding or covering of data ( crypto and
steganography)
• Data Integrity
– This mechanism append to the data a short check
value that has been created by a specific process
from data itself
• Digital signature
– The sender electronically sign the data and
receiver can electronically verify the signature
File Downloaded
37
A. Forouzan
• Authentication Exchange
– Two entities exchange some message to prove their
identify to each other
– Something the user knows(unique secret)
– Something the user has(security card)
– Something the user is(fingerprint, retina voice)
• Traffic padding
– It means inserting some bogus data into a data
traffic to thwart the adversary attempt to use the
traffic analysis
File Downloaded
38
A. Forouzan
• Routing Control
– It means selecting and continuously changing
different available routes between the sender and
the receiver to prevent eavesdropping
• Notarization
– It means selecting third trusted party to control the
communication between two parties. This can be
done to prevent repudiation
• Access Control
– It uses method to prove that user has to right to the
data or resources owned by a system
File Downloaded
39
A. Forouzan
Relation between Services
File Downloaded and Mechanisms
From www.Bustudymate.in
Table 1.2 Relation between security services and mechanisms
File Downloaded
40
A. Forouzan
TECHNIQUES
Mechanisms discussed in the previous sections are only

theoretical recipes to implement security. The actual
implementation of security goals needs some
techniques. Two techniques are prevalent today:
cryptography and steganography.
•Cryptography
• Steganography
File Downloaded
41
A. Forouzan
Cryptography
Cryptography, a word with Greek origins, means “secret

writing.”
However, we use the term to refer to the science and art of

transforming messages to make them secure and immune to
attacks.
File Downloaded
42
A. Forouzan
Cryptography
• can be characterized by:

– type of encryption operations used
• substitution / transposition / product
– number of keys used
• single-key or secret-key vs two-key or public-key
– way in which plaintext is processed
• block / stream
File Downloaded
43
A. Forouzan
Cryptography
• Cryptographic systems are generally classified
along 3 independent dimensions:
• Type of operations used for transforming
plain text to cipher text
– All the encryption algorithms are based on two
general principles:
– substitution, in which each element in the
plaintext is mapped into another element.
– transposition, in which elements in the plaintext
are rearranged.
File Downloaded
44
A. Forouzan
• The number of keys used

– If the sender and receiver uses same key then it is
said to be symmetric key (or) single key (or)
conventional encryption.
– If the sender and receiver use different keys then it
is said to be asymmetric key or public key
encryption.
File Downloaded
45
A. Forouzan
• The way in which the plain text is processed

– A block cipher processes the input and block of
elements at a time, producing output block for
each input block.
– A stream cipher processes the input elements
continuously, producing output element one at a
time, as it goes along.
File Downloaded
46
A. Forouzan
Steganography
The word steganography, with origin in Greek, means

“covered writing,” in contrast with cryptography, which
means “secret writing.”
Example: covering data with text
File Downloaded
47
A. Forouzan
• .e.g., (i) the sequence of first letters of each

word of the overall message spells out the real
(Hidden) message.
• (ii) Subset of the words of the overall message
is used to convey the hidden message.
File Downloaded
48
A. Forouzan
Various other techniques
• Character marking – selected letters of printed

or typewritten text are overwritten in pencil.
The marks are ordinarily not visible unless the
paper is held to an angle to bright light.
• Invisible ink – a number of substances can be
used for writing but leave no visible trace until
heat or some chemical is applied to the paper.
File Downloaded
49
A. Forouzan
• Pin punctures – small pin punctures on

selected letters are ordinarily not visible unless
the paper is held in front of the light.
• Typewritten correction ribbon – used between
the lines typed with a black ribbon, the results
of typing with the correction tape are visible
only under a strong light.
File Downloaded
50
A. Forouzan
File Downloaded
51
A. Forouzan
Types of steganography
• Technical steganography uses scientific
methods to hide a message, such as the use of
invisible ink or microdots and other size-
reduction methods.
• Linguistic steganography hides the message in
the carrier in some nonobvious ways and is
further categorized as semagrams or open
codes.
File Downloaded
52
A. Forouzan
• Semagrams hide information by the use of

symbols or signs.
• A visual semagram uses innocent-looking or
everyday physical objects to convey a
message, such as doodles or the positioning of
items on a desk or Website.
• A text semagram hides a message by
modifying the appearance of the carrier text,
such as subtle changes in font size or type,
adding extra spaces, or different flourishes in
letters or handwritten text.
File Downloaded
53
A. Forouzan
• Open codes hide a message in a legitimate

carrier message in ways that are not obvious to
an unsuspecting observer.
• The carrier message is sometimes called the
overt communication whereas the hidden
message is the covert communication.
• This category is subdivided into jargon codes
and covered ciphers.
File Downloaded
54
A. Forouzan
• Jargon code, as the name suggests, uses

language that is understood by a group of
people but is meaningless to others.
• A subset of jargon codes is cue codes, where
certain prearranged phrases convey meaning.
File Downloaded
55
A. Forouzan
• Covered or concealment ciphers hide a message

openly in the carrier medium so that it can be
recovered by anyone who knows the secret for how it
was concealed.
• A grille cipher employs a template that is used to
cover the carrier message. The words that appear in
the openings of the template are the hidden message.
• A null cipher hides the message according to some
prearranged set of rules, such as "read every fifth
word" or "look at the third character in every word."
File Downloaded
56
A. Forouzan
Mathematics of
Cryptography
Part I: Modular Arithmetic, Congruence,

and Matrices
File Downloaded
57
A. Forouzan
Objectives
 To review integer arithmetic, concentrating on divisibility
and finding the greatest common divisor using the Euclidean
algorithm
 To understand how the extended Euclidean algorithm can be
used to solve linear Diophantine equations, to solve linear
congruent equations, and to find the multiplicative inverses
 To emphasize the importance of modular arithmetic and
the modulo operator, because they are extensively used in
cryptography
 To emphasize and review matrices and operations on residue
matrices that are extensively used in cryptography
 To solve a set of congruent equations using residue matrices
Cryptography & Network Security - Behrouz
58
A. Forouzan
2-1 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.
Topics discussed in this section:

2.1.1 Set of Integers
2.1.2 Binary Operations
2.1.3 Integer Division
2.1.4 Divisibility
2.1.5 Linear Diophantine Equations
File Downloaded
59
A. Forouzan
2.1.1 Set of Integers
The set of integers, denoted by Z, contains all integral

numbers (with no fraction) from negative infinity to
positive infinity (Figure 2.1).
Figure 2.1 The set of integers
File Downloaded
60
A. Forouzan
2.1.2 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.
Figure 2.2 Three binary operations for the set of integers
File Downloaded
61
A. Forouzan
2.1.2 Continued
Example 2.1
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.
File Downloaded
62
A. Forouzan
2.1.3 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
File Downloaded
63
A. Forouzan
2.1.3 Continued File Downloaded From www.Bustudymate.in
Example 2.2
Assume that a = 255 and n = 11. We can find q = 23 and R = 2 using
the division algorithm.
Figure 2.3 Example 2.2, finding the quotient and the remainder
File Downloaded
64
A. Forouzan
Restriction on integer division relation
Figure 2.4 Division algorithm for integers
File Downloaded
65
A. Forouzan
2.1.3 ContinuedFile Downloaded From www.Bustudymate.in
Example 2.3
When we use a computer or a calculator, r and q are negative

when a is negative. How can we apply the restriction that r
needs to be positive? The solution is simple, we decrement the
value of q by 1 and we add the value of n to r to make it positive.
File Downloaded
66
A. Forouzan
Figure 2.5 Graph of division alogorithm
File Downloaded
67
A. Forouzan
2.1.4 Divisbility
If a is not zero and we let r = 0 in the division relation, we

get
a=q×n
If the remainder is zero,
If the remainder is not zero,
File Downloaded
68
A. Forouzan
2.1.4 Continued
Example 2.4
a. The integer 4 divides the integer 32 because 32 = 8 × 4. We

show this as
b. The number 8 does not divide the number 42 because

42 = 5 × 8 + 2. There is a remainder, the number 2, in the
equation. We show this as
File Downloaded
69
A. Forouzan
2.1.4 Continued
Properties
Property 1: if a|1, then a = ±1.
Property 2: if a|b and b|a, then a = ±b.
Property 3: if a|b and b|c, then a|c.
Property 4: if a|b and a|c, then

a|(m × b + n × c), where m
and n are arbitrary integers
File Downloaded
70
A. Forouzan
2.1.4 Continued
Example 2.5
File Downloaded
71
A. Forouzan
2.1.4 Continued
Example 2.6
File Downloaded
72
A. Forouzan
2.1.4 Continued
Note
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).
File Downloaded
73
A. Forouzan
Figure 2.6 Common divisors of two integers
File Downloaded
74
A. Forouzan
2.1.4 Continued
Note Greatest Common Divisor
The greatest common divisor of two

positive integers is the largest integer that
can divide both integers.
Note 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
File Downloaded
75
A. Forouzan
Figure 2.7 Euclidean Algorithm
Note
When gcd (a, b) = 1, we say that a and b

are relatively prime.
File Downloaded
76
A. Forouzan
2.1.4 Continued
Note
When gcd (a, b) = 1, we say that a and b

are relatively prime.
File Downloaded
77
A. Forouzan
2.1.4 Continued
Example 2.7
Find the greatest common divisor of 2740 and 1760.
Solution
We have gcd (2740, 1760) = 20.
File Downloaded
78
A. Forouzan
Example 2.8
Find the greatest common divisor of 25 and 60.
Solution
We have gcd (25, 65) = 5.
File Downloaded
79
A. Forouzan
2.1.4 Continued
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.
File Downloaded
80
A. Forouzan
Figure 2.8.a Extended Euclidean algorithm, part a
File Downloaded
81
A. Forouzan
Figure 2.8.b Extended Euclidean algorithm, part b
File Downloaded
82
A. Forouzan
Example 2.9
Given a = 161 and b = 28, find gcd (a, b) and the values of s and t.
Solution
We get gcd (161, 28) = 7, s = −1 and t = 6.
File Downloaded
83
A. Forouzan
Example 2.10
Given a = 17 and b = 0, find gcd (a, b) and the values of s
and t.
Solution
We get gcd (17, 0) = 17, s = 1, and t = 0.
File Downloaded
84
A. Forouzan
Example 2.11
Given a = 0 and b = 45, find gcd (a, b) and the values of s

and t.
Solution
We get gcd (0, 45) = 45, s = 0, and t = 1.
File Downloaded
85
A. Forouzan
2.1.4 Continued
Linear Diophantine Equation
Note
A linear Diophantine equation of two

variables is ax + by = c.
File Downloaded
86
A. Forouzan
2.1.4 Continued
Linear Diophantine Equation
Note
Particular solution:
x0 = (c/d)s and y0 = (c/d)t
Note
General solutions:
x = x0 + k (b/d) and y = y0 − k(a/d)
where k is an integer
File Downloaded
87
A. Forouzan
Example 2.12
Find the particular and general solutions to the equation

21x + 14y = 35.
Solution
File Downloaded
88
A. Forouzan
Example 2.13
For example, imagine we want to cash a $100 check and get

some $20 and some $5 bills. We have many choices, which we
can find by solving the corresponding Diophantine equation 20x
+ 5y = 100. Since d = gcd (20, 5) = 5 and 5 | 100, the equation has
an infinite number of solutions, but only a few of them are
acceptable in this case The general solutions
with x and y nonnegative are
(0, 20), (1, 16), (2, 12), (3, 8), (4, 4), (5, 0).
File Downloaded
89
A. Forouzan
2-2 MODULAR ARITHMETIC
The division relationship (a = q × n + r) discussed in the

previous section 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.

2.2.1 Modular Operator
2.2.2 Set of Residues
2.2.3 Congruence
2.2.4 Operations in Zn
2.2.5 Addition and Multiplication Tables
2.2.6 Different Sets
File Downloaded
90
A. Forouzan
2.2.1 Modulo Operator
The modulo operator is shown as mod. The second input

(n) is called the modulus. The output r is called the
residue.
Figure 2.9 Division algorithm and modulo operator
File Downloaded
91
A. Forouzan
Example 2.14
Find the result of the following operations:
a. 27 mod 5 b. 36 mod 12
c. −18 mod 14 d. −7 mod 10
Solution
a. Dividing 27 by 5 results in r = 2
b. Dividing 36 by 12 results in r = 0.
c. Dividing −18 by 14 results in r = −4. After adding the modulus
r = 10
d. Dividing −7 by 10 results in r = −7. After adding the modulus
to −7, r = 3.
File Downloaded
92
A. Forouzan
2.2.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 Zn.
Figure 2.10 Some Zn sets
File Downloaded
93
A. Forouzan
2.2.3 Congruence
To show that two integers are congruent, we use the

congruence operator ( ≡ ). For example, we write:
File Downloaded
94
A. Forouzan
Figure 2.11 Concept of congruence
File Downloaded
95
A. Forouzan
Figure 2.12 Comparison of Z and Zn using graphs
File Downloaded
96
A. Forouzan
Example 2.15
We use modular arithmetic in our daily life; for example, we use

a clock to measure time. Our clock system uses modulo 12
arithmetic. However, instead of a 0 we use the number 12.
File Downloaded
97
A. Forouzan
2.2.4 Operation in Zn
The three binary operations that we discussed for the set Z

can also be defined for the set Zn. The result may need to
be mapped to Zn using the mod operator.
Figure 2.13 Binary operations in Zn
File Downloaded
98
A. Forouzan
Example 2.16
Perform the following operations (the inputs come from Zn):
a. Add 7 to 14 in Z15.
b. Subtract 11 from 7 in Z13.
c. Multiply 11 by 7 in Z20.
Solution
File Downloaded
99
A. Forouzan
2.2.4 Continued
Properties
File Downloaded
100
A. Forouzan
Figure 2.14 Properties of mode operator
File Downloaded
101
A. Forouzan
Exampleshows
The following 2.18 the application of the above properties:
1. (1,723,345 + 2,124,945) mod 11 = (8 + 9) mod 11 = 6
2. (1,723,345 − 2,124,945) mod 16 = (8 − 9) mod 11 = 10
3. (1,723,345 × 2,124,945) mod 16 = (8 × 9) mod 11 = 6

Or
(200+301) mod 11 = (2+4)mod11 = 6
(200-301) mod 11 = (2-4)mod11 = 9
(200*301) mod 11 = (2*4)mod11 = 8
File Downloaded
102
A. Forouzan
2.2.5 Inverses File Downloaded From www.Bustudymate.in
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).
File Downloaded
103
A. Forouzan
2.2.5 Continue File Downloaded From www.Bustudymate.in
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.
File Downloaded
104
A. Forouzan
Example 2.21
Find all additive inverse pairs in Z10.
Solution
The six pairs of additive inverses are (0, 0), (1, 9), (2, 8), (3, 7), (4,
6), and (5, 5).
File Downloaded
105
A. Forouzan
2.2.5 Continue File Downloaded From www.Bustudymate.in
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.
File Downloaded
106
A. Forouzan
Example 2.22
Find the multiplicative inverse of 8 in Z10.
Solution
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 2.23
Find all multiplicative inverses in Z10.
Solution
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.
File Downloaded
107
A. Forouzan
Example 2.24
Find all multiplicative inverse pairs in Z11.
Solution
We have seven pairs: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 9), and
(10, 10).
File Downloaded
108
A. Forouzan
2.2.5 Continued
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 Zn.
File Downloaded
109
A. Forouzan
Figure 2.15 Using extended Euclidean algorithm to

find multiplicative inverse
File Downloaded
110
A. Forouzan
Example 2.25
Solution
The gcd (26, 11) is 1; the inverse of 11 is -7 or 19.

File Downloaded
111
A. Forouzan
Example 2.26
Solution
The gcd (100, 23) is 1; the inverse of 23 is -13 or 87.

File Downloaded
112
A. Forouzan
Example 2.27
Find the inverse of 12 in Z26.
Solution
The gcd (26, 12) is 2; the inverse does not exist.
File Downloaded
113
A. Forouzan
2.2.6 Addition and Multiplication Tables
Figure 2.16 Addition and multiplication table for Z10
File Downloaded
114
A. Forouzan
2.2.7 Different Sets
Figure 2.17 Some Zn and Zn* sets
Note
We need to use Zn when additive inverses

are needed; we need to use Zn* when
multiplicative inverses are needed.
File Downloaded
115
A. Forouzan
2.2.8 Two More Sets
Cryptography often uses two more sets: Zp and Zp*. The

modulus in these two sets is a prime number.
File Downloaded
116
A. Forouzan
2-3 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.

2.3.1 Definitions
2.3.2 Operations and Relations
2.3.3 Determinants
2.3.4 Residue Matrices
File Downloaded
117
A. Forouzan
2.3.1 Definition
Figure 2.18 A matrix of size l ´ m
File Downloaded
118
A. Forouzan
2.3.1 Continued
Figure 2.19 Examples of matrices
File Downloaded
119
A. Forouzan
2.3.2 Operations and Relations
Example 2.28
Figure 2.20 shows an example of addition and

subtraction.
Figure 2.20 Addition and subtraction of matrices
File Downloaded
120
A. Forouzan
Example 2. 29
Figure 2.21 shows the product of a row matrix (1 × 3)

by a column matrix (3 × 1). The result is a matrix of size
1 × 1.
Figure 2.21 Multiplication of a row matrix by a column matrix
File Downloaded
121
A. Forouzan
Example 2. 30
Figure 2.22 shows the product of a 2 × 3 matrix by a

3 × 4 matrix. The result is a 2 × 4 matrix.
Figure 2.22 Multiplication of a 2 × 3 matrix by a 3 × 4 matrix
File Downloaded
122
A. Forouzan
Example 2. 31
Figure 2.23 shows an example of scalar multiplication.
Figure 2.23 Scalar multiplication
File Downloaded
123
A. Forouzan
2.3.3 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.
File Downloaded
124
A. Forouzan
Example 2. 32
Figure 2.24 shows how we can calculate the

determinant of a 2 × 2 matrix based on the
determinant of a 1 × 1 matrix.
Figure 2.24 Calculating the determinant of a 2 ´ 2 matrix
File Downloaded
125
A. Forouzan
Example 2. 33
Figure 2.25 shows the calculation of the determinant of

a 3 × 3 matrix.
Figure 2.25 Calculating the determinant of a 3 ´ 3 matrix
File Downloaded
126
A. Forouzan
2.3.4 Inverses
Note
Multiplicative inverses are only defined for

square matrices.
File Downloaded
127
A. Forouzan
2.3.5 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 2. 34
Figure 2.26 A residue matrix and its multiplicative inverse
File Downloaded
128
A. Forouzan
2-4 LINEAR CONGRUENCE
Cryptography often involves solving an equation or a

set of equations of one or more variables with
coefficient in Zn. This section shows how to solve
equations when the power of each variable is 1 (linear
equation).

2.4.1 Single-Variable Linear Equations
2.4.2 Set of Linear Equations
File Downloaded
129
A. Forouzan
Equations of the form ax ≡ b (mod n ) might have no

solution or a limited number of solutions.
File Downloaded
130
A. Forouzan
Example 2.35
Solve the equation 10 x ≡ 2(mod 15).
Solution
First we find the gcd (10 and 15) = 5. Since 5 does not divide 2,
we have no solution.
Example 2.36
Solve the equation 14 x ≡ 12 (mod 18).
Solution
File Downloaded
131
A. Forouzan
Example 2.37
Solve the equation 3x + 4 ≡ 6 (mod 13).
Solution
First we change the equation to the form ax ≡ b (mod n). We add
−4 (the additive inverse of 4) to both sides, which give
3x ≡ 2 (mod 13). Because gcd (3, 13) = 1, the equation has only
one solution, which is x0 = (2 × 3−1) mod 13 = 18 mod 13 = 5. We
can see that the answer satisfies the original equation:
3 × 5 + 4 ≡ 6 (mod 13).
File Downloaded
132
A. Forouzan
We can also solve a set of linear equations with the

same modulus if the matrix formed from the
coefficients of the variables is invertible.
Figure 2.27 Set of linear equations
File Downloaded
133
A. Forouzan
Example 2.38
Solve the set of following three equations:
Solution
The result is x ≡ 15 (mod 16), y ≡ 4 (mod 16), and z ≡ 14 (mod
16). We can check the answer by inserting these values into the
equations.
File Downloaded
134
A. Forouzan

CNS Unit I

Uploaded by

Copyright:

Available Formats

CNS Unit I

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CNS Unit I

Uploaded by

Copyright:

Available Formats

File Downloaded From www.Bustudymate.

BCA: III SEM: VI

Figure 1.1 Taxonomy of security goals

• Confidentiality is probably the most common aspect of

• Information needs to be changed constantly.

• The information created and stored by an organization

Security Attacks, Services and

• Security attack – Any action that compromises

• They are broadly classified as

Types of Cryptanalytic Attacks

Non Cryptanalytic Attacks

The three goals of securityconfidentiality, integrity,

• Attacks Threatening Confidentiality

Figure 1.2 Taxonomy of attacks with relation to security goals

Attacks Threatening Confidentiality

• Interception an unauthorized party gains

Snooping refers to unauthorized access to or interception of

Traffic analysis refers to obtaining some other type of

Attacks Threatening Integrity

• Modification an unauthorized party not only

Modification means that the attacker intercepts the message

Masquerading or spoofing happens when the attacker

Replaying means the attacker obtains a copy

Repudiation means that sender of the message might later

Attacks Threatening Availability

• Interruption an asset of the system is destroyed

Denial of service (DoS) is a very common attack. It may

Attacks Threatening Authenicity

• Fabrication an unauthorized party inserts

• Passive attacks are in the nature of

• Release of message contents: A telephone

• Traffic analysis: If we had encryption

• Masquerade – One entity pretends to be a

• Denial of service – Prevents or inhibits the

Table 1.1 Categorization of passive and active attacks

SERVICES AND MECHANISMS

ITU-T provides some security services and some

Figure 1.3 Security services

• The classification of security services are as

• Integrity: Ensures that only authorized parties

• Access control: Requires that access to

Figure 1.4 Security mechanisms

Table 1.2 Relation between security services and mechanisms

Mechanisms discussed in the previous sections are only

Cryptography, a word with Greek origins, means “secret

However, we use the term to refer to the science and art of

• can be characterized by:

• The number of keys used

• The way in which the plain text is processed

The word steganography, with origin in Greek, means

Example: covering data with text

• .e.g., (i) the sequence of first letters of each

Various other techniques

• Character marking – selected letters of printed

• Pin punctures – small pin punctures on

• Semagrams hide information by the use of

• Open codes hide a message in a legitimate

• Jargon code, as the name suggests, uses

• Covered or concealment ciphers hide a message