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 $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$
• Number $a\in [2,2]$
• $\beta =\alpha ^{a}{\pmod {p}}$

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

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

To decode, the recipient computes ${\frac {\beta ^{k}\,m}{(\alpha ^{k})^{a}}}={\frac {\text{2nd}}{\text{1st}}}{\pmod {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{\pmod {p}}$

Crypytanalysis

Most obvious: find $a$.

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

Example

• $p=1009$
• $\alpha =101$ (i.e. $\left\{\alpha ^{1},\ldots ,\alpha ^{1008}\right\}=\left\{1,\ldots ,1008\right\}$)
• $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({\tfrac {\beta }{p}}\right)\equiv \beta ^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$.
• If $\beta$ is a non-square mod $p$, then $\left({\tfrac {\beta }{p}}\right)\equiv \beta ^{\frac {p-1}{2}}\equiv -1{\pmod {p}}$.

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

• when $a$ is even, then $\beta ^{\frac {p-1}{2}}\equiv 1{\pmod {p}}$
• when $a$ is odd, then $\beta ^{\frac {p-1}{2}}\equiv -1{\pmod {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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^a \equiv 5 \pmod{211}} . Is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} odd or even? (check Legendre symbol)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5^{\frac{p-1}{2}} \equiv 5^{105} \equiv 1 \pmod{211}}

So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} is even and $a\equiv 0{\pmod {2}}$.

Now we want to find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \pmod{3}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5^{\frac{p-1}{3}} \equiv 5^{70} \equiv 2^{\left( \frac{p-1}{2} \right) \, a_0}}

Where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_0 \in [0,2]} is the last digit mod 3.

We find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5^70 \equiv 1 \equiv (2^{70})^{a_0} \equiv (-15)^{a_0}} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_0} must be 0.

So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 0 \pmod{3}}

Now we want to find Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \pmod{5}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5^{\frac{p-1}{5}} \equiv (\alpha^a)^{\frac{p-1}{5}} \equiv (\alpha^{\frac{p-1}{5}})^a_0 \equiv 2^{\left(\frac{p-1}{5} \right) \, a_0 }}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_0 \in [0,4]} , and by brute force, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_0 = 2} .

So Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 2 \pmod{5}}

Yada yada, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 6 \pmod{7}}

The Chinese Remainder Theorem states that we have a unique Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} such that it is equivalent to (0,0,2,6) mod (2,3,5,7), respectively.

• Combine Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 0 \pmod{2}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 0 \pmod{3}} to get Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 0 \pmod{6}}
• Combine that with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 6 \pmod{7}} to get Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 6 \pmod{42}}
• Combine that with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 2 \pmod{5}} to get Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a \equiv 132 \pmod{211}} .

And indeed, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = 132} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{132} \equiv 5 \pmod{211}}

Note: Pohlig Hellman also handles base Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^k}