MATH 470 Lecture 16

« previous | Thursday, March 7, 2013 | next »

Pohlig-Hellman

Recall:

• The security of RSA is based on the (apparent) hardness of integer factoring.
• The security of El Gamal is based on the (apparent) hardness of discrete logarithms.

For El Gamal, you should really only use 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 p} with $p-1$ having at least 1 large factor. Otherwise, you can easily break El Gamal easily via the Pohlig-Hellman method:

input: prime $p$, $\alpha ,\beta \in (\mathbb {Z} /p\mathbb {Z} )^{*}$ such that $\beta =\alpha ^{a}{\pmod {p}}$

output: $a$

1. factor $p-1$ as $2^{r_{1}}\cdot 3^{r_{2}}\dots p_{n}^{r_{n}}$
2. find an $a_{i}$ with $a\equiv a_{i}{\pmod {p_{i}^{r_{i}}}}$ for all $i\in [1,n]$
3. Recover $a$ from $a_{1},\ldots ,a_{n}$ via the Chinese Remainder Theorem.

Main trick to (2) is to expand $a$ in base $p_{i}$: ${\begin{aligned}a&=d_{0}+d_{1}\,p_{i}+d_{2}\,p_{i}^{2}+\dots +d_{n}\,p_{i}^{n}&=\left(\alpha ^{d_{0}}\right)\,\left(\alpha ^{d_{1}}\right)^{p_{i}}\dots \left(\alpha ^{d_{n}}\right)^{p_{i}^{n}}\end{aligned}}$

Example

Last time, we used a prime with $p-1$ having many small primes and no power greater than 1.

This time, we'll use a prime with $p-1$ having only one prime and a large power:

p = 65537 R = Integers(p) alpha = R(3) beta = R(2) factor(p-1) # => 2^16




1. 1. FIND d0 ##

1. beta^((p-1)/2) == (alpha^a)^((p-1)/2)

beta^((p-1)/2) # => 1

1. (alpha^a)^((p-1)/2) == (3^d0)^((p-1)/2) * (3^(2*d1))^((p-1)/2) * ...
2. == (3^((p-1)/2))^d0 * (3^(p-1))^d1 * ...
3. == 3^(d0*(p-1)/2) * 1 * 1 * ...

3^((p-1)/2) # => -1

1. d0 == 0 since (-1)^d0 == 1

d0 = 0

1. 1. FIND d1 ##

1. beta = (alpha^d0) * (alpha^d1)^2 * ... * (alpha^d15)^(2^15)
2. therefore beta/alpha^d0 == (alpha^d1)^2 * ... * (alpha^d15)^(2^15)

beta/alpha^d0 # => 2

1. raise both sides to the (p-1)/2^2 th power
2. 2^((p-1)/2^2) == alpha^(2*d1*(p-1)/2^2) * alpha^(2^2*d1*(p-1)/2^2) * ... * alpha^(2^15*d15*(p-1)/2^2)
3. == (alpha^((p-1)/2))^d1 * 1 * 1 * ... * 1

R(2)^((p-1)/2^2) # => 1 alpha^((p-1)/2) # => -1

1. d1 == 0 since (-1)^d0 == 1

d1 = 0

1. 1. FIND d2 ##

1. beta/alpha^(d0+2*d1) == alpha^(d2*2^2) * alpha^(d15*2^15)

beta/alpha^(d0+2*d1) # => 2

1. raise to (p-1)/2^3 power
2. 2^((p-1)/2^3) == alpha^(4*d2*(p-1)/2^3) * 1 * ... * 1

R(2)^((p-1)/2^3) # => 1 alpha^(4*(p-1)/2^3) #=> -1

1. d2 == 0 since (-1)^d2 == 1

d2 = 0

1. 1. CONTINUE IN SAME WAY ##
2. . . .
3. a = 55296

Proof Example

Prove Fermat's Little Theorem.

Proposition. Given any $a\in \mathbb {Z}$ and prime $p$, then $a^{p-1}\equiv 1{\pmod {p}}$.

Proof. Consider the numbers $a$, $2a$, …, $(p-1)\,a$. They are distinct mod $p$ since

${\begin{aligned}i\,a&\equiv j\,a{\pmod {p}}\\(i-j)\,a&\equiv 0{\pmod {p}}\\i-j&\equiv 0{\pmod {p}}\\i&\equiv j{\pmod {p}}\end{aligned}}$

We can divide by $a$ in step 3 since $\mathrm {GCD} (a,p)=1$.

So then $\{a,2a,3a,\ldots ,(p-1)a\}=\{1,\ldots ,p-1\}$

If we multiply all elements of these sets, we get

${\begin{aligned}a^{p-1}\,(p-1)!&=(p-1)!{\pmod {p}}\\a^{p-1}&=1{\pmod {p}}\end{aligned}}$

Q.E.D.

Non-Computational Example

Find $k$ such that computing the exact power of 3 dividing $n$ is doable in time $O(\log ^{k}(N))$

Hint: You may assume that multiplying or dividing two numbers no bigger than $n$ takes time $O(\log ^{2}{n})$

Solution: Use binary search

Check if $N$ is divisible by 3, 3², 3⁴, etc.

At a certain point, we get $3^{2^{j}}\mid n$, but $3^{2^{j+1}}\nmid n$. Note $3^{2^{j}}\leq n$, so

${\begin{aligned}3^{2^{j}}&=n\\2^{j}&=\log _{3}{n}\\j&=\log _{2}{(\log _{3}{n})}\end{aligned}}$

So checks take $O((\log {\log {n}})\,(\log ^{2}{n}))$.

Suppose $n=645,700,815$. $3^{2^{4}}\mid n$, but $2^{4}$ is not the highest power dividing $n$.

Replace $n$ by $n'={\frac {n}{3^{2^{j}}}}$

Example: 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 n' = \frac{n}{3^{2^4}} = 15}

Note 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 n' \le \frac{n}{3}} since 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 3^{2^{j+1}} \nmid n} . Now proceed recursively:

This takes at most 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 \log_3{n}} binary searches, and since each binary search takes 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 O((\log{\log{n}})\,(\log^2{n}))} time, the total work 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 O((\log{\log{n}})\,(\log^3{n}))}

Now 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 k = 3 + \epsilon} for any 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 \epsilon > 0} since we have that 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 \log{\log{n}}} factor.

Moral

Factoring 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 n} may take exponential time (in 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 \log{n}} ), but computing the 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 j} 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 n = p^j \, m} for 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 p \nmid m} is doable in polynomial time (in 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 \log{n}} ).