pythonmathcryptographyprecisionelgamal

Python: Large float arithmetic for El Gamal decryption

Context

The decryption math formula for the El Gamal method is the following:

m = ab^(-k) mod p

Specifically in Python, I want to compute the following equivalent:

>>> m = (b**(-k) * a) % p

The issue in the above Python code is that the numbers inserted would overflow or result in 0.0 due to precision. Consider the following example:

>>> (15653**(-3632) * 923) % 262643
0.0

The expected answer for the above example is 152015.

More Examples

enter image description here

Attempts

I've tried to research a strategy to deal with this problem and found that using Python's default pow(x,y,z), which differs from math.pow(), can help.

pow(x,y,z) is equivalent to x**y % z

However, I cannot use pow(x,y,z). I tried to use pow(15653, -3632, 262643), but I cannot multiply the result of pow(15653, -3632) by 923 to then, as a final step, mod by 262643.

In other words, instead of x**y % z, I am trying to perform (x**y * a ) % z, but there is clearly a 3-parameter limit or number of operations from pow(x,y,z).

What can I do to compute the math formula in Python?

Solution

  • Very easily: just multiply the two, and do an explicit mod:

    >>> p = 262643
>>> pow(15653, -3632, p)
86669
>>> 86669 * 923 % p
152015

    Done!