Unit 1: Introduction and Mathematics of Cryptography

1. Introduction: Foundations of Information Security

In an interconnected digital civilization, information is transmitted across untrusted, broadcast-based physical media and multi-hop packet routing fabrics. Without mathematical safeguards, digital communications are fundamentally vulnerable to eavesdropping, unauthorized modification, impersonation, and repudiation.

Cryptography (from the Greek kryptos, meaning hidden, and graphein, meaning writing) is the scientific discipline that employs mathematical principles to secure communications and data storage. Network Security encompasses the protocols, architectural standards, and operational policies designed to defend data across all layers of the networking stack against adversaries.

2. Core Security Objectives: The CIA Triad and Beyond

CODECopy Code
                             +-------------------+
                             |  CONFIDENTIALITY  |
                             | (Encryption / ACL)|
                             +-------------------+
                                      ^
                                     / \
                                    /   \
                                   /     \
                                  v       v
            +-------------------+           +-------------------+
            |     INTEGRITY     |<=========>|   AVAILABILITY    |
            | (Hashes / HMACs)  |           | (DDoS Resilience) |
            +-------------------+           +-------------------+

The Three Pillars of the CIA Triad

1. Confidentiality: Assures that sensitive information is accessible only to authorized entities and remains concealed from eavesdroppers and unauthorized processes. Achieved primarily via symmetric and asymmetric encryption algorithms.
2. Integrity: Assures that data has not been altered, tampered with, deleted, or fabricated during transit or in storage. Enforced via cryptographic hash functions, Message Authentication Codes (MACs), and digital signatures.
3. Availability: Assures that systems, networks, and data remain accessible to authorized parties upon request, providing resilience against Denial-of-Service (DoS) and Distributed Denial-of-Service (DDoS) disruptions.

Supporting Security Services

• Authentication: Verifies the true identity of a communicating principal (origin authentication) or confirms that data originated from its claimed source (data origin authentication).
• Non-Repudiation: Prevents a sender or receiver from denying having transmitted, received, or authorized a specific message or transaction (achieved using digital signatures).
• Access Control: Enforces permissions governing who or what process may access specific compute, network, or storage resources.

3. Cryptographic Attack Models & Kerckhoffs's Principle

Kerckhoffs's Principle (Shannon's Maxim)

Formulated by Auguste Kerckhoffs in 1883 and restated by Claude Shannon as "The enemy knows the system":

Kerckhoffs's Principle: A cryptosystem should be secure even if everything about the system, except the cryptographic key, is public knowledge.

Relying on keeping cryptographic algorithms secret (known as Security through Obscurity) invariably fails when the algorithm is reverse-engineered, leaked, or deduced from ciphertext samples.

Taxonomy of Adversary Attacks

• Passive Attacks: The adversary intercepts and observes network traffic without altering data packets or communicating actively.
  • Eavesdropping (Packet Sniffing): Capturing plaintext transmission payloads.
  • Traffic Analysis: Inspecting transmission frequencies, message volumes, packet sizes, and communicating IP endpoints to deduce operational intelligence even when payload is encrypted.
• Active Attacks: The adversary actively injects, alters, delays, or blocks communications.
  • Masquerade (Spoofing): Impersonating another entity's identity or network address.
  • Replay Attack: Intercepting a valid authentication or financial transmission and re-transmitting it later to produce unauthorized actions.
  • Modification of Messages: Tampering with packet headers or body contents in transit.
  • Denial of Service (DoS): Overwhelming server resources, network links, or routing buffers to render services unavailable.

4. Mathematics of Cryptography: Modular Arithmetic & Number Theory

Modern cryptosystems rely on discrete mathematics, modular arithmetic, and computational number theory.

A. Divisibility and the Division Algorithm

For any integers $a$ and $b$ (with $b > 0$), there exist unique integers $q$ (quotient) and $r$ (remainder) such that:

$a = q \cdot b + r, \quad ext{where } 0 \le r < b$

We write $b \mid a$ (read: "$b$ divides $a$") if the remainder $r = 0$.

B. The Euclidean Algorithm for Greatest Common Divisor (GCD)

The Greatest Common Divisor $\gcd(a, b)$ is the largest positive integer that divides both $a$ and $b$. If $\gcd(a, b) = 1$, $a$ and $b$ are said to be relatively prime (coprime).

The Euclidean Algorithm relies on the recurrence:

\gcd(a, b) = \gcd(b, a mod b)

Computational Example: Find $\gcd(270, 192)$

1. $270 = 1 \cdot 192 + 78 \implies \gcd(270, 192) = \gcd(192, 78)$
2. $192 = 2 \cdot 78 + 36 \implies \gcd(192, 78) = \gcd(78, 36)$
3. $78 = 2 \cdot 36 + 6 \implies \gcd(78, 36) = \gcd(36, 6)$
4. $36 = 6 \cdot 6 + 0$
   The remainder reaches zero; hence, $\gcd(270, 192) = 6$.

C. The Extended Euclidean Algorithm & Modular Multiplicative Inverses

Bézout's identity states that for any integers $a$ and $b$, there exist integers $x$ and $y$ such that:

$a \cdot x + b \cdot y = \gcd(a, b)$

When $\gcd(a, m) = 1$, the integer $x$ satisfies:

$a \cdot x \equiv 1 \pmod m$

Here, $x$ is the modular multiplicative inverse of $a$ modulo $m$, denoted $a^{-1} \pmod m$.

Significance in Cryptography

Modular inverses are vital for decrypting classical ciphers (e.g., Affine and Hill ciphers) and generate public/private key pairs in RSA and Diffie-Hellman protocols. A modular inverse $a^{-1} \pmod m$ exists if and only if $\gcd(a, m) = 1$.

5. Classical Cryptographic Ciphers: Substitution vs. Transposition

Traditional ciphers operate on characters or bit permutations and fall into two primary mechanical archetypes:

CODECopy Code
                          Classical Ciphers
                                  |
                +-----------------+-----------------+
                |                                   |
       Substitution Ciphers                Transposition Ciphers
       (Replace character values)          (Rearrange character positions)
          |                |                     |                 |
    Monoalphabetic   Polyalphabetic         Rail Fence         Columnar
    - Caesar Cipher  - Vigenère Cipher      Cipher             Transposition
    - Affine Cipher  - Playfair Cipher

A. Substitution Ciphers

In a substitution cipher, each character in the plaintext is replaced by another character, symbol, or number.

1. Caesar Cipher (Monoalphabetic):

   • Shift each alphabet letter by a fixed key $k$ (traditionally $k = 3$):
     $C \equiv (P + k) \pmod{26}, \quad P \equiv (C - k) \pmod{26}$
   • Weakness: Trivial keyspace (25 possible shifts); easily broken via brute force in seconds.

2. Affine Cipher:

   • Multiplies plaintext value by $a$ and adds offset $b$:
     $C \equiv (a \cdot P + b) \pmod{26}, \quad ext{where } \gcd(a, 26) = 1$
   • Decryption requires modular inverse of $a$:
     $P \equiv a^{-1} \cdot (C - b) \pmod{26}$

3. Vigenère Cipher (Polyalphabetic):

   • Uses a repeating keyword where each letter dictates a distinct Caesar shift.
   • Mitigates simple frequency analysis by mapping the same plaintext letter to different ciphertext letters depending on position.
   • Cryptanalysis: Broken via Kasiski examination (finding repeating ciphertext patterns to deduce key length) followed by frequency analysis of individual slices.

B. Transposition (Permutation) Ciphers

In a transposition cipher, the letters themselves are unchanged, but their spatial positions are scrambled.

• Rail Fence Cipher: Letters are written diagonally down and up across imaginary "rails" and read off horizontally row by row.
• Columnar Transposition: Plaintext is written in rows of fixed width and read out column by column according to the alphabetical order of a key word.
• Cryptanalysis: Letter frequency counts match standard natural language frequencies, but digram and trigram patterns are broken.

6. Security Threats Across the Protocol Stack

7. Security in Wireless Ad Hoc Networks & VANETs

Unique Vulnerabilities of Ad Hoc Networks

Unlike traditional wired networks with centralized firewalls, routers, and domain controllers, Mobile Ad Hoc Networks (MANETs) and Vehicular Ad Hoc Networks (VANETs) operate without fixed infrastructure:

• Open Wireless Medium: Anyone with an antenna can intercept or inject radio packets.
• Dynamic Topology: Nodes join, leave, and move rapidly, requiring distributed routing.
• Constrained Resources: Nodes rely on batteries and limited bandwidth, making them susceptible to exhaustion attacks.

Classical Ad Hoc & VANET Attacks

1. Blackhole Attack: A malicious node falsely advertises the shortest route to a destination in routing protocols (like AODV) and silently drops all intercepted packets.
2. Wormhole Attack: Two colluding adversaries tunnel packets captured at one end of the network through a private high-speed link and replay them at another location, distorting routing graphs.
3. Sybil Attack: A single rogue node claims multiple forged identities or pseudo-addresses simultaneously, undermining voting consensus or reputation models.
4. VANET-Specific Threats: Tampering with safety-critical Basic Safety Messages (BSMs), GPS position spoofing, and false accident broadcasting causing phantom traffic congestion.

8. Common Pitfalls & Exam Tips

• Confusing Kerckhoffs's Principle with Security by Obscurity: Kerckhoffs's principle dictates that security depends only on key confidentiality. Hiding an algorithm is not true security.
• Existence of Modular Inverse: Remember that $a^{-1} \pmod m$ exists only if $\gcd(a, m) = 1$. In modulo 26, values like 2, 4, 13 have no inverse because $\gcd(a, 26) e 1$.
• Passive vs Active Attacks: Passive attacks compromise confidentiality (traffic sniffing); active attacks compromise integrity or availability (spoofing, DDoS).
• Caesar vs Vigenère: Caesar is monoalphabetic (one-to-one mapping; vulnerable to single-letter frequency analysis). Vigenère is polyalphabetic (one-to-many mapping; flattens simple single-letter frequency spikes).

9. Quick Revision Summary

• The CIA triad forms the core of security: Confidentiality (encryption), Integrity (hashes), Availability (resilience).
• Kerckhoffs's Principle assumes the adversary knows the algorithm; secrecy lies entirely in the key.
• $\gcd(a, b)$ is computed via the Euclidean Algorithm; modular inverse $a^{-1} \pmod m$ exists if and only if $\gcd(a, m) = 1$.
• Substitution ciphers replace characters (Caesar, Affine, Vigenère); transposition ciphers rearrange character orders.
• Classical ciphers are broken using frequency analysis, Kasiski examination, and exhaustive keyspace search.
• Each layer of the network stack faces specific threats, from physical jamming to transport SYN floods and application injection.
• Wireless ad hoc networks and VANETs face decentralized attacks like Blackhole, Wormhole, and Sybil attacks.