02信息安全概论--第二章-密码学信息必威体育官网网址技术.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 有限域上的椭圆曲线 密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（其中p为一大素数）。其中最为常用的是由方程： y2≡x3+ax+b(mod p) (a,b∈GF(p),4a3+27b2(mod p)≠0) * * 例：p=23，a=b=1，4a3+27b2(mod 23) ≡8≠0 ，方程为y2≡x3+x+1，其图形是连续曲线，由上图(b)所示。 然而我们感兴趣的是曲线在第一象限中的整数点。设Ep(a,b)表示方程所定义的椭圆曲线上的点集{(x,y)|0≤xp,0≤yp，且x,y均为整数}并上无穷远点O。 * * 一般来说，Ep(a,b)由以下方式产生： ① 对每一x(0≤xp且x为整数），计算 x3+ax+b(mod p)。 ② 决定①中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根（y=0 时只有一个平方根）。 * * Ep(a,b)上的加法定义如下： 设P，Q∈Ep(a,b)，则 ① P+O=P。 ② 如果P=(x,y)，那么(x, y)+(x, -y)=O 即 (x, -y)是P的加法逆元，表示为-P。 由Ep(a,b)的产生方式知，-P也是Ep(a,b)中的点，如上例，P=(13,7)∈E23(1,1)，-P=(13, -7)，而-7 mod 23≡16，所以-P=(13, 16)，也在E23(1,1)中。 * * ③ 设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下规则确定： x3≡λ2-x1-x2(mod p) y3≡λ(x1-x3)-y1(mod p) 其中 * * 例： 仍以E23(1,1)为例，设P=(3,10)，Q=(9,7)，则： 所以P+Q=（17,20），仍为E23(1,1)中的点。 * * 若求2P则 所以2P=(7,12)。 * * 倍点运算仍定义为重复加法，如 4P=P+P+P+P。 从上例可以看出，加法运算在E23(1,1)中是封闭的，且能验证还满足交换律。对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，所以Ep(a,b)是一个Abel群。 * * 椭圆曲线上的密码 为使用椭圆曲线构造密码体制，需要找出椭圆曲线上的数学困难问题。 在椭圆曲线构成的Abel群Ep(a,b)上考虑方程Q=kP，其中P，Q∈Ep(a,b)，kp，则由k和P易求Q，但由P、Q求k则是困难的，这就是椭圆曲线上的离散对数问题，可应用于公钥密码体制。 ElGamal密码体制是基于有限域上离散对数问题的公钥体制，下面考虑如何用椭圆曲线来实现这种密码体制。 * * ElGamal密码体制的原理 密钥产生过程： 选一素数p以及两个小于p的随机数g和x，计算y≡gx mod p。以(y, g, p)作为公开密钥，x作为秘密密钥。 加密过程： 设欲加密明文消息M，随机选一与p-1互素的整数k，计算C1≡gk mod p,C2≡ykM mod p，密文为C=(C1,C2)。 * * 解密过程： 这是因为 * * 利用椭圆曲线实现ElGamal密码体制 首先选取一条椭圆曲线，并得Ep(a,b)，将明文消息m通过编码嵌入到曲线上得点Pm，再对点Pm做加密变换。 取Ep(a,b)的一个生成元G，Ep(a,b)和G作为公开参数。 * * 用户A选nA作为秘密钥，并以PA=nAG作为公开钥。任一用户B若想向A发送消息Pm，可选取一随机正整数k，产生以下点对作为密文： Cm={kG,Pm+kPA} A解密时，以密文点对中的第二个点减去用自己的秘密钥与第一个点的倍乘，即 Pm+kPA-nAkG=Pm+k(nAG)-nAkG=Pm * * 攻击者若想由Cm得到Pm，就必须知道k。而要得到k，只有通过椭圆曲线上的两个已知点G和kG，这意味着必须求椭圆曲线上的离散对数，因此不可行。 * * * 椭圆曲线版的ElGamal密码 算法椭圆曲线版的ElGamal密码 Alice欲加密明文Pm代码成密文PC传送给Bob。 （曲线参数约定）约定 (E/Fq,P)。 （密钥产生）Bob随机选取一个整数B且B与g互质，即gcd(B,g)=1，计算PB=[B]P。公开密钥为(E/Fq,P,PB) ，私钥为B