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)$

$\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

  • $\begingroup$ I haven't looked at this particularly close, and I hope I'm interpreting your difficulty correctly: Remember that you can reduce everything $\pmod{81}$ as you go. This prevents you from having to work with very large numbers. $\endgroup$ – Kaj Hansen Jun 19 '18 at 21:02
  • $\begingroup$ @KajHansen even modulo $11$.. $\endgroup$ – Henno Brandsma Jun 19 '18 at 22:11
  • $\begingroup$ Oops, yeah. Mod 11. $\endgroup$ – Kaj Hansen Jun 19 '18 at 22:21

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.