应用密码学第21讲--EIGamal体制与公钥密码体制小结教材教学课件.ppt

EIGamal体制与公钥密码体制小结 数学基础 本原元：设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=2q+1)中随机选择一个 ,若 且 , 则判定 是安全素数;否则再随机选择另一个 进行检验. 问题:容易找到本原元吗? 答案: 容易,至少在安全素数条件下容易. 习题 在用户a对用户b利用RSA公钥密码体制进行消息的加密＋签名时，若二者使用的模数nanb，为了使脱密正常进行，应该先加密还是先签名？