Cryptography and Network Security – Unit 2 Notes

Unit 2 introduces the mathematical foundations used in modern cryptography and then applies these concepts to AES, public-key cryptography and RSA. The topics include modular arithmetic, groups, fields, finite fields, the Extended Euclidean Algorithm, Fermat's theorem, Euler's theorem, primality testing, the Chinese Remainder Theorem, the Discrete Logarithmic Problem and RSA.

1. Modular Arithmetic

Modular arithmetic is arithmetic based on remainders. If a number a is divided by n and the remainder is r, then we write:

a mod n = r

For example, 17 divided by 5 gives a remainder of 2.

17 mod 5 = 2

1.1 Congruence

Two numbers a and b are congruent modulo n when they leave the same remainder after division by n. It can also be written as:

a ≡ b (mod n)

This means that n divides a - b.

1.2 Modular Addition

(a + b) mod n

1.3 Modular Subtraction

(a - b) mod n

1.4 Modular Multiplication

(a × b) mod n

1.5 Modular Exponentiation

Modular exponentiation means calculating a large power and then finding its remainder. It is very important in RSA and other cryptographic algorithms.

3⁴ mod 5 = 81 mod 5 = 1

1.6 Modular Multiplicative Inverse

The modular inverse of a modulo n is a number x satisfying:

a × x ≡ 1 (mod n)

2. Prime and Relatively Prime Numbers

2.1 Prime Number

A prime number is an integer greater than 1 that has exactly two positive divisors: 1 and the number itself.

Examples: 2, 3, 5, 7, 11, 13, 17 and 19.

2.2 Composite Number

A composite number is greater than 1 and has more than two positive divisors.

2.3 Relatively Prime Numbers

Two numbers are relatively prime, or coprime, if their greatest common divisor is 1.

gcd(a, b) = 1

2.4 Importance in Cryptography

• Prime numbers are used to construct cryptographic keys.
• Coprime numbers are needed when calculating modular inverses.
• RSA requires the public exponent e to satisfy gcd(e, φ(n)) = 1.

3. Groups and Abelian Groups

3.1 Group

A group is a set together with an operation that satisfies four basic properties: closure, associativity, identity and inverse.

3.2 Example of a Group

The integers under addition, written as (Z, +), form a group. The identity element is 0 and the inverse of a is -a.

3.3 Abelian Group

A group is called an Abelian group when the operation is also commutative.

a * b = b * a

4. Fields

A field is an algebraic structure in which addition, subtraction, multiplication and division follow the required field rules. Every non-zero element has a multiplicative inverse.

4.1 Important Properties

• Addition and multiplication are the main operations.
• There is an additive identity, 0.
• There is a multiplicative identity, 1.
• Every non-zero element has a multiplicative inverse.
• The required associative, commutative and distributive properties hold.

4.2 Examples

The rational numbers, real numbers and complex numbers are examples of fields. Finite fields are especially important in cryptography because they provide a finite set in which arithmetic can be performed systematically.

5. Finite Fields and GF(p)

5.1 Finite Field

A finite field is a field containing a finite number of elements. It is commonly written as GF(q), where q represents the number of elements.

5.2 GF(p)

When p is a prime number, the finite field containing p elements is written as GF(p). Its elements are 0, 1, 2, ..., p-1, and arithmetic is performed modulo p.

GF(5) = {0, 1, 2, 3, 4}

5.3 Importance of GF(p)

• It provides a finite mathematical environment for cryptographic calculations.
• It is important for number-theoretic cryptography.
• Finite-field arithmetic is also used in modern cryptographic constructions.

6. Extended Euclidean Algorithm

The Extended Euclidean Algorithm (EEA) finds the greatest common divisor of two integers and also finds integers x and y satisfying Bézout's identity.

ax + by = gcd(a, b)

6.1 Why EEA is Important

• It finds the GCD of two numbers.
• It can find a modular multiplicative inverse.
• Modular inverses are required in RSA key generation.

6.2 Worked Example: Inverse of 7 Modulo 26

First use the Euclidean divisions:

26 = 7 × 3 + 5
7  = 5 × 1 + 2
5  = 2 × 2 + 1
2  = 1 × 2 + 0

Therefore:

gcd(26, 7) = 1

Now work backwards:

1 = 5 - 2 × 2
1 = 3 × 5 - 2 × 7
1 = 3 × 26 - 11 × 7

Therefore:

7(-11) ≡ 1 (mod 26)
-11 ≡ 15 (mod 26)

Therefore, 7⁻¹ ≡ 15 (mod 26).

7. Advanced Encryption Standard (AES)

7.1 Introduction

AES stands for Advanced Encryption Standard. It is a symmetric-key block cipher used to protect digital information. AES uses a secret key for encryption and the corresponding secret-key process for decryption.

7.2 AES Key Sizes and Rounds

7.3 AES State

A 128-bit data block contains 16 bytes. AES arranges these bytes as a 4 × 4 matrix called the state.

128 bits = 16 bytes = 4 × 4 byte state

7.4 AES Encryption Structure

The following diagram shows only the main AES encryption flow needed for understanding the tutorial topic.

7.5 Main AES Operations

• SubBytes: Each byte is replaced using the AES S-box.
• ShiftRows: The rows of the state are cyclically shifted.
• MixColumns: Each column is transformed using finite-field arithmetic.
• AddRoundKey: The state is XORed with the round key.

7.6 Initial AddRoundKey

Before the regular rounds, AES performs an AddRoundKey operation. The plaintext state is XORed with the first round key.

State = Plaintext XOR RoundKey

7.7 SubBytes

SubBytes is a byte substitution operation. Each byte in the state is replaced with another byte using the AES S-box. This introduces non-linearity and makes simple relationships between input and output more difficult to exploit.

7.8 ShiftRows

ShiftRows changes the positions of bytes in the state. Row 0 is not shifted, row 1 is shifted left by one byte, row 2 by two bytes and row 3 by three bytes.

7.9 MixColumns

MixColumns transforms every column using matrix multiplication over the finite field GF(2⁸). Its purpose is to provide diffusion by spreading the influence of bytes.

7.10 AddRoundKey

AddRoundKey combines the current state with a round key using XOR.

New State = Current State XOR Round Key

7.11 AES-128 Round Structure

For AES-128, rounds 1 to 9 contain SubBytes, ShiftRows, MixColumns and AddRoundKey. The final round contains SubBytes, ShiftRows and AddRoundKey, but does not contain MixColumns.

7.12 AES Key Expansion

AES expands the original secret key into a number of round keys. AES-128 requires 11 round keys: one for the initial AddRoundKey and one for each of the 10 rounds.

7.13 AES Decryption

AES decryption reverses the encryption process using inverse transformations and the appropriate round keys.

8. Fermat's Little Theorem

Fermat's Little Theorem is an important result in modular arithmetic. If p is prime and gcd(a,p) = 1, then:

a^(p-1) ≡ 1 (mod p)

8.1 Example

Take a = 2 and p = 7. Since 7 is prime and gcd(2,7) = 1:

8.2 Modular Inverse Connection

For a prime modulus p and a not divisible by p:

a^(p-2) ≡ a⁻¹ (mod p)

8.3 Uses

• Modular arithmetic.
• Finding inverses under a prime modulus.
• Number-theoretic reasoning in cryptography.

9. Euler's Theorem and Euler's Totient Function

9.1 Euler's Theorem

If gcd(a,n) = 1, Euler's theorem states:

a^φ(n) ≡ 1 (mod n)

9.2 Euler's Totient Function

Euler's totient function, written as φ(n), counts the positive integers up to n that are relatively prime to n.

9.3 Important Totient Formulas

9.4 Importance in RSA

In RSA, when n = pq for two distinct primes, φ(n) = (p - 1)(q - 1). This value is used while generating the private exponent.

10. Primality Testing

Primality testing determines whether an integer is prime or composite. It is important in public-key cryptography because RSA requires large prime numbers.

10.1 Basic Primality Test

For a number n, it is enough to test possible divisors up to √n. If no integer from 2 through √n divides n, then n is prime.

10.2 Probabilistic Primality Testing

For very large numbers, testing every possible divisor is inefficient. Cryptographic systems therefore use probabilistic tests.

11. Chinese Remainder Theorem (CRT)

The Chinese Remainder Theorem provides a method for solving a system of simultaneous congruences when the moduli are pairwise relatively prime.

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...
x ≡ aₖ (mod nₖ)

If the moduli are pairwise coprime, a unique solution exists modulo:

N = n₁ × n₂ × ... × nₖ

11.1 Simple CRT Example

Consider:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)

The number 8 satisfies both conditions:

11.2 CRT in RSA

RSA private-key calculations can be performed separately modulo p and q and then combined using CRT. This is known as RSA-CRT and can make private-key operations significantly faster.

12. Discrete Logarithmic Problem

The Discrete Logarithmic Problem (DLP) asks us to find an exponent x from an equation such as:

g^x ≡ y (mod p)

Here, g and y are known, p is the modulus and x is the unknown exponent.

12.1 Simple Example

12.2 Why DLP is Important

For small numbers, the discrete logarithm can be found by trial. For appropriately selected large parameters, finding the secret exponent can become computationally difficult.

• Diffie-Hellman key exchange uses related discrete-logarithm assumptions.
• ElGamal encryption uses discrete-logarithm based mathematics.
• ElGamal digital signatures use related mathematics.
• Elliptic-curve cryptography uses related discrete-logarithm problems on elliptic curves.

13. Principles of Public-Key Cryptosystems

Public-key cryptography, also called asymmetric cryptography, uses a pair of related keys: a public key and a private key.

13.1 Basic Public-Key Encryption Model

If Bob wants to receive a confidential message, he publishes his public key. Alice uses Bob's public key to encrypt the message. Bob uses his private key to decrypt it.

C = E(Kpublic, P)
P = D(Kprivate, C)

13.2 Requirements

• Key-pair generation should be practical.
• Encryption using the public key should be practical.
• Legitimate decryption using the private key should be practical.
• An attacker should not be able to feasibly derive the private key from public information.
• The system should provide security under appropriate attack models.

14. RSA Algorithm

RSA is a public-key cryptographic algorithm named after Rivest, Shamir and Adleman. It uses modular arithmetic and large prime numbers.

14.1 RSA Key Generation

The standard educational sequence is:

1. Choose two large prime numbers p and q.
2. Calculate n = p × q.
3. Calculate φ(n) = (p - 1)(q - 1).
4. Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1.
5. Find d such that ed ≡ 1 (mod φ(n)).
6. Public key = (e, n).
7. Private key = (d, n).

14.2 Small Educational Example

Choose p = 11 and q = 13.

n = p × q
  = 11 × 13
  = 143

Now calculate Euler's totient:

φ(n) = (p - 1)(q - 1)
     = 10 × 12
     = 120

Choose e = 7 because:

gcd(7, 120) = 1

Now find d such that:

7d ≡ 1 (mod 120)

One solution is:

d = 103

7 × 103 = 721
721 mod 120 = 1

Therefore:

Public Key  = (7, 143)
Private Key = (103, 143)

14.3 RSA Encryption

If the plaintext is represented by an integer M, encryption is performed using the public key:

C = M^e mod n

14.4 RSA Decryption

The receiver uses the private key to recover the plaintext:

M = C^d mod n

14.5 Small RSA Numerical Example

Using the educational key pair above, let the plaintext be M = 9.

C = 9^7 mod 143
  = 48

The receiver calculates:

M = 48^103 mod 143
  = 9

14.6 RSA Process Summary

15. Security of RSA

15.1 Factorization Problem

The RSA modulus is n = pq. The public key contains n, while p and q are kept secret. If an attacker can efficiently factor n into p and q, the attacker can calculate φ(n) and potentially derive the private exponent.

15.2 Strong Key Generation

• Use sufficiently large, randomly generated prime numbers.
• Use a cryptographically secure random-number generator.
• Avoid weak or predictable primes.
• Follow secure parameter-generation practices.

15.3 Public Exponent

A commonly used RSA public exponent is 65537. It provides efficient exponentiation while avoiding some issues associated with extremely small exponents. Secure RSA still requires appropriate padding and protocol design.

15.4 RSA Padding

Practical RSA encryption should not simply encrypt raw messages using C = M^e mod n. A secure padding scheme is required. RSA-OAEP is used for encryption, while RSA-PSS is a modern approach for RSA signatures.

15.5 Side-Channel Attacks

An implementation may unintentionally leak information through execution time, power consumption, cache behaviour or other physical effects. Such attacks are called side-channel attacks.

15.6 RSA-CRT

RSA-CRT performs private-key calculations separately modulo p and q and then combines the results using the Chinese Remainder Theorem. This can make RSA private-key operations faster.

16. Important Unit 2 Formulas

17. Quick Comparison Tables

17.1 Prime vs Relatively Prime

17.2 Fermat vs Euler

17.3 Symmetric vs Public-Key Cryptography

17.4 AES vs RSA

18. Important Examination Questions

18.1 Short-Answer Questions

• What is modular arithmetic?
• Define a prime number.
• What are relatively prime numbers?
• What is a group?
• What is an Abelian group?
• Define a field.
• What is GF(p)?
• What is the Extended Euclidean Algorithm?
• State Fermat's Little Theorem.
• State Euler's theorem.
• What is Euler's totient function?
• What is the Chinese Remainder Theorem?
• Define the Discrete Logarithm Problem.
• What is a public-key cryptosystem?
• What is RSA?
• What is the block size of AES?

18.2 Long-Answer / Numerical Questions

• Explain modular arithmetic and modular multiplicative inverse with examples.
• Explain groups and fields and state their important properties.
• Explain finite field GF(p) with suitable examples.
• Use the Extended Euclidean Algorithm to find a modular inverse.
• State and explain Fermat's Little Theorem with an example.
• Explain Euler's theorem and Euler's totient function.
• Solve a system of congruences using the Chinese Remainder Theorem.
• Explain the Discrete Logarithm Problem and its role in cryptography.
• Explain the structure and encryption process of AES.
• Explain AES decryption and its inverse transformations.
• Explain the complete RSA key-generation procedure.
• Perform RSA encryption and decryption using a numerical example.
• Explain the security of RSA and the importance of secure key generation.
• Explain RSA padding, side-channel concerns and RSA-CRT.
• Compare symmetric and public-key cryptography.

19. Unit 2 – Final Revision

• Modular arithmetic is the basic mathematical foundation of many cryptographic calculations.
• Prime numbers and relatively prime numbers are important for public-key cryptography.
• Groups, fields and finite fields provide algebraic structures for cryptographic operations.
• The Extended Euclidean Algorithm is useful for finding GCD and modular inverses.
• AES is a symmetric block cipher with a 128-bit block size.
• AES supports 128-, 192- and 256-bit keys with 10, 12 and 14 rounds respectively.
• Fermat's and Euler's theorems provide important modular relationships.
• Euler's totient function is particularly important in RSA.
• CRT solves systems of simultaneous congruences and can speed up RSA private-key operations.
• The Discrete Logarithm Problem is important in several public-key cryptosystems.
• RSA uses two large primes, n = pq, φ(n) = (p-1)(q-1), a public exponent e and a private exponent d.
• In RSA, ed ≡ 1 (mod φ(n)), C = M^e mod n and M = C^d mod n.