密码学基础

Key
对称密钥密码的模型
2.3.1 对称密钥密码加密模式
• 对称密码加密系统从工作方式上可分为：
– 分组密码、序列密码
• 分组密码原理：
– 明文消息分成若干固定长度的组，进行加密；解密亦然。
明文分组 key 密文分组 BLOCK1 L bit 加密E Mbit BLOCK1 解密D L bit BLOCK1 BLOCK2 L bit 加密E Mbit BLOCK2 解密D L bit BLOCK2 BLOCK3 L bit 加密E Mbit BLOCK3 解密D L bit BLOCK3 …… …… …… key BLOCK n L bit 加密E Mbit BLOCK n key 解密D L bit BLOCK n
• 密钥范围
– K1：所有和26互素的数。K1=1？ – k2：1-25的整数。K2=0？
仿射密码事例
– 设k=(5, 3)，注意到5# mod 26=21. – 加密函数：
• Ek(x)=5x+3 (mod 26)，
– 解密函数：
• Dk(y)=21(y -3) mod 26 =21y – 11 (• 公元前一世纪，古罗马皇帝凯撒曾使用移位密码。 宋代的曾公亮、丁度等编撰《武经总要》中“字验”。 20世纪初，出现了最初的机械式和电动式密码机。 60年代后，电子密码机得到较快发展和应用。
2.1.2 密码体制
– 消息（为了沟通思想而传递的信息）在密码学中 被称为明文（Plain Text）。 – 伪装消息以隐藏它的内容的过程称为加密(Encrypt) – 被加密的消息称为密文(Cipher Text) – 把密文转变为明文的过程称为解密(Decrypt)。
2.1 密码学基础知识
2.1.1 引言
– 解决信息的机密性、完整性、不可否认性以及身份 识别等问题均需要以密码为基础。
• 密码技术是保障信息安全的核心基础。
– 密码学(Cryptography)包括密码编码学和密码分析学 两部分。
• 将密码变化的客观规律应用于编制密码，用来保守通信 秘密的，称为密码编码学； • 研究密码变化客观规律中的固有缺陷，并应用于破译密 码以获取通信情报的，称为密码分析学。
伪随机字节发生器 （密钥流发生器） 伪随机字节K 明文字节流M 密文字节流C
+
加密
+
解密
10000110 …… …… 00011000 00011011
序列密码工作原理示意图
2.3.2 数据加密标准DES
– 1973年美国国家标准局NBS公开征集国家密码标 准方案；
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 算法必须提供高度的安全性； 算法必须有详细的说明，并易于理解； 算法的安全性取决于密钥，不依赖于算法； 算法适用于所有用户； 算法适用于不同应用场合； 算法必须高效、经济； 算法必须能被证实有效； 算法必须是可出口的。
凯撒Caesar密码
• 凯撒密码体系的数学表示：
– M=C={有序字母表}，q = 26，k = 3。
• 其中q 为有序字母表的元素个数，本例采用英文字 母表，q = 26。
– 使用凯撒密码对明文字符串逐位加密结果：
• 明文信息M = meet me after the toga party • 密文信息C = phhw ph diwho wkh wrjd sduwb
密钥ke 破译者 明文 加密 密文 信道 发送方 加密通信模型 接收方 密文 解密 明文 密钥kd
2.1.2 密码体制
– 完整密码体制要包括如下五个要素：
• • • • • M是可能明文的有限集，称为明文空间； C是可能密文的有限集，称为密文空间； K是一切可能密钥构成的有限集，称为密钥空间； E为加密算法，对于任一密钥， 都能够有效地计算； D为解密算法，对于任一密钥，都能够有效地计算。
0.978
0.095
0.074
a
b c
d e
f
g
h
i
j
k
l m n o p q
r
s
t
u v w x
y
z
2.2.2多表代替密码
– 多表代替密码是以一系列代替表依次对明文消 息的字母进行代替的加密方法。
– 多表代替密码使用从明文字母到密文字母的多 个映射来隐藏单字母出现的频率分布。每个映 射是简单代替密码中的一对一映射。 – 非周期多表代替密码
LS-1 LS-2 P8 5 LS-1 5 8 LS-2 5
10位密钥 K0 P10 10
5
5
5 P8 8
K1 S-DES的密钥产生
K2
8位明文
S-DES的加密变换过程
• 初始置换IP 和末尾置换IP-1
4 E/P 8
8 IP 4
– IP = (2,6,3,1,4,8,5,7) – IP-1 = (4,1,3,5,7,2,8,6) – 例子：1110 0100
• 古典替换密码：单表代替密码，多表代替密码以及 轮换密码。 • 对称密钥密码：分组密码和流密码。 • 公开密钥密码：加密和解密使用不同的密钥。
– 密码分析也称为密码攻击，密码分析攻击主要 包括：
• 唯密文攻击、已知明文攻击、选择明文攻击、自适 应选择明文攻击、选择密文攻击、选择密钥攻击。
2.2 古典替换密码
F
4 S0 2
LS-1 LS-2 P8 5 LS-1 5 8 LS-2 5
10位密钥 K0 P10 10
5
5
5 P8 8
K1
K2
S-DES的密钥产生
– P10和P8是置换函数，LS是循环左移函数 – 例子：
• P10 =(3,5,2,7,4,10,1,9,8,6)； P8=(6,3,7,4,8,5,10,9) • K0=1010000010；K1=10100100；K2=01000011
– 是以移位代替为基础的周期多表代替密码。 – 加密时每一个密钥被用来加密一个明文字母，当所 有密钥使用完后，密钥又重新循环使用。 – Ek(m)=C1 C2 … Cn，其中Ci=（mi + ki）mod 26； – 密钥K可以通过周期性反复使用以至无穷。
2.3 对称密钥密码
攻击者 发送方 Key 密文 公共信道 明文 安全信道 密文 明文 接收方 Key
密钥取值与乘法逆元
• K#为k在模q下的乘法逆元：
– 其定义为k# * k mod q =1， – 可采用扩展的欧几里德算法。欧几里德算法又 称辗转相除法，用于计算两个整数a和b的最大 公约数。
• 乘数密码的密钥k与26互素时，加密变换才 是一一映射的。
– k的选择有11种：3、5、7、9、11、15、17、 19、21、23、25。K取1时没有意义。 – k取13会如何？
key 明文分组
分组密码工作原理示意图
序列密码（流密码）
• 通过伪随机数发生器产生性能优良的伪随机序列(密钥流) ，用该序列加密明文消息流，得到密文序列；解密亦然。
密钥Key 密钥Key
明文字节流M 10000110 …… …… 00011000 00011011
伪随机字节发生器 （密钥流发生器） 伪随机字节K
乘数密码
• 乘数密码
– 将明文字母串逐位乘以密钥k并进行模运算。 – 数学表达式:Ek ( m )=k * m mod q, gcd (k, q) = 1。
• gcd(k,q)=1表示k与q的最大公因子为1。
– 例子：
• M=C=Z/(26)，明文空间和密文空间同为英文字母表空 间，包含26个元素；q=26； • K={k∈整数集 | 0<k<26，gcd(k,26)=1}，密钥为大于0小 于26，与26互素的正整数； • Ek ( m ) = k m mod q。 • Dk#(c)=k#c mod q，其中k#为k在模q下的乘法逆元。
14 12
12.702
相对使用频度（%）
10
8.167
9.056 6.996 6.094 4.253 4.025
2.228 2.015 0.772 0.153
8 6 4 2 0
2.782
1.492
7.507 6.749
6.327 5.987
2.406
2.758 1.929
2.36
1.974 0.15
10位密钥 加密过程 P10 8位明文 Shift IP P8 fk SW IP-1 8位明文 解密过程
K1
Shift P8
K1
fk SW
fk IP-1
K2
K2
fk IP
8位密文 S-DES的体制
8位密文
S-DES的密钥产生
– P10和P8是置换函数，LS是循环左移函数 – 例子：
• P10 =(3,5,2,7,4,10,1,9,8,6)； P8=(6,3,7,4,8,5,10,9) • K0=1010000010；K1=？；K2=？ • 00001循环左移两位 00100 ，循环右移位01000
– 加密明文“yes”的加密与解密过程如下：
Ek y e s
= 5×
24 4 18
+
3 3 3
=
19 23 15
=
t x p
21 ×
19 23 15
-
11 11 11
=
24 4 18
=
y e s
Mod 26 加密过程
Mod 26 解密过程
基于统计的密码分析
• 简单代替密码的加密是从明文字母到密文字母的一一映射 • 攻击者统计密文中字母的使用频度，比较正常英文字母的 使用频度，进行匹配分析。 • 如果密文信息足够长，很容易对单表代替密码进行破译。
2.2.1 简单代替密码
– 简单代替密码