② 设P1=(x,y)是椭圆曲线上的一点, 它的加法逆元定义为P2=P1=(x, -y)。
这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的 另一点O，即椭圆曲线上的3点P1、P2，O共线，所以 P1+P2+O=O，P1+P2=O，即P2=-P1。
由O+O=O，还可得O=-O
2020/4/9
y2+axy+by=x3+cx2+dx+e
(4.1)
其中a，b，c，d，e是满足某些简单条件的实数。 定义中包括一个称为无穷点的元素，记为O。
图4.4 是椭圆曲线的两个例子。
2020/4/9
11
有限域上的椭圆曲线 椭圆曲线
4
P1
2 R Q
-2 -1
01 2 3
-2
- P1 -4
4
P1
2 R Q -2 -1 0 1 2 3
-2
-4
-P1
(a) y2=x3-x
(b) y2=x3+x+1
图4.4 椭圆曲线的两个例子
2020/4/9
12
有限域上的椭圆曲线
椭圆曲线
椭圆曲线上的加法运算定义如下： 如果其上的3个点位于同 一直线上，那么它们的和为O。
ቤተ መጻሕፍቲ ባይዱ
进一步可如下定义椭圆曲线上的加法律（加法法则）：
① O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。
(4.2)
2020/4/9
15
有限域上的椭圆曲线
有限域上的椭圆曲线
例4.12 p=23，a=b=1，4a3+27b2(mod 23)≡8≠0 ，方程 (4.2)为y2≡x3+x+1，其图形是连续曲线，由图4.4(b)所示。 然而我们感兴趣的是曲线在第一象限中的整数点。设 Ep(a,b)表示方程(4.2)所定义的椭圆曲线上的点集 {(x,y)|0≤x<p,0≤y<p，且x,y均为整数}并上无穷远点O。本 例中E23(1,1)由表4.6给出，表中未给出O
2020/4/9
16
有限域上的椭圆曲线 有限域上的椭圆曲线
一般来说，Ep(a,b)由以下方式产生：
①
对每一x(0≤x<p且x为整数），计算
x3+ax+b(mod p)。
② 决定①中求得的值在模p下是否有平方根， 如果没有，则曲线上没有与这一x相对应的点；如 果有，则求出两个平方根（y=0 时只有一个平方 根）。
2020/4/9
17
有限域上的椭圆曲线 有限域上的椭圆曲线
Ep(a,b)上的加法定义如下：
设P，Q∈Ep(a,b)，则
13
有限域上的椭圆曲线
椭圆曲线
③ 设Q和R是椭圆曲线上x坐标不同的两点，Q+R的定义 如下： 画一条通过Q、R的直线与椭圆曲线交于P1（这一 交点是惟一的，除非所做的直线是Q点或R点的切线，此时 分别取P1=Q和P1=R）。由Q+R+P1=O得Q+R=-P1。 ④ 点Q的倍数定义如下： 在Q点做椭圆曲线的一条切线， 设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可 定义3Q=Q+Q+Q+，…，等。 以上定义的加法具有加法运算的一般性质，如交换律、 结合律等。
椭圆曲线密码体制
为保证RSA算法的安全性，它的密钥长度需一 再增大，使得它的运算负担越来越大。相比之下， 椭圆曲线密码体制ECC（elliptic curve cryptography）可用短得多的密钥获得同样的安全 性，因此具有广泛的应用前景。ECC已被IEEE公 钥密码标准P1363采用。
2020/4/9
2020/4/9
14
有限域上的椭圆曲线 有限域上的椭圆曲线
密码中普遍采用的是有限域上的椭圆曲线，有限域上 的椭圆曲线是指曲线方程定义式(4.1)中，所有系数都是某 一有限域GF(p)中的元素（其中p为一大素数）。其中最为 常用的是由方程
y2≡x3+ax+b(mod p)
(a,b∈GF(p),4a3+27b2(mod p)≠0) 定义的曲线。
则称F为一个域．
2020/4/9
8
有限域
定义4.3.2 有限个元素构成的域称为有限域．域中元素 的个数称为有限域的阶．
例：当p是素数时，模p剩余类集合
{0,1,2K, p1}
构成p阶有限域GF(p) ，这也是最简单的一种有限域．
2020/4/9
9
有限域
定义4.3.3 设G是群，a是G中的一个元素，如果存在正 整数m，使得am=1，则称a是有限阶的元素，把最小的满 足am=1 的正整数m叫做元素a的阶，用|a|表示。
4
轻量级密码算法——ECC
ECC特别适用于诸如以下实现中：
➢ 无线Modem的实现； ➢ web服务器的实现； ➢ 集成电路卡的实现； ➢ ……
轻量级密码算法——ECC
➢ 安全性高，其安全性依赖于椭圆曲线上的离散 对数困难问题；
➢ 运算速度快； ➢ 便于软硬件实现。
轻量级密码算法——ECC
正是由于椭圆曲线具有丰富的群结构和多选择性，并可在保持和 RSA/DSA体制同样安全性能的前提下大大缩短密钥长度（目前160比特 足以保证安全性），因而在密码领域有着广阔的应用前景。表4.9给出 了椭圆曲线密码体制和RSA/DSA体制在保持同等安全的条件下各自所 需的密钥的长度。
域
定义4.3.1 若代数系统<F, +, •>的二元运算满足: 1） <F, +>是交换群； 2） <F-{0}, •> 是交换群,其中0是+运算的单位元； 3）乘法在加法+运算上满足分配律，即对于任意a，b，
cF，有
a• (b+c) = a•b+a•c和(b+c) •a=b•a+c•a；
定义4.3.4 q阶有限域中阶为q1的元素称为本原域元素，
简称本原元．
本原元的意义是很明显的．如果q阶有限域中存在本原元a，
则所有非零元构成一个由a生成的q1阶循环群．那么q阶
有限域就可以表示为
{ 0，1，a1，a2，…，aq2}．
2020/4/9
10
有限域上的椭圆曲线 椭圆曲线
椭圆曲线并非椭圆，之所以称为椭圆曲线是因为 它的曲线方程与计算椭圆周长的方程类似。一般来 讲，椭圆曲线的曲线方程是以下形式的三次方程：
物联网感知层安全
课前回顾
3 物联网感知层安全 3.1物联网感知层安全概述 3.2RFID安全 RFID安全密码协议
本次课学习内容
3.2RFID安全 轻量级密码算法 1 椭圆曲线密码算法 2 RC4算法 3 Present算法 4 SM3算法 国家商用密码算法简介
轻量级密码算法——ECC