Cryptography · Unit 3 · 8 hrs
Asymmetric Ciphers
Exam-focused notes for Asymmetric Ciphers (Cryptography, CSC327): what the TU syllabus asks and how it has actually been tested, with 12 solved past questions from this unit.
What this unit covers
- Number Theory: Prime Numbers, Fermat’s Theorem, Euler’s Theorem, Primility Testing, Miller-Rabin Algorithm, Extended Euclidean Theorem, Discrete Logarithms
- Public Key Cryptosystems
- Applications of Public Key Cryptosystems
- Distribution of public key
- Distribution of secret key by using public key cryptography
- Diffie-Helman Key Exchange
- Man-in-the-Middle Attack
- RSA Algorithm
- Elgamal Cryptographic System
Man-in-the-Middle Attack
Illustrate the man in middle attack in Diffie-Hellman key exchange protocol. Assume the prime number be 19 and 10 as its primitive root. Select 5 as private key and 4 as random integer. Find the cipher text of M = 2 using Elgamal crypto system.[10]
- Prime number: $p = 19$ - Primitive root: $g = 10$ - Private key: $x = 5$ - Random integer: $k = 4$ - Message: $M = 2$ --- Public parameters: $p = 19$, $g = 10$. 1. Alice picks private $XA$, sends $YA = g^{XA} \bmod p$. 2. Bob picks private $XB$, sends $YB...
Full solved answer →Number Theory
State Fermat's theorem with example. What is the implication of discrete logarithm? [5]
Statement: If p is a prime number and a is a positive integer such that gcd(a, p) = 1 (i.e., a is not divisible by p), then: $$a^{p-1} \equiv 1 \pmod{p}$$ An alternative (and equally important) form of Fermat's theorem is: $$a^p \equiv a \pmod{p}$$ This hol...
Full solved answer →How Miller Rabin test is used for primality testing? Show whether the number 561 passes the test. [5]
- Number to test: $n = 561$ - Test base (chosen): $a = 2$ Miller-Rabin is a probabilistic primality test based on the fact that for a prime $n$, the only square roots of $1 \pmod n$ are $\pm 1$. Algorithm: 1. Write $n - 1 = 2^k \cdot m$ where $m$ is odd. 2....
Full solved answer →What is the condition of for two integers, x and y, to be relatively prime? Find whether 61 is prime or not using Miller-Rabin algorithm. [5]
- Number to test: $n = 61$ - Question asks: (a) condition for two integers $x, y$ to be relatively prime; (b) test primality of 61 using Miller-Rabin. - No specific witness $a$ is given, so we choose valid witnesses. Two integers $x$ and $y$ are relatively ...
Full solved answer →Find the value of $7^{2019} \mod 13$ using Fermat's Little theorem. Define Euler totient function with an example. [5]
- Expression to evaluate: $7^{2019} \bmod 13$ - Base $a = 7$, modulus $p = 13$ (prime), exponent $= 2019$ - Task: define Euler totient function with an example --- Fermat's Little Theorem: If $p$ is prime and $\gcd(a,p)=1$, then $$a^{p-1} \equiv 1 \pmod{p}$...
Full solved answer →What is the role of the prime number in the Euler totient Function? Find the GCD of 12 and 16 using the Euclidean algorithm. [5]
- Euler totient function context; find role of prime numbers. - Numbers for GCD: $a = 16$, $b = 12$. --- Euler's Totient Function $\phi(n)$ counts the number of positive integers in the range $1 \le k \le n$ that are relatively prime to $n$ (i.e. $\gcd(k, n...
Full solved answer →Diffie-Helman Key Exchange
Why do we need discrete logarithm? Illustrate with an example. Consider a Diffie-Hellman scheme with a common prime p = 13 between user A and user B. Suppose public key of A is 10 and public key of B is 8. Now determine their private keys and shared secret key. Select any valid primitive root of 13.[10]
- Common prime: $p = 13$ - Public key of A: $YA = 10$ - Public key of B: $YB = 8$ - Task: find private keys $XA, XB$ and shared secret $K$, using any valid primitive root of 13. --- Definition. Given a prime $p$, a primitive root $g$, and a value $y$, the d...
Full solved answer →How does meet in middle attack work in Diffie Helman key exchange protocol? Explain. [5]
In the Diffie-Hellman (DH) protocol, two parties (Alice and Bob) agree on public parameters: - A large prime q - A primitive root a of q Each party generates a private key and computes a public key, then exchanges public keys to derive a shared secret. --- ...
Full solved answer →Define discrete logarithm. Explain the procedure of sharing the secret key in Diffie Hellman. [5]
For a prime number P and a primitive root a, if: $$a^i \equiv b \pmod{P}$$ Then i is called the discrete logarithm of the number b for the base a mod P, and is denoted as: $$dloga(b) = i$$ The difficulty of computing the discrete logarithm (given b, a, and ...
Full solved answer →RSA Algorithm
Discrete Logarithms and RSA Cryptosystem
- Primes: $p = 13$, $q = 7$ - Plaintext: $M = \text{'hi'}$ - Encoding: $a=0, b=1, \ldots, z=25$ All required data is present. --- Given a prime $p$, a primitive root (generator) $g$, and a value $y$, the discrete logarithm is the integer $x$ such that: $$g^...
Full solved answer →Elgamal Cryptographic System
Show that Z 5 is a field. John publishes the ElGamal public key (q, α, YA) =(101, 2, 14). Jane desired to send the secret message CSIT to John. Using the equivalence A = 0, B=1, ..., Z=25, encrypt the message using John’s public key. Use a random number k = 4.[10]
--- Field problem: - Set: $\mathbb{Z}5 = \{0,1,2,3,4\}$ under addition and multiplication mod 5. ElGamal problem: - Public key: $(q, \alpha, YA) = (101, 2, 14)$ - Message: "CSIT" - Encoding: $A=0, B=1, \dots, Z=25$ - Random number: $k = 4$ All required data...
Full solved answer →State Fermat’s theorem with an example. Given the prime number p=29 and its primitive root g=8, private key sender with X=9 and random integer K=11, encrypt the message m=13 using ElGamal cryptosystem.[10]
If $p$ is a prime number and $a$ is an integer with $\gcd(a, p) = 1$, then: $$a^{p-1} \equiv 1 \pmod{p}$$ Let $p = 7$, $a = 3$: $$3^{6} \bmod 7$$ - $3^2 = 9 \equiv 2 \pmod 7$ - $3^3 = 27 \equiv 6 \pmod 7$ - $3^6 = (3^3)^2 = 6^2 = 36 \equiv 1 \pmod 7$ Thus $...
Full solved answer →Make Unit 3 stick
Practice CSC327 with flashcards & quizzes