第19讲 EIGamal体制.pptVIP

EIGamal体制与椭圆曲线(ECC)密码体制 数学基础 本原元：设p为素数，若存在一个整数a，使得a，a2，a3，……，ap－1，，关于模p互不同余，则称模p的本原元。 离散对数问题：Y=logaX X计算Y是容易的，至多需要2×log2p次运算就可以。但是根据Y计算X就是困难的，利用目前最好的算法，对于小心选择的p将至少需要p1/2次以上的运算，只要p足够的大，求解离散 对数就是相当困难的。 EIGamal公钥密码体制 设计过程: Step1 选取大素数p,再选取 的一个本原元a,并将p和a公开. Step2 随机选取整数 ,并计算出 并将 作为公开的加密密钥,将d作为必威体育官网网址的脱密密钥. 加脱密变换 加密变换: ,秘密选择一个整数, 则密文为 其中 脱密变换: 对任意密文 明文为 实例 P=2597,取a＝2，秘密密钥为765，可以计算出公开密钥为y＝2765 mod 2597＝949。 取明文M＝1299，随机数k＝853，则 C1＝2853 mod 2597＝435， C2＝1299×949853 mod 2597＝2396 所以密文为: （C1，C2）＝（435，2396） 解密时计算: M＝2396×(435765)-1 mod 2597＝1299 特点 (1) 密文长度扩展1倍; (2) 只利用了有限域的乘法群的性质,即只使用了乘法运算和求乘法逆的运算 为何密文需要扩展1倍? 这涉及其设计思想问题. 安全性分析 因为该算法是基于离散对数问题的，所以p的选取必须足够的大，为150位以上的十进制数，且p－1有大素因子 为了加密和签名的安全k必须是一次性的 设计思想 (1) 利用Diffie-Hellman密钥交换协议生成双方加密用的密钥.此时 不同之处在于已将 作为公开密钥公布,不需每次发送. (2) 采取了一次一密的加密思想. 将 作为双方交换的密钥,利用它对明文进行加脱密. 问题 为什么要求 ? 答案: 因为 的周期为 p-1 ,即 备注: (1) 参数可以全网公用,也可一人一套; (2) 加密不同的明文分组时选用独立的随机数,但秘密的脱密密钥需和其版本号一起长期不变. 实现方法 (1) 大素数的选择与构造 将大素数p选为安全素数,即使p=2q+1且q为素数. 实验表明,平均100个随机数中可选出1个素数, 平均100素数中可选出1个安全素数. (2)安全素数条件下本原元的判断方法 由Fermat定理知 ,即 因而如果 则有w 整除p-1=2q,因而由q是素数知,w只能是2或q.　此时是　　本原元等价于 　　　　　　　 且 安全素数条件下本原元的构造方法 在 ( p=2q+1)中随机选择一个 ,若 且 , 则判定 是安全素数;否则再随机选择另一个 进行检验. 问题:容易找到本原元吗? 答案: 容易,至少在安全素数条件下容易. 椭圆曲线(ECC)密码体制 Elliptic Curve Cryptography 概述 获得同样的安全性，密钥长度较RSA短得多 被IEEE公钥密码标准P1363采用 椭圆曲线 椭圆曲线的曲线方程是以下形式的三次方程 y2+axy+by=x3+cx2+dx+e a,b,c,d,e是满足某些简单条件的实数。定义中包含一个称为无穷远点的元素，记为O. 椭圆曲线加法的定义 如果其上的3个点位于同一直线上，那么它们的和为O。 O为加法单位元，即对ECC上任一点P,有P+O=P 设P1=(x,y)是ECC上一点，加法逆元定义为P2=-P1=(x,-y) P1,P2连线延长到无穷远，得到ECC上另一点O,即P1,P2,O三点共线，所以P1+P2+O=O, P1+P2=O, P2=-P1 O＋O＝O,O=-O 椭圆曲线加法的定义 Q,R是ECC上x坐标不同的两点，Q+R定义为：画一条通过Q,R的直线与ECC交于P1(交点是唯一的，除非做的Q,R点的切线，此时分别取P1=Q或P1=R)。由Q