信息安全导论（模块4－密码基础） 密码基础－对称密码

现代密码学 密码体制的分类： 对称、非对称 分组、序列

分组密码的设计原则 混乱：所设计的密码应使得密钥、明文以及密文之间的依赖关系相当复杂，以至于这种依赖性对密码分析者来说是无法利用的 扩散：所设计的密码应使得密钥的每一位数字影响密文的许多位数字，以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数字，以便隐蔽明文数字统计特性

典型的分组密码算法—DES DES的历史 1971年，IBM，由Horst Feistel领导的密码研究项目组研究出LUCIFER算法，并应用于商业领域 1973年美国标准局征求标准，IBM提交结果，之后被选为数据加密标准

分组密码的例子——DES DES是1975年被美国联邦政府确定为非敏感信息的加密标准，它利用64比特长度的密钥K来加密长度为64比特的明文，得到64比特长的密文 1997年，由于计算机技术迅速发展，DES的密钥长度已经太短，NIST建议停止使用DES算法作为标准. 目前，二重DES和三重DES仍然广泛使用 5

DES算法的整体结构——Feistel结构

DES算法的整体结构——Feistel结构 输 入 密 钥 编 排 I P K1……K16 16轮迭代 I P-1 输出 7 7

DES算法的整体结构——Feistel结构 1. 给定明文，通过一个固定的初始置换IP来重排输入明文块P中的比特，得到比特串P0=IP(P)=L0R0，这里L0和R0分别是P0的前32比特和后32比特 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 初始置换IP 8

DES算法的整体结构——Feistel结构 2. 按下述规则进行16次迭代，即 1≤i≤16 这里 是对应比特的模2加，f是一个函数（称为轮函数）； 16个长度为48比特的子密钥Ki(1≤i≤16)是由密钥k经密钥编排函数计算出来的. Li-1 Ri-1 ki + f Li Ri 第16轮迭代左右两块不交换

DES算法的整体结构——Feistel结构 3.对比特串R16L16使用逆置换IP-1得到密文C，即C=IP-1 (R16L16)。 IP-1 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 10

分组密码的轮函数 函数f以长度为32比特串Ri-1作为第一输入，以长度为48比特串Ki作为第二个输入，产生长度为32比特的输出： 11

分组密码的轮函数 E (Ri-1) B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8 C1 Ki E (Ri-1) B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8 C1 C2 C3 C4 C5 C6 C7 C8 f (Ri-1 ,Ki) + P E E扩展 S盒代换 P置换 32 4 6 48 密钥加

分组密码的轮函数 E扩展：Ri-1根据扩展规则扩展为48比特长度的串； E：比特——选择表 32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

E扩展（32bit扩展到48bit） 32 1 2 3 4 5 6 7 8 9 32 1 32 1 2 3 4 5 4 5 6 7 8 9 8 9

分组密码的轮函数 密钥加：计算 ，并将结果写成8个比特串，每个6比特，B=B1B2B3B4B5B6B7B8.

分组密码的轮函数 S盒代换：6入4出，查表 8个S盒S1……S8. 每个S盒是一个固定的4*16阶矩阵，其元素取0~15之间的整数. 输入6比特b1b2b3b4b5b6，输出如下 1) b1b6两个比特确定了S盒的行 2) b2b3b4b5四个比特确定了S盒的列 3) 行、列确定的值即为输出 16

S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 7 S2 S3 S4 S5 S6 S7 S8 17

例如：输入101100，行”10“＝2，列”0110“＝6 输出2，即0010 例如：输入111001，行”11“＝3，列”1100“＝12 S1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 7 例如：输入101100，行”10“＝2，列”0110“＝6 输出2，即0010 例如：输入111001，行”11“＝3，列”1100“＝12 输出10，即1010 18

分组密码的轮函数 P置换：长度为32比特串C=C1C2C3C4C5C6C7C8, 根据固定置换P(*)进行置换，得到比特串P(C). P置换 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 19

DES算法的密钥编排算法 根据密钥K来获得每轮中所使用的子密钥Ki 64 28 28 56 48 …… …… K PC-1 C0 D0 LS1 LS1 56 48 C1 D1 PC-2 K1 LS2 LS2 …… …… LS16 LS16 C16 D16 PC-2 K16 20

DES算法的密钥编排算法 1. 给定64比特密钥K，根据固定的置换PC-1来处理K得到C0D0，其中C0和D0分别由最前和最后28比特组成 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 1. 给定64比特密钥K，根据固定的置换PC-1来处理K得到C0D0，其中C0和D0分别由最前和最后28比特组成

DES算法的密钥编排算法 2. 计算Ci=LSi(Ci-1)和Di=LSi(Di-1)， 且Ki=PC-2(CiDi)，LSi表示循环左移两个或一个位置，具体地，如果i=1,2,9,16就移一个位置，否则就移两个位置 PC-2是另一个固定的置换.

DES算法的密钥编排算法 PC-2 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

DES的解密变换 DES的解密与加密一样使用相同的算法，它以密文y作为输入，但以相反的顺序使用密钥编排K16,K15,…,K1, 输出的是明文x

DES加密的例子 设16进制明文X为：0123456789ABCDEF 密钥K为：133457799BBCDFF1 加密后的密文为：

DES的核心是S盒，除此之外的计算是线性的 S盒作为该密码体制的非线性组件对安全性至关重要。 S盒的设计准则：

分组密码的分析方法 如果密码分析者能够确定正在使用的密钥，则他就可以像合法用户一样阅读所有消息，则称该密码是完全可破译的 如果密码分析者仅能从所窃获的密文恢复明文，却不能发现密钥，则称该密码是部分可破译的

DES的破解 DES的实际密钥长度为56-bit，就目前计算机的计算能力而言，DES不能抵抗对密钥的穷举搜索攻击。 1997年1月28日，RSA数据安全公司在RSA安全年会上悬赏10000美金破解DES，克罗拉多州的程序员Verser在Inrernet上数万名志愿者的协作下用96天的时间找到了密钥长度为40-bit和48-bit的DES密钥。 1998年7月电子边境基金会（EFF）使用一台价值25万美元的计算机在56小时之内破译了56-bit的DES。 1999年1月电子边境基金会（EFF）通过互联网上的10万台计算机合作，仅用22小时15分就破解了56-bit的ＤES。 不过这些破译的前提是，破译者能识别出破译的结果确实是明文，也即破译的结果必须容易辩认。如果明文加密之前经过压缩等处理，辩认工作就比较困难。

DES算法的公开性与脆弱性 DES的两个主要弱点： DES的半公开性：S盒的设计原理至今未公布 密钥容量：56位不太可能提供足够的安全性 S盒：可能隐含有陷井（Hidden trapdoors） DES的半公开性：S盒的设计原理至今未公布

DES小结 充分混乱：密钥、明文以及密文之间的依赖关系相当复杂 充分扩散：密钥的每一位数字影响密文的许多位数字，明文的每一位数字也应影响密文的许多位数字

密码分析的几种情况 根据攻击者掌握的信息，密码分析分为 仅知密文攻击：攻击者除了所截获的密文外，没有其他可以利用的信息 已知明文攻击：攻击者仅知道当前密钥下的一些明密文对 选择明文攻击：攻击者能获得当前密钥下的一些特定的明文所对应的密文 选择密文攻击：攻击者能获得当前密钥下的一些特定的密文所对应的明文

分组密码 序列密码（流密码）

流密码（序列密码） 分组密码 流密码 将待加密的明文分为若干个字符一组，逐组进行加密 将待加密的明文分成连续的字符或比特，然后用相应的密钥流对其进行加密 密钥流由种子密钥通过密钥流生成器产生

流密码基本原理 通过随机数发生器产生性能优良的伪随机序列（密钥流），使用该序列加密信息流（逐比特加密），得到密文序列 种子密钥K 密钥流Ki 加密变换 密文流Ci 明文流mi

按照加解密的工作方式，流密码分为同步流密码和自同步流密码

同步流密码 自同步流密码 密钥流的产生完全独立于消息流（明文流或者密文流） 特点：无错误扩散。如果传输过程产生一位错误，只影响当前位的解密结果，不影响后续位 自同步流密码

同步流密码 ki ci ：密钥流生成器的内部状态 F：状态转移函数 G：密钥流产生函数 安全信道 种子密钥K 公开信道 种子密钥k 解密变换 公开信道 加密变换 种子密钥K ：密钥流生成器的内部状态 F：状态转移函数 G：密钥流产生函数

同步流密码 自同步流密码 每一个密钥字符是由前面n个密文字符参与运算得到的

自同步流密码 ki ci ：密钥流生成器的内部状态 F：状态转移函数 G：密钥流产生函数 安全信道 公开信道 种子密钥k 加密变换 解密变换 公开信道 加密变换 ：密钥流生成器的内部状态 F：状态转移函数 G：密钥流产生函数

二元加法流密码 目前使用最多的流密码 明文m、密文c、密钥k都为0，1序列，运算为模2加（异或） 加密： 解密：

二元加法流密码 解密操作： 密钥流：k1,k2,k3,… ⊕⊕⊕ 密文流：c1,c2,c3,… ↓↓↓ 明文流：m1,m2,m3,… 符号描述与示例 加密操作： 密钥流：k1,k2,k3,… ⊕⊕⊕ 明文流：m1,m2,m3,… ↓↓↓ 密文流：c1,c2,c3,… 解密操作： 密钥流：k1,k2,k3,… ⊕⊕⊕ 密文流：c1,c2,c3,… ↓↓↓ 明文流：m1,m2,m3,… [例]电报内容“专列下午2点到达。”的加密过程如下： 密钥流：78,35,02,E4,B2… ⊕ ⊕ ⊕ ⊕ ⊕ 明文流：D7,A8,C1,D0,CF,C2,CE,E7,32,B5,E3,B5,BD,B4,EF,A1,A3 ↓ ↓ ↓ ↓ ↓ 密文流：AF,9D,C3,34,7D…

二元加法流密码算法的安全强度完全取决于密钥流的特性 如果密钥流是无限长、无周期的完全随机的序列，则这种密码就是“一次一密”的密码体制。仙农曾证明它是不可破译的 但实际应用中，密钥流都是由有限存储和有限复杂的逻辑电路产生的字符序列，因此是有周期性的，不是真正的随机序列 要设计周期尽可能长、随机性尽可能好的，近似真正的随机序列，做密钥流

Golomb随机性假设 在序列的一个周期内，0与1的个数相差至多为1 在序列的一个周期圈内，长为1的游程数占总游程数的1/2，长为2的游程数占总游程数的 ，……，长为i的游程数占总游程数的 且在等长的游程中，0，1游程各占一半 序列的异相自相关函数为一个常数

第一个条件说明，01序列中0和1出现的概率“基本”相同 第二个条件说明：在已知位置n前若干位置上的值的条件下，0与1在第n位置上出现的概率是相同的 第三个条件说明：若将原序列(ai)与序列的移位(ai+j)比较，无法得到关于ai的实质性信息（如：周期）

把满足Golomb随机性假设的序列称为伪随机序列 流密码最核心的问题是密钥流生成器的设计 密钥流生成器一般由线性反馈移位寄存器(Linear Feedback Shift Register, LFSR)和一个非线性组合函数构成 驱动部分 （LFSR） 非线性 组合部分 密钥流 ki

移位寄存器：可用来存储数据，脉冲到来时，移位寄存器所有位右移一位；最右边移出位为输出，最左边输入位由反馈函数的输出填充 反馈移位寄存器：由寄存器和反馈函数组成 移位寄存器：可用来存储数据，脉冲到来时，移位寄存器所有位右移一位；最右边移出位为输出，最左边输入位由反馈函数的输出填充 反馈函数是n元（a1,a2,…,an)的布尔函数 an-1 … a3 a2 a1 an 反馈函数 f(a1, …,an) 输出位oi

二元加法流密码（续） 工作原理 移位寄存器中所有位右移一位，最右边移出的位是输出位，最左端的一位由反馈函数的输出填充。反馈函数f(a1, …,an)是n元(a1 ,…,an)的布尔函数。移位寄存器根据需要不断地进动m拍，便有m位的输出，形成输出序列o1 o2 … om 。

二元加法流密码（续） 例：图示为一个3-级反馈移位寄存器，反馈函数f(x)=b3⊕b2，初态为：100。输出序列生成过程： 状态 输出位 状态 输出位 100 →0 110 →0 011 →1 101 →1 因此，对应初态(100)的输出序列为： 0011011011 …（周期为3） b3 b2 b1 t3 t2 (a) 移位寄存器结构图 1 初态 (100) (011) 1 (110) (101) (b) 状态转移图 (c) 序列圈

二元加法流密码（续） 当反馈移位寄存器的反馈函数是异或变换时，这样的反馈移位寄存器叫线性反馈移位寄存器，如图所示：

二元加法流密码（续） 移位寄存器中存储器的个数称为移位寄存器的级数，移位寄存器存储的数据为寄存器的状态，状态的顺序从左到右依次为从最高位到最低位。 在所有状态中， 叫初态，并且从左到右依次称为第一级、第二级、…、第n级，亦称为抽头1、抽头2、抽头3、….、抽头n。n级线性反馈移位寄存器的有效状态为 个。它主要是用来产生周期大，统计性能好的序列。

二元加法流密码（续） 非线性组合部分主要是增加密钥流的复杂程度，使密钥流能够抵抗各种攻击（对流密码的攻击手段主要是对密钥流进行攻击）。 以线性反馈移位寄存器产生的序列为基序列，经过不规则采样、函数变换等（即非线性变换），就可以得到实用安全的密钥流。

几种常见的流密码算法 流密码算法没有公开的国际标准，大多数设计、分析成果都是保密的 1.A5算法 2.Rambutan算法 3.RC4算法 法国，欧洲数字蜂窝移动电话系统（GSM）中使用的序列密码加密算法 用于从手机到基站的连接加密。A5/1，A5/2 2.Rambutan算法 英国的算法，由通信电子安全组织设计 3.RC4算法 由Ron Rivest于1987年为RSA数据安全公司设计的可变密钥长度的序列密码，广泛用于商业密码产品中。 4.SEAL算法 IBM公司的Phil Rogaway和Don Coppersmith设计的一种易于用软件实现的序列密码。

对称密码体制使用中存在的问题 密钥分配问题：通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现 密钥管理问题：在有多个用户的网络中，任何两个用户之间都需要有共享的秘密钥，当网络中的用户n很大时，需要管理的密钥数目非常大n(n-1)/2

小结 对称密码体制 分组密码的代表：DES 序列密码

作业 给定DES算法源代码 对照DES的原理，对源代码进行理解并注释 对明文“0123456789ABCDEF”用密钥“123456789ABCDEF0”进行加解密，验证算法的正确性 密钥不变，对明文修改最后一比特，得到密文，对比密文的差异 明文不变，对密钥修改第一个比特，得到密文，对比密文的差异 明文不变，对密钥修改最后一个比特，得到密文，对比密文的差异 输入任意明文、密钥，得到密文