现代密码学第六章.ppt

6.5.1 椭圆曲线上的密码体制 1. Diffie-Hellman密钥交换(GF(p)上的方案见5.2.3节) 第1步：取一素数p≈2180和两个参数a、b，则得椭圆曲线上面的点及无穷远点构成Abel群Ep(a,b)，a，b应使群的阶n具有大素因子 第2步: 取Ep(a,b)的一个生成元G＝(x1,y1)，要求G的阶是一个非常大的素数，G的阶是满足nG=O的最小正整数n。Ep(a,b)和G作为公开参数 第3步: 两用户A和B之间的密钥交换如下进行： ① A随机选整数nAn，必威体育官网网址nA，计算PA=nAG产生Ep(a,b)上的一点发给B ② B类似地选取秘密的nB并计算PB发给A ③ A、B分别由K=nAPB和K=nBPA产生出双方共享的秘密钥 这是因为K=nAPB=nA(nBG)=nB(nAG)=nBPA 攻击者若想获取K，则必须由PA和G求出nA，或由PB和G求出nB，即需要求椭圆曲线上的离散对数，因此是不可行的 如果将这一密钥用作单钥加密的会话密钥，则可简单地取其中的一个，如取x坐标，或取x坐标的某一简单函数。或计算hash值 */ 第六章 公钥密码和离散对数 6.5.1 椭圆曲线上的密码 2. 利用椭圆曲线实现ElGamal密码体制 首先选取一条椭圆曲线，并得Ep(a,b)，将明文消息m通过编码嵌入到曲线上得点Pm，再对点Pm做加密变换。如4.7.4 取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，这意味着必须求椭圆曲线上的离散对数，因此不可行 */ 第六章 公钥密码和离散对数 6.5.1 椭圆曲线上的密码体制 3. 椭圆曲线密码体制的优点 与基于有限域上离散对数问题的公钥体制（如Diffie-Hellman密钥交换和ElGamal密码体制）相比，椭圆曲线密码体制有如下优点: (1) 安全性高 攻击有限域上的离散对数问题可以用指数积分法，其运算复杂度为 O(exp )，其中p是模数（为素数）。而它对椭圆曲线上的离散对数问题并不有效。 目前攻击椭圆曲线上的离散对数问题的方法只有适合攻击任何循环群上离散对数问题的大步小步法，其运算复杂度为O(exp ) 其中pmax是椭圆曲线所形成的Abel群的阶的最大素因子。 如果p有大素因子q，且p＝2q＋1，则非常安全 因此，椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体制更安全 */ 第六章 公钥密码和离散对数 6.5.1 椭圆曲线上的密码 (2) 密钥量小 由攻击两者的算法复杂度可知，在实现相同的安全性能条件下，椭圆曲线密码体制所需的密钥量远比基于有限域上的离散对数问题的公钥体制的密钥量小。 (3) 灵活性好 有限域GF(q)一定的情况下，其上的循环群（即GF(q)-{0}）就定了 GF(q)上的椭圆曲线可以通过改变曲线参数，得到不同的曲线，形成不同的循环群。因此，椭圆曲线具有丰富的群结构和多选择性 可在保持和RSA/DSA体制同样安全性能的前提下大大缩短密钥长度(目前160比特足以保证安全性)，因而在密码领域有着广阔的应用前景 表4-7给出了椭圆曲线密码体制和RSA/DSA体制所需的密钥的长度 */ 第六章 公钥密码和离散对数 RSA/DSA 512 768 1024 2048 21000 120000 ECC 106 132 160 211 600 1200 MIPS-年，(每秒百万条指令) 1012 1036 1078 10168 6.5.2 ElGamal体制的安全性 */ 第六章 公钥密码和离散对数 (1)离散对数的比特安全性 6.5.2 ElGamal体制的安全性 */ 第六章 公钥密码和离散对数 （2） ElGamal体制的语义安全性 6.6 公钥体制的安全性定义 为了设计出安全的公钥密码体制，需要对公钥体制的安全性进行形式化的定义，给出精确的度量，然后设计出能够证明满足所定义安全性的密码算法，才是有安全性保障的算法。 公钥密码体制按照可能的攻击目标，可以分为： 单向性、不可区分性、语义安全性、不可展性、明文可意识性 1. 单向性OW(One-Way)：由密文不能直接恢复明文 单向性在公钥密码中是最基本的概念，对于公钥密码算法