Information Security · Unit 2
Cryptographic Foundations
Exam-focused notes for Cryptographic Foundations (Information Security, BIT303): what the TU syllabus asks and how it has actually been tested, with 6 solved past questions from this unit.
What this unit covers
- Number theory basics
- Euler totient function
- Extended Euclidean algorithm
- Primality testing algorithms
- Finite fields and polynomial operations
- Substitution and transposition ciphers
Substitution and transposition ciphers
Distinction between Substitution and Transposition Cipher, DES Sub-Key Generation, and Finite Fields
--- Feature Substitution Cipher Transposition Cipher --------- Basic Operation Replaces each plaintext character with another character Rearranges (permutes) the positions of plaintext characters Character Identity Characters change their identity Character...
Full solved answer →Finite fields and polynomial operations
Perform polynomial addition, subtraction and multiplication of $2x^2 + 4x + 2$ and $5x + 6$ over $GF(7)$. [5]
$$A(x) = 2x^2 + 4x + 2$$ $$B(x) = 5x + 6$$ Field: $GF(7)$, so all coefficients reduced $\bmod 7$. Coefficient vectors: - $A: [x^2, x^1, x^0] = [2, 4, 2]$ - $B: [x^2, x^1, x^0] = [0, 5, 6]$ Degree A B Sum mod 7 -------------------------- $x^2$ 2 0 2 2 $x^1$ ...
Full solved answer →Primality testing algorithms
Write Rabin Miller Algorithm for primality testing. Test whether 341 is prime or not using the algorithm. [5]
- Number to test: $n = 341$ - Witness base (standard choice): $a = 2$ --- If $n$ is an odd prime, write $n - 1 = 2^s \cdot d$ with $d$ odd. Then for any witness $a$ coprime to $n$, either: $$a^d \equiv 1 \pmod{n} \quad\text{OR}\quad a^{2^r d} \equiv -1 \pmo...
Full solved answer →Define Euler Totient function. Determine whether 37 is Composite or not using Miller Rabin Primality testing. [5]
--- The Euler Totient Function, denoted $\phi(n)$, is defined as the number of positive integers less than or equal to $n$ that are relatively prime (coprime) to $n$. $$\phi(n) = \{ k : 1 \le k \le n,\ \gcd(k, n) = 1 \}$$ Key properties: - If $p$ is prime: ...
Full solved answer →Euler totient function
Define Euler totient function with an example. Find the GCD of 12 and 32 using Extended Euclidean algorithm.[10]
- Euler totient function: define with an example - Numbers for GCD: $a = 12$, $b = 32$ - Method: Extended Euclidean Algorithm --- The Euler Totient Function $\phi(n)$ counts the number of positive integers from $1$ to $n$ that are relatively prime (coprime)...
Full solved answer →Extended Euclidean algorithm
Write an algorithm for Extended Euclidean Algorithm. Illustrate the algorithm for a=84 and b=320. [5]
- $a = 84$ - $b = 320$ - Goal: find $\gcd(a,b)$ and integers $x, y$ such that $ax + by = \gcd(a,b)$. --- The Extended Euclidean Algorithm computes $\gcd(a,b)$ along with coefficients $x, y$ satisfying: $$ax + by = \gcd(a,b)$$ The returned triple $(d, x, y)$...
Full solved answer →Make Unit 2 stick
Practice BIT303 with flashcards & quizzes