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

Classical Encryption Techniques

Classical encryption operates on plaintext letters using substitution (replacing letters with others) and transposition (rearranging letter positions). They use a shared secret key and are vulnerable to frequency analysis. Two important polyalphabetic/digraph-and-matrix examples are the Playfair and Hill ciphers.

Playfair Cipher

The Playfair cipher is a digraph substitution cipher that encrypts pairs of letters using a $5\times5$ key matrix built from a keyword (I and J share a cell).

Key = MONARCHY:

Rules for each digraph (insert filler X between identical letters; pad odd length):

1. Same row → take the letter to the right (wrap around).
2. Same column → take the letter below (wrap around).
3. Rectangle → each letter is replaced by the letter in its own row at the other letter's column.

Example: encrypt BALLOON → split as BA LX LO ON.

• BA: rectangle → IB → IB
• LX: rectangle → SU
• LO: rectangle → PM
• ON: same row → NA

Ciphertext = IBSUPMNA.

Hill Cipher

The Hill cipher is a polygraphic substitution cipher based on linear algebra mod 26. A block of $n$ letters (as numbers $A=0\dots Z=25$) is encrypted by multiplying with an invertible $n\times n$ key matrix $K$:

Example ($2\times2$): $K=\begin{bmatrix}3 & 3\\2 & 5\end{bmatrix}$, plaintext HI = $\begin{bmatrix}7\\8\end{bmatrix}$.

So ciphertext = TC. Decryption uses $K^{-1}\pmod{26}$ (which exists only if $\gcd(\det K,26)=1$).

Digital Signature

A digital signature is a cryptographic value, computed from a message and the signer's private key, that lets any verifier confirm the message's authenticity, integrity and origin using the signer's public key. Unlike encryption (which provides confidentiality), a signature provides proof of who created the message and that it was not altered.

Digital Signature Scheme Using RSA

RSA can be used in reverse for signing: the signer encrypts the message digest with the private key, and anyone can verify with the public key.

Setup: key pair public $(e,n)$ and private $(d,n)$ where $ed\equiv1\pmod{\phi(n)}$.

Signing (by sender):

1. Compute a hash of the message: $h = H(M)$.
2. Sign with the private key: $S = h^{d} \bmod n$.
3. Send $(M, S)$.

Verification (by receiver):

1. Recover the hash: $h' = S^{e} \bmod n$.
2. Independently compute $h = H(M)$.
3. If $h' = h$, the signature is valid; otherwise it is rejected.

Hashing before signing ensures fixed-size input, efficiency, and security.

Role in Authentication and Non-Repudiation

• Authentication: Only the holder of the private key could produce a signature that verifies with the matching public key, so a valid signature authenticates the sender's identity.
• Integrity: Because the signature is over the message hash, any change to $M$ makes $H(M)\ne h'$, exposing tampering.
• Non-repudiation: Since the private key is known only to the signer, the signer cannot later deny having signed the message; the signature is binding evidence accepted by a third party (e.g., in disputes).

RSA Algorithm

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

Key Generation

1. Choose two large primes $p$ and $q$.
2. Compute $n = p \cdot q$ (the modulus).
3. Compute $\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

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

1. $n = 7\times11 = 77$.
2. $\phi(n) = (7-1)(11-1) = 6\times10 = 60$.
3. Choose $e=13$ ($\gcd(13,60)=1$).
4. Find $d$ with $13d \equiv 1 \pmod{60}$. Since $13\times37 = 481 = 8\times60 + 1$, we get $d = 37$.

• Public key $=(13,77)$, Private key $=(37,77)$.

Encryption of $M=8$:

Compute by repeated squaring: $8^2=64$, $8^4=64^2=4096\equiv15$, $8^8\equiv15^2=225\equiv71\pmod{77}$.

So $C = \mathbf{50}$.

Verification (decryption): $M = 50^{37} \bmod 77 = 8$, recovering the original message.

(Note: with $e=7$ instead, $d=43$ and $C=8^7\bmod77=57$; any valid $e$ coprime to 60 works.)

SHA-2 Family and Differences from SHA-1

SHA-2 is a family of cryptographic hash functions designed by the NSA (2001) using a Merkle–Damgård construction with Davies–Meyer compression. Members differ in digest length and internal word size:

Differences from SHA-1

• Digest length: SHA-1 produces only 160 bits; SHA-2 produces 224–512 bits, giving a much larger output space.
• Security: SHA-1 is broken for collision resistance (practical collisions demonstrated, e.g., SHAtter 2017); SHA-2 has no known practical collision attacks.
• Rounds & complexity: SHA-2 uses more rounds (64/80) and a more complex message schedule and round function.
• Word size: SHA-1 and SHA-256 use 32-bit words; SHA-384/512 use 64-bit words for efficiency on 64-bit hardware.

SHA-2 is therefore recommended over SHA-1 for digital signatures, certificates and integrity checks.

Public Key Infrastructure (PKI)

PKI is the framework of hardware, software, policies, standards and procedures used to create, manage, distribute, store and revoke digital certificates and public–private key pairs. It binds public keys to verified identities, enabling secure, trusted communication over insecure networks.

Core components: Certificate Authority (CA), Registration Authority (RA), digital certificates, a certificate repository/directory, and a Certificate Revocation List (CRL)/OCSP.

Certificate Authority (CA)

The CA is the trusted third party that:

• Verifies the identity of an applicant (often via an RA).
• Issues digital certificates by digitally signing them with the CA's own private key.
• Revokes compromised or expired certificates and publishes a CRL.
• Acts as the root of trust; clients trust certificates that chain up to a trusted root CA.

Digital Certificates

A digital certificate (typically X.509) is an electronic document that binds a public key to an identity. It contains:

• Subject name (owner) and the subject's public key,
• Issuer (CA) name, serial number, validity period,
• The CA's digital signature over the certificate.

When a party presents its certificate, the receiver verifies the CA's signature using the CA's public key, thereby trusting that the enclosed public key truly belongs to the named subject—providing authentication and enabling secure key exchange (e.g., in TLS/HTTPS).

Malicious Code: Viruses, Worms and Trojan Horses

Malicious code (malware) is any program intentionally written to damage systems, steal data or disrupt operations.

Virus

A virus is a code fragment that attaches itself to a host program or file and replicates by inserting copies into other programs when the infected host runs. It requires human action (running the infected file) to spread. Phases: dormant → propagation → triggering → execution (payload). Example: file-infector and macro viruses.

Worm

A worm is a standalone, self-replicating program that spreads automatically across networks by exploiting vulnerabilities, without needing a host file or user action. It consumes bandwidth and resources and can carry payloads. Example: Morris worm, Conficker.

Trojan Horse

A Trojan horse is a program that masquerades as legitimate or useful software but secretly performs malicious actions (e.g., installing a backdoor, stealing credentials). It does not self-replicate; it relies on social engineering to trick the user into installing it.

Key distinction: a virus needs a host and user action; a worm self-propagates over networks; a Trojan does not replicate but disguises its malicious intent.

Chinese Remainder Theorem (CRT)

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

has a unique solution modulo $M$.

The solution is $x \equiv \sum_{i=1}^{k} a_i\, M_i\, y_i \pmod{M}$, where $M_i = M/m_i$ and $y_i = M_i^{-1} \bmod m_i$.

Worked Example

Solve:

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

• $M_1 = 105/3 = 35,\; y_1 = 35^{-1}\bmod 3 = 2^{-1}\equiv 2$.
• $M_2 = 105/5 = 21,\; y_2 = 21^{-1}\bmod 5 = 1^{-1}\equiv 1$.
• $M_3 = 105/7 = 15,\; y_3 = 15^{-1}\bmod 7 = 1^{-1}\equiv 1$.

$233 \bmod 105 = 23$.

Answer: $x \equiv \mathbf{23} \pmod{105}$ (check: $23\bmod3=2$, $23\bmod5=3$, $23\bmod7=2$).

Security Goals (CIA Triad) and Types of Attacks

Goals of Security

• Confidentiality: Ensures information is accessible only to authorized parties; prevents unauthorized disclosure (achieved by encryption, access control).
• Integrity: Ensures data is accurate and not altered by unauthorized parties; any modification is detectable (achieved by hashes, MACs, digital signatures).
• Availability: Ensures systems and data are accessible to authorized users whenever needed (protected against DoS, ensured by redundancy/backups).

Types of Security Attacks

Classified (per Stallings) as passive and active:

Passive attacks (eavesdropping; hard to detect, aim is to obtain information):

• Release of message contents
• Traffic analysis

Active attacks (modify data or affect operation):

• Masquerade – pretending to be another entity
• Replay – capturing and retransmitting data
• Modification of messages – altering content/order
• Denial of Service (DoS) – disrupting availability

Alternatively by goal: interception (confidentiality), modification & fabrication (integrity), and interruption (availability).

Symmetric vs Asymmetric Key Cryptography

Symmetric cryptography uses the same key, e.g., AES encrypts and decrypts a file with one shared key. Asymmetric uses mathematically related but different keys: data encrypted with the public key can only be decrypted with the matching private key (e.g., RSA); this solves the key-distribution problem and enables digital signatures.

In practice, hybrid systems combine both: asymmetric crypto exchanges a session key, then fast symmetric crypto encrypts the actual data.

Caesar Cipher and Mono-alphabetic Substitution

Caesar Cipher

A Caesar cipher shifts each plaintext letter by a fixed key $k$:

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

Cryptanalysis: there are only 25 possible keys, so a brute-force (exhaustive key search) attack tries all shifts and inspects which produces readable plaintext — trivially broken.

Mono-alphabetic Substitution Cipher

Each plaintext letter is mapped to a fixed but arbitrary ciphertext letter using a permutation of the alphabet, giving a key space of $26! \approx 4\times10^{26}$, far too large for brute force.

Cryptanalysis: it is broken by frequency analysis, because the substitution preserves the statistical structure of the language. The analyst:

1. Counts letter frequencies in the ciphertext.
2. Maps the most frequent ciphertext letters to common English letters (E, T, A, O...).
3. Uses common digrams (TH, HE) and trigrams (THE, ING) to refine the mapping until plaintext emerges.

Thus, despite a huge key space, the mono-alphabetic cipher is insecure because it leaks language statistics.

Modular Arithmetic and Euler's Totient Function

Modular Arithmetic

Modular arithmetic deals with integers that wrap around upon reaching a modulus $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$. It satisfies addition, subtraction and multiplication congruences and is the foundation of RSA, Diffie–Hellman, etc. Example: $17 \equiv 2 \pmod 5$.

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

$\phi(n)$ counts the positive integers $\le n$ that are coprime to $n$ (i.e., $\gcd(k,n)=1$).

• For a prime $p$: $\phi(p) = p-1$.
• If $n = p_1^{a_1} p_2^{a_2}\cdots$, then $\phi(n) = n\prod_i\left(1-\dfrac{1}{p_i}\right)$.
• Multiplicative: $\phi(mn)=\phi(m)\phi(n)$ when $\gcd(m,n)=1$.

Computations

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

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

ElGamal Cryptosystem

ElGamal is a public-key encryption scheme whose security relies on the difficulty of the discrete logarithm problem in a cyclic group. It is probabilistic (randomized).

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 \le x \le p-2$.
3. Compute $y = g^{x} \bmod p$.

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

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

1. Pick a random ephemeral key $k$, $1 \le k \le p-2$.
2. Compute $C_1 = g^{k} \bmod p$ and $C_2 = M \cdot y^{k} \bmod p$.
3. Ciphertext $= (C_1, C_2)$.

Decryption

Using private key $x$:

since $C_1^{x} = g^{kx} = y^{k}$, the masking factor cancels.

Example

Let $p=11$, $g=2$, private $x=3$, so $y = 2^3 \bmod 11 = 8$. Encrypt $M=7$ with $k=4$:

• $C_1 = 2^4 \bmod 11 = 5$.
• $C_2 = 7 \cdot 8^{4} \bmod 11 = 7 \cdot 4096 \bmod 11 = 7 \cdot 4 = 28 \equiv 6$.
• Ciphertext $=(5,6)$.

Decrypt: $C_1^{x}=5^3=125\equiv 4$; inverse of $4 \bmod 11$ is $3$; $M = 6\cdot3 = 18 \equiv 7 \pmod{11}$. ✓