BSc CSIT (TU) Science Cryptography (BSc CSIT, CSC316) Question Paper 2078 Nepal

Diffie-Hellman Key Exchange

The Diffie-Hellman (DH) algorithm allows two parties to agree on a shared secret key over an insecure channel without ever transmitting the key itself. Its security rests on the difficulty of the Discrete Logarithm Problem.

Algorithm

Public parameters (agreed in advance):

• A large prime $p$.
• A primitive root $g$ modulo $p$ (the generator).

Steps:

1. Alice picks a secret integer $a$ and computes $A = g^{a} \bmod p$; she sends $A$ to Bob.
2. Bob picks a secret integer $b$ and computes $B = g^{b} \bmod p$; he sends $B$ to Alice.
3. Alice computes $K = B^{a} \bmod p$.
4. Bob computes $K = A^{b} \bmod p$.

Both obtain the same key because

Example ($p = 23,\ g = 5$)

• Alice: $a = 6 \Rightarrow A = 5^{6} \bmod 23 = 8$.
• Bob: $b = 15 \Rightarrow B = 5^{15} \bmod 23 = 19$.
• Alice: $K = 19^{6} \bmod 23 = 2$.
• Bob: $K = 8^{15} \bmod 23 = 2$.

Shared secret $K = 2$. An eavesdropper sees $p,g,A,B$ but cannot find $a$ or $b$ without solving the discrete log.

Man-in-the-Middle (MITM) Attack

DH provides no authentication, so an attacker Mallory sitting between Alice and Bob can impersonate each to the other:

1. Alice sends $A = g^{a}$. Mallory intercepts it and instead sends her own $M = g^{m}$ to Bob.
2. Bob sends $B = g^{b}$. Mallory intercepts it and sends $M = g^{m}$ to Alice.
3. Alice computes $K_1 = M^{a} = g^{am}$; Mallory computes the same $K_1 = A^{m}$.
4. Bob computes $K_2 = M^{b} = g^{bm}$; Mallory computes the same $K_2 = B^{m}$.

Now Mallory shares $K_1$ with Alice and $K_2$ with Bob. She decrypts every message from one side with one key and re-encrypts it with the other, reading and altering traffic while both believe they share a secret.

Countermeasure: Authenticate the exchanged public values, e.g. by signing $A$ and $B$ (digital signatures / certificates) — this gives authenticated Diffie-Hellman (as in TLS/IKE/STS).

Cryptographic Hash Functions

A cryptographic hash function $H$ maps an arbitrary-length message $M$ to a fixed-length output $h = H(M)$ called the message digest. Required properties:

• Preimage resistance (one-way): given $h$, infeasible to find $M$ with $H(M)=h$.
• Second-preimage resistance: given $M$, infeasible to find $M' \neq M$ with $H(M')=H(M)$.
• Collision resistance: infeasible to find any pair $M \neq M'$ with $H(M)=H(M')$.
• Avalanche effect: a 1-bit input change flips ~half the output bits.

Uses: integrity checks, digital signatures, MACs, password storage.

SHA-1 Algorithm

SHA-1 produces a 160-bit digest using the Merkle-Damgård construction and processes the message in 512-bit blocks.

1. Padding

Append a 1 bit, then 0 bits, then a 64-bit length field so that the total length $\equiv 448 \pmod{512}$. Final length is a multiple of 512 bits.

2. Initialize the five 32-bit chaining variables

3. Process each 512-bit block

Expand the sixteen 32-bit words $W_0..W_{15}$ to eighty words:

Set $a,b,c,d,e = H_0..H_4$. For $t=0..79$ run 80 rounds:

The round function $f_t$ and constant $K_t$ change every 20 rounds:

4. Update chaining values

5. Output

After all blocks, the 160-bit digest is the concatenation

Note: SHA-1 is now considered broken for collision resistance (SHAttered attack, 2017) and is deprecated in favour of SHA-2/SHA-3.

Classical Encryption Techniques

Classical ciphers work on plaintext letters and fall into two classes:

• Substitution ciphers – replace letters with other symbols (Caesar, Playfair, Hill, Vigenère).
• Transposition ciphers – rearrange letter positions (Rail Fence, Columnar).

Playfair Cipher (digraph substitution)

Encrypts pairs of letters using a $5\times5$ key matrix (I/J share a cell).

Key = "MONARCHY":

M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z

Rules (after splitting plaintext into digraphs; insert X between repeated letters and pad if odd):

1. Same row: replace each letter by the one to its right (wrap).
2. Same column: replace each by the one below (wrap).
3. Rectangle: replace each by the letter in its own row but the other letter's column.

Example: plaintext BALLOON → digraphs BA LX LO ON.

• BA: rectangle → IB
• LX: rectangle → SU
• LO: rectangle → PM (L row, O column = P; O row, L column = M)
• ON: same row → NA

Ciphertext = IBSUPMNA.

Hill Cipher (polygraphic, linear algebra)

Encrypts blocks of $n$ letters using an invertible $n\times n$ key matrix $K$ modulo 26. Letters map $A=0,\dots,Z=25$.

Example with $K=\begin{pmatrix}3 & 3\\ 2 & 5\end{pmatrix}$, plaintext HI = $\begin{pmatrix}7\\8\end{pmatrix}$:

Ciphertext = TC. Decryption requires $K^{-1}\bmod 26$, which exists only when $\gcd(\det K, 26)=1$ (here $\det K = 9$, coprime to 26).

Message Authentication Code (MAC)

A MAC is a short fixed-length tag computed from a message $M$ and a shared secret key $K$: $\text{tag}=\text{MAC}(K,M)$. The sender appends the tag; the receiver recomputes it and accepts only if they match. A MAC provides data integrity and authentication (proof the message came from someone holding $K$), but not non-repudiation (both parties share the key) or confidentiality.

HMAC (Hash-based MAC)

HMAC builds a MAC from any cryptographic hash $H$ (e.g. SHA-256). It uses two padded constants — ipad (0x36 repeated) and opad (0x5C repeated) — and the key $K$:

Steps:

1. Pad/hash key $K$ to the block size.
2. Inner hash: XOR key with ipad, prepend to $M$, hash it.
3. Outer hash: XOR key with opad, prepend to the inner result, hash again.

The nested (two-pass) structure defeats length-extension attacks that affect plain $H(K\|M)$, and HMAC is provably secure if the underlying hash's compression function is a PRF.

Key Management and Distribution in Symmetric Cryptography

In symmetric cryptography both parties share one secret key, so the central problem is securely generating, distributing, storing and renewing that key. For $n$ users wanting pairwise communication, $\binom{n}{2}=n(n-1)/2$ keys are needed — this key-explosion is the core scaling challenge.

Key Distribution Methods

1. Physical/manual delivery: A hands the key to B in person or via courier. Secure but unscalable.
2. Encrypted via an existing key: if A and B already share a key, a new session key can be sent encrypted under it.
3. Third-party encrypted delivery: a trusted Key Distribution Center (KDC) shares a master key with each user and issues short-lived session keys on demand (the basis of Kerberos).
4. Public-key based exchange: use a public-key method or Diffie-Hellman to establish the symmetric session key.

KDC Operation (typical)

• A requests a session key for B from the KDC.
• The KDC generates session key $K_s$ and sends it to A encrypted under A's master key, plus a ticket $E_{Kb}(K_s, ID_A)$ for B.
• A forwards the ticket; B decrypts it to obtain $K_s$.

Key Lifecycle

Generation → distribution → storage (protected) → usage → periodic rotation → revocation/destruction. Session keys are short-lived to limit exposure; master keys are long-lived and heavily protected.

Fermat's Little Theorem

Statement: If $p$ is prime and $\gcd(a,p)=1$, then

Equivalently, for any integer $a$: $a^{p} \equiv a \pmod p$.

Example: $p=7,\ a=3$:

Euler's Theorem (generalisation)

Statement: If $\gcd(a,n)=1$, then

where $\phi(n)$ is Euler's totient = count of integers in $[1,n]$ coprime to $n$. For prime $p$, $\phi(p)=p-1$, so Fermat's theorem is the special case.

Example: $n=10,\ a=3$. $\phi(10)=4$ (the units $1,3,7,9$):

Relevance to cryptography: Euler's theorem underlies RSA — choosing $ed \equiv 1 \pmod{\phi(n)}$ guarantees $m^{ed}\equiv m \pmod n$, so decryption inverts encryption. It also speeds modular exponentiation by reducing exponents modulo $\phi(n)$.

Is MITM Possible in Diffie-Hellman?

Yes. Plain Diffie-Hellman is vulnerable to a man-in-the-middle attack because it establishes a shared secret but provides no authentication of the communicating parties — neither side can verify that the public value it received actually came from the intended partner.

Why

An attacker Mallory between Alice and Bob can substitute her own public values:

1. Alice sends $A=g^{a}$; Mallory replaces it with $g^{m}$ toward Bob.
2. Bob sends $B=g^{b}$; Mallory replaces it with $g^{m}$ toward Alice.
3. Alice forms $K_1=g^{am}$ with Mallory; Bob forms $K_2=g^{bm}$ with Mallory.

Mallory now holds both keys, decrypting and re-encrypting all traffic while Alice and Bob believe they share one secret. The underlying discrete-log hardness is never broken — the weakness is the missing authentication.

Justification & Fix

The attack is possible precisely because messages $A$ and $B$ are unauthenticated. Authenticating the exchange — signing the public values with digital signatures, using certificates/PKI, or a password-authenticated variant (e.g. the Station-to-Station protocol, used in TLS and IKE) — prevents the substitution and stops the MITM attack.

The SHA-2 Family

SHA-2 is a family of cryptographic hash functions designed by the NSA and standardised by NIST (FIPS 180-4). It comprises six variants distinguished mainly by digest length and internal word size:

SHA-224/256 use eight 32-bit working variables; SHA-384/512 use eight 64-bit variables (with truncated outputs for 224/384). The 224/384 versions are truncations of 256/512 with different initial hash values.

Differences from SHA-1

Summary: SHA-2 offers larger, configurable digests, more chaining variables, a stronger message-schedule and round function, and far greater collision resistance, making it the recommended replacement for the now-deprecated SHA-1.

Public Key Infrastructure (PKI)

PKI is the framework of hardware, software, policies, people and procedures used to create, manage, distribute, store and revoke digital certificates and public keys. Its purpose is to reliably bind a public key to an identity, enabling authentication, confidentiality, integrity and non-repudiation in public-key cryptography.

Main components: Certificate Authority (CA), Registration Authority (RA), digital certificates, a certificate repository/directory, and a revocation mechanism (CRL / OCSP).

Certificate Authority (CA)

The CA is the trusted third party that:

• Verifies an applicant's identity (often via an RA).
• Issues digital certificates by signing them with the CA's private key.
• Maintains and publishes Certificate Revocation Lists (CRLs) for compromised/expired certificates.
• Forms a chain of trust: root CA → intermediate CAs → end-entity certificates.

Digital Certificate (X.509)

A digital certificate is a signed data structure that binds a public key to its owner. An X.509 certificate contains:

• Version, serial number.
• Subject name (owner) and the subject's public key.
• Issuer name (the CA).
• Validity period (not-before / not-after).
• Signature algorithm and the CA's digital signature over the certificate.

A relying party trusts the certificate by verifying the CA's signature with the CA's (already trusted) public key, thereby trusting the bound public key without prior contact.

Malicious Code (Malware)

Malicious code is software intentionally written to damage, disrupt or gain unauthorised access to systems and data.

1. Virus

A virus is a code fragment that attaches itself to a host program or file and cannot run independently — it executes when the infected host is run. On execution it replicates by inserting copies into other programs/files and may carry a payload (corrupting data, displaying messages). Spread requires user action (running the host), e.g. boot-sector, file-infector and macro viruses.

2. Worm

A worm is a standalone program that does not need a host and self-propagates across networks automatically by exploiting vulnerabilities or using email/file shares — no user action required. Because it replicates autonomously, a worm can spread extremely fast and consume bandwidth/resources (e.g. Code Red, ILOVEYOU, Conficker).

3. Trojan Horse

A trojan horse is a program that disguises itself as legitimate or useful software but hides malicious functionality (backdoor, data theft, spyware). It does not self-replicate; it relies on the user being tricked into installing/running it.

Chinese Remainder Theorem (CRT)

Statement: If $n_1, n_2, \dots, n_k$ are pairwise coprime positive integers, then the system of congruences

has a unique solution modulo $N = n_1 n_2 \cdots n_k$.

Solution Method

Let $N=\prod n_i$, $N_i = N/n_i$, and $M_i = N_i^{-1} \bmod n_i$. Then

Worked Example

Solve:

$N = 3\cdot5\cdot7 = 105.$

Answer: $x \equiv 23 \pmod{105}$. Check: $23\bmod3=2$, $23\bmod5=3$, $23\bmod7=2$. ✓

CRT is widely used in cryptography to speed up RSA decryption by working modulo the prime factors $p$ and $q$ separately.

Goals of Security (CIA Triad)

• Confidentiality: ensure information is accessible only to authorised parties; prevent unauthorised disclosure. Achieved by encryption and access control.
• Integrity: ensure data is accurate and not modified in an unauthorised way; detect tampering. Achieved with hashes, MACs and digital signatures.
• Availability: ensure systems and data are accessible to authorised users when needed. Threatened by Denial-of-Service attacks; protected by redundancy, backups and DoS mitigation.

Supporting goals: authentication, non-repudiation and access control.

Types of Security Attacks

By effect (passive vs active):

• Passive attacks – attacker only observes; no modification. Hard to detect.
  • Release of message contents (eavesdropping).
  • Traffic analysis (inferring info from patterns/metadata).
• Active attacks – attacker alters data or operation; easier to detect, harder to prevent.
  • Masquerade – impersonating another entity.
  • Replay – capturing and re-sending valid data.
  • Modification of messages – altering content.
  • Denial of Service (DoS) – disrupting availability.

By security-goal violated (Stallings model):

• Interception → confidentiality.
• Interruption → availability.
• Modification → integrity.
• Fabrication → authenticity.