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

Data Encryption Standard (DES)

DES is a symmetric-key block cipher that encrypts a 64-bit plaintext block using a 56-bit key (supplied as 64 bits, with 8 parity bits) and produces a 64-bit ciphertext. It is based on a Feistel structure with 16 rounds.

Overall Structure (Block Diagram in words)

64-bit Plaintext
      |
[ Initial Permutation (IP) ]
      |
  split into L0 (32 bits) | R0 (32 bits)
      |
  Round 1  (uses subkey K1)
  Round 2  (uses subkey K2)
     ...
  Round 16 (uses subkey K16)
      |
  swap (R16 | L16)  -> 32+32 = 64 bits
      |
[ Inverse Initial Permutation (IP^-1) ]
      |
64-bit Ciphertext

The 56-bit key is processed by a key schedule: it is passed through Permuted Choice 1 (PC-1), split into two 28-bit halves, circularly left-shifted each round, and compressed by Permuted Choice 2 (PC-2) into a 48-bit round subkey $K_i$.

A Single Round of DES

DES uses the Feistel structure. For round $i$, the input $(L_{i-1}, R_{i-1})$ is transformed as:

The right half is fed to the round function $F$, the result is XORed with the left half, and the halves are swapped.

The Function F (the heart of DES)

F takes the 32-bit $R_{i-1}$ and the 48-bit subkey $K_i$ and returns 32 bits:

1. Expansion (E): the 32-bit right half is expanded to 48 bits by the expansion permutation E (some bits are duplicated).
2. Key mixing (XOR): the 48-bit expanded value is XORed with the 48-bit subkey $K_i$.
3. Substitution (S-boxes): the 48 bits are split into eight 6-bit groups; each group enters an S-box that maps 6 bits to 4 bits (non-linear, provides confusion), giving $8 \times 4 = 32$ bits.
4. Permutation (P): the 32-bit S-box output is permuted by the P-box (provides diffusion), producing the 32-bit output of F.

The S-boxes are the only non-linear component and are crucial to DES security.

Decryption

Decryption uses the same algorithm with subkeys applied in reverse order ($K_{16}, K_{15}, \ldots, K_1$), a property of the Feistel network.

Advanced Encryption Standard (AES)

AES is a symmetric block cipher that operates on 128-bit blocks with key sizes of 128, 192, or 256 bits, using 10, 12, or 14 rounds respectively. Unlike DES, AES is not a Feistel cipher; it is a substitution-permutation network (SPN).

The 128-bit block is arranged as a 4x4 matrix of bytes called the State, filled column by column. All arithmetic is done in the finite field $GF(2^8)$ with the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$.

Structure (for AES-128, 10 rounds)

AddRoundKey (initial)
Rounds 1..9:  SubBytes -> ShiftRows -> MixColumns -> AddRoundKey
Round 10:     SubBytes -> ShiftRows -> AddRoundKey   (NO MixColumns)

The Four Transformations

1. SubBytes (substitution / confusion) Each byte of the State is replaced using a fixed S-box (a non-linear byte substitution = multiplicative inverse in $GF(2^8)$ followed by an affine transform). Example: the byte 0x53 is replaced by 0xED according to the S-box lookup.

2. ShiftRows (permutation / diffusion) The rows of the State are cyclically shifted left:

• Row 0: no shift
• Row 1: shift left by 1
• Row 2: shift left by 2
• Row 3: shift left by 3

Example: row [b0 b1 b2 b3] becomes [b1 b2 b3 b0] (1-byte shift).

3. MixColumns (diffusion) Each column is treated as a polynomial over $GF(2^8)$ and multiplied (mod $x^4+1$) by the fixed matrix:

Multiplication is in $GF(2^8)$ and addition is XOR. This spreads each input byte across all four output bytes of the column. (Omitted in the final round.)

4. AddRoundKey The 128-bit round key (derived from the cipher key by the key expansion / key schedule) is XORed byte-by-byte with the State:

Decryption

Decryption applies the inverse transformations (InvSubBytes, InvShiftRows, InvMixColumns, AddRoundKey) in reverse order.

Diffie-Hellman Key Exchange

Diffie-Hellman (DH) lets two parties establish a shared secret key over an insecure channel without prior secrets. Its security rests on the Discrete Logarithm Problem: it is easy to compute $g^a \bmod p$ but hard to recover $a$ from it.

Algorithm

Public parameters: a large prime $p$ and a primitive root (generator) $g$ of $p$.

1. Alice picks a private $a$, computes $A = g^a \bmod p$, sends $A$ to Bob.
2. Bob picks a private $b$, computes $B = g^b \bmod p$, 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:

Numerical Example

Let $p = 23$, $g = 5$.

• Alice: private $a = 6$, $A = 5^6 \bmod 23 = 15625 \bmod 23 = 8$.
• Bob: private $b = 15$, $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=8, B=19$ but cannot easily find $a$ or $b$.

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:

Alice  --A=g^a-->  Mallory  --M1=g^m-->  Bob
Alice  <--M2=g^n-- Mallory  <--B=g^b---  Bob

1. Alice sends $A = g^a$; Mallory intercepts it and sends her own $g^m$ to Bob.
2. Bob sends $B = g^b$; Mallory intercepts it and sends her own $g^n$ to Alice.
3. Alice computes $K_1 = (g^n)^a = g^{na}$ (shared with Mallory).
4. Bob computes $K_2 = (g^m)^b = g^{mb}$ (shared with Mallory).

Now Mallory shares key $K_1$ with Alice and $K_2$ with Bob. She decrypts every message from one side, reads/alters it, re-encrypts with the other key, and forwards it. Neither party detects the attack.

Countermeasure: authenticate the exchanged values (e.g. signed/certified public values, station-to-station protocol, or DH within TLS with certificates).

Caesar Cipher

The Caesar cipher is a mono-alphabetic shift substitution: each letter is shifted by a fixed key $k$.

Example ($k=3$): HELLO -> KHOOR.

Cryptanalysis: the key space has only 25 possibilities, so a brute-force attack trying all shifts breaks it instantly; alternatively frequency analysis on a single letter reveals the shift.

Mono-alphabetic Substitution Cipher

Here each plaintext letter maps to an arbitrary fixed letter, giving a key space of $26!\approx 4\times10^{26}$ permutations, so brute force is infeasible.

Cryptanalysis (frequency analysis): the cipher preserves letter frequencies. In English, E (~12.7%), T, A, O are most common. By matching the most frequent ciphertext letters to common English letters and using digram/trigram patterns (e.g. TH, THE), the substitution table is recovered. Example: if X is the most frequent ciphertext letter, it likely maps to E.

Conclusion: both are insecure - Caesar by brute force, mono-alphabetic by frequency analysis.

Modular Arithmetic

Modular arithmetic is arithmetic over the integers where numbers wrap around after reaching a modulus $n$. We write $a \equiv b \pmod{n}$ if $n$ divides $(a-b)$, i.e. they leave the same remainder when divided by $n$. Example: $17 \equiv 5 \pmod{12}$. It underlies almost all modern public-key cryptography (RSA, Diffie-Hellman, ElGamal).

Euler's Totient Function $\phi(n)$

$\phi(n)$ counts the integers in $\{1,2,\ldots,n\}$ that are coprime to $n$ (i.e. $\gcd = 1$).

Properties used for computation:

• If $p$ is prime, $\phi(p) = p-1$.
• $\phi$ is multiplicative: if $\gcd(m,n)=1$, $\phi(mn)=\phi(m)\phi(n)$.
• For $n = \prod p_i^{k_i}$, $\ \phi(n) = n\prod_{p\mid n}\left(1-\tfrac1p\right)$.

Compute $\phi(35)$

$35 = 5 \times 7$ (both prime, coprime):

Compute $\phi(24)$

$24 = 2^3 \times 3$:

(The 8 numbers coprime to 24 are 1, 5, 7, 11, 13, 17, 19, 23.)

ElGamal Cryptosystem

ElGamal is a public-key (asymmetric) encryption scheme whose security is based on the Discrete Logarithm Problem. It is probabilistic (the same plaintext encrypts to different ciphertexts).

Key Generation

1. Choose a large prime $p$ and a generator $g$ of $\mathbb{Z}_p^*$.
2. Choose a private key $x$ with $1 < x < p-1$.
3. Compute the public value $y = g^x \bmod p$.

• Public key: $(p, g, y)$ Private key: $x$.

Encryption (of message $m$, where $1 \le m < p$)

1. Pick a random ephemeral $k$ with $1 < k < p-1$.
2. Compute $C_1 = g^k \bmod p$.
3. Compute $C_2 = m \cdot y^k \bmod p$.

• Ciphertext: $(C_1, C_2)$.

Decryption

Using private key $x$:

This works because $C_1^x = g^{kx} = y^k$, so $C_2 \cdot (C_1^x)^{-1} = m\,y^k\,(y^k)^{-1} = m$.

Small Example

Let $p=11$, $g=2$, private $x=3 \Rightarrow y = 2^3 \bmod 11 = 8$. To encrypt $m=7$ with $k=4$: $C_1 = 2^4 \bmod 11 = 5$, $C_2 = 7\cdot 8^4 \bmod 11 = 7\cdot 4 \bmod 11 = 6$. Ciphertext $(5,6)$. Decrypt: $C_1^x = 5^3 = 125 \equiv 4$, inverse of 4 mod 11 is 3, so $m = 6\cdot 3 \bmod 11 = 18 \bmod 11 = 7$.

Note: a fresh random $k$ must be used for every message; reusing $k$ leaks the plaintext.

Block Ciphers vs Stream Ciphers

Modes of Operation of Block Ciphers

Modes let a block cipher securely encrypt messages longer than one block.

• ECB (Electronic Codebook): each block encrypted independently, $C_i = E_K(P_i)$. Simple but identical plaintext blocks give identical ciphertext, leaking patterns - not secure for structured data.
• CBC (Cipher Block Chaining): $C_i = E_K(P_i \oplus C_{i-1})$ with an IV for $C_0$. Identical blocks encrypt differently; errors propagate to two blocks. Encryption is sequential.
• CFB (Cipher Feedback): turns the block cipher into a self-synchronizing stream cipher; $C_i = P_i \oplus E_K(C_{i-1})$.
• OFB (Output Feedback): generates a keystream by repeatedly encrypting the IV ($O_i = E_K(O_{i-1})$, $C_i = P_i \oplus O_i$); no error propagation, but no self-synchronization.
• CTR (Counter): encrypts an incrementing counter to form a keystream, $C_i = P_i \oplus E_K(\text{counter}_i)$. Parallelizable and random-access; widely used.

Message Authentication Code (MAC)

A MAC is a short fixed-length tag computed from a message and a shared secret key $K$ that provides data integrity and authentication of origin. The sender computes $T = \text{MAC}(K, M)$ and sends $(M, T)$; the receiver recomputes the MAC and accepts only if the tags match. Anyone without $K$ cannot forge a valid tag. (Unlike a digital signature, a MAC uses a symmetric key, so it does not provide non-repudiation.)

HMAC (Hash-based MAC)

HMAC builds a MAC from a cryptographic hash function $H$ (e.g. SHA-256) and a key $K$:

where:

• $K'$ is the key padded/hashed to the hash block size.
• ipad = the byte 0x36 repeated; opad = the byte 0x5C repeated.
• $\|$ denotes concatenation.

How it works: the inner hash mixes the (ipad-keyed) value with the message; the outer hash re-keys the result with opad. The nested two-pass construction protects against length-extension attacks that affect plain $H(K \| M)$. HMAC is provably secure as long as the underlying hash's compression function is a good PRF, and is used in TLS, IPsec and JWT.

Key Management and Distribution in Symmetric Cryptography

Key management covers the full life cycle of secret keys: generation, distribution, storage, use, update/rotation, and destruction. In symmetric cryptography both parties share the same secret key, so securely delivering that key is the central challenge.

The Key Distribution Problem

For $n$ users who all wish to communicate pairwise, $\binom{n}{2} = \dfrac{n(n-1)}{2}$ distinct keys are needed, which scales poorly. Keys must reach both parties without exposure to attackers.

Distribution Methods

1. Manual / physical delivery: key handed over out-of-band (courier, smart card). Secure but not scalable.
2. Key encrypting key (KEK): a previously shared master key is used to encrypt and transmit fresh session keys.
3. Key Distribution Center (KDC): a trusted server shares a long-term key with each user and issues short-lived session keys on demand (basis of Kerberos). Reduces the number of long-term keys to $n$.
4. Public-key assisted exchange: use Diffie-Hellman or encrypt the symmetric key under the recipient's public key, then communicate symmetrically.

Good Practice

• Use session keys (short-lived) rather than reusing one key, limiting exposure.
• Protect keys in storage (HSMs, key vaults); rotate and revoke keys; destroy expired keys securely.

Fermat's Little Theorem

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

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

Use: primality testing and computing modular inverses ($a^{-1} \equiv a^{p-2} \pmod p$).

Example: $a=3$, $p=7$: $3^{6} = 729 = 104\times7 + 1$, so $3^{6} \equiv 1 \pmod{7}$. ✓

Euler's Theorem

Statement (generalisation of Fermat's): If $\gcd(a,n)=1$, then

where $\phi(n)$ is Euler's totient function. When $n$ is prime, $\phi(n)=n-1$ and this reduces to Fermat's little theorem.

Use: it is the basis of the RSA correctness proof and of modular exponentiation reduction.

Example: $a=3$, $n=10$, $\phi(10)=4$: $3^{4} = 81 = 8\times10 + 1$, so $3^{4} \equiv 1 \pmod{10}$. ✓

Is MITM possible in Diffie-Hellman? - Yes.

Plain Diffie-Hellman provides no authentication of the exchanged public values, so an active attacker (Mallory) positioned between the two parties can mount a man-in-the-middle attack.

Justification

Alice and Bob exchange $A=g^a$ and $B=g^b$ over the channel, but neither can verify who actually sent the value they received. Mallory intercepts and substitutes her own values:

1. Alice -> Mallory: $A = g^a$. Mallory sends Bob $g^m$ instead.
2. Bob -> Mallory: $B = g^b$. Mallory sends Alice $g^n$ instead.
3. Alice computes $K_1 = (g^n)^a = g^{an}$ (shared with Mallory, not Bob).
4. Bob computes $K_2 = (g^m)^b = g^{bm}$ (shared with Mallory, not Alice).

Mallory now shares a separate key with each party, so she can decrypt, read, modify and re-encrypt all traffic transparently. The DLP-hardness of DH does not help, because Mallory never needs to solve a discrete log - she simply uses her own private values.

Why it works / countermeasure

The vulnerability exists only because the public values are unauthenticated. It is prevented by authenticating the exchange: signed/certified public keys, the Station-to-Station (STS) protocol, or running DH inside an authenticated channel (e.g. TLS with certificates).

SHA-2 Family

SHA-2 is a family of cryptographic hash functions designed by the NSA and standardised by NIST (FIPS 180-4). It is built on the Merkle-Damgard construction with a Davies-Meyer compression function and uses modular addition, logical functions, rotations and round constants.

Members of SHA-2

SHA-224/256 share one algorithm (different IVs and truncation); SHA-384/512 share another (64-bit words, larger blocks).

Differences from SHA-1

Summary: SHA-2 offers larger and selectable digest sizes, a stronger internal structure (8 working variables, more complex message schedule), and far greater collision/preimage resistance, whereas SHA-1's 160-bit output is now considered cryptographically broken and deprecated.