ElGamal is another public key encryption idea. It is different from the RSA encryption scheme in that its security depends on the difficulty depends on the difficulty of the discrete log problem, as opposed to the factoring problem.
Ben sends message to Anne as follows:
Anne decrypts as follows:
Pick , . Pick , so that . Anne's public key is . Anne's private key is . Suppose Ben is Anne's son and wants to send the message ``Hi Mom''. He converts this to and . Ben picks and computes , so . The encryption is and , so and are sent to Anne.
Anne computes . Then returns the original messages and . Since has an odd number of digits, the first digit must have been a 0 . Anne can see that must mean that the first letter comes from the , the second letter comes from a . These spell out ``hi''. For , the third letter must come from the , the fourth letter must come from the , and the last must be a . These spell out ``hi'' and ``mom''. Adding a space and proper capitalization, this is ``Hi Mom''!
More details are given in [MOV], §8.4.
(a) Let , , . Decrypt the ElGamal ciphers and .
(a) the order of mod ,
(b) the order of mod ,
(c) the order of mod ,
(d) the order of mod .