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

RSA Algorithm

RSA (Rivest–Shamir–Adleman) 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 distinct primes $p$ and $q$.
2. Compute the modulus $n = p \times q$.
3. Compute Euler's totient $\phi(n) = (p-1)(q-1)$.
4. Choose a public exponent $e$ such that $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$.
5. Compute the private exponent $d$ such that $d \equiv e^{-1} \pmod{\phi(n)}$, i.e. $d \cdot e \equiv 1 \pmod{\phi(n)}$.

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

Encryption and Decryption

For a plaintext message $M$ (with $0 \le M < n$):

Correctness follows from Euler's theorem: $M^{ed} \equiv M \pmod n$ since $ed \equiv 1 \pmod{\phi(n)}$.

Worked Example ($p=7,\ q=11,\ M=8$)

1. $n = p \times q = 7 \times 11 = 77$.
2. $\phi(n) = (7-1)(11-1) = 6 \times 10 = 60$.
3. Choose $e$ with $\gcd(e,60)=1$. Take $e = 13$ (since $\gcd(13,60)=1$).
4. Find $d = e^{-1} \bmod 60$. Solve $13d \equiv 1 \pmod{60}$. Testing, $13 \times 37 = 481 = 8\times60 + 1$, so $d = 37$.

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

Encryption of $M=8$:

Compute by repeated 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} \equiv 71 \cdot 15 \cdot 8 \pmod{77}$.

• $71 \times 15 = 1065 \equiv 1065 - 13\times77 = 1065 - 1001 = 64 \pmod{77}$
• $64 \times 8 = 512 \equiv 512 - 6\times77 = 512 - 462 = 50 \pmod{77}$

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

Note: with another common choice $e=7$, $d=43$ and $C = 8^7 \bmod 77 = 57$. Any valid $(e,d)$ pair is acceptable provided the computation is consistent.

Data Encryption Standard (DES)

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

Overall Structure (Block Diagram in words)

64-bit Plaintext
        |
  Initial Permutation (IP)
        |
   Split into L0 (32) | R0 (32)
        |
  Round 1  (uses subkey K1)
  Round 2  (uses subkey K2)
     ...
  Round 16 (uses subkey K16)
        |
  32-bit Swap (L16, R16 -> R16, L16)
        |
  Inverse Initial Permutation (IP^-1)
        |
64-bit Ciphertext

A separate key schedule takes the 64-bit key, applies Permuted Choice 1 (PC-1, drops parity to 56 bits), splits into two 28-bit halves, performs left circular shifts each round, and applies Permuted Choice 2 (PC-2) to produce a 48-bit subkey $K_i$ for each round.

A Single Round (Feistel structure)

Each round splits the 64-bit block into left and right halves $L_{i-1}, R_{i-1}$ (32 bits each) and computes:

Thus only the right half passes through the function $F$; the halves swap each round (the final round omits the swap via the 32-bit swap at the end).

The Function F (the heart of DES)

$F$ takes a 32-bit input $R_{i-1}$ and a 48-bit subkey $K_i$:

1. Expansion (E): The 32-bit $R_{i-1}$ is expanded to 48 bits by the expansion permutation (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-bit result is split into eight 6-bit groups; each is fed to one of eight S-boxes, each mapping 6 bits to 4 bits. The S-boxes provide the cipher's non-linearity (confusion) and are the only non-linear component. Output is $8 \times 4 = 32$ bits.
4. Permutation (P): The 32-bit S-box output is permuted by the P-box (diffusion).

The 32-bit result of $F$ is XORed with $L_{i-1}$ to form $R_i$.

Decryption

DES decryption uses the same algorithm with the subkeys applied in reverse order ($K_{16}$ first, $K_1$ last) — a key advantage of the Feistel structure.

DES is now considered insecure due to its short 56-bit key (brute-forceable); 3DES and AES are its successors.

Advanced Encryption Standard (AES)

AES is a symmetric block cipher (Rijndael) that encrypts 128-bit blocks using key sizes of 128, 192 or 256 bits, with 10, 12 or 14 rounds respectively. Unlike DES it is not a Feistel cipher; it is a substitution–permutation network operating on a $4\times4$ matrix of bytes called the state.

Overall Structure

Plaintext (128 bits) -> State (4x4 bytes)
  AddRoundKey (initial)
  Rounds 1..(Nr-1): SubBytes -> ShiftRows -> MixColumns -> AddRoundKey
  Final round Nr:   SubBytes -> ShiftRows -> AddRoundKey   (no MixColumns)
 -> Ciphertext (128 bits)

Round keys are derived from the cipher key by the key expansion (key schedule). Operations are performed in the finite field $GF(2^8)$ with the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$.

The Four Transformations

1. SubBytes (byte substitution – confusion) Each byte of the state is replaced using a fixed 16×16 lookup table, the S-box, which is the multiplicative inverse in $GF(2^8)$ followed by an affine transform. Example: byte 0x53 is replaced by 0xED from the S-box. This is the only non-linear step.

2. ShiftRows (permutation – diffusion across columns) Rows of the state are cyclically shifted left: row 0 by 0, row 1 by 1, row 2 by 2, row 3 by 3 bytes. Example: a row $[b_0, b_1, b_2, b_3]$ in row 1 becomes $[b_1, b_2, b_3, b_0]$.

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

Example: output byte $= (02 \cdot a_0) \oplus (03 \cdot a_1) \oplus a_2 \oplus a_3$, where multiplication is in $GF(2^8)$. (Skipped in the final round.)

4. AddRoundKey (key mixing) The 128-bit state is XORed byte-by-byte with the 128-bit round key derived from key expansion. Example: state byte 0x53 XOR round-key byte 0xA6 = 0xF5.

Decryption

Uses the inverse transformations (InvSubBytes, InvShiftRows, InvMixColumns) with round keys applied in reverse order. AES combines confusion (SubBytes) and diffusion (ShiftRows + MixColumns) and is the current global encryption standard.

Goals of Security (CIA Triad)

• Confidentiality: Ensures that information is accessible only to authorized parties and protected from disclosure to unauthorized users. Achieved mainly through encryption and access control.
• Integrity: Ensures that information is not altered, modified, or destroyed by unauthorized parties; data received is exactly what was sent. Achieved through hashing, MACs and digital signatures.
• Availability: Ensures that systems, services and data are accessible to authorized users whenever needed. Threatened by denial-of-service (DoS) attacks; protected by redundancy and backups.

Types of Security Attacks

Attacks are broadly classified as passive and active:

Passive attacks (eavesdropping, hard to detect):

• Release of message contents (interception/eavesdropping)
• Traffic analysis (studying patterns of communication)

Active attacks (modify the data stream, easier to detect but harder to prevent):

• Masquerade (one entity pretends to be another)
• Replay (capturing and retransmitting data)
• Modification of messages
• Denial of service (DoS)

These can also be described as interruption (availability), interception (confidentiality), modification (integrity) and fabrication (authenticity).

Symmetric vs Asymmetric Key Cryptography

Summary

• Symmetric cryptography is fast but suffers from the key-distribution problem.
• Asymmetric cryptography solves key distribution and enables digital signatures but is slow.
• In practice both are combined (hybrid cryptography): asymmetric crypto securely exchanges a symmetric session key, which then encrypts the bulk data (e.g. TLS/SSL).

Caesar Cipher

The Caesar cipher is a monoalphabetic substitution cipher that shifts each letter by a fixed amount $k$ (the key, classically $k=3$).

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

Cryptanalysis: Trivially broken by brute force — there are only 25 possible non-trivial keys, so an attacker tries all shifts until meaningful text appears.

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}$ possible keys — far too many for brute force.

Example: a key mapping A→Q, B→W, C→E, ... ; CAB → EQW.

Cryptanalysis: Although brute force is infeasible, it is easily broken by frequency analysis. Each plaintext letter always maps to the same ciphertext letter, so the statistical frequency of letters is preserved. In English, E is most frequent (~12.7%), followed by T, A, O. The attacker matches the most frequent ciphertext letters to common plaintext letters, and uses digraphs (TH, ER), common words and patterns to recover the rest of the mapping.

Conclusion

Both ciphers fail because they are monoalphabetic: the Caesar cipher to brute force, and the general substitution cipher to frequency analysis. Polyalphabetic ciphers (e.g. Vigenère) were developed to defeat frequency analysis.

Modular Arithmetic

Modular arithmetic deals with integers and a fixed modulus $n$: two integers $a$ and $b$ are congruent modulo $n$ if they leave the same remainder on division by $n$, written

The result of any operation is reduced to the set $\{0, 1, \dots, n-1\}$ ($\mathbb{Z}_n$). It is fundamental to cryptography (RSA, ElGamal, Diffie–Hellman) because operations are bounded and one-way functions (e.g. modular exponentiation) are easy to compute but hard to invert. Example: $17 \equiv 2 \pmod 5$, and $(7 + 9) \bmod 5 = 16 \bmod 5 = 1$.

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$).

Properties:

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

Compute $\phi(35)$

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

Compute $\phi(24)$

$24 = 2^3 \times 3$:

Alternatively $\phi(24) = 24\left(1-\tfrac12\right)\left(1-\tfrac13\right) = 24 \cdot \tfrac12 \cdot \tfrac23 = 8.$

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

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

Encryption (sender, to encrypt message $M$ where $M < p$)

1. Choose a random ephemeral key $k$ with $1 \le k \le p-2$, $\gcd(k, p-1)=1$.
2. Compute the two ciphertext components:

The ciphertext is the pair $(C_1, C_2)$.

Decryption (receiver, using private key $x$)

This works because $C_1^x = (g^k)^x = (g^x)^k = y^k$, so dividing $C_2$ by $y^k$ recovers $M$.

Example (small numbers)

Let $p=11$, $g=2$, private $x=3$ ⇒ $y = 2^3 \bmod 11 = 8$. To send $M=7$ with random $k=4$:

• $C_1 = 2^4 \bmod 11 = 16 \bmod 11 = 5$
• $C_2 = 7 \cdot 8^4 \bmod 11 = 7 \cdot 4096 \bmod 11 = 7 \cdot 4 = 28 \bmod 11 = 6$.

Decrypt: $C_1^x = 5^3 = 125 \equiv 4 \pmod{11}$, inverse of 4 mod 11 is 3, so $M = 6 \cdot 3 = 18 \equiv 7 \pmod{11}$. ✓

Notes

• A fresh random $k$ must be used for each message (reuse breaks security).
• The ciphertext is twice the size of the plaintext (message expansion).

Block Ciphers vs Stream Ciphers

Block ciphers are more common for stored/bulk data; stream ciphers suit continuous communication.

Modes of Operation of Block Ciphers

Modes let a block cipher encrypt messages longer than one block:

1. ECB (Electronic Codebook): Each block encrypted independently, $C_i = E_K(P_i)$. Simple but insecure — identical plaintext blocks give identical ciphertext, revealing patterns.
2. CBC (Cipher Block Chaining): Each plaintext block is XORed with the previous ciphertext block before encryption: $C_i = E_K(P_i \oplus C_{i-1})$, with $C_0 = IV$. Hides patterns; sequential.
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$. Errors do not propagate.
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; widely used.

A random/unique Initialization Vector (IV) is required for CBC, CFB, OFB and a nonce for CTR.

Message Authentication Code (MAC)

A MAC is a small fixed-size tag generated from a message and a shared secret key that provides data integrity and authentication of the message source. The sender computes $\text{MAC} = C_K(M)$ and appends it; the receiver recomputes it with the same key $K$ and accepts the message only if the values match.

• Provides: integrity (detects tampering) and authentication (only a holder of $K$ could produce a valid tag).
• Unlike a digital signature it uses a symmetric key, so it does not provide non-repudiation.
• A MAC differs from a plain hash because it depends on a secret key — an attacker cannot forge it without $K$.

HMAC (Hash-based MAC)

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

where:

• $K^+$ = key padded with zeros to the hash block size,
• $ipad$ = the byte 0x36 repeated, $opad$ = the byte 0x5C repeated,
• $\|$ denotes concatenation.

How it works (steps)

1. Pad/format the key $K$ to block length, producing $K^+$.
2. XOR $K^+$ with $ipad$ and prepend it to the message; hash → inner hash.
3. XOR $K^+$ with $opad$, prepend it to the inner hash; hash again → HMAC value.

The nested (two-pass) structure protects against length-extension attacks. HMAC is provably secure if the underlying hash is reasonably strong and is widely used in TLS, IPSec and API authentication.

Key Management and Key Distribution in Symmetric Cryptography

The Problem

In symmetric cryptography both parties share one secret key. The central challenge is distributing that key securely so an eavesdropper never obtains it. For $n$ users wanting pairwise communication, $\frac{n(n-1)}{2}$ keys are needed — this scales poorly.

Key Distribution Options

For parties A and B, a key can be delivered by:

1. A physically selects the key and hands it to B (manual/out-of-band).
2. A trusted third party selects and delivers it to both.
3. If A and B already share a key, one can encrypt and send a new (session) key.
4. Via a Key Distribution Center (KDC) that shares a long-term master key with each user.

KDC-based Distribution (typical approach)

• Each user shares a permanent master key with the KDC.
• When A wants to talk to B, A requests a session key from the KDC.
• The KDC generates a one-time session key and sends it to A (encrypted with A's master key) and to B (encrypted with B's master key, often forwarded by A as a ticket).
• A and B then use the session key for that session only, then discard it.
• Kerberos is a well-known KDC-based protocol.

Key Management Lifecycle

Key management covers the full lifecycle: generation (strong random keys), distribution/exchange (KDC or Diffie–Hellman), storage (protected, e.g. in HSMs), use, rotation/renewal, and revocation/destruction. Using session keys (short-lived) plus master keys (long-lived) limits exposure if a key is compromised.

Note

Asymmetric techniques such as Diffie–Hellman key exchange are often used to establish a symmetric key over an insecure channel without a pre-shared secret.

Fermat's Little Theorem

Statement: If $p$ is a prime and $a$ is an integer not divisible by $p$ (i.e. $\gcd(a,p)=1$), then

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

Use: primality testing (Fermat test), and computing modular inverses ($a^{-1} \equiv a^{p-2} \pmod p$).

Example: Let $a=3$, $p=7$. Then $3^{7-1} = 3^6 = 729$. Since $729 = 104 \times 7 + 1$, we get $3^6 \equiv 1 \pmod 7$. ✓

Euler's Theorem

Statement: Euler's theorem generalizes Fermat's to any modulus $n$. If $\gcd(a,n)=1$, then

where $\phi(n)$ is Euler's totient function. When $n=p$ is prime, $\phi(p)=p-1$ and this reduces exactly to Fermat's little theorem.

Use: It is the mathematical foundation of RSA decryption ($M^{ed} \equiv M \pmod n$ because $ed \equiv 1 \pmod{\phi(n)}$).

Example: Let $a=3$, $n=10$. Then $\phi(10) = \phi(2)\phi(5) = 1 \times 4 = 4$. So $3^{\phi(10)} = 3^4 = 81$. Since $81 = 8\times10 + 1$, $3^4 \equiv 1 \pmod{10}$. ✓

Relationship

Euler's theorem is the general case; Fermat's little theorem is the special case for a prime modulus.