Number Theory & Math Foundations for Cryptography

TAKEAWAYS:

• Modular arithmetic is the “clock math” behind RSA encryption and digital signatures, where $a\equiv b(\mathrm{mod}m)$ means $m$ divides $a-b$.
• Prime numbers are the “building blocks” of cryptography: RSA’s security relies on the hardness of factoring large primes like $p\times q$.
• Euler’s Totient $\varphi (n)$ and Fermat’s Little Theorem ($a^{p-1}\equiv 1(\mathrm{mod}p)$) unlock symmetric and asymmetric encryption schemes.
• The Miller-Rabin test efficiently checks if a number is probably prime—critical for generating RSA keys.
• Chinese Remainder Theorem (CRT) speeds up RSA decryption by splitting work across coprime factors.
• Real-world: WhatsApp uses modular arithmetic for end-to-end encryption keys; Ncell’s SIM cards rely on primes for authentication.

Core Concepts: The Math Behind Cryptography

1. Modular Arithmetic: The Clock Math of Cryptography

Modular arithmetic is the foundation of all modern cryptosystems. It defines operations “modulo $m$” (remainder after division by $m$), turning addition/subtraction/multiplication into cyclic operations—like a clock wrapping around at 12.

How it works: For integers $a$ and $b$, and modulus $m$: $$a\equiv b(\mathrm{mod}m)\text{if}m\mid (a-b)$$ Example: $17\equiv 2(\mathrm{mod}5)$ because $5\times 3=15$ and $17-15=2$.

Why it matters:

• Encryption: In RSA, plaintext $M$ is encrypted as $C=M^e(\mathrm{mod}n)$, where $n$ is a large composite.
• Key exchange: Diffie-Hellman uses modular exponentiation to share secrets.

Real-world use:

• WhatsApp’s Signal Protocol: Uses modular arithmetic to compute shared keys between users. When Alice and Bob exchange public keys $A$ and $B$, their shared secret is $A^B(\mathrm{mod}p)$, where $p$ is a large prime.
• Ncell SIM Authentication: Your SIM card’s unique identifier (IMSI) is hashed using modular operations to generate a response for network authentication.

2. Prime Numbers: The Backbone of RSA

Prime numbers are integers >1 with no divisors other than 1 and themselves. In cryptography, they are used to:

• Generate large keys (e.g., 2048-bit RSA keys use two 1024-bit primes).
• Ensure the security of asymmetric encryption (hardness of factoring $n=p\times q$).

Key properties:

• Uniqueness: Every integer >1 has a unique prime factorization (Fundamental Theorem of Arithmetic).
• Density: Primes become rarer as numbers grow, but checking primality for large numbers is computationally hard.

Example: Factorize 55: $$55=5\times 11$$ Both 5 and 11 are primes.

Real-world use:

• Nepal Rastra Bank (NRB) Digital Transactions: When you transfer money via eSewa or Khalti, the system uses RSA keys generated from two large primes to encrypt your transaction details. Breaking this would require factoring $n=p\times q$, which is infeasible for 2048-bit primes.
• NEPSE Stock Exchange: Encrypted communications between brokers and the exchange rely on prime-based cryptography to prevent fraud.

3. Fermat’s Little Theorem and Euler’s Totient

These theorems provide shortcuts for working with modular arithmetic in cryptography.

Fermat’s Little Theorem:

If $p$ is prime and $a$ is not divisible by $p$: $$a^{p-1}\equiv 1(\mathrm{mod}p)$$ Example: Let $p=7$, $a=3$: $$3^6=729\equiv 1(\mathrm{mod}7)\text{because}729÷7=104\text{ with remainder }1.$$

Euler’s Totient Function $\varphi (n)$:

Counts the integers up to $n$ that are coprime with $n$ (i.e., $\gcd (k,n)=1$). For a prime $p$: $$\varphi (p)=p-1$$ For $n=p\times q$ (two distinct primes): $$\varphi (n)=(p-1)(q-1)$$

Why it matters:

• RSA decryption uses Euler’s theorem: $C^d\equiv M(\mathrm{mod}n)$, where $d$ is the private exponent derived from $\varphi (n)$.

Real-world use:

• Khalti’s Secure Payments: When you pay via Khalti, the system uses Euler’s Totient to compute the private key for decrypting your transaction. For example, if $n=35$ (from primes 5 and 7), $\varphi (35)=4\times 6=24$. The private exponent $d$ is the modular inverse of the public exponent $e$ modulo 24.

4. Primality Testing: Is It Prime?

Testing if a number is prime is critical for cryptography. The Miller-Rabin test is a probabilistic method to check primality efficiently.

Miller-Rabin Algorithm Steps:

1. Write $n-1$ as $d\times 2^s$ (where $d$ is odd).
2. Pick a random $a$ in $2\le a\le n-2$.
3. Compute $x=a^d(\mathrm{mod}n)$.
4. If $x\equiv 1$ or $x\equiv n-1$, $n$ is probably prime.
5. Otherwise, square $x$ up to $s-1$ times. If none yield $n-1$, $n$ is composite.

Example: Test if 561 is prime (it’s a Carmichael number, so it fools naive tests).

• Let $a=2$:
  • $561-1=560=70\times 2^3$ → $d=70$, $s=3$.
  • $2^{70}(\mathrm{mod}561)=1$ → Fails (561 is composite).

stateDiagram-v2
  [*] --> Is n-1 = d*2^s?
  Is n-1 = d*2^s? --> Yes: Pick random a in [2, n-2]
  Pick random a in [2, n-2] --> Compute x = a^d mod n
  Compute x = a^d mod n --> Is x ≡ 1 or x ≡ n-1?
  Is x ≡ 1 or x ≡ n-1? --> Yes: n is probably prime
  Is x ≡ 1 or x ≡ n-1? --> No: Square x up to s-1 times
  Square x up to s-1 times --> Any x ≡ n-1? Yes: n is probably prime
  Any x ≡ n-1? No: n is composite

Real-world use:

• Pathao’s Driver Verification: When you register as a driver on Pathao, the app uses primality testing to generate a unique cryptographic key pair. The server checks if the public key’s modulus $n$ is probably prime using Miller-Rabin before accepting it.
• NTC’s Online Bill Payments: The NTC website uses primality tests to validate the large primes used in its SSL/TLS certificates, ensuring secure connections for online payments.

5. Chinese Remainder Theorem (CRT): Speeding Up RSA

CRT allows breaking a problem into smaller coprime parts and combining results. In RSA, it speeds up decryption by:

1. Splitting the ciphertext $C$ into parts using $p$ and $q$.
2. Decrypting each part separately: $M_p=C^d(\mathrm{mod}p)$, $M_q=C^d(\mathrm{mod}q)$.
3. Combining results to get $M$.

Example: Let $n=15$ ($p=3$, $q=5$), $C=8$, $d=7$ (private exponent).

• Decrypt $M_p=8^7(\mathrm{mod}3)=2$ (since $8\equiv 2(\mathrm{mod}3)$).
• Decrypt $M_q=8^7(\mathrm{mod}5)=3$ (since $8\equiv 3(\mathrm{mod}5)$).
• Combine using CRT: $M=2\times 5\times 2+3\times 3\times 1=20+9=29\equiv 4(\mathrm{mod}15)$.
• Original message $M=4$.

Real-world use:

• eSewa’s Fast Transactions: When you pay via eSewa, the system uses CRT to speed up decryption of your transaction details. Instead of computing $C^d(\mathrm{mod}n)$ (where $n$ is large), it splits the work into $C^d(\mathrm{mod}p)$ and $C^d(\mathrm{mod}q)$, then combines results—saving time and computational power.

## In the Real World

1. WhatsApp/Signal Protocol:

   • Idea: Modular arithmetic and primes.
   • How: When Alice and Bob exchange keys, they compute a shared secret using $A^B(\mathrm{mod}p)$, where $p$ is a large prime (e.g., 2048-bit). This ensures only they can decrypt messages.

2. Ncell SIM Authentication:

   • Idea: Primality testing and modular exponentiation.
   • How: Your SIM’s unique identifier is hashed using primes to generate a response for the network. If the response matches, your SIM is authenticated.

3. Khalti/eSewa Payments:

   • Idea: RSA encryption (primes + Euler’s Totient).
   • How: When you transfer money, your transaction details are encrypted as $C=M^e(\mathrm{mod}n)$, where $n=p\times q$. The merchant’s server decrypts using $d$ (derived from $\varphi (n)$).

4. NEPSE Stock Exchange:

   • Idea: Secure communication via primes.
   • How: Brokers and the exchange use RSA keys (based on large primes) to encrypt order details, preventing insider trading or fraud.

5. Pathao/Daraz Driver Verification:

   • Idea: Miller-Rabin primality test.
   • How: When you register, the app checks if your cryptographic key’s modulus $n$ is probably prime before accepting it. This ensures only valid keys are used for secure communications.

## Exam Tip

1. Modular Arithmetic:

   • Always reduce results to the smallest positive remainder (e.g., $-3(\mathrm{mod}5)=2$).
   • Practice computing $a^b(\mathrm{mod}m)$ efficiently (use exponentiation by squaring).

2. Primes and Factorization:

   • Memorize: Primes are the “atoms” of cryptography. RSA’s security relies on the difficulty of factoring $n=p\times q$.
   • For exams: Given $n$, factorize it into primes if possible (e.g., $n=15=3\times 5$).

3. Fermat’s Little Theorem vs. Euler’s Totient:

   • Fermat’s theorem applies only to primes: $a^{p-1}\equiv 1(\mathrm{mod}p)$.
   • Euler’s theorem generalizes: $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ for any $n$ coprime with $a$.

4. Miller-Rabin Test:

   • Key steps: Write $n-1=d\times 2^s$, pick $a$, compute $x=a^d(\mathrm{mod}n)$, check squares.
   • Exam trick: If $n$ passes for a few random $a$, it’s probably prime. For full marks, show all steps for one example.

5. CRT in RSA:

   • Explain how splitting decryption into $p$ and $q$ reduces computation time.
   • Example: Given $n=p\times q$, $C$, and $d$, show how to compute $M$ using CRT.

6. Common Pitfalls:

   • Off-by-one errors: $a^{p-1}\equiv 1(\mathrm{mod}p)$ (not $a^p$).
   • Non-coprime cases: Euler’s theorem requires $\gcd (a,n)=1$.
   • Miller-Rabin: Always check all $s$ squarings, not just the first.

Past Exam Question Breakdown: For the question:

“What do you mean by ‘Feistel Structure for Block Ciphers’? Explain with block diagram. How can a number be tested for primality using Miller-Rabin algorithm? Explain with suitable example.”

Expected Answer Structure:

1. Feistel Structure (5 marks):

   • Definition: A block cipher design where plaintext is split into two halves, processed in rounds with a function $F$ and a subkey.
   • Diagram: Draw a 4-round Feistel network with inputs $L_0,R_0$, rounds $L_{i+1}=R_i$, $R_{i+1}=L_i\oplus F(R_i,K_i)$.
   • Example: DES uses Feistel structure.

2. Miller-Rabin (5 marks):

   • Steps: Write $n-1=d\times 2^s$, pick $a$, compute $x=a^d(\mathrm{mod}n)$, square up to $s-1$ times.
   • Example: Test $n=561$ with $a=2$ (show it fails).
   • Conclusion: 561 is composite (Carmichael number).

Visual for Feistel Structure: