第四章 公钥密码体制
主讲人：朱天清
4.1 公钥密码体制的基本原理
对称密码体制的缺点,
密钥分配和管理
传统密钥管理两两分别用一对密钥时，则 n个用户需要
C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧
增大如,
n=100 时 C(100,2)=4,995
n=5000时 C(5000,2)=12,497,500
确证问题
? 数字签名
公开钥密码的基本思想
加密算法 E 解密算法 D
加密密钥 Ke 解密密钥 Kd
明文 m 明文 m
公开，其他用户可以像查
找电话号码一样查到
用户选择一对密钥 Ke和 Kd，分别为公开钥
和秘密钥，并构造加密算法 Ee和解密算
法 Ed
已知,C = E(M,Ke)
M = D(C,Kd)=D(E(M,Ke),Kd)
用户公开 Ke和 Ee
若用户 A想向用户 B传送一条消息 M
用户 A 用户 B
M
用户 A 用户 B
C
Ke Kd
对称密钥加密方法
公开密钥加密方法 1
用户 A 用户 B
C
KeB K
dB
A查到 B的公开加密钥 KeB,用它加密 M后得到 C,
将 C发给 B,B收到 C以后，用自己保密的解密钥
KdB解密 C,得到明文 M
查找
找到 KeB
方法 1缺点
任何人都能够冒充用户 A给 B发消息,B无
法察觉
用户 A 用户 B
C
KeB
KdB
查找
找到 KeB
用户 C 此消息对用户 A可
能不利
无法保证信息的真实性
公开密钥加密方法 2
用户 A 用户 B
C
KdA K
eA
查找
找到 KeA
A用自己保密的密钥 KdA解密 M,得到密文 C，将 C发给 B,B
收到 C以后，查 A的公开加密钥 KeA,用 KeA加密 C后得到明
文 M
方法 2缺点
用户 A 用户 B
C
KdA
KeA
查找
找到 KeA
用户 C
截获密文
用户 C获取了
明文
无法保证信息的秘密性
公开密钥加密方法 3
用户 A 用户 B
C
KeB KdB
查找
找到 KeB
KdA KeA
查找
找到 KeA
A用自己保密的解密钥 KdA解密 M,
得到中间密文 S
查到 B的公开加密钥 KeB
A用 KeB加密 S得到 C
A发 C给 B
S=D(M,KdA)
C=E(S,KeB)
用户 A
B用自己保密的解密钥 KdB解密 C,
得到中间密文 S
B接收 C
用 KeA加密 S得到 M
查到 A的公开加密钥 KeA
用户 B
D(C,KdB)=S
E(S,KeA)=M
保证了数据的秘密性和真实性
公开密钥密码应当满足的条件
加密算法和解密算法互逆，即对所有明文
都有
D(E(M,Ke),Kd)=M
计算上不能由 Ke求出 Kd
算法 E和 D都是高效的
E(D(M,Kd),Ke)=M
单项陷门函数
单向陷门函数是满足下列条件的函数 f
? (1)给定 x，计算 y=f(x)是容易的
? (2)给定 y,计算 x使 y=f(x)是困难的
(所谓计算 x=f-1(Y)困难是指计算上相当复杂已无
实际意义 )
? (3)存在 k 已知 k时,对给定的任何 y,若相应的 x存在,则
计算 x使 y=f(x)是容易的
注,1*,仅满足 (1) (2)两条的称为单向函数。第 (3)条称为陷门性称为陷门信息。
几个典型的公开钥密码系统
RSA系统
背包系统
椭圆曲线密码体制
4.2 RSA 算法
RSA公钥算法是由 Rivest,Shamir Adleman在
1978年提出 来 的。
该 算法的数学 基础 是 初 等数 论 中的 Euler (欧
拉 )定理,并建立 在大整数 因子 的困难性 之
上。
素数 (Prime Numbers)
一个大于 1的整数，如果它的正因数只有 1和它本
身，就叫做质数（素数），否则就叫做合数。
eg,2,3,5,7 素数,4,6,8,9,10 不是
素数在数论中具有重要的地位
小于 200 的素数有,
2 3 5 7 11 13 17 19 23 29 31 37 41
43 47 53 59 61 67 71 73 79 83 89 97
101 103 107 109 113 127 131 137 139
149 151 157 163 167 173 179 181 191
193 197 199
素因子分解
数 n的因子分解是把它写成其它数的乘积
n=a × b × c
相对于把因子相乘得到一个数，进行一个
数的因子分解是困难的。
素因子分解是把一个数写成素数的乘积形
式
eg,91=7× 13 ; 3600=24× 32× 52
RSA的安全性基于大整数分解因子的困难
性
N为两个大素数 p和 q的乘积，分解 n被认为
是非常困难的
生成 RSA密钥
选择两个素数 p,q,对外界保密
计算 n=pq
计算 ? (n)=(p-1)(q-1)
选择 e,使它成为是 ? (n)的一个互质数
确定 d,使得 de=1mod ? (n),并且 d< ? (n)
数字 n应该为 200位
或者是一个更大的
数字。这样,p和 q
都至少在 100位。
实际使用中，密钥
至少要 1024位。对
于敏感信息，可以
考虑 2046位或者以
上
基本算法
C=Me mod n
M=Cd mod n
公钥,{e,n}
私钥,{d,n}
在等式中,mod表示计算余数，例如 12 mod 10=2
例子,
选择 p=7,q=17
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算法的安全性
对 RSA算法的攻击实际上等效于对 n的乘积
分解。
? 由于 M=Cd mod n,n公开,则需要求出 d
? 有由于 de=1mod ? (n),e已知
? 需要求出 ? (n)
? 由于 ? (n)=(p-1)(q-1)，所以必须求出 p,q
? n=pq,所以必须对 n进行分解
PGP安装及使用
实验课程
PGP来源
PGP— Pretty Good Privacy，是一个基于
RSA公匙加密体系的加密软件
它采用了：审慎的密匙管理，
一种 RSA和传统加密的杂合算
法，用于数字签名的邮件文
摘算法，加密前压缩等，还
有一个良好的人机工程设计。
它的功能强大，有很快的速
度。而且它的源代码是免费
的。
PGP官方网站
目前最新版本某些功能需要注册以后才能使用
PGP6.5.3安装过程
点击安装
文件后出
现的画面，
表明文件
版本和安
装的注意
事项
相关的应用工具和帮助文档
PGP使用
使用 PGP之前，首先需要生成一对密钥，这一对密钥其实是同时生
成的，其中的一个我们称为公钥，你可以把它分发给你的朋友们，让他们
用这个密钥来加密文件，另一个私钥，这个密钥由你保存，你是用这个密
钥来解开加密文件的。
产生密钥
加密文件
数字签名
文件解密
验证签名并解密
安全删除
产生密钥
密钥产生过程
密钥产生过程
密钥产生过程
产生密钥
密钥的发送
把你的公用密钥发给你的朋友。用快捷键
Ctrl+E或者菜单 keys>Emport 将你的密钥导
出为扩展名为 asc或 txt的文件，将它发给你
的朋友们。（对方则用 Ctrl+M，
keys>import导入
文件加密
对文件加密非常简单，只须选中该文件，
然后点击右键中 PGP的 Encrypt，会弹出一
个对话框让你选择你要用的密钥，双击使
它加到下面的 Recipients框中即可。
文件加密
选中该文件，然后点击右键中
PGP的 Encrypt，会弹出一个
对话框让你选择你要用的密钥，
双击使它加到下面的
Recipients框中即可。
文件解密
解密时双击扩展名为 pgp
的文件或选中并点击右键
中的 PGP>Decrypt，在图
中的下框输入密码即可
加密的例子
加密的例子
用公钥加密，私钥解密。发给朋友的信
用对方的公钥加密，然后传给对方，对
方用自己的私钥解密
主讲人：朱天清
4.1 公钥密码体制的基本原理
对称密码体制的缺点,
密钥分配和管理
传统密钥管理两两分别用一对密钥时，则 n个用户需要
C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧
增大如,
n=100 时 C(100,2)=4,995
n=5000时 C(5000,2)=12,497,500
确证问题
? 数字签名
公开钥密码的基本思想
加密算法 E 解密算法 D
加密密钥 Ke 解密密钥 Kd
明文 m 明文 m
公开，其他用户可以像查
找电话号码一样查到
用户选择一对密钥 Ke和 Kd，分别为公开钥
和秘密钥，并构造加密算法 Ee和解密算
法 Ed
已知,C = E(M,Ke)
M = D(C,Kd)=D(E(M,Ke),Kd)
用户公开 Ke和 Ee
若用户 A想向用户 B传送一条消息 M
用户 A 用户 B
M
用户 A 用户 B
C
Ke Kd
对称密钥加密方法
公开密钥加密方法 1
用户 A 用户 B
C
KeB K
dB
A查到 B的公开加密钥 KeB,用它加密 M后得到 C,
将 C发给 B,B收到 C以后，用自己保密的解密钥
KdB解密 C,得到明文 M
查找
找到 KeB
方法 1缺点
任何人都能够冒充用户 A给 B发消息,B无
法察觉
用户 A 用户 B
C
KeB
KdB
查找
找到 KeB
用户 C 此消息对用户 A可
能不利
无法保证信息的真实性
公开密钥加密方法 2
用户 A 用户 B
C
KdA K
eA
查找
找到 KeA
A用自己保密的密钥 KdA解密 M,得到密文 C，将 C发给 B,B
收到 C以后，查 A的公开加密钥 KeA,用 KeA加密 C后得到明
文 M
方法 2缺点
用户 A 用户 B
C
KdA
KeA
查找
找到 KeA
用户 C
截获密文
用户 C获取了
明文
无法保证信息的秘密性
公开密钥加密方法 3
用户 A 用户 B
C
KeB KdB
查找
找到 KeB
KdA KeA
查找
找到 KeA
A用自己保密的解密钥 KdA解密 M,
得到中间密文 S
查到 B的公开加密钥 KeB
A用 KeB加密 S得到 C
A发 C给 B
S=D(M,KdA)
C=E(S,KeB)
用户 A
B用自己保密的解密钥 KdB解密 C,
得到中间密文 S
B接收 C
用 KeA加密 S得到 M
查到 A的公开加密钥 KeA
用户 B
D(C,KdB)=S
E(S,KeA)=M
保证了数据的秘密性和真实性
公开密钥密码应当满足的条件
加密算法和解密算法互逆，即对所有明文
都有
D(E(M,Ke),Kd)=M
计算上不能由 Ke求出 Kd
算法 E和 D都是高效的
E(D(M,Kd),Ke)=M
单项陷门函数
单向陷门函数是满足下列条件的函数 f
? (1)给定 x，计算 y=f(x)是容易的
? (2)给定 y,计算 x使 y=f(x)是困难的
(所谓计算 x=f-1(Y)困难是指计算上相当复杂已无
实际意义 )
? (3)存在 k 已知 k时,对给定的任何 y,若相应的 x存在,则
计算 x使 y=f(x)是容易的
注,1*,仅满足 (1) (2)两条的称为单向函数。第 (3)条称为陷门性称为陷门信息。
几个典型的公开钥密码系统
RSA系统
背包系统
椭圆曲线密码体制
4.2 RSA 算法
RSA公钥算法是由 Rivest,Shamir Adleman在
1978年提出 来 的。
该 算法的数学 基础 是 初 等数 论 中的 Euler (欧
拉 )定理,并建立 在大整数 因子 的困难性 之
上。
素数 (Prime Numbers)
一个大于 1的整数，如果它的正因数只有 1和它本
身，就叫做质数（素数），否则就叫做合数。
eg,2,3,5,7 素数,4,6,8,9,10 不是
素数在数论中具有重要的地位
小于 200 的素数有,
2 3 5 7 11 13 17 19 23 29 31 37 41
43 47 53 59 61 67 71 73 79 83 89 97
101 103 107 109 113 127 131 137 139
149 151 157 163 167 173 179 181 191
193 197 199
素因子分解
数 n的因子分解是把它写成其它数的乘积
n=a × b × c
相对于把因子相乘得到一个数，进行一个
数的因子分解是困难的。
素因子分解是把一个数写成素数的乘积形
式
eg,91=7× 13 ; 3600=24× 32× 52
RSA的安全性基于大整数分解因子的困难
性
N为两个大素数 p和 q的乘积，分解 n被认为
是非常困难的
生成 RSA密钥
选择两个素数 p,q,对外界保密
计算 n=pq
计算 ? (n)=(p-1)(q-1)
选择 e,使它成为是 ? (n)的一个互质数
确定 d,使得 de=1mod ? (n),并且 d< ? (n)
数字 n应该为 200位
或者是一个更大的
数字。这样,p和 q
都至少在 100位。
实际使用中，密钥
至少要 1024位。对
于敏感信息，可以
考虑 2046位或者以
上
基本算法
C=Me mod n
M=Cd mod n
公钥,{e,n}
私钥,{d,n}
在等式中,mod表示计算余数，例如 12 mod 10=2
例子,
选择 p=7,q=17
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算法的安全性
对 RSA算法的攻击实际上等效于对 n的乘积
分解。
? 由于 M=Cd mod n,n公开,则需要求出 d
? 有由于 de=1mod ? (n),e已知
? 需要求出 ? (n)
? 由于 ? (n)=(p-1)(q-1)，所以必须求出 p,q
? n=pq,所以必须对 n进行分解
PGP安装及使用
实验课程
PGP来源
PGP— Pretty Good Privacy，是一个基于
RSA公匙加密体系的加密软件
它采用了：审慎的密匙管理，
一种 RSA和传统加密的杂合算
法，用于数字签名的邮件文
摘算法，加密前压缩等，还
有一个良好的人机工程设计。
它的功能强大，有很快的速
度。而且它的源代码是免费
的。
PGP官方网站
目前最新版本某些功能需要注册以后才能使用
PGP6.5.3安装过程
点击安装
文件后出
现的画面，
表明文件
版本和安
装的注意
事项
相关的应用工具和帮助文档
PGP使用
使用 PGP之前，首先需要生成一对密钥，这一对密钥其实是同时生
成的，其中的一个我们称为公钥，你可以把它分发给你的朋友们，让他们
用这个密钥来加密文件，另一个私钥，这个密钥由你保存，你是用这个密
钥来解开加密文件的。
产生密钥
加密文件
数字签名
文件解密
验证签名并解密
安全删除
产生密钥
密钥产生过程
密钥产生过程
密钥产生过程
产生密钥
密钥的发送
把你的公用密钥发给你的朋友。用快捷键
Ctrl+E或者菜单 keys>Emport 将你的密钥导
出为扩展名为 asc或 txt的文件，将它发给你
的朋友们。（对方则用 Ctrl+M，
keys>import导入
文件加密
对文件加密非常简单，只须选中该文件，
然后点击右键中 PGP的 Encrypt，会弹出一
个对话框让你选择你要用的密钥，双击使
它加到下面的 Recipients框中即可。
文件加密
选中该文件，然后点击右键中
PGP的 Encrypt，会弹出一个
对话框让你选择你要用的密钥，
双击使它加到下面的
Recipients框中即可。
文件解密
解密时双击扩展名为 pgp
的文件或选中并点击右键
中的 PGP>Decrypt，在图
中的下框输入密码即可
加密的例子
加密的例子
用公钥加密，私钥解密。发给朋友的信
用对方的公钥加密，然后传给对方，对
方用自己的私钥解密
