MATH 470 Lecture 15

« previous | Tuesday, March 5, 2013 | next »

Midterm

Midterm Thursday after Spring Break

Material is anything up to today.

Practice midterm available on web page

Review

• Powering mod $n$ is easy but slow.
• Computing square roots mod prime $p$ is easy-ish
• Computing square roots mod any integer $n$ is hard: in fact, deciding whether $\sqrt{a}\in [1,b]$ is NP-Complete
• Deciding existence of square roots mod $p$ can be done by powering, but is faster via quadratic reciprocity of Jacobi symbols
• Factoring appears hard, but is easy if computing square roots mod $n$ is easy.

El Gamal

• Large prime $p$, with $p-1$ having at least one huge prime factor
• Generator $\alpha$ for ${(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$
• Number $a\in [2,2]$
• $\beta ={\alpha }^a(\mathrm{mod}p)$

$(p,\alpha ,\beta )$ are public, recipient holds $a$ secret.

to transmit a message $m\in {(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$, the sender computes a random $k\in [2,p-2]$, ${\alpha }^k$, and ${\beta }^k$; and then sends $({\alpha }^k,{\beta }^{k}m)(\mathrm{mod}p)$

To decode, the recipient computes $\frac{{\beta }^{k}m}{({\alpha }^k{)}^a}=\frac{\text{2nd}}{\text{1st}}(\mathrm{mod}p)$

Questions:

1. How does this hide $m$? (${\beta }^k$ appears random, and multiplication by it scrambles $m$)
2. why does decryption work? $\frac{{\beta }^{k}m}{({\alpha }^k{)}^a}=\frac{{\beta }^{k}m}{({\alpha }^a{)}^k}=\frac{{\beta }^{k}m}{{\beta }^k}=m(\mathrm{mod}p)$

Crypytanalysis

Most obvious: find $a$.

Finding $a$ involves solving ${\alpha }^a\equiv \beta (\mathrm{mod}p)$ for $a$. This involves solving the discrete log problem, which is appears to be hard

Example

• $p=1009$
• $\alpha =101$ (i.e. $\{{\alpha }^1,\dots ,{\alpha }^{1008}\}=\{1,\dots ,1008\}$)
• $m=559$
• pick $k=291$ at random and transmit $({\alpha }^k,{\beta }^{k}m)=(421,661)$

Pohlig-Hellman

Recall:

• If $\beta$ is a square mod $p$, then $\left(\frac{\beta }{p}\right)\equiv {\beta }^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$.
• If $\beta$ is a non-square mod $p$, then $\left(\frac{\beta }{p}\right)\equiv {\beta }^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$.

So if $\beta ={\alpha }^a$, we see that

• when $a$ is even, then ${\beta }^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$
• when $a$ is odd, then ${\beta }^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$

That is, you can tell the parity of $a$ (the last base-2 digit).

Example

$p=211$, $\alpha =2$, $a=?$, and $\beta =5$

Notice that $p-1=210=2\cdot 3\cdot 5\cdot 7$. This would be a bad choice.

Note: Fermat primes are of the form $2^n+1$

We want to find $a$ with $2^a\equiv 5(\mathrm{mod}211)$. Is $a$ odd or even? (check Legendre symbol)

$5^{\frac{p-1}{2}}\equiv 5^{105}\equiv 1(\mathrm{mod}211)$

So $a$ is even and $a\equiv 0(\mathrm{mod}2)$.

Now we want to find $a(\mathrm{mod}3)$

$5^{\frac{p-1}{3}}\equiv 5^{70}\equiv 2^{\left(\frac{p-1}{2}\right)a_0}$

Where $a_0\in [0,2]$ is the last digit mod 3.

We find $5^{7}0\equiv 1\equiv (2^{70}{)}^{a_0}\equiv (-15{)}^{a_0}$, so $a_0$ must be 0.

So $a\equiv 0(\mathrm{mod}3)$

Now we want to find $a(\mathrm{mod}5)$

$5^{\frac{p-1}{5}}\equiv ({\alpha }^a{)}^{\frac{p-1}{5}}\equiv ({\alpha }^{\frac{p-1}{5}}{)}_0^a\equiv 2^{\left(\frac{p-1}{5}\right)a_0}$

$a_0\in [0,4]$, and by brute force, $a_0=2$.

So $a\equiv 2(\mathrm{mod}5)$

Yada yada, $a\equiv 6(\mathrm{mod}7)$

The Chinese Remainder Theorem states that we have a unique $a$ such that it is equivalent to (0,0,2,6) mod (2,3,5,7), respectively.

• Combine $a\equiv 0(\mathrm{mod}2)$ and $a\equiv 0(\mathrm{mod}3)$ to get $a\equiv 0(\mathrm{mod}6)$
• Combine that with $a\equiv 6(\mathrm{mod}7)$ to get $a\equiv 6(\mathrm{mod}42)$
• Combine that with $a\equiv 2(\mathrm{mod}5)$ to get $a\equiv 132(\mathrm{mod}211)$.

And indeed, $a=132$, and $2^{132}\equiv 5(\mathrm{mod}211)$

Note: Pohlig Hellman also handles base $q^k$