decrypt elgamal encrypted message

Question

I have this exercise and I'm stuck on the last question (I'm translating it from French so excuse me if I use incorrect terms) :

Lets assume an El Gamal cryptosystem. Alice choose $p = 11$ and $g = 3$. She also choose $ a = 4 \\$

1. What is Alice public key : $(11, 3, 3^4)$

2. Bob wants to send Alice the message $m = 2$, he choose $b = 5$. What is the encrypted message ? : $(3^5, 2 \times 3^{4 \times 5}) $

3. How does Alice decrypts the message ? Retrieve the original message

i'm stuck at question 3

i know i must find $(g^b)^a$ inverse which is $ g^{-ab}$. Which i can calculate by raising $g^b$ to the power $a(p-2)$

because
$\forall y \in \mathbb{Z/pZ} \neq 0, y^{p-1} = 1$ then $\\ y^{-1} = y^{p-2} $ in $\mathbb{Z/pZ}$

Then all i have to do is multiply $g^{-ab} \times mg^{ab}$ to find m but I'm ending with too high numbers.

Am I calculating the inverse wrong or is my mistake somewhere else? If somebody could pinpoint it I'd be glad

Answer 1

Alice has the public key $(11,3,3^4)$, so her secret key is $4$ and $3^4 = 81$ must be reduced modulo $11$ as we are working in $\mathbb{Z}/11\mathbb{Z}$ and $81 = 4$ modulo $11$. So the PK is $(11, 3, 4)$ really. That her public key contains her secret key $4$ is happenstance.

Bob wants to send $m=2$ and chooses his blinding number $b=5$. So he sends the DH contribution $3^5$ (modulo $11$, of course), so this is $3^5 \pmod{11} = 1$, and we see that $3$ is not even a generator of $(\mathbb{Z}/11\mathbb{Z})^\ast$: the powers of $3$ are $3,9,5,4,1$ (cyclically) and not all non-zero values of $\mathbb{Z}/11\mathbb{Z}$ are reached.... Too bad, een though it's a toy example, a more realistic value would have been nicer, IMHO. So $m$ is multiplied by $4^5$ modulo $11$ ($4$ as it is Alice PK value, and $5$ as the blinding number. $4^2 = 16 = 5$ modulo $11$ so $4^5 = 5 \cdot 5 \cdot 4$ modulo $11$, so $4^5 \equiv 1 \pmod{11}$, so Bob sends $(g^b, m\cdot (g^a)^b) \pmod{11} = (1,2)$. Again with these small numbers we happen to have that $3^5 = 4^5$ modulo $11$, making this extra trivial.

Alice gets $(1,2)$ and also computes the DH value $(g^a)^b$ as $(g^b)^a = 1^a = 1$ and divides $2$ by $1$ modulo $11$ (pretty boring again) to get $m=2$.

You can also compute $(g^{-a})^b$, if you already precomputed $g^{-a}$ modulo $p$. In this case $g^a$ is $4$ which has inverse $3$ ($4 \times 3 = 12 \equiv 1$ modulo $11$) so you can indeed compute $4^5 = 1$ as the required multiplier (to divide $m (g^{a})^b$ by $(g^a)^b$). You should realise that here everything takes place modulo the prime $11$ so we get no large numbers at all. It's even easier because of the fact that $3$ is not even a generator, $2$ would have been a better choice, its powers modulo $11$ are $2,4,8,5,10,9,7,3,6,1$, which does assume all values $1 \le x \le 10$.