2010-5-14 1
第五章 公钥密码
2010-5-14 2
公钥密码
? 数论简介
? 公钥密码体制的基本概念
? RSA算法
? 椭圆曲线密码体制
2010-5-14 3
RSA算法
RSA Algorithm
2010-5-14 4
RSA的安全性
? |p-q|要大
? p-1,q-1都应有大的素因子。
? e<n且 d<n1/4,则 d能被容易的确定。
2010-5-14 5
对 RSA的攻击－共模攻击
? 每一用户有相同的模数 n
? 设用户的公开密钥分别为 e1,e2,且 e1,e2互素，明
文消息为 m,密文为
? 因为（ e1,e2)=1,用欧几里德算法可求 r e1+s e2=1
假定 r为负数，从而可知由 Euclidean算法可计算
(c1-1)r? c2s=m mod n
nmc
nmc
e
e
m o d
m o d
2
1
2
1
?
?
2010-5-14 6
对 RSA的攻击－低指数攻击
令网中三用户的加密钥 e均选 3,而有不同的模 n1,
n2,n3,若有一用户将消息 x传给三个用户的密文
分别为 y1=x 3 mod n1 x< n1
y2=x 3 mod n2 x< n2
y3=x 3 mod n3 x< n3
一般选 n1,n2,n3互素 (否则, 可求出公因子, 而
降低安全性 ),利用中国余定理, 可从 y1,y2,y3
求出 y=x 3 mod (n1 n2 n3)。 由 x<n1,x<n2,
x<n3,可得 x3< n1 ? n2,? n3,故有xy ?
3
2010-5-14 7
椭圆曲线 (ECC)密码体制
Elliptic Curve Cryptography
2010-5-14 8
概述
? 获得同样的安全性，密钥长度较 RSA短得
多
? 被 IEEE公钥密码标准 P1363采用
2010-5-14 9
椭圆曲线
? 椭圆曲线的曲线方程是以下形式的三次方程
y2+axy+by=x3+cx2+dx+e
a,b,c,d,e是满足某些简单条件的实数。定义中包含一个
称为无穷远点的元素，记为 O.
2010-5-14 10
椭圆曲线加法的定义
? 如果其上的 3个点位于同一直线上，那么
它们的和为 O。
? O为加法单位元，即对 ECC上任一点 P,有
P+O=P
? 设 P1=(x,y)是 ECC上一点，加法逆元定义为
P2=-P1=(x,-y)
? P1,P2连线延长到无穷远，得到 ECC上另一点 O,即
P1,P2,O三点共线，所以 P1+P2+O=O,P1+P2=O,
P2=-P1
? O＋ O＝ O,O=-O
2010-5-14 11
椭圆曲线加法的定义
? Q,R是 ECC上 x坐标不同的两点,Q+R定义为：
画一条通过 Q,R的直线与 ECC交于 P1(交点是
唯一的，除非做的 Q,R点的切线，此时分别
取 P1=Q或 P1=R)。由 Q+R+P1=O,得 Q+R=-
P1
? 点 Q的倍数定义如下：在 Q点做 ECC的一条
切线，设切线与 ECC交于 S,定义
2Q=Q+Q=-S。类似可定义
3Q=Q+Q+Q,…,
? 上述加法满足加法的一般性质，如交换律、
结合律等
2010-5-14 12
有限域上的椭圆曲线
? 曲线方程中的所有系数都是某一有限域 GF(p)中的元素
(p为一大素数 )，最为常用的曲线方程为
y2=x3+ax+b mod(p) (a,b∈ GF(p),4a3+27b2≠0 mod p)
? 例,p=23,a=b=1,4a3+27b2=8 ≠0 (mod23),方程
为 y2=x3+x+1 mod(p),图形为连续图形。我们感兴趣
的是在第一象限的整数点。设 Ep(a,b)表示 ECC上点集
{(x,y)|0≤x<p,0 ≤y<p,且 x,y均为整数 }并上 O.
2010-5-14 13
有限域上的椭圆曲线点集产生
方法
? 对每一 x(0≤x<p 且 x为整数），计算
x3+ax+b mod p
? 决定求出的值在模 p下是否有平方根，如果没
有则椭圆曲线上没有与这一 x对应的点；如果
有，则求出两个平方根。
2010-5-14 14
Ep(a,b)上加法
? 如果 P,Q∈ E p(a,b)
? P+O=P
? 如果 P＝ (x,y),则 (x,y)+(x,-y)＝ O
? P＝ (x1,y1),Q= (x2,y2),P≠-Q,P+Q= (x3,y3)
x3=l2-x1-x2（ mod p）
y3=l(x1-x3)-y1 (mod p)
?
?
?
??
?
?
?
?
?
?
?
?
QP
y
ax
QP
xx
yy
1
2
1
12
12
2
3
l
2010-5-14 15
例,E23(1,1)
? P=(3,10),Q(=9,7)
)12,7(2
23m o d123410)73(6
23m o d730336
23m o d6
4
1
20
5
102
133
:2
)1,1()20,17(
23m o d2016410)173(11
23m o d171099311
23m o d11
2
22
2
1
6
3
39
107
3
2
3
2
23
3
2
3
??
??????
?????
???
?
??
?
????
??????
?????
??
?
?
?
?
?
?
?
P
y
x
P
EQP
y
x
l
l
2010-5-14 16
ECC上的密码
? ECC上的离散对数问题
? 在 ECC构成的交换群 Ep(a,b)上考虑方程 Q＝
kP,P,Q∈E p(a,b),k<p.由 k和 P求 Q容易，由
P,Q求 k则是困难的。
? 由 ECC上离散对数问题可以构造 Diffie-
Hellman密钥交换和 Elgamal密码体制
2010-5-14 17
Diffie-Hellman密钥交换
? 取一素数 p≈2 180,两个参数 a,b,得到 Ep(a,b).
? 取 Ep(a,b)的一个生成元 G(x1,y1),要求 G的阶是一
个非常大的素数。 (阶是满足 nG=O的最小正整
数 n),Ep(a,b)和 G公开,A和 B密钥交换过程如
下
? A选小于 n的整数 nA作为秘密钥，并有 PA=nAG作为
公钥
? B类似选取自己的秘密钥 nB和公开钥 PB
? A和 B分别由 K=nAPB和 K＝ nBPA产生共享的秘密钥
? 攻击者如想获得 K，必须由 PA和 G求出 nA或 PB和
G求出 nB
2010-5-14 18
Elgamal密码体制
? 密钥产生过程
? 选择一个素数 p，以及 g(g <p),x<p,计算公钥
y?gx mod p,(y,g,p)为公钥,x为秘密钥
? 加密过程
? M是发送明文组，选择随机数 k，且 (k,p－ 1)=1，
计算：
C1=g k mod p (随机数 k被加密 )
C2=Myk mod p(明文被随机数 k和公钥 ?加密 )
? 密文由 C1,C2级连构成，即密文 C=C1||C2。
? 解密过程
? M=C2/C1x=My k/gkx=Mgxk/gkx mod p
2010-5-14 19
ECC实现 Elgamal密码体制
? 选取一条椭圆曲线，得到 Ep(a,b)。将明文消息
通过编码嵌入曲线上得到点 pm
? 取 Ep(a,b)的生成元 G,Ep(a,b)和 G为公开参数
? 用户选取 nA为秘密钥,PA=nAG为公开钥。
? 加密：选随机正整数 k，密文为
Cm=(kG,Pm+kPA)
? 解密,Pm+kPA-nAkG=Pm
2010-5-14 20
椭圆曲线密码体制的优点
? 安全性高
? 攻击有限域上的离散对数可用指数积分法，运算
复杂度为 。 对 ECC上离散对
数攻击并不有效。
? 攻击 ECC上离散对数问题的方法只有大步小步法，
复杂度为 。 pmax是 ECC形成的
交换群的阶的最大素因子，因此 ECC上的密码体
制比基于有限域上离散对数问题的公钥体制更安
全
3 2)lo g) ( lo g( lo g( e x p ppO
))( e x p ( lo g m a xpO
2010-5-14 21
椭圆曲线密码体制的优点
? 密钥量小
? 实现相同安全性条件下,ECC所需密钥量远
下雨有限域上离散对数问题的公钥体制的密
钥量
? 灵活性好
? 通过改变参数可以获得不同的曲线，具有丰
富的群结构和多选择性
2010-5-14 22
ECC与 RSA/DSA在同等安全条
件下所需密钥长度
RSA/DSA 512 768 1024 2048 2100
0
ECC 106 132 160 211 600
第五章 公钥密码
2010-5-14 2
公钥密码
? 数论简介
? 公钥密码体制的基本概念
? RSA算法
? 椭圆曲线密码体制
2010-5-14 3
RSA算法
RSA Algorithm
2010-5-14 4
RSA的安全性
? |p-q|要大
? p-1,q-1都应有大的素因子。
? e<n且 d<n1/4,则 d能被容易的确定。
2010-5-14 5
对 RSA的攻击－共模攻击
? 每一用户有相同的模数 n
? 设用户的公开密钥分别为 e1,e2,且 e1,e2互素，明
文消息为 m,密文为
? 因为（ e1,e2)=1,用欧几里德算法可求 r e1+s e2=1
假定 r为负数，从而可知由 Euclidean算法可计算
(c1-1)r? c2s=m mod n
nmc
nmc
e
e
m o d
m o d
2
1
2
1
?
?
2010-5-14 6
对 RSA的攻击－低指数攻击
令网中三用户的加密钥 e均选 3,而有不同的模 n1,
n2,n3,若有一用户将消息 x传给三个用户的密文
分别为 y1=x 3 mod n1 x< n1
y2=x 3 mod n2 x< n2
y3=x 3 mod n3 x< n3
一般选 n1,n2,n3互素 (否则, 可求出公因子, 而
降低安全性 ),利用中国余定理, 可从 y1,y2,y3
求出 y=x 3 mod (n1 n2 n3)。 由 x<n1,x<n2,
x<n3,可得 x3< n1 ? n2,? n3,故有xy ?
3
2010-5-14 7
椭圆曲线 (ECC)密码体制
Elliptic Curve Cryptography
2010-5-14 8
概述
? 获得同样的安全性，密钥长度较 RSA短得
多
? 被 IEEE公钥密码标准 P1363采用
2010-5-14 9
椭圆曲线
? 椭圆曲线的曲线方程是以下形式的三次方程
y2+axy+by=x3+cx2+dx+e
a,b,c,d,e是满足某些简单条件的实数。定义中包含一个
称为无穷远点的元素，记为 O.
2010-5-14 10
椭圆曲线加法的定义
? 如果其上的 3个点位于同一直线上，那么
它们的和为 O。
? O为加法单位元，即对 ECC上任一点 P,有
P+O=P
? 设 P1=(x,y)是 ECC上一点，加法逆元定义为
P2=-P1=(x,-y)
? P1,P2连线延长到无穷远，得到 ECC上另一点 O,即
P1,P2,O三点共线，所以 P1+P2+O=O,P1+P2=O,
P2=-P1
? O＋ O＝ O,O=-O
2010-5-14 11
椭圆曲线加法的定义
? Q,R是 ECC上 x坐标不同的两点,Q+R定义为：
画一条通过 Q,R的直线与 ECC交于 P1(交点是
唯一的，除非做的 Q,R点的切线，此时分别
取 P1=Q或 P1=R)。由 Q+R+P1=O,得 Q+R=-
P1
? 点 Q的倍数定义如下：在 Q点做 ECC的一条
切线，设切线与 ECC交于 S,定义
2Q=Q+Q=-S。类似可定义
3Q=Q+Q+Q,…,
? 上述加法满足加法的一般性质，如交换律、
结合律等
2010-5-14 12
有限域上的椭圆曲线
? 曲线方程中的所有系数都是某一有限域 GF(p)中的元素
(p为一大素数 )，最为常用的曲线方程为
y2=x3+ax+b mod(p) (a,b∈ GF(p),4a3+27b2≠0 mod p)
? 例,p=23,a=b=1,4a3+27b2=8 ≠0 (mod23),方程
为 y2=x3+x+1 mod(p),图形为连续图形。我们感兴趣
的是在第一象限的整数点。设 Ep(a,b)表示 ECC上点集
{(x,y)|0≤x<p,0 ≤y<p,且 x,y均为整数 }并上 O.
2010-5-14 13
有限域上的椭圆曲线点集产生
方法
? 对每一 x(0≤x<p 且 x为整数），计算
x3+ax+b mod p
? 决定求出的值在模 p下是否有平方根，如果没
有则椭圆曲线上没有与这一 x对应的点；如果
有，则求出两个平方根。
2010-5-14 14
Ep(a,b)上加法
? 如果 P,Q∈ E p(a,b)
? P+O=P
? 如果 P＝ (x,y),则 (x,y)+(x,-y)＝ O
? P＝ (x1,y1),Q= (x2,y2),P≠-Q,P+Q= (x3,y3)
x3=l2-x1-x2（ mod p）
y3=l(x1-x3)-y1 (mod p)
?
?
?
??
?
?
?
?
?
?
?
?
QP
y
ax
QP
xx
yy
1
2
1
12
12
2
3
l
2010-5-14 15
例,E23(1,1)
? P=(3,10),Q(=9,7)
)12,7(2
23m o d123410)73(6
23m o d730336
23m o d6
4
1
20
5
102
133
:2
)1,1()20,17(
23m o d2016410)173(11
23m o d171099311
23m o d11
2
22
2
1
6
3
39
107
3
2
3
2
23
3
2
3
??
??????
?????
???
?
??
?
????
??????
?????
??
?
?
?
?
?
?
?
P
y
x
P
EQP
y
x
l
l
2010-5-14 16
ECC上的密码
? ECC上的离散对数问题
? 在 ECC构成的交换群 Ep(a,b)上考虑方程 Q＝
kP,P,Q∈E p(a,b),k<p.由 k和 P求 Q容易，由
P,Q求 k则是困难的。
? 由 ECC上离散对数问题可以构造 Diffie-
Hellman密钥交换和 Elgamal密码体制
2010-5-14 17
Diffie-Hellman密钥交换
? 取一素数 p≈2 180,两个参数 a,b,得到 Ep(a,b).
? 取 Ep(a,b)的一个生成元 G(x1,y1),要求 G的阶是一
个非常大的素数。 (阶是满足 nG=O的最小正整
数 n),Ep(a,b)和 G公开,A和 B密钥交换过程如
下
? A选小于 n的整数 nA作为秘密钥，并有 PA=nAG作为
公钥
? B类似选取自己的秘密钥 nB和公开钥 PB
? A和 B分别由 K=nAPB和 K＝ nBPA产生共享的秘密钥
? 攻击者如想获得 K，必须由 PA和 G求出 nA或 PB和
G求出 nB
2010-5-14 18
Elgamal密码体制
? 密钥产生过程
? 选择一个素数 p，以及 g(g <p),x<p,计算公钥
y?gx mod p,(y,g,p)为公钥,x为秘密钥
? 加密过程
? M是发送明文组，选择随机数 k，且 (k,p－ 1)=1，
计算：
C1=g k mod p (随机数 k被加密 )
C2=Myk mod p(明文被随机数 k和公钥 ?加密 )
? 密文由 C1,C2级连构成，即密文 C=C1||C2。
? 解密过程
? M=C2/C1x=My k/gkx=Mgxk/gkx mod p
2010-5-14 19
ECC实现 Elgamal密码体制
? 选取一条椭圆曲线，得到 Ep(a,b)。将明文消息
通过编码嵌入曲线上得到点 pm
? 取 Ep(a,b)的生成元 G,Ep(a,b)和 G为公开参数
? 用户选取 nA为秘密钥,PA=nAG为公开钥。
? 加密：选随机正整数 k，密文为
Cm=(kG,Pm+kPA)
? 解密,Pm+kPA-nAkG=Pm
2010-5-14 20
椭圆曲线密码体制的优点
? 安全性高
? 攻击有限域上的离散对数可用指数积分法，运算
复杂度为 。 对 ECC上离散对
数攻击并不有效。
? 攻击 ECC上离散对数问题的方法只有大步小步法，
复杂度为 。 pmax是 ECC形成的
交换群的阶的最大素因子，因此 ECC上的密码体
制比基于有限域上离散对数问题的公钥体制更安
全
3 2)lo g) ( lo g( lo g( e x p ppO
))( e x p ( lo g m a xpO
2010-5-14 21
椭圆曲线密码体制的优点
? 密钥量小
? 实现相同安全性条件下,ECC所需密钥量远
下雨有限域上离散对数问题的公钥体制的密
钥量
? 灵活性好
? 通过改变参数可以获得不同的曲线，具有丰
富的群结构和多选择性
2010-5-14 22
ECC与 RSA/DSA在同等安全条
件下所需密钥长度
RSA/DSA 512 768 1024 2048 2100
0
ECC 106 132 160 211 600
