How to Decrypt a Message Using ElGamal Encryption?

[ploppers]

Homework Statement

Suppose someone uses ElGamal to encrypt a message. You know
that the public key is p = 29, g = 18, and a = 14. The message was translated
from letters into numbers by the system A $ 2, B $ 3, ..., Z $ 27. If the
encrypted message was
M1 = 17 M2 = 14; 11; 9; 24; 23; 24; 11;
then what was the original message?

Homework Equations

N/a (please read below)

The Attempt at a Solution

I understand how to do this question actually if I was given the unknown k value. Does this question expect us to break the code and find the unknown k value...? Because this could take a very long time considering that's what the encryption methods are designed to do...

 

[mighty2000]

Hello,

Thank you for your question. No, this question does not require you to break the code and find the unknown k value. The purpose of this question is to test your understanding of the ElGamal encryption method and its components.

To solve this problem, you will need to use the formula for decryption in ElGamal encryption:

M = (M1 / (M2^a)) mod p

In this case, M1 = 17 and M2 = 14; 11; 9; 24; 23; 24; 11. Plugging these values into the formula, we get:

M = (17 / (14^14)) mod 29
M = (17 / (27^14)) mod 29

Now, we need to find the inverse of 14 and 27 mod 29. Using the Extended Euclidean Algorithm, we get that the inverse of 14 is 25 and the inverse of 27 is 4.

Substituting these values into our formula, we get:

M = (17 * 25^14) mod 29
M = (17 * 4^14) mod 29
M = (17 * 18^14) mod 29
M = (17 * 18^2)^7 mod 29
M = (17 * 324)^7 mod 29
M = (17 * 16)^7 mod 29
M = 272^7 mod 29
M = 17 mod 29

Therefore, the original message was "A" as it corresponds to the number 1 in the system A $ 2, B $ 3, ..., Z $ 27.

I hope this helps clarify the question for you. Let me know if you have any further questions. Good luck!