2 3 2
复旦大学 信息科学与工程学院 通信科学与工程系
• 椭圆曲线普通方程： 椭圆曲线普通方程：
• 无穷远点 ∞(0,Y,0) 无穷远点O • 平常点(x,y)斜率 ： 斜率k： 平常点 斜率
Fx ( x, y ) = a1 y − 3x 2 − 2a 2 x − a 4 Fy ( x, y ) = 2 y + a1 x + a3
复旦大学 信息科学与工程学院 通信科学与工程系
•
公钥加密－ 公钥加密－私钥解密
C1 − kC 2 = M + rK − k (rG ) = M + r ( K − kG ) = M
ling@
网络安全－椭圆曲线加密
17
ECC密钥互换算法 密钥互换算法
① ② ③ ④ ⑤ ⑥ 上的椭圆曲线E、基点P∈ 双方公开选定有限域GF(2k)上的椭圆曲线 、基点 ∈E(GF(2k))， 双方公开选定有限域 上的椭圆曲线 ， n为P的阶，k为二进制位数 为 的阶 的阶， 为二进制位数 Alice随机选取 ，0≤x≤n 随机选取x， 随机选取 Alice发送 A=xP 发送k 发送 Bob随机选取 ，0≤y≤n 随机选取y， 随机选取 Bob发送 B=yP 发送k 发送 Alice计算：kAB=yKA=xyP 计算： 计算 Bob计算： kAB=xKB=xyP 计算： 计算
3
射影平面
• 对普通平面上点 对普通平面上点(x,y)，令x=X/Z，y=Y/Z，Z≠0， ， ， ， ， 则投影为射影平面上的点(X:Y:Z) 则投影为射影平面上的点
– 例如：点(1,3)可投影为 例如： 可投影为(Z:3Z:Z)，可为 可投影为 ，可为(1:3:1),(2.3:6.9:2.3)等 等 – 对普通平面上的直线 对普通平面上的直线ax+by+c=0，同样变换，得到对应于射影平 ，同样变换， 面上的直线为aX+bY+cZ=0 面上的直线为 – 对平行线 对平行线aX+bY+c1Z=0和aX+bY+c1Z=0，易解得 和 ，易解得Z=0，说明无穷 ， 的座标为(X:Y:0) 远点 的座标为
2 3 2 2 3 1 3 2 4 6
– 椭圆曲线方程是一个齐次方程 – 曲线上的每个点都必须是非奇异的（光滑的），偏导 曲线上的每个点都必须是非奇异的（光滑的），偏导 ）， 不同为0 数FX(X,Y,Z)、FY(X,Y,Z)、FZ(X,Y,Z)不同为 、 、 不同为
ling@
– 则给定 和G，根据加法法则，计算 很容易 则给定k和 ，根据加法法则，计算K很容易 – 但反过来，给定 和G，求k就非常困难 但反过来，给定K和 ， 就非常困难 这就是椭圆曲线加密算法的数学依据 – 点G称为基点（base point） 称为基点 称为基点（ ） – k（k<n）为私有密钥（privte key） （ ） 私有密钥（ ） – K为公开密钥（public key) 为公开密钥（
网络安全－椭圆曲线加密
复旦大学 信息科学与工程学院 通信科学与工程系
• ECC－椭圆曲线加密 Ellipse Curve Cryptography －
ling@
2
无穷远点
复旦大学 信息科学与工程学院 通信科学与工程系
• 定义平行线相交于无穷远点 ∞，使平面上所 定义平行线相交于无穷远点P 有直线都统一为有唯一的交点 • 性质： 性质：
复旦大学 信息科学与工程学院 通信科学与工程系
• 有限域 p 有限域F
ling@
网络安全－椭圆曲线加密
12
有限域椭圆曲线示例
y 2 = x 3 + ax + b (mod p )
复旦大学 信息科学与工程学院 通信科学与工程系
• 椭圆曲线 p(a,b)，p为质数，x,y∈[0,p-1] 椭圆曲线E 为质数， ∈ ， 为质数 • 选择两个满足下列约束条件的小于 的非负整数a、b 选择两个满足下列约束条件的小于p的非负整数 、 的非负整数
网络安全－椭圆曲线加密
5
Y 2 Z = X 3 + XZ 2 + Z 3
椭圆曲线示例
Y 2 Z = X 3 + XZ 2 + Z 3
y 2 = x3 + x + 1
Y 2 Z = X 3 − XZ 2
y 2 = x3 − x
复旦大学 信息科学与工程学院 通信科学与工程系
Y 2 Z = X 3 + XZ 2 + Z 3
4a 3 + 27b 2 ≠ 0 (mod p)
• 当p=23，a=b=1时，椭圆曲线: p=23，a=b=1时 椭圆曲线:
P＋Q
-P P
2P
Q
ling@
网络安全－椭圆曲线加密
13
P＋Q
-P P
2P
Q
ling@
网络安全－椭圆曲线加密
14
复旦大学 信息科学与工程学院 通信科学与工程系
椭圆曲线点的阶
n，使得数乘nP=O∞（显然 ，使得数乘 显然(n-1)P=-P ）， 则将n称为 的阶 则将 称为P的阶 称为 • 若n不存在，则P是无限阶的 不存在， 不存在 是无限阶的
在有限域上定义的椭圆曲线上所有的点的阶n都是存在的
复旦大学 信息科学与工程学院 通信科学与工程系
• 如果椭圆曲线上一点 ，存在最小的正整数 如果椭圆曲线上一点P，
ling@ 网络安全－椭圆曲线加密
16
ECC保密通信算法 保密通信算法
① ② ③ ④ ⑤ ⑥ ⑦ Alice选定一条椭圆曲线 ，并取椭圆曲线上一点作为基点 选定一条椭圆曲线E，并取椭圆曲线上一点作为基点G 选定一条椭圆曲线 Alice选择一个私有密钥 （k<n），并生成公开密钥K=kG 选择一个私有密钥k（ ），并生成公开密钥 选择一个私有密钥 ），并生成公开密钥 Alice将E和点 、G传给 和点K、 传给 传给Bob 将 和点 Bob收到信息后，将待传输的明文编码到上的一点 （编码 收到信息后， 收到信息后 将待传输的明文编码到上的一点M（ 方法略），并产生一个随机整数 ），并产生一个随机整数r（ 方法略），并产生一个随机整数 （r<n） ） Bob计算点 1=M+rK和C2=rG 计算点C 计算点 和 Bob将C1、C2传给 传给Alice 将 Alice收到信息后，计算C1-kC2，结果就应该是点M，因为： 收到信息后，计算 结果就应该是点 ，因为： 收到信息后
网络安全 Network Security
椭圆曲线加密
主要内容
• • • • • • 椭圆曲线加密概念 射影平面 椭圆曲线 椭圆曲线加法群 有限域椭圆曲线 椭圆曲线加密方法
复旦大学 信息科学与工程学院 通信科学与工程系
ling@
网络安全－椭圆曲线加密
1
ECC概念 概念
– 基于椭圆曲线理论的公钥加密技术（1985） 基于椭圆曲线理论的公钥加密技术（ ） – 与传统的基于大质数因子分解困难性的加密方法不同， 与传统的基于大质数因子分解困难性的加密方法不同， ECC通过椭圆曲线方程式的性质产生密钥 通过椭圆曲线方程式的性质产生密钥 – ECC 164位的密钥产生一个安全级，相当于 位的密钥产生一个安全级， 位的密钥产生一个安全级 相当于RSA 1024 位密钥提供的保密强度，而且计算量较小， 位密钥提供的保密强度，而且计算量较小，处理速度 更快， 更快，存储空间和传输带宽占用较少
ling@
网络安全－椭圆曲线加密
15
椭圆曲线加密
复旦大学 信息科学与工程学院 通信科学与工程系
• 考虑 考虑K=kG ，其中 、G为椭圆曲线 p(a,b) 其中K、 为椭圆曲线 为椭圆曲线E 上的点， 为 的阶 的阶（ ），k为小于 为小于n 上的点，n为G的阶（nG=O∞ ）， 为小于 的整数
A
B C= -C’
（a）
（b）
如果椭圆曲线上的三个点A、B、C处于同一直线上， 那么其和等于零元，即A+B+C=O∞
ling@ 网络安全－椭圆曲线加密 10
同点加法
P + P + P = 2 P + P = 3P
复旦大学 信息科学与工程学院 通信科学与工程系
• 若有 个相同的点P相加，记作 若有k个相同的点 相加 记作kP 个相同的点 相加，
– 一条直线只有一个无穷远点；一对平行线有公共的无穷远点 一条直线只有一个无穷远点； – 平面上全体无穷远点构成一条无穷远直线
– 任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点） 任何两条不平行的直线有不同的无穷远点（否则会造成有两个交点）
P∞
ling@
网络安全－椭圆曲线加密
复旦大学 信息科学与工程学院 通信科学与工程系
• 阿贝尔（Abel）加法群 阿贝尔（ ）
ling@
（a）
网络安全－椭圆曲线加密 （b）
9
零元与负元
O∞（零元） C’=A+B y2-xy = x3+1 P
复旦大学 信息科学与工程学院 通信科学与工程系
• O∞与-P
P’= -P（负元）
（a）
（b）
ling@
网络安全－椭圆曲线加密
6
非椭圆曲线示例
Y 2Z = X 3 + X 2
Y 2Z = X 3
（a）
（b）
ling@
网络安全－椭圆曲线加密
7
复旦大学 信息科学与工程学院 通信科学与工程系
椭圆曲线普通方程
y + a1 xy + a 3 y = x + a 2 x + a 4 x + a 6
• 一条椭圆曲线是在射影平面上满足威尔斯 特拉斯方程（ 特拉斯方程（Weierstrass）所有点的集合： ）所有点的集合：