Cryptography & Information Security (CS-703 (A)) Notes

How unit 1 is examined

Covers modular arithmetic and number-theory tools (inverse, Fermat, Euler), classical ciphers (Caesar, Playfair, frequency analysis), and block and stream ciphers (DES, modes, RC4). Marks sit in Block Cipher, DES, Modes, Fermat, cryptanalysis, and the numericals (inverse, Playfair, primitive roots).

Mathematical Background for Cryptography: Abstract Algebra

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Abstract algebra studies sets with operations; a group is a set $G$ with one operation that is closed, associative, has an identity and gives every element an inverse.

Key points.

An abelian group is a group whose operation is also commutative, for example the integers under addition.
A ring has two operations (addition and multiplication) and is an abelian group under addition; $\mathbb{Z}_n$ is a ring.
A field is a ring in which every non-zero element has a multiplicative inverse; $\mathbb{Z}_p$ with $p$ prime is a finite field, written $GF(p)$.
AES works in $GF(2^8)$ and RSA works in $\mathbb{Z}_n^*$.

Number Theory

Definition. Modular arithmetic writes $a \equiv b \pmod n$ when $n$ divides $a-b$, and $a \bmod n$ is the remainder of $a$ on division by $n$ (from 0 to $n-1$).

Key points.

Addition and multiplication respect congruence, so $(a+b) \bmod n = ((a \bmod n)+(b \bmod n)) \bmod n$, and the same holds for products; for example $7+5 \equiv 0 \pmod{12}$ and $7\cdot 5=35\equiv 11 \pmod{12}$.
Two numbers are coprime when $\gcd(a,n)=1$, and only then does $a$ have an inverse mod $n$.
For prime $p$, $g$ is a primitive root if its powers $g^1,\dots,g^{p-1}$ mod $p$ give every value $1,\dots,p-1$, that is, its order is $p-1$.

Example (Jun 2025). $85 \bmod 120 = 85$ and $89 \bmod 119 = 89$, since each number is smaller than its modulus. If the paper meant powers, $8^5 \bmod 120 = 8$ and $8^9 \bmod 119 = 8$. Mod 7 ($p-1=6$): $3$ has powers $3,2,6,4,5,1$, all six values, so $3$ is a root; $2$ gives $2,4,1$ (order 3), so it fails. Mod 13 ($p-1=12$): $2$ has powers $2,4,8,3,6,12,11,9,5,10,7,1$, all twelve, so $2$ is a root; $3$ fails since $3^3=27\equiv1$.

Answer. Primitive roots of 7 are $\{3,5\}$; primitive roots of 13 are $\{2,6,7,11\}$.

Asked: [7 marks] (Jun 2025) Find i) 85 mod 120, ii) 89 mod 119, iii) primitive root of 13, iv) primitive root of 7.

Modular Inverse

Definition. The multiplicative inverse of $a$ mod $m$ is the number $x$ with $a x \equiv 1 \pmod m$; it exists only if $\gcd(a,m)=1$.

Key points.

The inverse is found by the Extended Euclidean Algorithm, which writes $\gcd(a,m)=1=sa+tm$, so $s \bmod m$ is the inverse.
It is unique modulo $m$.
RSA uses it to get the private key $d = e^{-1} \bmod \phi(n)$, and the Hill and affine ciphers use it to decrypt.

Example. Inverse of $11 \bmod 26$. $26 = 2\cdot 11 + 4$; $11 = 2\cdot 4 + 3$; $4 = 1\cdot 3 + 1$. So $\gcd=1$. Back-substitute: $1 = 4-3 = 4-(11-2\cdot4) = 3\cdot4-11 = 3(26-2\cdot11)-11 = 3\cdot 26 - 7\cdot 11$. So $-7\cdot 11 \equiv 1 \pmod{26}$ and $x=-7+26=19$. Verify: $11\cdot19=209=8\cdot26+1\equiv 1 \pmod{26}$. Inverse = 19.

Asked: [7 marks] (Dec 2025) Find the multiplicative inverse of 11 mod 26 using the Extended Euclidean Algorithm and verify.

Extended Euclid Algorithm

Definition. Euclid's algorithm finds $\gcd(a,b)$ by repeated division, and the extended version also finds integers $s,t$ with $sa+tb=\gcd(a,b)$ (Bezout's identity).

Key points.

Euclid uses $\gcd(a,b)=\gcd(b, a \bmod b)$ until the remainder is 0; the last non-zero remainder is the gcd.
Extended Euclid back-substitutes from the last equation to get $s,t$.
When the gcd is 1, $s$ is the inverse of $a$ mod $b$, as in $11^{-1} \bmod 26 = 19$.

Fermat's Little Theorem

Definition. <mark>If $p$ is prime and $a$ is not divisible by $p$, then $a^{p-1} \equiv 1 \pmod p$.</mark>

Key points.

The alternate form $a^p \equiv a \pmod p$ holds for every integer $a$, including multiples of $p$.
Proof idea: the numbers $a, 2a, \dots, (p-1)a$ mod $p$ are a rearrangement of $1,2,\dots,p-1$, because $a$ is invertible mod $p$; multiplying both lists gives $a^{p-1}(p-1)! \equiv (p-1)!$, and cancelling $(p-1)!$ (coprime to $p$) leaves $a^{p-1}\equiv 1$.
It gives fast modular powers and inverses, since $a^{-1} \equiv a^{p-2} \pmod p$.
It is the basis of primality tests: if $a^{n-1} \not\equiv 1 \pmod n$ then $n$ is composite.
It is the special case of Euler's theorem with $n=p$, where $\phi(p)=p-1$.

Example. $p=11$, $a=2$: $2^{10}=1024=93\cdot11+1$, so $2^{10}\equiv1 \pmod{11}$. Also $p=7$, $a=2$: $2^6=64=9\cdot7+1\equiv1 \pmod 7$. Using it, $2^{100} = (2^{10})^{10}\equiv 1 \pmod{11}$.

Answer frame. Open with the statement and the condition $\gcd(a,p)=1$; give the alternate form; sketch the rearrangement proof in 3 lines; work $2^{10} \bmod 11$; close with use in primality testing and RSA.

Pitfall: Forgetting that $a$ must not be a multiple of $p$ for the $a^{p-1}$ form, and that $p$ must be prime.

Asked: [7 marks] (Dec 2020, Nov 2023) Explain / describe Fermat's little theorem with an example.

Euler Phi-Function

Definition. $\phi(n)$ is the number of integers from 1 to $n$ that are coprime to $n$.

Key points.

For prime $p$, $\phi(p)=p-1$, and $\phi(p^k)=p^k-p^{k-1}$.
It is multiplicative for coprime numbers: $\phi(pq)=(p-1)(q-1)$ for distinct primes $p,q$, which is the RSA modulus formula.
Example: $\phi(10)=4$, counting $1,3,7,9$; $\phi(21)=2\cdot6=12$.

Euler's theorem

Definition. ==If $\gcd(a,n)=1$, then $a^{\phi(n)} \equiv 1 \pmod n$.==

Derivation.

Let $R=\{r_1,\dots,r_{\phi(n)}\}$ be the residues coprime to $n$.
Multiply each by $a$ (coprime to $n$): $aR=\{ar_1 \bmod n,\dots\}$ contains only residues coprime to $n$, and they are all distinct, because $ar_i\equiv ar_j$ would give $r_i\equiv r_j$ (as $a$ is invertible). So $aR$ is a rearrangement of $R$.
Multiply all elements: $a^{\phi(n)}\prod r_i \equiv \prod r_i \pmod n$.
$\prod r_i$ is coprime to $n$, so cancel it: $a^{\phi(n)}\equiv 1 \pmod n$.

Key points.

Check: $n=10$, $a=3$, $\phi(10)=4$, $3^4=81\equiv1 \pmod{10}$.
Significance: RSA works because $M^{ed}\equiv M \pmod n$ when $ed\equiv 1 \pmod{\phi(n)}$, and it also gives inverses $a^{-1}\equiv a^{\phi(n)-1} \pmod n$.

Answer frame. Define congruence and give the two examples; state the theorem; derive in the four steps above; close with RSA and inverses.

Asked: [7 marks] (Dec 2025) Explain modular arithmetic with examples. Derive Euler's theorem and state its significance in cryptography.

Introduction to Cryptography: Principles of Cryptography

Definition. Cryptography is the science of securing information by transforming plaintext into unreadable ciphertext using a key.

Key points.

Confidentiality keeps data secret from unauthorised readers, and integrity detects any change to it.
Authentication proves who sent the data, and non-repudiation stops the sender denying it later.
Kerckhoffs' principle says security must rest on the secrecy of the key only, never on the secrecy of the algorithm.

Classical Cryptosystem

Definition. Classical ciphers are pre-computer ciphers that work on letters by substitution (replace letters) or transposition (rearrange them).

Key points.

Caesar cipher shifts every letter by $k$: $C=(P+k) \bmod 26$ and $P=(C-k) \bmod 26$; with $k=3$, HELLO becomes KHOOR.
Caesar has only 25 keys, so brute force breaks it at once; Playfair encrypts digraphs with a 5x5 key square and has $25!$ keys.
Playfair hides single-letter frequencies, but digraph frequencies remain.

Feature	Caesar	Playfair
Type	Monoalphabetic substitution	Digraph (polygraphic) substitution
Unit encrypted	One letter	Pair of letters
Key	Shift $k$ (1-25)	Keyword building a 5x5 matrix
Key space	25	About $25!$
Frequency analysis	Breaks it easily	Harder; needs digraph statistics
Security	Very weak	Weak but stronger than Caesar

Frequency analysis example: in WKLV LV D VHFUHW the most frequent letter is V (3 times) and the one-letter word D suggests A; shift 3 gives THIS IS A SECRET.

Asked: [7 marks] (Dec 2025) Compare Caesar and Playfair cipher. Perform frequency analysis on a simple ciphertext example.

Cryptanalysis on Substitution Cipher (Frequency Analysis)

Definition. <mark>Cryptanalysis is the study of breaking ciphers to recover plaintext or the key without knowing the key.</mark> A substitution cipher replaces each plaintext letter with another symbol by a fixed mapping.

Key points.

The goal of cryptanalysis is to recover the plaintext or, better, the key, which exposes all messages.
Ciphertext-only attack: the attacker has only ciphertext. Known-plaintext: some plaintext-ciphertext pairs are known. Chosen-plaintext: the attacker gets chosen plaintexts encrypted. Chosen-ciphertext: the attacker gets chosen ciphertexts decrypted.
A brute-force attack tries every key until readable plaintext appears; effort is up to $2^k$ trials for a $k$-bit key (on average half), so a large key space defeats it.
A monoalphabetic substitution has $26!\approx 4\times10^{26}$ keys, too many for brute force, but it keeps the language's letter statistics.
In English, E (about 12.7%), T, A, O, I, N are the most common letters, and TH, HE, IN are the common digraphs; THE is the common trigram.

Steps (frequency analysis).

Step 1: Count how often each ciphertext letter occurs.
Step 2: Match the most frequent ciphertext letter to E, the next to T, A, O and so on.
Step 3: Use digraphs, trigrams and one-letter words (A, I) to confirm or correct.
Step 4: Fill in the remaining letters from word patterns until the text reads sensibly.

Answer frame. Open with definition of cryptanalysis and its goal; list the four attack types; define brute force with key-size effort; define substitution cipher; give the four steps and the example; close with countermeasures (large keys, polyalphabetic and modern ciphers).

Asked: [7 marks] (Dec 2020, Nov 2022) Explain the concept of cryptanalysis and brute force attack. Asked: [7 marks] (Nov 2023) Define cryptanalysis. Explain the concept of cryptanalysis on substitution cipher.

Play Fair Cipher

Definition. Playfair encrypts a plaintext in digraphs (letter pairs) using a 5x5 matrix built from a keyword, with I and J sharing one cell.

Rules.

Split plaintext into pairs; a pair of equal letters gets X inserted between, and an odd last letter gets X appended.
Same row: take the letter to the right of each (wrapping around).
Same column: take the letter below each (wrapping around).
Otherwise (rectangle): each letter is replaced by the one in its own row and the other letter's column.

Example (Jun 2025). Keyword MONARCHY, matrix:

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

Plaintext SWARAJ IS MY BIRTH RIGHT (J as I) gives digraphs SW AR AI IS MY BI RT HR IG HT, with no repeats needing X.

Pair	Case	Cipher
SW	rectangle	QX
AR	same row	RM
AI	same column	BS
IS	same row	SX
MY	rectangle	NC
BI	same column	IS
RT	same column	DZ
HR	rectangle	DO
IG	same row	KI
HT	rectangle	DP

Ciphertext = QX RM BS SX NC IS DZ DO KI DP.

Asked: [7 marks] (Jun 2025) Encrypt "SWARAJ IS MY BIRTH RIGHT" using Playfair with keyword MONARCHY, X for blank spaces.

Block Cipher

Definition. <mark>A block cipher encrypts a fixed-size block of plaintext (for example 64 or 128 bits) at a time, under one key, into a ciphertext block of the same size.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-01" viewBox="0 0 424 166" width="424" height="166" role="img" aria-label="Block cipher: an n-bit plaintext block P and key K give an n-bit ciphertext block C"><style>#dsfig-u1-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-01 .t{fill:#16181D;font-weight:500}#dsfig-u1-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-01 .dot{fill:#16181D}#dsfig-u1-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-01 .ah{fill:#454C5A}#dsfig-u1-01 .ah.hi{fill:#2340B8}#dsfig-u1-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-01 .e{stroke:#B1B7C3}html.dark #dsfig-u1-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-01 .t{fill:#E6E8ED}html.dark #dsfig-u1-01 .t.inv{fill:#0F1115}html.dark #dsfig-u1-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-01 .dot{fill:#E6E8ED}html.dark #dsfig-u1-01 .ann{fill:#8FA3FF}html.dark #dsfig-u1-01 .lbl{fill:#858D9C}html.dark #dsfig-u1-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-01 .ah{fill:#B1B7C3}html.dark #dsfig-u1-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh1" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,126 L191,126" marker-end="url(#ah1)"/><path class="e" d="M212,59 L212,105" marker-end="url(#ah1)"/><path class="e" d="M231,126 L363,126" marker-end="url(#ah1)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">P</text><circle class="n" cx="212" cy="126" r="18"/><text class="t" x="212" y="126" dy=".35em" text-anchor="middle">Enc</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">K</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Block cipher: an n-bit plaintext block P and key K give an n-bit ciphertext block C</figcaption></figure>

Key points.

A block cipher is a keyed permutation: for each key, encryption maps every $n$-bit block to a unique $n$-bit block, so decryption is possible.
Shannon's principles are confusion (the key-ciphertext relation is complex, through substitution) and diffusion (each plaintext bit affects many ciphertext bits, through permutation).
Most block ciphers are Feistel networks of repeated rounds, each round splitting the block into $L$ and $R$, with $L_i=R_{i-1}$ and $R_i=L_{i-1}\oplus F(R_{i-1},K_i)$.
Examples are DES (64-bit block, 56-bit key), 3DES and AES (128-bit block, 128/192/256-bit key).
Messages longer than one block need a mode of operation, and a short last block needs padding.
Applications are file and disk encryption, TLS and IPsec channels, and MAC and hash building blocks.
Advantages are strong diffusion and reuse across modes; limitations are padding and error propagation in some modes.

Answer frame. Open with the definition; draw the box; develop points 1-5, then applications; close with advantages and limitations.

Asked: [14 marks] (Nov 2023) Write short notes on any two: Block Cipher, Hash Function, Transport Layer Security, Foot Printing Tools.

Data Encryption Standard (DES)

Definition. <mark>DES is a symmetric Feistel block cipher that encrypts a 64-bit block with a 56-bit key in 16 rounds, using a different 48-bit subkey in each round.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-02" viewBox="0 0 596 252" width="596" height="252" role="img" aria-label="DES: IP, 16 Feistel rounds, 32-bit swap, FP; the key schedule PC-1, shifts, PC-2 feeds each round"><style>#dsfig-u1-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-02 .t{fill:#16181D;font-weight:500}#dsfig-u1-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-02 .dot{fill:#16181D}#dsfig-u1-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-02 .ah{fill:#454C5A}#dsfig-u1-02 .ah.hi{fill:#2340B8}#dsfig-u1-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-02 .e{stroke:#B1B7C3}html.dark #dsfig-u1-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-02 .t{fill:#E6E8ED}html.dark #dsfig-u1-02 .t.inv{fill:#0F1115}html.dark #dsfig-u1-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-02 .dot{fill:#E6E8ED}html.dark #dsfig-u1-02 .ann{fill:#8FA3FF}html.dark #dsfig-u1-02 .lbl{fill:#858D9C}html.dark #dsfig-u1-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-02 .ah{fill:#B1B7C3}html.dark #dsfig-u1-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L105,40" marker-end="url(#ah2)"/><path class="e" d="M145,40 L191,40" marker-end="url(#ah2)"/><path class="e" d="M231,40 L277,40" marker-end="url(#ah2)"/><path class="e" d="M317,40 L363,40" marker-end="url(#ah2)"/><path class="e" d="M403,40 L449,40" marker-end="url(#ah2)"/><path class="e" d="M489,40 L535,40" marker-end="url(#ah2)"/><path class="e" d="M59,212 L148,212" marker-end="url(#ah2)"/><path class="e" d="M188,212 L277,212" marker-end="url(#ah2)"/><path class="e" d="M317,212 L406,212" marker-end="url(#ah2)"/><path class="e" d="M289.5,195 L221.4,58.8" marker-end="url(#ah2)"/><path class="e" d="M422.4,193.6 L389.1,60.4" marker-end="url(#ah2)"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">PT</text><circle class="n" cx="126" cy="40" r="18"/><text class="t" x="126" y="40" dy=".35em" text-anchor="middle">IP</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">R1</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">Rn</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">R16</text><circle class="n" cx="470" cy="40" r="18"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">SW</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">FP</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">PC1</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">SH</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">PC2</text><circle class="n" cx="427" cy="212" r="18"/><text class="t" x="427" y="212" dy=".35em" text-anchor="middle">K16</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">DES: IP, 16 Feistel rounds, 32-bit swap, FP; the key schedule PC-1, shifts, PC-2 feeds each round</figcaption></figure> <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-03" viewBox="0 0 510 166" width="510" height="166" role="img" aria-label="F-function: R (32 bits) expanded to 48, XOR Ki, 8 S-boxes give 32 bits, P-box permutes; then XOR with L"><style>#dsfig-u1-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-03 .t{fill:#16181D;font-weight:500}#dsfig-u1-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-03 .dot{fill:#16181D}#dsfig-u1-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-03 .ah{fill:#454C5A}#dsfig-u1-03 .ah.hi{fill:#2340B8}#dsfig-u1-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-03 .e{stroke:#B1B7C3}html.dark #dsfig-u1-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-03 .t{fill:#E6E8ED}html.dark #dsfig-u1-03 .t.inv{fill:#0F1115}html.dark #dsfig-u1-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-03 .dot{fill:#E6E8ED}html.dark #dsfig-u1-03 .ann{fill:#8FA3FF}html.dark #dsfig-u1-03 .lbl{fill:#858D9C}html.dark #dsfig-u1-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-03 .ah{fill:#B1B7C3}html.dark #dsfig-u1-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,126 L105,126" marker-end="url(#ah3)"/><path class="e" d="M145,126 L191,126" marker-end="url(#ah3)"/><path class="e" d="M212,59 L212,105" marker-end="url(#ah3)"/><path class="e" d="M231,126 L277,126" marker-end="url(#ah3)"/><path class="e" d="M317,126 L363,126" marker-end="url(#ah3)"/><path class="e" d="M403,126 L449,126" marker-end="url(#ah3)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="126" cy="126" r="18"/><text class="t" x="126" y="126" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="212" cy="126" r="18"/><text class="t" x="212" y="126" dy=".35em" text-anchor="middle">X</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">SB</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">P</text><circle class="n" cx="470" cy="126" r="18"/><text class="t" x="470" y="126" dy=".35em" text-anchor="middle">Out</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">Ki</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">F-function: R (32 bits) expanded to 48, XOR Ki, 8 S-boxes give 32 bits, P-box permutes; then XOR with L</figcaption></figure>

Key points (encryption).

The 64-bit plaintext goes through the Initial Permutation (IP) and is split into 32-bit halves $L_0$ and $R_0$.
Each of 16 rounds computes $L_i=R_{i-1}$ and $R_i=L_{i-1}\oplus F(R_{i-1},K_i)$.
The F-function expands $R$ from 32 to 48 bits (E-box), XORs it with the 48-bit $K_i$, passes it through eight S-boxes (6 bits in, 4 bits out) and permutes the 32-bit result with the P-box.
After round 16 the halves are swapped and the Final Permutation ($IP^{-1}$) gives the ciphertext.
Decryption uses the same circuit with subkeys in reverse order $K_{16},\dots,K_1$.

Key generation (steps).

Step 1: The 64-bit key has 8 parity bits; PC-1 drops them and permutes to 56 bits.
Step 2: Split into two 28-bit halves C0 and D0.
Step 3: In round i rotate C and D left by 1 bit (rounds 1, 2, 9, 16) or 2 bits (all others).
Step 4: PC-2 compresses the 56 bits of C and D to a 48-bit subkey Ki.
Step 5: Repeat for 16 rounds to get K1 to K16.

S-box importance. The S-boxes are the only non-linear part of DES, so they give confusion; each maps 6 bits to 4 bits by a table (outer bits pick the row, middle four the column), which stops the cipher being solved as linear equations and resists differential and linear cryptanalysis.

Answer frame. Open with the definition; draw the structure diagram, then the F-function; describe encryption in points 1-4; give key generation and decryption; end with S-box importance and DES's weakness (56-bit key, brute forced, replaced by 3DES and AES).

Asked: [7 marks] (Nov 2022) Explain the steps for the key generation of DES. Asked: [7 marks] (Nov 2023, Jun 2025) Illustrate DES algorithm with neat diagram. Explain S-box importance in DES. Explain key generation, encryption and decryption of DES in detail.

Triple DES

Definition. Triple DES applies DES three times with two or three keys in encrypt-decrypt-encrypt order: $C=E_{K_3}(D_{K_2}(E_{K_1}(P)))$.

Key points.

It was made because the 56-bit DES key is too short and can be brute forced.
With $K_1=K_2=K_3$ it reduces to single DES, so it stays backward compatible.
Effective key strength is 112 bits (two keys) or 168 bits (three keys), since a meet-in-the-middle attack cuts double DES to about 57 bits.
It is three times slower than DES, so AES replaced it.

Modes of Operation

Definition. <mark>A mode of operation is a method for using a block cipher to encrypt messages longer than one block.</mark>

Key points.

The five modes are ECB, CBC, CFB, OFB and CTR.
ECB encrypts each block alone, $C_i=E_K(P_i)$: it is parallel but equal blocks give equal ciphertext, so it leaks patterns.
CBC: $C_i=E_K(P_i\oplus C_{i-1})$, $C_0=IV$; it hides patterns, an error in one ciphertext block garbles two plaintext blocks, and encryption is sequential.
CFB: $C_i=P_i\oplus \text{MSB}_s(E_K(\text{shift register}))$; the register is shifted left by $s$ bits and filled with $C_i$; it acts as a self-synchronising stream cipher, and errors spread for one block.
OFB: output is fed back, $O_i=E_K(O_{i-1})$, $O_0=IV$, $C_i=P_i\oplus O_i$; there is no error propagation, and the keystream is precomputable.
CTR: $C_i=P_i\oplus E_K(\text{counter}_i)$; it is parallel with no error propagation, and the counter never repeats.
In CFB, OFB and CTR decryption also uses only the encryption function.

CFB as a stream cipher. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u1-04" viewBox="0 0 596 166" width="596" height="166" role="img" aria-label="CFB encryption: shift register (start IV) is encrypted, s leftmost bits are XORed with s-bit plaintext to give ciphertext, which is fed back into the register"><style>#dsfig-u1-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u1-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u1-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u1-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u1-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u1-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u1-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u1-04 .t{fill:#16181D;font-weight:500}#dsfig-u1-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u1-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u1-04 .dot{fill:#16181D}#dsfig-u1-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u1-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u1-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u1-04 .ah{fill:#454C5A}#dsfig-u1-04 .ah.hi{fill:#2340B8}#dsfig-u1-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u1-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u1-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u1-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u1-04 .e{stroke:#B1B7C3}html.dark #dsfig-u1-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u1-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u1-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u1-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u1-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u1-04 .t{fill:#E6E8ED}html.dark #dsfig-u1-04 .t.inv{fill:#0F1115}html.dark #dsfig-u1-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u1-04 .dot{fill:#E6E8ED}html.dark #dsfig-u1-04 .ann{fill:#8FA3FF}html.dark #dsfig-u1-04 .lbl{fill:#858D9C}html.dark #dsfig-u1-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u1-04 .ah{fill:#B1B7C3}html.dark #dsfig-u1-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u1-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u1-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u1-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,126 L148,126" marker-end="url(#ah4)"/><path class="e" d="M188,126 L277,126" marker-end="url(#ah4)"/><path class="e" d="M317,126 L406,126" marker-end="url(#ah4)"/><path class="e" d="M427,59 L427,105" marker-end="url(#ah4)"/><path class="e" d="M446,126 L535,126" marker-end="url(#ah4)"/><path class="e" d="M537,126 L61,126" marker-end="url(#ah4)"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">SR</text><circle class="n" cx="169" cy="126" r="18"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">Enc</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">Sel</text><circle class="n" cx="427" cy="126" r="18"/><text class="t" x="427" y="126" dy=".35em" text-anchor="middle">X</text><circle class="n" cx="556" cy="126" r="18"/><text class="t" x="556" y="126" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="427" cy="40" r="18"/><text class="t" x="427" y="40" dy=".35em" text-anchor="middle">P</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">CFB encryption: shift register (start IV) is encrypted, s leftmost bits are XORed with s-bit plaintext to give ciphertext, which is fed back into the register</figcaption></figure> A block cipher makes a block, but CFB uses only $s$ bits ($s=1,8$) of its output as a keystream and XORs them with the plaintext, so data of any length is sent in $s$-bit units with no padding. Decryption uses the same encryption and XOR.

Answer frame. For the CFB question: define block versus stream cipher; draw the diagram; give the equation and the shift-register steps; note error effect. For the five modes: list all five, then explain CBC and CFB with equations, IV and error propagation; close with a use (CBC for files, CTR for fast disks and networks).

Pitfall: Reusing an IV or counter with the same key in CTR, OFB or CFB breaks security.

Asked: [7 marks] (Nov 2022) How do you convert a block cipher into a stream cipher using CFB mode? Explain. Asked: [7 marks] (Jun 2025) Give the five modes of operation of block cipher. Explain any two.

Stream Cipher

Definition. A stream cipher encrypts data one bit or byte at a time by XORing it with a pseudorandom keystream: $C_i=P_i\oplus K_i$.

Key points.

RC4 is a variable-key-length (1-256 byte) byte-oriented stream cipher with a 256-byte state array $S$.
Key Scheduling Algorithm (KSA) starts with $S[i]=i$ and permutes $S$ using the key.
Pseudo-Random Generation Algorithm (PRGA) then swaps elements and outputs one keystream byte per step.
Encryption and decryption are the same XOR.
Weaknesses: biased early keystream bytes and related-key attacks broke it in WEP; it was used in SSL/TLS and WEP and is now deprecated.

KSA: for i=0..N-1: S[i]=i; j=0
     for i=0..N-1: j=(j+S[i]+K[i mod keylen]) mod N; swap(S[i],S[j])
PRGA: i=j=0; repeat: i=(i+1) mod N; j=(j+S[i]) mod N; swap(S[i],S[j]);
      output S[(S[i]+S[j]) mod N]

Example. With $N=8$ (3-bit words), key $K=[1,2,3,6]$: KSA gives $S=[2,3,7,4,6,0,1,5]$. The first four keystream values are $5,1,0,1$; plaintext $[1,2,2,2]$ XOR keystream gives ciphertext $[4,3,2,3]$.

Asked: [7 marks] (Dec 2020) Explain RC4 cipher with the help of suitable example.

Last-minute revision

Congruence: $a\equiv b \pmod n$ means $n \mid (a-b)$; inverse exists iff $\gcd(a,n)=1$.
$11^{-1} \bmod 26=19$, since $11\cdot19=209\equiv1$.
Primitive roots: mod 7 are 3 and 5; mod 13 are 2, 6, 7 and 11.
Fermat: $a^{p-1}\equiv1 \pmod p$; $2^{10}\equiv1 \pmod{11}$.
Euler: $a^{\phi(n)}\equiv1 \pmod n$; $\phi(pq)=(p-1)(q-1)$.
Caesar has 25 keys; monoalphabetic substitution has $26!$ keys; English's top letter is E.
Playfair MONARCHY, SWARAJ IS MY BIRTH RIGHT gives QX RM BS SX NC IS DZ DO KI DP.
DES: 64-bit block, 56-bit key, 16 rounds, 48-bit subkeys, 8 S-boxes (6 to 4 bits).
DES key shifts: 1 bit in rounds 1, 2, 9, 16; 2 bits otherwise.
3DES: $C=E_{K3}(D_{K2}(E_{K1}(P)))$, 112 or 168-bit strength.
Modes: ECB, CBC, CFB, OFB, CTR; CBC $C_i=E_K(P_i\oplus C_{i-1})$.
RC4: KSA then PRGA, keystream XOR plaintext, used in WEP and SSL.

Memory hooks

Fermat is for prime $p$ ($p-1$); Euler is for any $n$ ($\phi(n)$).
Playfair rules: Row right, Column down, Rectangle swap corners.
DES numbers: 64 in, 56 key, 16 rounds, 48 subkey, 32 halves.
Modes: "Every Child Can Out-Code" for ECB, CBC, CFB, OFB, CTR.
RC4 order: Key first (KSA), then Produce (PRGA).

Coverage checklist

Mathematical Background for Cryptography: Abstract Algebra: no past question.
Number Theory: Jun 2025 mod values and primitive roots.
Modular Inverse: Dec 2025 inverse of 11 mod 26.
Extended Euclid Algorithm: no past question (used in the Dec 2025 inverse).
Fermat's Little Theorem: Dec 2020, Nov 2023 explain with example.
Euler Phi-Function: no past question (used in the Dec 2025 Euler derivation).
Euler's theorem: Dec 2025 modular arithmetic and derive Euler's theorem.
Introduction to Cryptography: Principles of Cryptography: no past question.
Classical Cryptosystem: Dec 2025 compare Caesar and Playfair, frequency analysis.
Cryptanalysis on Substitution Cipher (Frequency Analysis): Dec 2020, Nov 2022 cryptanalysis and brute force; Nov 2023 cryptanalysis on substitution cipher.
Play Fair Cipher: Jun 2025 MONARCHY encryption.
Block Cipher: Nov 2023 short notes.
Data Encryption Standard (DES): Nov 2022 key generation; Nov 2023, Jun 2025 DES diagram and S-box.
Triple DES: no past question.
Modes of Operation: Nov 2022 CFB; Jun 2025 five modes.
Stream Cipher: Dec 2020 RC4.

Account

Cryptography & Information Security (CS-703 (A)) - Unit 1 Short Notes

How unit 1 is examined

Mathematical Background for Cryptography: Abstract Algebra

Number Theory

Modular Inverse

Extended Euclid Algorithm

Fermat's Little Theorem

Euler Phi-Function

Euler's theorem

Introduction to Cryptography: Principles of Cryptography

Classical Cryptosystem

Cryptanalysis on Substitution Cipher (Frequency Analysis)

Play Fair Cipher

Block Cipher

Data Encryption Standard (DES)

Triple DES

Modes of Operation

Stream Cipher

Last-minute revision

Memory hooks

Coverage checklist