I'm implementing a semi ELGamal cryptosystem(from a research paper) function that has been used in PVSS. Unfortunately, I fail to decrypt as it has been described in the algorithm.
Here is the initialisation phase:
Select a secure prime p such that p-1=2q where q is also a prime, then make a cyclic group G and let g be a random generator of this group. Pick a random x(private key) in the group and let y = g^x(public key). I simply initialise the algorithm as following:
p = 233;
g = 131;
x = 139;
y = g ^ x mod 233; //y = 182
Now let s (secret) be 23 and we compute our es (encrypted secret):
s = 23
es = y ^ s mod 233// es = 231
In order to decrypt the es, I raise es to the inverse of x(private key), I should return the g ^ s, assume ds is the deciphered value:
ds = es ^ 1/x mod 233 // 1/x = 57, ds = 116
Problem is here, ds is not equal to g ^ s but in theory it should be because:
recall that we encrypted our s as:
es = y ^ s mod 233
and we know that
y = g ^ x mod 233
so,
es = g ^ x ^ s mod 233
Given that,
ds = es ^ 1/x mod 233
// which means:
ds = g ^ x ^ s ^ 1/x mod 233
therefore, I expect to get same result as of g^s (131 ^ 23 mod 233) which must be 182 while what I get as the ds result is 116.
Is there anything wrong with what I'm doing?
When you have:
x * invX = 1 mod p
the following equality is generally not true:
(g ^ x) ^ invX = g mod p
Above expression means multiplying g*g*....*g a certain number of times, x * invX, which is also k * p + 1 according to first modulo relation.
Say your generator has a size n <= p-1:
g ^ n = 1 mod p
That means that x * invX must be a multiple of n...
In your preamble, you assert that q=(p-1)/2 is prime, but here, it's not the case, q=116...
And in your example g=131 is generating a sequence of length 58=(p-1)/4.
Then, only those x have the property g ^ x ^(1/x) = 1 mod p :
58 116 132 154 174 203 229 231 232
Note that for another generator, g=5, the sequence is of maximal length p-1, and then the sole x satisfying (g ^ x) ^ invX = 1 mod p is x=p-1.
Since y^(p-1) = 1 mod p for any y non multiple of p, x=p-1 is allways working as you expect anyway...