encrypt the message P=111 and k=3 using the ElGamal cryptosystem with the public key (p,r,b)=(2551,6,33). Show how the resulting ciphertext can be decrypted using the private key a=13.
Encryption:
Compute r^k mod p
= 6^3 = 216 mod 2551
and Pb^k mod p
= 111 * 33^3 = 1794 mod 2551
So, the cyphertext is the pair (216, 1794).
Decryption:
1794 / (216^13) mod 2551
= 1794 / 223 mod 2551
By Euclid's Algorithm,
2551 = 11* 223 + 98 ==> 2551 - 11* 223 = 98
223 = 2 * 98 + 27 ==> 223 - 2 * 98 = 27
98 = 3 * 27 + 17 ==> 98 - 3 * 27 = 17
27 = 1 * 17 + 10 ==> 27 -17 = 10
17 = 1 * 10 + 7 ==> 17 -10 = 7
10 = 1 * 7 + 3 ==> 10 - 7 = 3
7 = 2 * 3 + 1.
Back-substituting yields
66 * 2551 - 755* 223 = 1.
So, 1/223 = -755 = 1796 mod 2551
Finally,
1794 / 223 mod 2551
= 1794 * 1796 mod 2551
= 111 mod 2551, which is the original message.
Comments
Encryption:
Compute r^k mod p
= 6^3 = 216 mod 2551
and Pb^k mod p
= 111 * 33^3 = 1794 mod 2551
So, the cyphertext is the pair (216, 1794).
Decryption:
1794 / (216^13) mod 2551
= 1794 / 223 mod 2551
By Euclid's Algorithm,
2551 = 11* 223 + 98 ==> 2551 - 11* 223 = 98
223 = 2 * 98 + 27 ==> 223 - 2 * 98 = 27
98 = 3 * 27 + 17 ==> 98 - 3 * 27 = 17
27 = 1 * 17 + 10 ==> 27 -17 = 10
17 = 1 * 10 + 7 ==> 17 -10 = 7
10 = 1 * 7 + 3 ==> 10 - 7 = 3
7 = 2 * 3 + 1.
Back-substituting yields
66 * 2551 - 755* 223 = 1.
So, 1/223 = -755 = 1796 mod 2551
Finally,
1794 / 223 mod 2551
= 1794 * 1796 mod 2551
= 111 mod 2551, which is the original message.