密码学的基本概念

• 密码编码：通过信息编码使信息保密

• 密码分析：用分析方法（破解）解密信息

• 密码解码：用（正常手段，如拥有密钥）将密文转换成明文

• 基本术语

  • 明文（plain text）；密文（cipher text）
  • 加密（encrypt，encryption），解密（decrypt，decryption）
  • 密码算法（Algorithm），密码（Cipher）：用来加密和解密的数学函数
    c=E(m)，m=D( c )，D(E(m))=m
  • 密钥(Key)：算法中的一个变量[kd加密密钥，ke解密密钥]
    c=E_ke(m)，m=D_kd( c )，D_kd(E_ke(m))=m

• 密码学基本模型
  
  各国在密码分析上投入的资源最多

• 简单加密系统模型
  

• 什么是密码？就是一组含有参数K的变换E。设已知消息m，通过变换E_k得密文C，即，这个过程称为加密，E为加密算法，k不同，密文C亦不同。传统的保密通信机制：
  

• 理论安全和实际安全

  • 理论安全，或无条件安全 Theoretical Security(or Perfect Security)：
    攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。Shannon（香农）用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密，One-time Pad，不实用。
  • 实际安全，或计算上安全 Practical Secure(or Computationally Secure)：
    如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源[指人类所能掌握的资源总和]范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行（Computationally Infeasible）。
    考虑到时间资源 Shannon假定给定一个n位的密文，必有一个最小的工作时间来破解这个系统，这个工作时间为W(n).
    当n趋于无穷，则W(n)>W(∞)；当n大到一定程度，具有有限资源的攻击者在合理的时间内不能破译系统，该系统就被称为是Practical Secure 或Computationally Secure。现在的问题是，W(n)多大系统才安全？
    例：N₁=n⁵，N₂=2ⁿ，N₃=n！假定每秒可以计算100万次，即10^-6 sec/compute

  n	n5	2n	n！
  10	0.1s	0.001s	3.6s
  100	104 s = 2.8h	1030 s = 1016 年	10186 s = 10176年
  1000	109s=10年	10286 s	102974世纪

  所以，n=100，2ⁿ=10³⁰sec=10¹⁶年，W(n)>10³⁰才安全。

密码学的演变历史

• 演变史

  • 1949，Claude Shannon’s The Communication Theory of Secrecy System，成为理论基础
  • 1976-1977，美国国家标准局正式公布实施DES，Data Encryption Standard
  • 1977-1978，Rivest，Shamir，Adelman 第一次提出公开密钥密码系统的实现方法RSA
  • 1981，成立International Association for Cryptology Research
  • 1985，EIGamal 提出概率密码系统EIGamal方法
  • 1990-1992，Lai Xuejia and James:IDEA，The International Data Encryption Algorithm
  • 2000，AES，Advanced Encryption Standard

• 古罗马：Caesar密码（公元前100年）

  • 替代技术（Substitution）
    改变明文内容的表示形式，保持内容元素之间相对位置不变。单表替换如恺撒密码（Caesar Cipher）
    明文字母用密文中对应字母代替，例：
    明文字母表P={p₀, p₁, …, p_n-1}
    密文字母表C={c₀, c₁…，c_n-1}

  CAESAR密码：c=(p+3) Mod 26

  密码本	ABCDEFGHIGKLMNOPQRSTUVWXYZ
  密文	DEFGHIGKLMNOPQRSTUVWXYZABC

  明文	Caesar was a great soldier
  密文	Fdhvdu zdv d juhdw vroglhu

• 美国南北战争 1861

  • 置换技术：改变明文内容元素的相对位置，保持内容的表现形式不变。
  • 一维变换：横向输入，纵向输出

  C	A	N	Y
  O	U	U	N
  D	E	R	S
  T	A	N	D

  明文：Canyouunderstand
  密文：codtaueanurnynsd

  • 二维变换 — 图形转置

D T A N N D E R S C A N Y O U U

在此处明文按照从左到右从下往上的顺序填入，密文按照斜右下向左的层次输出
明文：can you understand
密文：dnsu aru teo dy nn a c

古典密码和现代密码

• 古典密码

  • 代替密码（Substitution Cipher）
  • 换位密码（transposition Cipher）
  • 代替密码与换位密码的组合

• 古典密码（受限密码）的缺陷

  • 密码体制的安全性在于保持算法本身的保密性
  • 受限算法的缺陷
  • 不适合大规模生产
  • 不适合较大的或者人员变动较大的组织
  • 用户无法了解算法的安全性

• 现代密码算法

  • 把算法和密钥分开
  • 密码算法可以公开，密钥保密
  • 密码系统的安全性在于保持密钥的保密性
    

• 图灵（计算机之父）

  • Alan Mathison Turing，1912-1954.英国数学家。一生对智能与机器之间的关系进行着不懈探索。
  • 1936年，24岁的图灵提出“图灵机”的设想。二战期间成功地参与破译了纳粹德国的密码Enigma，设计并制造了COLOSSUS，向现代计算机迈进了重要一步
  • 1952年，图灵遭到警方拘捕，原因是同性恋。1954年6月8日，服毒自杀，年仅42岁
  • 图灵去世12年后，美国计算机协会以他的名字命名了计算机领域的最高奖"图灵奖"

• 转子加密机（Rotor Machine）：转轮密码机ENIGMA，由Arthur Scherbius于1919年发明，4轮ENIGMA在1944年装备德国海军
  

• 英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号
  

• 一个简单的加密算法——异或 ⊕
  异或运算（不进位加法）

加密	???明文 ⊕密钥 ------------ ???密文	????0 0 1 1 ⊕ 0 1 0 1 ------------- ????0 1 1 0
解密	???密文 ⊕密钥 ------------ ???明文	????0 1 1 0 ⊕ 0 1 0 1 ------------- ????0 0 1 1

明文P，密文C，密钥K间的转换规则：
C = P ⊕ K
P = C ⊕ K
K = C ⊕ P

对称密码算法和非对称密码算法

• 对称密钥密码算法，又称传统密码算法、秘密密钥密码算法
  • 加密和解密使用相同的密钥 Ke=Kd
  • 常用算法：DES，IDEA，Blowfish，RC2等
  • 优点
    • 加密速度快，便于硬件实现和大规模生产
  • 缺点
    • 密钥分配：必须通过保密的信道
    • 密钥个数：n（n-1）/2
    • 无法用来签名和抗抵赖（没有第三方公证时）
• 非对称密码，又称公开密钥密码算法
  • 加密和解密使用不同的密钥（K_p，K_s），把加密密钥公开，解密密钥保密：c=E_Kp(m)，m=D_Ks（c）
  • 常用算法：RSA，DSA，背包算法，ElGamal，椭圆曲线等
  • 优点：
    • 密钥分配：不必保持信道的保密性
    • 密钥个数：n pair
    • 可以用来签名和抗抵赖
  • 缺点
    • 加密速度慢，不便于硬件实现和大规模生产

分组密码和序列密码

• 分组密码（Block Cipher）
  • 一次加密或解密操作作用于一个数据块，比如64位
• 序列密码（Stream Cipher）
  • 一次加密或解密操作作用于一位或者一个字节

对称密钥算法

• 加密和解密使用相同的密钥：K_E=K_D
• 密钥必须使用秘密的信道分配
  
• 常用对称密钥密码算法
  • DES（Data Encryption Standard）及其各种变形
  • IDEA（International Data Encryption Algorithm）
  • RC2，RC4，RC5，
  • AES（Advanced Encryption Standard）
  • CAST-128-Blowfish

DES算法原理

• IBM公司，70年代初提出，80年代成为国家标准
• DES是一种对称密钥算法，密钥长度为56bits（加上奇偶校验，通常写成64bits）
• 是一种分组加密算法，64bits为一个分组
• 基本思想：
  – 混乱（Confusion）和扩散（Diffusion）
• 使用标准的算术和逻辑运算

DES加密过程

首先把明文分成以64bit为单位的块m，对于每个m，执行如下操作
DES（m）=IP^-1·T₁₆·T₁₅…T₂·T₁·IP（m）

• 初始置换，IP
• 16轮迭代（每轮迭代思路相同），T_i，i=1，2…16
• 末置换，IP^-1

重点在于初始置换、其中一轮迭代和末置换

初始换位 IP

置换表：

58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7

初始序列：
M=m₁,m₂,m₃…,m₆₂,m₆₃,m₆₄
置换后序列：
M’=IP(M) = m₅₈,m₅₀,m₄₂,…,m₂₃,m₁₅,m₇

一轮迭代

子密钥K_i长度48bit，总密钥长度64bit

1. E-盒(extend)置换：对明文的任何变化都会扩散到密文的每一处

• 将Ri从32位扩展到48位

• 目的：输入的一位影响下一步的两个替换，使得输出对输入的依赖性传播得更快，密文的每一位都依赖于明文的每一位
  

  原位置	1	2	3	4	5	6	7	8	9	…	31	32
  映射到	2,48	3	4	5,7	6,8	9	10	11,13	12,14	…	46	47,1

3. 置换结果 和 子密钥K_i 异或

• 子密钥的生成
  密钥K共64bits，其中第8，16，24，32，40，48，56，64用做奇偶校验位，实际上密钥长度为56位
  
  

拆分：56bits 的密钥分成两部分, C_i , D_i , 各28bits
循环左移：根据迭代的轮数，分别左移一位或两位

迭代轮数	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
左移位数	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

压缩置换PC（置换选择）：按照下表的指导，从56bits中选择48bits

14	17	11	24	1	5	3	28	15	6	21	10
23	19	12	4	26	8	16	7	27	20	13	2
41	52	31	37	47	55	30	40	51	45	33	48
44	49	39	56	34	53	46	42	50	36	29	32

4. S-盒代替
   将48比特压缩成32比特
   

• 输入6bit：b₁b₂b₃b₄b₅b₆
• 输出4bit：S(b₁b₆, b₂b₃b₄b₅)

假定S1盒为：

		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
S1	0 1 2 3	14 0 4 15	4 15 1 12	13 7 14 8	1 4 8 2	2 14 13 4	15 2 6 9	11 13 2 1	8 1 11 7	3 10 15 5	10 6 12 11	6 12 9 3	12 11 7 14	5 9 3 10	9 5 10 0	0 3 5 6	7 8 0 13

可以求得 S1(100110) = 1000
注意到：b₁b₆=10₍₂₎ = 2₍₁₀₎，b₂b₃b₄b₅=0011₍₂₎ = 3₍₁₀₎
在S1盒中查出 (2,3)中的数据为8，转为二进制为1000

4. P-盒置换

32比特输入，32比特输出
P盒的输出：

1	2	3	4	5	6	7	8	9	10	…	30	31	32
16	7	20	21	29	12	28	17	1	15	…	11	4	25

置换是为了还原

末置换

末置换表（IP）：

40	8	48	16	56	24	64	32
39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30
37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28
35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26
33	1	41	9	49	17	57	25

对比初始置换表（IP^-1）：

58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7

IP^-1(IP(M)) = M
经过初始置换后，第1位跑到了40位，末置换将第40位还原为第1位
两个置换并不能提升密码强度，却带来大量计算消耗，因此实际使用的时候并不做初始置换和末置换。

DES解密过程

• DES解密过程与加密过程完全相似，只不过将16次迭代的子密钥顺序倒过来，即
  m = DES^-1（c）=IP^-1·T₁·T₂…T₁₅·T₁₆·IP（c）
• 可以证明 DES(DES^-1(m)) = m

DES算法工作模式

电子密码本模式（ECB）

• 基本的DES算法就是ECB模式
• 相同的输入永远产生相同的输出
• 相当于加密、解密双方各有一个密码本，对于一个密钥，密码本有2⁶⁴个表项(我们可以穷举2^64中输入以及对应产生的输出，形成密码本，从而通过直接查找实现加解密，由此可以直接销毁密钥)
• 存在重放（Replay）类型的攻击，特别是对于结构化的报文
  • 攻击者可以在不知道密钥的情况下修改被加密过的消息
    

密码分组链模式（CBC）

C_i是第i组密文，P_i是第i组明文
????C_i = E(C_i-1 ⊕ P_i)
????P_i = C_i-1 ⊕ E^-1(C_i)
如上图左边，三块数据链之间的加密有依赖关系，想破解全部信息需要获取所有密钥，特别是破解后面的信息需要拿到前面所有的密钥。

DES的安全性和速度

• 弱密钥
  • 产生的子密钥相同，4个，如0000…00，11111…111，0101010101…01，101010…10
• 半弱密钥
  • 用不同的密钥加密产生相同的密文，即用一个密钥加密的信息可以用其他密钥解开，12个

DES密钥长度

• 关于DES算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有2⁵⁶≈10¹⁷个
• 早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元
• 在CRYPTO’93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。花费10万美元，平均用1.5天左右就可找到DES密钥
• 美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元
• 1998年7月电子前沿基金会（EFF）使用一台25万美元的电脑在56小时内破译了56比特密钥的DES
• 1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥

DES的变形

三重DES加密，密钥长度为112比特，k=k₁k₂

密钥长度2¹¹² = 2⁵⁶⁺⁵⁶

软硬件实现的速度

硬件实现：商业DES芯片

• VLSI公司VM0091993年制造200M Bytes/s

软件实现：

• 80486，CPU66Hz，每秒加密43000个DES分组，336K Bytes/s
• HP9000/887，CPU125Hz，每秒加密196,000个分组，1.53M Bytes/s

高级加密标准（AES）

AES的起源

• 1997年9月，NIST征集AES方案，以替代DES。
• 1999年8月，以下5个方案成为最终候选方案：MARS，RC6，Rijndael，Serpent，Twofish。
• 2000年10月，由比利时的Joan Daemen和Vincent Rijmen提出的算法最终胜出。（Rijndael 读成Rain Doll）
• http://www.esat.kuleuven.ac.be/~rijmen/rijndael/

AES的设计原则

• 能抵抗所有（算法发明之前）已知的攻击；
• 在各种平台上易于实现，速度快；
• 设计简单

Rijndael是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变

AES算法描述

Rijndael密码系统的数学背景

• Rijndael密码系统的运算都在有限域GF(2⁸)
• GF(2⁸)的定义:
  假设字节b由b₇b₆b₅b₄b₃b₂b₁b₀组成，将b_i当作一个7次多项式的系数。
  (57)₁₆=(01010111)₂表示成多项式为：x⁶+x⁴+x²+x+1
• 算法定义了自己的 “加法”、“乘法”、“乘以”

AES算法的一般描述

加密步骤

1. 字节替换SubBytes
   以字节的高四位为行索引，低四位为列索引，从S盒(16*16)中找出对应的字节进行替换

2. 行移位ShiftRows
   第一行固定不动，第二三四行根据列数决定按字节循环左移多少位。
   当列数为4时，二三四行分别按字节循环左移1,2,3位。

3. 列混合MixColumns
   将每一列作为列向量，左乘一个给定的矩阵（四阶方阵），计算结果覆盖原有的列。
   注意，这里采用的是有限域GF(2⁸)上的乘法。
   算法的原理如下：

   1. GF(2⁸)中任何数乘0x01都不变
   2. GF(2⁸)中计算乘0x02，可以分两种情况考虑：
      • 原数值小于(1000 0000)₂，即0x80的时候，乘2后第8个比特不会溢出，那么结果就是原数值左移一位；
      • 原数值大于(1000 0000)₂，即0x80的时候，乘2后第8个比特会溢出，结果需要减去一个不可约多项式(x⁸+x⁴+x²+x+1)，注意到GF(2⁸)中的减法就是加法(异或相当于不进位加法或者不退位减法)，那么结果就为原数值左移一位后(乘2)再与(0001 1011)₂即0x1b进行异或 (这里假定x⁸已经溢出了，只需要再减去 x⁴+x²+x+1 ，如果计算器位数足够多导致x⁸没溢出，仍需与 x⁸+x⁴+x²+x+1 异或)。
   3. 类似第2点，可以得到GF(2⁸)中计算乘4/乘8的结果；
   4. GF(2⁸)中计算乘其它数时，可以表示为乘1、2、4、8的线性组合。

   
   例如：计算上图左上角的04的步骤如下

   D4·02 ⊕ BF·03 ⊕ 5D·01 ⊕ 30·01
   = D4·02 ⊕ BF·02 ⊕ BF·01 ⊕ 5D·01 ⊕ 30·01
   = 1101 0100·0000 0010 ⊕ 1011 1111·0000 0010 ⊕ 1011 1111·0000 0001 ⊕ 0101 1101·0000 0001 ⊕ 0011 0000·0000 0001
   = (?0001 1010 1000? xor 1 0001 0111) ⊕ (?0001 0111 1110? xor 1 0001 0111)? ⊕ 1011 1111 ⊕ 0101 1101 ⊕ 0011 0000
   = ??1011 1111? ⊕ ?0110 1001? ⊕ 1011 1111 ⊕ 0101 1101 ⊕ 0011 0000
   = 0000 0100
   = 0x 04
   

4. 轮密钥加
   将输入状态和轮次密钥按列求异或，计算结果放回到输入状态。

密钥轮转

初始密钥可以是128位 (4×4×16)、192位 (4×6×16)或256位 (4×8×16)

1. 把初始密钥的最后一列取出，进行一次按字节循环上移(此处变成 CF 4F 3C 09)
   
2. 将得到的列用S盒做字节替换SubBytes运算（变为 8A 84 EB 01），称为变换列
3. 从种子 Rcon中取出第一列，将初始密钥的第一列，变换列和Rcon的第一列做异或运算
   这里的Rcon一共有十列，是因为加密进行了10轮，每轮都要用到一组流转密钥
   
   
4. 将计算结果填入第1步标出的W_i中。
5. 计算第2、3、4列的轮转密钥，假定当前列是W_i，则向W_i中填入 W_i-4⊕W_i-1的运算结果
   
6. 回到步骤1，继续生成下一组密钥，直到Rcon的每一列均被使用，轮转密钥全部生成为止
   

小结

快速演示AES加密过程

cs