公钥密码体制的基本原理
对称密码体制的缺点
• 密钥必须秘密地分配 • 如果密钥被损害了，攻击者就能解密所有消息，并可以假
装是其中一方。
• 密钥分配和管理
传统密钥管理两两分别用一对密钥时，则当用户量增大时密钥空 间急剧增大如:
n=100 时C(100,2)=4,995 n=5000时C(5000,2)=12,497,500
为素数的概率为1-ε ，若r足够大(如r=100)，则几乎认 为N是素数。
②确定性验证素数法
定理 令 pi+1=hipi+1，若满足下述条件，则pi+1必为素数。 (1) pi是奇素数; (2) hi<4(pi+1), hi为偶数;
(3) 2hi pi 1 mod pi1; (4) 2hi 1 mod pi1
A用KeB加密S得到C
C=E(S, KeB) A发C给B
结论
B接收C
B用自己保密的密钥KdB解密C, 得到中间密文S
D(C,KdB)=S 查到A的公开加密钥KeA
E(S,KeA)=M 用KeA解密S得到M
保证了数据的秘密性和真实性
公钥密码应当满足的条件
• 加密算法和解密算法互逆，即对所有明文都有 D(E(M,Ke),Kd)=M
RSA算法描述
1.生成RSA密钥
• 选择两个素数p,q,对外界保密 • 计算n=p*q • 计算Ø (n)=(p-1)(q-1) • 选择e , 使它成为是Ø (n)的一个互质数
数字n应该为200 位或者是一个更大 的数字。这样，p 和q都至少在100 位。实际使用中， 密钥至少要1024 位。对于敏感信息， 可以考虑2048位 或者以上
C 用户A
KdA
截获密文
方法2缺点
用户B
用户C
查找
KeA
用户C获取了明文
找到KeA
结论 方法2无法保证信息的秘密性
公开密钥加密方法3
C 用户A
KeB KdA
查找
找到KeB
用户B KdB KeA
查找
找到KeA
用户A
用户B
A用自己保密的密钥KdA加密M, 得到中间密文S
S=D(M,KdA) 查到B的公开加密钥KeB
2 1 2 0
1 3 21 3 (5 3) 325
(13 5 2) 2 5
13 2 5 5 13 2 5 (2436 13187)
937 13 5 2436
左右同时模2436，即 937×13≡1 mod 2436
即取
e=13, d=937
加密
明文public key encryptions，先将明文按两个一组进行 分块，再将明文数字化，如按英文字母表的顺序得： pu=1520, bl=0111, ic=0802, ke=1004, ye=2404, nc=1302, ry=1724, pt=1519, io=0814, ns=1418。
数字签名
公钥密码算法
• 用户选择一对密钥 Ke和 Kd，分别为公钥和私钥， 并构造加密算法 Ee 和解密算法 Ed 。
• C = E(M,Ke) M = D(C,Kd)=D(E(M,Ke),Kd)
• 用户公开Ke和Ee
注意： 密钥都是成对生成的，由一个公钥和一个私钥组成。
公钥密码的基本思想
加密密钥Ke
方法1缺点
• 任何人都能够冒充用户A给B发消息，B无法察觉
用户A
用户B
KdB
C
此消息对用户A可 能不利
查找 找到KeB
用户C
KeB
结论 方法1无法保证信息的真实性
公开密钥加密方法2
C 用户A
KdA
用户B
KeA
查找
找到KeA
A用自己保密的密钥 KdA 加密 M,得到密文C，将C发给 B，B收到C以后，查A的公开加密钥 KeA ,用 KeA 解密C 后得到明文 M 。
素数位数 64 bit 128 bit 256 bit
所含素数个数 2.05×1017 1.9×1036 3.25×1074
问题3. 如何产生一个素数?
①概率测试素数法
方法：对于一个给定的大正整数N，每进行一次检验， 给出yes：N为素数的概率为1/2，或者no：N不是素数， 若N通过r次检验，则N不是素数的概率为ε=2-r ，则N
n
n1
r 0 n1
gcd(a, b) rn
例：利用Euclid 算法求gcd(1694，917)
1694 917 1 777 917 777 1140 777 140 5 77
140 77 1 63
77 63114 63 14 4 7 14 7 2 0
得 gcd(1694，917) = 7
利用 ci≡mei mod n 加密得：pu=0095, bl=1648,
ic=1410 , ke=1299, ye=1365, nc=1379, ry=2333, pt=2332, io=1751, ns=1289。
例题：
设张小姐需要发送机密信息（明文）m=85给李先 生，她已经从公开媒体得到了李先生的公开密钥（n， e）=（143，7），计算密文为：
给定一个奇合数n和整数a，决定是否a为mod n平方 剩余问题。
几个典型的公开钥密码系统
• 菲-赫尔曼（Diffie-Hellman）密码系统 • RSA系统 • 背包系统 • 椭圆曲线密码体制
RSA 算法
• RSA公钥算法是由Rivest,Shamir Adleman在1978年提 出来的。
• 该算法的数学基础是初等数论中的Euler (欧拉)定理, 并建立在大整数因子的困难性之上。
安全素数
所谓安全素数p，应满足： (1) p是一个位数足够大的随机素数; (2) p-1含有一个大的素数因子r; (3) p+1含有一个大的素数因子; (4) r-1含有一个大的素数因子t
如何获得安全素数？
(1) 选择两个指定长度的奇数a, b (2) 在a附近产生随机素数s，在b附近产生随机素数t (3) 由t产生素数r
① r=1+2t; ② 若r非素数，则r=r+2直到r (4) 由r, s生成p: ① p=(sr-1-rs-1) mod (rs); ② 若p为偶数, 则p=p+rs; ③ p=p+2rs 直到p为素数。
高次幂的求模算法
C=Me mod p，已知M、e、p，
C？
步骤如下： 将e用二进制表示, e=kt, kt-1, …, k0, ki∈{0, 1}, 0≤i≤t c=1 For i=t~0 C=C2 mod p 若ki=1，则C=C(M mod p) mod p
• RSA算法起源
欧拉定理
若整数a和m互素，则
aφ(m)≡1 mod m
其中, φ(m)是比m小，且与m互素的正整数个数。
素数
一个大于1的整数，如果它的正因数只有1和它本身，就 叫做质数（素数），否则就叫做合数。
素因子分解
• 数n的因子分解是把它写成其它数的乘积 n=a × b × c
• 素因子分解是把一个数写成素数的乘积形式 eg. 91=7×13
• N=pq=119, Ø (n)=(p-1)(q-1)=6*16=96
• 选择随机整数e=5，与96互素
• 找出d,使得d*e=1mod96,选择d=77
• 算法 C=Me mod n
M=Cd mod n
• 选择明文19，C=195mod119=66
• 密文66，M=6677mod119=19
RSA算法的安全性
• 确定d , 使得d*e=1mod Ø (n),并且d< Ø (n)
d为私钥，e为公钥，p、q不再需要，丢弃。
RSA算法描述
2.加密
(1) 把m分成等长数据块m1、m2、…、mi ，块长s，其中 2s≤n，s要尽可能的大。
(2) 对应的密文是
3. 解密
ci≡mei mod n
mi
C
d i
mod n
• 相对于把因子相乘得到一个数，进行一个数的因子分解是 困难的。
欧几里（Euclid ）算法
gcd(a, b) ?
用于求两个数 的最大公约数
a bq r
1
1
b rq r
12
2
r rq r
1
23
3
0r b 1
0r r
2
1
0r r
3
2
r r q r
n2
n1 n
n
r rq r
n1
n n1
n1
0r r
• 对RSA算法的攻击实际上等效于对n的乘积分解。 – 由于M=Cd mod n, n公开,则需要求出d – 由于de=1mod Ø (n), e已知 – 需要求出Ø (n) – 由于Ø (n)=(p-1)(q-1)，所以必须求出p,q – n=pq,所以必须对n进行分解
大素数分解记录
最新纪录
2007年，瑞士洛桑理工学院的Arjen Lenstra宣称，他们 的分布式计算工程在经过11个月的努力后破解了一个307位的 RSA密钥，并且已经有能力在不久后破解700位，因此他警告 说，在五六年后，随着各种计算、破解技术的不断强大，也许 1024位的RSA加密都不能完全保险，人们必须寻求更安全的加 密技术。
解密密钥Kd
明文m
加密算法E
解密算法D
明文m
公开，其他用户可以像查 找电话号码一样查到
若用户A想向用户B传送一条消息M
M 用户A
用户B
对称密钥加密方法
C 用户A
Ke
用户B Kd
公开密钥加密方法1
C 用户A
KeB
查找 找到KeB