Cryptography and Network Security Notes U-1

  

Security Goals

1. Confidentiality

• Need to Protect Storage and Transmission of information

• It specifies that only sender and intended recipient(s) should be able to access the contents of message.

• E.g.: e-mail send by person A to person B.

 

2. Integrity

• Integrity means that changes need to be done only by authorized entities and through authorized mechanisms.

• E.g: Updating bank account information

3. 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.

• E.g Services of web server are always available.

 

 

• Cryptographic attacks can be broadly categorized into two distinct types:

1. Cryptanalytic

2. Non-cryptanalytic

 

1. Cryptanalytic Attacks

• Combination of statistical and algebraic techniques aimed to learn the secret key.

• Opponent knows Encryption algorithm, ciphertext, plaintext and ciphertext combinations, etc.

• Using these info, opponent performs analysis and guesses key.

• These attacks exploits a weakness or a flaw in the design.

 

Attacks  with relation to security goals

 

a. Snooping refers to unauthorized access to or interception of data.

b. Traffic analysis refers to obtaining some other type of information by monitoring online traffic.

 

a. Modification means that the attacker intercepts the message and changes it.

b. Masquerading or spoofing happens when the attacker impersonates somebody else.

c. 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.

 

3. Attacks Threatening Availability

a. Denial of service (DoS) is a very common attack. It may slow down or totally interrupt the service of a system.

 

• Passive Versus Active Attacks

1. Passive Attacks

• The attacker goal is to obtain information only. The attack does not modify the data or harm the system.

• The system continues with its normal operation.

• It may harm either sender or receiver.

• Two types of passive attacks are the snooping attack and traffic analysis.

• It is difficult to detect. And can be prevented using encipherment.

 

2. Active attack:

• May change the data or harm the system. Attacks that threaten the integrity and availability are active attacks.

• Easier to detect than to prevent.

 

Security services

It is a communication service that enhance security of data processing systems and information transfers of an organization.

 

ITU-T X.800 defines security services in 5 major categories

• Data Confidentiality

Protection of data from unauthorized disclosure

• Data Integrity

Assurance that data received is as sent by an authorized entity

• Authentication

Assurance that the communicating entity is the one claimed

• Access Control

Prevention of the unauthorized use of a resource

• Non-Repudiation

Protection against denial by one of the parties in a communication

 

SECURITY MECHANISMS

A process that is designed to detect, prevent or recover from

a security attack.

 

• Encipherment: = encryption algorithms

– Converting data into form that is not readable

– Can provide data and traffic flow confidentiality.

• Data integrity: To assure the integrity of a data unit.

– Protection against modification of data.

– Provide data integrity and origin authentication services. Also basis of some authentication exchange mechanisms.

• Digital signatures: To check authenticity and integrity of data

– Signing procedure (private),

– Verification procedure (public)

– Can provide non-repudiation, origin authentication and data integrity services.

 

• Authentication exchange: : To ensure identity of an entity by means of info exchange.

– Provide entity authentication service.

• Traffic padding: Insertion of bits into gaps in data stream to frustrate traffic analysis.

– Provides traffic flow confidentiality.

• Routing control: Selection of secure routes

– Used to prevent sensitive data using insecure channels.

– E.g. route might be chosen to use only physically secure network

components.

• Notarisation: Use of trusted third party for data exchange

– Integrity, origin and/or destination of data can be guaranteed by using

a 3rd party trusted notary.

• Access Control: Enforcing access rights to resources

– A server using client information to decide whether to grant access to

resources

 

Chapter 2

Mathematics of Cryptography

Part I: Modular Arithmetic, Congruence,

and Matrices

 

 

 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

 

2-1 INTEGER 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

 

 

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

 

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

 

 

 

 

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

 

 

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

 

 

 

2.1.3 Continued

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.

 

 

 

 

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,  

 

 

 

 

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

 

 

 

 

 

 

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).

 

 

 

 

 

Euclidean Algorithm

 

 

 

 

2.1.4 Continued

Figure 2.7 Euclidean Algorithm

 

 

 

 

 

Find the greatest common divisor of 2740 and 1760. Solution

We have gcd (2740, 1760) = 20.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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.

Topics discussed in this section:

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

 

 

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

 

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.

 

-7 mod 10

 

27 mod 5

 

10 -7 0 5

0

2

-7

 

 

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

 

 

To show that two integers are congruent, we use the congruence operator ( ≡ ). For example, we write:

2 mod 10 = 12 mod 10

2 ≡ 12 mod 10

 

 

 

 

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

 

 

 

 

 

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

 

 

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.

 

 

Perform  the following  operations  (the inputs  come  from

either Z or Zn):

a. Add 17 to 27 in Z14.

b. Subtract 43 from 12 in Z13.

c. Multiply 123 by −10 in Z19.

 

 

 

 

 

 

 

Exponentiation:

 Exponentiation is done by repeated multiplication, as in ordinary arithmetic.

 

 

 

We have been told in arithmetic that the remainder of an integer divided by 3 is the same as the remainder of the sum of its decimal digits. We write an integer as the sum of its digits multiplied by the powers of 10.

 

2.2.5 Inverses

When we are working in modular arithmetic, we often need to find the inverse of a number relative to an operation. We are normally looking for an additive inverse (relative to an addition operation) or a multiplicative inverse (relative to a multiplication operation).

 

 

 

 

 

2 8 -- mod 10

2+8 = 10 (mod 10) = 0

7, 2  --- mod 10

7+2 = 9 mod 10 = 9

5 8 ---  mod 10

5+8 = 13 mod 10 = 3

 

2.2.5 Continue

Multiplicative Inverse

 

a x (1/a) = 1

 

In Zn, two numbers a and b are the multiplicative inverse of

each other if

Note

In modular arithmetic, an integer may or may not have a multiplicative inverse.

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

 

 

 

Example 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 

 

2.2.5 Continued

Find all multiplicative inverse pairs in Z11. Solution

We have seven pairs: (1, 1), (2, 6), (3, 4), (5, 9), (7, 8), (9, 5),

and (10, 10).

 

Note

The extended Euclidean algorithm finds the multiplicative inverses of b in Zn when n and b are given and

gcd (n, b) = 1.

The multiplicative inverse of b is the value of t after being mapped to Zn.

 

Figure 2.15 Using extended Euclidean algorithm to

find multiplicative inverse

 

 

Find the multiplicative inverse of 11 in Z26.

Solution

 

 

Find the multiplicative inverse of 23 in Z100.

Solution

 

 

 

 

 

 

 

 

 

2-3 MATRICES

Topics discussed in this section:

2.3.1 Definitions

2.3.2 Operations and Relations

2.3.3 Determinants

2.3.4 Residue Matrices

 

 

Figure 2.18 A matrix of size l  m

 

 

Figure 2.19 Examples of matrices

 

 

Figure 2.20 Addition and subtraction of matrices

 

 

Figure 2.21 Multiplication of a row matrix by a column matrix

 

 

Figure 2.22 Multiplication of a 2 × 3 matrix by a 3 × 4 matrix

 

 

Figure 2.23 Scalar multiplication

 

The determinant of a square matrix A of size m × m denoted as det (A) is a scalar calculated recursively as shown below:

 

 

Figure 2.24 Calculating the determinant of a 2  2 matrix

 

 

Figure 2.25 Calculating the determinant of a 3  3 matrix

 

 

 

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

 

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).

Topics discussed in this section:

2.4.1 Single-Variable Linear Equations

2.4.2 Set of Linear Equations

 

 

 

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 

 

 

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).

 

2.4.2 Single-Variable Linear Equations

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

 

 

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.