Number Theory and Cryptography – Study Guide

Number Theory and Cryptography – Comprehensive Report

Number Theory and Cryptography

Chapter 4: A Comprehensive Study Guide

📑 Table of Contents

1. Divisibility and Modular Arithmetic

📌 Definition: Division

Let a, b ∈ ℤ with a ≠ 0.

a | b (read as “a divides b”) if there exists an integer c such that b = ac.

  • a is called a factor or divisor of b
  • b is called a multiple of a
  • a ∤ b denotes that a does not divide b

💡 Examples

  • 3 | -12 is TRUE because -12 = 3 × (-4)
  • 3 | 7 is FALSE (a bigger number cannot divide a smaller positive number)
  • 77 | 7 is FALSE
  • 7 | 77 is TRUE because 77 = 7 × 11
  • 24 | 24 is TRUE because 24 = 24 × 1
  • 0 | 24 is FALSE (only 0 is divisible by 0)
  • 24 | 0 is TRUE (0 is divisible by every number: 0 = 24 × 0)

🎯 Properties of the Divides Relation

For all integers a, b, c ∈ ℤ:

  1. (a|b ∧ a|c) → a|(b+c)
    Example: 3|12 ∧ 3|9 → 3|(12+9) = 3|21 = 7
  2. a|b → a|bc
    Example: 2|6 → 2|(6×3) = 2|18 = 9
  3. (a|b ∧ b|c) → a|c
    Example: 4|8 ∧ 8|64 → 4|64 = 16

2. Primes and Greatest Common Divisor

🔢 Prime and Composite Numbers

Prime Number

A positive integer p > 1 is prime if the only positive factors of p are 1 and p.

Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29…

Composite Number

Non-prime integers greater than 1 are called composite because they can be composed by multiplying two integers greater than 1.

🎯 Fundamental Theorem of Arithmetic

Prime Factorization: Every positive integer greater than 1 has a unique representation as a prime or as the product of two or more primes where the prime factors are written in order of increasing size.

Examples:

  • 100 = 2·2·5·5 = 2² × 5²
  • 13 = 13 (prime)
  • 1024 = 2·2·2·2·2·2·2·2·2·2 = 2¹⁰

🔍 Prime Testing

Testing for Primality

Theorem: If n is a composite integer, then n has a prime divisor ≤ √n

Method: An integer n is prime if it is not divisible by any prime ≤ √n

💡 Example: Test if 139 and 143 are primes

Step 1: Calculate √n

  • √139 ≈ 11.8, √143 ≈ 12.0

Step 2: List all primes ≤ √n: 2, 3, 5, 7, 11

Step 3: Check divisibility

  • 139: Not divisible by 2, 3, 5, 7, 11 → PRIME
  • 143: Using alternating sum trick: 1-4+3 = 0 → divisible by 11 (143 = 11 × 13) → COMPOSITE

🔗 Greatest Common Divisor (GCD)

Definition

The greatest common divisor gcd(a,b) of integers a, b (not both 0) is the largest (most positive) integer d that is a divisor both of a and of b.

📋 Two Methods to Find GCD

Method 1: List All Divisors

Find gcd(24, 36)

  • Divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24
  • Divisors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
  • Common divisors: 1, 2, 3, 4, 6, 12
  • MAXIMUM = 12
  • ∴ gcd(24, 36) = 12

Method 2: Prime Factorization (Take the MIN)

Find gcd(24, 36)

  • 24 = 2³ × 3¹
  • 36 = 2² × 3²
  • gcd(24, 36) = 2^min(3,2) × 3^min(1,2) = 2² × 3¹ = 12

Find gcd(98, 420)

  • 98 = 2 × 49 = 2¹ × 7²
  • 420 = 2 × 210 = 2 × 2 × 105 = 2² × 3 × 5 × 7
  • Common factors: 2 × 7
  • gcd(98, 420) = 14

🔄 Relatively Prime

Two integers a and b are said to be relatively prime if gcd(a,b) = 1, meaning they have no prime common divisors.

Examples:

  • gcd(11, 77) = 11 → NOT relatively prime
  • gcd(33, 77) = 11 → NOT relatively prime
  • gcd(24, 36) = 12 → NOT relatively prime
  • gcd(24, 25) = 1 → RELATIVELY PRIME

📝 Note: A prime number is relatively prime to all other numbers which it doesn’t divide.

📐 Least Common Multiple (LCM)

The least common multiple lcm(a,b) of positive integers a, b is the smallest positive integer that is a multiple both of a and of b.

Using Prime Factorization (Take the MAX):
lcm(a, b) = product of all prime factors with maximum exponents

💡 Examples

Find lcm(6, 10)

  • 6 = 2 × 3
  • 10 = 2 × 5
  • lcm(6, 10) = 2 × 3 × 5 = 30

Find lcm(24, 36)

  • 24 = 2³ × 3¹
  • 36 = 2² × 3²
  • lcm(24, 36) = 2³ × 3² = 8 × 9 = 72

3. Division Algorithm and Modular Arithmetic

➗ The Division Algorithm

Let a be an integer and d a positive integer. Then there are unique integers q and r such that:

a = d × q + r, where 0 ≤ r < d
  • d is called the divisor
  • a is called the dividend
  • q is the quotient: q = a div d
  • r is the remainder: r = a mod d

💡 Examples

What are the quotient and remainder when 101 is divided by 11?

  • 101 = 11 × 9 + 2
  • q = 9, r = 2

What are the quotient and remainder when -11 is divided by 3?

  • -11 = 3 × (-4) + 1
  • q = -4, r = 1
  • Note: -11 ≠ 3 × (-3) – 2 because r ≥ 0 (can’t be negative)

🔢 The Modulo Function

The mod function returns the remainder when an integer is divided by a positive integer.

a mod d = r, where 0 ≤ r < d

💡 Examples

  • 113 mod 24:
    • 24 | 113
    • 113 = 24 × 4 + 17
    • 113 mod 24 = 17
  • -29 mod 7:
    • 7 | -29
    • -29 = 7 × (-5) + 6
    • -29 mod 7 = 6

⏰ Practical Application: Time Calculation

💡 What time will it be 50 hours from 11 am?

Method 1: Step by step

  • After 24 hours → 11 am
  • After 48 hours (another 24) → 11 am
  • After 50 hours (2 more) → 1 pm (13:00)

Method 2: Using modulo

  • (11 + 50) mod 24 = 61 mod 24 = 13
  • Answer: 13:00 (1 pm)

Converting 24-hour to 12-hour clock:

  • 13 mod 12 = 1 (1 pm)
  • 23 mod 12 = 11 (11 pm)

≡ Modular Congruence

Let a, b ∈ ℤ, m ∈ ℤ⁺. Then a is congruent to b modulo m, written as:

a ≡ b (mod m)

if and only if:

  1. a mod m = b mod m, OR
  2. m | (a – b), i.e., (a – b) mod m = 0

💡 Is 17 congruent to 5 modulo 6?

  • 17 mod 6 = 5 and 5 mod 6 = 5 ✓
  • 6 | (17-5) ↔ 6 | 12 where 12/6 = 2 ✓
  • Therefore: 17 ≡ 5 (mod 6)

💡 Is 24 congruent to 14 modulo 6?

  • 24 mod 6 = 0 and 14 mod 6 = 2 ✗
  • 6 ∤ (24-14) ↔ 6 ∤ 10 ✗
  • Therefore: 24 ≢ 14 (mod 6)

🧮 Congruence Theorems

Let a, b, c, d ∈ ℤ, m ∈ ℤ⁺. If a ≡ b (mod m) and c ≡ d (mod m), then:

  • a + c ≡ b + d (mod m)
  • ac ≡ bd (mod m)

💡 Example

Let 7 ≡ 2 (mod 5) and 11 ≡ 1 (mod 5)

Then:

  • (7 + 11) ≡ (2 + 1) (mod 5) ↔ 18 ≡ 3 (mod 5) ✓
  • (7 × 11) ≡ (2 × 1) (mod 5) ↔ 77 ≡ 2 (mod 5) ✓

🔐 4. Cryptography Fundamentals

What is Cryptography?

Cryptography is the science that applies complex mathematics and logic to design strong encryption methods. It is both a science and an art that allows people to maintain confidence in the electronic world.

🎯 Key Concepts

  • Plaintext: The original readable message
  • Ciphertext: The encrypted message
  • Encryption: The process of converting plaintext to ciphertext
  • Decryption: The process of converting ciphertext back to plaintext
  • Key: A secret parameter used in encryption/decryption

🏛️ Cryptosystem Definition

A cryptosystem is a five-tuple (P, C, K, E, D), where:

  • P is the set of plaintext strings
  • C is the set of ciphertext strings
  • K is the keyspace (set of all possible keys)
  • E is the set of encryption functions
  • D is the set of decryption functions
Dk(Ek(p)) = p, for all plaintext strings p

🔑 5. Symmetric Encryption (Single-Key Encryption)

Symmetric encryption is the universal technique for providing confidentiality where the same key is used for both encryption and decryption.

Common Algorithms: DES, Triple DES, AES

📝 Requirements for Secure Use

  1. Need a strong encryption algorithm
  2. Sender and receiver must have obtained copies of the secret key in a secure fashion
  3. Must keep the key secure

🏛️ Caesar Cipher

Julius Caesar created secret messages by shifting each letter three letters forward in the alphabet (sending the last three letters to the first three letters).

Example: B → E, X → A

📋 Caesar Cipher Process

  1. Replace each letter by an integer from Z₂₆ (0 to 25), representing one less than its position in the alphabet
    • A=0, B=1, C=2, …, Z=25
  2. Apply the encryption function: f(p) = (p + 3) mod 26
  3. Replace each integer p by the letter with position p + 1 in the alphabet

💡 Example: Encrypt “MEET YOU IN THE PARK”

Step 1: Convert to numbers

  • M E E T → 12 4 4 19
  • Y O U → 24 14 20
  • I N → 8 13
  • T H E → 19 7 4
  • P A R K → 15 0 17 10

Step 2: Apply f(p) = (p + 3) mod 26

  • 15 7 7 22 1 17 23 11 16 22 10 7 18 3 20 13

Step 3: Convert back to letters

  • Encrypted message: “PHHW BRX LQ WKH SDUN”

🔄 Shift Ciphers

The Caesar cipher is one of a family of ciphers called shift ciphers. Letters can be shifted by any integer k.

Encryption: f(p) = (p + k) mod 26
Decryption: f⁻¹(p) = (p – k) mod 26

The integer k is called the key.

💡 Example: Encrypt “STOP GLOBAL WARMING” with k = 11

Step 1: Convert to numbers

  • 18 19 14 15 6 11 14 1 0 11 22 0 17 12 8 13 6

Step 2: Apply f(p) = (p + 11) mod 26

  • 3 4 25 0 17 22 25 12 11 22 7 11 2 23 19 24 17

Step 3: Convert back to letters

  • Encrypted: “DEZA RWZMLW HLCXTYR”

💡 Example: Decrypt “LEWLYPLUJL PZ H NYLHA ALHJOLY” with k = 7

Step 1: Convert to numbers

  • 11 4 22 11 24 15 11 20 9 11 15 25 7 13 24 11 7 0 0 11 7 9 14 11 24

Step 2: Apply f⁻¹(p) = (p – 7) mod 26

  • 4 23 15 4 17 8 4 13 2 4 8 18 0 6 17 4 0 19 19 4 0 2 7 4 17

Step 3: Convert back to letters

  • Decrypted: “EXPERIENCE IS A GREAT TEACHER”

🔍 Cryptanalysis

Cryptanalysis (breaking codes) is the process of recovering plaintext from ciphertext without knowledge of both the encryption method and the key.

🛠️ Tools for Cryptanalysis

Relative Frequencies of Letters in English:

  • E: 13% (most common)
  • T: 9%
  • A, O: 8%
  • I, N, S: 7%
  • H, R: 6%

Method:

  1. Find the frequency of letters in the ciphertext
  2. Hypothesize that the most frequent letter corresponds to E
  3. Calculate the shift value k
  4. Decrypt the entire message
  5. If it doesn’t make sense, try T, then A, etc.

📊 Letter-Number Correspondence

LetterABCDEFGHIJKLM
Number0123456789101112
LetterNOPQRSTUVWXYZ
Number13141516171819202122232425

🔓 6. Public Key Cryptography – RSA Cryptosystem

What is Public Key Cryptography?

In public key cryptosystems, knowing how to encrypt a message does not help one to decrypt the message. Therefore, everyone can have a publicly known encryption key. The only key that needs to be kept secret is the decryption key.

🏆 The RSA System

Introduced in 1976 by Ronald Rivest, Adi Shamir, and Leonard Adleman at MIT. Also discovered earlier by Clifford Cocks (UK government, classified).

🔑 RSA Key Generation

📋 RSA Algorithm Steps

  1. Select two prime numbers p and q where p ≠ q
    • Typically very large primes (200+ digits each)
  2. Calculate n = p × q
    • n is the modulus (approximately 400 digits)
  3. Calculate Φ(n) = (p-1) × (q-1)
    • Euler’s totient function
  4. Select e such that:
    • e is relatively prime to Φ(n): gcd(e, Φ(n)) = 1
    • 1 < e < Φ(n)
  5. Calculate d = e⁻¹ mod Φ(n)
    • Or: e × d ≡ 1 (mod Φ(n))
  6. Public key = {e, n}
  7. Private key = {d, n}
Encryption: C = Pe mod n
Decryption: P = Cd mod n
Where P < n

💡 Complete RSA Examples

Example 1: p=7, q=11, e=5, plaintext=6

  1. p = 7, q = 11
  2. n = p × q = 7 × 11 = 119
  3. Φ(n) = (7-1) × (11-1) = 6 × 10 = 96
  4. Public key e = 5 (given)
  5. Calculate d:
    • d = ((Φ(n) × i) + 1) / e
    • d = (96×1+1)/5 = 19.4 ✗
    • d = (96×2+1)/5 = 38.6 ✗
    • d = (96×3+1)/5 = 57.8 ✗
    • d = (96×4+1)/5 = 77 ✓
  6. Public key = {5, 119}, Private key = {77, 119}
  7. Encryption: C = 6⁵ mod 119 = 7776 mod 119 = 41
  8. Decryption: P = 41⁷⁷ mod 119 = 6 ✓

Example 2: p=5, q=7, e=11, plaintext=2

  1. p = 5, q = 7
  2. n = 5 × 7 = 35
  3. Φ(n) = 4 × 6 = 24
  4. e = 11
  5. d = 11 (since 11 × 11 mod 24 = 1)
  6. Public key = {11, 35}, Private key = {11, 35}
  7. Encryption: C = 2¹¹ mod 35 = 2048 mod 35 = 18
  8. Decryption: P = 18¹¹ mod 35 = 2 ✓

Example 3: p=17, q=11, e=7, plaintext=5

  1. p = 17, q = 11
  2. n = 17 × 11 = 187
  3. Φ(n) = 16 × 10 = 160
  4. e = 7
  5. d = 23 (calculate: (160×i+1)/7 until integer)
  6. Public key = {7, 187}, Private key = {23, 187}
  7. Encryption: C = 5⁷ mod 187 = 78125 mod 187 = 146
  8. Decryption: P = 146²³ mod 187 = 5 ✓

Example 4: p=3, q=11, e=3, plaintext=(00111011)₂ = 59

  1. p = 3, q = 11
  2. n = 3 × 11 = 33
  3. Φ(n) = 2 × 10 = 20
  4. e = 3
  5. d = 7
  6. Public key = {3, 33}, Private key = {7, 33}
  7. Encryption: C = 59³ mod 33 = 205379 mod 33 = 20
  8. Decryption: P = 20⁷ mod 33 = 1280000000 mod 33 = 26

Example 5: p=13, q=17, e=19, plaintext=12

  1. p = 13, q = 17
  2. n = 13 × 17 = 221
  3. Φ(n) = 12 × 16 = 192
  4. e = 19
  5. d = 91
  6. Public key = {19, 221}, Private key = {91, 221}
  7. Encryption: C = 12¹⁹ mod 221 = 181
  8. Decryption: P = 181⁹¹ mod 221 = 12 ✓

📝 Encrypting Text Messages with RSA

💡 Example: Encrypt “STOP” using RSA with key (2537, 13)

Given: n = 2537 = 43 × 59, e = 13

Step 1: Convert letters to numbers

  • S T O P → 18 19 14 15

Step 2: Divide into blocks

  • Since 2525 < 2537 < 252525, use 4-digit blocks
  • Blocks: 1819, 1415

Step 3: Encrypt each block: C = M¹³ mod 2537

  • 1819¹³ mod 2537 = 2081
  • 1415¹³ mod 2537 = 2182

Encrypted message: 2081 2182

💡 Example: Decrypt “0981 0461” with n=2537, e=13

Step 1: Find decryption key d

  • d is inverse of 13 modulo (42 × 58) = 2436
  • d = 937

Step 2: Decrypt each block: M = C⁹³⁷ mod 2537

  • 0981⁹³⁷ mod 2537 = 0704
  • 0461⁹³⁷ mod 2537 = 1115

Step 3: Convert to letters

  • 0704 → 07 04 → H E
  • 1115 → 11 15 → L P

Decrypted message: HELP

⚠️ Security Note

RSA works as a public key system because the only known method of finding d is based on factorization of n into primes. There is currently no known feasible method for factoring large numbers (400+ digits) into primes in reasonable time.

🔄 7. Diffie-Hellman Key Exchange

What is Diffie-Hellman?

The Diffie-Hellman algorithm, developed by Whitfield Diffie and Martin Hellman in 1976, enables two users to securely exchange a key over an insecure channel that can be used for subsequent encryption of messages.

🔑 Diffie-Hellman Algorithm Steps

  1. Select q (prime number) and α (primitive root of q)
    • These values are public
  2. User A Key Generation:
    • Select XA, where XA < q (private)
    • Calculate public key: YA = αXA mod q
    • Share YA with User B
  3. User B Key Generation:
    • Select XB, where XB < q (private)
    • Calculate public key: YB = αXB mod q
    • Share YB with User A
  4. User A calculates secret key:
    • K = (YB)XA mod q
  5. User B calculates secret key:
    • K = (YA)XB mod q
Both users obtain the same key:
K = αXA·XB mod q

💡 Complete Diffie-Hellman Examples

Example 1: q=353, α=3, XA=97, XB=233

Step 1: Public parameters

  • q = 353, α = 3

Step 2: User A’s public key

  • XA = 97 (private)
  • YA = 3⁹⁷ mod 353 = 40

Step 3: User B’s public key

  • XB = 233 (private)
  • YB = 3²³³ mod 353 = 248

Step 4: User A calculates shared secret

  • K = (YB)XA mod q
  • K = 248⁹⁷ mod 353 = 160

Step 5: User B calculates shared secret

  • K = (YA)XB mod q
  • K = 40²³³ mod 353 = 160 ✓

Shared Secret Key: K = 160

Example 2: q=23, α=5, XA=6, XB=15

  1. q = 23, α = 5
  2. YA = 5⁶ mod 23 = 8
  3. YB = 5¹⁵ mod 23 = 19
  4. KA = 19⁶ mod 23 = 2
  5. KB = 8¹⁵ mod 23 = 2 ✓

Shared Secret Key: K = 2

Example 3: q=11, α=17, XA=8, XB=12

  1. q = 11, α = 17
  2. YA = 17⁸ mod 11 = 4
  3. YB = 17¹² mod 11 = 3
  4. KA = 3⁸ mod 11 = 5
  5. KB = 4¹² mod 11 = 5 ✓

Shared Secret Key: K = 5

🔒 Security

To find the secret information from the public information would require an adversary to find XA and XB from αXA mod q and αXB mod q respectively. This is an instance of the discrete logarithm problem, considered computationally infeasible when q and α are sufficiently large.

📝 Cryptographic Protocols

Digital Signatures

Adding a digital signature to a message ensures the recipient that the message came from the purported sender.

Process (using RSA):

  1. Alice translates message to numerical equivalents and splits into blocks
  2. She applies her decryption function D(n,e) to the blocks
  3. Recipients apply Alice’s encryption function to recover the original message
  4. Since only Alice has the private key, everyone knows it came from her

📚 Summary

🔢 Number Theory

  • Divisibility and factors
  • Prime and composite numbers
  • GCD and LCM
  • Division algorithm
  • Modular arithmetic

🔐 Classical Cryptography

  • Caesar cipher
  • Shift ciphers
  • Affine ciphers
  • Symmetric encryption
  • Cryptanalysis techniques

🔓 Modern Cryptography

  • RSA public key system
  • Diffie-Hellman key exchange
  • Digital signatures
  • Cryptographic protocols
  • Security considerations

🎯 Key Takeaways

  • Number theory provides the mathematical foundation for modern cryptography
  • Modular arithmetic is essential for encryption algorithms
  • Prime factorization is computationally difficult for large numbers, making RSA secure
  • Public key cryptography solves the key distribution problem
  • RSA enables secure communication without prior shared secrets
  • Diffie-Hellman allows secure key exchange over insecure channels

Number Theory and Cryptography – Comprehensive Study Guide

© Qimah | Omar Alnaqeeb