ElGamal algorithm problem
843810Nov 14 2002 — edited Nov 10 2005Hi there,
Sorry to bother you all with this but I'm having a problem creating a simple ElGamal cipher. If someone could take a look at my working and point out the stupid mistake(s) I'd really be grateful. BTW Sorry if my notation is wrong, I wasn't sure how to illustrate power so I've used x^y to indicate x raised to the power of y.
At the minute, all I want to do is to take a single byte (value: 65), encrypt it and then decrypt it as a test.
Since ElGamal is a block cipher I think I need an 8-bit key to make this work?
Anyway, I start by generating my 8-bit prime p = 233.
Then two other random nums less than p.
x = 120
g = 33
Generate y
y = (g^x) mod p = 184
So the public key is p,g,y = 233,33,184 and the private key is x = 120.
Then I try to encrypt my plaintext byte (M=65). Get a random number, k, which is relatively prime to p-1.
k = 15
a = (g^k) mod p = (33^15) mod 233 = 181
b = (y^k)M mod p = ((184^15) * 65) mod 233 = 47
So the ciphertext is 181,47.
Now for decryption.
M = b/(a^x) mod p = 47 / (181^120) mod 233 = 5.6320807597844912172790263583038e-270
ERR.... you see. Somewhere along the line I'm getting this wrong. But I've not a clue where.
Any ideas?
Thanks,
E