(续)2.3加法法则.ppt

3.4 椭圆曲线上的离散对数(续) 4 椭圆曲线密码 4.1 明文表示 4.1 明文表示(续) 4.2 椭圆曲线ElGamal密码系统 4.2 椭圆曲线ElGamal密码系统(续) 4.2 椭圆曲线ElGamal密码系统(续) 4.2 椭圆曲线ElGamal密码系统(续) 4.3 椭圆曲线数字签名算法(ECDSA) 4.3 椭圆曲线数字签名算法(ECDSA)(续) 5 椭圆曲线在分解中的应用5.1 椭圆曲线分解算法 5.1 椭圆曲线分解算法(续) 5.1 椭圆曲线分解算法(续) 5.1 椭圆曲线分解算法(续) 5.1 椭圆曲线分解算法(续) 5.1 椭圆曲线分解算法(续) 5.2 退化曲线 5.2 退化曲线(续) 5.2 退化曲线(续) Certicom是ECC的主要商业支持者，拥有超过130项专利，并且已经以2千5百万美元的交易获得了国家安全机构（NSA）的技术许可。他们也已经发起了许多对ECC算法的挑战。已经被解决的最复杂的是109位的密钥，是在2003年初由一个研究团队破解的。破解密钥的这个团队使用了基于生日攻击的大块并行攻击，用超过10,000台奔腾级的PC机连续运行了540天以上。对于ECC推荐的最小密钥长度163位来说，当前估计需要的计算资源是109位问题的108倍。 * 椭圆曲线 1984年，Hendrik Lenstra提出了依靠椭圆曲线性质分解整数的精妙算法。这一发现激发了学者进一步研究椭圆曲线在密码和计算数论的其它应用。 椭圆曲线密码在1985年分别由Neal Koblitz 和Victor Miller提出。椭圆曲线密码方案为公钥机制，提供如同RSA一样的功能。但是，它的安全性依赖不同的困难问题，也就是椭圆曲线离散对数问题(ECDLP)。 我们知道解决分解整数问题需要亚指数时间复杂度的算法，而目前已知计算ECDLP的最好方法都需要全指数时间复杂度。这意味着在椭圆曲线系统中我们只需要使用相对于RSA 短得多的密钥就可以达到与其相同的安全强度。例如，一般认为160比特的椭圆曲线密钥提供的安全强度与1024比特RSA密钥相当。使用短的密钥的好处在于加解密速度快、节省能源、节省带宽、存储空间。 本讲提要 Weierstrass方程 实域上的椭圆曲线 有限域上的椭圆曲线 椭圆曲线密码 椭圆曲线在分解中的应用 1 WEIERSTRASS方程 2 实域上的椭圆曲线2.1 简化WEIERSTRASS方程 2.2 实域上的椭圆曲线 2.3 加法法则 弦和切线法则 2.3 加法法则(续) 弦和切线法则(续) 2.3 加法法则(续) 2.3 加法法则(续) 2.3 加法法则(续) 代数公式 2.3 加法法则(续) 2.3 加法法则(续) 3 有限域上的椭圆曲线 3.1 模素数p的椭圆曲线，p≠2，3情形 3.1.1 加法法则 3.1.2 例子 3.1.2 例子(续) 3.2 有限域GF(2N)上的椭圆曲线 3.2.1简化WEIERSTRASS方程 3.2.2 加法法则 3.2.2 加法法则(续) 3.2.2 加法法则(续) 3.2.2 加法法则(续) 3.2.3 例子 3.3 点的数量 3.3 点的数量(续) 3.4 椭圆曲线上的离散对数 Certicom是ECC的主要商业支持者，拥有超过130项专利，并且已经以2千5百万美元的交易获得了国家安全机构（NSA）的技术许可。他们也已经发起了许多对ECC算法的挑战。已经被解决的最复杂的是109位的密钥，是在2003年初由一个研究团队破解的。破解密钥的这个团队使用了基于生日攻击的大块并行攻击，用超过10,000台奔腾级的PC机连续运行了540天以上。对于ECC推荐的最小密钥长度163位来说，当前估计需要的计算资源是109位问题的108倍。 *