Week - 7

TITLE

Lecture 31:
Generalised ElGamal Public Key Cryptosystem

Setup (General)

• Cyclic group:

  $$G$$

• Generator:

  $$\alpha$$

• Private key:

  $$a$$

• Public key:

  $$\beta = \alpha^a$$

• Public:

  $$(G,\alpha,\beta)$$

---

Encryption

Choose random:

$$k$$

Ciphertext:

$$y_1 = \alpha^k$$ $$y_2 = x \cdot \beta^k$$

---

Decryption

$$x = y_2 \cdot (y_1^a)^{-1}$$

---

Core Hard Problem

$$\beta = \alpha^a \Rightarrow \text{find } a$$

(Discrete Log Problem)

---

Elliptic Curve Version

• Group:

  $$E(\mathbb{Z}_p)$$

• Operation: point addition

---

Keys

• Generator point:

  $$\alpha$$

• Private key:

  $$a$$

• Public key:

  $$\beta = a\alpha$$

---

Encryption (ECC)

Choose random:

$$k$$ $$y_1 = k\alpha$$ $$y_2 = x + k\beta$$

---

Decryption

$$x = y_2 - a y_1$$

---

Example Values

• $p = 11$

• Curve:

  $$y^2 \equiv x^3 + x + 6 \pmod{11}$$

• Generator:

  $$\alpha = (2,7)$$

• Private:

  $$a = 7$$

• Public:

  $$\beta = (7,2)$$

---

Encryption Example

Message:

$$x = (10,9)$$

Random:

$$k = 3$$ $$y_1 = (8,3)$$ $$y_2 = (10,2)$$

---

Decryption

$$x = (10,2) - 7(8,3) = (10,9)$$

---

Notes

• Uses point addition instead of multiplication

• Security based on:

  $$\text{ECDLP}$$

• Smaller keys, strong security

TITLE

Lecture 32:
Chinese Remainder Theorem

Linear Equations (mod p)

Given:

$$4x + 7y \equiv 9 \pmod{13}$$ $$5x + 2y \equiv 3 \pmod{13}$$

---

Steps

• Multiply by inverses:

$$4^{-1} \equiv 10 \pmod{13}$$ $$5^{-1} \equiv 8 \pmod{13}$$

---

Transform

$$x + 5y \equiv 12 \pmod{13}$$ $$x + 3y \equiv 11 \pmod{13}$$

---

Subtract

$$2y \equiv 1 \pmod{13}$$ $$y \equiv 7 \pmod{13}$$

---

Substitute

$$x = 12 - 5y \equiv 3 \pmod{13}$$

---

Solution

$$x = 3,\quad y = 7$$

---

Chinese Remainder Theorem (2 equations)

Given:

$$x \equiv a \pmod{m}$$ $$x \equiv b \pmod{n}$$

Condition:

$$\gcd(m,n)=1$$

---

General Form

$$x = a + tm$$

Substitute:

$$a + tm \equiv b \pmod{n}$$

---

Solve for ( t )

$$t \equiv m^{-1}(b-a) \pmod{n}$$

---

Final Solution

$$x = a + tm \pmod{mn}$$

---

Example

$$x \equiv 3 \pmod{5}$$ $$x \equiv 5 \pmod{7}$$

---

Compute

$$5^{-1} \equiv 3 \pmod{7}$$ $$t = 3(5-3) \equiv 6 \pmod{7}$$

---

Result

$$x = 3 + 5 \cdot 6 = 33$$ $$x \equiv 33 \pmod{35}$$

---

General CRT (r equations)

Given:

$$x \equiv a_i \pmod{m_i}$$

Condition:

$$\gcd(m_i,m_j)=1$$

---

Define

$$M = \prod m_i$$ $$M_i = \frac{M}{m_i}$$ $$y_i = M_i^{-1} \pmod{m_i}$$

---

Solution

$$x = \sum a_i M_i y_i \pmod{M}$$

---

Key Properties

• Unique solution:

  $$\mod \left(\prod m_i\right)$$

• Works only if moduli are pairwise coprime

---

Key Insight

• Break big modulus into smaller ones
• Solve separately
• Combine using CRT

---

Final Note

• Used in:

  • RSA optimization
  • Cryptographic computations

TITLE

Lecture 33:
Rabin Cryptosystem

Quadratic Residue

Definition:

$$a \text{ is quadratic residue mod } p \iff \exists y:\ y^2 \equiv a \pmod{p}$$

---

Euler Criterion

$$a^{\frac{p-1}{2}} \equiv 1 \pmod{p} ;; \Rightarrow ;; a \text{ is QR}$$ $$a^{\frac{p-1}{2}} \equiv -1 \pmod{p} ;; \Rightarrow ;; a \text{ is non-QR}$$

---

Square Root (Special Case)

If:

$$p \equiv 3 \pmod{4}$$

Then:

$$y \equiv \pm a^{\frac{p+1}{4}} \pmod{p}$$

---

Key Generation

• Choose primes:

$$p \equiv q \equiv 3 \pmod{4}$$

• Compute:

$$n = pq$$

• Public key:

$$n$$

• Private key:

$$(p, q)$$

---

Plaintext Space

$$x \in \mathbb{Z}_n^*$$

---

Encryption

$$y \equiv x^2 \pmod{n}$$

---

Decryption

Solve:

$$x^2 \equiv y \pmod{n}$$

Using CRT:

$$x^2 \equiv y \pmod{p}$$ $$x^2 \equiv y \pmod{q}$$

---

Roots

From each:

$$x \equiv \pm y^{\frac{p+1}{4}} \pmod{p}$$ $$x \equiv \pm y^{\frac{q+1}{4}} \pmod{q}$$

---

Total Solutions

$$4 \text{ possible values of } x$$

---

Example

Given:

$$p = 7,; q = 11,; n = 77$$

Ciphertext:

$$y = 23$$

---

Solve

$$x^2 \equiv 23 \pmod{7}$$ $$x^2 \equiv 23 \pmod{11}$$

---

Final Solutions

$$x \in {10, 32, 45, 67}$$

---

Key Points

• Not injective → 1 ciphertext → 4 plaintexts
• Requires guessing / redundancy
• Based on square root modulo problem

---

Insight

• Uses:

  • CRT
  • Quadratic residues
  • Modular square roots

• Limitation:

  • Ambiguity (4 solutions) → not widely used

TITLE

Lecture 34:
Legendre and Jacobi Symbol

Quadratic Residues Count

• In ( $\mathbb{Z}_p$ ) (p prime):

$$|\text{QR}| = |\text{Non-QR}| = \frac{p-1}{2}$$

---

Construction

Set:

$${1^2, 2^2, ..., (\frac{p-1}{2})^2} \mod p$$

✔ Gives all quadratic residues

---

Legendre Symbol

$$\left(\frac{a}{p}\right) = \begin{cases} 0 & p \mid a \ 1 & a \text{ is QR mod } p \ -1 & a \text{ is non-QR mod } p \end{cases}$$

---

Euler Relation

$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p$$

---

Multiplicative Property

$$\left(\frac{mn}{p}\right) = \left(\frac{m}{p}\right)\left(\frac{n}{p}\right)$$

---

Special Values

For ( -1 )

$$\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}$$

• (= 1) if:

  $$p \equiv 1 \pmod{4}$$

• (= -1) if:

  $$p \equiv 3 \pmod{4}$$

---

For ( 2 )

$$\left(\frac{2}{p}\right) = (-1)^{\frac{p^2 - 1}{8}}$$

• (= 1) if:

  $$p \equiv \pm 1 \pmod{8}$$

• (= -1) if:

  $$p \equiv \pm 3 \pmod{8}$$

---

Congruence Property

If:

$$a \equiv b \pmod{p}$$

Then:

$$\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$$

---

Jacobi Symbol

For:

$$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$

Define:

$$\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{e_1} \left(\frac{a}{p_2}\right)^{e_2} \cdots \left(\frac{a}{p_k}\right)^{e_k}$$

---

Properties (Jacobi)

$$\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$$ $$\left(\frac{a}{mn}\right) = \left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$$

---

Quadratic Reciprocity

$$\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\frac{(m-1)(n-1)}{4}}$$

---

Key Insight

• Fast QR checking using:

  $$a^{\frac{p-1}{2}} \mod p$$

• Used in:

  • Primality testing
  • Cryptography

---

Note

• Jacobi ≠ guarantee of QR
• Only: $$\left(\frac{a}{n}\right) = -1 \Rightarrow \text{non-QR}$$

---

Use

• Efficient computation of residue properties
• Important in crypto algorithms

TITLE

Lecture 35:
Jacobi Symbol (Contd.)

Jacobi Symbol Computation

Given:

$$\left(\frac{a}{n}\right), \quad n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$ $$\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{e_1} \left(\frac{a}{p_2}\right)^{e_2} \cdots \left(\frac{a}{p_k}\right)^{e_k}$$

---

Example Structure

For:

$$n = 9975 = 3 \cdot 5^2 \cdot 7 \cdot 19$$ $$\left(\frac{6278}{9975}\right) = \left(\frac{6278}{3}\right) \left(\frac{6278}{5}\right)^2 \left(\frac{6278}{7}\right) \left(\frac{6278}{19}\right)$$

✔ Reduce using:

$$a \equiv b \pmod{p}$$

---

Euler-Based Check

$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p$$

---

Euler Pseudoprime

If:

$$\left(\frac{a}{n}\right) \equiv a^{\frac{n-1}{2}} \mod n$$

Then:

• (n) behaves like prime for base (a)
• Called Euler pseudoprime

---

Solovay–Strassen Test

Input:

• Odd integer ( n > 2 )

Steps:

1. Choose random:

$$a \in [1, n-1]$$

2. Compute:

$$x = \left(\frac{a}{n}\right)$$

3. Compute:

$$y \equiv a^{\frac{n-1}{2}} \mod n$$

---

Decision:

• If:

$$x = 0$$

→ (n) is composite

---

• If:

$$y \not\equiv x \mod n$$

→ (n) is composite

---

• Else:

→ (n) is probably prime

---

Property

• If algorithm says composite → always correct
• If prime → probabilistic

---

Goldwasser–Micali Cryptosystem

Key Generation

• Choose primes:

$$p, q$$

• Compute:

$$n = pq$$

• Choose:

$$m \text{ such that } \left(\frac{m}{p}\right) = -1,; \left(\frac{m}{q}\right) = -1$$

Then:

$$\left(\frac{m}{n}\right) = 1$$

✔ (m) = pseudo-quadratic residue

---

Public Key

$$(n, m)$$

Private Key

$$(p, q)$$

---

Encryption

Plaintext:

$$x \in {0,1}$$

Choose random:

$$r \in \mathbb{Z}_n^*$$

Ciphertext:

$$y \equiv r^2 \cdot m^x \mod n$$

---

Decryption

Check QR:

• If:

$$y \text{ is QR mod } p \text{ and } q$$

→

$$x = 0$$

---

• Else:

$$x = 1$$

---

Key Insight

• Security based on:

  • Difficulty of distinguishing QR vs non-QR
  • Without knowing (p, q)

---

Important Note

• Jacobi = 1 does NOT guarantee QR
• Used to hide bit information securely

---

Use

• Probabilistic primality testing
• Bit encryption scheme (GM cryptosystem)