# Elgamal decryption computations for big numbers [closed]

I am a beginner in cryptography. I studied the Elgamal algorithm.

secret key= (p,g,a)
Encryption= c1=(g^k mod p) , c2=(m.B^k mod p) // 0<k<p-1
Decryption= c1^(p-1-a)*c2 mod p


A simple example for decryption:

a=4
p=7
g=3
c1=2 , c2=3
decrypted message= 2^(7-1-4)*3 mod 7 = 2^(2)*3 mod 7 = 4*3 mod 7 = 12 mod 7 = 5


Numbers in the example are very small (2^2 *3), If they were very big numbers, How can I compute them?(power and multiplication)
Thanks

• I don't think this question is necessarily off-topic here, but I do think that it's basically been asked before already. While that earlier question is phrased in the context of RSA instead of ElGamal, the basic question ("How do computers handle the large numbers that come up in public-key crypto?") is the same, as are the answers. May 16, 2017 at 18:38

Since you are a beginner, I would not spend a lot of time designing your own arbitrary-precision / "BigNum" library. A lot of languages have this feature built-in, like Python or Ruby. For example, in Python, to calculate $a^b \mod m$, you can use the built-in pow(a,b,m) function:

In [2]: pow(199703471997348597303557477228581222008, 20617548250412763970655475611439323667, 340282366920942343108801213731143778827)
Out[2]: 147463488513399901685538085562973037255L


Notice the auto-conversion to bignums (the "L" at the end).

You can also use a tool like Genius or, for heavier lifting, Sage.

Lastly, there are great libraries for arbitrary-precision integers, like GMP. Or you could write your own, but do that much later!

You can use bc calculator to computing big numbers on shell linux or install the version for windows. Also you can make your own Java application using the BigInteger library for work with big numbers.

I made a implementation of ElGamal encrytion using Big Integer library but the encrytion process was very slow with numbers most than 21 bits. I hope I've been helpful.

• Thanks, There is no mathematical relation to converting numbers smaller? May 16, 2017 at 13:42
• If you have any problem with numbers larger than 21 bits (which is tiny by cryptographical standards), you are doing things wrong. Any of the packages mentioned by galvatron does it correctly... May 16, 2017 at 16:59