9.5椭圆曲线公钥体制
1．椭圆曲线
? 定义 9.5.1：设 p是一个大于 3的素数，在
Zp上的椭圆曲线 y2=x3+ax+b 由一个基
于同余式 y2=x3+ax+b modp的解集（ x，
y） ∈ Zp*Zp和一个称为无穷远点的特定
点 O组成，这里的 a,b∈ Zp是二个满足
4a+27b≡ 0 modp 的常数。
椭圆曲线上的运算
? 设 P=(x1,y1) ∈ E,Q=(x2,y2) ∈ E,若
x1=x2且 y1=-y2,那么 P+Q=O;否则
P+Q=(x3,y3),这里的 x3=λ2-x1-x2,y3=λ
(x1-x3)-y1,
x3=
?
?
?
?
?
?
?
?
?
?
?
?
QP
y
ax
Q
xx
yy
如果
如果
1
2
1
12
12
2
3
P
2．椭圆曲线密码体制
定理 9.5.1（ Hasse定理）：如果 E是定义在
域 GF(q)上的椭圆曲线,N是 E上的点 (x,y)
∈ GF(q)的数目，则
qqN 2|)1(| ???
系统参数；设 E 是一个定义在 Z
p
(P>3 的素数 ) 上的椭圆曲线,令
?
?
E,则由
?
生成的子群 H 满足 其上的离散对数问题是难处理的,选取 a, 计算
?
=a
?
,则
私有密钥,a,
公开密钥：
?
，
?
,p 。
加密算法,对于明文 x,随机选取正整数 k
?
Z
1?p
,
e
1
k
( x,k) = ( y
1
,y
2
),其中 y
1
=k
?
,y
2
= x + k
?
。
解密算法,d
2
k
(y
1
,y
2
) =y
2
- ay
1
E L G a m a l 密 码 体 制 的 椭 圆 曲 线 形 式
椭圆曲线密码体制有如下的一些特点,
? 1.在安全性相当的前提下,可使用较短的密钥,
? 2.椭圆曲线密码体制是建立在一个不同于大整数分解及素
域乘法群离散对数问题的数学难题之上,
? 3 椭圆曲线资源丰富,同一个有限域上存在着大量不同的
椭圆曲线,这为安全性增加了额外的保证。
? 4,在执行速度方面,椭圆曲线密码体制较对应的离散对数
体制要快,且在签名和解密方面较 RSA 快,但在签名验证
和加密方面较 RSA 慢,
? 5．椭圆曲线密码体制的安全性分析成果并不丰硕, 也许这
可视为椭圆曲线密码体制具有高强度的一种证据,因此,大
多数密码学家对这种密码体制的前景持乐观态度,
9.6其他公开密钥密码体制
9.6.1Goldwasser-
Micali概率公开密钥
密码系统
系统参数,A 随机选取两个大的强素数 p,q,计算 n = pq,随机 选取数 y 且满足
J( y,n ) =1,J ( y,p) = J ( y,q) = - 1,则
公开密钥,y,n 。
私有密钥,p,q 。
加密算法：若 B 想给 A 传送明文 m, m 表示成二进制形式，即 m = ( m
1
,m
2
,…,m
k
)
?
F
k
2
,
对于 m
i
（ 0
?
i
?
k ）,任意选取 x
i
?
[ 1,n - 1],
当 m
i
=1 时, B 计算 C
i
= yx
2
i
m od n 。
当 m
i
=0 时, B 计算 C
i
= x
2
i
m od n 。
则密文为 E(m ) = ( C
1
,C
2
,…,C
k
) 。
解密算法,A 收到 B 传来的密文 ( C
1
,C
2
,…,C
k
) 后，对每一个 C
i
（ 0
?
i
?
k ），计算 J( C
i
,p)
和 J ( C
i
,q ) 。
当 J( C
i
,p) = J ( C
i
,q ) = - 1,则 m
i
为 =1
当 J ( C
i
,p) = J ( C
i
,q) = 1,则 m
i
为 =0
( m
1
,m
2
,…,m
k
) 即为明文 m 。
G o l d w a s s e r - M i c a l i 概 率 公 开 密 钥 密 码 系 统
Goldwasser-Micali概率公开密钥密码系统
的安全性分析与讨论
? 对于攻击者来说，当他截获到密文
(C1,C2,…,Ck)时，他能求出 J(Ci,n),但当
mi=0,J(Ci,n)= J(xi2,n)=1，当 mi=1,
J(yxi2,n)= J(y,n)J(xi2,n)=1,攻击者无法获
得其它的任何信息，而对 A来说，因为他
拥有私有密钥 p和 q,可求出 J(Ci,p)，
J(Ci,q),从而得到明文。
? 从传输效率来看，由于明文对应至 [1,n-1]
之间，故其效率为,|n|为 n的长度。效率
非常差 。
9.6.2Merkle-Hellman背包公
钥密码体制
系统参数,A 任选一个超递增序列 T= ( t
1
,t
2
,…,t
n
),整数 W,N 满足 N>
?
?
n
i
i
t
1
且 gcd( W,N ) = 1
将 递增序列 T 转化成为伪随机序列 G = ( g
1
,g
2
,…,g
n
),这里的 g
i
( i = 1,2,…,n) 满足
g
i
=t
i
W m odN,
公开密钥,G,
私有密钥,T,N,W 。
加密算法：对于待加密消息 m = ( m
1
,m
2
,…,m
n
)
?
F
n
2
,B 想将之传给 A, B 先找出 A 的公开密
钥 G,则密文为 V=
?
?
n
i
ii
gm
1
。
解密算法：收到密文 V 后，计算
V
'
= V W
1?
=
?
?
n
i
ii
tm
1
WW
1?
=
?
?
n
i
ii
tm
1
m odN
由于 T 是超递增序列，利用超递增序列算法就可算出明文 m 。
9.6.3有限自动机公开密钥密码
体制
? 此类体制是基于分解两个有限自动机的
合成也是困难的而构造的，尤其是当其
中的一个或两个为非线性时，难度就会
更大。
小结
? 公钥密码学是现代密码学的很重要的组
成部分，本章主要介绍了公钥密码的思
想和几种基于计算复杂性的公钥密码体
制。
? 公钥密码的思想
? RSA体制
? 基于纠错码的公钥密码体制
? 基于椭圆曲线的公钥密码体制。
1．椭圆曲线
? 定义 9.5.1：设 p是一个大于 3的素数，在
Zp上的椭圆曲线 y2=x3+ax+b 由一个基
于同余式 y2=x3+ax+b modp的解集（ x，
y） ∈ Zp*Zp和一个称为无穷远点的特定
点 O组成，这里的 a,b∈ Zp是二个满足
4a+27b≡ 0 modp 的常数。
椭圆曲线上的运算
? 设 P=(x1,y1) ∈ E,Q=(x2,y2) ∈ E,若
x1=x2且 y1=-y2,那么 P+Q=O;否则
P+Q=(x3,y3),这里的 x3=λ2-x1-x2,y3=λ
(x1-x3)-y1,
x3=
?
?
?
?
?
?
?
?
?
?
?
?
QP
y
ax
Q
xx
yy
如果
如果
1
2
1
12
12
2
3
P
2．椭圆曲线密码体制
定理 9.5.1（ Hasse定理）：如果 E是定义在
域 GF(q)上的椭圆曲线,N是 E上的点 (x,y)
∈ GF(q)的数目，则
qqN 2|)1(| ???
系统参数；设 E 是一个定义在 Z
p
(P>3 的素数 ) 上的椭圆曲线,令
?
?
E,则由
?
生成的子群 H 满足 其上的离散对数问题是难处理的,选取 a, 计算
?
=a
?
,则
私有密钥,a,
公开密钥：
?
，
?
,p 。
加密算法,对于明文 x,随机选取正整数 k
?
Z
1?p
,
e
1
k
( x,k) = ( y
1
,y
2
),其中 y
1
=k
?
,y
2
= x + k
?
。
解密算法,d
2
k
(y
1
,y
2
) =y
2
- ay
1
E L G a m a l 密 码 体 制 的 椭 圆 曲 线 形 式
椭圆曲线密码体制有如下的一些特点,
? 1.在安全性相当的前提下,可使用较短的密钥,
? 2.椭圆曲线密码体制是建立在一个不同于大整数分解及素
域乘法群离散对数问题的数学难题之上,
? 3 椭圆曲线资源丰富,同一个有限域上存在着大量不同的
椭圆曲线,这为安全性增加了额外的保证。
? 4,在执行速度方面,椭圆曲线密码体制较对应的离散对数
体制要快,且在签名和解密方面较 RSA 快,但在签名验证
和加密方面较 RSA 慢,
? 5．椭圆曲线密码体制的安全性分析成果并不丰硕, 也许这
可视为椭圆曲线密码体制具有高强度的一种证据,因此,大
多数密码学家对这种密码体制的前景持乐观态度,
9.6其他公开密钥密码体制
9.6.1Goldwasser-
Micali概率公开密钥
密码系统
系统参数,A 随机选取两个大的强素数 p,q,计算 n = pq,随机 选取数 y 且满足
J( y,n ) =1,J ( y,p) = J ( y,q) = - 1,则
公开密钥,y,n 。
私有密钥,p,q 。
加密算法：若 B 想给 A 传送明文 m, m 表示成二进制形式，即 m = ( m
1
,m
2
,…,m
k
)
?
F
k
2
,
对于 m
i
（ 0
?
i
?
k ）,任意选取 x
i
?
[ 1,n - 1],
当 m
i
=1 时, B 计算 C
i
= yx
2
i
m od n 。
当 m
i
=0 时, B 计算 C
i
= x
2
i
m od n 。
则密文为 E(m ) = ( C
1
,C
2
,…,C
k
) 。
解密算法,A 收到 B 传来的密文 ( C
1
,C
2
,…,C
k
) 后，对每一个 C
i
（ 0
?
i
?
k ），计算 J( C
i
,p)
和 J ( C
i
,q ) 。
当 J( C
i
,p) = J ( C
i
,q ) = - 1,则 m
i
为 =1
当 J ( C
i
,p) = J ( C
i
,q) = 1,则 m
i
为 =0
( m
1
,m
2
,…,m
k
) 即为明文 m 。
G o l d w a s s e r - M i c a l i 概 率 公 开 密 钥 密 码 系 统
Goldwasser-Micali概率公开密钥密码系统
的安全性分析与讨论
? 对于攻击者来说，当他截获到密文
(C1,C2,…,Ck)时，他能求出 J(Ci,n),但当
mi=0,J(Ci,n)= J(xi2,n)=1，当 mi=1,
J(yxi2,n)= J(y,n)J(xi2,n)=1,攻击者无法获
得其它的任何信息，而对 A来说，因为他
拥有私有密钥 p和 q,可求出 J(Ci,p)，
J(Ci,q),从而得到明文。
? 从传输效率来看，由于明文对应至 [1,n-1]
之间，故其效率为,|n|为 n的长度。效率
非常差 。
9.6.2Merkle-Hellman背包公
钥密码体制
系统参数,A 任选一个超递增序列 T= ( t
1
,t
2
,…,t
n
),整数 W,N 满足 N>
?
?
n
i
i
t
1
且 gcd( W,N ) = 1
将 递增序列 T 转化成为伪随机序列 G = ( g
1
,g
2
,…,g
n
),这里的 g
i
( i = 1,2,…,n) 满足
g
i
=t
i
W m odN,
公开密钥,G,
私有密钥,T,N,W 。
加密算法：对于待加密消息 m = ( m
1
,m
2
,…,m
n
)
?
F
n
2
,B 想将之传给 A, B 先找出 A 的公开密
钥 G,则密文为 V=
?
?
n
i
ii
gm
1
。
解密算法：收到密文 V 后，计算
V
'
= V W
1?
=
?
?
n
i
ii
tm
1
WW
1?
=
?
?
n
i
ii
tm
1
m odN
由于 T 是超递增序列，利用超递增序列算法就可算出明文 m 。
9.6.3有限自动机公开密钥密码
体制
? 此类体制是基于分解两个有限自动机的
合成也是困难的而构造的，尤其是当其
中的一个或两个为非线性时，难度就会
更大。
小结
? 公钥密码学是现代密码学的很重要的组
成部分，本章主要介绍了公钥密码的思
想和几种基于计算复杂性的公钥密码体
制。
? 公钥密码的思想
? RSA体制
? 基于纠错码的公钥密码体制
? 基于椭圆曲线的公钥密码体制。
