Don't like this style? Click here to change it! blue.css

# MATH NOTES

## Topic 1: Pohlig-Hellman

You have this problem to solve, given $$g, h, p$$ find the unknown $$x$$ such that $$g^x = h$$ mod $$p$$.

We know, thanks to Fermat's little Theorem, that $$m^{p-1} = 1$$ mod $$p$$ for any integer $$m$$.

So we're interested in reducing the search space for $$x$$ from $$1, \cdots, p-2$$ to something much smaller.

The idea is that we can actually figure out $$x$$ mod $$m$$ for any $$m$$ that divides $$p-1$$

When I go concrete I'll use $$p=31$$ in the following to match the notes.

To show how that works let's play with $$x$$ mod $$3$$. Every integer can be written down as $$3k, 3k+1,$$ or $$3k + 2$$ for an arbitrary integer $$k$$. This comes from when we looked at modular arithmetic as infinite sets, like $$3 \cdot \mathbb{Z} + 1$$ as this big infinite set of all things that are 1 larger than a multiple of 3.

We don't know which of those 3 worlds $$x$$ lives in but we could say that $$x = 3k + y$$ where $$y$$ is either 0, 1, or 2.

At this point maybe it seems a tad abstract but if we can change this problem from hunting for $$x$$ inside the range $$1, \cdots, p-2$$ to hunting for $$y$$ in the range $$0,1,2$$ we've certainly made a smaller problem.

OK NOW we're ready to play with the original equation: $$g^x = h$$

Let's replace $$x$$ with $$3k + y$$:

$$g^{3k + y} = h$$

We know that $$g^{p-1} = 1$$. Now if 3 happens to divide $$p-1$$ like in the $$p=31$$ case then we have a trick we can use:

In our $$p=31$$ case Fermat's little theorem gives $$g^{30} = 1$$. So the big idea is that we can raise both sides of the main equation to the 10th power.

Watch what happens

$$g^{10 \cdot (3k + y)} = h^{10}$$

Playing with the left hand side we get:

$$g ^{10 \cdot (3k + y)} = g^{30k + 10y} = g^{30k} \cdot g^{10y} = (g^{30})^{k} \cdot g^{10y} = (1)^{k} \cdot g^{10y} = g^{10y}$$

So that means $$g^{10y} = h^{10}$$

Did we make progress?

Well now we have a simple search to do, look at $$g^0, g^{10}, g^{20}$$ and compare those 3 values with $$h^{10}$$ (all of this is mod 31)

So we calculate $$h^{10}$$ and compare it with the three possible values of $$y$$ and we KNOW that one of them will match up. Let's say when $$y=1$$ for some specific value of $$h$$ then it must be that $$g^{10} == h^{10}$$ which would imply that $$x = 3k + 1$$ for some value of $$k$$. Now we know that the final answer will be 1 mod 3.

You can imagine that we could repeat this process for other factors of $$p-1$$. When $$p=31$$ that would mean 2, 3, 5.

But could the trick work for other moduli?

Like, no one is stopping us from writing down $$x = 7k + y$$. So plug it in to the original equation: $$g^x = h$$ We get $$g^{7k + y} = h$$ But since 7 doesn't divide 30 we don't have some nice way to get rid of needing to find the $$k$$ AND find the $$y$$. Raising both sides to any power is never going to reduce my search space.

That is the heart of Pohlig-Hellman, for numbers $$m$$ that divide $$p-1$$ we can change the search space from $$m \cdot k + y$$, (where $$y = x$$ mod $$m$$ ), to ignoring needing the $$k$$ and only needing to find $$y$$ which is ALOT less work.

After all of that use Chinese Remainder Theorem to finish the problem.

## Topic 2: RSA Math

So we know that $$g^{p-1} = 1$$ mod $$p$$ for any non-zero integer $$g$$ and any prime $$p$$.

The next more general version of that is Euler's Theorem which says that for any modulus $$N$$ (not necessarily prime) we have:

$$g^{\phi(N)} = 1$$ mod $$N$$

DETAILED ASIDE: We actually know where this comes from, which is the size of the group made by non-zero integers mod $$N$$ mixed with LaGrange's theorem (from our math week ages ago). It comes from the fact that any number with GCD 1 with $$N$$ has a modular inverse and the rest don't. BUT we can ignore the origins and trust the theorem.

OK, Back to the narrative: $$g^{\phi(N)} = 1$$ mod $$N$$

So my next question is, what is $$g^{\phi(N) + 1}$$ mod $$N$$ ???

Well $$g^{\phi(N) + 1} = g^{\phi(N)} \cdot g = 1 \cdot g = g$$.

How about this one then: what is $$g^{2 \cdot \phi(N) + 1}$$???

OK let's play some more: $$g^{2 \cdot \phi(N) + 1} = (g^{\phi(N)})^{2} \cdot g = (1)^{2} \cdot g = 1 \cdot g = g$$.

If you follow, you're probably easy to convince now that $$g^{k \cdot \phi(N) + 1} = g$$ mod $$N$$ for any integer value of $$k$$.

THAT is the big idea behind RSA.

Take your plaintext message PT and convert it to an integer (as we've done many times) and call it $$m$$ (for message).

Then take a large modulus $$N$$ which is the product of two large primes $$p$$ and $$q$$.

Now publish $$N$$ and a public exponent $$e$$ (usually 65537). The cipher text $$c$$ is $$m^e$$ mod $$N$$.

The big idea is that if someone knows $$\phi(N)$$ which happens to be $$(p-1)(q-1)$$ they can calculate the modular inverse of $$e$$ mod $$\phi(N)$$ to get some $$d$$ such that $$d \cdot e = k \cdot \phi(N) + 1$$ for some integer $$k$$.

Now that means that $$m ^{d \cdot e} = m ^ {k \cdot \phi(N) + 1} = (m^{\phi(N)})^{k} \cdot m^{1} = (1)^k \cdot m = m$$.

So to decrypt $$c = m^e$$ we just take it to the $$d$$, the modular inverse of $$e$$ modulo $$\phi(N)$$. Thus $$c^d = m$$ mod $$N$$ and finding $$d$$ takes knowing $$phi(N)$$ which takes knowing how $$N$$ factors into $$N = p \cdot q$$. Since factoring giant numbers is expensive things are "safe".