18
一、椭圆曲线
4、 GF(2m)上的椭圆曲线
z 除了 GF(p) 上的椭圆曲线，还有定义在 GF(2m) 上的 圆曲线。 z 基于这两种椭圆曲线都可以设计出安全的椭圆曲线 密码。 z 定义：设m是正整数，且b ≠0，称曲线 y2 +xy =x3 +ax2+b ，a,b∈GF(2m) 为GF(2m)上的椭圆曲线。 z 注意：GF(2m)上的椭圆曲线与GF(p)上的椭圆曲线 加法定义不同。
160 位的椭圆曲线密码的安全性相当于 1024 位的 RSA 密 码， 而且运算速度也较快。
27
三、椭圆曲线公钥密码
1、椭圆曲线密码概况
19
一、椭圆曲线
z 举例：g(x)=x4+x+1是GF(2)上的既约多项式，用g(x)构造扩域 GF(24)。取a =α3，b =α14，考虑GF(24)上的椭圆曲线多项式 y2 +xy=x3 +ax2+b=x3 +α3x2+α14 通过穷举，求出其全部解点如下： P1= (0000，1011) P2= (0001，0000) P3= (0001，0001) P4= (0010，1101) P5= (0010，1111) P6= (0011，1100) P7= (0011，1111) P8 = (0101，0000) P9= (0101，0101) P10= (0111，1011) P11= (0111，1100) P12= (1000 , 0001) P13= (1000，1001) P14= (1001，0110) P15= (1001，1111) P16= (1011，0010) P17= (1011，1001) P18= (1100，0000) P19= (1100，1100) P20= (1111，0100) P21= (1111，1011)
17
一、椭圆曲线
G ＝（2，7） 2G ＝（5，2） 3G ＝（8，3） 4G ＝（10，2） 6G ＝（7，9） 5G ＝（3，6） 7G ＝（7，2） 8G ＝（3，5） 9G ＝（10，9） 10G ＝（8，8） 11G ＝（5，9） 12G ＝（2，4） 13G ＝O（ ∞，∞ ） z 在上例中，由于p较小，使GF(p)也较小，故可以利用穷举的 方法求出所有解点。但是，对于一般情况要确切计算椭圆曲 线解点数N的准确值比较困难。 z N满足以下不等式 P+1-2P 1/2≤N≤P+1+2P 1/2 。
22
二、椭圆曲线离散对数问题
③求对数 x 的运算为 x=logαy，1≤x≤p-1 由于上述运算是定义在有限域Fp 上的，所以称为离 散对数运算。 z 从 x 计算 y 是容易的。可是从 y计算 x 就困难得多，利 用目前最好的算法，对于认真选择的p，求解离散对 数问题的计算复杂性为O(p ½)。 z 据此，对于认真选择的、足够大的p，求解离散对数 问题是困难的。
密码学
第十一讲 中国商用公钥密码 SM2加密算法
张焕国 武汉大学计算机学院 空天信息安全与可信计算教育部重点实验室
目录
第一讲 第二讲 第三讲 第四讲 第五讲 第六讲 第七讲 第八讲 第九讲 信息安全概论 密码学的基本概念 数据加密标准（DES） 高级数据加密标准（AES） 中国商用密码SMS4与分组密码应用技术 序列密码基础 祖冲之密码 中国商用密码HASH函数SM3 复习
25
三、椭圆曲线公钥密码
1、椭圆曲线密码的一般情况
z 一些国际标准化组织已把椭圆曲线密码作为新的信 息安全标准。如， IEEE P1363/D4，ANSI F9.62， ANSI F9.63 等标准，分别规范了椭圆曲线密码在 Internet协议安全、电子商务、Web服务器、空间通 信、移动通信、智能卡等方面的应用。 z 我国商用密码采用了椭圆曲线密码，并颁布了椭圆 曲线密码标准算法SM2。
24
二、椭圆曲线离散对数问题
2、椭圆曲线群上的离散对数问题
z 一般情况下，椭圆曲线上的解点所构成的群 E不一 定都是循环群。于是我们希望从中找出一个循环子 群E1 。 z 可以证明， 当循环子群 E1 的阶 n 是足够大的素数 时，这个循环子群中的椭圆离散对数问题是困难 的。 z 基于子群E1的椭圆离散对数问题可以构造密码，并 称为椭圆曲线密码。
8
一、椭圆曲线
1、素域上的椭圆曲线
③定义加法 z 设P(x1，y1)≠Q(x2，y2)，且P和Q不互逆 ，则 P（x1 ，y1）＋Q（x2 ，y2）＝R（x3 ，y3） 。其中 x 3 = λ2 - x1 - x2 ， y3 = λ(x1 –x3) - y1 ， (y2 -y1 ) λ= 。 (x2 -x1 )
10
一、椭圆曲线
1、素域上的椭圆曲线
z 作集合E={全体解点，无穷点O }。 z 可以验证，如上定义的集合E和加法运算构成加法交 换群。 z 复习：群G的定义
G是一个非空集，定义了一种运算，且运算是自封闭的； 运算满足结合律； G中有单位元； G中的元素都有逆元；
11
一、椭圆曲线
z 结果说明，这个群是循环群，P5是群的一个生成元。 z 注意：并不是所有非零元素都是群的生成元，如P12= (1000，0001)的阶为11。
21
二、椭圆曲线离散对数问题
1、对比素域上的离散对数问题
①设p为素数，则模p的剩余构成有限域： Fp= GF(p) ={0,1,2 ,… , p-1} Fp 的非零元素构成乘法循环群Fp*： Fp* ={1,2 ,…, p-1} ={α，α2，α3，… ,αp-1}， 则称α为Fp*的生成元或模 p 的本原元。 ②求α的摸幂运算为: y =αx mod p，1≤x≤p-1,
13
一、圆曲线
3、举例
z 求出mod 11 的平方剩余。
12=1 mod 11 32=9 mod 11 52=25=3 mod 11 72=49=5 mod 11 92=81=4 mod 11 22=4 mod 11 42=16=5 mod 11 62=36=3 mod 11 82=64=9 mod 11 102=100=1 mod 11
所以，mod 11的平方剩余为： {1,3,4,5,9}
14
一、椭圆曲线
x 0 1 2 3 4 5 6 7 8 9 10 x3+x+6 mod 11 6 8 5 3 8 4 8 4 9 7 4 是否是模11平方剩余？ No No Yes Yes No Yes No Yes Yes No Yes y
9
一、椭圆曲线
1、素域上的椭圆曲线
③定义加法 z 当P （x1 ，y1） = Q(x2，y2)时 P（x1 ，y1）＋ Q(x2，y2) ＝2 P（x1 ，y1） ＝R（x3 ，y3）。 其中 x3 = λ2 - 2x1 ， y3 =λ(x1 –x3) - y1 ， (3x12 +a ) λ= 。 (2y1 )
16
一、椭圆曲线
z 由于是加法群，n个元素G相加表示为： G+G+...+G ＝ nG ， 并称为倍点运算。 z 我们取G ＝（2，7）为生成元，2倍点计算如下： 2G =（2，7）+（2，7）=（5，2） z 因 为 λ= （ 3×22+1 ） （ 2×7 ） -1 mod 11 =2×3-1 mod 11=2×4 mod 11=8 。于是， x3 =82-2×2 mod 11=5 ， y3 =8（2-5）-7 mod 11=2 。
4,7 5,6 2,9 2,9 3,8 2,9
15
一、椭圆曲线
z 根据上表可知椭圆曲线 y2=x3+x+6 mod 11 的全部解 点集为： (2，4), (2，7), (3，5), (3，6), (5，2), (5，9), (7，2), (7，9), (8，3), (8，8), (10，2), (10，9)。 再加上无穷远点O，共13的点构成一个加法交换群。 z E={全体解点 ∪ 无穷远点O} z 由于群E的元素个数为13，而13为素数，所以群E是 循环群，而且任何一个非0元素都是生成元。
6
一、椭圆曲线
1、素域上的椭圆曲线
为了利用解点构成交换群，需要引进一个 0 元素，并 定义如下的加法运算： ①定义单位元O 引进一个无穷点 O （∞，∞）， 简记为 O ，作为 0 元 素。 O（∞，∞）＋O（∞，∞）＝0＋0＝0 。 并定义对于所有的解点P（x ，y）， P（x ，y）+O＝O + P（x ，y）＝P（x ，y）。
一、椭圆曲线 二、椭圆曲线离散对数问题 三、椭圆曲线公钥密码 四、中国商用椭圆曲线公钥密码SM2
5
一、椭圆曲线
人们对椭圆曲线的研究已有100多年的历史
1、素域上的椭圆曲线
z 设p是大于3的素数，且4a3+27b2 ≠0 mod p ，称 y2 =x3 +ax+b ， a, b∈GF(p) 为GF（p）上的椭圆曲线。 z 由椭圆曲线可得到一个同余方程： y2 =x3 +ax+b mod p z 其解为一个二元组<x, y>，x, y∈GF(p)，将此二元组 描画到椭圆曲线上便为一个点，故 称其为一个解 点。
23
二、椭圆曲线离散对数问题
2、椭圆曲线群上的离散对数问题
z 设G是椭圆曲线上的一个解点，它的阶为n，t 为一 正整数，且1≤t <n。对于给定的G和t，计算tG＝Q 是容易的。但若已知 G 和 Q 点，要计算出 t则是困难 的。这便是椭圆曲线群上的离散对数问题，简记为 ECDLP。 z 除了几类特殊的椭圆曲线外，对于一般ECDLP目前 尚没有有效求解方法。因子分解和DLP问题都有亚 指数求解算法，而ECDLP尚没有亚指数求解算法。 z 据此，对于认真选择的、足够大的解点群，椭圆曲 线离散对数问题是困难的。