Negative exponentiation for Encryption / Decryption using Fast Exponentiation

All,

I have coded Fast exponentiation algorithm to check if the encrypted value is equal to the original value for a given exponent (e) and modulo base (n). When I have a negative exponent, the values are not the same. Here is what I do:

1 > Any value base

2 > Private key prKey

3 > Public key puKey

4 > Modulo base modN

Decrypt using base ^ prKey mod modN to get decryptVal

then encrypt decryptVal ^ puKey mod modN to get encryptVal

Now encryptVal should be equal to base. In my code, this condition is satisfied for positive values of private key prKey only. For negative values of prKey, the condition is never satisfied.

Example (from my code run for various random values):

1 > base: 4092

2 > modN = 6499

3 > puKey = 5

4 > prKey = -1267

would give decryptVal = 4092 and encryptVal = 5537 !=开发者_运维知识库 base

whereas when,

1 > base: 249

2 > modN = 6059

3 > puKey = 5

4 > prKey = 1181

gives me decryptVal = 4067 and encryptVal = 249 = base

Is this condition the expected behavior or there is a flaw in my code based on above execution results? [Note]: prKey and puKey are computed using Extended Euclidean algorithm

I read through your post twice and cannot quite understand what the problem is. You ask if there is a flaw in your code but you haven't shown any code. Anyway, the usual definition of exponentiation ax mod n for negative x requires that gcd(a,n) = 1. If gcd(a,n) = 1 then a^xmod n == (a-1)-x mod n. So if x is negative first compute the inverse of a and then raise that to the -x power, all mod n.