Cryptography and Network Security

2.1 Divisibility and the Division of Algorithm

1. Divisibility Concepts

Basic Definition

 We say that a nonzero integer b divides a if a = mb for some integer m

 Notation: b|a means "b divides a"
 When b|a, we say b is a divisor of a
 Example: The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24

Properties of Divisibility

1. If a|1, then a = ±1
2. If a|b and b|a, then a = ±b
3. Any b ≠ 0 divides 0
4. If a|b and b|c, then a|c (transitivity)
5. If b|g and b|h, then b|(mg + nh) for any integers m and n

Proof of Property 5:

 If b|g, then g = bg₁ for some integer g₁

 If b|h, then h = bh₁ for some integer h₁
 Therefore: mg + nh = mbg₁ + nbh₁ = b(mg₁ + nh₁)
 Thus b divides (mg + nh)

Example:

Given: b = 7, g = 14, h = 63, m = 3, n = 2

7|14 and 7|63

To show: 7|(3 × 14 + 2 × 63)

Solution: (3 × 14 + 2 × 63) = 7(3 × 2 + 2 × 9)

Therefore: 7|(7(3 × 2 + 2 × 9))

2. The Division Algorithm

Formal Statement
For any positive integer n and any integer a, there exist unique integers q (quotient) and r
(remainder) such that:

a = qn + r

where 0 ≤ r < n

Key Points

1. q = ⌊a/n⌋ (floor function - largest integer less than or equal to a/n)

2. r is called the residue
3. 0 ≤ r < n (remainder is non-negative and less than divisor)
4. q and r are unique for given a and n

Examples

1. When a = 11, n = 7:
o 11 = 1 × 7 + 4
o r = 4, q = 1
2. When a = -11, n = 7:
o -11 = (-2) × 7 + 3
o r = 3, q = -2

Visual Representation

The division algorithm can be visualized on a number line where:

 Points are marked at multiples of n: 0, n, 2n, 3n, ...

 For any a, find q where qn ≤ a < (q+1)n
 The remainder r is the distance from qn to a

Important Note

While called an "algorithm," this is actually a theorem that states the existence and uniqueness of
q and r. However, by tradition, it is referred to as the division algorithm.

2.2 The Euclidian Algorithm

1. Basic Definitions

Relatively Prime Numbers

 Two integers are relatively prime if their only common positive integer factor is 1
 Example: 8 and 15 are relatively prime because:
 o Divisors of 8: 1, 2, 4, 8
o Divisors of 15: 1, 3, 5, 15
o Only common divisor: 1

Greatest Common Divisor (GCD)

 Notation: gcd(a, b)
 Definition: Largest integer that divides both a and b
 Formal properties:
1. c is a divisor of both a and b
2. Any divisor of a and b is also a divisor of c
 Alternative definition: gcd(a, b) = max[k, such that k|a and k|b]
 Important properties:

o gcd(a, b) = gcd(a, -b) = gcd(-a, b) = gcd(-a, -b)

o gcd(a, 0) = |a|
o Two numbers are relatively prime if gcd(a, b) = 1

2. The Euclidean Algorithm

Algorithm Steps

1. Start with a ≥ b > 0

2. Apply division algorithm repeatedly:

a = q₁b + r₁ 0 ≤ r₁ < b

b = q₂r₁ + r₂ 0 ≤ r₂ < r₁

r₁ = q₃r₂ + r₃ 0 ≤ r₃ < r₂

...

rₙ₋₁ = qₙ₊₁rₙ + 0

3. The last non-zero remainder is the GCD

Flowchart Logic

1. Compare a and b
2. If a < b, swap a and b
3. Divide a by b, get remainder r
4. If r = 0, b is the GCD
5. If r ≠ 0, replace a with b and b with r
6. Repeat steps 3-5 until r = 0

Example: gcd(710, 310)

710 = 2 × 310 + 90

310 = 3 × 90 + 40

90 = 2 × 40 + 10

40 = 4 × 10 + 0

Therefore, gcd(710, 310) = 10

Large Number Example: gcd(1160718174, 316258250)

1160718174 = 3 × 316258250 + 211943424

316258250 = 1 × 211943424 + 104314826

211943424 = 2 × 104314826 + 3313772

104314826 = 31 × 3313772 + 1587894

3313772 = 2 × 1587894 + 137984

1587894 = 11 × 137984 + 70070

137984 = 1 × 70070 + 67914

70070 = 1 × 67914 + 2156

67914 = 31 × 2156 + 1078

2156 = 2 × 1078 + 0

Therefore, gcd(1160718174, 316258250) = 1078

3. Proof of Correctness

Top-Down Proof

 At each step, gcd(a, b) = gcd(b, r)

 When remainder becomes 0, previous non-zero remainder is GCD

Bottom-Up Proof

1. Last non-zero remainder (rₙ) divides rₙ₋₁

2. Using previous equation, rₙ divides rₙ₋₂
3. Continue up the chain to show rₙ divides both a and b
4. Any common divisor of a and b must divide all remainders
5. Therefore, rₙ is the greatest common divisor
2.3 Modular Arithmetic

1. Basic Concepts

The Modulus

Formula: a = ⌊a/n⌋ × n + (a mod n)

 For integer a and positive integer n, a mod n is the remainder when a is divided by n

 Examples:
o 11 mod 7 = 4
o -11 mod 7 = 3

Congruence

 Notation: a ≡ b (mod n) means a and b have same remainder when divided by n

 Examples:
o 73 ≡ 4 (mod 23)
o 21 ≡ -9 (mod 10)

Properties of Congruences

1. a ≡ b (mod n) if n|(a-b)
2. a ≡ b (mod n) implies b ≡ a (mod n)
3. a ≡ b (mod n) and b ≡ c (mod n) imply a ≡ c (mod n)

2. Modular Arithmetic Operations

Basic Properties

1. [(a mod n) + (b mod n)] mod n = (a + b) mod n

2. [(a mod n) - (b mod n)] mod n = (a - b) mod n
3. [(a mod n) × (b mod n)] mod n = (a × b) mod n

Example Calculations

11 mod 8 = 3; 15 mod 8 = 7

Addition: (11 + 15) mod 8 = 26 mod 8 = 2

Subtraction: (11 - 15) mod 8 = -4 mod 8 = 4

Multiplication: (11 × 15) mod 8 = 165 mod 8 = 5

Modular Exponentiation
Example: 11⁷ mod 13

11² = 121 ≡ 4 (mod 13)

11⁴ = (11²)² ≡ 4² ≡ 3 (mod 13)

11⁷ = 11 × 11² × 11⁴ ≡ 11 × 4 × 3 ≡ 132 ≡ 2 (mod 13)

3. Residue Classes

Definition

 Zn = {0, 1, ..., (n-1)} is the set of residues modulo n

 Each element represents a residue class [r] = {a: a ≡ r (mod n)}

Example (mod 4)

[0] = {..., -8, -4, 0, 4, 8, ...}

[1] = {..., -7, -3, 1, 5, 9, ...}

[2] = {..., -6, -2, 2, 6, 10, ...}

[3] = {..., -5, -1, 3, 7, 11, ...}

4. Special Properties

Multiplicative Inverses

 An integer a has a multiplicative inverse in Zn if and only if gcd(a,n) = 1

 Example in Z8:
o 1, 3, 5, 7 have multiplicative inverses
o 2, 4, 6 do not have multiplicative inverses

Important Theorems

1. If (a + b) ≡ (a + c) (mod n), then b ≡ c (mod n)

2. If (a × b) ≡ (a × c) (mod n), then b ≡ c (mod n) only if gcd(a,n) = 1

5. Extended Euclidean Algorithm

Purpose

 Finds x, y, and d that satisfy: ax + by = d = gcd(a,b)

Example with a = 1759, b = 550

Properties

 Values of ax + by are always multiples of gcd(a,b)

 Smallest positive value of ax + by equals gcd(a,b)

2.4 Prime Numbers

1. Basic Definition

 A prime number p is an integer > 1 whose only divisors are ±1 and ±p

 Table 2.5 shows all prime numbers less than 2000
 Distribution pattern: Primes become less frequent as numbers get larger

2. Fundamental Theorem of Arithmetic

Basic Statement

 Every integer a > 1 can be factored uniquely as: a = p₁ᵃ¹ × p₂ᵃ² × ... × pₜᵃᵗ
 Where:
o p₁ < p₂ < ... < pₜ are prime numbers
o Each aᵢ is a positive integer

Examples

91 = 7 × 13

3600 = 2⁴ × 3² × 5²

11011 = 7 × 11² × 13

3. Prime Factor Notation

Alternative Expression
 all p ∈ P
 For set P of all prime numbers, any positive integer a can be written as: a = ∏(p^ap) for

 Most exponents ap will be 0

 Only need to list nonzero exponents

Examples

12 is represented by {a₂ = 2, a₃ = 1}

18 is represented by {a₂ = 1, a₃ = 2}

91 is represented by {a₇ = 1, a₁₃ = 1}

4. Operations with Prime Factorizations

Multiplication

 When multiplying numbers, add corresponding prime exponents

 For k = ab: kp = ap + bp for all prime p

Example

k = 12 × 18

= (2² × 3) × (2 × 3²)

= 2³ × 3³

= 216

Where:

k₂ = 2 + 1 = 3

k₃ = 1 + 2 = 3

5. Division Properties

Divisibility Rule

 For a|b to be true: ap ≤ bp must hold for all prime numbers p

Example

12|36 because:

12 = 2² × 3

36 = 2² × 3²
Check:

a₂ = 2 = b₂

a₃ = 1 ≤ 2 = b₃

6. Greatest Common Divisor with Prime Factorizations

Rule

 For k = gcd(a,b): kp = min(ap, bp) for all prime p

Example

300 = 2² × 3¹ × 5²

18 = 2¹ × 3²

gcd(18,300) = 2¹ × 3¹ × 5⁰ = 6

Important Note

While this method is theoretically elegant, it's not practical for large numbers since finding prime
factors of large numbers is computationally difficult.

2.5 Fermat’s and Euler’s Theorems

1. Fermat's Theorem

Basic Statement

 If p is prime and a is a positive integer not divisible by p:

o aᵖ⁻¹ ≡ 1 (mod p)

Alternative Form

 For any positive integer a and prime p:

o aᵖ ≡ a (mod p)
o Note: This form doesn't require a to be relatively prime to p

Examples

For a = 7, p = 19:
7² = 49 ≡ 11 (mod 19)

7⁴ ≡ 121 ≡ 7 (mod 19)

7⁸ ≡ 49 ≡ 11 (mod 19)

7¹⁶ ≡ 121 ≡ 7 (mod 19)

7¹⁸ = 7¹⁶ × 7² ≡ 7 × 11 ≡ 1 (mod 19)

2. Euler's Totient Function φ(n)

Definition

 φ(n) = number of positive integers less than n and relatively prime to n

 By convention, φ(1) = 1

Properties

1. For prime p: φ(p) = p - 1

2. For distinct primes p and q: φ(pq) = φ(p) × φ(q) = (p-1)(q-1)

Examples

φ(37) = 36 (since 37 is prime)

φ(35) = 24 (numbers relatively prime to 35:

1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34)

φ(21) = φ(3) × φ(7) = 2 × 6 = 12

3. Euler's Theorem

Basic Statement

 For a and n that are relatively prime:

o aᶠ⁽ⁿ⁾ ≡ 1 (mod n)

Alternative Form

 For any a and n:

o aᶠ⁽ⁿ⁾⁺¹ ≡ a (mod n)
o Note: This form doesn't require a to be relatively prime to n

Examples

a = 3, n = 10:
φ(10) = 4

3⁴ = 81 ≡ 1 (mod 10)

a = 2, n = 11:

φ(11) = 10

2¹⁰ = 1024 ≡ 1 (mod 11)

4. Proof Components

For Fermat's Theorem

1. Consider set {1, 2, ..., p-1}

2. Multiply each by a mod p
3. Show resulting set is a permutation
4. Multiply all elements and compare

For Euler's Theorem

1. Consider set R of numbers relatively prime to n

2. Multiply each by a mod n
3. Show resulting set S is a permutation of R
4. Use same multiplication principle as Fermat's proof

5. Applications

 These theorems play crucial roles in:

o Public-key cryptography
o RSA algorithm
o Modular exponentiation
o Primality testing

2.6 Testing for Primality

1. Introduction

 Testing large numbers for primality is crucial for cryptographic algorithms

 No simple yet efficient method exists
 Most popular methods are probabilistic rather than deterministic

2. Miller-Rabin Algorithm
Fundamental Properties

1. Any odd integer n ≥ 3 can be expressed as:

o n - 1 = 2ᵏq where k > 0 and q is odd
2. Two key properties for prime numbers:
o Property 1: If p is prime and a < p, then a² mod p = 1 if and only if a mod p = ±1
o Property 2: For prime p > 2, where p - 1 = 2ᵏq, and 1 < a < p - 1, one of these
must be true:
 aᵍ ≡ 1 (mod p)
 a²ʲ⁻¹ᵍ ≡ -1 (mod p) for some j where 1 ≤ j ≤ k

Algorithm (TEST)

TEST(n)

1. Find k, q where n - 1 = 2ᵏq (q is odd)

2. Select random a, 1 < a < n - 1

3. if aᵍ mod n = 1 return "inconclusive"

4. for j = 0 to k - 1 do

5. if a²ʲᵍ mod n = n - 1 return "inconclusive"

6. return "composite"

Examples

1. Testing n = 29 (prime):

k = 2, q = 7

With a = 10:

10⁷ mod 29 = 17

(10⁷)² mod 29 = 28 (-1 mod 29)

Result: Inconclusive (correct)

2. Testing n = 221 (composite):

k = 2, q = 55

With a = 5:

5⁵⁵ mod 221 = 112

(5⁵⁵)² mod 221 = 168

Result: Composite (correct)

With a = 21:

21⁵⁵ mod 221 = 200

(21⁵⁵)² mod 221 = 220

Result: Inconclusive (false positive)

Reliability

 For composite n, probability of "inconclusive" result is < 1/4

 With t different values of a, probability of false positive is < (1/4)ᵗ
 For t = 10, probability of error < 10⁻⁶

3. The AKS Algorithm

 First deterministic polynomial-time primality test (2002)

 Theoretically significant but less efficient than Miller-Rabin
 Not widely used in practice

4. Distribution of Primes

Prime Number Theorem

 Primes near n are spaced approximately ln(n) integers apart

 When seeking primes, average number of trials needed ≈ 0.5 ln(n)
 Example: For prime near 2²⁰⁰, approximately 69 trials needed

Interesting Facts

 Prime gaps can be very small:

o 1,000,000,000,061 and 1,000,000,000,063 are consecutive primes
 Or very large:
o 1001! + 2 through 1001! + 1001 are all composite

Practical Implications

 Understanding prime distribution helps in:

o Estimating time needed to find primes
o Setting parameters for cryptographic algorithms
o Optimizing primality testing procedures
2.7 The Chinese Remainder Theorem

1. Basic Concept

 Allows reconstruction of integers from their residues modulo relatively prime moduli
 Originally discovered by Chinese mathematician Sun-Tsu (circa 100 A.D.)

Simple Example

In Z₁₀ (integers 0-9), using moduli 2 and 5:

Given: x mod 2 = 0 and x mod 5 = 3

Solution: x = 8 (unique in Z₁₀)

2. Formal Statement

Prerequisites

 Let M = m₁ × m₂ × ... × mₖ
 Where all mᵢ are pairwise relatively prime (gcd(mᵢ,mⱼ) = 1 for i ≠ j)

Mapping

A ↔ (a₁, a₂, ..., aₖ) where:

A ∈ ZM
aᵢ ∈ Zmᵢ


 aᵢ = A mod mᵢ for 1 ≤ i ≤ k

3. Main Assertions

First Assertion

 One-to-one correspondence between:

o ZM and Zm₁ × Zm₂ × ... × Zmₖ
 Each integer A (0 ≤ A < M) has unique k-tuple representation
 Each valid k-tuple represents unique integer in ZM

Second Assertion

 Operations on ZM elements can be performed independently on corresponding tuple

elements
 Supports addition, subtraction, and multiplication
4. Construction Method

Computing A from Residues

1. Calculate Mᵢ = M/mᵢ for each i

2. Find cᵢ = Mᵢ × (Mᵢ⁻¹ mod mᵢ)
3. Compute A = (Σ aᵢcᵢ) mod M

Arithmetic Operations

If A ↔ (a₁, a₂, ..., aₖ) and B ↔ (b₁, b₂, ..., bₖ):

(A + B) mod M ↔ ((a₁ + b₁) mod m₁, ..., (aₖ + bₖ) mod mₖ)

(A - B) mod M ↔ ((a₁ - b₁) mod m₁, ..., (aₖ - bₖ) mod mₖ)

(A × B) mod M ↔ ((a₁ × b₁) mod m₁, ..., (aₖ × bₖ) mod mₖ)

5. Practical Example

Setup

m₁ = 37, m₂ = 49

M = 1813

A = 973

Conversion to Tuple

973 ↔ (11, 42) because:

973 mod 37 = 11

973 mod 49 = 42

Addition Example

Add 678 to 973:

678 ↔ (12, 41)

(11, 42) + (12, 41) = (23, 34)

Verify: 1651 = 973 + 678 mod 1813

Multiplication Example
Multiply 1651 by 73:

(23, 34) × 73 = (14, 32)

Verify: 865 = 1651 × 73 mod 1813

6. Applications

 Efficient handling of large numbers

 Useful for numbers > 150 digits
 Requires known factorization of modulus
 Common in cryptographic algorithms

2.8 Discrete Logarithms

1. Powers of Integers Modulo n

Properties from Euler's Theorem

 For relatively prime a and n: aᶠ⁽ⁿ⁾ ≡ 1 (mod n)

 More generally: aᵐ ≡ 1 (mod n)

Order of an Integer

The least positive exponent m for which aᵐ ≡ 1 (mod n) is called:

 The order of a (mod n)

 The exponent to which a belongs (mod n)
 The length of the period generated by a

Example: Powers of 7 mod 19

7¹ ≡ 7 (mod 19)

7² = 49 ≡ 11 (mod 19)

7³ = 343 ≡ 1 (mod 19)

7⁴ = 2401 ≡ 7 (mod 19)

7⁵ = 16807 ≡ 11 (mod 19)

Period length is 3 since 7³ ≡ 1 (mod 19)

2. Primitive Roots
Definition

 A primitive root of n is an integer whose powers generate all numbers coprime to n

 The order of a primitive root equals φ(n)

Important Properties

1. All sequences of powers end in 1

2. Sequence length divides φ(n)
3. For prime p, primitive root a generates all numbers 1 to p-1

Existence

Primitive roots exist only for integers of the form:

 2, 4, pᵃ, or 2pᵃ (where p is odd prime)

3. Discrete Logarithms

Definition

 For prime p and primitive root a:

 If b ≡ aⁱ (mod p), then i = dlogₐ,ₚ(b)
 i is unique for 0 ≤ i ≤ p-1

Basic Properties

dlogₐ,ₚ(1) = 0

dlogₐ,ₚ(a) = 1

Logarithm Properties (mod p)

dlogₐ,ₚ(xy) ≡ [dlogₐ,ₚ(x) + dlogₐ,ₚ(y)] (mod φ(p))

dlogₐ,ₚ(yʳ) ≡ [r × dlogₐ,ₚ(y)] (mod φ(p))

4. Computational Aspects

Forward Calculation

 Given g, x, p: computing y = gˣ mod p is straightforward

 Can be done efficiently with repeated squaring

Inverse Calculation (Discrete Log Problem)

  Given y, g, p: finding x where y = gˣ mod p is computationally hard
 Best known algorithm complexity: e((ln p)¹/³(ln(ln p))²/³)
 Difficulty comparable to prime factorization

5. Applications

 Fundamental to various public-key algorithms:

o Diffie-Hellman key exchange
o Digital Signature Algorithm (DSA)
o Other cryptographic protocols

6. Example Tables

The reviewer includes reference to Tables 2.7 and 2.8 showing:

 Powers of integers modulo 19

 Discrete logarithms for various bases modulo 19