,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,EIGamal,体制与公钥密码体制小结,数学根底,本原元：设p为素数，假设存在一个整数a，使得a，a2，a3，ap1，关于模p互不同余，那么称模p的本原元。,离散对数问题：Y=logaX,X计算Y是容易的，至多需要2log2p次运算就可以。但是根据Y计算X就是困难的，利用目前最好的算法，对于小心选择的p将至少需要p1/2次以上的运算，只要p足够的大，求解离散,对数就是相当困难的。,EIGamal,公钥密码体制,设计过程,:,Step1,选取大素数,p,再选取 的一个本原元,a,并将,p,和,a,公开,.,Step2,随机选取整数,并计算出 并将 作为公开的加密密钥,将,d,作为保密的脱密密钥,.,加脱密变换,加密变换:,秘密选择一个整数,那么密文为,其中,脱密变换:对任意密文,明文为,实例,P=2597,取a2，秘密密钥为765，可以计算出公开密钥为y2765 mod 2597949。,取明文M1299，随机数k853，那么,C12853 mod 2597435，,C21299949853 mod 25972396,所以密文为:,C1，C2435，2396,解密时计算:,M2396(435765)-1 mod 25971299,特点,(1),密文长度扩展,1,倍,;,(2),只,利,用了有限域的乘法群的性质,即只使用了乘法运算和求乘法逆的运算,为何密文需要扩展,1,倍,?,这涉及其设计思想问题,.,平安性分析,因为该算法是基于离散对数问题的，所以p的选取必须足够的大，为150位以上的十进制数，且p1有大素因子,为了加密和签名的平安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)中随机选择一个 ,假设,且 ,那么判定,是平安素数;否那么再随机选择另一个,进行检验.,问题:,容易找到本原元吗?,答案:,容易,至少在平安素数条件下容易.,习题,在用户a对用户b利用RSA公钥密码体制进行消息的加密签名时，假设二者使用的模数nanb，为了使脱密正常进行，应该先加密还是先签名？,