大數的 Elgamal 解密計算

我是密碼學的初學者。我研究了 Elgamal 算法。

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=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

範例中的數字非常小（2 ^ 2 * 3），如果它們是非常大的數字，我該如何計算它們？（冪和乘法）

謝謝

由於您是初學者，我不會花很多時間設計您自己的任意精度/“BigNum”庫。許多語言都內置了此功能，例如 Python 或 Ruby。例如，在 Python 中，計算 $ a^b \mod m $ ，您可以使用內置pow(a,b,m)函式：

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

請注意自動轉換為 bignums（末尾的“L”）。

您還可以使用Genius 之類的工具，或者對於較重的舉重，使用Sage。

最後，有很多用於任意精度整數的庫，比如GMP。或者你可以自己寫，但要等很久！

您可以使用 bc 計算器在 shell linux 上計算大數或安裝windows 版本。您還可以使用BigInteger 庫製作自己的 Java 應用程序來處理大數字。

我使用 Big Integer 庫實現了 ElGamal 加密，但加密過程非常慢，數字超過 21 位。我希望我對您有所幫助。

引用自：https://crypto.stackexchange.com/questions/47457