密码学——加密演算法教学课件邓安文第10章 椭圆曲线密码.ppt

《密码学——加密演算法教学课件邓安文第10章 椭圆曲线密码.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、返回总目录第10章椭圆曲线密码教学目的了解椭圆曲线密码了解椭圆曲线了解ECCp-109挑战了解并行PollardRho法椭圆曲线本章内容椭圆曲线（modp）加权投影坐标定义在Galois域的椭圆曲线密码安全曲线将信息转化为椭圆曲线代码本章内容椭圆曲线公开密钥密码算法椭圆曲线因数分解ECCp-109挑战并行PollardRho法椭圆曲线的安全度椭圆曲线密码112-bit163-bit224-bitRSA512-bit1024-bit2048-bit密钥长度比5:16:19:1椭圆曲线密码256-bit3

2、84-bit512-bitRSA3072-bit7680-bit15360-bit密钥长度比12:120:130:1椭圆曲线10.1椭圆曲线定义椭圆曲线即三次平滑代数平面曲线（SmoothAlgebraicPlaneCurve），可在适当的坐标下，表达成Weierstrass方程式除了特殊系数，一般而言，可在适当的坐标下，表示成在系数K上的平面图形，其中E也包括无限远点O。椭圆曲线加法律定义椭圆曲线加法律在椭圆曲线定义“加法”如下：（1）视无限远点O为“加法单位素”。（2）点P的“加法反元素”即点-P，定义为点P对x轴的

3、镜像。（3）一般而言，三次曲线与直线相交于三点（需计算重数（Multiplicity），若相切时，重数为2，如图所示，P、Q、-（P+Q）共线，点(P+Q)即点-(P+Q)对x轴的镜像，依此定义“加法”。椭圆曲线加法律（4）加法坐标计算：令、，欲求其中可分为三种情形：：取通过P、Q截线的斜率。、：即P=Q，取通过P切线的斜率。、：此时。除第3种情形外，椭圆曲线定理为交换群（AbelianGroup），其中加法“+”，如上所定，无限远点O为加法单位素。定义令P为椭圆曲线E上一点。对自然数n，可定义“乘法”定理Mordell

4、-Weil令椭圆曲线E定义在有理数上，为曲线上所有x、y坐标皆为有理数的点所成的集合（也包含无穷远点O），则椭圆曲线（modp）10.2椭圆曲线（modp）定理令P>3为质数。令定义在整数上的椭圆曲线其中a、系数、均为整数且满足则为定义在FP上的椭圆曲线。椭圆曲线（modp）定义椭圆曲线离散对数问题令（modp）为一椭圆曲线，令P、Q为E(FP)上的两点，假设点Q由点P生成。在E上的离散对数问题就是要解的k值。定理令E为定义在FP上的椭圆曲线，则E(FP)的个数满足其中误差项定理令椭圆曲线(modp)，则加权投影坐标10

5、.3加权投影坐标性质令椭圆曲线令，为E上的点（加权投影坐标表达式）。而点若P1、P2≠0，且P1≠±P2，则加法公式为若P1=P2，则的公式为定义在Galois域的椭圆曲线10.4定义在Galois域的椭圆曲线定义定义在特征值为2的Non-Supersingular椭圆曲线，可在适当的坐标系选取下表示成加法律”可定义如下：：P＝Q：密码安全曲线10.5密码安全曲线例：令p>3为质数、b为整数，且p

6、b。令椭圆曲线则E为Supersingular曲线。证明：考虑乘法群的Homomorphism：故由Lagrange定理，可

7、得将信息转化为椭圆曲线代码10.6将信息转化为椭圆曲线代码而信息m将对应到E(FP)之某点的x坐标值。然而，m3+am+b为完全平方数的概率为0.5，因此可添加若干位在m上，即使得x3+ax+b为完全平方数，如此便可对应到E(FP)上的一点；而失败的概率，即m’无法对应到的概率是为2-K，其中(m+1)K

8、小，可利用Legendre符号公式计算（4）质因数分解g，得（5）计算故点P(1,65537)的秩为椭圆曲线版的Diffie-Hellman密钥交换算法椭圆曲线版的Diffie-Hellman密钥交换Alice与Bob要用椭圆曲线密码共同约定密钥。（曲线参数约定）约定(E/Fq,P)。Alice选择一正整数A，计算PA=[A]P，将点PA传送给Bob。Bob选择一正整数B，计算PB=[B]P，将点PB传送给Alice。Alice收到PB，计算PK=[A]PB，PK即共同约定的密钥。Bob收到PA，计算PK=[B]PA，P

9、K即共同约定的密钥。椭圆曲线版的ElGamal密码算法椭圆曲线版的ElGamal密码Alice欲加密明文Pm代码成密文PC传送给Bob。（曲线参数约定）约定(E/Fq,P)。（密钥产生）Bob随机选取一个整数B且B与g互质，即gcd(B,g)=1，计算PB=[B]P。公开密钥为(E/Fq,P,PB)，私钥为B。（加密