Number Theory & Math Foundations: Primes, GCD, RSA, ElGamal

Core Concepts & Definitions

1. Prime Numbers & Primality Testing

Definition: A prime number is a natural number >1 divisible only by 1 and itself. Primes are the building blocks of RSA and ElGamal.

Why primes?

• RSA: Relies on the hardness of factoring large primes (e.g., $p\times q$).
• ElGamal: Uses a prime $q$ and primitive root $\alpha$ for secure key exchange.
• Diffie-Hellman: Requires a prime $p$ and generator $g$ to prevent MITM attacks.

Primality Tests

Example: Miller-Rabin Test for $n=561$

1. Factor $n-1=560=2^4\times 35$.
2. Pick a witness $a=2$.
3. Compute $a^d\mathrm{mod}n$ where $d=35$: $2^{35}\mathrm{mod}561=1$ (passes). But $a=7$ fails → 561 is composite (Carmichael number).

stateDiagram-v2
    [*] --> IsPrime: Check if n > 1
    IsPrime --> TrialDivision: For small n
    IsPrime --> FermatTest: Fast but unreliable
    IsPrime --> MillerRabin: Reliable (k rounds)
    MillerRabin --> Pass: If all tests pass
    MillerRabin --> Fail: If any witness fails

2. Modular Arithmetic & Congruences

Definition: $a\equiv b\mathrm{mod}m$ means $m$ divides $(a-b)$. Key Properties:

• $(a+b)\mathrm{mod}m=[(a\mathrm{mod}m)+(b\mathrm{mod}m)]\mathrm{mod}m$
• $(a\times b)\mathrm{mod}m=[(a\mathrm{mod}m)\times (b\mathrm{mod}m)]\mathrm{mod}m$

Example: RSA Encryption

• Public key: $(e,n)=(29,561)$ (where $n=3\times 11\times 17$).
• Encrypt $m=4$: $c=4^{29}\mathrm{mod}561$. Compute step-by-step: $4^2=16$, $4^4=256$, $4^8=256^2\mathrm{mod}561=67$, $4^{16}=67^2\mathrm{mod}561=169$, $4^{29}=169\times 67\times 4\mathrm{mod}561=3$.

3. Euler’s Totient Function $\varphi (n)$

Definition: Counts integers up to $n$ coprime with $n$. Formula:

• If $n=p_1^{k_1}{p}_2^{k_2}\dots p_m^{k_m}$, then $\varphi (n)=n\times {\prod }_{i=1}^m\left(1-\frac{1}{p_i}\right)$.

Example: $n=12=2^2\times 3$ $\varphi (12)=12\times (1-\frac{1}{2})\times (1-\frac{1}{3})=4$.

Role in RSA:

• Private key $d$ is the modular inverse of $e$ modulo $\varphi (n)$: $d\equiv e^{-1}\mathrm{mod}\varphi (n)$.

4. Greatest Common Divisor (GCD) & Euclidean Algorithm

Definition: Largest integer dividing two numbers without remainder. Euclidean Algorithm:

1. Divide $a$ by $b$, get remainder $r$.
2. Replace $a$ with $b$, $b$ with $r$.
3. Repeat until $r=0$. GCD is the last non-zero remainder.

Example: $\gcd (12,16)$

16 = 1 × 12 + 4
12 = 3 × 4 + 0 → GCD = 4

Extended Euclidean Algorithm: Finds integers $x,y$ such that $ax+by=\gcd (a,b)$. Use in RSA: Computes the private key $d$.

In the Real World

1. eSewa & Khalti (Nepal)

   • Use RSA for secure payment authentication. When you log in, your device generates a session key encrypted with eSewa’s public key (derived from large primes). The private key (kept secret) decrypts it to verify your identity.
   • Example: If eSewa’s modulus $n=p\times q$ (where $p,q$ are 2048-bit primes), breaking RSA would require factoring $n$, which is computationally infeasible.

2. Ncell & NTC (Nepal)

   • Diffie-Hellman (DH) secures your 4G/5G connection. When your phone connects to a tower, it exchanges $g^a\mathrm{mod}p$ and $g^b\mathrm{mod}p$ to derive a shared secret key for encryption. An eavesdropper (MITM) would need to solve the Discrete Logarithm Problem (DLP), which is hard for large primes.

3. YouTube (Global)

   • Digital Signatures (DSA/ECDSA) verify video uploads. When you upload a video, YouTube signs it with its private key. Viewers use the public key to verify the signature, ensuring the video hasn’t been tampered with. This relies on Euler’s theorem and primitive roots in finite fields.

Worked Example: ElGamal Encryption (Nepal Context)

Scenario: A farmer in Pokhara wants to send a secret message to a buyer via Pathao’s secure chat (hypothetical). The system uses ElGamal.

• Public params: $q=101$ (prime), $\alpha =2$ (primitive root), $Y_A=14$ (buyer’s public key).
• Farmer’s private key: $X=9$, random $K=11$.
• Message: "CSIT" → $m=2$ (C=2, S=18, I=8, T=19; here, we encrypt "C" as 2).

Steps:

1. Compute shared secret: $\beta ={\alpha }^X\mathrm{mod}q=2^9\mathrm{mod}101=512\mathrm{mod}101=41$.
2. Encrypt $m=2$:
   • $c_1={\alpha }^K\mathrm{mod}q=2^{11}\mathrm{mod}101=2048\mathrm{mod}101=9$.
   • $c_2=m\times {\beta }^K\mathrm{mod}q=2\times 41^{11}\mathrm{mod}101$. Compute $41^{11}\mathrm{mod}101$: $41^2=1681\mathrm{mod}101=61$, $41^4=61^2=3721\mathrm{mod}101=51$, $41^8=51^2=2601\mathrm{mod}101=9$, $41^{11}=9\times 51\times 41\mathrm{mod}101=18549\mathrm{mod}101=85$. So, $c_2=2\times 85\mathrm{mod}101=170\mathrm{mod}101=69$.
3. Ciphertext: $(9,69)$.

Decryption by Buyer:

• Buyer computes $\beta =Y_A^X\mathrm{mod}q=14^9\mathrm{mod}101$. $14^2=196\mathrm{mod}101=95$, $14^4=95^2=9025\mathrm{mod}101=41$, $14^8=41^2=1681\mathrm{mod}101=61$, $14^9=61\times 14=854\mathrm{mod}101=41$.
• Then, $m=c_2\times (c_1^X{)}^{-1}\mathrm{mod}q$. $c_1^X=9^9\mathrm{mod}101=387420489\mathrm{mod}101=41$. $(c_1^X{)}^{-1}\mathrm{mod}101$ is the inverse of 41, which is 77 (since $41\times 77\mathrm{mod}101=1$). $m=69\times 77\mathrm{mod}101=5313\mathrm{mod}101=2$.

Comparison: Symmetric vs. Asymmetric Cryptography

Exam Tip

1. Memorize Definitions:

   • Prime, totient function $\varphi (n)$, congruence, GCD, and their formulas.
   • Fermat’s Little Theorem: $a^{p-1}\equiv 1\mathrm{mod}p$ if $p$ is prime and $\gcd (a,p)=1$.

2. Algorithms:

   • Euclidean Algorithm: Practice on $\gcd (1234,567)$.
   • Miller-Rabin: Show steps for $n=2047$ (Carmichael number).

3. Worked Examples:

   • RSA: Given $p,q,e$, compute $d$ and encrypt/decrypt.
   • ElGamal: Given $q,\alpha ,Y_A,X,K$, encrypt/decrypt a message.
   • Primality Test: Apply Miller-Rabin to $n=701$ (prime) and $n=561$ (composite).

4. Real-World Links:

   • eSewa/Khalti: RSA for authentication.
   • Ncell/NTC: DH for secure key exchange.
   • YouTube: DSA for digital signatures.

5. Common Pitfalls:

   • Forgetting to check $\gcd (a,n)=1$ in Fermat’s theorem.
   • Misapplying the Euclidean algorithm (e.g., not updating $a$ and $b$ correctly).
   • Confusing primitive roots (used in ElGamal/DH) with just any generator.

Diagram of Alice and Bob exchanging $g^a\mathrm{mod}p$ and $g^b\mathrm{mod}p$ to derive $g^{ab}\mathrm{mod}p$. (Image: de:Benutzer:DaMutz, CC BY-SA 4.0, via Wikimedia Commons)