计算机安全 分组密码

1、计算机安全与保密,张 旻,杭 州 电 子 科 技 大 学,现代对称密码,回顾上一讲的内容,乘积密码,乘积密码,1、扩大密码体制的密钥空间 2、挫败语言的统计分析,数据加密标准(DES),对称密码算法有两种类型： 分组密码(Block Cipher): 一次处理一块输入，每个输入块生成一个输出块； 流密码(Stream Cipher): 对输入元素进行连续处理，同时产生连续单个输出元素。 分组密码将明文消息划分成固定长度的分组，各分组分别在密钥的控制下变换成等长度的密文分组。,DES的历史 1973年，美国国家标准局(NBS) 开始征集联邦数据加密标准的方案。 Feistel等人研究了一种128

2、位的对称密钥系统， 后IBM改进为56位的密钥系统，并提交NBS。 1975年3月17日，NBS公布了IBM公司提供的密码算法，以标准建议的形式在全国范围内征求意见。 1977年7月15日，NBS接受这个建议，数据加密标准DES正式颁布，供商业界和非国防性政府部门使用。 争论： 1.56位够长吗？ 2.内部结构公开，设计原理没公开？,描述,DES利用56比特串长度（不包括8比特的奇偶校验位）的密钥K来加密长度为64位的明文，得到长度为64位的密文。,描述,明文(64位)输入,初始密钥(56位),初始置换IP,迭代16次,迭代16次产生16个子密钥,初始逆置换IP-1,密文(64位)输出,初始置

3、换:对明文中的各位进行换位,以打乱明文原有的排列次序. 输出m=m1m2 m64=m58m50 m7,DES加密算法,L0R0 = IP(x) 初始置换 for 1 = i = 16 Li = Ri1 Ri = Li1 XOR f(Ri1, Ki) 共作16轮 c= IP1(R16L16) 末置换函数,48,48,48,获取子密钥Ki DES加密算法的密钥长度为56位，一般表示为64位（每个第8位用于奇偶校验），将用户提供的64位初始密钥经过一系列的处理得到K1，K2，K16，分别作为116轮运算的16个子密钥,子密钥的产生:,PC-1置换: 将56位密钥重新编排,将前28位作为C,后28位作

4、为D; 循环左移: Ci=LSi(Ci-1),Di=LSi(Di-1),1 i 16 其中LS_i表示循环左移1位或两位: 当i=1,2,9,16时,左移1位;其余左移2位. 置换选择: 删除C的第9,18,22,25位以及D的第7,9,15,26比特位,并将余下的48位重新排列后作为子密钥输出.,F(R,K)函数,F(Ri, Ki)计算,迭代函数的三个子过程 扩展置换E:将32位扩展到48位,异或。扩展后的48位输出E(Ri)与压缩后的48位密钥Ki作异或运算。 S盒替代。将异或得到的48位结果分成八个6位的块，每一块通过对应的一个S盒产生一个4位的输出。 每个S盒都是416的矩阵.若输入为

5、B1B2B3B4B5B6,将B1B6作为S盒的行号, B2B3B4B5作为列号,S 盒,P置换:将变换后得到的32位结果重新排列,其即为迭代函数的输出.,DES的解密: DES的解密算法和加密算法完全相同，只是各子密钥的使用顺序相反，即为k16,k15,k14,k2,k1。 DES的安全性: 最可靠的攻击办法。强力攻击。 最有效的攻击。差分密码分析，通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。 线性密码分析。本质上是一种已知明文攻击方法，通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统。 插值攻击方法、密钥相关攻击,DES加密过程示例,取16进制明文X：012345

6、6789ABCDEF 2进制为:00000001 00100011 01000101 01100111 10001001 10101011 11001101 11101111 密钥K为：133457799BBCDFF1去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000,48,48,48,(1)初如置换 明文M经过IP，我们得到：L0=11001100 00000000 11001100 11111111R0=11110000 10101010 11110000 10101010 经过子密钥生成算

7、法，密钥K确定16轮子密钥 K1=00011011 00000010 11101111 11111100 01110000 01110010,48,48,48,(2)第1轮迭代 L1=R0=11110000 10101010 11110000 10101010,48,48,48,11110000 10101010 11110000 10101010,01111010 00010101 01010101 01111010 00010101 01010101,00011011 00000010 11101111 11111100 01110000 01110010,011000 010001 01

8、1110 111010 100001 100110 010100 100111,0101 1100 1000 0010 1011 0101 1001 0111,00100011 01001010 10101001 10111011,(2)第1轮迭代 L1=R0=11110000 10101010 11110000 10101010 R1=L0+F(R0,k1)=11101111 01001010 01100101 01000100 经过16轮迭代，最后对L16, R16 使用IP-1得到密文：85E813540F0AB405,48,48,48,双重,3重DES,在3重DES中,如果k1=k2=

9、k3,则其就是单重DES.较好的选取方式是k1=k3,其攻击复杂度从O(256)提高到O(2112).,DES的工作模式,电子密码本ECB (electronic codebookmode)； 密码分组链接CBC (cipher blockchaining)； 密码反馈CFB (cipher feedback)； 输出反馈OFB (output feedback)；,分组密码加密中的四种模式 ： 1。ECB模式,电子密码本模式:,特点 简单和有效； 可并行实现； 相同明文相同密文，同样信息多次出现造成泄漏，不能隐藏明文的模式信息； 对明文的主动攻击是可能的，信息块可重放； 误差传递：密文块损坏

10、仅对应明文块损坏； 适合于传输短信息。,2 CBC模式：,分组链接模式:,CBC特点： 不能并行实现； 相同明文不同密文，需共同初始向量IV，能隐藏明文的模式信息； 不易对明文主动攻击； 密文块损坏两明文块损坏； 安全性好于ECB； 适合长报文传输，可进行用户鉴别，是大多系统的标准，如SSL、IPSec。,3 CFB模式,密码反馈模式CFB:,CFB特点： 分组密码!流密码； 隐藏了明文模式； 需要共同的移位寄存器初始值IV； 误差传递：一个单元损坏影响多个单元。,4 OFB模式,输出反馈模式OFB,OFB特点 分组密码!流密码； 隐藏了明文模式； 需要共同的移位寄存器初始值IV； 误差传递：

11、一个单元损坏只影响对应单元； 对明文的主动攻击是可能的,信息块可被替换、重放； 安全性较CFB差。,分组密码的一般设计原理,为了有效地抵抗攻击者对密码体制的统计分析，香农提出了混乱原则和扩散原则的基本设计思想。 混乱：将明文与密钥以及密文之间的统计关系变得尽可能复杂，使破译者无法理出相互间的关系。常用非线性替代变换达到混乱效果 扩散：让明文中的每一位影响密文中的许多位。常用置换达到扩散效果。 非线性替代和置换是分组密码的两个基本组件，采用替代和置换交替使用的方式构造密码体制。,分组密码的整体结构,在1949年，香农提出了代替置换结构(SP结构）的思想。,分组密码的整体结构,Feistel可以利

12、用任何轮函数迭代构造分组密码,A5 序列密码,序列密码又称流密码，将明文划分成字符(如单个字母)或其编码的基本单元(如0、1bit)，将其与密钥流作用以加密，以同步产生的相同密钥流解密。,问题：,1.序列密码强度： 依赖于密钥流产生器所产生的序列的随机性和不可预测性; 2.核心问题： 密钥流生成器的设计； 3.关键技术： 保持收发两端密钥流的精确同步是实现可靠解密的关键；,A5算法 性质：序列密码 标准：欧洲GSM标准中规定的加密算法 用途：用于数字蜂窝移动电话从用户设备到基站之间的链路。 版本： A5/1(强加密算法)适用于欧洲地区，有出口限制； A5/2(弱加密算法)适用于欧洲以外的地区，

13、沒出口限制； A5/3算法，尚未被 GSM 標準所採用。 A5 從來沒有被公開過技術內容與細節，A5/1 與 A5/2 兩個算法的正確設計後來被 Marc Briceno、Ian Goldberg 和 David Wagner 用逆向工程給破解出來。,A5/1算法组成: 三个长度不同的LFSR（线性反馈移位寄存器） R1、R2和R3，长度分别为19、22和23。 移位寄存器在时钟的控制下左移，寄存器最低位由寄存器中的反馈多项式计算： R1：x18+x17+x16+x13 R2：x21+x20 R3：x22+x21+x20+x7,“多数为主”原则： 从每个寄存器取出一位（8,10,10）： 两个

14、或两个以上的值等于1时，为1的寄存器移位，为0的不移位； 两个或两个以上的0时，为0的移位，为1的不移位； 将三个移位寄存器最高位的异或运算结果作为输出。 A5算法的输入： 64位的会话密钥Kc A5算法的输出： 最高位（共3位）的异或运算结果作为流密码密钥用于加密运算；,64位的会话密钥Kc1 0 1 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 00 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 11 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1,1 0 1 1 0 0 1 0 1 1 0 1 1 0

15、 0 0 1 1 0,0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1,1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1,0,1,1,1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1,1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 1,0,0,K1=0,K2=1,0 1 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0,64位的会话密钥Kc1 0 1 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 00 1

16、1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 11 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1,1,0,0,1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1,1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 1,K1=0,K2=1,0 1 1 0 0 1 0 1 1 0 1 1 0 0 0 1 1 0 0,1 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0,0 1 0 1 0 0 1 0 1 1 1 0 0 1

17、 0 1 1 1 0 0 1 1 0,K3=1,A5的破解,曾有台灣立委指稱由於手機的 SIM 都交由大陸代工製造，大陸可能在監聽軍方的通訊，軍方還因此把全部將領的手機 SIM 卡都更新一遍。 還有新聞說大陸有架設 GSM 監聽設備可以破解與監聽台灣中華電信等電信公司的 GSM 通話。 以色列理工學院的教授與學生在2003年第 23 屆 Annual International Cryptology Conference 上發表了一篇名為Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication的論文，全場震撼： We