|
目录
Elgamal公钥加密算的过程与要求
本原根生成
代码部分
Elgamal公钥加密算的过程与要求
1. 密钥产生与加解密过程 2. 数据要求
秘密长度近150位，验收用的5个秘密（145，140，135，130，125位）
大素数的形式为p=2q+1形式的强素数，这里面q也是素数，要求p为150位的大素数，大素数p和本原根自己生成。
解密出的结果要与明文对比，验证解密是否正确。
中间数据显示在屏幕上，包括P，g，g^a，k及密文c=(c1, c2)等。
本原根生成
算法的难题在于生成大素数p的本原根，生成本原根有多种方法，比如遍历判断等，本文选取的方法为：
随机生成一个大素数q，当q为素数时，则p = 2p + 1一定为素数。
生成一个随机数g（1 2 ≠ 1 且 gq ≠ 1，则g为大素数p的本原根。
代码部分
本代码使用了SymPy科学计算库中关于求素数和判定素数的两个函数，需提前安装SymPy包。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465from random import randint
import sympy
import sys
sys.setrecursionlimit(10000)
#快速取模幂
def fastExpMod(a, e, m):
a = a % m
res = 1
while e != 0:
if e&1:
res = (res * a) % m
e >>= 1 #右移一位
a = (a * a) % m
return res
#生成原根
def primitive_element(p, q):
while True:
g = randint(2, p - 2)
if fastExpMod(g, 2, p) != 1 and fastExpMod(g, q, p) != 1:
return g
def e_gcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = e_gcd(b, a%b)
return g, y, x-a//b*y #1.gcd 2.a^-1 mod b 3.b^-1 mod a
def encrypt(p, g, y, m): #Bob -- 加密
k = randint(2, p-2)
c1 = fastExpMod(g, k, p)
c2 = (m*fastExpMod(y, k, p))%p
return c1, c2
def decrypt(c1, c2, p, a): #Alice -- 解密
v = fastExpMod(c1, a, p)
v_1 = e_gcd(v, p)[1]
m_d = c2 * v_1 % p
return m_d
def main():
m = int(open('secret0.txt').readline())
while True:
q = sympy.randprime(10**149, 10**150 / 2 - 1) #使得p也在150位
if sympy.isprime(q):
p = 2 * q + 1
if len(str(p)) == 150 and sympy.isprime(p):
break
g = primitive_element(p, q)
a = randint(2, p-2)
y = fastExpMod(g, a, p)
c1, c2 = encrypt(p, g, y, m)
m_d = decrypt(c1, c2, p, a)
if m == m_d:
print("They are the same!")
else:
print("Nooooooooooo!")
return m, p, g, y, c1, c2, m_d
if __name__ == '__main__':
print("m = %d\nALice的公钥：\np = %d\ng = %d\ng^a = %d\n密文(c1, c2) = (%d,\n%d)\n明文m = %d"
% main())
|