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

Cryptographic Hash Functions

A cryptographic hash function $H$ maps a message $M$ of arbitrary length to a fixed-length output $h = H(M)$ called the message digest. It must satisfy:

• Pre-image resistance (one-way): given $h$, it is infeasible to find $M$ with $H(M)=h$.
• Second pre-image resistance: given $M$, it is infeasible to find $M' \neq M$ with $H(M')=H(M)$.
• Collision resistance: it is infeasible to find any pair $(M, M')$ with $H(M)=H(M')$.
• Avalanche effect: a 1-bit change in input flips ~half the output bits.

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

SHA-1 Algorithm

SHA-1 takes a message of length $< 2^{64}$ bits and produces a 160-bit digest. It follows the Merkle–Damgård construction.

Step 1 – Padding. Append a 1 bit, then 0 bits, until the length $\equiv 448 \pmod{512}$. Append the original message length as a 64-bit integer, making the total a multiple of 512 bits.

Step 2 – Parse into blocks. Split into $N$ blocks $M_1,\dots,M_N$ of 512 bits each; each block is 16 words of 32 bits.

Step 3 – Initialize 5 chaining variables (160 bits total):

Step 4 – Message schedule. Expand the 16 words $W_0..W_{15}$ to 80 words:

Step 5 – Compression (80 rounds in 4 stages of 20). Set $a,b,c,d,e = H_0..H_4$. For $t=0..79$:

where the round function and constant change each 20-round stage:

Step 6 – Update chaining values (mod $2^{32}$):

Process all blocks; the final 160-bit digest is the concatenation $H_0\Vert H_1\Vert H_2\Vert H_3\Vert H_4$.

SHA-1 is now considered broken for collision resistance (the 2017 SHAttered attack) and is deprecated in favour of SHA-2/SHA-3.

Classical Encryption Techniques

Classical ciphers are symmetric and fall into two families:

• Substitution – replace plaintext units with other symbols (Caesar, Playfair, Hill, Vigenère).
• Transposition – rearrange the positions of plaintext characters (rail fence, columnar).

Playfair Cipher

A digraph substitution cipher using a $5\times5$ key matrix (I/J share a cell).

Key = MONARCHY, fill remaining letters of alphabet:

M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z

Rules (process plaintext as pairs; insert X between repeats, pad with X):

1. Same row → take letter to the right (wrap).
2. Same column → take letter below (wrap).
3. Otherwise (rectangle) → take the letter in the same row but the other pair's column.

Example: plaintext BALLOON → BA LX LO ON

• BA → IB
• LX → SU
• LO → PM (rectangle)
• ON → NA

Ciphertext = IBSUPMNA.

Hill Cipher

A polygraphic cipher using linear algebra mod 26. For block size $n$, choose an invertible key matrix $K$ ($\gcd(\det K,26)=1$). Encryption:

Example ($n=2$): Let $K=\begin{pmatrix}3 & 3\\ 2 & 5\end{pmatrix}$, plaintext HI $\to P=\begin{pmatrix}7\\8\end{pmatrix}$.

Ciphertext = letters 19,2 = TC.

Decryption uses $K^{-1}$, computed via $K^{-1}=(\det K)^{-1}\,\mathrm{adj}(K)\bmod 26$. Here $\det K=15-6=9$, $9^{-1}\bmod 26=3$, giving $K^{-1}=\begin{pmatrix}15&17\\20&9\end{pmatrix}$, which recovers HI.

Digital Signature

A digital signature is a cryptographic value, computed from a message and the signer's private key, that lets anyone verify the message's origin and integrity using the signer's public key. It is the digital analogue of a handwritten signature but also binds to the message content.

Properties provided:

• Authentication – verifier is assured of the signer's identity.
• Integrity – any change to the message invalidates the signature.
• Non-repudiation – the signer cannot later deny signing, since only they hold the private key.

RSA Digital Signature Scheme

Key generation: choose primes $p,q$; $n=pq$; $\phi(n)=(p-1)(q-1)$; pick $e$ with $\gcd(e,\phi)=1$; compute $d=e^{-1}\bmod\phi(n)$. Public key $(e,n)$, private key $(d,n)$.

Signing (signer uses private key on the hash of the message):

The signer sends $(M, S)$.

Verification (verifier uses signer's public key):

Because $(h^d)^e \equiv h \pmod n$, a valid signature recovers the hash. Signing the hash rather than $M$ keeps signatures short and avoids existential forgery on raw RSA.

Tiny example: $p=5,q=11,n=55,\phi=40$; $e=3$, $d=27$ (since $3\cdot27=81\equiv1\bmod40$). If $H(M)=4$: $S=4^{27}\bmod55=9$. Verify: $9^{3}\bmod55=4=H(M)$ ✓.

Role in Authentication and Non-repudiation

• Authentication: only the holder of the private key could have produced $S$ that verifies under the matching public key, proving identity.
• Non-repudiation: the binding between signer and message is verifiable by any third party, so the signer cannot deny authorship — essential for contracts, e-commerce and certificates. (Trust in the public key itself is established through a PKI / Certificate Authority.)

Fermat's Little Theorem

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=104\cdot7+1\equiv 1\pmod 7$. ✓

Euler's Theorem

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

where $\phi(n)$ is Euler's totient (count of integers in $[1,n]$ coprime to $n$). It generalises Fermat's theorem (for prime $p$, $\phi(p)=p-1$).

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

Relevance: these theorems underpin RSA — the decryption exponent works because $m^{ed}=m^{1+k\phi(n)}\equiv m\pmod n$ — and enable fast modular exponentiation.

Yes — Diffie–Hellman is vulnerable to a Man-in-the-Middle (MITM) attack.

Plain Diffie–Hellman exchanges public values but provides no authentication of the parties, so an active attacker can sit between Alice and Bob.

The attack: Alice and Bob agree on prime $p$ and generator $g$.

• Alice sends $A=g^{a}\bmod p$; attacker Mallory intercepts it and instead sends Bob $M=g^{m}\bmod p$.
• Bob sends $B=g^{b}\bmod p$; Mallory intercepts and sends Alice $M$.
• Alice computes shared key $K_1=M^{a}=g^{am}\bmod p$.
• Bob computes shared key $K_2=M^{b}=g^{bm}\bmod p$.

Now Mallory shares $K_1$ with Alice and $K_2$ with Bob, can decrypt, read/modify, and re-encrypt all traffic — neither party detects it.

Why: DH guarantees secrecy of the discrete log but does not bind a public value to an identity.

Countermeasure: authenticated Diffie–Hellman — sign the exchanged values (e.g., station-to-station protocol), use certificates/PKI, or combine DH with pre-shared keys, so each side verifies the peer's identity.

SHA-2 Family

SHA-2 is a family of cryptographic hash functions standardised by NIST (FIPS 180-4), built on the Merkle–Damgård structure with two core compression functions (32-bit word for shorter, 64-bit word for longer variants):

SHA-224 is a truncated SHA-256 with different IVs; SHA-384 and SHA-512/t are truncated SHA-512.

Differences from SHA-1

Summary: SHA-2 offers longer digests, more chaining variables, a stronger message schedule and per-round constants, giving far greater collision resistance than SHA-1.

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 keys. It solves the key-distribution / trust problem of asymmetric cryptography by reliably binding a public key to a verified identity.

Main components:

• Certificate Authority (CA) – trusted third party that issues and signs certificates.
• Registration Authority (RA) – verifies identity before the CA issues a certificate.
• Certificate Repository / Directory – stores and publishes certificates.
• CRL / OCSP – mechanisms to check revoked certificates.

Role of the Certificate Authority

The CA is the root of trust. It:

1. Verifies the applicant's identity (via the RA).
2. Binds the subject's identity to their public key and digitally signs the certificate with the CA's private key.
3. Publishes and renews certificates, and revokes compromised ones (publishing a CRL).

Anyone holding the CA's public key can verify the CA's signature and thus trust the certified public key.

Digital Certificates

A digital certificate (typically X.509) is a signed data structure binding a public key to an identity. Key fields:

• Version, serial number
• Subject name and subject public key
• Issuer (CA) name
• Validity period (not-before / not-after)
• Signature algorithm and the CA's digital signature

When a user presents a certificate, the verifier checks the CA's signature, the validity dates and revocation status before trusting the enclosed public key (used in TLS/HTTPS, S/MIME, code signing).

Malicious Code

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

Virus

A program fragment that attaches itself to a host program or file and replicates when that host is executed. It needs a host and usually user action (running the infected file) to spread. Phases: dormant → propagation → triggering → execution (payload). Example: boot-sector and macro viruses.

Worm

A standalone, self-replicating program that spreads automatically across networks by exploiting vulnerabilities, without needing a host file or user action. It consumes bandwidth/resources and propagates very fast. Example: the Morris worm, Code Red.

Trojan Horse

A program that appears legitimate/useful but hides a malicious payload. It does not self-replicate; it relies on tricking the user into installing it, then performs hidden actions such as opening a backdoor, stealing data or installing other malware.

Key Differences

Chinese Remainder Theorem (CRT)

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

has a unique solution modulo $M$, given by

Worked Example

Solve:

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

Check: $23\bmod3=2$ ✓, $23\bmod5=3$ ✓, $23\bmod7=2$ ✓. So $x=23$ (CRT speeds up RSA decryption via mod $p$ and mod $q$).

Goals of Security (the CIA Triad)

• Confidentiality – ensuring information is accessible only to authorised parties; prevents unauthorised disclosure. Achieved by encryption and access control.
• Integrity – ensuring data is not altered in an unauthorised or undetected way; messages received are exactly as sent. Achieved by hashes, MACs and digital signatures.
• Availability – ensuring authorised users can access systems and data when needed; resisting denial of service. Achieved by redundancy, backups and DoS protection.

(Often extended with Authentication and Non-repudiation.)

Types of Security Attacks

Passive attacks (observe, do not alter — hard to detect, prevent via encryption):

• Release of message contents (eavesdropping)
• Traffic analysis

Active attacks (alter data or affect operation — easier to detect, hard to prevent):

• Masquerade – one entity pretends to be another
• Replay – capturing and retransmitting data
• Modification of messages – altering message contents
• Denial of Service (DoS) – preventing legitimate use of resources

A further classification by Stallings: interruption (availability), interception (confidentiality), modification (integrity), and fabrication (authenticity).

Symmetric vs Asymmetric Key Cryptography

Symmetric (secret-key): a single shared key is used for both encryption and decryption.

Asymmetric (public-key): a mathematically related key pair — encrypt with the recipient's public key, decrypt with their private key (or sign with private, verify with public).

Note: practical systems are hybrid — asymmetric crypto exchanges a symmetric session key, which then encrypts the bulk data (e.g., TLS).

Caesar Cipher

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

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

Cryptanalysis: only 25 possible keys, so a brute-force attack trying every shift instantly breaks it. The key can also be found by recognising frequency patterns (e.g., the most common ciphertext letter likely maps to E).

Mono-alphabetic Substitution Cipher

Each plaintext letter maps to a fixed but arbitrary ciphertext letter (a permutation of the alphabet), giving a key space of $26! \approx 4\times10^{26}$, so brute force is infeasible.

Cryptanalysis: broken by frequency analysis, because the substitution preserves letter statistics:

1. Count ciphertext letter frequencies and compare to English (E≈12.7%, T, A, O, I, N …).
2. Map the most frequent ciphertext letters to common plaintext letters.
3. Use digram/trigram patterns (TH, HE, THE, ING) and word structure to refine and confirm the key.

Conclusion: both ciphers fail because they hide letter identity but not letter frequency; only the key space differs (25 vs $26!$), yet both succumb to statistical cryptanalysis.