-1
$\begingroup$

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

|improve this question
$\endgroup$

closed as off-topic by e-sushi May 16 '17 at 18:19

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm or protocol works, you should look into asking on Stack Overflow instead." – e-sushi
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ 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. $\endgroup$ – Ilmari Karonen May 16 '17 at 18:38
1
$\begingroup$

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!

|improve this answer
$\endgroup$
0
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks, There is no mathematical relation to converting numbers smaller? $\endgroup$ – user7747790 May 16 '17 at 13:42
  • 2
    $\begingroup$ 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... $\endgroup$ – poncho May 16 '17 at 16:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.