第5章-ElGamal公钥.pptVIP

ElGamal公钥加密算法 一、若干数论概念 本原元 离散对数 离散对数的计算 已知 ,a,p,计算 是容易的 已知 , ,p,计算a 是困难的 二、 ElGamal Example 选择 p=97 及本原根α=5 recipient Bob 选择 秘密钥a =58 计算并发布公钥β =558=44 mod 97 (p, α,a, β)=(97,5,58,44) Alice 要加密 M=3 to Bob 首先得到 Bob的公开密钥β = 44 选择随机 x=36 计算密文对: C1 = αx mod 97 = 536 mod 97 = 50 mod 97 C2 = m βx mod 97 =3× 4436 mod 97 = 31 mod 97 发送 {50,31} to Bob Bob 恢复 message key Bob 恢复明文 M = C2(C1a) -1 mod 97 = 31 × (5058 ) -1 mod 97 = 31 × 22 mod 97 = 3 mod 97 三、离散对数计算问题 Reference 书 William Stallings, Cryptography and network security: principles and practice, Second Edition. Bruce Shneier, Applied cryptography: protocols, algorithms, and sourcecode in C, Second Edition. 文章 密码学的新方向 Web站点 /~weidai/cryptlib.html * 公钥密码基于的数学难题 背包问题 大整数分解问题（The Integer Factorization Problem,RSA体制） 有限域的乘法群上的离散对数问题 (The Discrete Logarithm Problem, ElGamal体制） 椭圆曲线上的离散对数问题（The Elliptic Curve Discrete Logarithm Problem, 类比的ElGamal体制） 本原元(primitive root) Euler定理表明,对两个互素的整数a,n, a?(n) ? 1 mod n 定义： 素数p的本原元定义：如果a是素数p的本原元，则数 a mod p, a2 mod p, … , ap-1 mod p 是不同的并且包含1到p-1的整数的某种排列。 我们又称 a 为Zp的生成元。 离散对数 小心地选择素数，对于离散对数问题目前 还没有多项式时间算法。人们认为离散对数问 题是困难问题。为了抵抗已经知道的攻击，一 般至少150 位，应该至少有大的素因子。 加密： 加密： 证明： ＝ 椭圆曲线密码介绍 1985年Miller,Koblitz 独立提出 y2+axy+by=x3+cx2+dx+e 曲线上的点连同无穷远点O的集合 运算定义： 若曲线三点在一条直线上,则其和为O O用作加法的单位：O = -O; P+O = P 一条竖直线交X轴两点P1、P2，则P1+P2+O=O，于是P1 = -P2 如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P1 2倍，一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S 椭圆曲线密码示意图 有限域上椭圆曲线 有限域上椭圆曲线 y2?x3+ax+b mod p p是奇素数,且4a3+27b2?0 mod p 针对所有的0= x p，可以求出有效的y，得到曲线上的点(x,y)，其中x,y p。记为Ep(a,b) Ep(a,b)中也包括O 加法公式: P+O=P 如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P。而且(x,-y)也在Ep(a,b)中 如果P=(x1,y1)，Q=(x2,y2)，则 P+Q=(x3,y3)为x3=?2-x1-x2 (mod p)y3=?(x1-x3)-y1 (mod p)其中，如果P?Q，则 ? = (y2-y1)/(x2-x1)  如果P=Q，则 ? = (3x12+