El Gamal examples

I will give one worked out example, followed by a partial one. As in class, this example is not entirely accurate and you should not rely on it to implement El Gamal encryption for real.

Note that you can easily perform modular arithmetic (on “small” values) using the ‘bc’ command on unix. E.g., you can compute $5^2 \bmod 24$ by typing ‘bc’ at the unix command line and then typing $\verb+5^2 % 24+$ .

Say the receiver chooses prime $p = 71$ , and $g=33$ (one can check that 33 is a generator of ${\mathbb Z}_{71}^*$ ), and secret exponent $x=62$ . Then $h = g^x \bmod 71 = 10$ . (I won’t explicitly write the “ $\bmod 71$ ” anymore.) The receiver would publish the public key $(p=71, g=33, h=10)$ .

Say a sender wants to send the message $m=15$ . It chooses random exponent $r=31$ , say, computes the ciphertext $(g^r, h^rm) = (62, 18)$ , and sends this to the receiver.

To decrypt the ciphertext $(62, 18)$ , the receiver needs to compute $18/62^x = 18/62^{62}$ . Recall that dividing by 62 modulo 71 really means to multiply by $62^{-1} \bmod 71$ . We did not discuss how to compute multiplicative inverses in class, but one can verify that $62^{-1} = 63 \bmod 71$ because $62 \cdot 63 = 1 \bmod 71$ . Thus, the receiver will compute $18 \cdot (62^{-1})^{62} = 18 \cdot 63^{62} \bmod 71 = 15$ . Of course, this was exactly the message sent by the sender!

Now a partial example. Let’s take $p=107$ and $g = 2$ . (One can check that 2 is a generator of ${\mathbb Z}_{107}^*$ .) Say the receiver chooses secret exponent $x=29$ . What would the receiver’s public key be?

Now say a sender wants to send the message $m=100$ using random exponent $r=19$ . What would be the ciphertext computed by the sender?

Finally, verify that decryption successfully recovers the message. (You may have difficulty finding the correct multiplicative inverse. Hint: $2^{-1} = 54 \bmod 107$ .)

This entry was posted on September 23, 2009 at 8:04 pm and is filed under other. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

9 Responses to “El Gamal examples”

Anonymous Says:
October 2, 2009 at 3:15 pm | Reply
p = 107, g = 2, x = 29
h = g^x mod p = 2^(29) mod 107 = 17
— public key = (p,g,h) = (107,2,17)

m = 100, r = 19
— c = (g^r , (h^r)*m) mod p = (95,15)

c = (95,15)
— m = (15*(95^-1)^29) = (15 * (-9)^29) = 15 * 78 mod 107 = 100
- raj Says:
  October 11, 2016 at 7:23 pm | Reply
  can you send me the solution for p=13 and g=2 and k^u base a =7 and what is private key
chakravarthy Says:
October 10, 2011 at 5:29 am | Reply
Consider the Largest Prime say P, and find the primitive root for Prime P. Let the primitive root is g. Choose an random number say x (Secret key), x lies between 1 to p-2. Announce public key as(p,g,e). sender’s receive the public keys and send the cipher message as c1, c2 and decrypt the cipher message with the your secret key x.
Eg:- p = 11 and g = 2. and x = 3 e =g^x mod p= 2^3 mod 11= 8. So the public keys are (2, 8, 11) and the private(secret) key is 3. Sender receives the public keys (2,8,11) chooses random value r = 4 and calculates C1 and C2 for the plaintext(m= 7).
C1=g^r mod p = 2^4 mod 11 =16 mod 11 =5
C2=m*(e^r) mod p =7*(8^4) mod 11 = 7*4096 mod 11=28672=6
sender sends (c1,c2) as (5,6)
m=C2*(C1^-1/x)) mod p=6*(5^-1/3) mod 11= 6*5^(11-1-3) mod 11= 6*5^7 mod 11=6*78125 mod 11=468750 mod 11=7 =m(plain text)

note : please do it manually so you can understand
chakravarthy
S.V.Arts College
Tirupati
andhra pradesh
India
NotAMathGenius Says:
January 22, 2012 at 11:19 am | Reply
both of your Calculations work, but only with the numbers you took. If you take any different number in x, r, p or any of the other not calculable variables you calculations don’t make sense anymore… I’m sorry!
- jonkatz Says:
  January 22, 2012 at 3:18 pm | Reply
  What exactly is your question…?
xxx Says:
April 26, 2013 at 11:51 am | Reply
how we got (62)^-1=63..??
Bert Helpt Says:
December 15, 2013 at 1:47 pm | Reply
that my question too. That is mystery, I told my students to use p-1-n
jonkatz Says:
December 15, 2013 at 9:20 pm | Reply
There are (at least) two ways to compute modular inverses:
– In general, one can always compute a^{-1} mod b using the extended Euclidean algorithm. The details are in my book “Introduction to Modern Cryptography.”

– In this specific case, we know that the order of the group Z^*_{71} is 70 (because 71 is prime). Since a^{70} = 1 mod 71 for any a \in Z^*_{71}, we have that a^{-1} = a^{69} mod 71 for any a.
Abdi aziz hussein Says:
November 28, 2019 at 2:31 am | Reply
I want to encrypt and decrypt 32 words using Elgamal algorithm In matlab

CMSC414: Computer/Network Security