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

Feistel Cipher Structure

A Feistel cipher is a symmetric structure used to build many block ciphers (e.g. DES). The plaintext block is split into two halves and processed through several rounds, in each of which one half is transformed by a round function $F$ keyed with a round subkey, and then XORed with the other half.

For round $i$, given the halves $(L_{i-1}, R_{i-1})$:

        Plaintext (split into L0 | R0)
                 |
   +-------------+-------------+
   |                           |
  L0                          R0 ---> F(R0, K1)
   |                           |        |
   +------------ XOR <---------|--------+
   |                           |
  (swap) L1 = R0          R1 = L0 XOR F(R0,K1)
   |                           |
        ... repeat for n rounds ...
                 |
        Ciphertext (Rn | Ln)

Key features:

• Decryption uses the same structure, applying subkeys in reverse order $K_n \dots K_1$ — so encryption and decryption hardware/software are identical.
• The round function $F$ need not be invertible, giving great design freedom.
• Security depends on the number of rounds, the function $F$, and the key schedule (Shannon's confusion and diffusion).

AES Key Expansion: First 4 Bytes of the Next Round Key

The AES key is grouped into 4-byte words. The given 16-byte key gives:

The next round key starts with $W_4$, and the first 4 bytes of the next key are exactly $W_4$:

where $g$ = RotWord → SubWord → XOR Rcon(1).

Step 1 — RotWord($W_3$): cyclic left shift of (01 02 03 04) → (02 03 04 01).

Step 2 — SubWord (substitute each byte using the AES S-Box):

• 02 → 77
• 03 → 7B
• 04 → F2
• 01 → 7C

Result: (77 7B F2 7C).

Step 3 — XOR with Rcon(1) = (01 00 00 00):

So $g(W_3) =$ 76 7B F2 7C.

Step 4 — $W_4 = W_0 \oplus g(W_3)$:

So the first four bytes of the next round key after the first iteration are 5D 05 E7 6A.

Man-in-the-Middle Attack on Diffie–Hellman

The Diffie–Hellman (DH) key exchange has no authentication, so an active attacker (Eve) sitting between Alice and Bob can impersonate each to the other.

  Alice                Eve (attacker)              Bob
   |  g^a  ----------->  | (intercepts)            |
   |                     |  g^e  --------------->   |
   |                     |  <---------------  g^b   |
   |  <----------  g^e   | (intercepts)            |
   |                     |                          |
  shares g^(ae) with Eve |     shares g^(be) with Eve

1. Alice sends $g^{a}$; Eve intercepts it and sends her own $g^{e}$ to Bob.
2. Bob sends $g^{b}$; Eve intercepts it and sends $g^{e}$ to Alice.
3. Alice computes $K_1 = g^{ae}$ (thinking she shares it with Bob); Bob computes $K_2 = g^{be}$.
4. Eve knows both $K_1$ and $K_2$. She decrypts, reads/alters, and re-encrypts every message between them. Neither party detects the attack.

Countermeasure: authenticate the public values (e.g. signed DH, STS protocol, certificates) so Eve cannot substitute her keys.

ElGamal Encryption of M = 2

Given: prime $p = 19$, primitive root $g = 10$, private key $x = 5$, random integer $k = 4$, message $M = 2$.

Step 1 — public key $y = g^{x} \bmod p$:

• $10^{2} = 100 \equiv 5 \pmod{19}$
• $10^{4} = 5^{2} = 25 \equiv 6 \pmod{19}$
• $10^{5} = 10^{4}\cdot 10 = 6 \times 10 = 60 \equiv 3 \pmod{19}$

So $y = 3$. Public key: $(p,g,y) = (19, 10, 3)$.

Step 2 — $C_1 = g^{k} \bmod p$:

Step 3 — $C_2 = M \cdot y^{k} \bmod p$:

• $y^{4} = 3^{4} = 81 \equiv 81 - 76 = 5 \pmod{19}$
• $C_2 = 2 \times 5 = 10 \pmod{19}$

Ciphertext:

(Verification: $M = C_2\,(C_1^{x})^{-1} \bmod 19$. $C_1^{x} = 6^{5} \bmod 19 = 5$; $5^{-1} \equiv 4 \pmod{19}$; $M = 10 \times 4 = 40 \equiv 2 \pmod{19}$. ✓)

Properties of a Cryptographic Hash Function

A hash function $H$ maps an arbitrary-length message to a fixed-length digest. To be cryptographically secure it must satisfy:

1. Fixed output length: any input size produces a fixed-size digest (e.g. 160 bits for SHA-1).
2. Efficiency: $H(x)$ is fast to compute for any $x$.
3. Preimage resistance (one-way): given a hash $h$, it is infeasible to find any $x$ with $H(x)=h$.
4. Second preimage resistance (weak collision resistance): given $x$, it is infeasible to find $x' \neq x$ with $H(x') = H(x)$.
5. Collision resistance (strong): it is infeasible to find any two distinct inputs $x, x'$ with $H(x) = H(x')$.
6. Avalanche effect: a small change in input (even one bit) changes the output drastically.
7. Deterministic: the same input always yields the same digest.

SHA-1 Algorithm

SHA-1 takes a message of length $< 2^{64}$ bits and produces a 160-bit message digest. It processes the message in 512-bit blocks over 80 rounds per block.

Step 1 — Padding

The message is padded so its length $\equiv 448 \pmod{512}$: append a single 1 bit, then 0 bits, then a 64-bit representation of the original message length. Total length becomes a multiple of 512.

Step 2 — Initialize Buffer (five 32-bit words)

H0 = 67452301   H1 = EFCDAB89   H2 = 98BADCFE
H3 = 10325476   H4 = C3D2E1F0

Step 3 — Process each 512-bit block

For each block:

1. Expand the sixteen 32-bit words $W_0 \dots W_{15}$ into eighty words:

2. Set working variables $a,b,c,d,e = H_0,H_1,H_2,H_3,H_4$.
3. Run 80 rounds; for $t = 0 \dots 79$:

The round function $f_t$ and constant $K_t$ depend on the round group:

4. Add the working variables back into the buffer:

Step 4 — Output

After the last block, the digest is the concatenation:

Note: SHA-1 is now considered broken for collision resistance (practical collisions found in 2017) and is replaced by SHA-2/SHA-3 in modern systems.

Types of Malicious Logic

Malicious logic is code that performs unauthorized, harmful actions. Three common types:

1. Virus A program fragment that attaches itself to a host file or program and replicates by inserting copies of itself into other programs when the infected host runs. It requires a host and usually some user action to spread, and carries a payload that may corrupt or delete data.

2. Worm A stand-alone, self-replicating program that spreads across networks on its own, without attaching to a host or needing user action. It exploits system/network vulnerabilities to copy itself to other machines, consuming bandwidth and resources (e.g. the Morris worm).

3. Trojan Horse A program that masquerades as legitimate or useful software but secretly performs malicious actions such as data theft or installing a backdoor. It does not self-replicate and relies on deceiving the user into running it.

(Other examples of malicious logic include logic bombs, rootkits, spyware and ransomware.)

Playfair Cipher Encryption

Key: HELLOWORLD Plaintext: TURINGTEST

Step 1 — Build the 5×5 key matrix (I/J share a cell)

Write the key letters left-to-right (dropping repeats), then fill with the remaining alphabet. Unique key letters: H E L O W R D.

Step 2 — Split plaintext into digraphs

TURINGTEST → TU · RI · NG · TE · ST (no repeated-letter or odd-length padding needed).

Step 3 — Apply Playfair rules

Same row → take letter to the right; same column → take letter below; rectangle → take letter in the same row but the other pair's column.

(rows/cols numbered from 0)

Result

Modes of Block Cipher Encryption

A block cipher only encrypts one fixed-size block; a mode of operation defines how to securely encrypt messages longer than one block. Two important modes:

1. Electronic Codebook (ECB)

Each plaintext block is encrypted independently with the same key:

P1 ->[E_K]-> C1     P2 ->[E_K]-> C2     P3 ->[E_K]-> C3

• Pros: simple, blocks can be processed in parallel, random access.
• Cons: identical plaintext blocks produce identical ciphertext blocks, so data patterns leak (the classic "ECB penguin"). Insecure for structured data.

2. Cipher Block Chaining (CBC)

Each plaintext block is XORed with the previous ciphertext block before encryption, using an Initialization Vector (IV) for the first block:

P1 -XOR(IV)->[E_K]-> C1
P2 -XOR(C1)->[E_K]-> C2
P3 -XOR(C2)->[E_K]-> C3

• Pros: identical plaintext blocks give different ciphertext (hides patterns); each block depends on all previous blocks.
• Cons: encryption is sequential (cannot parallelize); a transmission error in $C_{i-1}$ corrupts two decrypted blocks; requires a random IV.

(Other modes include CFB, OFB and CTR, which turn the block cipher into a stream cipher.)

Fermat's Theorem (Fermat's Little Theorem)

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

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

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

It is widely used for modular exponentiation, computing inverses, and primality testing (Fermat test) in cryptography.

Implication of the Discrete Logarithm

Given a prime $p$, a generator $g$ of $\mathbb{Z}_p^{*}$, and a value $y = g^{x} \bmod p$, the discrete logarithm problem (DLP) is to find the exponent $x$.

• Forward direction is easy: computing $y = g^{x} \bmod p$ is fast (modular exponentiation).
• Reverse direction is hard: recovering $x$ from $y$ is computationally infeasible for large $p$ — it is a presumed one-way / trapdoor function.

Implication: This asymmetry is the security foundation of several public-key schemes — Diffie–Hellman key exchange, ElGamal encryption, the Digital Signature Algorithm (DSA), and elliptic-curve cryptography (ECDLP). Their secrecy holds only as long as the discrete logarithm remains intractable; an efficient DLP solver (e.g. a large quantum computer running Shor's algorithm) would break all of them.

Digital Signature Algorithm (DSA)

DSA is a standard (FIPS 186) for generating and verifying digital signatures. Its security relies on the discrete logarithm problem. A signature provides authentication, integrity, and non-repudiation, but (unlike RSA signing) DSA is used only for signing, not encryption.

Parameter & Key Generation

• Choose a large prime $p$ and a prime $q$ that divides $p-1$.
• Choose $g = h^{(p-1)/q} \bmod p$ (an element of order $q$).
• Private key: random $x$ with $0 < x < q$.
• Public key: $y = g^{x} \bmod p$.
• Public parameters: $(p, q, g, y)$.

Signing a message $M$ (signer with private key $x$)

1. Pick a fresh random secret $k$, $0 < k < q$.
2. Compute $r = (g^{k} \bmod p) \bmod q$.
3. Compute the hash $H(M)$ and

4. The signature is the pair $(r, s)$, sent with $M$.

Verification (verifier with public key $y$)

1. Compute $w = s^{-1} \bmod q$.
2. Compute $u_1 = H(M)\,w \bmod q$ and $u_2 = r\,w \bmod q$.
3. Compute $v = \big((g^{u_1} y^{u_2}) \bmod p\big) \bmod q$.
4. Accept the signature if and only if $v = r$.

  Sign:    M -> H(M) -> (r,s) using x, k
  Send:    (M, r, s)
  Verify:  recompute v from H(M), r, s, y  ->  v == r ?  -> valid

Key points: the hash binds the signature to the message (integrity); only the holder of $x$ can produce a valid $(r,s)$ (authentication & non-repudiation); the random $k$ must be unique and secret for every signature — reusing $k$ leaks the private key.

Firewall

A firewall is a hardware or software system placed between a trusted internal network and an untrusted external network (e.g. the Internet) that filters traffic according to a security policy, allowing or blocking packets/connections.

Types of Firewalls

1. Packet-Filtering Firewall Operates at the network/transport layer. It inspects each packet's header — source/destination IP, port, and protocol — and accepts or drops it based on a rule set (ACL).

• Pros: fast, cheap, transparent.
• Cons: stateless; cannot see application content; vulnerable to spoofing.

2. Stateful Inspection Firewall Keeps a state table of active connections and evaluates packets in the context of the whole session (e.g. only allows reply packets that belong to an established connection).

• Pros: more secure than simple packet filters; tracks connection state.
• Cons: more resource-intensive.

3. Application-Level Gateway (Proxy Firewall) Works at the application layer; a proxy relays traffic for specific applications (HTTP, FTP). It inspects the actual content of requests/responses.

• Pros: deep inspection, hides internal hosts, strong control.
• Cons: slow; needs a separate proxy per application.

4. Circuit-Level Gateway Operates at the session layer; it validates the TCP handshake/session setup (e.g. SOCKS) and then relays data without inspecting content.

• Pros: low overhead, hides internal network.
• Cons: no content inspection.

(Modern "Next-Generation Firewalls" combine stateful inspection with deep-packet inspection, IPS and application awareness.)

Hill Cipher Decryption

Ciphertext: HI Key matrix (columns 5,4 and 3,3):

with letter values $A=0, B=1, \dots, Z=25$, so $H = 7$, $I = 8$, and $C = \begin{bmatrix}7\\8\end{bmatrix}$.

Decryption uses the inverse key matrix mod 26: $P = K^{-1} C \bmod 26$.

Step 1 — Determinant of K (mod 26)

Step 2 — Modular inverse of the determinant

Find $3^{-1} \bmod 26$: $3 \times 9 = 27 \equiv 1 \pmod{26}$, so $(\det K)^{-1} = 9$.

Step 3 — Adjugate of K

Step 4 — Inverse key matrix

Step 5 — Recover plaintext

• $P_1 = (1)(7) + (25)(8) = 7 + 200 = 207 \equiv 207 - 182 = 25 \;(\to Z)$
• $P_2 = (16)(7) + (19)(8) = 112 + 152 = 264 \equiv 264 - 260 = 4 \;(\to E)$

(Check by re-encrypting: $K\begin{bmatrix}25\\4\end{bmatrix} = \begin{bmatrix}5\cdot25+3\cdot4\\4\cdot25+3\cdot4\end{bmatrix} = \begin{bmatrix}137\\112\end{bmatrix} \equiv \begin{bmatrix}7\\8\end{bmatrix} = \text{HI}. \checkmark$)

Digital Certificate

A digital certificate is an electronic document that binds a public key to the identity of its owner, and is digitally signed by a trusted third party called a Certificate Authority (CA). It lets a relying party trust that a given public key really belongs to the named subject (preventing public-key substitution / MITM).

The common standard is X.509, whose fields include: version, serial number, signature algorithm, issuer (CA) name, validity period (not-before / not-after), subject name, subject's public key, extensions, and the CA's digital signature.

Certificate Life Cycle

1. Key generation: the subject (or CA) generates a public/private key pair.
2. Registration / Enrollment: the applicant submits a Certificate Signing Request (CSR) with their public key and identity to a Registration Authority (RA).
3. Verification (Identity validation): the RA/CA verifies the applicant's identity and ownership of the key.
4. Issuance: the CA creates the certificate, signs it with the CA private key, and delivers it to the subject.
5. Distribution / Publication: the certificate is published (directory, LDAP) and used to establish secure communication.
6. Usage / Validation: relying parties verify the CA's signature, the validity period, and revocation status (via CRL or OCSP) before trusting it.
7. Renewal: before expiry, the certificate is re-issued (usually with a new validity period / key).
8. Revocation: if the private key is compromised or details change, the CA revokes the certificate early and lists it on a CRL (Certificate Revocation List) / OCSP.
9. Expiration / Destruction: after the validity period ends, the certificate expires and associated keys are securely archived or destroyed.

Key-gen -> Enroll(CSR) -> Verify -> Issue -> Distribute -> Use
                                               |
                                  Renew <------+------> Revoke -> Expire

Authentication System

An authentication system is a mechanism that verifies the claimed identity of an entity (user, host, or process) before granting access. It answers "are you who you say you are?" and is based on one or more factors:

• Something you know — password, PIN, passphrase.
• Something you have — smart card, token, OTP device.
• Something you are — biometrics (fingerprint, iris, face).

Combining two or more factors gives multi-factor authentication (MFA), which is far stronger than a single factor. A good authentication system also resists eavesdropping and replay of credentials.

Challenge–Response System

A challenge–response authentication scheme proves identity without transmitting the secret itself, defeating eavesdropping and replay attacks.

Working mechanism:

1. The claimant requests access to the verifier.
2. The verifier sends a random, one-time challenge (a nonce) to the claimant.
3. The claimant computes a response by applying a secret-keyed function to the challenge — e.g. encrypting it or hashing it together with the shared secret:

4. The verifier performs the same computation (or verifies it) and grants access only if the response matches.

  Claimant                         Verifier
     |  request access  ------------->  |
     |  <-----------  random challenge  |
     |  response = f(secret,challenge)->|
     |                          verify  | -> grant / deny

Advantages:

• The secret is never sent over the network.
• Because the challenge is fresh each time, an attacker who records an old response cannot replay it.
• Used in CHAP, Kerberos, OTP/token systems and smart-card authentication.