快捷搜索: 王者荣耀 脱发

ElGamal公钥密码和椭圆曲线密码体制

ElGamal公钥密码 基于有限域上离散对数问题的公钥密码体制,最著名的是ElGamal体制,是由T. ElGamal在1985年提出的 ElGamal有较好的安全性,同一明文在不同时刻会产生不同的密文 应用广泛,尤其数字签名方面的应用,著明的美国数字签名标准DSS就是ElGamal的一种变形。

离散对数问题 设 p是素数,g 是 Zp* 的本原元:即 g1, g2, …, gp−1 在 mod p 下产生 1 到 p−1 的所有值 对任意 y∈[1, …, p−1],有唯一的 x∈[1, …, p−1]使得 y≡gx mod p 称 x 为模 p 下以 g 为底 y 的离散对数,记为 x≡loggy mod p 当g, p, x已知时,计算 y的值比较容易,但如果已知g, p, y,求 x 则非常困难。

密钥生成算法KG: 选择一素数 p , Zp= [1, …, p−1] g 是 Zp* 的一个本原元 选择随机数 x∈[1,p−1], 计算 y=gx mod p 私钥为 x,公钥为 y。g 和 p 可由一组用户共享。 *已知{x, g, p}, 计算y是容易的 已知{y, g, p}, 计算x是困难的

加密算法: c1=gk (mod p) c2=myk (mod p) C=(c1,c2)

解密算法: m=c2(c1x)-1 mod p

例:假设 p=2579, 本原元g=2,私钥为 x=765,则公钥 y=2765 mod 2579=949。若消息 m=1299,
加密:A选择随机数k=853,使用公钥y=949
计算 c1=2853 mod 2579=435
和 c2=1299*949853 mod 2579=2396。
发送密文(435,2396)
解密:B解密消息,使用私钥x=765
m = 2396*(435765)-1 mod 2579=1299。

简化为:
#encrypt
c1 = (g**k) % p 
c2 = (m*(y**k)) %p
c = (c1,c2)
# decrypt 
m = (c2*(c1**(-1))) %p 
可以加个素数判断,和本原元求解

椭圆曲线密码体制

椭圆曲线在代数学和几何学上已研究了150多年,有丰富而深厚的理论积累。 1985年,Koblitz和Miller提出椭圆曲线密码体制(Elliptic Curve Cryptosystem,简称ECC) 椭圆曲线并不是椭圆,之所以称为椭圆曲线是因为它们是用三次方程来表示的,它的一般形式:y2 + axy + by = x3 + cx2 + dx + e 其中a, b, c, d和 e是满足某些条件的实数。 在实数系中,椭圆曲线是所有满足方程 E: y2=x3+ax+b 的点 (x, y) 所构成的集合。 若 4a3+27b2≠0,则E:y2=x3+ax+b能成为群(group) 例如,椭圆曲线 E: y2=x3-7x+3 的图形:

密码学中采用有限域上的椭圆曲线 曲线方程中,所有系数来自某一有限域GF§中 常用表示: E: y2≡x3+ax+b (mod p) ,p是大素数, a, b, x, y 属于GF§,即从{0, 1, …, p−1}中取值,并满足 4a3+27b2 (mod p)≠0 该曲线上只有有限个点(x, y),包括一个特殊点 O,称无限远点 定义 Ep(a,b) 为在模 p下 E 上所有点的集合(包括O) 点 P=(x, y) 关于X轴的对称点 (x, −y) 称为 P 的逆 −P 若 nP=O,且n 为最小的正整数,则 n 为E上P 的阶

椭圆群的构造 Ep(a, b)的生成过程 (i) 对 x=0,1,…,p−1,计算 x3+ax+b(mod p) 。 (ii) 对于每一计算结果确定它是否有模p的平方根。 如果没有,则 Ep(a,b) 中没有与该结果相应 x坐标的点;如果有,设两个平方根为y和p−y,则点(x,y)和(x,p−y)都是Ep (a,b)的点(如果y=0,只有(x, 0)一个点)

椭圆曲线在模p下的运算规则 ***加法规则:*** (i) 对所有 P∈Ep,则 P+O=O+P=P,P+(−P)=O (ii) 令 P=(x1, y1)∈Ep 和 Q=(x2, y2)∈Ep, 且 P≠ −Q ,则 P+Q=R =(x3, y3) ∈Ep ,其中: 密钥生成

选择椭圆曲线 E: y2=x3+ax+b (mod p), 构造一个椭圆群Ep(a, b)
在Ep(a,b) 中挑选生成元点 G, 使满足n·G=O 的最小的 n 是一个非常大的素数
选择一个小于n 的整数 x 作为私钥,产生公钥 Y=x·G
私钥:x; 公钥:{Y,E,G}
**加密算法**
(1) 在区间[1, n−1]内选取随机数k,计算 kG。
(2) 依据明文m和公钥Y,计算 m+kY。
(3) 传送加密数据 {kG, m+kY} 给接收方。
**解密算法**
接收方使用自己的私钥 x 计算:
(m+kY)−x·(kG) = (m+kY)−k(xG) = m
#难点在于椭圆曲线群的构造和坐标点的运算上,对应相应的规则使用即可,如需要编程实现原理同上。
经验分享 程序员 微信小程序 职场和发展