Skip to main content

Week - 6

TITLE

Lecture 26:
More on RSA​

Fast Modular Exponentiation (Square & Multiply)​

Goal​

Compute:

anmod  ma^n \mod m

efficiently

Idea​

  • Write exponent in binary:

    n=(bkbk−1...b0)2n = (b_k b_{k-1} ... b_0)_2

  • Then:

    an=ab020⋅ab121⋯abk2ka^n = a^{b_0 2^0} \cdot a^{b_1 2^1} \cdots a^{b_k 2^k}

Key Observation​

a2i=(a2i−1)2a^{2^i} = (a^{2^{i-1}})^2

✔ Compute using repeated squaring

Complexity​

  • Number of steps: O(log⁡n)O(\log n)

✔ Much faster than naive ( O(n) )

Algorithm (Concept)​

  1. Convert ( n ) to binary

  2. Initialize result = 1

  3. For each bit:

    • Square current value
    • If bit = 1 → multiply

Side-Channel Attack (Timing Attack)​

Problem​

  • Computation time depends on:

    • Bits of exponent

Idea​

  • Attacker measures:

    • Execution time

  • Infers:

    • Whether bit = 1 or 0

Example Insight​

  • If extra multiplication occurs → bit = 1
  • Leads to key leakage

RSA Key Generation (Practical Issues)​

1. Prime Generation​

Need:

p,q large primes (e.g., 512+ bits)p, q \text{ large primes (e.g., 512+ bits)}

Naive Method (Inefficient)​

  • Check divisibility up to: n\sqrt{n}

❌ Too slow for large numbers

Sieve Method​

  • Remove multiples:

    • 2, 3, 5, ...

✔ Works for small ( n ) ❌ Not practical for large primes

Efficient Approach​

  • Use probabilistic tests

Example:​

  • Miller-Rabin test

✔ Fast ✔ High probability of correctness

RSA Security​

Based On​

n=p⋅qn = p \cdot q

  • Public:

    nn

  • Secret:

    p,qp, q

Hard Problem​

Factorization of large integers\text{Factorization of large integers}

Why Secure?​

  • Given: nn

❌ Hard to compute:

p,qp, q

Key Insight​

  • If attacker finds: p,qp, q

→ Can compute:

ϕ(n)\phi(n)

→ Then:

dd

→ System breaks

Key Takeaways​

  • Square & multiply:

    • Efficient exponentiation

  • Timing attacks:

    • Real-world vulnerability

  • Prime generation:

    • Uses probabilistic tests

  • RSA security:

    • Depends on factorization hardness

Final Conclusion​

  • RSA efficiency:

    O(log⁡n)O(\log n)

  • RSA security:

    Hardness of factoring n=p⋅q\text{Hardness of factoring } n = p \cdot q

✔ Still widely used, but requires:

  • Large keys
  • Secure implementations
TITLE

Lecture 27:
Primality Testing​

Goal​

  • Check whether a number ( n ) is prime or composite

Fermat Primality Test​

Idea (from Fermat’s Little Theorem)​

If ( p ) is prime and ( \gcd(a,p)=1 ), then:

ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}

Algorithm​

  1. Choose random:

    a<na < n

  2. Compute:

    y=an−1mod  ny = a^{n-1} \mod n

  3. Check:

  • If:

    y≠1y \ne 1

    → ( n ) is composite ✅

  • If:

    y=1y = 1

    → ( n ) is probably prime

Limitation​

  • Some composite numbers pass test

  • Called:

    • Fermat pseudoprimes

Miller–Rabin Primality Test​

Stronger Test​

Step 1: Write​

n−1=2k⋅mn - 1 = 2^k \cdot m

where:

m is oddm \text{ is odd}

Step 2: Choose Random Base​

a<na < n

Step 3: Compute​

b0=ammod  nb_0 = a^m \mod n

Step 4: Check Conditions​

  • If: b0≡1(modn)b_0 \equiv 1 \pmod{n} → probably prime
  • Else compute:
bi=bi−12mod  nb_i = b_{i-1}^2 \mod n

Check if any:

bi≡−1(modn)b_i \equiv -1 \pmod{n}

→ probably prime

Final Decision​

  • If none satisfy: ±1\pm 1

→ ( n ) is composite ✅

Key Property​

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

Why Better than Fermat​

  • Detects:

    • Carmichael numbers

  • Much lower error probability

Key Takeaways​

  • Fermat test:

    • Fast but weak

  • Miller-Rabin:

    • Fast and reliable

  • Used in:

    • RSA key generation

Final Conclusion​

  • Primality testing is:

    Essential for generating large primes\text{Essential for generating large primes}

  • Practical systems use:

    • Miller-Rabin test

✔ Efficient + high confidence for cryptography

TITLE

Lecture 28:
ElGamal Cryptosystem.​

Overview​

  • Public key cryptosystem based on: Discrete Logarithm Problem\text{Discrete Logarithm Problem}

Setup (Bob)​

Step 1: Choose Parameters​

  • Prime:

    pp

  • Generator:

    α∈Zp∗\alpha \in \mathbb{Z}_p^*

Step 2: Choose Secret Key​

a∈1,2,...,p−2a \in {1,2,...,p-2}

Step 3: Compute Public Value​

β=αamod  p\beta = \alpha^a \mod p

Keys​

  • Public key:

    (p,α,β)(p, \alpha, \beta)

  • Private key:

    aa

Encryption (Alice)​

Input​

  • Message:

    x∈Zp∗x \in \mathbb{Z}_p^*

  • Choose random:

    kk

Compute Ciphertext​

y1=αkmod  py_1 = \alpha^k \mod p y2=x⋅βkmod  py_2 = x \cdot \beta^k \mod p

Ciphertext​

(y1,y2)(y_1, y_2)

Decryption (Bob)​

Step 1​

y1a=(αk)a=αak=βkmod  py_1^a = (\alpha^k)^a = \alpha^{ak} = \beta^k \mod p

Step 2​

x=y2⋅(y1a)−1mod  px = y_2 \cdot (y_1^a)^{-1} \mod p

Why It Works​

y2=x⋅βky_2 = x \cdot \beta^k y1a=βky_1^a = \beta^k

So:

x=y2βkmod  px = \frac{y_2}{\beta^k} \mod p

✔ Correct decryption

Important Property​

  • Same message → different ciphertexts

✔ Because of random:

kk

Example​

Given​

p=2579,;α=2,;a=765p = 2579,; \alpha = 2,; a = 765

Compute​

β=2765mod  2579=949\beta = 2^{765} \mod 2579 = 949

Encryption​

Message:

x=1299x = 1299

Choose:

kk
y1=2kmod  2579=435y_1 = 2^k \mod 2579 = 435 y2=1299⋅949kmod  2579=2396y_2 = 1299 \cdot 949^k \mod 2579 = 2396

Ciphertext​

(435,2396)(435, 2396)

Decryption​

x=y2⋅(y1a)−1mod  px = y_2 \cdot (y_1^a)^{-1} \mod p x=1299x = 1299

✔ Original message recovered

Security​

  • Based on: Discrete logarithm hardness\text{Discrete logarithm hardness}

Key Takeaways​

  • Uses:

    • Modular exponentiation

  • Randomness:

    • Provides semantic security

  • Different from RSA:

    • Non-deterministic

Final Conclusion​

  • ElGamal provides:

    • Strong security
    • Randomized encryption
Widely used in cryptographic protocols and digital signatures\text{Widely used in cryptographic protocols and digital signatures}
TITLE

Lecture 29:
Elliptic Curve over the Reals​

Curve Equation​

y2=x3+ax+by^2 = x^3 + ax + b
  • Condition: 4a3+27b2≠04a^3 + 27b^2 \ne 0

✔ Ensures no singular points

Point Set​

  • Points:

    (x,y)(x,y)

    satisfying equation

  • Plus point at infinity:

    O\mathcal{O}

Point Addition​

Let:

  • P=(x1,y1)P = (x_1, y_1)
  • Q=(x2,y2)Q = (x_2, y_2)

Case 1: P≠QP \ne Q​

Slope:

λ=y2−y1x2−x1\lambda = \frac{y_2 - y_1}{x_2 - x_1}

Coordinates:

x3=λ2−x1−x2x_3 = \lambda^2 - x_1 - x_2 y3=λ(x1−x3)−y1y_3 = \lambda(x_1 - x_3) - y_1

Case 2: Q=−PQ = -P​

P+Q=OP + Q = \mathcal{O}
  • Where: (x,y)→(x,−y)(x, y) \rightarrow (x, -y)

Case 3: P=QP = Q (Point Doubling)​

Slope:

λ=3x12+a2y1\lambda = \frac{3x_1^2 + a}{2y_1}

Coordinates:

x3=λ2−2x1x_3 = \lambda^2 - 2x_1 y3=λ(x1−x3)−y1y_3 = \lambda(x_1 - x_3) - y_1

Inverse of Point​

P=(x,y)P = (x,y) −P=(x,−y)-P = (x, -y)

Identity Element​

O\mathcal{O}
  • Point at infinity

Group Properties​

  • Closure

  • Associativity

  • Identity:

    P+O=PP + \mathcal{O} = P

  • Inverse:

    P+(−P)=OP + (-P) = \mathcal{O}

  • Commutative:

    P+Q=Q+PP + Q = Q + P

✔ Forms Abelian group

Key Operation (Scalar Multiplication)​

kP=P+P+⋯+PkP = P + P + \cdots + P

Cryptographic Idea​

  • Given: P,;kPP,; kP

❌ Hard to find:

kk

✔ Elliptic Curve Discrete Log Problem

Key Takeaways​

  • Points on curve form group
  • Addition defined geometrically + algebraically
  • Security based on: ECDLP\text{ECDLP}

Final Conclusion​

  • Elliptic curves provide:
High security with smaller key sizes\text{High security with smaller key sizes}

✔ Widely used in modern cryptography (ECC)

TITLE

Lecture 30:
Elliptic curve Modulo a Prime​

Over (Zp\mathbb{Z}_p )​

Curve​

y2≡x3+ax+b(modp)y^2 \equiv x^3 + ax + b \pmod{p}

  • Points:

    (x,y)∈Zp(x,y) \in \mathbb{Z}_p

  • Plus:

    O\mathcal{O}

Finding Points​

For each:

x∈0,1,2,...,p−1x \in {0,1,2,...,p-1}

Compute:

z=x3+ax+bmod  pz = x^3 + ax + b \mod p

Check Validity​

  • Check if (z)( z ) is quadratic residue:
zp−12≡1(modp)z^{\frac{p-1}{2}} \equiv 1 \pmod{p}

✔ If true → valid point exists

Compute ( y )​

If:

p≡3(mod4)p \equiv 3 \pmod{4}

Then:

y=zp+14mod  py = z^{\frac{p+1}{4}} \mod p
  • Points: (x,y),;(x,−y)(x, y),; (x, -y)

Example​

Given:

p=11p = 11 y2≡x3+x+6(mod11)y^2 \equiv x^3 + x + 6 \pmod{11}

Quadratic Residues mod 11​

1,3,4,5,9{1,3,4,5,9}

Valid Points​

(2,4),(2,7)(2,4), (2,7) (3,5),(3,6)(3,5), (3,6) (5,2),(5,9)(5,2), (5,9) (7,2),(7,9)(7,2), (7,9) (8,3),(8,8)(8,3), (8,8) (10,2),(10,9)(10,2), (10,9)

Total Points​

12+1=1312 + 1 = 13

(including (O)( \mathcal{O} ))

Notes​

  • For each valid ( x ):

    • Either 0 or 2 points

  • Symmetry:

    y↔−yy \leftrightarrow -y

Key Idea​

  • Points form group under addition
  • Used for: Elliptic Curve Cryptography (ECC)\text{Elliptic Curve Cryptography (ECC)}