# Role of Fermat's little theorem in the proof of correctness of ElGamal signature

In the Wikipedia article about the ElGamal signature scheme it is written, that Fermat's little theorem is used in the following proof of correctness:

From the signature generation in ElGamal we can derive, that:

$$H(m) \equiv xr + sk \pmod {p-1}$$

Then - the article states - Fermat's little theorem implies the following:

\begin{align} g^{H(m)} &\equiv g^{xr}g^{ks} &\pmod p\\ &\equiv (g^x)^r(g^k)^s &\pmod p\\ &\equiv (y)^r(r)^s &\pmod p \end{align}

The proof makes sense to me, i am just wondering, in what way Fermat's little theorem is used here, instead of just regular properties of exponentiation.

• Hint: apply the definition of $H(m)\equiv xr+sk\pmod{p-1}$ so that you remove the modulo. You should then see how establishing $g^{H(m)}\equiv g^{xr}g^{ks}\pmod p$ involves Fermat's little theorem. – fgrieu Jan 24 '16 at 20:24

## 2 Answers

Thanks to fgrieu's comment above and the following quote from here (PDF):

Theorem:

Let $p$ be a prime and let $a$ be a number not divisible by $p$. Then if $$r \equiv s \pmod {p − 1}$$ we have $$a^r \equiv a^s \pmod p$$ In brief, when we work $\mod p$, exponents can be taken $\mod{p − 1}$.

I (think i) understood, how the first (implicit) step relies on Fermat's little theorem: \begin{align} g^{H(m) \pmod{p-1}} &= g^{xr+sk \pmod{p-1}} \\ g^{H(m)} &\equiv g^{xr+sk} \pmod p \end{align}

For $c\ne0$, the definition of $a\equiv b\pmod c$ is: $\exists d\in\mathbb Z$ such that $a=b+cd$.

Applying that definition to $H(m)\equiv xr+sk\pmod{p-1}$, we have that $\exists d\in\mathbb Z$ such that $H(m)=xr+sk+(p-1)d\;\text{ (equ. 1)}$.

Fermat's little theorem is that for $p$ prime and $g\not\equiv0\pmod p$, it holds that $g^{p-1}\equiv1\pmod p\;\text{ (equ. 2)}$.

We can now compute \begin{align} g^{H(m)} &\equiv g^{xr+sk+(p-1)d}&\pmod p&&\text{ (by equ. 1)}\\ &\equiv {(g^x)}^r\;{(g^k)}^s\;(g^{p-1})^d&\pmod p&&\text{ (rearanging)}\\ &\equiv {(g^x)}^r\;{(g^k)}^s\;1^d&\pmod p&&\text{ (by equ. 2)}\\ &\equiv {(g^x)}^r\;{(g^k)}^s&\pmod p&&\text{ (simplifying)}\\ &\equiv y^r\;r^s&\pmod p&&\text{ (by definition of }y\text{ and }r\text{)} \end{align}