第九章 公钥密码学
对称密码体制的缺陷,
1 ） 密钥分配问题 通信双方要进行加密通信，需要通过秘密
的安全信道协商加密密钥，而这种安全信道可能很难实现；
2 ） 密钥管理问题 在有多个用户的网络中，任何两个用户之
间都需要有共享的秘密钥，当网络中的用户 n 很大时，需
要管理的密钥数目是非常大
2/)1( ?nn
。
3 ） 没有签名功能,当主体 A 收到主体 B 的电子文挡（电子
数据）时，无法向第三方证明此电子文档确实来源于 B 。
9.1公钥密码学思想
? 定义 9.1.1一个公钥密码体制是这样的一个 5元组 {M,C,K,EK,DK}，
且满足如下的条件,
? 1.M是可能消息的集合；
? 2.C是可能的密文的集合；
? 3,密钥空间 K是一个可能密钥的有限集；
? 4．对每一个 K={K1,K2} ∈ K，都对应一个加密算法 EK1 ∈ E,
EK1:M→ C和解密算法 DK2 ∈ D,DK2:C → M,满足对于任意的 m ∈ M,
都有 c= EK1（ m）,m= DK2(c)=DK2(EK1（ m） )=m；
? 5．对于所有的 KK，在已知 E的情况下推出 D是计算上不可能的；
? 对每一个 K∈ K，函数 EK1和 DK2都是多项式时间可计算的函数。
EK1是一个公开函数,K1 称作公钥；而 DK2是一个秘密函数,K2称作
私钥，由用户秘密地保存。
? public-key/two-key/asymmetric 包括两
个密钥,
? 公开密钥 (a public-key),可以被任何人
知道,用于加密或验证签名
? 私钥 ( private-key),只能被消息的接收
者或签名者知道,用于解密或签名
? 加密或验证签名者不能解密或多或生成签
名,
? 是密码学几千年历史中最有意义的结果
3.公钥加密方案
4.公钥密码理论
? 由私钥及其他密码信息容易计算出公开密钥 (a
polynomial time (P-time) problem)
? 由公钥及算法描述,计算私钥是难的 (an NP-
time problem)
? 因此,公钥可以发布给其他人 (wishing to
communicate securely with its owner )
? 密钥分配问题不是一个容易的问题 (the key
distribution problem )
5.公钥算法分类
? Public-Key Distribution Schemes (PKDS)
? 用于交换秘密信息 (依赖于双方主体 )
? 常用于对称加密算法的密钥
? Public Key Encryption (PKE)
? 用于加密任何消息
? 任何人可以用公钥加密消息
? 私钥的拥有者可以解密消息
? 任何公钥加密方案能够用于密钥分配方案 PKDS
? 许多公钥加密方案也是数字签名方案
? Signature Schemes
? 用于生成对某消息的数字签名
? 私钥的拥有者生成数字签名
? 任何人可以用公钥验证签名
6.公钥的安全性
? 依赖于足够大大的困难性差别
? 类似与对称算法,穷搜索在理论上是能够破解
公钥密码 exhaustive search
? 但实际上,密钥足够长 (>512bits)
? 一般情况下,有一些已知的困难问题 (hard
problem”
? 要求足够大的密钥长度 (>512 bits)
? 导致加密速度比对称算法慢
2,RSA (Rivest,Shamir,Adleman)
? 使用最广泛的公钥加密算法
? Rivest,Shamir & Adleman (RSA) in
1977
? R L Rivest,A Shamir,L Adleman,"On
Digital Signatures and Public Key
Cryptosystems",Communications of the
ACM,vol 21 no 2,pp120-126,Feb 1978
?
3,RSA Setup
? 每个用户生成自己的公钥 \私钥对,
? 选择两个随机大素数 (~100 digit),p,q
? 计算模数 N=p.q
? 选择一个随机加密密钥匙 e, e<N,
gcd(e,?(N))=1
? 解下列同余方程,求解密密钥 d,
? e.d=1 mod ?(N) and 0<=d<=N
? 公开加密密钥, Kr={er,Nr}
? 保存其解密似钥,
? K-1r={d,p,q}
4。 RSA 参数选择
? 需要选择足够大的素数 p,q
? 通常选择小的加密指数 e,且与 ?(N) 互素
? e 对所有用户可以是相同的
? 最初建议使用 e=3
? 现在 3太小
? 常使用 e=216-1 = 65535
? 解密指数比较大
5,RSA Usage
? 要加密消息 M,发送者要得到接收者的
公钥 Kr={er,Nr}
? 计算, C=Mer mod Nr,where 0<=M<N
? 为解密 C,接收者使用私钥
? K-1r={d,p,q}
? 计算, M=Cd mod Nr
6,RSA理论
? RSA 基于 Fermat's Theorem,
? if N = pq where p,q are primes,then,
X?(N) = 1 mod N
? for all x not divisible by p or q,ie
gcd(x,?(N))=1
? where ?(N)=(p-1)(q-1)
? 但在 RSA 中,e & d 是特殊选择的
? ie e.d=1 mod ?(N) 或 e.d=1+R?(N)
? hence have,
M = Cd = Me.d = M1+R?(N) =
M1.(M?(N))R = M1.(1)R = M1 mod N
?
8。 RSA举例 例子,
1,选素数 p=47和 q＝ 71，得 n=3337,
? (n)=46× 70＝ 3220；
2,选择 e=79，求得私钥 d=e -1 ? 1019(mod
3220）。
3,公开 n=3337和 e=79,
4,现要发送明文 688，计算,
68879(mod 3337)=1570
5.收到密文 1570后，用私钥 d＝ 1019进行解密,
15701019（ mod 3337)=688
9。 RSA 安全性
? RSA 安全性基于计算 ?(N)的困难性
? 要求分解模 N
10,RSA的实现问题
? 需要计算模 300 digits (or 1024+ bits)
的乘法
? 计算机不能直接处理这么大的数
? （计算速度很慢）
? 需要考虑其它技术，加速 RSA的实现
11,RSA – 的快速实现
? 加密很快，指数小
? 解密比较慢，指数较大
? 利用中国剩余定理 CRT,
? CRT 对 RSA解密算法生成两个解密方程 （利用 M = Cd
mod R ）
? 即, M1 = M mod p = (C mod p)d mod (p-1)
? M2 = M mod q = (C mod q)d mod (q-1)
? 解方程 M = M1 mod p
? M = M2 mod q
? 具有唯一解（利用 CRT ）,
?,M = [((M2 +q - M1)u mod q] p + M1
? 其中 p.u mod q = 1
9.2.3概率素性检测
? 定义 9.2.3：如果 P是素数，且 a小于 p,如果至少存在一
个 x∈ [1,p-1]满足 x2≡ a(modp)，则我们称 a是模 p的
二次剩余（ quadratic residue）。
? 定义 9.2.4：设 p是一奇素数，对任何 a≧ 0,我们定义勒
让德符号（ Legendre symbol） L(a,p)为
0 如果 a ≡ 0(modp)
L(a,p)= 1 如果 a是模 p的二次剩余
-1 如果 a是 p的非二次剩余
? 定理 9.2.1（欧拉准则）：设 p是素数，那么 x是模 p的
二次剩余当且仅当
x(P-1)/2 ≡ 1(modp)
? 推论 9.2.1：假设 p是素数，那么 L(a,p) ≡
a(P-1)/2(modp)
? 定义 9.2.5：雅可比符号（ Jacobi
symbol）,记作 J(a,n),是勒让德符号的一
般化表示，它定义在任意正整数 a和奇整
数 n上。设 n的素数因子分解式为
pe1…… pek,则
J(a,n)=L(a,p1)e1 ?… ?L(a,p)ek
对一个奇整数 n的 Solovay-strassen素性测试
1,选择一随机整数 a,满足 a∈ [1,n-1]
2.如果 J(a,n)=a(n-1)/2modn 则
回答, n是素数,
否则 回答, n是合数,
7.Diffie-Hellman 密钥分配方案
? 公钥密码问世
? Diffie & Hellman in 1976,
? 密钥交换的实际方法
? 公钥方案概念的提出
? W Diffie,M E Hellman,"New directions in
Cryptography",IEEE Trans,Information Theory,
IT-22,pp644-654,Nov 1976
? James Ellis (UK CESG) 在案 970年曾提出此概念
12。 El Gamal 公钥加密方案
? Diffie-Hellman key distribution scheme 的变形
? 能够用于安全交换密钥
? published in 1985 by ElGamal,
? T,ElGamal,"A Public Key Cryptosystem and a
Signature Scheme Based on Discrete
Logarithms",IEEE Trans,Information Theory,
vol IT-31(4),pp469-472,July 1985,
? 安全性是基于离散对数
? 缺点：增加了消息长度（ 2倍）
13 密钥建立
? 密钥生成,
? 选取一个大素数 p及本原元 a mod p
? 接收者 Bob有一个密秘钥 xB
? 计算 yB = axB mod p
?
14,El Gamal 加密
? 为加密 M
? 发送者选择随机数 k,0<=k<=p-1
? 计算消息密钥 K,
? K = yBk mod p
? 计算密文对, C = {C1,C2}
? C1 = ak mod p
? C2 = K.M mod p
? 发送到接收者
? k 需要永久保密
15,El Gamal 解密
? 首先计算 message key K
? K = C1xB mod p = ak.xB mod p
? 计算明文,
? M = C2.K-1 mod p
16,El Gamal Example
? 选择 p=97 及本原根 a=5
? recipient Bob 选择 秘密钥 xB=58 & 计算并发布公钥
yB=558=44 mod 97
? Alice 要加密 M=3 to Bob
? 首先得到 Bob的公开密钥 yB=44
? 选择随机 k=36 计算,
K=4436=75 mod 97
? 计算密文对,
? C1 = 536 = 50 mod 97
? C2 = 75.3 mod 97 = 31 mod 97
? 发送 {50,31} to Bob
? Bob 恢复 message key K=5058=75 mod 97
? Bob 计算 K-1 = 22 mod 97
? Bob 恢复明文 M = 31.22 = 3 mod 97
9.3.1离散对数问题算法
1,计算
?
mi
m odp,i
?
[ 0,m - 1],按第二个坐标排序 m 个有序对（ i,
?
mi
m odp ），
得到表 T
1
,
2,计算
?
?
j? m odp,j
?
[ 0,m - 1],按第二个坐标排序 m 个有序对（ j,
?
?
j? m odp ），得到表 T
2
,
3,从 T
1
,T
2
中分别各自寻找一对（ i,y ）
?
T
1
和（ j,y ）
?
T
2
定义
l og
?
?
= m i + j m od( p - 1)
S h a n k s 算 法
1, 计算
j
?
=
?
1
)1(
?
? qp
j m odp,j
?
[ 0,q - 1],
2, i,
?
i
的初始值为 i
?
0 和
?
i
?
?
Whi l e i
?
c - 1 do
计算
?
=
?
i
)1(
)1(
??
?
j
qp m odp,
找一个 j 满足
?
=
?
j
,
a
i
?
j,
?
1?i
?
?
i
?
i
i
qa?,i
?
i + 1,
P o h l i g - H e l l m a n 算 法
9.4 基于纠错码的公钥密码体制
? 纠错码理论中的 NPC问题。
? 问题 1 陪集重量问题
? 问题 2 重量分布问题
? 问题 3 最小距离问题
? 当前关于建立基于纠错码的密码体制很
多是基于传统的 Hamming距离的。
系统参数：设 G 是 G F(2) 上的 [n, k,d]Go ppa 码的生成矩阵, 其中 n= 2
m
,d=2 t+1,k= n - mt,
设明文集为 GF( 2)
k
，密文集合为 GF( 2)
n
随机选取 G F(2) 上的 k
?
k 阶可逆矩阵 S 和 n
?
n 阶置换矩阵 P,令 G
'
=SGP 则
私有密钥,S,G,P
公开密钥,G
'
加密算法：对于待加密的明文 m
?
GF(2)
k
,其对应的密文为 c =m G
'
+z 这里的 z 是 GF( 2)
n
上重量为 t 的随机向量。
解密算法：接收者收到密文 c 后，计算 cP
1?
=mSGPP
1?
+zP
1?
=mSG+z
'
,由于 P 是置换阵，故 w(z
'
)=
w(z)= t 利用 Gop pa 的 快速译码算法将其译成 m
'
=mS 则密文 c 对应的明文为 m=m
'
S
1?
,
,
M c E l i e c e 体 制
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 ） 密钥分配问题 通信双方要进行加密通信，需要通过秘密
的安全信道协商加密密钥，而这种安全信道可能很难实现；
2 ） 密钥管理问题 在有多个用户的网络中，任何两个用户之
间都需要有共享的秘密钥，当网络中的用户 n 很大时，需
要管理的密钥数目是非常大
2/)1( ?nn
。
3 ） 没有签名功能,当主体 A 收到主体 B 的电子文挡（电子
数据）时，无法向第三方证明此电子文档确实来源于 B 。
9.1公钥密码学思想
? 定义 9.1.1一个公钥密码体制是这样的一个 5元组 {M,C,K,EK,DK}，
且满足如下的条件,
? 1.M是可能消息的集合；
? 2.C是可能的密文的集合；
? 3,密钥空间 K是一个可能密钥的有限集；
? 4．对每一个 K={K1,K2} ∈ K，都对应一个加密算法 EK1 ∈ E,
EK1:M→ C和解密算法 DK2 ∈ D,DK2:C → M,满足对于任意的 m ∈ M,
都有 c= EK1（ m）,m= DK2(c)=DK2(EK1（ m） )=m；
? 5．对于所有的 KK，在已知 E的情况下推出 D是计算上不可能的；
? 对每一个 K∈ K，函数 EK1和 DK2都是多项式时间可计算的函数。
EK1是一个公开函数,K1 称作公钥；而 DK2是一个秘密函数,K2称作
私钥，由用户秘密地保存。
? public-key/two-key/asymmetric 包括两
个密钥,
? 公开密钥 (a public-key),可以被任何人
知道,用于加密或验证签名
? 私钥 ( private-key),只能被消息的接收
者或签名者知道,用于解密或签名
? 加密或验证签名者不能解密或多或生成签
名,
? 是密码学几千年历史中最有意义的结果
3.公钥加密方案
4.公钥密码理论
? 由私钥及其他密码信息容易计算出公开密钥 (a
polynomial time (P-time) problem)
? 由公钥及算法描述,计算私钥是难的 (an NP-
time problem)
? 因此,公钥可以发布给其他人 (wishing to
communicate securely with its owner )
? 密钥分配问题不是一个容易的问题 (the key
distribution problem )
5.公钥算法分类
? Public-Key Distribution Schemes (PKDS)
? 用于交换秘密信息 (依赖于双方主体 )
? 常用于对称加密算法的密钥
? Public Key Encryption (PKE)
? 用于加密任何消息
? 任何人可以用公钥加密消息
? 私钥的拥有者可以解密消息
? 任何公钥加密方案能够用于密钥分配方案 PKDS
? 许多公钥加密方案也是数字签名方案
? Signature Schemes
? 用于生成对某消息的数字签名
? 私钥的拥有者生成数字签名
? 任何人可以用公钥验证签名
6.公钥的安全性
? 依赖于足够大大的困难性差别
? 类似与对称算法,穷搜索在理论上是能够破解
公钥密码 exhaustive search
? 但实际上,密钥足够长 (>512bits)
? 一般情况下,有一些已知的困难问题 (hard
problem”
? 要求足够大的密钥长度 (>512 bits)
? 导致加密速度比对称算法慢
2,RSA (Rivest,Shamir,Adleman)
? 使用最广泛的公钥加密算法
? Rivest,Shamir & Adleman (RSA) in
1977
? R L Rivest,A Shamir,L Adleman,"On
Digital Signatures and Public Key
Cryptosystems",Communications of the
ACM,vol 21 no 2,pp120-126,Feb 1978
?
3,RSA Setup
? 每个用户生成自己的公钥 \私钥对,
? 选择两个随机大素数 (~100 digit),p,q
? 计算模数 N=p.q
? 选择一个随机加密密钥匙 e, e<N,
gcd(e,?(N))=1
? 解下列同余方程,求解密密钥 d,
? e.d=1 mod ?(N) and 0<=d<=N
? 公开加密密钥, Kr={er,Nr}
? 保存其解密似钥,
? K-1r={d,p,q}
4。 RSA 参数选择
? 需要选择足够大的素数 p,q
? 通常选择小的加密指数 e,且与 ?(N) 互素
? e 对所有用户可以是相同的
? 最初建议使用 e=3
? 现在 3太小
? 常使用 e=216-1 = 65535
? 解密指数比较大
5,RSA Usage
? 要加密消息 M,发送者要得到接收者的
公钥 Kr={er,Nr}
? 计算, C=Mer mod Nr,where 0<=M<N
? 为解密 C,接收者使用私钥
? K-1r={d,p,q}
? 计算, M=Cd mod Nr
6,RSA理论
? RSA 基于 Fermat's Theorem,
? if N = pq where p,q are primes,then,
X?(N) = 1 mod N
? for all x not divisible by p or q,ie
gcd(x,?(N))=1
? where ?(N)=(p-1)(q-1)
? 但在 RSA 中,e & d 是特殊选择的
? ie e.d=1 mod ?(N) 或 e.d=1+R?(N)
? hence have,
M = Cd = Me.d = M1+R?(N) =
M1.(M?(N))R = M1.(1)R = M1 mod N
?
8。 RSA举例 例子,
1,选素数 p=47和 q＝ 71，得 n=3337,
? (n)=46× 70＝ 3220；
2,选择 e=79，求得私钥 d=e -1 ? 1019(mod
3220）。
3,公开 n=3337和 e=79,
4,现要发送明文 688，计算,
68879(mod 3337)=1570
5.收到密文 1570后，用私钥 d＝ 1019进行解密,
15701019（ mod 3337)=688
9。 RSA 安全性
? RSA 安全性基于计算 ?(N)的困难性
? 要求分解模 N
10,RSA的实现问题
? 需要计算模 300 digits (or 1024+ bits)
的乘法
? 计算机不能直接处理这么大的数
? （计算速度很慢）
? 需要考虑其它技术，加速 RSA的实现
11,RSA – 的快速实现
? 加密很快，指数小
? 解密比较慢，指数较大
? 利用中国剩余定理 CRT,
? CRT 对 RSA解密算法生成两个解密方程 （利用 M = Cd
mod R ）
? 即, M1 = M mod p = (C mod p)d mod (p-1)
? M2 = M mod q = (C mod q)d mod (q-1)
? 解方程 M = M1 mod p
? M = M2 mod q
? 具有唯一解（利用 CRT ）,
?,M = [((M2 +q - M1)u mod q] p + M1
? 其中 p.u mod q = 1
9.2.3概率素性检测
? 定义 9.2.3：如果 P是素数，且 a小于 p,如果至少存在一
个 x∈ [1,p-1]满足 x2≡ a(modp)，则我们称 a是模 p的
二次剩余（ quadratic residue）。
? 定义 9.2.4：设 p是一奇素数，对任何 a≧ 0,我们定义勒
让德符号（ Legendre symbol） L(a,p)为
0 如果 a ≡ 0(modp)
L(a,p)= 1 如果 a是模 p的二次剩余
-1 如果 a是 p的非二次剩余
? 定理 9.2.1（欧拉准则）：设 p是素数，那么 x是模 p的
二次剩余当且仅当
x(P-1)/2 ≡ 1(modp)
? 推论 9.2.1：假设 p是素数，那么 L(a,p) ≡
a(P-1)/2(modp)
? 定义 9.2.5：雅可比符号（ Jacobi
symbol）,记作 J(a,n),是勒让德符号的一
般化表示，它定义在任意正整数 a和奇整
数 n上。设 n的素数因子分解式为
pe1…… pek,则
J(a,n)=L(a,p1)e1 ?… ?L(a,p)ek
对一个奇整数 n的 Solovay-strassen素性测试
1,选择一随机整数 a,满足 a∈ [1,n-1]
2.如果 J(a,n)=a(n-1)/2modn 则
回答, n是素数,
否则 回答, n是合数,
7.Diffie-Hellman 密钥分配方案
? 公钥密码问世
? Diffie & Hellman in 1976,
? 密钥交换的实际方法
? 公钥方案概念的提出
? W Diffie,M E Hellman,"New directions in
Cryptography",IEEE Trans,Information Theory,
IT-22,pp644-654,Nov 1976
? James Ellis (UK CESG) 在案 970年曾提出此概念
12。 El Gamal 公钥加密方案
? Diffie-Hellman key distribution scheme 的变形
? 能够用于安全交换密钥
? published in 1985 by ElGamal,
? T,ElGamal,"A Public Key Cryptosystem and a
Signature Scheme Based on Discrete
Logarithms",IEEE Trans,Information Theory,
vol IT-31(4),pp469-472,July 1985,
? 安全性是基于离散对数
? 缺点：增加了消息长度（ 2倍）
13 密钥建立
? 密钥生成,
? 选取一个大素数 p及本原元 a mod p
? 接收者 Bob有一个密秘钥 xB
? 计算 yB = axB mod p
?
14,El Gamal 加密
? 为加密 M
? 发送者选择随机数 k,0<=k<=p-1
? 计算消息密钥 K,
? K = yBk mod p
? 计算密文对, C = {C1,C2}
? C1 = ak mod p
? C2 = K.M mod p
? 发送到接收者
? k 需要永久保密
15,El Gamal 解密
? 首先计算 message key K
? K = C1xB mod p = ak.xB mod p
? 计算明文,
? M = C2.K-1 mod p
16,El Gamal Example
? 选择 p=97 及本原根 a=5
? recipient Bob 选择 秘密钥 xB=58 & 计算并发布公钥
yB=558=44 mod 97
? Alice 要加密 M=3 to Bob
? 首先得到 Bob的公开密钥 yB=44
? 选择随机 k=36 计算,
K=4436=75 mod 97
? 计算密文对,
? C1 = 536 = 50 mod 97
? C2 = 75.3 mod 97 = 31 mod 97
? 发送 {50,31} to Bob
? Bob 恢复 message key K=5058=75 mod 97
? Bob 计算 K-1 = 22 mod 97
? Bob 恢复明文 M = 31.22 = 3 mod 97
9.3.1离散对数问题算法
1,计算
?
mi
m odp,i
?
[ 0,m - 1],按第二个坐标排序 m 个有序对（ i,
?
mi
m odp ），
得到表 T
1
,
2,计算
?
?
j? m odp,j
?
[ 0,m - 1],按第二个坐标排序 m 个有序对（ j,
?
?
j? m odp ），得到表 T
2
,
3,从 T
1
,T
2
中分别各自寻找一对（ i,y ）
?
T
1
和（ j,y ）
?
T
2
定义
l og
?
?
= m i + j m od( p - 1)
S h a n k s 算 法
1, 计算
j
?
=
?
1
)1(
?
? qp
j m odp,j
?
[ 0,q - 1],
2, i,
?
i
的初始值为 i
?
0 和
?
i
?
?
Whi l e i
?
c - 1 do
计算
?
=
?
i
)1(
)1(
??
?
j
qp m odp,
找一个 j 满足
?
=
?
j
,
a
i
?
j,
?
1?i
?
?
i
?
i
i
qa?,i
?
i + 1,
P o h l i g - H e l l m a n 算 法
9.4 基于纠错码的公钥密码体制
? 纠错码理论中的 NPC问题。
? 问题 1 陪集重量问题
? 问题 2 重量分布问题
? 问题 3 最小距离问题
? 当前关于建立基于纠错码的密码体制很
多是基于传统的 Hamming距离的。
系统参数：设 G 是 G F(2) 上的 [n, k,d]Go ppa 码的生成矩阵, 其中 n= 2
m
,d=2 t+1,k= n - mt,
设明文集为 GF( 2)
k
，密文集合为 GF( 2)
n
随机选取 G F(2) 上的 k
?
k 阶可逆矩阵 S 和 n
?
n 阶置换矩阵 P,令 G
'
=SGP 则
私有密钥,S,G,P
公开密钥,G
'
加密算法：对于待加密的明文 m
?
GF(2)
k
,其对应的密文为 c =m G
'
+z 这里的 z 是 GF( 2)
n
上重量为 t 的随机向量。
解密算法：接收者收到密文 c 后，计算 cP
1?
=mSGPP
1?
+zP
1?
=mSG+z
'
,由于 P 是置换阵，故 w(z
'
)=
w(z)= t 利用 Gop pa 的 快速译码算法将其译成 m
'
=mS 则密文 c 对应的明文为 m=m
'
S
1?
,
,
M c E l i e c e 体 制
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体制
? 基于纠错码的公钥密码体制
? 基于椭圆曲线的公钥密码体制。
