密码学基础

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
S-DES
• S-DES加密算法
– S-DES是由美国圣达卡拉大学的 Edward Schaeffer教授提出的， 主要用于教学，其设计思想和 性质与DES一致，有关函数变 换相对简化，具体参数要小得 多。 – 输入为一个8位的二进制明文 组和一个10位的二进制密钥， 输出为8位二进制密文组； – 解密与加密基本一致。 – 加密:IP-1(fk2(SW(fk1(IP(明文))))) – 解密: IP-1(fk1(SW(fk2(IP(密文)))))
密钥取值与乘法逆元
• 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会如何？
• 古典替换密码：单表代替密码，多表代替密码以及 轮换密码。 • 对称密钥密码：分组密码和流密码。 • 公开密钥密码：加密和解密使用不同的密钥。
– 密码分析也称为密码攻击，密码分析攻击主要 包括：
• 唯密文攻击、已知明文攻击、选择明文攻击、自适 应选择明文攻击、选择密文攻击、选择密钥攻击。
2.2 古典替换密码
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
2.1 密码学基础知识
2.1.1 引言
– 解决信息的机密性、完整性、不可否认性以及身份 识别等问题均需要以密码为基础。
• 密码技术是保障信息安全的核心基础。
– 密码学(Cryptography)包括密码编码学和密码分析学 两部分。
• 将密码变化的客观规律应用于编制密码，用来保守通信 秘密的，称为密码编码学； • 研究密码变化客观规律中的固有缺陷，并应用于破译密 码以获取通信情报的，称为密码分析学。
LS-1 LS-2 P8 5 LS-1 5 8 LS-2 5
10位密钥 K0 P10 10
5
5
5 பைடு நூலகம்8 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
凯撒Caesar密码
• 凯撒密码体系的数学表示：
– M=C={有序字母表}，q = 26，k = 3。
• 其中q 为有序字母表的元素个数，本例采用英文字 母表，q = 26。
– 使用凯撒密码对明文字符串逐位加密结果：
• 明文信息M = meet me after the toga party • 密文信息C = phhw ph diwho wkh wrjd sduwb
– 历史
• • • • 公元前一世纪，古罗马皇帝凯撒曾使用移位密码。 宋代的曾公亮、丁度等编撰《武经总要》中“字验”。 20世纪初，出现了最初的机械式和电动式密码机。 60年代后，电子密码机得到较快发展和应用。
2.1.2 密码体制
– 消息（为了沟通思想而传递的信息）在密码学中 被称为明文（Plain Text）。 – 伪装消息以隐藏它的内容的过程称为加密(Encrypt) – 被加密的消息称为密文(Cipher Text) – 把密文转变为明文的过程称为解密(Decrypt)。
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
2.2.1 简单代替密码
– 简单代替密码
• 指将明文字母表M中的每个字母用密文字母表C中的 相应字母来代替。 • 例如：移位密码、乘数密码、仿射密码等。
– 移位密码
• 具体算法是将字母表的字母右移k个位置，并对字母 表长度作模运算。
– 每一个字母具有两个属性：本身代表的含义；可计算的位置 序列值。 – 加密函数：Ek(m) = (m + k) mod q。 – 解密函数：Dk (c) = ( c – k ) mod q。
伪随机字节发生器 （密钥流发生器） 伪随机字节K 明文字节流M 密文字节流C
+
加密
+
解密
10000110 …… …… 00011000 00011011
序列密码工作原理示意图
2.3.2 数据加密标准DES
– 1973年美国国家标准局NBS公开征集国家密码标 准方案；
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 算法必须提供高度的安全性； 算法必须有详细的说明，并易于理解； 算法的安全性取决于密钥，不依赖于算法； 算法适用于所有用户； 算法适用于不同应用场合； 算法必须高效、经济； 算法必须能被证实有效； 算法必须是可出口的。
– 1974年NBS开始第二次征集时，IBM公司提交了 算法LUCIFER。
2.3.2 数据加密标准DES
– 1975年，NBS公开了LUCIFER的全部设计细节并 指派了两个小组进行评价。 – 1976年，LUCIFER被采纳为联邦标准，批准用于 非军事场合的各种政府机构。 – 1977年，LUCIFER被美国国家标准局NBS作为“ 数据加密标准 FIPS PUB 46”发布，简称为DES。
• 若映射系列是非周期的无限序列，则相应的密码称 为非周期多表代替密码。 • 对每个明文字母都采用不同的代替表(或密钥)进行加 密，称作一次一密密码。
维吉尼亚Vigenère密码
– 周期多表代替密码： • Vigenère、Beaufort、Running Key、Vernam和 轮转机等密码。 • 维吉尼亚Vigenère密码：
– 密码体系必须满足如下特性：
• 加密算法(Ek：M->C)和解密算法(Dk：C->M)满足:
– Dk(Ek(x))=x, 这里xϵM；
• 破译者不能在有效的时间内破解出密钥k或明文x。
2.1.3 密码的分类
– 密码学发展的三个阶段：
• 古代加密密码、古典密码、近代密码
– 依据密码体制的特点以及出现的时间分类：
key 明文分组
分组密码工作原理示意图
序列密码（流密码）
• 通过伪随机数发生器产生性能优良的伪随机序列(密钥流) ，用该序列加密明文消息流，得到密文序列；解密亦然。
密钥Key 密钥Key
明文字节流M 10000110 …… …… 00011000 00011011
伪随机字节发生器 （密钥流发生器） 伪随机字节K
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多表代替密码
– 多表代替密码是以一系列代替表依次对明文消 息的字母进行代替的加密方法。
– 多表代替密码使用从明文字母到密文字母的多 个映射来隐藏单字母出现的频率分布。每个映 射是简单代替密码中的一对一映射。 – 非周期多表代替密码
– 是以移位代替为基础的周期多表代替密码。 – 加密时每一个密钥被用来加密一个明文字母，当所 有密钥使用完后，密钥又重新循环使用。 – Ek(m)=C1 C2 … Cn，其中Ci=（mi + ki）mod 26； – 密钥K可以通过周期性反复使用以至无穷。
2.3 对称密钥密码
攻击者 发送方 Key 密文 公共信道 明文 安全信道 密文 明文 接收方 Key
– 加密明文“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 解密过程
基于统计的密码分析
• 简单代替密码的加密是从明文字母到密文字母的一一映射 • 攻击者统计密文中字母的使用频度，比较正常英文字母的 使用频度，进行匹配分析。 • 如果密文信息足够长，很容易对单表代替密码进行破译。
仿射密码
• 仿射密码
– 可以看作是移位密码和乘数密码的结合。
• 密码体制描述如下：
– M=C=Z/(26)；q=26； – K={ k1,k2∈Z | 0< k1,k2<26，gcd(k1,26)=1}； – Ek(m)=(k1m+k2) mod q； – Dk(c)= k1#( c - k2) mod q，其中k1#为k1在模q下的乘 法逆元。
• 密钥范围
– 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 (mod 26)。
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
乘数密码
• 乘数密码
– 将明文字母串逐位乘以密钥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下的乘法逆元。
第1章 信息安全概述
① 信息、信息系统和信息安全概念
② 信息安全的三个发展阶段
③ 信息安全的五个特性
④ 信息安全威胁五个基本类型
⑤ 网络安全与政治、军事、经济和社会稳定 ⑥ 互联网安全性分析 ⑦ 信息安全的体系结构
第2章 密码学基础
2.1 2.2 2.3 2.4 2.5 2.6 密码学基础知识 古典替换密码 对称密钥密码 公开密钥密码 消息认证 密码学新进展
密钥ke 破译者 明文 加密 密文 信道 发送方 加密通信模型 接收方 密文 解密 明文 密钥kd
2.1.2 密码体制
– 完整密码体制要包括如下五个要素：
• • • • • M是可能明文的有限集，称为明文空间； C是可能密文的有限集，称为密文空间； K是一切可能密钥构成的有限集，称为密钥空间； E为加密算法，对于任一密钥， 都能够有效地计算； D为解密算法，对于任一密钥，都能够有效地计算。
F
4 S0 2