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

Digital Signature

A digital signature is a cryptographic value, computed from the data and a signer's private key, that binds the identity of the signer to the message. It provides authentication, data integrity, and non-repudiation. Unlike a handwritten signature, it is a function of the message itself, so any change to the message invalidates the signature.

Digital Signature Using RSA

RSA signing is the reverse of RSA encryption: the signer uses the private key to sign, and any verifier uses the public key to verify.

Key setup (same as RSA):

• Choose primes $p, q$; compute $n = pq$ and $\phi(n) = (p-1)(q-1)$.
• Choose public exponent $e$ with $\gcd(e, \phi(n)) = 1$; compute private exponent $d \equiv e^{-1} \pmod{\phi(n)}$.
• Public key: $(e, n)$; private key: $(d, n)$.

Signing (by sender A): compute a hash $h = H(M)$ of the message, then

A sends $(M, S)$.

Verification (by receiver B): using A's public key,

and independently compute $H(M)$. If $h' = H(M)$, the signature is valid.

In practice the message is hashed first (e.g. SHA-256) so that signing works on a fixed-size digest and to prevent existential forgery.

Role in Authentication and Non-Repudiation

• Authentication: Only the holder of the private key could have produced $S$ such that $S^{e} \bmod n$ equals the message hash. Successful verification with A's public key proves the message came from A.
• Integrity: If the message is altered in transit, $H(M)$ changes and verification fails.
• Non-repudiation: Because only A possesses the private key $d$, A cannot later deny having signed the message — a third party can verify the signature using the publicly known key, providing legal/dispute-resolution evidence.

RSA Algorithm

RSA is a public-key (asymmetric) cryptosystem whose security rests on the difficulty of factoring large integers.

Key Generation

1. Choose two large primes $p$ and $q$.
2. Compute $n = p \times q$.
3. Compute Euler's totient $\phi(n) = (p-1)(q-1)$.
4. Choose public exponent $e$ with $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$.
5. Compute private exponent $d \equiv e^{-1} \pmod{\phi(n)}$.

• Public key: $(e, n)$ Private key: $(d, n)$.

Encryption / Decryption

• Encryption: $C = M^{e} \bmod n$.
• Decryption: $M = C^{d} \bmod n$.

Worked Example: $p = 7$, $q = 11$, $M = 8$

Step 1 — n: $n = 7 \times 11 = 77$.

Step 2 — totient: $\phi(n) = (7-1)(11-1) = 6 \times 10 = 60$.

Step 3 — choose e: pick $e = 13$ (since $\gcd(13, 60) = 1$).

Step 4 — compute d: find $d$ with $13d \equiv 1 \pmod{60}$. $13 \times 37 = 481 = 8 \times 60 + 1 \equiv 1 \pmod{60}$, so $d = 37$.

• Public key: $(e, n) = (13, 77)$
• Private key: $(d, n) = (37, 77)$

Step 5 — encrypt M = 8:

Using successive squaring mod 77:

• $8^{2} = 64$
• $8^{4} = 64^{2} = 4096 \equiv 15 \pmod{77}$
• $8^{8} = 15^{2} = 225 \equiv 71 \pmod{77}$
• $8^{13} = 8^{8} \cdot 8^{4} \cdot 8^{1} = 71 \times 15 \times 8$.
• $71 \times 15 = 1065 \equiv 64 \pmod{77}$; $64 \times 8 = 512 \equiv 50 \pmod{77}$.

(Check: decryption $50^{37} \bmod 77 = 8$ recovers the message.)

Data Encryption Standard (DES)

DES is a symmetric block cipher that encrypts 64-bit plaintext blocks under a 56-bit effective key (64-bit key with 8 parity bits) using a 16-round Feistel network.

Overall Structure (Block Diagram in words)

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

A separate key schedule takes the 56-bit key, applies Permuted Choice 1 (PC-1), splits it into two 28-bit halves, and for each round performs left circular shifts followed by Permuted Choice 2 (PC-2) to produce sixteen 48-bit subkeys $K_1 \dots K_{16}$.

A Single DES Round (Feistel structure)

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

The right half is fed into the round function $F$ together with the round subkey, and the result is XORed with the left half.

The Function F (Mangler Function)

$F(R, K_i)$ operates on a 32-bit input and a 48-bit subkey in four steps:

1. Expansion (E): the 32-bit $R$ is expanded to 48 bits by the E-box (duplicating some bits).
2. Key mixing: XOR the 48-bit expanded value with the 48-bit subkey $K_i$.
3. Substitution (S-boxes): the 48 bits are split into eight 6-bit groups; each enters one of eight S-boxes, each outputting 4 bits → 32 bits total. The S-boxes provide non-linearity (confusion) and are the heart of DES security.
4. Permutation (P): the 32-bit S-box output is permuted by the P-box to spread bits (diffusion).

After 16 rounds the halves are swapped and passed through $IP^{-1}$ to yield the ciphertext. Decryption uses the identical algorithm with subkeys applied in reverse order ($K_{16} \dots K_1$).

Malicious Code

Virus: A program fragment that attaches itself to a host file/program and replicates by inserting copies into other programs when the infected host is executed. It needs a host and usually user action (running the file) to spread, and carries a payload that may damage data.

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

Trojan Horse: A program that masquerades as legitimate/useful software but secretly performs malicious actions (data theft, backdoor installation). It does not self-replicate; it relies on tricking the user into running it.

Chinese Remainder Theorem (CRT)

Statement: If $m_1, m_2, \dots, m_k$ are pairwise coprime positive integers, then the system

has a unique solution modulo $M = m_1 m_2 \cdots m_k$.

Construction: Let $M_i = M/m_i$ and $y_i \equiv M_i^{-1} \pmod{m_i}$. Then

Example

Solve: $x \equiv 2 \pmod 3,\; x \equiv 3 \pmod 5,\; x \equiv 2 \pmod 7$.

• $M = 3 \cdot 5 \cdot 7 = 105$.
• $M_1 = 35$, $M_2 = 21$, $M_3 = 15$.
• Inverses: $35 \equiv 2 \pmod 3 \Rightarrow y_1 = 2$ (since $2\cdot2=4\equiv1$). $21 \equiv 1 \pmod 5 \Rightarrow y_2 = 1$. $15 \equiv 1 \pmod 7 \Rightarrow y_3 = 1$.
• $x = 2(35)(2) + 3(21)(1) + 2(15)(1) = 140 + 63 + 30 = 233$.
• $233 \bmod 105 = 23$.

Check: $23 = 7\cdot3+2 \equiv 2 \pmod3$, $23 = 4\cdot5+3 \equiv 3\pmod5$, $23 = 3\cdot7+2 \equiv 2\pmod7$. ✓

Goals of Security (CIA Triad)

• Confidentiality: Ensures information is accessible only to authorized parties; data is protected from unauthorized disclosure (achieved via encryption, access control).
• Integrity: Ensures information is not altered in an unauthorized or undetected manner; data remains accurate and trustworthy (achieved via hashes, MACs, digital signatures).
• Availability: Ensures information and resources are accessible to authorized users when needed; systems resist disruption (achieved via redundancy, backups, DoS protection).

Types of Security Attacks

Passive attacks (eavesdropping; threaten confidentiality):

• Release of message contents (interception/snooping).
• Traffic analysis (inferring info from message patterns).

Active attacks (modify data/stream; threaten integrity & availability):

• Masquerade (impersonation / fabrication of identity).
• Replay (capturing and retransmitting data).
• Modification of messages (altering message contents).
• Denial of Service (DoS) (disrupting availability).

In terms of information flow these correspond to interception, modification, fabrication, and interruption.

Symmetric vs Asymmetric Key Cryptography

In practice the two are combined (hybrid cryptography): an asymmetric algorithm (e.g. RSA) securely exchanges a session key, and a fast symmetric algorithm (e.g. AES) encrypts the actual bulk data.

Caesar Cipher

A monoalphabetic substitution cipher that shifts each letter by a fixed amount $k$ (classically $k=3$):

Example ($k=3$): plaintext HELLO → ciphertext KHOOR.

Cryptanalysis: There are only 25 possible keys, so it is broken by brute force (exhaustive key search) — try all shifts until readable text appears.

General Monoalphabetic Substitution Cipher

Each plaintext letter is mapped to a fixed but arbitrary ciphertext letter (a permutation of the alphabet), giving $26! \approx 4 \times 10^{26}$ keys — far too many for brute force.

Cryptanalysis: Broken by frequency analysis, because the cipher preserves letter-frequency statistics of the language. The analyst:

1. Counts ciphertext letter frequencies.
2. Maps the most frequent ciphertext letters to common English letters (E, T, A, O...).
3. Uses digram/trigram patterns (TH, THE) to confirm and complete the substitution.

Thus, despite the huge key space, the monoalphabetic cipher is insecure because it does not hide the underlying language statistics.

Modular Arithmetic

Modular arithmetic is arithmetic over a fixed modulus $n$, where numbers "wrap around" after reaching $n$. We write $a \equiv b \pmod n$ if $n \mid (a-b)$, i.e. $a$ and $b$ leave the same remainder when divided by $n$. Operations $+, -, \times$ are well-defined on residue classes $\{0,1,\dots,n-1\}$. It is the foundation of most public-key cryptography (RSA, Diffie-Hellman, ElGamal).

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

$\phi(n)$ counts the integers in $\{1, 2, \dots, n\}$ that are coprime to $n$.

• For a prime $p$: $\phi(p) = p-1$.
• For $n = p^{k}$: $\phi(p^k) = p^k - p^{k-1}$.
• Multiplicative: if $\gcd(m,n)=1$ then $\phi(mn) = \phi(m)\phi(n)$.

Euler's theorem: if $\gcd(a,n)=1$ then $a^{\phi(n)} \equiv 1 \pmod n$.

Computations

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

$\phi(24)$: $24 = 2^{3} \times 3$, so

ElGamal Cryptosystem

ElGamal is a public-key cryptosystem whose security relies on the difficulty of the Discrete Logarithm Problem in a finite cyclic group.

Key Generation

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

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

Encryption (of message $M$, $M < p$)

Sender picks a random ephemeral key $k$ ($1 < k < p-1$) and computes:

Ciphertext is the pair $(C_1, C_2)$.

Decryption

Receiver uses private key $x$:

This works because $C_1^{x} = g^{kx} = y^{k}$, which cancels the $y^k$ factor in $C_2$.

Example (small numbers)

Let $p=11$, $g=2$, $x=3$ → $y = 2^3 \bmod 11 = 8$. Public key $(11,2,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 = 28 \equiv 6$. Ciphertext $(5,6)$.

Note: Because of the random $k$, ElGamal is probabilistic — the same message encrypts to different ciphertexts each time, and the ciphertext is roughly twice the message size.

Block Cipher vs Stream Cipher

Modes of Operation of Block Ciphers

1. ECB (Electronic Codebook): Each block encrypted independently: $C_i = E_K(P_i)$. Simple but identical plaintext blocks give identical ciphertext (leaks patterns) — insecure for structured data.
2. CBC (Cipher Block Chaining): Each plaintext block is XORed with the previous ciphertext before encryption: $C_i = E_K(P_i \oplus C_{i-1})$, with $C_0 = IV$. Hides patterns; errors propagate to two blocks.
3. CFB (Cipher Feedback): Turns the block cipher into a self-synchronizing stream cipher: $C_i = P_i \oplus E_K(C_{i-1})$.
4. OFB (Output Feedback): Generates a keystream independent of plaintext: $O_i = E_K(O_{i-1})$, $C_i = P_i \oplus O_i$. No error propagation.
5. CTR (Counter): Encrypts an incrementing counter to form a keystream: $C_i = P_i \oplus E_K(\text{counter}_i)$. Parallelizable and random-access.

All feedback modes require an Initialization Vector (IV) to ensure that identical plaintexts encrypt differently.

Message Authentication Code (MAC)

A MAC is a short, fixed-length tag computed from a message and a shared secret key $K$: $\text{MAC} = C_K(M)$. It provides data integrity and authentication — the receiver, who shares $K$, recomputes the MAC and accepts the message only if the tags match. An attacker without $K$ cannot forge a valid tag for a modified message. (A MAC does not provide non-repudiation, since both parties share the key.)

HMAC (Hash-based MAC)

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

where:

• $ipad$ = the byte 0x36 repeated to block size,
• $opad$ = the byte 0x5C repeated to block size,
• $\|$ denotes concatenation, $\oplus$ is XOR, and $K$ is padded to the hash block size.

How it works:

1. The key is padded and XORed with $ipad$, prepended to the message, and hashed → inner hash.
2. The key is padded and XORed with $opad$, prepended to the inner hash, and hashed again → final HMAC.

The two nested hashes with two key-derived values make HMAC resistant to length-extension and other attacks, so its security depends only on the strength of the underlying hash and the secrecy of $K$.