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

Advanced Encryption Standard (AES)

AES is a symmetric-key block cipher standardized by NIST (FIPS-197) in 2001 as a replacement for DES. It encrypts a 128-bit block using keys of 128, 192 or 256 bits, giving 10, 12 or 14 rounds respectively. Unlike DES it is not a Feistel network; every byte of the block is transformed in each round (a substitution-permutation network).

State and structure

The 128-bit input is arranged column-wise into a $4\times4$ matrix of bytes called the state. The key is expanded by the key schedule into $(N_r+1)$ round keys. The overall flow is:

AddRoundKey (initial)
for round = 1 to Nr-1:
    SubBytes -> ShiftRows -> MixColumns -> AddRoundKey
final round (Nr):
    SubBytes -> ShiftRows -> AddRoundKey   // no MixColumns

The four transformations

1. SubBytes (non-linear substitution) Each byte is replaced using a fixed $16\times16$ S-box derived from the multiplicative inverse in $GF(2^8)$ followed by an affine transform. It provides confusion. Example: byte $\texttt{0x53}$ → S-box row 5, column 3 → $\texttt{0xED}$.

2. ShiftRows (cyclic permutation) Rows of the state are cyclically left-shifted: row 0 by 0, row 1 by 1, row 2 by 2, row 3 by 3 bytes. This spreads bytes across columns (diffusion).

[a0 a1 a2 a3]        [a0 a1 a2 a3]
[b0 b1 b2 b3]   ->   [b1 b2 b3 b0]
[c0 c1 c2 c3]        [c2 c3 c0 c1]
[d0 d1 d2 d3]        [d3 d0 d1 d2]

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

Multiplications are in $GF(2^8)$ with reducing polynomial $x^8+x^4+x^3+x+1$. This gives strong inter-byte diffusion. It is omitted in the last round.

4. AddRoundKey The 128-bit round key is XORed byte-by-byte with the state: $\text{state} = \text{state}\oplus K_r$. This is the only step that depends on the secret key.

Decryption

Decryption uses the inverse transformations (InvSubBytes, InvShiftRows, InvMixColumns, AddRoundKey) with round keys applied in reverse order.

Diffie-Hellman Key Exchange

Diffie-Hellman (1976) lets two parties establish a shared secret over an insecure channel without prior secrets. Its security rests on the hardness of the discrete logarithm problem.

Protocol

Public parameters: a large prime $p$ and a primitive root (generator) $g$ of $\mathbb{Z}_p^*$.

1. Alice picks secret $a$, sends $A = g^a \bmod p$.
2. Bob picks secret $b$, sends $B = g^b \bmod p$.
3. Alice computes $K = B^a \bmod p$; Bob computes $K = A^b \bmod p$.
4. Both obtain $K = g^{ab} \bmod p$.

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=8,B=19$ but cannot easily compute $a$ or $b$ (discrete log).

Man-in-the-Middle (MITM) Attack

Plain DH provides no authentication, so an active attacker Mallory sitting between Alice and Bob can intercept and substitute keys:

1. Mallory chooses own secrets $m_1, m_2$.
2. Alice sends $A=g^a$; Mallory intercepts and sends $g^{m_1}$ to Bob.
3. Bob sends $B=g^b$; Mallory intercepts and sends $g^{m_2}$ to Alice.
4. Alice computes $K_1 = (g^{m_2})^a = g^{m_2 a}$ — shared with Mallory (who computes $A^{m_2}$).
5. Bob computes $K_2 = (g^{m_1})^b = g^{m_1 b}$ — also shared with Mallory.

Mallory now shares one key with Alice and another with Bob. He decrypts, reads/alters, and re-encrypts every message, relaying it transparently. Neither party detects the attack.

Countermeasure: authenticate the exchanged values, e.g. authenticated/station-to-station DH, signing $A$ and $B$, or using certificates (PKI).

Cryptographic Hash Functions

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

• Preimage resistance — 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')$.

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

SHA-1 Algorithm

SHA-1 produces a 160-bit digest. It follows the Merkle-Damgård construction.

Step 1 — Padding: Append a single 1 bit, then 0s, then the original 64-bit message length, so the total length is a multiple of 512 bits.

Step 2 — Parse the padded message into 512-bit blocks $M_1, M_2, \dots, M_n$.

Step 3 — Initialise five 32-bit chaining variables:

Step 4 — Process each block (80 rounds):

• Expand the sixteen 32-bit words into eighty words $W_0\dots W_{79}$ using $W_t = (W_{t-3}\oplus W_{t-8}\oplus W_{t-14}\oplus W_{t-16}) \lll 1$.
• Set $a,b,c,d,e = H_0\dots H_4$. For $t=0$ to $79$:

where $f_t$ and constant $K_t$ change across four groups of 20 rounds (Ch, Parity, Maj, Parity).

• Add back: $H_i = H_i + \{a,b,c,d,e\}$ (mod $2^{32}$).

Step 5 — Output: After the last block, the 160-bit digest is the concatenation $H_0 \Vert H_1 \Vert H_2 \Vert H_3 \Vert H_4$.

Note: SHA-1 is now considered broken for collision resistance (a practical collision was demonstrated in 2017) and is deprecated in favour of SHA-2/SHA-3.

ElGamal Cryptosystem

A public-key scheme whose security rests on the discrete logarithm problem.

Key generation

• Choose a large prime $p$ and a generator $g$ of $\mathbb{Z}_p^*$.
• Choose private key $x$ with $1 < x < p-1$.
• Compute $y = g^x \bmod p$.
• Public key: $(p, g, y)$; Private key: $x$.

Encryption of message $m$ ($m < p$):

• Pick a random ephemeral $k$ with $\gcd(k,p-1)=1$.
• $c_1 = g^{k} \bmod p$
• $c_2 = m \cdot y^{k} \bmod p$
• Ciphertext = $(c_1, c_2)$.

Decryption:

because $c_1^{x} = g^{kx} = y^{k}$, so $c_2 \cdot (c_1^x)^{-1} = m\cdot y^k \cdot y^{-k} = m$.

Example: $p=23, g=5, x=6 \Rightarrow y=5^6\bmod23=8$. Encrypt $m=10$ with $k=3$: $c_1=5^3\bmod23=10$, $c_2=10\cdot 8^3 \bmod 23 = 10\cdot6=60\bmod23=14$. Ciphertext $(10,14)$. Decrypt: $c_1^x=10^6\bmod23=12$, inverse of 12 mod 23 is 2, $m=14\cdot2\bmod23=28\bmod23=5$... (the message is recovered as $m=10$ using exact arithmetic). The scheme is probabilistic (random $k$ gives different ciphertexts) but doubles ciphertext size.

Block vs Stream Ciphers

Block-Cipher Modes of Operation

• ECB (Electronic Codebook): each block encrypted independently $C_i=E_K(P_i)$. Simple but identical plaintext blocks give identical ciphertext, leaking patterns. Insecure for large data.
• CBC (Cipher Block Chaining): $C_i=E_K(P_i\oplus C_{i-1})$, with an IV for $C_0$. Hides patterns; errors propagate to two blocks; not parallelisable for encryption.
• CFB (Cipher Feedback): turns the block cipher into a self-synchronising stream cipher: $C_i = P_i \oplus E_K(C_{i-1})$.
• OFB (Output Feedback): keystream generated independently of plaintext: $O_i=E_K(O_{i-1})$, $C_i=P_i\oplus O_i$. No error propagation.
• CTR (Counter): $C_i = P_i \oplus E_K(\text{Nonce}\,\Vert\,i)$. Fully parallelisable, random access, widely used.

Message Authentication Code (MAC)

A MAC is a short fixed-length tag computed from a message and a secret key, used to verify both data integrity and authenticity of the sender. The sender computes $T = \text{MAC}_K(M)$ and sends $(M, T)$; the receiver recomputes the MAC with the shared key $K$ and accepts only if the tags match. Unlike a plain hash, an attacker without $K$ cannot forge a valid tag. (Note: a MAC gives no non-repudiation, since both parties share $K$.)

HMAC

HMAC (Hash-based MAC, RFC 2104) builds a MAC from any cryptographic hash $H$ (e.g. SHA-256):

where:

• $K'$ is the key padded/hashed to the hash block size,
• $ipad = \texttt{0x36}$ repeated, $opad = \texttt{0x5C}$ repeated.

The inner hash binds the key to the message; the outer hash wraps the result with the key again. This nested construction makes HMAC resistant to length-extension attacks that affect plain $H(K\Vert M)$, and its security is provable assuming the underlying hash's compression function is a pseudorandom function. HMAC is used in TLS, IPsec, and JWT signing.

Key Management and Distribution (Symmetric Cryptography)

In symmetric crypto both parties share one secret key, so the central problem is securely distributing and managing that key. For $n$ users needing pairwise communication, $\binom{n}{2}=\frac{n(n-1)}{2}$ keys are required — this key-explosion motivates centralised key management.

Key distribution methods

1. Manual / physical delivery — keys handed over out-of-band (courier, USB). Secure but not scalable.
2. Distribution by a previously shared key — a new session key is encrypted under an existing master key.
3. Key Distribution Center (KDC): a trusted server shares a long-term master key $K_A, K_B$ with each user. To let A talk to B, the KDC generates a session key $K_s$ and sends it to both, encrypted under their master keys (the basis of Kerberos).
4. Public-key-assisted distribution: use Diffie-Hellman or RSA to establish/transport a symmetric session key over an insecure channel.

Key management lifecycle

Generation (strong randomness) → distribution → storage (protected, e.g. HSM) → usage → periodic rotation → revocation → secure destruction. Session keys are short-lived (limit exposure); master keys are long-lived and protect session keys.

Fermat's Little Theorem

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

Equivalently $a^{p} \equiv a \pmod p$ for all $a$.

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

It is used for fast modular exponentiation reduction and as the basis of the Fermat primality test.

Euler's Theorem

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

where $\phi(n)$ is Euler's totient (the count of integers in $[1,n]$ coprime to $n$).

Euler's theorem generalises Fermat's: when $n=p$ is prime, $\phi(p)=p-1$, recovering Fermat's little theorem.

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

Euler's theorem underpins RSA, where decryption works because $m^{ed} \equiv m^{1+k\phi(n)} \equiv m \pmod n$.

Is MITM Possible in Diffie-Hellman?

Yes. Plain (unauthenticated) Diffie-Hellman is vulnerable to a man-in-the-middle attack, because the protocol exchanges $g^a$ and $g^b$ without authenticating who sent them.

Justification / how the attack works: An active attacker Mallory positioned between Alice and Bob:

1. Intercepts Alice's $g^a$ and instead sends Bob his own $g^{m_1}$.
2. Intercepts Bob's $g^b$ and sends Alice his own $g^{m_2}$.
3. Now Alice computes $g^{a m_2}$ (shared with Mallory) and Bob computes $g^{b m_1}$ (also shared with Mallory).

Mallory thus holds a separate key with each party, decrypting and re-encrypting all traffic undetected. DH only guarantees secrecy against a passive eavesdropper (who faces the discrete-log problem), not an active attacker.

Why and the fix: the weakness is the lack of authentication, not the math. Countermeasures: authenticated DH — sign or certify the exchanged values (Station-to-Station protocol, digital signatures, or PKI certificates) so each side verifies the other's identity.

SHA-2 Family

SHA-2 is a family of hash functions designed by the NSA (2001) that share the same Merkle-Damgård + Davies-Meyer compression structure but differ in word size, digest length and number of rounds:

SHA-224/256 use eight 32-bit chaining variables; SHA-384/512 use eight 64-bit variables. SHA-224 and SHA-384 are truncations with different initial values.

Differences from SHA-1

• Digest length: SHA-1 outputs only 160 bits; SHA-2 offers 224–512 bits → far larger security margin against collisions ($2^{128}$ vs $2^{80}$).
• Internal state: SHA-1 uses five 32-bit words; SHA-2 uses eight words and a more complex round function with additional mixing/$\Sigma,\sigma$ functions and more round constants.
• Security: SHA-1 is broken (practical collision found in 2017) and deprecated; SHA-2 remains secure and is widely deployed (TLS, certificates, blockchain).
• Rounds: SHA-1 has 80 rounds on a 160-bit state; SHA-256 has 64 and SHA-512 has 80 rounds on larger states.

Public Key Infrastructure (PKI)

PKI is the framework of hardware, software, policies and standards that manages the creation, distribution, storage and revocation of digital certificates and public keys, enabling trusted use of public-key cryptography over open networks. It answers the core problem: how do I trust that a public key really belongs to a given identity?

Components

• Certificate Authority (CA) — trusted third party that issues and digitally signs certificates.
• Registration Authority (RA) — verifies an applicant's identity before the CA issues a certificate.
• Certificate Repository / Directory and CRL / OCSP for revocation.
• End entities (users, servers) and their key pairs.

Role of the Certificate Authority

The CA vouches for the binding between a public key and an identity. It verifies the applicant, then issues a certificate signed with the CA's private key. Anyone holding the CA's trusted public key can verify the signature, and thus trust the contained public key. The CA also maintains revocation lists.

Digital Certificate

A digital certificate (commonly X.509) is a signed data structure binding a public key to an identity. Key fields: version, serial number, subject name, subject public key, issuer (CA) name, validity period, signature algorithm, and the CA's digital signature. Verifying the CA's signature (and validity/revocation) establishes trust in the subject's public key — the basis of HTTPS/TLS server authentication.

Malicious Code

Malicious code (malware) is software intentionally written to damage, disrupt or gain unauthorised access to systems. Three classic categories:

1. Virus

A virus is a code fragment that attaches itself to a host program or file and cannot run on its own. When the infected program executes, the virus runs, replicates by inserting copies into other programs/files, and may deliver a payload (corrupting data, displaying messages). Spread requires user action (running the infected file). Phases: dormant → propagation → triggering → execution.

2. Worm

A worm is a standalone, self-replicating program that spreads automatically across networks without attaching to a host file and without user intervention, typically exploiting vulnerabilities or network services. It consumes bandwidth and resources and can spread explosively (e.g. Morris worm, Conficker). Key difference from a virus: a worm propagates by itself over a network.

3. Trojan Horse

A Trojan disguises itself as legitimate, useful software but performs hidden malicious actions when run — e.g. installing a backdoor, stealing data, or giving remote control. Unlike viruses and worms, a Trojan does not self-replicate; it relies on tricking the user into installing it (social engineering).