160102_椭圆曲线密码.pptVIP

1.* ? 2006 第10章 椭圆曲线密码 返回总目录 第10章 椭圆曲线密码 教学目的 了解椭圆曲线密码 了解椭圆曲线 了解ECCp-109挑战 了解并行Pollard Rho法 ? 椭圆曲线 本章内容 ? 椭圆曲线（mod p） ? 加权投影坐标 ? 定义在Galois域的椭圆曲线 ? 密码安全曲线 ? 将信息转化为椭圆曲线代码 本章内容 ? 椭圆曲线公开密钥密码算法 ? 椭圆曲线因数分解 ? ECCp-109挑战 ? 并行Pollard Rho法 椭圆曲线的安全度 30:1 20:1 12:1 密钥长度比 15360-bit 7680-bit 3072-bit RSA 512-bit 384-bit 256-bit 椭圆曲线密码 9:1 6:1 5:1 密钥长度比 2048-bit 1024-bit 512-bit RSA 224-bit 163-bit 112-bit 椭圆曲线密码 椭圆曲线 10.1 椭圆曲线 定义 椭圆曲线即三次平滑代数平面曲线（Smooth Algebraic Plane Curve），可在适当的坐标下，表达成Weierstrass方程式 除了特殊系数，一般而言，可在适当的坐标下，表示成 在系数K上的平面图形，其中E也包括无限远点O。 椭圆曲线加法律 定义椭圆曲线加法律 在椭圆曲线定义“加法”如下： （1）视无限远点O为“加法单位素”。 （2）点P的“加法反元素”即点-P，定义为点P对x轴的镜像。 （3）一般而言，三次曲线与直线相交于三点（需计算重数（Multiplicity），若相切时，重数为2，如图所示，P、Q、-（P+Q）共线，点(P+Q)即点-(P+Q)对x轴的镜像，依此定义“加法”。 椭圆曲线加法律 （4）加法坐标计算：令 、 ，欲求 其中可分为三种情形： ：取通过P、Q截线的斜率 。 、 ：即P=Q，取通过P切线的斜率 。 、 ：此时 。 除第3种情形外， 椭圆曲线 定理 为交换群（Abelian Group），其中加法“+”，如上所定，无限远点O为加法单位素。 定义 令P为椭圆曲线E上一点。对自然数n，可定义“乘法” 定理Mordell-Weil 令椭圆曲线E定义在有理数上 ， 为曲线上所有x、y坐标皆为有理数的点所成的集合（也包含无穷远点O），则 椭圆曲线（mod p） 10.2 椭圆曲线（mod p） 定理 令P3为质数。令定义在整数 上的椭圆曲线 其中a、 系数、均为整数且满足 则 为定义在FP上的椭圆曲线。 椭圆曲线（mod p） 定义椭圆曲线离散对数问题 令 （mod p）为一椭圆曲线，令P、Q为E(FP)上的两点，假设点Q由点P生成。在E上的离散对数问题就是要解 的k值。 定理 令E为定义在FP上的椭圆曲线，则E(FP)的个数满足 其中误差项 定理 令椭圆曲线 (mod p)，则 加权投影坐标 10.3 加权投影坐标 性质 令椭圆曲线 令 ， 为E上的点（加权投影坐标表达式）。而点 若P1、P2≠0，且P1≠±P2，则加法公式为 若P1=P2，则 的公式为 定义在Galois域的椭圆曲线 10.4 定义在Galois域的椭圆曲线 定义 定义在特征值为2的Non-Supersingular椭圆曲线，可在适当的坐标系选取下表示成 加法律”可定义如下： ： P＝Q： 密码安全曲线 10.5 密码安全曲线 例： 令p3为质数、b为整数，且p|b。令椭圆曲线 则E为Supersingular曲线。 证明： 考虑乘法群的Homomorphism： 故由Lagrange定理，可得 将信息转化为椭圆曲线代码 10.6 将信息转化为椭圆曲线代码 而信息m将对应到E(FP)之某点的x坐标值。然而，m3+am+b为完全平方数的概率