0

I'm just looking for a bit of clarification on a question I've found on ElGamal:

You want to let people send you messages using ElGamal. You begin by choosing $p =101, g =2$ and $a =12.$
(a) Calculate your public key and then decrypt Bob's message $(B = 54, C = 13)$

I think I've calculated the key but I'm unsure:

$$ d=g^a(mod\space p) $$ $$ d=2^{12}(mod\space 101) $$ $$ d=56 $$ public key = $$(101, 2, 56) $$

If anyone can clarify if this is correct or how I can rectify this. Thanks

Lauren Burke
  • 405
  • You are quoting "a question I've found", but in taking this exercise out of context, many (perhaps most) Readers will find the reference to "ElGamal" cryptic. Please explain its meaning or at least link to a source that explains the algorithm. – hardmath Mar 08 '17 at 13:35
  • @Moo Thank you for responding! In order to decrypt Bob's message which number do I use as my private key? – Lauren Burke Mar 08 '17 at 13:58
  • 1
    Thank you very much, thats exactly what I was looking for. – Lauren Burke Mar 08 '17 at 14:04

1 Answers1

0

So Alice's public key (her private one is $12$) is $g^{12} = 2^{12} \pmod{101} = 56$, including the $p$ and $g$, which are implicit. If Bob then sends $(54, 13)$ you first compute the DH shared secret $54^{12} \pmod{101} = 19$ and the message is then $13 \cdot 19^{-1}$ (inverse and multiplication mod 101), which is $13 \cdot 16 = 6 \pmod{101}$.

You can do the computations online (wolframalpha.com) or on the commandline using Python (e.g.), which I did. Or by hand if you're patient.

Henno Brandsma
  • 242,131