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 by typing ‘bc’ at the unix command line and then typing .

Say the receiver chooses prime , and (one can check that 33 is a generator of ), and secret exponent . Then . (I won’t explicitly write the “” anymore.) The receiver would publish the public key .

Say a sender wants to send the message . It chooses random exponent , say, computes the ciphertext , and sends this to the receiver.

To decrypt the ciphertext , the receiver needs to compute . Recall that dividing by 62 modulo 71 really means to multiply by . We did not discuss how to compute multiplicative inverses in class, but one can verify that because . Thus, the receiver will compute . Of course, this was exactly the message sent by the sender!

Now a partial example. Let’s take and . (One can check that 2 is a generator of .) Say the receiver chooses secret exponent . What would the receiver’s public key be?

Now say a sender wants to send the message using random exponent . 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:** .)

### Like this:

Like Loading...

*Related*

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.

October 2, 2009 at 3:15 pm |

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

October 11, 2016 at 7:23 pm |

can you send me the solution for p=13 and g=2 and k^u base a =7 and what is private key

October 10, 2011 at 5:29 am |

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

January 22, 2012 at 11:19 am |

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!

January 22, 2012 at 3:18 pm |

What exactly is your question…?

April 26, 2013 at 11:51 am |

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

December 15, 2013 at 1:47 pm |

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

December 15, 2013 at 9:20 pm |

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.