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


8 Responses to “El Gamal examples”

  1. Anonymous Says:

    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

  2. chakravarthy Says:

    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
    S.V.Arts College
    andhra pradesh

  3. NotAMathGenius Says:

    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!

  4. xxx Says:

    how we got (62)^-1=63..??

  5. Bert Helpt Says:

    that my question too. That is mystery, I told my students to use p-1-n

  6. jonkatz Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: