2012-3-19 1
第四章 公钥密码
http://web.xhu.edu.cn/jpkc/
2012-3-19 2
公钥密码
一、基本概念与简单算法
二,RSA公钥密码体制
三、离散对数公钥密码体制
四、可证明性安全公钥密码体制
2012-3-19 3
一,公钥密码体制的基本概念
Basic Concept of Public Key
Cryptography
2012-3-19 4
为什么需要公钥密码体制？
?密钥管理的方便
?数字签名的需要
2012-3-19 5
单钥加密体制的问题
E Network or Storage
明文
Plain
Text
密文
Cipher
Text
D
原明文
Original
Plain Text
Bob
私钥
Secret Key
Alice
私钥
Secret Key
密文
Cipher
Text
2012-3-19 6
单钥加密体制的问题
? 若 N个人相互保密通信，每人必须拥有 （ N-1）
个私钥,N很大时，需要保存的私钥很多。
如何解决？
? 可信中心分发：共需要发 N*(N-1)/2个私钥
N =1000时,999 *1000/2 = 499500
? 双方事先约定：用户之间自己秘密会面
（ 第一次远距离通信如何办？ ）
2012-3-19 7
基本概念
? 1976年,Standford Uni,Diffie博士和其导
师 Hellman 在 IEEE Trans,on IT 上发文
,New Direction in Cryptography”
? 这一体制的出现在密码学史上是划时代的
事件, 它为解决计算机信息网中的安全提
供了新的理论和技术基础 。 被公认为现代
密码学诞生的标志 。
2012-3-19 8
基本概念
?公钥密钥保密、认证系统的的安全性主
要取决于构造双钥算法所依赖的数学问题
。要求加密函数具有单向性，即求逆的困
难性。因此，设计双钥体制的关键是先要 寻求一个合适的 陷门单向函数 。
2012-3-19 9
基本概念
X ? ?Xf Y
? ?Yf 1?
公钥
私钥
2012-3-19 10
基本概念
单向函数：一个可逆函数 f,A?B,若它满足,
1o 对所有 x?A,易于计算 f(x)。
2o 对, 几乎所有 x?A”由 f(x)求 x“极为困难,
,以至于实际上不可能做到, 则称 f为一单向
(One-way)函数 。
? 定义中的, 易于计算, 是指函数值能在其输
入长度的多项式时间内求出, 即若输入长度
为 n,计算函数的时间是 na的倍数, a为一固
定的常数 。
? 若计算函数时间是 an的倍数, 则为不可能做
到的 。
2012-3-19 11
基本概念
? 陷门单向函数：单向函数是求逆困难的函数, 而
单向陷门函数, 是在不知陷门信息下求逆困难的
函数, 当知道陷门信息后, 求逆是易于实现的 。
这是 Diffie和 Hellmam[1976]引入的概念 。
? 例：号码锁 。
如何给陷门单向函数下定义则很棘手, 因为
(1) 陷门函数其实就不是单向函数, 因为单向函
数是在任何条件下求逆都是困难的；
(2) 陷门可能不止一个, 通过试验,一个个陷门就
可容易地 找到逆 。 如果陷门信息的保密性不
强, 求逆也就不难 。
2012-3-19 12
基本概念
? 单向函数是求逆困难的函数，而单向陷门函
数 (Trapdoor one-way function)，是在不知
陷门信息 下求逆困难的函数，当知道陷门信
息后，求逆是易于实现的。
? 限门单向函数是一族可逆函数 fk，满足
1,Y=fk(X)易于计算（当 k和 X已知）
2,X＝ f-1k(Y)易于计算（当 k和 Y已知）
3,X＝ f-1k(Y)计算上不可行（ Y已知但 k未知）
研究公钥密码算法就是找出合适的单向限 门函数
2012-3-19 13
基本概念
? 公钥密码基于的数学难题,
– 背包问题
– 大 整 数 分 解 问 题 （ The Integer
Factorization Problem,RSA体制 ） 。
– Diffie-Hellman问题 。
2012-3-19 14
基本概念
– 二次剩余问题。
– 模 n的平方根问题。
– 离散对数问题,
– 有限域的乘法群上的离散对数问题（ The
Discrete Logarithm Problem,ELGamal体制）
– 定义在有限域的椭圆曲线上的离散对数问题（
The Elliptic Curve Discrete Logarithm
Problem，类比的 ELGamal体制）。
2012-3-19 15
公钥密码体制的原理
Plain Text
m
E Network
Cipher
Text
C
Cipher Text
D
Plain Text
Alice
Bob,
Public Key Directory (公钥簿 )
Secret
Key
SKB
PKB
Bob
基本概念
2012-3-19 16
基本概念
? 基于公钥的加密过程,
明文输入 加密算法 解密算法
密文传送
明文输出
的公钥B 的私钥B
密文传送
加密算法 解密算法 明文输出
的公钥 的私钥
2012-3-19 17
? 每个用户都有一对选定的密钥 (公钥 PK；私
钥 SK)____也称为 双钥加密系统
? 加密用 （ 接收方的 ） 公钥, 解密用私钥
? 无需事先分配密钥 —解决了密钥分配问题 ！
基本概念
公钥密码体制的原理
2012-3-19 18
? 公钥密码体制的数学描述：满足如下条件的五元组
(M,C,K,E,D)
（ 1） M是可能消息的集合；
（ 2） C是可能密文的集合；
（ 3） K是可能密钥的有限集
（ 4） 对每一个 k=(PK,SK)?K,有 E PK ? E,D SK ? D,
满足对所有 m ? M,DSK (EPK(m)) = m
(5) 对所有 k,E PK ? D SK 是计算上不可能的。
基本概念
2012-3-19 19
公钥密码体制的模型由以下算法组成
? 密钥生成 KG ( ),根据输入的安全参数,输
出公钥和私钥对 (PK,SK)
? 加密 E( ),根据输入的公钥和消息,输出密
文。
? 解密 D( ),根据输入的解密私钥 和密文, 算
法输出消息或输出表示密文不合法的特殊符号
,?”
基本概念
2012-3-19 20
基本概念
? 公钥密码算法应满足的要求,
– 接收方 B产生密钥对在计算上是容易的
– 发方 A用 B公钥对消息 M加密成 C在计算上是容
易的
– 收方 B用自己的私钥对 C解密成 M在计算上是容
易的
– 敌人由 B的公钥求 B的私钥计算上不可行
– 敌人由 B的公钥和 C求明文 M,计算上不可行
– 加, 解密次序可换
2012-3-19 21
私钥系统与公钥系统的区别
? 单钥〈 ---〉双钥
? 对称〈 ---〉非对称
? 双向性〈 ---〉单向性
? 保险柜 〈 --〉 邮箱
? 私钥分发 〈 --〉 公钥管理
基本概念
2012-3-19 22
基本概念
? 对公钥密码体制的攻击,
由于公钥体制的加密变换是公开的，
使得任何人都可以采用 选择明文来攻击 双钥
体制，因此，明文空间必须足够大才能防止
穷尽搜索明文空间攻击。一种更强有力的攻
击法是 选择密文攻击,攻击者选择密文，而
后通过某种途径得到相应的明文，多数双钥
体制对于选择密文攻击特别敏感。
2012-3-19 23
基本概念
通常采用两类选择密文攻击,
在接收到待攻击的密文之前, 可以向攻击者提供他
们所选择的密文的解密结果 。
自适应选择密文攻击, 攻击者可能利用 (或接入 )被
攻击者的解密机 (但不知其秘密钥 ),而可以对他
所选择的, 与密文有关的待攻击的密文, 以及以
前询问得到的密文进行解密
2012-3-19 24
基本概念
? 公钥密码标准,
非官方工业标准 银行标准工业标准
国际标准
联邦标准
2012-3-19 25
简单算法
? 背包密码体制：由 Merkle 和 Hellman
1978年提出的第一个公钥密码算法 。 它
利用背包问题构造构造公钥密码, 只适
用于加密, 修正后方可用于数字签名 。
? 背包问题描述：给定重量分别为
的 n 个物品, 装入一个背包中要求重量
满足一个给定值, 找出究竟是哪些物品
？
naaaa,...,,321
2012-3-19 26
简单算法
? 0-1背包问题,1972年由 Karp提出的, 已知向量
, 其中 为正整数,
称其为背包向量 。 给定向量
求和 很容易, 只需要 n-1次加法 。 但已知
和, 求 则非常困难, 称其为背包问题, 又称子
集合问题 。 用穷举搜索法, 有 种可能, n非常
大时, 相当困难 。 背包问题是一个 NP完全问题
。
? ?naaaA,...,,21? ia
? ? ? ?1,0,,...,,21 ?? in xxxxx
ii xaS ??
A
S
n2
x
2012-3-19 27
简单算法
? 用背包问题构建公钥密码, 关键在于有两类
背包, 一类可以在线性时间内求解, 而另一
类则不能 。 把易解得背包问题转换成难解的
背包问题, 便可实现 。 即
– 公开密钥使用难解的背包问题
– 私钥使用易解的背包问题
2012-3-19 28
简单算法
? 易解的背包即简单背包：又名超递增背包, 若背包向量
满足
称为超递增背包向量, 相应背包为简单背包 。
简单背包很易求解, 因为给定 及,
易知
由此可得出解此背包的所谓贪心算法 。 先取最大的放入
背包, 若能 放入, 则另相应的 为 1,否则另相应
为 0。 从中减去, 再试, 以此类推, 直到决定出 的取
值 。
? ?naaaA,...,,21? ?
?
?
??
1
1
2,1,
i
j
ji Niaa ?
? ?naaaA,...,,21? S
?
?
?
??
??
?
n
n
n aS
aS
x
0
1
nx
1x
2012-3-19 29
简单算法
? 转换背包 （ Merkle-Hellman陷门背包 ）,这一体制的基
本想法是将一个简单背包进行伪装, 使得对所有其他人
为一个困难背包, 而对合法用户则为简单的背包 。 构造
方法如下,
（ 1） 各用户随机地选择一个超递增序列
A0=(a10,a20,…,aN0)。
（ 2） 将其进行随机排列得到矢量
A’=(a1’,a2’,…,aN’)。
（ 3） 随机地选择两个整数 u和 w使
u?2aN0
?
?
?
N
i
iau
1
2012-3-19 30
简单算法
且 gcd(u,w)=1 0<w<u
由 Euclidean算法可得出 a,b且 1=au+bw,由此
可得出 bw ?1 mod u,即 w-1? b mod u
（ 4） 计算 ai=w ? ai’ mod u,i=1,…,N 构造出新
的 (难的 ) 背包矢量 A=(a1,…,aN)。
（ 5） 陷门信息为 u和 w-1。 且用户收到加密信息 y
且, 先转成为整数 S, 而后计算 S’=(w-1?S)
mod u且最后可由简单背包
解出 x=(x1,x2,…,xN )。
?
?
?
N
i
ii axS
1
2012-3-19 31
简单算法
? 证明
? 这样就把有 S直接解难背包通过 转化为
解简单背包
uSwS m o d 1 ?? ?
uaxw
N
i
ii m o d
1
1 ?
?
? ??
uuawwx
N
i
ii m o d))m o d ((
1
1?
?
? ???
uuawwx
N
i
ii m o d))m o d (
1
1?
?
? ???
uax i
N
i
i m o d
1
?
?
?
)(
1 11
? ??
? ??
???
N
i
N
i
iii
N
i
ii uaaxax 因
uw,1?
2012-3-19 32
简单算法
? 基于背包问题的公钥密码系统 （ MH公钥算法
）,
– 加密：将明文分为长度为 的块
然后用公钥 将明文加密成密
文
– 解密：先计算 在求解简单
背包问题
n ? ?nxxxx,.,,,,21?
? ?''2'1',...,,naaaA ?
? ? ii xaXES ??? '
uSwS m o d1' ??
?? ii xaS '
2012-3-19 33
简单算法
? 例子：从私钥计算公钥
– 私钥 {2,3,6,13,27,52}
– w=31,u=105
2*31mod105=62
3*31mod105=93
6*31mod105=81
13*31mod105=88
27*31mod105=102
52*31mod105=37
– 公钥 {62,93,81,88,102,37}
2012-3-19 34
简单算法
? 例子：加密
– 消息 =011000 110101 101110
– 明文 0 1 1 0 0 0
– 背包 62,93,81,88,102,37
– 密文,93+81=174
– 011000对应 93+81=174
– 110101对应 62+93+88+37=280
– 101110对应 62+81+88+102=333
2012-3-19 35
简单算法
? 例子：解密
– 解密者知道 {2,3,6,13,27,52},n,u
– 计算,
– 174*61mod105=9=3+6对应 011000
– 280*61mod105=70=2+3+13+52对应 110101
– 333*61mod105=48=2+3+13+27对应 101110
– 因此消息为 011000 110101 101110
? ? ? ?uww m o d11 ??
611 ??w
2012-3-19 36
简单算法
? 背包密码系统的意义,
– 是 Diffe和 Hellman 1976年提出公钥密
码体制的设想后的第一个公钥密码体制
,由 Merkle和 Hellman在 1978年提出 。
– 由较好的理论价值 。
2012-3-19 37
简单算法
? 背包体制的缺陷：背包体制的加, 解密的速度远比RSA体制快的多, 它大约只需要 200次加法运算,
速度可与对称加密算法相比, 但有一些致命的弱点
,
– MH背包体制已经证明不安全, 大多数背包方案
都已被破解 。
– MH背包不是满射, 因而不能用作数字签字 。
Shamir曾提出一种可用于签字的背包体制
[1978],被 Odlyzko[1984]破译 。
– 消息扩展太大, n=200,每个密钥分量为 400
bit序列, 公钥 80 kb长 !
2012-3-19 38
二,RSA公钥密码体制
2012-3-19 39
RSA算法
2012-3-19 40
概况,
? MIT三位年青数学家 R.L.Rivest,A.Shamir和
L.Adleman 在 1978年发现了一种用数论构造双
钥体制的方法, 称作 MIT体制, 后来被广泛称
之为 RSA体制 。
? 它既可用于加密, 又可用于数字签名 。
? RSA算法的安全性基于数论中大整数分解的困
难性 。
RSA算法
2012-3-19 41
RSA算法
? 数论基础：算术基本定理
– 任意大于 1的整数 a都能被因式分解为如
下的唯一形式,
– 其中 都是素数
,而且每一个 。
t21 a
t
a
2
a
1 p...ppa ?
t21 p....pp ??
? ?t,...3,2,1i0a i ??
2012-3-19 42
RSA算法
? 数论基础：中国剩余定理
。同余的意义下有唯一解在模
则同余方程组
两两互素，并记设自然数
N
mbx
mbx
mbx
mmmNmmm
rr
rr
m o d
..,,,,,,,,,
..,,,,,,,,,
m o d
m o d
,...,...,
22
11
2121
?
?
?
?
?
2012-3-19 43
RSA算法
? 数论基础,Fermat’s Theorem
– Fermat定理,p是素数, a是整数且不
能被 p整除, 则,
– 推论,p是素数, a是任意整数, 则,
? 在公钥理论和素性检测中很重要 。
pm o d1a 1-p ?
pm o daa p ?
2012-3-19 44
RSA算法
? 数论基础,Euler’s Function
– 模 n的非负最小完全剩余系是
– 如果一个模 n的剩余类里面的数与 n互素, 就把
他叫做一个与模 n互素的剩余系 。
– 与模 n的全部剩余系中, 从每一个系中各取一
个数组成的数的集合叫做模 n的一个简化剩余
系 。
– Euler函数,定义为小于 n且与 n互素的正整
数个数 。
? ?1.,,,,3210 ?n，，，
? ?n?
2012-3-19 45
RSA算法
? 数论基础,Euler’s Theorem
– Euler定理：若 a与 n为互素的正整数,
则,
– 是 Fermat定理的推广 。
– 例子,a=3,n=10,； 因此
? ? nm o d1a n ??
? ? 4?n?
10m o d1813 4 ＝＝
2012-3-19 46
RSA算法
? 数论基础：欧拉定理推论
– 若 是素数
,k 是 任 意 整 数, 则,
对任意
qppqn ??,
? ? ? ?,m o d111 nmm qp ????
nm ??0
2012-3-19 47
算法描述－密钥产生 KG( ),
? 选取两互异大素数 p和 q
? 计算 n=p× q 和其欧拉函数值 ?(n)=(p－ 1)(q－ 1)
? 选一整数 e,1 < e<?(n),使得 gcd(?(n),e)=1
? 在模 ?(n)下, 计算 e的逆元 d,即求 d,使得
ed ≡ 1 mod ?(n)
? 以 (n,e )为公钥 。 d 为秘密钥 。
(p,q不再需要, 可以销毁 。 )
RSA算法
2012-3-19 48
算法描述－加密 E( )和解密 D( ),
? 加密：将明文分组, 各组对应的十进制数
m<n,计算
c =E(m)≡ me mod n
? 解密, m = D(c)≡ cd mod n
RSA算法
2012-3-19 49
解密正确性证明,
na n m o d1)( ??
Euler定理 若 a 与 n互素, 则
10m o d1813 4 ??如,a=3,n=10时
RSA算法
2012-3-19 50
解密正确性证明,
? 要证 cd mod n ≡ m, 由加密过程
cd mod n ≡ （ me） d mod n
≡ mk??n)+1 mod n （ ed ≡ 1 mod ?(n) )
1） 若 m与 n互素, 由欧拉定理 m??n)≡1 mod n
有 mk??n)≡1 mod n,
mk??n)+1≡ m mod n
RSA算法
2012-3-19 51
解密正确性证明,
2） 若 m与 n不互素, 即 gcd(m,n) ≠1,则 m
是 p的倍数或 q的倍数, 不妨设 m=cp （ c < q）
此时 gcd(m,q)=1,由欧拉定理,
m??q)≡1 mod q,[m??q)]k??p)≡1 mod q
即 mk??n)≡1 mod q,
于是存在一整数 r,使 mk??n)≡1 ＋ rq,
两边同乘 m=cp,得
mk??n)+1≡ m+rcpq=m+rcn,即 mk??n)+1≡ m mod n
RSA算法
2012-3-19 52
一个例子,
? 密钥生成
– 取,p=17,q=11那么 n=pq=17 × 11=187,
– 计算 ?(n)=(p－ 1)(q－ 1)=16 × 10=160
– 选取与 ?(n)=160互素的整数 e=7
– 按照扩展的欧几里德算法计算 d=e -1 mod ?(n)
= 7 -1 mod160= 23
– 公开密钥为 (n,e)=(187,7),私钥为 d=23,
RSA算法
2012-3-19 53
一个例子,
? 加密
c=me mod n
为了对消息 m =88加密, 按照如下步骤计算密文
c=memodn =887mod 187=11
RSA算法
2012-3-19 54
一个例子,
? 解密：当收到密文 c后，利用私钥计
算明文
88)187m o d (11 23 ??m
RSA算法
2012-3-19 55
RSA算法
? RSA加密实质上是一种 Zn?Zn上的单表代换
！ 给定 n=p1p2和合法明文 x?Zn,其相应密文
y=xe mod n ?Zn。 对于 x?x, 必有 y?y 。 Zn
中的任一元素 (0,p1,p2的倍数除外 )是一
个明文, 但它也是与某个明文相对应的一个
密文 。 因此, RSA是 Zn?Zn的一种单表代换
密码, 关键在于 n极大时在不知陷门信息下
极难确定这种对应关系, 而用模指数算法又
易于实现一种给定的代换 。 正由于这种一一
对应性使 RSA不仅可以用于加密也可以用于
数字签字 。
2012-3-19 56
对 RSA的攻击与参数选取
? 单向性是如何表现的？
? f,x ? f(x)=xe mod n
容易
? f -1,f(x) ? x 困难
? 陷门：私钥 d
f(x)d mod n =(xe)d mod n=x
2012-3-19 57
对 RSA的攻击与参数选取
? RSA的安全性是基于分解大整数的困难性
假定（尚未证明分解大整数是 NP问题 ）
m = D(c)≡ cd mod n ? d?
? 如果能分解 n=p× q，则立即可得 ?(n)=
(p－ 1)(q－ 1)，从而能够确定 e的模 ?(n)
乘法逆 d
2012-3-19 58
对 RSA的攻击与参数选取
数学技术 =Money？
? RSA-129历时 8个月于 1994年 4月被成功分解
(600多位科学家,100$)
? RSA－ 130于 1996年 4月被成功分解
? RSA－ 140于 1999年 2月被成功分解
? RSA－ 155于 1999年 8月被成功分解
? 密钥长度应该介于 1024bit到 2048bit之间
? 由 n直接求 ?(n)等价于分解 n
2012-3-19 59
对 RSA的攻击与参数选取
因子分解复杂度,
密钥长 (bit) 所需的 MIPS-年 *
116(Blacknet密钥 ) 400
129 5,000
512 30,000
768 200,000,000
1024 300,000,000,000
2048 300,000,000,000,000,000,000
* MIPS-年指以每秒执行 1,000,000条指令的计算机运
行一年
2012-3-19 60
对 RSA的攻击与参数选取
对 RSA的攻击,
（ 1 ） 迭代攻击法,Simmons 和
Norris曾提 迭代或循环攻击法 。 例如,
给定一 RSA的参数为 (n,e,y)=(35,17,
3),可由 y0=y=3计算 y1=317=33 mod 35。
再由 y1计算 y2=y117=3 mod 35,从而得到
明文 x=y1=33 mod 35。 一般对明文 x加密
多次, 直到再现 x为止 。 Rivest证明, 当
p1－ 1和 p2－ 1中含有大素数因子, 且 n足
够大时, 这种攻击法成功的概率趋于 0。
2012-3-19 61
对 RSA的攻击与参数选取
（ 2） 选择明文攻击
(a) 消息破译 。 攻击者收集用户 A以公
钥 e加密的密文 y=xe mod n,并想分析出消
息 x。 选随机数 r<n,计算 y1=re mod n,这
意味 r=y1d mod n。 计算 y2=y1× y mod n。
令 t=r-1 mod n,则 t=y1-d mod n。 现在攻
击者请 A对消息 y2进行签字 (用秘密钥, 但不
能用 Hash函数 ),得到 S=y2d mod n。 攻击
者计算 ts mod n=y1-d× y2d mod n=y1-
d× y1d× yd mod n=yd mod n=x,得到了明
文 。
2012-3-19 62
(b) 骗取仲裁签字。在有仲裁情况下,A
有一个文件要求仲裁，可先将其送给仲
裁 T,T以 RSA的秘密钥进行签署后回送给
A(未用单向 Hash函数，只以秘密钥对整
个消息加密 )。
攻击者有一个消息要 T签署，但 T并
不情愿给他签，因为可能有伪造的时戳
，也可能是来自另外人的消息。但攻击
者可用下述方法骗取 T签字。
2012-3-19 63
(c) 骗取用户签字。攻击者可制作两
条消息 x1和 x2,凑出所要的 x3?x1× x2
mod n。
首先他可得到用户 A对 x1和 x2的签
字 x1d mod n 和 x2d mod n,则可计
算 x3d mod n?(x1d mod n)?(x2d mod
n ) mod n。
因此，任何时候不要为不相识的
人签署随机性文件，最好先采用单向
Hash函数。 ISO 9796的分组格式可以
防止这类攻击。
2012-3-19 64
对 RSA的攻击与参数选取
令攻击者的消息为 x,他首先任意选一个数 N，
计算 y=Ne mod n(e是 T的公钥 ),而后计算
M=yx,送给 T,T将签字的结果 Md mod n送给
攻击者, 则有 ( Md mod n)N-1 mod n=(yx)d?N-1 mod n=xdyd?N-1 mod n=xdNN-1
mod n=xd mod n,此为 T对 x的签字 。
所以能有这类攻击是因为指数运算保持了输
入的乘法结构 。
2012-3-19 65
对 RSA的攻击与参数选取
（ 3） 共模攻击,
? 每一用户有相同的模数 n
? 设用户的公开密钥分别为 e1,e2,且 e1,e2互素，明文
消息为 m,密文为
? 因为（ e1,e2)=1,用欧几里德算法可求
r e1+s e2=1从而由 Euclidean算法可计算
c1r ? c2s=m mod n
nmc
nmc
e
e
m o d
m o d
2
1
2
1
?
?
2012-3-19 66
对 RSA的攻击与参数选取
（ 4） 低加密指数攻击：令网中三用户的加密钥 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
2012-3-19 67
对 RSA的攻击与参数选取
（ 5）定时攻击法,
定时 (Timing)攻击法由 P,Kocher提出，利
用测定 RSA解密所进行的模指数运算的时间来估
计解密指数 d,而后再精确定出 d的取值。 R,
Rivest曾指出，这一攻击法可以通过将解密运
算量与参数 d无关挫败。另外还可采用盲化技术
，即先将数据进行盲化，再进行加密运算，而
后做去盲运算。这样做虽然不能使解密运算时
间保持不变，但计算时间被随机化而难于推测
解密所进行的指数运算的时间 。
2012-3-19 68
对 RSA的攻击与参数选取
RSA的参数选取,
（ 1） n的确定
– n=p1× p2,p1与 p2必须为强素数 。
强素数 p的条件,（ a） 存在两个大素数 p1和 p2
,p1|(p－ 1),p2|(p＋ 1)。 （ b） 存在 4个大素数 r1,
s1,r2及 s2,使 r1|(p1－ 1),s1|(p1＋ 1),r2|(p2－
1),s2|(p2＋ 1)。 称 r1,r2,s1和 s2； p1和 p2为二级
素数 。
a
i
t
i
pR
1?
??
2012-3-19 69
采 用 强 素 数 的 理 由 如 下, 若
,pi为素数, ai为正整数 。 分解式中 pi<B
,B为已知一个小整数, 则存在一种 p－ 1
的分解法, 使我们易于分解 n。 令 n=pq，
且 p－ 1满足上述条件, pi<B。 令 a?ai，
i=1,2,…,t。 即可构造
显然 (p－ 1)?R。 由费尔马定理 2R?1
mod p。 令 2R=x mod n。 若 x =1则选 3代
2,直到出现 x?1。 此时, 由 GCD(x－ 1,
n)=p,就得到 n的分解因子 p和 q。
2012-3-19 70
简单算法
– p1与 p2之差要大 。 若 p1与 p2之差很小, 则可
由 n=p1p2估计 (p1＋ p2)/2=n1/2,则由 ((p1＋
p2)/2)2－ n=((p1－ p2)/2)2。 上式右边为小
的平方数, 可以试验给出 p1,p2的值 。
– p,q要足够大, 以使 n分解在计算上不可行
。
– p1－ 1与 p2－ 1的最大公因子要小 。 在惟密文
攻击下, 设破译者截获密文 y=x e mod n。
破译者做下述递推计算,
xi=xi-1e mod n=(xe)i mod n
2012-3-19 71
简单算法
（ 2） e的选取原则
(e,?(n))=1的条件易于满足, 因为两个随机数为
互素的概率约为 3/5。 e小时, 加密速度快, Knuth和
Shamir曾建议采用 e=3。 但 e太小存在一些问题 。
– e不可过小：若 e小, x小, y=xe mod n,当 xe<n，
则未取模, 由 y直接开 e次方可求 x。 易遭低指数攻
击 。
– 由选 e在 mod ?(n)中的阶数, 即 i,ei ?1 mod
?(n),i达到 (p1－ 1)(p2－ 1)/2。
2012-3-19 72
简单算法
（ 3） d的选择,
e选定后可用 Euclidean算法在多项式时间内
求出 d。 d要大于 n1/4。 d小, 签字和解密运算快,
这在 IC卡中尤为重要 (复杂的加密和验证签字可
由主机来做 )。 类似于加密下的情况, d不能太小
,否则由已知明文攻击, 构造 (迭代地做 )y=xe
mod n,再猜测 d值, 做 xd mod n,直到试凑出
xd?1 mod n是 d值就行了 。 Wiener给出对小 d的
系统攻击法, 证明了当 d长度小于 n的 1/4时, 由
连分式算法, 可在多项式时间内求出 d值 。 这是
否可推广至 1/2还不知道 。
。
2012-3-19 73
小结
? 公钥加密体制的基本思想
? 公钥加密体制的要求和特点
? 单向函数的基本特点
? RSA的具体方案和安全性考虑
? 如何实现安全的 RSA体制？
2012-3-19 74
三、离散对数公钥密码体制
2012-3-19 75
ElGamal密码体制
ElGamal密码体制：由 ElGamal[1984,1985]
提出, 是一种基于离散对数问题的公钥密码
体制, 既可用于加密, 又可用于签字 。
2012-3-19 76
ElGamal密码体制
? ElGamal方案,
（ 1） Zp, p个元素的有限域 p,一个素数
g：是 Zp＊ (Zp中除去 0元素 )中的一个本原
元或其生成元。
明文集 M, Zp＊ 密文集 C,Zp＊
× Zp＊ 。
公钥,选定 g(g <p的生成元 )，计算公钥
??g? mod p
秘密钥,?<p
2012-3-19 77
ElGamal密码体制
（ 2） 加密：选择随机数 k?Zp-1,且 (k,p－
1)=1,计算,
y1=g k mod p (随机数 k被加密 )
y2=M?k mod p(明文被随机数 k和公钥 ?加密 )
M是发送明文组。密文由 y1,y2级连构成，
即密文 C=y1||y2。
2012-3-19 78
ElGamal密码体制
特点：密文由明文和所选随机数 k来定，因
而是非 确定性加密，一般称
之为随机化加密，对 同一明文由于不
同时刻的随机数 k不同而给 出不同的
密文。代价是使 数据扩展 一倍。
（ 3）解密：收到密文组 C后，计算
M=y2/y1?=M? k/gk?=Mg?k/gk? mod p
2012-3-19 79
ElGamal密码体制
? 例子,
– 生成密钥：使用者 A选取素数 p=2357及 Z2357*的生成
元 2,A选取私钥 x=1751并计算
A的公钥是
– 加密：为加密信息 m=2053,B选一个随机整数
k=1520,并计算
然后发送给 A。
– 解密,
11852357m o d2m o d 1 7 5 1 ??pg x
1185,2,2357 ??? xggp
6972 3 5 7m o d1 1 8 52 0 3 5
1 4 3 02 3 5 7m o d2
1 5 2 0
1 5 2 0
???
??
b
a
2357m o d2035872697/
2357m o d87214301430 6 0 51
?????
???
?
???
xx
xpx
baabm
a
2012-3-19 80
ElGamal密码体制
? 上述方案是基于乘法群 Zp*建立的 ElGamal公
钥密码体制, 实际上可基于任何离散对数问
题难处理的群实现 ElGamal公钥密码体制 。
下面介绍推广的 ElGamal公钥密码体制 。
? 设群 G是一运算符为 × 的有限群, 子群 H是
由 a生成的, 且满足其上的离散对数问题是难
解的, 具体推广如下,
2012-3-19 81
ElGamal密码体制
? 系统参数,
? 加密：对于消息 m,选随机数
? 解密：消息接受者解密
? ? ? ? 1
1221,2
??? d
k yyyyd
? ? ? ? ? ?
kk
k
myay
yykmeHk
????
???
21
21
,
,,,1,0
1
其中
则密文为
? ?
?
?
,
,)(
0,
ad
aHdaH
iaHGaG
d
i
公钥：则私钥：
＝计算，选生成的是由即
的有限群，为运算符为
?
????
2012-3-19 82
ElGamal密码体制
? ElGamal签名,
pgy
pg
p
x m o d?
? （可由一组用户共享）
享）素数（可由一组用户共公钥：
px ?私钥：
)1m o d ()()(
m o d)(
1
???
?
pkbxaMb
pga
pk
k
满足签名
＝签名
互素，与签名：随机选取
签名有效验证：如果,m o dm o d pgpay Mba ?
2012-3-19 83
ElGamal密码体制
? ElGamal的安全性,
– 攻击该算法等价于解离散对数难题
– 要使用不同的随机数 k来加密不同的消息
,否则很容易被破解 。 假设用同一个 k来加
密两个消息 m1和 m2,所得的密文分别为 （
a1,b1),(a2,b2),则 b1/b2=m1/m2,故当 m1已
知, m2可以很容易的计算出来 。
2012-3-19 84
安全性分析
? 离散对数难题,
计算
– 已知 g,x,p时计算 y是容易的 。
– 已知 y,g,p时计算 x是困难的 。
? 一般的描述,
m o d pgy x?
? ?
? ?
?
?
?
a
y
i
y
aHy
H
iaHHGaG
l o g
,,1,0
,0,,
?
???
?????
们记为
我满足整数问题：能否找到唯一的
是由生成的。
即其中的有限群，是运算符为条件：设群
2012-3-19 85
安全性分析
? 密码学中常用的离散对数,
– 有限域 上的乘法群
– 有限域 上的乘法群
– 有限域 上的椭圆曲线群
? ?pGF
? ?n2GF
F
2012-3-19 86
安全性分析
? 求离散对数的算法介绍,Pohlig-Hellman算法
? ?
1210
1
0
1
,...,,
m o dl o g
,m o d01,m o d01
?
?
?
??
??
????
c
c
c
i
c
ia
cc
p
aaaa
qqa
qpqpqZa
的则算法用来计算满足
是素数，且的本原元，是
?
? ?
? ?
? ?
? ?
.1,,
,m o d
1
,0,.2
1,0,m o d.1
1
,
1
1
1
1
????
??
??
???
?
?
?
?
??
?
iiaja
j
p
do
ci
W h i l e
ii
qjpa
i
i
j
j
qa
iii
j
qp
i
ii
qp
j
??
??
??
???
?
＝满足找一个
＝计算
的初始值为
计算
2012-3-19 87
安全性分析
? 计算离散对数与因子分解有紧密的关系, 如果能
解决离散对数问题, 那么就能解决因子分解问题
,（ 逆命题的正确性还未被证明 ） 。 目前在素数
域上有 3种方法计算：线性筛选法, 高斯整数法,
和 NFS。
? 基本的扩展计算必须在每个域上做一次, 之后,
单个的对数就能快速进行计算, 对基于这些域的
系统而言, 是一个安全缺陷 。 所以, 不同的用户
采用不同的素数域很重要 。
2012-3-19 88
安全性分析
? Diffie-HEllman假定
? 一般可认为有两类假定 。
一, 计算 Diffie-Hellman 假定 （
Computational Diffie-HellmanAssumption,CDH)
。
二, 决定 Diffie-Hellman 假定 （ Decisional
Diffie-Hellman Assumption,DDH)。
? 两类假定均有 Diffie-Hellman问题引出, 当在某个
群或域上求解 Diffie-Hellman问题是困难时, 就认
为假定在该群或域上成立 。
2012-3-19 89
安全性分析
? CDH
Diffie-Hellman函数定义为,
如果在一个群上没有有效的算法能够
计算 Diffie-Hellman函数, 那么该群满足
CDH 假定 。 即已知
。
? ? abbag gggDH ?,
abba ggg 没有有效算法计算,
2012-3-19 90
安全性分析
? DDH
给定群 上 的 任 意 一 个 三 元 组
, 没有有效的概率算法
能够当 时, 输出, 真,, 否则输出,
假, 。
? 除 CDH和 DDH外, 还有推广的问题如
BDHP(Bilinear Diffie-Hellman Problem),
BIDHP(Bilinear Inverse Diffie-Hellman
Problem)等 。
cba ggg,,
3G
abc ?
2012-3-19 91
椭圆曲线密码体制
? 简要历史
椭圆曲线 (Elliptic curve)作为代数几何中的
重要问题已有 100多年的研究历史
1985年,N,Koblitz和 V,Miller独立将其引
入密码学中，成为构造公钥密码体制的一个有力工
具 。
利用有限域 GF(2n )上的椭圆曲线上点集所构成
的群上定义的离散对数系统，可以构造出基于有限
域上离散对数的一些公钥体制 --椭圆曲线离散对数
密码体制 (ECDLC )，如 Diffie-Hellman,ElGamal，
Schnorr,DSA等
2012-3-19 92
椭圆曲线密码体制
? 实数上的椭圆曲线,
? 其中的 是满足简单条件的
实数
? 一些曲线上的点连同无穷远点 O的集合 。
edxcxxbya x yy ?????? 232
edcba,,,,
2012-3-19 93
椭圆曲线密码体制
? 实数上的椭圆曲线例子,
132 ??? xxy
2012-3-19 94
椭圆曲线密码体制
? 运算定义,
SQQS
Q
OpRQp
XRQ
ppOOpp
ppX
pOpOOO
O
???
???
?????
????
于是线的另一交点
曲倍是，找到它的切线与的倍，一个点
，，则得到第三个点
轴不同，则画一连线，的和如果两个点
，于是
则轴两点一条竖直线交
，用作加法的单位：
，上，则其和为若曲线三点在一条直线
,
22
,
,;
11
2121
21
2012-3-19 95
椭圆曲线密码体制
? 有限域上的椭圆曲线,
? 模 P椭圆群记为 群中的元素 （ x,y)是满足
以上方程的小于 P的非负整数另外加上无穷远点
O
? 计算
pbap
pbaxxy
m o d0274
m o d
23
32
??
???
是奇素数，且
? ?,,baE p
? ?,,baE p
? ? ? ?。，记为其中
得到曲线上的点的确定是否可以求出有效
计算针对所有的
baEpyxyx
y
pbaxxpx
p
,,,,
,
m o d,0
3
?
????
2012-3-19 96
椭圆曲线密码体制
? 的加法规则,? ?baE
p,
? ? ? ? ? ?
? ? ? ?
? ? ? ? ? ?
? ?
? ? ? ?
? ? ? ?
1
2
1
1212
1313
21
2
3
332211
2/3,
/,
m o d
m o d
,,,,,
,,
,,,,,
yaxQP
xxyyQP
pyxxy
pxxx
yxQPyxQyxP
baEyxP
PyxOyxPyxP
POP
p
??
???
???
???
?????
??
??????
???
＝则如果
＝则其中，如果
为则如果
中也在。而且点，记为
的负点是则如果
?
?
?
?
2012-3-19 97
椭圆曲线密码体制
? ECC的加解密,
? ?
? ?
? ?
? ?
? ? ? ?
加密消息有扩张
解密
则重新选择为或者使得如果
计算密文然后选择随机数
中的一个点变换成为先把消息加密
保密
为公钥公开
然后计算秘密选择整数
值的最小的阶是指满足
是一个大素数的阶使得的元素选择
?
???????
??
?
??
?
?
mmmm
mm
mp
p
Prk Gk rGPkGrkPPC
kOkPkGk
kPPkGCk
PbaEMM
r
PPGbap
rGPr
nOnGG
nGGbaE
:
,
,,
,:
,,,,,
,,
,,
2012-3-19 98
椭圆曲线密码体制
? ECC加解密例子,
? ?
? ?
? ?
? ?
? ? ? ?
? ? ? ? ? ?
? ? ? ?? ?328385558676
328,3855,201386201,562
558,676376,0386
5,201
386,201,562
,
376,0,188
,188,1,751
32
，，，发送密文因此
我们有
的公钥是
选择随机数而椭圆曲线上的点
这个报文被编码为希望发送一个报文给假设
这等价于曲线取
A
kPP
kG
PB
kAP
BA
Gxxy
Ep
Bm
B
m
p
?
?????
???
?
??
?
????
???
2012-3-19 99
椭圆曲线密码体制
? ECC特别适用,
(1) 无线 Modem的实现：对分组交换数据网提供加密
，在移动通信器件上运行 4 MHz的 68330 CPU,ECC可实现
快速 Diffie-Hellman密钥交换，并极小化密钥交换占用的
带宽，将计算时间从大于 60秒降到 2秒以下。
(2) Web服务器的实现：在 Web服务器上集中进行密
码计算会形成瓶颈,Web服务器上的带宽有限使带宽费用
高，采用 ECC可节省计算时间和带宽，且通过算法的协商
较易于处理兼容性。
(3) 集成电路卡的实现,ECC无需协处理器就可以在
标准卡上实现快速、安全的数字签名，这是 RSA体制难以
做到。 ECC可使程序代码、密钥、证书的存储空间极小化
，数据帧最短，便于实现，大大降低了 IC卡的成本。
2012-3-19 100
椭圆曲线密码体制
? 在安全性方面,
Menezes,Okamoto和 Vanstone 指出应
避免选用超奇异曲线，否则椭圆曲线群上的
离散对数问题退化为有限域低次扩域上的离
散对数问题，从而能在多项式时间上可解。
他们还指出，若所用循环子群的阶数达 2160
，则可提供足够的安全性。
2012-3-19 101
椭圆曲线密码体制
? ECC和 RSA对比：在实现相同的安全性下,ECC 所
需的密钥量比 RSA少得多，如下表所示。其中 MIPS
年表示用每秒完成 100万条指令的计算机所需工作
的年数,m表示 ECC的密钥由 2 m点构成。以 40 MHz
的钟频实现 155 bits的 ECC,每秒可完成 40,000次
椭园曲线运算，其速度比 1024 bits的 DSA和 RSA快
10倍。
ECC的密钥长度 m RSA的密钥长度 MIPS-年
160 1024 1012
320 5120 1036
600 21000 1078
1200 120000 10168
2012-3-19 102
四、可证明性安全公钥密码
体制
2012-3-19 103
公钥加密中若干安全性概念
2012-3-19 104
OAEP方案、安全性结论
2012-3-19 105
OAEP方案、安全性结论
2012-3-19 106
OAEP方案、安全性结论
2012-3-19 107
OAEP方案、安全性结论
2012-3-19 108
OAEP方案、安全性结论
2012-3-19 109
OAEP方案、安全性结论
2012-3-19 110
OAEP方案、安全性结论
2012-3-19 111
OAEP方案、安全性结论
2012-3-19 112
Cramer-Shoup方案、安全性结论
第四章 公钥密码
http://web.xhu.edu.cn/jpkc/
2012-3-19 2
公钥密码
一、基本概念与简单算法
二,RSA公钥密码体制
三、离散对数公钥密码体制
四、可证明性安全公钥密码体制
2012-3-19 3
一,公钥密码体制的基本概念
Basic Concept of Public Key
Cryptography
2012-3-19 4
为什么需要公钥密码体制？
?密钥管理的方便
?数字签名的需要
2012-3-19 5
单钥加密体制的问题
E Network or Storage
明文
Plain
Text
密文
Cipher
Text
D
原明文
Original
Plain Text
Bob
私钥
Secret Key
Alice
私钥
Secret Key
密文
Cipher
Text
2012-3-19 6
单钥加密体制的问题
? 若 N个人相互保密通信，每人必须拥有 （ N-1）
个私钥,N很大时，需要保存的私钥很多。
如何解决？
? 可信中心分发：共需要发 N*(N-1)/2个私钥
N =1000时,999 *1000/2 = 499500
? 双方事先约定：用户之间自己秘密会面
（ 第一次远距离通信如何办？ ）
2012-3-19 7
基本概念
? 1976年,Standford Uni,Diffie博士和其导
师 Hellman 在 IEEE Trans,on IT 上发文
,New Direction in Cryptography”
? 这一体制的出现在密码学史上是划时代的
事件, 它为解决计算机信息网中的安全提
供了新的理论和技术基础 。 被公认为现代
密码学诞生的标志 。
2012-3-19 8
基本概念
?公钥密钥保密、认证系统的的安全性主
要取决于构造双钥算法所依赖的数学问题
。要求加密函数具有单向性，即求逆的困
难性。因此，设计双钥体制的关键是先要 寻求一个合适的 陷门单向函数 。
2012-3-19 9
基本概念
X ? ?Xf Y
? ?Yf 1?
公钥
私钥
2012-3-19 10
基本概念
单向函数：一个可逆函数 f,A?B,若它满足,
1o 对所有 x?A,易于计算 f(x)。
2o 对, 几乎所有 x?A”由 f(x)求 x“极为困难,
,以至于实际上不可能做到, 则称 f为一单向
(One-way)函数 。
? 定义中的, 易于计算, 是指函数值能在其输
入长度的多项式时间内求出, 即若输入长度
为 n,计算函数的时间是 na的倍数, a为一固
定的常数 。
? 若计算函数时间是 an的倍数, 则为不可能做
到的 。
2012-3-19 11
基本概念
? 陷门单向函数：单向函数是求逆困难的函数, 而
单向陷门函数, 是在不知陷门信息下求逆困难的
函数, 当知道陷门信息后, 求逆是易于实现的 。
这是 Diffie和 Hellmam[1976]引入的概念 。
? 例：号码锁 。
如何给陷门单向函数下定义则很棘手, 因为
(1) 陷门函数其实就不是单向函数, 因为单向函
数是在任何条件下求逆都是困难的；
(2) 陷门可能不止一个, 通过试验,一个个陷门就
可容易地 找到逆 。 如果陷门信息的保密性不
强, 求逆也就不难 。
2012-3-19 12
基本概念
? 单向函数是求逆困难的函数，而单向陷门函
数 (Trapdoor one-way function)，是在不知
陷门信息 下求逆困难的函数，当知道陷门信
息后，求逆是易于实现的。
? 限门单向函数是一族可逆函数 fk，满足
1,Y=fk(X)易于计算（当 k和 X已知）
2,X＝ f-1k(Y)易于计算（当 k和 Y已知）
3,X＝ f-1k(Y)计算上不可行（ Y已知但 k未知）
研究公钥密码算法就是找出合适的单向限 门函数
2012-3-19 13
基本概念
? 公钥密码基于的数学难题,
– 背包问题
– 大 整 数 分 解 问 题 （ The Integer
Factorization Problem,RSA体制 ） 。
– Diffie-Hellman问题 。
2012-3-19 14
基本概念
– 二次剩余问题。
– 模 n的平方根问题。
– 离散对数问题,
– 有限域的乘法群上的离散对数问题（ The
Discrete Logarithm Problem,ELGamal体制）
– 定义在有限域的椭圆曲线上的离散对数问题（
The Elliptic Curve Discrete Logarithm
Problem，类比的 ELGamal体制）。
2012-3-19 15
公钥密码体制的原理
Plain Text
m
E Network
Cipher
Text
C
Cipher Text
D
Plain Text
Alice
Bob,
Public Key Directory (公钥簿 )
Secret
Key
SKB
PKB
Bob
基本概念
2012-3-19 16
基本概念
? 基于公钥的加密过程,
明文输入 加密算法 解密算法
密文传送
明文输出
的公钥B 的私钥B
密文传送
加密算法 解密算法 明文输出
的公钥 的私钥
2012-3-19 17
? 每个用户都有一对选定的密钥 (公钥 PK；私
钥 SK)____也称为 双钥加密系统
? 加密用 （ 接收方的 ） 公钥, 解密用私钥
? 无需事先分配密钥 —解决了密钥分配问题 ！
基本概念
公钥密码体制的原理
2012-3-19 18
? 公钥密码体制的数学描述：满足如下条件的五元组
(M,C,K,E,D)
（ 1） M是可能消息的集合；
（ 2） C是可能密文的集合；
（ 3） K是可能密钥的有限集
（ 4） 对每一个 k=(PK,SK)?K,有 E PK ? E,D SK ? D,
满足对所有 m ? M,DSK (EPK(m)) = m
(5) 对所有 k,E PK ? D SK 是计算上不可能的。
基本概念
2012-3-19 19
公钥密码体制的模型由以下算法组成
? 密钥生成 KG ( ),根据输入的安全参数,输
出公钥和私钥对 (PK,SK)
? 加密 E( ),根据输入的公钥和消息,输出密
文。
? 解密 D( ),根据输入的解密私钥 和密文, 算
法输出消息或输出表示密文不合法的特殊符号
,?”
基本概念
2012-3-19 20
基本概念
? 公钥密码算法应满足的要求,
– 接收方 B产生密钥对在计算上是容易的
– 发方 A用 B公钥对消息 M加密成 C在计算上是容
易的
– 收方 B用自己的私钥对 C解密成 M在计算上是容
易的
– 敌人由 B的公钥求 B的私钥计算上不可行
– 敌人由 B的公钥和 C求明文 M,计算上不可行
– 加, 解密次序可换
2012-3-19 21
私钥系统与公钥系统的区别
? 单钥〈 ---〉双钥
? 对称〈 ---〉非对称
? 双向性〈 ---〉单向性
? 保险柜 〈 --〉 邮箱
? 私钥分发 〈 --〉 公钥管理
基本概念
2012-3-19 22
基本概念
? 对公钥密码体制的攻击,
由于公钥体制的加密变换是公开的，
使得任何人都可以采用 选择明文来攻击 双钥
体制，因此，明文空间必须足够大才能防止
穷尽搜索明文空间攻击。一种更强有力的攻
击法是 选择密文攻击,攻击者选择密文，而
后通过某种途径得到相应的明文，多数双钥
体制对于选择密文攻击特别敏感。
2012-3-19 23
基本概念
通常采用两类选择密文攻击,
在接收到待攻击的密文之前, 可以向攻击者提供他
们所选择的密文的解密结果 。
自适应选择密文攻击, 攻击者可能利用 (或接入 )被
攻击者的解密机 (但不知其秘密钥 ),而可以对他
所选择的, 与密文有关的待攻击的密文, 以及以
前询问得到的密文进行解密
2012-3-19 24
基本概念
? 公钥密码标准,
非官方工业标准 银行标准工业标准
国际标准
联邦标准
2012-3-19 25
简单算法
? 背包密码体制：由 Merkle 和 Hellman
1978年提出的第一个公钥密码算法 。 它
利用背包问题构造构造公钥密码, 只适
用于加密, 修正后方可用于数字签名 。
? 背包问题描述：给定重量分别为
的 n 个物品, 装入一个背包中要求重量
满足一个给定值, 找出究竟是哪些物品
？
naaaa,...,,321
2012-3-19 26
简单算法
? 0-1背包问题,1972年由 Karp提出的, 已知向量
, 其中 为正整数,
称其为背包向量 。 给定向量
求和 很容易, 只需要 n-1次加法 。 但已知
和, 求 则非常困难, 称其为背包问题, 又称子
集合问题 。 用穷举搜索法, 有 种可能, n非常
大时, 相当困难 。 背包问题是一个 NP完全问题
。
? ?naaaA,...,,21? ia
? ? ? ?1,0,,...,,21 ?? in xxxxx
ii xaS ??
A
S
n2
x
2012-3-19 27
简单算法
? 用背包问题构建公钥密码, 关键在于有两类
背包, 一类可以在线性时间内求解, 而另一
类则不能 。 把易解得背包问题转换成难解的
背包问题, 便可实现 。 即
– 公开密钥使用难解的背包问题
– 私钥使用易解的背包问题
2012-3-19 28
简单算法
? 易解的背包即简单背包：又名超递增背包, 若背包向量
满足
称为超递增背包向量, 相应背包为简单背包 。
简单背包很易求解, 因为给定 及,
易知
由此可得出解此背包的所谓贪心算法 。 先取最大的放入
背包, 若能 放入, 则另相应的 为 1,否则另相应
为 0。 从中减去, 再试, 以此类推, 直到决定出 的取
值 。
? ?naaaA,...,,21? ?
?
?
??
1
1
2,1,
i
j
ji Niaa ?
? ?naaaA,...,,21? S
?
?
?
??
??
?
n
n
n aS
aS
x
0
1
nx
1x
2012-3-19 29
简单算法
? 转换背包 （ Merkle-Hellman陷门背包 ）,这一体制的基
本想法是将一个简单背包进行伪装, 使得对所有其他人
为一个困难背包, 而对合法用户则为简单的背包 。 构造
方法如下,
（ 1） 各用户随机地选择一个超递增序列
A0=(a10,a20,…,aN0)。
（ 2） 将其进行随机排列得到矢量
A’=(a1’,a2’,…,aN’)。
（ 3） 随机地选择两个整数 u和 w使
u?2aN0
?
?
?
N
i
iau
1
2012-3-19 30
简单算法
且 gcd(u,w)=1 0<w<u
由 Euclidean算法可得出 a,b且 1=au+bw,由此
可得出 bw ?1 mod u,即 w-1? b mod u
（ 4） 计算 ai=w ? ai’ mod u,i=1,…,N 构造出新
的 (难的 ) 背包矢量 A=(a1,…,aN)。
（ 5） 陷门信息为 u和 w-1。 且用户收到加密信息 y
且, 先转成为整数 S, 而后计算 S’=(w-1?S)
mod u且最后可由简单背包
解出 x=(x1,x2,…,xN )。
?
?
?
N
i
ii axS
1
2012-3-19 31
简单算法
? 证明
? 这样就把有 S直接解难背包通过 转化为
解简单背包
uSwS m o d 1 ?? ?
uaxw
N
i
ii m o d
1
1 ?
?
? ??
uuawwx
N
i
ii m o d))m o d ((
1
1?
?
? ???
uuawwx
N
i
ii m o d))m o d (
1
1?
?
? ???
uax i
N
i
i m o d
1
?
?
?
)(
1 11
? ??
? ??
???
N
i
N
i
iii
N
i
ii uaaxax 因
uw,1?
2012-3-19 32
简单算法
? 基于背包问题的公钥密码系统 （ MH公钥算法
）,
– 加密：将明文分为长度为 的块
然后用公钥 将明文加密成密
文
– 解密：先计算 在求解简单
背包问题
n ? ?nxxxx,.,,,,21?
? ?''2'1',...,,naaaA ?
? ? ii xaXES ??? '
uSwS m o d1' ??
?? ii xaS '
2012-3-19 33
简单算法
? 例子：从私钥计算公钥
– 私钥 {2,3,6,13,27,52}
– w=31,u=105
2*31mod105=62
3*31mod105=93
6*31mod105=81
13*31mod105=88
27*31mod105=102
52*31mod105=37
– 公钥 {62,93,81,88,102,37}
2012-3-19 34
简单算法
? 例子：加密
– 消息 =011000 110101 101110
– 明文 0 1 1 0 0 0
– 背包 62,93,81,88,102,37
– 密文,93+81=174
– 011000对应 93+81=174
– 110101对应 62+93+88+37=280
– 101110对应 62+81+88+102=333
2012-3-19 35
简单算法
? 例子：解密
– 解密者知道 {2,3,6,13,27,52},n,u
– 计算,
– 174*61mod105=9=3+6对应 011000
– 280*61mod105=70=2+3+13+52对应 110101
– 333*61mod105=48=2+3+13+27对应 101110
– 因此消息为 011000 110101 101110
? ? ? ?uww m o d11 ??
611 ??w
2012-3-19 36
简单算法
? 背包密码系统的意义,
– 是 Diffe和 Hellman 1976年提出公钥密
码体制的设想后的第一个公钥密码体制
,由 Merkle和 Hellman在 1978年提出 。
– 由较好的理论价值 。
2012-3-19 37
简单算法
? 背包体制的缺陷：背包体制的加, 解密的速度远比RSA体制快的多, 它大约只需要 200次加法运算,
速度可与对称加密算法相比, 但有一些致命的弱点
,
– MH背包体制已经证明不安全, 大多数背包方案
都已被破解 。
– MH背包不是满射, 因而不能用作数字签字 。
Shamir曾提出一种可用于签字的背包体制
[1978],被 Odlyzko[1984]破译 。
– 消息扩展太大, n=200,每个密钥分量为 400
bit序列, 公钥 80 kb长 !
2012-3-19 38
二,RSA公钥密码体制
2012-3-19 39
RSA算法
2012-3-19 40
概况,
? MIT三位年青数学家 R.L.Rivest,A.Shamir和
L.Adleman 在 1978年发现了一种用数论构造双
钥体制的方法, 称作 MIT体制, 后来被广泛称
之为 RSA体制 。
? 它既可用于加密, 又可用于数字签名 。
? RSA算法的安全性基于数论中大整数分解的困
难性 。
RSA算法
2012-3-19 41
RSA算法
? 数论基础：算术基本定理
– 任意大于 1的整数 a都能被因式分解为如
下的唯一形式,
– 其中 都是素数
,而且每一个 。
t21 a
t
a
2
a
1 p...ppa ?
t21 p....pp ??
? ?t,...3,2,1i0a i ??
2012-3-19 42
RSA算法
? 数论基础：中国剩余定理
。同余的意义下有唯一解在模
则同余方程组
两两互素，并记设自然数
N
mbx
mbx
mbx
mmmNmmm
rr
rr
m o d
..,,,,,,,,,
..,,,,,,,,,
m o d
m o d
,...,...,
22
11
2121
?
?
?
?
?
2012-3-19 43
RSA算法
? 数论基础,Fermat’s Theorem
– Fermat定理,p是素数, a是整数且不
能被 p整除, 则,
– 推论,p是素数, a是任意整数, 则,
? 在公钥理论和素性检测中很重要 。
pm o d1a 1-p ?
pm o daa p ?
2012-3-19 44
RSA算法
? 数论基础,Euler’s Function
– 模 n的非负最小完全剩余系是
– 如果一个模 n的剩余类里面的数与 n互素, 就把
他叫做一个与模 n互素的剩余系 。
– 与模 n的全部剩余系中, 从每一个系中各取一
个数组成的数的集合叫做模 n的一个简化剩余
系 。
– Euler函数,定义为小于 n且与 n互素的正整
数个数 。
? ?1.,,,,3210 ?n，，，
? ?n?
2012-3-19 45
RSA算法
? 数论基础,Euler’s Theorem
– Euler定理：若 a与 n为互素的正整数,
则,
– 是 Fermat定理的推广 。
– 例子,a=3,n=10,； 因此
? ? nm o d1a n ??
? ? 4?n?
10m o d1813 4 ＝＝
2012-3-19 46
RSA算法
? 数论基础：欧拉定理推论
– 若 是素数
,k 是 任 意 整 数, 则,
对任意
qppqn ??,
? ? ? ?,m o d111 nmm qp ????
nm ??0
2012-3-19 47
算法描述－密钥产生 KG( ),
? 选取两互异大素数 p和 q
? 计算 n=p× q 和其欧拉函数值 ?(n)=(p－ 1)(q－ 1)
? 选一整数 e,1 < e<?(n),使得 gcd(?(n),e)=1
? 在模 ?(n)下, 计算 e的逆元 d,即求 d,使得
ed ≡ 1 mod ?(n)
? 以 (n,e )为公钥 。 d 为秘密钥 。
(p,q不再需要, 可以销毁 。 )
RSA算法
2012-3-19 48
算法描述－加密 E( )和解密 D( ),
? 加密：将明文分组, 各组对应的十进制数
m<n,计算
c =E(m)≡ me mod n
? 解密, m = D(c)≡ cd mod n
RSA算法
2012-3-19 49
解密正确性证明,
na n m o d1)( ??
Euler定理 若 a 与 n互素, 则
10m o d1813 4 ??如,a=3,n=10时
RSA算法
2012-3-19 50
解密正确性证明,
? 要证 cd mod n ≡ m, 由加密过程
cd mod n ≡ （ me） d mod n
≡ mk??n)+1 mod n （ ed ≡ 1 mod ?(n) )
1） 若 m与 n互素, 由欧拉定理 m??n)≡1 mod n
有 mk??n)≡1 mod n,
mk??n)+1≡ m mod n
RSA算法
2012-3-19 51
解密正确性证明,
2） 若 m与 n不互素, 即 gcd(m,n) ≠1,则 m
是 p的倍数或 q的倍数, 不妨设 m=cp （ c < q）
此时 gcd(m,q)=1,由欧拉定理,
m??q)≡1 mod q,[m??q)]k??p)≡1 mod q
即 mk??n)≡1 mod q,
于是存在一整数 r,使 mk??n)≡1 ＋ rq,
两边同乘 m=cp,得
mk??n)+1≡ m+rcpq=m+rcn,即 mk??n)+1≡ m mod n
RSA算法
2012-3-19 52
一个例子,
? 密钥生成
– 取,p=17,q=11那么 n=pq=17 × 11=187,
– 计算 ?(n)=(p－ 1)(q－ 1)=16 × 10=160
– 选取与 ?(n)=160互素的整数 e=7
– 按照扩展的欧几里德算法计算 d=e -1 mod ?(n)
= 7 -1 mod160= 23
– 公开密钥为 (n,e)=(187,7),私钥为 d=23,
RSA算法
2012-3-19 53
一个例子,
? 加密
c=me mod n
为了对消息 m =88加密, 按照如下步骤计算密文
c=memodn =887mod 187=11
RSA算法
2012-3-19 54
一个例子,
? 解密：当收到密文 c后，利用私钥计
算明文
88)187m o d (11 23 ??m
RSA算法
2012-3-19 55
RSA算法
? RSA加密实质上是一种 Zn?Zn上的单表代换
！ 给定 n=p1p2和合法明文 x?Zn,其相应密文
y=xe mod n ?Zn。 对于 x?x, 必有 y?y 。 Zn
中的任一元素 (0,p1,p2的倍数除外 )是一
个明文, 但它也是与某个明文相对应的一个
密文 。 因此, RSA是 Zn?Zn的一种单表代换
密码, 关键在于 n极大时在不知陷门信息下
极难确定这种对应关系, 而用模指数算法又
易于实现一种给定的代换 。 正由于这种一一
对应性使 RSA不仅可以用于加密也可以用于
数字签字 。
2012-3-19 56
对 RSA的攻击与参数选取
? 单向性是如何表现的？
? f,x ? f(x)=xe mod n
容易
? f -1,f(x) ? x 困难
? 陷门：私钥 d
f(x)d mod n =(xe)d mod n=x
2012-3-19 57
对 RSA的攻击与参数选取
? RSA的安全性是基于分解大整数的困难性
假定（尚未证明分解大整数是 NP问题 ）
m = D(c)≡ cd mod n ? d?
? 如果能分解 n=p× q，则立即可得 ?(n)=
(p－ 1)(q－ 1)，从而能够确定 e的模 ?(n)
乘法逆 d
2012-3-19 58
对 RSA的攻击与参数选取
数学技术 =Money？
? RSA-129历时 8个月于 1994年 4月被成功分解
(600多位科学家,100$)
? RSA－ 130于 1996年 4月被成功分解
? RSA－ 140于 1999年 2月被成功分解
? RSA－ 155于 1999年 8月被成功分解
? 密钥长度应该介于 1024bit到 2048bit之间
? 由 n直接求 ?(n)等价于分解 n
2012-3-19 59
对 RSA的攻击与参数选取
因子分解复杂度,
密钥长 (bit) 所需的 MIPS-年 *
116(Blacknet密钥 ) 400
129 5,000
512 30,000
768 200,000,000
1024 300,000,000,000
2048 300,000,000,000,000,000,000
* MIPS-年指以每秒执行 1,000,000条指令的计算机运
行一年
2012-3-19 60
对 RSA的攻击与参数选取
对 RSA的攻击,
（ 1 ） 迭代攻击法,Simmons 和
Norris曾提 迭代或循环攻击法 。 例如,
给定一 RSA的参数为 (n,e,y)=(35,17,
3),可由 y0=y=3计算 y1=317=33 mod 35。
再由 y1计算 y2=y117=3 mod 35,从而得到
明文 x=y1=33 mod 35。 一般对明文 x加密
多次, 直到再现 x为止 。 Rivest证明, 当
p1－ 1和 p2－ 1中含有大素数因子, 且 n足
够大时, 这种攻击法成功的概率趋于 0。
2012-3-19 61
对 RSA的攻击与参数选取
（ 2） 选择明文攻击
(a) 消息破译 。 攻击者收集用户 A以公
钥 e加密的密文 y=xe mod n,并想分析出消
息 x。 选随机数 r<n,计算 y1=re mod n,这
意味 r=y1d mod n。 计算 y2=y1× y mod n。
令 t=r-1 mod n,则 t=y1-d mod n。 现在攻
击者请 A对消息 y2进行签字 (用秘密钥, 但不
能用 Hash函数 ),得到 S=y2d mod n。 攻击
者计算 ts mod n=y1-d× y2d mod n=y1-
d× y1d× yd mod n=yd mod n=x,得到了明
文 。
2012-3-19 62
(b) 骗取仲裁签字。在有仲裁情况下,A
有一个文件要求仲裁，可先将其送给仲
裁 T,T以 RSA的秘密钥进行签署后回送给
A(未用单向 Hash函数，只以秘密钥对整
个消息加密 )。
攻击者有一个消息要 T签署，但 T并
不情愿给他签，因为可能有伪造的时戳
，也可能是来自另外人的消息。但攻击
者可用下述方法骗取 T签字。
2012-3-19 63
(c) 骗取用户签字。攻击者可制作两
条消息 x1和 x2,凑出所要的 x3?x1× x2
mod n。
首先他可得到用户 A对 x1和 x2的签
字 x1d mod n 和 x2d mod n,则可计
算 x3d mod n?(x1d mod n)?(x2d mod
n ) mod n。
因此，任何时候不要为不相识的
人签署随机性文件，最好先采用单向
Hash函数。 ISO 9796的分组格式可以
防止这类攻击。
2012-3-19 64
对 RSA的攻击与参数选取
令攻击者的消息为 x,他首先任意选一个数 N，
计算 y=Ne mod n(e是 T的公钥 ),而后计算
M=yx,送给 T,T将签字的结果 Md mod n送给
攻击者, 则有 ( Md mod n)N-1 mod n=(yx)d?N-1 mod n=xdyd?N-1 mod n=xdNN-1
mod n=xd mod n,此为 T对 x的签字 。
所以能有这类攻击是因为指数运算保持了输
入的乘法结构 。
2012-3-19 65
对 RSA的攻击与参数选取
（ 3） 共模攻击,
? 每一用户有相同的模数 n
? 设用户的公开密钥分别为 e1,e2,且 e1,e2互素，明文
消息为 m,密文为
? 因为（ e1,e2)=1,用欧几里德算法可求
r e1+s e2=1从而由 Euclidean算法可计算
c1r ? c2s=m mod n
nmc
nmc
e
e
m o d
m o d
2
1
2
1
?
?
2012-3-19 66
对 RSA的攻击与参数选取
（ 4） 低加密指数攻击：令网中三用户的加密钥 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
2012-3-19 67
对 RSA的攻击与参数选取
（ 5）定时攻击法,
定时 (Timing)攻击法由 P,Kocher提出，利
用测定 RSA解密所进行的模指数运算的时间来估
计解密指数 d,而后再精确定出 d的取值。 R,
Rivest曾指出，这一攻击法可以通过将解密运
算量与参数 d无关挫败。另外还可采用盲化技术
，即先将数据进行盲化，再进行加密运算，而
后做去盲运算。这样做虽然不能使解密运算时
间保持不变，但计算时间被随机化而难于推测
解密所进行的指数运算的时间 。
2012-3-19 68
对 RSA的攻击与参数选取
RSA的参数选取,
（ 1） n的确定
– n=p1× p2,p1与 p2必须为强素数 。
强素数 p的条件,（ a） 存在两个大素数 p1和 p2
,p1|(p－ 1),p2|(p＋ 1)。 （ b） 存在 4个大素数 r1,
s1,r2及 s2,使 r1|(p1－ 1),s1|(p1＋ 1),r2|(p2－
1),s2|(p2＋ 1)。 称 r1,r2,s1和 s2； p1和 p2为二级
素数 。
a
i
t
i
pR
1?
??
2012-3-19 69
采 用 强 素 数 的 理 由 如 下, 若
,pi为素数, ai为正整数 。 分解式中 pi<B
,B为已知一个小整数, 则存在一种 p－ 1
的分解法, 使我们易于分解 n。 令 n=pq，
且 p－ 1满足上述条件, pi<B。 令 a?ai，
i=1,2,…,t。 即可构造
显然 (p－ 1)?R。 由费尔马定理 2R?1
mod p。 令 2R=x mod n。 若 x =1则选 3代
2,直到出现 x?1。 此时, 由 GCD(x－ 1,
n)=p,就得到 n的分解因子 p和 q。
2012-3-19 70
简单算法
– p1与 p2之差要大 。 若 p1与 p2之差很小, 则可
由 n=p1p2估计 (p1＋ p2)/2=n1/2,则由 ((p1＋
p2)/2)2－ n=((p1－ p2)/2)2。 上式右边为小
的平方数, 可以试验给出 p1,p2的值 。
– p,q要足够大, 以使 n分解在计算上不可行
。
– p1－ 1与 p2－ 1的最大公因子要小 。 在惟密文
攻击下, 设破译者截获密文 y=x e mod n。
破译者做下述递推计算,
xi=xi-1e mod n=(xe)i mod n
2012-3-19 71
简单算法
（ 2） e的选取原则
(e,?(n))=1的条件易于满足, 因为两个随机数为
互素的概率约为 3/5。 e小时, 加密速度快, Knuth和
Shamir曾建议采用 e=3。 但 e太小存在一些问题 。
– e不可过小：若 e小, x小, y=xe mod n,当 xe<n，
则未取模, 由 y直接开 e次方可求 x。 易遭低指数攻
击 。
– 由选 e在 mod ?(n)中的阶数, 即 i,ei ?1 mod
?(n),i达到 (p1－ 1)(p2－ 1)/2。
2012-3-19 72
简单算法
（ 3） d的选择,
e选定后可用 Euclidean算法在多项式时间内
求出 d。 d要大于 n1/4。 d小, 签字和解密运算快,
这在 IC卡中尤为重要 (复杂的加密和验证签字可
由主机来做 )。 类似于加密下的情况, d不能太小
,否则由已知明文攻击, 构造 (迭代地做 )y=xe
mod n,再猜测 d值, 做 xd mod n,直到试凑出
xd?1 mod n是 d值就行了 。 Wiener给出对小 d的
系统攻击法, 证明了当 d长度小于 n的 1/4时, 由
连分式算法, 可在多项式时间内求出 d值 。 这是
否可推广至 1/2还不知道 。
。
2012-3-19 73
小结
? 公钥加密体制的基本思想
? 公钥加密体制的要求和特点
? 单向函数的基本特点
? RSA的具体方案和安全性考虑
? 如何实现安全的 RSA体制？
2012-3-19 74
三、离散对数公钥密码体制
2012-3-19 75
ElGamal密码体制
ElGamal密码体制：由 ElGamal[1984,1985]
提出, 是一种基于离散对数问题的公钥密码
体制, 既可用于加密, 又可用于签字 。
2012-3-19 76
ElGamal密码体制
? ElGamal方案,
（ 1） Zp, p个元素的有限域 p,一个素数
g：是 Zp＊ (Zp中除去 0元素 )中的一个本原
元或其生成元。
明文集 M, Zp＊ 密文集 C,Zp＊
× Zp＊ 。
公钥,选定 g(g <p的生成元 )，计算公钥
??g? mod p
秘密钥,?<p
2012-3-19 77
ElGamal密码体制
（ 2） 加密：选择随机数 k?Zp-1,且 (k,p－
1)=1,计算,
y1=g k mod p (随机数 k被加密 )
y2=M?k mod p(明文被随机数 k和公钥 ?加密 )
M是发送明文组。密文由 y1,y2级连构成，
即密文 C=y1||y2。
2012-3-19 78
ElGamal密码体制
特点：密文由明文和所选随机数 k来定，因
而是非 确定性加密，一般称
之为随机化加密，对 同一明文由于不
同时刻的随机数 k不同而给 出不同的
密文。代价是使 数据扩展 一倍。
（ 3）解密：收到密文组 C后，计算
M=y2/y1?=M? k/gk?=Mg?k/gk? mod p
2012-3-19 79
ElGamal密码体制
? 例子,
– 生成密钥：使用者 A选取素数 p=2357及 Z2357*的生成
元 2,A选取私钥 x=1751并计算
A的公钥是
– 加密：为加密信息 m=2053,B选一个随机整数
k=1520,并计算
然后发送给 A。
– 解密,
11852357m o d2m o d 1 7 5 1 ??pg x
1185,2,2357 ??? xggp
6972 3 5 7m o d1 1 8 52 0 3 5
1 4 3 02 3 5 7m o d2
1 5 2 0
1 5 2 0
???
??
b
a
2357m o d2035872697/
2357m o d87214301430 6 0 51
?????
???
?
???
xx
xpx
baabm
a
2012-3-19 80
ElGamal密码体制
? 上述方案是基于乘法群 Zp*建立的 ElGamal公
钥密码体制, 实际上可基于任何离散对数问
题难处理的群实现 ElGamal公钥密码体制 。
下面介绍推广的 ElGamal公钥密码体制 。
? 设群 G是一运算符为 × 的有限群, 子群 H是
由 a生成的, 且满足其上的离散对数问题是难
解的, 具体推广如下,
2012-3-19 81
ElGamal密码体制
? 系统参数,
? 加密：对于消息 m,选随机数
? 解密：消息接受者解密
? ? ? ? 1
1221,2
??? d
k yyyyd
? ? ? ? ? ?
kk
k
myay
yykmeHk
????
???
21
21
,
,,,1,0
1
其中
则密文为
? ?
?
?
,
,)(
0,
ad
aHdaH
iaHGaG
d
i
公钥：则私钥：
＝计算，选生成的是由即
的有限群，为运算符为
?
????
2012-3-19 82
ElGamal密码体制
? ElGamal签名,
pgy
pg
p
x m o d?
? （可由一组用户共享）
享）素数（可由一组用户共公钥：
px ?私钥：
)1m o d ()()(
m o d)(
1
???
?
pkbxaMb
pga
pk
k
满足签名
＝签名
互素，与签名：随机选取
签名有效验证：如果,m o dm o d pgpay Mba ?
2012-3-19 83
ElGamal密码体制
? ElGamal的安全性,
– 攻击该算法等价于解离散对数难题
– 要使用不同的随机数 k来加密不同的消息
,否则很容易被破解 。 假设用同一个 k来加
密两个消息 m1和 m2,所得的密文分别为 （
a1,b1),(a2,b2),则 b1/b2=m1/m2,故当 m1已
知, m2可以很容易的计算出来 。
2012-3-19 84
安全性分析
? 离散对数难题,
计算
– 已知 g,x,p时计算 y是容易的 。
– 已知 y,g,p时计算 x是困难的 。
? 一般的描述,
m o d pgy x?
? ?
? ?
?
?
?
a
y
i
y
aHy
H
iaHHGaG
l o g
,,1,0
,0,,
?
???
?????
们记为
我满足整数问题：能否找到唯一的
是由生成的。
即其中的有限群，是运算符为条件：设群
2012-3-19 85
安全性分析
? 密码学中常用的离散对数,
– 有限域 上的乘法群
– 有限域 上的乘法群
– 有限域 上的椭圆曲线群
? ?pGF
? ?n2GF
F
2012-3-19 86
安全性分析
? 求离散对数的算法介绍,Pohlig-Hellman算法
? ?
1210
1
0
1
,...,,
m o dl o g
,m o d01,m o d01
?
?
?
??
??
????
c
c
c
i
c
ia
cc
p
aaaa
qqa
qpqpqZa
的则算法用来计算满足
是素数，且的本原元，是
?
? ?
? ?
? ?
? ?
.1,,
,m o d
1
,0,.2
1,0,m o d.1
1
,
1
1
1
1
????
??
??
???
?
?
?
?
??
?
iiaja
j
p
do
ci
W h i l e
ii
qjpa
i
i
j
j
qa
iii
j
qp
i
ii
qp
j
??
??
??
???
?
＝满足找一个
＝计算
的初始值为
计算
2012-3-19 87
安全性分析
? 计算离散对数与因子分解有紧密的关系, 如果能
解决离散对数问题, 那么就能解决因子分解问题
,（ 逆命题的正确性还未被证明 ） 。 目前在素数
域上有 3种方法计算：线性筛选法, 高斯整数法,
和 NFS。
? 基本的扩展计算必须在每个域上做一次, 之后,
单个的对数就能快速进行计算, 对基于这些域的
系统而言, 是一个安全缺陷 。 所以, 不同的用户
采用不同的素数域很重要 。
2012-3-19 88
安全性分析
? Diffie-HEllman假定
? 一般可认为有两类假定 。
一, 计算 Diffie-Hellman 假定 （
Computational Diffie-HellmanAssumption,CDH)
。
二, 决定 Diffie-Hellman 假定 （ Decisional
Diffie-Hellman Assumption,DDH)。
? 两类假定均有 Diffie-Hellman问题引出, 当在某个
群或域上求解 Diffie-Hellman问题是困难时, 就认
为假定在该群或域上成立 。
2012-3-19 89
安全性分析
? CDH
Diffie-Hellman函数定义为,
如果在一个群上没有有效的算法能够
计算 Diffie-Hellman函数, 那么该群满足
CDH 假定 。 即已知
。
? ? abbag gggDH ?,
abba ggg 没有有效算法计算,
2012-3-19 90
安全性分析
? DDH
给定群 上 的 任 意 一 个 三 元 组
, 没有有效的概率算法
能够当 时, 输出, 真,, 否则输出,
假, 。
? 除 CDH和 DDH外, 还有推广的问题如
BDHP(Bilinear Diffie-Hellman Problem),
BIDHP(Bilinear Inverse Diffie-Hellman
Problem)等 。
cba ggg,,
3G
abc ?
2012-3-19 91
椭圆曲线密码体制
? 简要历史
椭圆曲线 (Elliptic curve)作为代数几何中的
重要问题已有 100多年的研究历史
1985年,N,Koblitz和 V,Miller独立将其引
入密码学中，成为构造公钥密码体制的一个有力工
具 。
利用有限域 GF(2n )上的椭圆曲线上点集所构成
的群上定义的离散对数系统，可以构造出基于有限
域上离散对数的一些公钥体制 --椭圆曲线离散对数
密码体制 (ECDLC )，如 Diffie-Hellman,ElGamal，
Schnorr,DSA等
2012-3-19 92
椭圆曲线密码体制
? 实数上的椭圆曲线,
? 其中的 是满足简单条件的
实数
? 一些曲线上的点连同无穷远点 O的集合 。
edxcxxbya x yy ?????? 232
edcba,,,,
2012-3-19 93
椭圆曲线密码体制
? 实数上的椭圆曲线例子,
132 ??? xxy
2012-3-19 94
椭圆曲线密码体制
? 运算定义,
SQQS
Q
OpRQp
XRQ
ppOOpp
ppX
pOpOOO
O
???
???
?????
????
于是线的另一交点
曲倍是，找到它的切线与的倍，一个点
，，则得到第三个点
轴不同，则画一连线，的和如果两个点
，于是
则轴两点一条竖直线交
，用作加法的单位：
，上，则其和为若曲线三点在一条直线
,
22
,
,;
11
2121
21
2012-3-19 95
椭圆曲线密码体制
? 有限域上的椭圆曲线,
? 模 P椭圆群记为 群中的元素 （ x,y)是满足
以上方程的小于 P的非负整数另外加上无穷远点
O
? 计算
pbap
pbaxxy
m o d0274
m o d
23
32
??
???
是奇素数，且
? ?,,baE p
? ?,,baE p
? ? ? ?。，记为其中
得到曲线上的点的确定是否可以求出有效
计算针对所有的
baEpyxyx
y
pbaxxpx
p
,,,,
,
m o d,0
3
?
????
2012-3-19 96
椭圆曲线密码体制
? 的加法规则,? ?baE
p,
? ? ? ? ? ?
? ? ? ?
? ? ? ? ? ?
? ?
? ? ? ?
? ? ? ?
1
2
1
1212
1313
21
2
3
332211
2/3,
/,
m o d
m o d
,,,,,
,,
,,,,,
yaxQP
xxyyQP
pyxxy
pxxx
yxQPyxQyxP
baEyxP
PyxOyxPyxP
POP
p
??
???
???
???
?????
??
??????
???
＝则如果
＝则其中，如果
为则如果
中也在。而且点，记为
的负点是则如果
?
?
?
?
2012-3-19 97
椭圆曲线密码体制
? ECC的加解密,
? ?
? ?
? ?
? ?
? ? ? ?
加密消息有扩张
解密
则重新选择为或者使得如果
计算密文然后选择随机数
中的一个点变换成为先把消息加密
保密
为公钥公开
然后计算秘密选择整数
值的最小的阶是指满足
是一个大素数的阶使得的元素选择
?
???????
??
?
??
?
?
mmmm
mm
mp
p
Prk Gk rGPkGrkPPC
kOkPkGk
kPPkGCk
PbaEMM
r
PPGbap
rGPr
nOnGG
nGGbaE
:
,
,,
,:
,,,,,
,,
,,
2012-3-19 98
椭圆曲线密码体制
? ECC加解密例子,
? ?
? ?
? ?
? ?
? ? ? ?
? ? ? ? ? ?
? ? ? ?? ?328385558676
328,3855,201386201,562
558,676376,0386
5,201
386,201,562
,
376,0,188
,188,1,751
32
，，，发送密文因此
我们有
的公钥是
选择随机数而椭圆曲线上的点
这个报文被编码为希望发送一个报文给假设
这等价于曲线取
A
kPP
kG
PB
kAP
BA
Gxxy
Ep
Bm
B
m
p
?
?????
???
?
??
?
????
???
2012-3-19 99
椭圆曲线密码体制
? ECC特别适用,
(1) 无线 Modem的实现：对分组交换数据网提供加密
，在移动通信器件上运行 4 MHz的 68330 CPU,ECC可实现
快速 Diffie-Hellman密钥交换，并极小化密钥交换占用的
带宽，将计算时间从大于 60秒降到 2秒以下。
(2) Web服务器的实现：在 Web服务器上集中进行密
码计算会形成瓶颈,Web服务器上的带宽有限使带宽费用
高，采用 ECC可节省计算时间和带宽，且通过算法的协商
较易于处理兼容性。
(3) 集成电路卡的实现,ECC无需协处理器就可以在
标准卡上实现快速、安全的数字签名，这是 RSA体制难以
做到。 ECC可使程序代码、密钥、证书的存储空间极小化
，数据帧最短，便于实现，大大降低了 IC卡的成本。
2012-3-19 100
椭圆曲线密码体制
? 在安全性方面,
Menezes,Okamoto和 Vanstone 指出应
避免选用超奇异曲线，否则椭圆曲线群上的
离散对数问题退化为有限域低次扩域上的离
散对数问题，从而能在多项式时间上可解。
他们还指出，若所用循环子群的阶数达 2160
，则可提供足够的安全性。
2012-3-19 101
椭圆曲线密码体制
? ECC和 RSA对比：在实现相同的安全性下,ECC 所
需的密钥量比 RSA少得多，如下表所示。其中 MIPS
年表示用每秒完成 100万条指令的计算机所需工作
的年数,m表示 ECC的密钥由 2 m点构成。以 40 MHz
的钟频实现 155 bits的 ECC,每秒可完成 40,000次
椭园曲线运算，其速度比 1024 bits的 DSA和 RSA快
10倍。
ECC的密钥长度 m RSA的密钥长度 MIPS-年
160 1024 1012
320 5120 1036
600 21000 1078
1200 120000 10168
2012-3-19 102
四、可证明性安全公钥密码
体制
2012-3-19 103
公钥加密中若干安全性概念
2012-3-19 104
OAEP方案、安全性结论
2012-3-19 105
OAEP方案、安全性结论
2012-3-19 106
OAEP方案、安全性结论
2012-3-19 107
OAEP方案、安全性结论
2012-3-19 108
OAEP方案、安全性结论
2012-3-19 109
OAEP方案、安全性结论
2012-3-19 110
OAEP方案、安全性结论
2012-3-19 111
OAEP方案、安全性结论
2012-3-19 112
Cramer-Shoup方案、安全性结论
