Unit 1: Introduction and mathematics of cryptography

I. Orientation

Cryptography is the science of protecting information by transforming plaintext into ciphertext using mathematical algorithms and keys. Modern network security combines cryptography with protocols, access controls, and detection mechanisms to protect data and systems against deliberate attacks and accidental failures.

• Core model: A sender applies encryption (E) to plaintext (P) using key (K), producing ciphertext (C); the receiver applies decryption (D).
  
  TEXT

    C = E_K(P)
    P = D_K(C)

• Security assumption: The algorithm may be public; security should depend on protecting the key, following Kerckhoffs's principle.
• Network setting: An adversary may observe, modify, inject, replay, delay, or delete messages transmitted over an untrusted channel.
• Cryptographic foundation: Modular arithmetic, number theory, substitutions, and permutations provide the mathematical operations used by many ciphers.
• Wireless setting: Ad hoc networks and vehicular ad hoc networks lack fixed boundaries, so shared radio channels and changing topologies expand the attack surface.

II. Security Foundations — Objectives, Defences, and Adversaries

A. Security Goals

Security goals define the properties that protected information and systems must preserve.

• Confidentiality: Prevents unauthorized disclosure; encryption ensures that an intercepted ciphertext cannot feasibly reveal its plaintext.
• Integrity: Detects unauthorized alteration; a message authentication code such as (T=\operatorname{HMAC}_K(M)) binds message (M) to secret key (K).
• Availability: Keeps services accessible to authorized users despite faults or denial-of-service attacks.
• Authentication: Verifies an entity's identity or a message's origin; passwords authenticate users, while digital signatures authenticate senders.
• Non-repudiation: Provides evidence that a sender performed an action; a valid digital signature can prevent credible denial of authorship.
• Authorization: Determines permitted actions after authentication, such as granting a user read access but denying write access.
• Accountability: Associates actions with responsible entities through protected logs, timestamps, and audit trails.

B. Cryptographic Attacks

Cryptographic attacks attempt to recover plaintext, discover keys, forge messages, or weaken a cryptographic protocol.

• Ciphertext-only attack: The attacker possesses ciphertexts (C_1,C_2,\ldots) and uses statistical patterns to infer plaintext or keys.
• Known-plaintext attack: Some plaintext-ciphertext pairs are known, such as (P_1) and (C_1=E_K(P_1)).
• Chosen-plaintext attack: The attacker selects plaintexts and obtains their ciphertexts, revealing how the cipher responds to controlled inputs.
• Chosen-ciphertext attack: Selected ciphertexts are submitted for decryption; secure systems restrict error information to resist such attacks.
• Brute-force attack: Every possible key is tested; a (k)-bit key has (2^k) candidates and requires about (2^{k-1}) trials on average.
• Side-channel attack: Timing, power consumption, electromagnetic leakage, or cache behavior reveals implementation-dependent information.
• Protocol attack: Replay, downgrade, and man-in-the-middle attacks exploit message sequencing or key establishment rather than the cipher itself.

C. Services and Mechanism

Security services describe what protection is provided, while mechanisms describe how that protection is implemented.

1. Security services:
   • Confidentiality service: Protects connection-oriented data, individual messages, selected fields, or traffic-flow information.
   • Authentication service: Includes peer-entity authentication and verification of data origin.
   • Integrity service: Detects modification, insertion, deletion, duplication, and replay.
   • Access-control service: Restricts resource use according to identity and policy.
2. Security mechanisms:
   • Cryptographic mechanisms: Encryption, MACs, hash functions, digital signatures, and key-exchange protocols.
   • Operational mechanisms: Access controls, audit logs, routing controls, traffic padding, and intrusion detection.
   • Relationship: One service may require several mechanisms; authenticated encryption supplies confidentiality and integrity together.

D. Cryptanalysis

Cryptanalysis studies methods for defeating cryptographic protection without directly knowing the secret key.

• Statistical analysis: Exploits non-random plaintext features; in English, letters such as E and T occur more frequently than Q or Z.
• Differential cryptanalysis: Examines how chosen input differences affect ciphertext differences across cipher rounds.
• Linear cryptanalysis: Constructs approximate linear relations among plaintext bits, ciphertext bits, and key bits.
• Success criteria: Total break recovers the key, while partial breaks may distinguish ciphertext from random data or recover only selected plaintexts.
• Security measure: A cipher is computationally secure when the cost or time of the best known attack exceeds the protected information's useful lifetime.

III. Mathematical Foundations — Integer and Modular Computation

A. Extended Euclidean Algorithm

The Extended Euclidean Algorithm computes (\gcd(a,b)) and integers (x,y) satisfying Bézout's identity.

• Formal identity: For integers (a) and (b), the algorithm finds:
  
  TEXT

    ax + by = gcd(a, b)

  
  Here, (\gcd(a,b)) is their greatest common divisor; (x) and (y) are Bézout coefficients.
• Method: Repeatedly apply (a=bq+r), where (q) is the quotient and (r) the remainder, then back-substitute.
• Cryptographic use: If (\gcd(a,n)=1), then (x) in (ax+ny=1) is the modular inverse (a^{-1}\pmod n).
• Worked example: Find the inverse of (7) modulo (26).
  
  TEXT

    26 = 3(7) + 5
     7 = 1(5) + 2
     5 = 2(2) + 1
  
    1 = 5 - 2(2)
      = 3(5) - 2(7)
      = 3(26) - 11(7)

  
  Thus (-11(7)\equiv1\pmod{26}), so (7^{-1}\equiv15\pmod{26}).

B. Modular Arithmetic

Modular arithmetic treats integers as equivalent when they have the same remainder after division by a modulus.

• Congruence: (a\equiv b\pmod n) means (n\mid(a-b)), where (n>0) is the modulus.
• Residue classes: Modulo (n), calculations use representatives (0,1,\ldots,n-1).
• Operations:
  
  TEXT

    (a + b) mod n = ((a mod n) + (b mod n)) mod n
    (ab) mod n    = ((a mod n)(b mod n)) mod n

• Inverse condition: (a) has a multiplicative inverse modulo (n) exactly when (\gcd(a,n)=1).
• Cryptographic role: Shift ciphers use addition modulo 26, while public-key systems use modular exponentiation such as (C\equiv P^e\pmod n).

IV. Layered Wireless Threats — Ad Hoc Network Attack Surface

A. Classification of attacks for wireless ad hoc and VANET

Wireless attacks can be classified by attacker behaviour, origin, capability, and affected protocol layer.

• Passive versus active: Passive attackers eavesdrop or analyse traffic; active attackers inject, alter, replay, or suppress packets.
• Internal versus external: External attackers lack legitimate credentials, while internal attackers control authenticated or compromised nodes.
• Single versus collaborative: One node may drop packets independently, whereas several malicious nodes may coordinate false routing information.
• Layer-based classification: Threats are mapped to the physical, MAC, network, transport, or application layer.
• VANET constraints: High mobility, short contact times, location dependence, and safety-critical broadcasts make timely authentication essential.

B. Attacks at the Physical Layer

Physical-layer attacks target radio transmission, hardware, and channel availability.

• Jamming: An attacker transmits interference on the operating frequency, reducing the signal-to-interference-plus-noise ratio.
• Eavesdropping: Radio signals are captured without physical cable access; encryption limits the value of intercepted frames.
• Node tampering: Physical access may expose stored keys or permit malicious hardware modification.
• Countermeasures: Spread spectrum, channel hopping, directional antennas, tamper resistance, and jamming detection improve resilience.

C. Attacks at the MAC Layer

MAC-layer attacks exploit channel-access and frame-handling procedures.

• Collision attack: Deliberate transmission during a legitimate frame corrupts it and forces retransmission.
• Backoff manipulation: A malicious node chooses unusually short contention windows to gain unfair channel access.
• MAC spoofing: Forged hardware addresses conceal identity or impersonate trusted devices.
• Exhaustion: Repeated control frames or collisions consume bandwidth and node energy.
• Defences: Frame authentication, rate limiting, fair scheduling, and abnormal-contention detection reduce impact.

D. Attacks at the Network Layer

Network-layer attacks manipulate route discovery, forwarding, and topology information.

• Blackhole attack: A node advertises an attractive route and then drops received packets.
• Greyhole attack: Packets are dropped selectively, making detection harder than continuous blackhole behaviour.
• Wormhole attack: Colluding nodes tunnel packets between distant locations, creating a false short route.
• Sinkhole attack: Forged metrics attract nearby traffic through a malicious node.
• Sybil attack: One device presents multiple identities, distorting routing or voting.
• Defences: Authenticated routing messages, packet-leash constraints, multipath routing, and trust monitoring protect forwarding.

E. Attacks at the Transport Layer

Transport-layer attacks target connection state, reliability, and end-to-end resource allocation.

• SYN flooding: Numerous TCP connection requests create half-open connections and exhaust server state.
• Session hijacking: Predicted or stolen sequence information enables injection into an established connection.
• Desynchronization: Forged control packets cause endpoints to repeatedly retransmit or lose synchronization.
• Countermeasures: SYN cookies, authenticated transport protocols, unpredictable sequence values, and connection-rate limits restrict abuse.

F. Attacks at the Application Layer

Application-layer attacks exploit services, user data, and software logic.

• Malware: Malicious code steals information, changes behaviour, or recruits nodes into botnets.
• Code injection: Unsanitized input is interpreted as commands, SQL, or executable script.
• Repudiation: A participant denies sending a message when logging and signature evidence are inadequate.
• Data corruption: False application data can trigger unsafe decisions even when packet delivery is correct.
• Controls: Input validation, signed updates, least privilege, application authentication, and protected audit logs limit damage.

V. Vehicular Network Security — Safety-Critical Communication

A. Attacks on VANET

VANET attacks exploit vehicle mobility, roadside infrastructure, location data, and safety-message dissemination.

• False-information attack: A vehicle broadcasts a fabricated accident or congestion warning, causing unsafe rerouting.
• Position spoofing: Forged GPS coordinates make a message appear to originate from another road location.
• Replay attack: A valid old hazard warning is retransmitted after the danger has passed; timestamps and freshness windows detect it.
• Sybil attack: One vehicle claims many identities to simulate congestion or influence cooperative decisions.
• GPS jamming and spoofing: Interference denies positioning, while counterfeit signals produce incorrect time or location.
• Privacy attack: Persistent identifiers allow an observer to track a driver's movements; rotating pseudonyms reduce linkability.
• Protection: Digital signatures, certificate revocation, plausibility checks, secure positioning, and misbehaviour detection establish trust.

VI. Symmetric-Key Cryptography — Classical Cipher Construction

A. Traditional symmetric-key cipher

Traditional symmetric-key ciphers use the same secret key for encryption and decryption and commonly transform letters rather than binary blocks.

• Shared-key model: Sender and receiver must securely obtain (K) before exchanging encrypted messages.
• Cipher families: Substitution replaces symbols; transposition rearranges their positions; product ciphers combine both.
• Design principle: Substitution provides confusion between key and ciphertext, while transposition contributes diffusion across ciphertext symbols.
• Limitation: Natural-language statistics remain visible in many classical ciphers, enabling manual frequency and pattern analysis.

B. Symmetric key cipher

A modern symmetric key cipher encrypts digital data efficiently using one shared secret key.

• Block cipher: Encrypts fixed-size blocks; AES processes 128-bit blocks with keys of 128, 192, or 256 bits.
• Stream cipher: Generates a keystream (Z) combined with plaintext, commonly as (C=P\oplus Z).
• Key requirement: Reusing a stream-cipher keystream exposes (C_1\oplus C_2=P_1\oplus P_2).
• Operational requirement: Modes and nonces must be selected correctly; authenticated encryption modes protect confidentiality and integrity.
• Strength and limitation: Encryption is fast, but secure key distribution becomes difficult as the number of communicating parties grows.

C. Substitution cipher

A substitution cipher replaces each plaintext unit with another unit according to a key-defined mapping.

• Caesar form: For letters represented by (0) through (25):
  
  TEXT

    E_k(x) = (x + k) mod 26
    D_k(y) = (y - k) mod 26

  
  Here, (x) is a plaintext letter, (y) is ciphertext, and (k) is the shift.
• Monoalphabetic substitution: One fixed permutation maps the alphabet to ciphertext symbols, giving (26!) possible mappings.
• Polyalphabetic substitution: Multiple alphabets are selected according to a repeating or generated key sequence.
• Weakness: Monoalphabetic schemes preserve letter frequencies and repeated patterns, so a large keyspace alone does not guarantee security.

D. Transposition cipher

A transposition cipher preserves plaintext symbols but changes their positions according to a permutation.

• Rail-fence method: Letters are written across multiple zigzag rows and read row by row.
• Columnar method: Plaintext is written into rows under a keyword, then columns are read in the key's sorted order.
• Invariant: Letter counts remain unchanged; ciphertext is an anagram of the plaintext.
• Cryptanalysis: Attackers test likely column widths, anagram patterns, and language statistics such as common digraphs.
• Combined construction: Repeated substitution and transposition rounds produce stronger product ciphers by jointly increasing confusion and diffusion.