Python：ElGamal

簡介

百度百科傳送門
基於迪菲-赫爾曼密鑰交換的非對稱加密算法
EIGamal公開密鑰密碼體制是基於有限域中離散對數間題的難解性。它所根據的原理是：求解離散對數是困難的，而其逆運算可以應用平方乘的方法有效的計算出來。在相應的群G中，指數函數是單向函數。

算法

說明

• import說明： 在導入中加入了我自己寫的素數相關函數，可自行添加改寫
• 輸入： 十進制整數（代碼中為mb，即B的明文），可用注釋部分替換
• 輸出： 分兩部分：加密部分輸出加密後的十進制密文對，解密部分輸出解密後的十進制明文（懶，自行拆解代碼
• 其他： 自動生成安全素數p（速度看運氣，快則兩三秒，沒有上限）、原根g、隨機數a、g的a次方， 素數p、原根g、g的a次方作為公鑰，隨機數a為私鑰，公私鑰對都是接收者A的
• 流程： 系統生成相關參數，B將明文mb加密成（c1，c2）後發送給A；A收到後用私鑰a解密輸出明文ma（，最後比對明文正確性，正常肯定沒這步）。

代碼

運行報錯、超時請看說明

import prime
import random
import math
p=prime.safe_length(150)
g=prime.safe_root(p)
a=random.randint(2, p)
ga=pow(g,a,p)
print('公鑰：('+str(p)+',\n'+str(g)+',\n'+str(ga)+')')
#print('私鑰：'+str(a))
mb=prime.length(149)#int(input('m:'))
print('\nB\'s input:\n'+str(mb))
k=random.randint(1, p-1)
while math.gcd(p-1, k)!=1:
k=random.randint(1, p-1)
c1=pow(g, k,p)
c2=((mb%p)*pow(ga,k,p))%p
print('\ncyphertext：('+str(c1)+',\n'+str(c2)+')')
v=pow(c1,a,p)
ma=(c2*prime.modinv(v,p))%p
print('\nA\'s output:\n'+str(ma))
print(ma==mb)#明文比對