HackingCrypto

Discrete Logarithm

Math

1. ElGamal Systems

Key Generation
$({\mathbb {Z}}_{p}^{*}, \cdot)$ : Cyclic group
1) $p$ : prime.
2) $e_1$ : primitive root of $({\mathbb {Z}}_{p}^{*}, \cdot)$

choose $d \in {\mathbb {Z}}_{p}^{*}$ and compute $e_2 \equiv {e_1}^d \mod p$

public key : $e_1, e_2, p$
private key : $d$

Encryption
$r \in {\mathbb {Z}}_{p}^{*} $
$C_1 \equiv {e_1}^r \mod p$
$C_2 \equiv M{e_2}^r \mod p$
$C = (C_1, C_2)$ is cipher text

Decryption
1) ${C_1}^d \equiv ({e_1}^r)^d \equiv ({e_1}^d)^r \equiv {e_2}^r \mod p$
2) $C_2({e_2}^r)^{-1} \equiv M \mod p$

2. Baby-step / Giant-step

$y \equiv g^x \mod p$
$x = \left\lceil x \right\rceil $ is the smallest integer greater than or equal to $x$

Let $m = \left\lceil \sqrt{p} \right\rceil, \exists q, r \in {Z}\quad$ s.t $\quad x = m\cdot q + r \quad (0 \leq r \leq m-1)$

$\Rightarrow y \equiv g^x \equiv g^{mq + r} \mod p$
$\Rightarrow y(g^{-m})^q \equiv g^r \mod p$

1) Construct a table with entries $(r, g^r \mod p)$ for $0 \leq r \leq m - 1$
2) Compute $g^{-m} \mod p$
3) For $q$ from $0$ to $m - 1$ find $q$ s.t $y(g^{-m})^q \equiv g^r \mod p$ in the table.

Example

$13 = 5^x \mod 23$
Set $m = \left\lceil \sqrt{23} \right\rceil = 5$
Construct a table with entries $(r, 5^r \mod p)$ for $0 \leq r \leq 4$

$r$ 0 1 2 3 4
$5^r \mod 23$ 1 5 2 10 4

Compute $5^{-5} \equiv 15 \mod 23$

q 0 1 2 3 4
$13 \cdot 15^q \mod 23$ 13 11 4 14 3

find $13 \cdot 15^q \equiv 5^x \mod 23$
so, $q = 2, r = 4. \quad x = m \cdot q + r$
$x = 5 * 2 + 4 = 14$

3. ElGamal - Low modulus Attack

If value of $p$ is not large enough, Eve can find $d$ or $r$.

4. ElGamal - Known Plaintext Attack

If Alice uses the same random exponent r, to encrypt two plaintext $P$ and $P’$, Eve finds $P’$ if she knows $P$.

Let $C_2 \equiv P \cdot {e_2}^r \mod p$ and ${C_2}’ \equiv P’ \cdot {e_2}^r \mod p$
Since ${e_2}^r \equiv C_2 \cdot P^{-1} \mod p$, $\quad P’ \equiv {C_2}’ \cdot ({e_2}^r)^{-1} \mod p$

5. ElGamal Digital Signature

Key Generation
public key : ${e_1}$, ${e_2}$, $p$
private key : $d$

Signing

Choose $r \in {\mathbb {Z}}_{p}^{*} \quad $ s.t $\quad gcd(r, p - 1) = 1$

$ S_1 \equiv {e_1}^r \mod p$
$ S_2 \equiv (M - dS_1)r^{-1} \mod p-1$
$\Rightarrow S = (S_1, S_2)$ : Signature

Verifying

Check $0 < S_1 < p$ and $0 < S_2 < p-1$

$V_1 \equiv {e_1}^M \mod p$
$V_2 \equiv {e_2}^{S_1} \cdot {S_1}^{S_2} \mod p$

If $V_1 \equiv V_2 \mod p$, then Accept.

$V_2 \equiv {e_2}^{S_1} \cdot {S_1}^{S_2} \equiv ({e_1}^d)^{S_1} \cdot ({e_1}^r)^{S_2} \equiv {e_1}^{dS_1 + rS_2} \equiv {e_1}^M \mod p$

6. Forgery in the ElGamal Signature

(1) choose $u, v \in {Z} \quad$ s.t $\quad gcd(v, p-1) = 1$

$S_1 \equiv {e_1}^u{e_2}^v \mod p$
$S_2 \equiv -S_1V^{-1} \mod p-1$
$M \equiv S_2u \mod p-1$

$\Rightarrow {e_2}^{S_1}{S_1}^{S_2} \equiv {e_2}^{S_1}({e_1}^u{e_2}^v)^{-S_1V^{-1}} \equiv {e_2}^{S_1}{e_2}^{-S_1}{e_1}^{-S_1uv^{-1}} \equiv {e_1}^{uS_2} \equiv {e_1}^M \mod p$

but, $M$ will be meaningless value.

(2) Given $(M, S_1, S_2)$, find $(M’, S_1’, S_2’) \quad$ s.t $\quad {e_2}^{S_1’}{S_1’}^{S_2’} \mod p$

Choose $M’$ and set $u \equiv M’M^{-1} \mod p - 1$ where $gcd(M, p-1) = 1$
Compute $S_2’ \equiv S_2u \mod p - 1$
Find $S_1’$

by CRT

$\Rightarrow (S_1’, S_2’)$ : Signature for $M’$

${e_2}^{S_1’}{S_1’}^{S_2’} \equiv {e_2}^{S_1u}{S_1}^{S_2u} \equiv e_1^{dS_1u}({e_1}^r)^{S_2u} \equiv {e_1}^{(dS_1 + rS_2)u} \equiv {e_1}^{Mu} \equiv {e_1}^{M’} \mod p $

$\Rightarrow S_1’ \geq p$

7. Schnorr Digital Signature

Key Generation
$p$ : prime.
$q$ : prime s.t $q \mid p - 1$

Choose $e_1$, s.t $ord(e_1) = q$ in ${\mathbb {Z}}_{p}^{*}$
Choose $d$

$e_2 \equiv {e_1}^d \mod p$

public key : $e_1$, $e_2$, $p$
private key : $d$

Signing

$r \in {\mathbb {Z}}_{q}^{*}$
$S_1 = h(M||{e_1}^r \mod p)$
$S_2 = r + dS_1 \mod q$

Verifying
Calculate $V=h(M||{e_1}^{S_2}{e_2}^{-S_1} \mod p)$
If $V = S_1$, then $M$ is accepted

${e_1}^{S_2}{e_2}^{-S_1} \equiv {e_1}^{r + dS_1}{e_1}^{-dS_1} \equiv {e_1}^r \mod p$

Share