elgamal公钥加密和数字签名

### ElGamal 公钥加密算法及其数字签名工作原理 #### 加密算法基础理论 ElGamal公钥加密算法基于离散对数难题构建了一种有效的非对称加密方案[^2]。该算法的安全性依赖于有限域上的离散对数问题难以求解这一特性。 #### 密钥生成流程 为了创建一对匹配的公私钥，在选定一个适当大小的素数 \( p \) 后，还需选取一个小于\( p \) 的整数作为基底 \( g \)，并随机挑选另一个小于 \( p-1 \) 的正整数 \( x \)。通过这些参数可以计算得到公开部分： \[ y = (g ^ {x}) \% p \] 最终形成的密钥对如下所示： - **公钥**：由三个元素组成\((y,g,p)\) - **私钥**：即之前选择的秘密指数\( x \) #### 加密过程描述 当发送方希望向接收者传递消息m时，会执行以下操作来完成数据保护： 1. 随机选出临时密钥 k； 2. 使用接收者的公钥组件按照特定方式处理原始信息 m 和辅助变量 r ，形成两部分构成的密文 C ： \[ C_1 = (g^{k} \% p),C_2=((y^{k}*M) \% p ) \] 这样就得到了完整的密文表示形式\( C=(C_{1},C_{2}) \)。 #### 解密机制解析 持有对应私钥的人可以通过下面的方法恢复初始的信息 M : 给定接收到的密文\( C=(C_{1},C_{2}) \)，利用自身的私钥 x 进行运算: \[ M=\frac{C_{2}}{(C_{1}^{x}\%p)} \% p \] 上述公式能够确保只有拥有正确私钥的一方才可成功还原出原本的消息内容。 #### 数字签名功能概述 除了提供基本的数据保密服务外，ElGamal还支持数字签名的应用场景。在此模式下，签署文件的过程涉及到了哈希函数 H() 来压缩待签发的内容至固定长度摘要 h 。具体步骤包括但不限于： - 发送者用自己的私钥 x 对h实施变换获得 s ; - 将s连同原文一起交给验证者; - 接收端则凭借对方提供的公钥重新计算相应的值并与所附带的签名相比较以确认真伪; 整个过程中涉及到的关键表达式有： \[ S=h*k^{-1}(mod(p-1)) \] \[ R=g^{S} * Y^{-r}(mod\;p) \] 其中\( k,r,s,R,Y \)均为参与运算的重要因子[^1]。 ```python import random from hashlib import sha256 def generate_keys(): q = get_prime(75) # 获取合适的大质数q p = 2*q + 1 # 构造强素数p while True: g = pow(random.randint(2, p-1),(p-1)//q ,p ) if(g != 1): break x = random.randint(1,q-1) y = pow(g,x,p) return ((y,g,p),x) def sign(message,private_key): hash_value=int.from_bytes(sha256(message.encode()).digest(),'big') k=random.randint(1,private_key[2]-2) r=pow(private_key[1],k,private_key[2]) s=(hash_value-private_key[0]*r)*pow(k,-1,(private_key[2]-1)) return (r,int(s%(private_key[2]-1))) def verify_signature(public_key,message,signature): hash_value=int.from_bytes(sha256(message.encode()).digest(),'big') v1=pow(public_key[1],signature[1],public_key[2])*\ pow(signature[0],public_key[0],public_key[2]) % public_key[2] v2=pow(int(pow(signature[0],int(hash_value*(pow(signature[1],-1,public_key[2]-1))),public_key[2])),1,public_key[2]) return v1==v2 # 测试代码片段 if __name__=='__main__': message="This is a test message." pub_key,priv_key=generate_keys() sig=sign(message,priv_key) result=verify_signature(pub_key,message,sig) print(f"Verification Result:{result}") ```