加密技术(1)-对称密码体系(自学)

1、2006 1 附1 数据加密技术 2006 2 u基础数论在密码学中的作用基础数论在密码学中的作用 基础数论作为一门古老的数学学科，在整 个数学学科中占有非常重要的位置。数论中许 多基本内容，如同余理论、中国剩余定理 （CRT）、高次剩余理论等，在新型密码体制、 密钥分配与管理、数字签名、身份认证等方面 有直接的应用。 u现代密码与近代数学形影不离现代密码与近代数学形影不离 近代数学在现代密码研究中比比皆是 ：群 论，有限域上椭圆曲线理论，多项式理论与迹 函数理论，陷门单向函数 等。 2006 3 1密码编码学密码编码学(Cryptography) 密码编码学就是研究对数据进行变换的原 理、手

2、段和方法的技术和科学。主要研究对 信息进行变换，以保护信息在信道的过程中 不被敌手窃取、解读和利用的方法 。 2密码分析学密码分析学 (Cryptanalytics) 密码分析学是为了取得秘密的信息，而对密 码系统及其流动的数据进行分析，是对密码原 理、手段和方法进行分析、攻击的技术和科学。 主要研究如何分析和破译密码。 2006 4 1明文明文 需要加密的信息称为明文 2密文密文 明文经过加密或伪装，形成密文 3加密和解密加密和解密 对明文而实施一系列的变换过程而形成密文，称为加 密或加密变换。反之对密文施加一系列的逆变换而还原 成明文，称为解密或解密更换 4 密码方案密码方案 密码方案确切

3、地描述了加密变换与解密变换的具体 规则 5 密钥空间密钥空间 密钥的全体称为密钥空间 2006 5 从数学的角度来讲，一个密码系统是从数学的角度来讲，一个密码系统是一族一族 映射映射，它在，它在密钥密钥的控制下将明文空间中的每一的控制下将明文空间中的每一 个元素映射到密文空间上的某个元素。这个元素映射到密文空间上的某个元素。这族族映映 射由密码方案确定，具体使用哪射由密码方案确定，具体使用哪一个一个映射由映射由密密 钥钥决定。决定。 可以将密码方案与密钥共同看作控制密码可以将密码方案与密钥共同看作控制密码 变换的变换的“密钥密钥”，只不过密码方案是，只不过密码方案是固定固定的的 “密钥密钥”，

4、而密钥是，而密钥是变换变换的的“密钥密钥”。将。将“密密 钥钥”中固定的部分（密码方案）与变化的部分中固定的部分（密码方案）与变化的部分 （密钥）区分开来对于密码分析以及密钥管理（密钥）区分开来对于密码分析以及密钥管理 等具有重大的意义等具有重大的意义 2006 6 信源编码器信道解码器接收者 秘密信道 密 码 分 析 者 密钥源密钥源 2006 7 1密码分析和密码攻击密码分析和密码攻击 如果非授权者借助窃听到的密文以及其他一些信息通过 各种方法推断原来的明文甚至密钥，这一过程称为密码分析 或密码攻击。 2 2多种攻击行为多种攻击行为 密码系统所假想的环境中除了接收者外，还有非授权者， 它们

5、通过各种方法来窃听、干扰信息 3 3无条件的安全性无条件的安全性 对于一个密码系统来说.若攻击者无论得到多少密文也 求不出确定明文的足够信息,这种密码系统就是理论上不可破 译的,即密码系统具有无条件安全性(或完善保密性) 2006 8 4. 4. 实际安全性实际安全性 若一个密码系统原则上虽可破译，但为了由密文得到明 文或密钥却需付出十分巨大的计算，而不能在希望的时间内 或实际可能的经济条件下求出准确的答案，这种密码系统就 是实际不可破译的，或称称该密码系统具有计算安全性 5.5.影响安全性的几个因素影响安全性的几个因素 v算法强度算法强度 算法的强度越高，攻击者越难破译 v其它因素其它因素

6、其他的各种非技术手段（如管理的漏洞，或是某个环 节无意暴露了敏感信息等）来攻破一个密码系统 2006 9 u惟密文攻击惟密文攻击 分析者知道一个或一些密文密文的情况下，企图得到明明 文文或密钥密钥等敏感信息 u已知明文攻击已知明文攻击 分析者知道一些明文及对应的密文的对应关系对应关系 u选择明文攻击选择明文攻击 分析者获得更大机会接近密码系统，可以选择选择一些 对攻击有利的特定明文特定明文，并得到对应的密文，以及在此 基础上进行密码的破译 u选择密文攻击选择密文攻击 与选择明文攻击相反，分析者可以选择选择性地知道一 些攻击有利的特定密文特定密文，并得到对应的明文 2006 10 u 密码系统的

7、密钥空间必须足够地大 u 加密与解密过程必须是计算上可行的，必 须能够被方便地实现与使用 u 整个密码系统的安全性系于密钥上，即使 密码方案被公布公布，在密钥不泄露不泄露的情况下， 密码系统的安全性也可以得到保证。 2006 11 u三种考虑角度 v（1）从明文到密文的变换 替换(substitution) 置换(transposition) v（2）钥匙的数目 对称、单钥加密法 双钥、公钥加密 v（3）明文的处理方式 分组加密（块加密算法） 流方式加密 2006 12 uUnconditionally secure，绝对安全？ v永不可破，是理想情况，理论上不可破，密钥 空间无限，在已知密文

8、条件下，方程无解。但 是我们可以考虑： 破解的代价超过了加密信息本身的价值 破解的时间超过了加密信息本身的有效期 uComputationally secure， v满足上述两个条件 2006 13 u假设密码(password)k是固定的 u明文和密文是一个映射关系：单射，即 Ek(x1) != Ek(x2) if x1 != x2 u通常情况是：明文非常有序 u好的密码条件下，我们期望得到什么样的 密文 v随机性 2006 14 u打破明文本身的规律性 v随机性(可望不可及) v非线性(一定要) v统计意义上的规律 u多次迭代 v迭代是否会增加变换的复杂性 v是否存在通用的框架，用于迭代

9、u复杂性带来密码分析的困难和不可知性 v实践的检验和考验 2006 15 u经典密码算法 v替换技术(Substitution) v置换技术(Transposition) u现代密码算法 vDES v其他密码算法 2006 16 u要求的计算强度小 u以字母表为主要加密对象 u替换和置换技术 u数据安全基于算法的保密 u密码分析方法基于明文的可读性以及字母 和字母组合的频率特性 2006 17 u太平洋战争中，美军破译了日本海军使用 的JN25密码，一举扭转了太平洋战争中 的劣势。 u1949年，香农Information Theory of Secrecy System的发表标志着密码从“黑

10、色艺术”进 入科学研究领域，论文证明了一次一密是 安全的，并给出两个密码设计原则：混淆 与扩散。 2006 18 uDES(Data Encryption Standard) uIDEA uRC5 uAES uBlowfish uCAST-128 u 2006 19 u加密: E: (X,K) Y, y = E(x,k) XY K E YX K D u解密: D: (Y,K) X, x = D(y,k) 2006 20 u序列(流)密码与分组密码 v序列密码(stream cipher)也叫流密码，是对单个 明文位(Bit-by-bit)变换的操作 v分组密码(block cipher)是对一

11、个大的明文块 (Block-by-block)进行固定变换的操作 2006 21 2006 22 2006 23 uConfusion(混淆) v为了防止分析者利用明文与密文之间的依赖关 系进行破译，密码的设计应该增加明文与密文 之间关系的复杂性 uDiffusion(发散) v小扰动的影响波及到全局，密码的设计应保证 密钥的每位数字能够影响密文中的多位数字。 v密文没有统计特征，明文一位影响密文的多位， 增加密文与明文之间关系的复杂性 2006 24 u电子簿模式(electronic codebook mode)ECB u密码块链接(cipher block chaining)CBC u密

12、码反馈方式(cipher feedback)CFB u输出反馈方式(output feedback)OFB 2006 25 u相同明文相同密文 u同样信息多次出现造成 泄漏 u信息块可被替换 u信息块可被重排 u密文块损坏仅对应明 文块损坏 u适合于传输短信息 2006 26 但是，通过采用流密码流密码的设计思想，在加密过程 中采用合理的记忆组件记忆组件，能够消除这些局限性。如果 在构造分组密码系统的时候直接采用分组密码算法， 则称这种工作模式为电码本（ECB）模式。分组密码 的上述缺陷导致了这种工作模式也具有相应的缺陷。 因此，实际采用的分组密码工作模式是对电码本 （ECB）模式的改进。 u

13、分组密码主要有两个优点分组密码主要有两个优点 v 易于标准化 v 易于实现同步 u局限性局限性 v 分组密码不便于隐藏明文的数据模式 v 对于重放、插入、删除等攻击方式的抵御能力 2006 27 u需要共同的初始化 向量IV u相同明文不同密 文 u初始化向量IV可以 用来改变第一块 u安全性好于ECB 2006 28 uCFB:分组密码流密码 u需要共同的移位寄存器共同的移位寄存器初始值IV u对于不同的消息，IV必须唯一 u一个单元损坏影响多个单元: (W+j-1)/j W为分组加密块大小，j为流单元位数 2006 29 uOFB:分组密码流密码 u需要共同的移位寄存器共同的移位寄存器初始

14、值IV u一个单元损坏只影响对应单元 2006 30 信源编码器信道解码器接收者 秘密信道 密码分析者 密钥源密钥源 2006 31 u基本思想：用简单算法的乘积来近似表达 大尺寸的替换变换 u多个简单算法的结合得到的加密算法比任 何一个部分算法都要强 u交替使用替换置换和排列(permutation) u混淆(confusion)和发散(diffusion)概念的应 用 2006 32 2006 33 u加密: Li = Ri-1; Ri = Li-1F(Ri-1,Ki) u解密: Ri-1 = Li Li-1 = RiF(Ri-1,Ki) = RiF(Li,Ki) 2006 34 u分组大

15、小：越大安全性越高，但速度下降，64比较合 理 u密钥位数：越大安全性越高，但速度下降，64广泛使 用，但现在已经不够用128 u步数：典型16步 u子钥产生算法：算法越复杂，就增加密码分析的难度 u每一步的子函数：函数越复杂，就增加密码分析的难 度 u快速软件实现：包括加密和解密算法 u易于分析：便于掌握算法的保密强度以及扩展办法。 2006 35 u1977年由美国的标准化局(NBS，现为NIST) 采纳 u64位分组、56位密钥 u历史： vIBM在60年代启动了LUCIFER项目，当时的算 法采用128位密钥 v改进算法，降低为56位密钥，IBM提交给 NBS(NIST)，于是产生DE

16、S u16轮的Feistel结构密码 2006 36 uDES是对称密钥加密的算法， DES 算法大致可以分成四个部分： v初始置换 v迭代过程 v逆初始置换 v子密钥生成 2006 37 明文（位） 初始置换（IP） LPTRPT 16轮 16轮 逆初始置换（FP） 密文（位） 2006 38 输入（64位） 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

17、45 37 29 21 13 5 63 55 47 39 31 23 15 7 输出（64位） 初始变换 IP L0（32位）R0（32位） 2006 39 Li Li-1Ri-1 Ri Li-1 f(Ri-1 , Ki) 2006 40 左半部分 32 位 右半部分32位 新的左半部分 新的右半部分 密钥移位 置换后的密钥 f + 2006 41 密钥变换 扩展置换 S盒替换 P盒替换 异或与交换 2006 42 A(32位) 扩展置换E 48位结果48位Ki + 选择函数组选择函数组 (S1S8) 32位结果 置换运算P 加密时A=Ri-1 压缩置换E K(56位) 2006 43 200

18、6 44 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 33 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 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

19、 i1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 LS 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2006 45 A 32位 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1 选择运算E 选择运算E的结果 48位 2006 46 u在密码函数中有在密码函数中有8个个S盒，称为盒，称为8个不同的个不同的 选择函数。每个选择函数。每个S盒

20、都是将盒都是将6位作为输入，位作为输入， 得到一个得到一个4位块作为输出位块作为输出 u S 盒是盒是DES 的最敏感部分，其原理至今未的最敏感部分，其原理至今未 公开。人们担心公开。人们担心S 盒隐藏陷门，使得只有他盒隐藏陷门，使得只有他 们才可以破译算法，但研究中并没有找到们才可以破译算法，但研究中并没有找到 弱点。弱点。 2006 47 S(1): 14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 07 00 15 07 04 14 02 13 01 10 06 12 11 09 05 03 08 04 01 14 08 13 06 02 11 1

21、5 12 09 07 03 10 05 00 15 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13 2006 48 8个选择函数的输出（32位）位） 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 置换P 加密函数的结果X（32位）位） 2006 49 uBiham和和Shamir的研究发现，只要将的研究发现，只要将DES 算法的第算法的第3 个盒与第个盒与第7个盒对调，就会使个盒对调，就会使 DES算法在某类攻击算法在某类攻击

22、 下，其安全性下降一下，其安全性下降一 个级数。个级数。 Biham,E. and Shamir,A., ”Differential Cryptanalysis of DES-like Cryptosystems”, Journal of Cryptology,Vol. 4 #1 , 1991 ,pp.3-27 2006 u数据的初始置换和末置换对算法的安全 性无意义。 v假设没有初始置换和末置换的算法称为EDS 算法。如果能够破解该算法，即给定算法的 一对明密文对，能够很容易找到密钥E,则E 也是对应DES算法的密钥。 假定DES明文对（m,c),对m做初始置换的逆运算得m, 对c做末置换的

23、逆运算得c,将（m,c)用EDS算法的 破解软件进行破解，故E也是DES算法的密钥。 v如果用k1加密后再用k2加密，k1的末置换与 k2的初始置换相抵消，现在通常用交互使用 加密与解密运算的方法。 50 2006 51 u穷举攻击 v56位密钥的使用，理论上，97年$100000的机器可以在 6小时内用穷举法攻破DES v实际攻破的例子，97年1月提出挑战，有人利用Internet 的分布式计算能力，组织志愿军连接了70000多个系统 在96天后攻破 uDES算法的本质 v关键在于8个S-BOX u针对DES的密码分析 v穷举攻击。 用于任何分组密码，攻击复杂度只依赖于分组长度和密钥长度 v

24、差分分析法 v线性分析法 2006 52 u Biham和Shamir于1991年提出 u 属于选择明文攻击选择明文攻击 u 基本思想：通过分析特定明文差对结果密文差明文差对结果密文差的影响来获得可能性最 大的密钥 u 适用于攻击迭代分组密码。对较低轮次的DES攻击较成功，如8轮的 DES在PC机上几分钟就可以用差分攻击破译。 u 针对每一个DES步骤，用差分法可以推导出该步的密钥。通过分析 DES的8个S盒，对于明文对的某一差别，在其导致的所有各种可能的 密文对的差别中，总有一种具有较高的概率，达到这种较高概率的明 文对称为正确对，正确对暗示了最后一轮加密函数正确的子密钥，当 偿试了足够多的

25、正确对以后，由能够发现具有最大概率的正确的子密 钥。对于DES算法，当得出K16以后，则确定了56位密钥中的48位， 其余8位可以通过穷尽分析得到。 u 247对选择明文，经过247量级的计算可攻破 u 只有当尝试的明文对的数目超过某一阀值后，才能够从大量的候选值 中发现正确的子密钥。此外此方法需要一个计数器为248个可能的子密 钥分配不同的概率，数据量过大，使其实际上不可行。 2006 53 u线性分析法 vMatsui和Yamagishi于1992年 v思想：用线性近似线性近似描述DES变换。寻找一个给 定密码算法的有关明文比特、密文比特和密钥 比特的有效的线形近似表达式，通过选择充分 多

26、的明密文对来析取密钥的某些比特。 v根据247已知明文，可以找到DES的密钥 2006 54 uS盒设计 u弱密钥或半弱密钥 v弱密钥：密钥K使每个左右两部的密钥所有位 都是0或1。 v半弱密钥：这些密钥将明文加密成相同的密文 uDES结构的互补对称性 v由于互补对称性，攻击者可在选择明文攻击时仅需要 试验其可能性密钥256的一半，互补对称性告诫不要使 用互补密钥 ()() k k DESMDESM 2006 55 u双重DES u三重DES v三个密钥 v两个密钥 2006 56 2006 57 2006 58 C=Ek2Ek1P = T=Ek1P=Dk2C 对于一对已知的（P、C） u 对

27、于所有的k1 ，计算Ek1P ，将256个结果排序 u 对于所有的k2 ，计算Dk2C ，将256个结果排序 u 进行匹配搜索，每找到一对，再用其他（P、C） 对进行检验，直到找到正确的k1和k2 密钥的空间为2112,但是只需要257个DES操作 2006 59 u三个密钥 2006 60 u两个密钥 2006 61 uIDEA算法 uRC5 u高级加密标准（AES） 2006 62 uIDEA算法可用于加密和解密。主要有三 种运算：异或、模加、模乘，容易用软 件和硬件来实现。 uIDEA的速度：现在IDEA的软件实现同 DES的速度一样块。 uIDEA的密码安全分析：IDEA的密钥长 度是

28、128位，是DES的密钥长度的两倍。 在穷举攻击的情况下，IDEA将需要经过 2128次加密才能恢复出密钥。 2006 63 u是由瑞士苏黎士联邦工业大学的Xuejia Lai和James L. Massey于1991年提出的。 u属于对称密码体系 u基本运算 v异或 v模216加法； v修改过以适应216范围的乘法X：计算32位结 果，用216+1取余。 2006 64 u IDEA工作原理 64位输入 第一轮 64位输出 第二轮 第17轮 密钥扩展 128位密钥 K1K2K3K4 K5K6 K49K50K51K52 2006 65 Xa Xa Ka Xd Xd Kd Xc Xc Kc Xb Xb Kb 2006 66 Xa Xa Xd Xd Xc Xc KeKf Xb Xb Mangler 函数 Yout=(Ke X Yin)+Zin) X Kf Zout=(Ke X Yin) + Yout Yin Yout Zin Zout 2006 67 v IDEA将128位密钥扩展成52个16位的循环密钥，加解密的密钥 扩展方式是不同的。 v 加密循环密钥的产生方式为： （1）将主密钥分成8个16比特块，便得到K1-K8； （2）将主密钥循环左移24位，再按（1），便得到K9-K16；