1、20061附1 数据加密技术20062u基础数论在密码学中的作用基础数论在密码学中的作用 基础数论作为一门古老的数学学科，在整个数学学科中占有非常重要的位置。数论中许多基本内容，如同余理论、中国剩余定理（CRT）、高次剩余理论等，在新型密码体制、密钥分配与管理、数字签名、身份认证等方面有直接的应用。u现代密码与近代数学形影不离现代密码与近代数学形影不离 近代数学在现代密码研究中比比皆是：群论，有限域上椭圆曲线理论，多项式理论与迹函数理论，陷门单向函数 等。200631密码编码学密码编码学(Cryptography)密码编码学就是研究对数据进行变换的原理、手段和方法的技术和科学。主要研究对信息进
2、行变换，以保护信息在信道的过程中不被敌手窃取、解读和利用的方法。2密码分析学密码分析学(Cryptanalytics)密码分析学是为了取得秘密的信息，而对密码系统及其流动的数据进行分析，是对密码原理、手段和方法进行分析、攻击的技术和科学。主要研究如何分析和破译密码。200641明文明文 需要加密的信息称为明文 2密文密文 明文经过加密或伪装，形成密文 3加密和解密加密和解密 对明文而实施一系列的变换过程而形成密文，称为加密或加密变换。反之对密文施加一系列的逆变换而还原成明文，称为解密或解密更换 4 密码方案密码方案 密码方案确切地描述了加密变换与解密变换的具体规则 5 密钥空间密钥空间 密钥的
3、全体称为密钥空间 20065 从数学的角度来讲，一个密码系统是从数学的角度来讲，一个密码系统是一族一族映射映射，它在，它在密钥密钥的控制下将明文空间中的每一的控制下将明文空间中的每一个元素映射到密文空间上的某个元素。这个元素映射到密文空间上的某个元素。这族族映映射由密码方案确定，具体使用哪射由密码方案确定，具体使用哪一个一个映射由映射由密密钥钥决定。决定。可以将密码方案与密钥共同看作控制密码可以将密码方案与密钥共同看作控制密码变换的变换的“密钥密钥”，只不过密码方案是，只不过密码方案是固定固定的的“密钥密钥”，而密钥是，而密钥是变换变换的的“密钥密钥”。将。将“密密钥钥”中固定的部分（密码方案
4、）与变化的部分中固定的部分（密码方案）与变化的部分（密钥）区分开来对于密码分析以及密钥管理（密钥）区分开来对于密码分析以及密钥管理等具有重大的意义等具有重大的意义 20066信源编码器信道解码器接收者秘密信道密 码 分 析者密钥源密钥源200671密码分析和密码攻击密码分析和密码攻击 如果非授权者借助窃听到的密文以及其他一些信息通过各种方法推断原来的明文甚至密钥，这一过程称为密码分析或密码攻击。2 2多种攻击行为多种攻击行为 密码系统所假想的环境中除了接收者外，还有非授权者，它们通过各种方法来窃听、干扰信息 3 3无条件的安全性无条件的安全性 对于一个密码系统来说.若攻击者无论得到多少密文也求
5、不出确定明文的足够信息,这种密码系统就是理论上不可破译的,即密码系统具有无条件安全性(或完善保密性)200684.4.实际安全性实际安全性 若一个密码系统原则上虽可破译，但为了由密文得到明文或密钥却需付出十分巨大的计算，而不能在希望的时间内或实际可能的经济条件下求出准确的答案，这种密码系统就是实际不可破译的，或称称该密码系统具有计算安全性 5.5.影响安全性的几个因素影响安全性的几个因素v算法强度算法强度 算法的强度越高，攻击者越难破译 v其它因素其它因素其他的各种非技术手段（如管理的漏洞，或是某个环节无意暴露了敏感信息等）来攻破一个密码系统 20069u惟密文攻击惟密文攻击 分析者知道一个或
6、一些密文密文的情况下，企图得到明明文文或密钥密钥等敏感信息 u已知明文攻击已知明文攻击 分析者知道一些明文及对应的密文的对应关系对应关系 u选择明文攻击选择明文攻击 分析者获得更大机会接近密码系统，可以选择选择一些对攻击有利的特定明文特定明文，并得到对应的密文，以及在此基础上进行密码的破译 u选择密文攻击选择密文攻击 与选择明文攻击相反，分析者可以选择选择性地知道一些攻击有利的特定密文特定密文，并得到对应的明文 200610u 密码系统的密钥空间必须足够地大 u 加密与解密过程必须是计算上可行的，必须能够被方便地实现与使用 u 整个密码系统的安全性系于密钥上，即使密码方案被公布公布，在密钥不泄
7、露不泄露的情况下，密码系统的安全性也可以得到保证。200611u三种考虑角度v（1）从明文到密文的变换替换(substitution)置换(transposition)v（2）钥匙的数目对称、单钥加密法双钥、公钥加密v（3）明文的处理方式分组加密（块加密算法）流方式加密200612uUnconditionally secure，绝对安全？v永不可破，是理想情况，理论上不可破，密钥空间无限，在已知密文条件下，方程无解。但是我们可以考虑：破解的代价超过了加密信息本身的价值破解的时间超过了加密信息本身的有效期uComputationally secure，v满足上述两个条件200613u假设密码(p
8、assword)k是固定的u明文和密文是一个映射关系：单射，即 Ek(x1)!=Ek(x2)if x1!=x2u通常情况是：明文非常有序u好的密码条件下，我们期望得到什么样的密文v随机性200614u打破明文本身的规律性v随机性(可望不可及)v非线性(一定要)v统计意义上的规律u多次迭代v迭代是否会增加变换的复杂性v是否存在通用的框架，用于迭代u复杂性带来密码分析的困难和不可知性v实践的检验和考验200615u经典密码算法v替换技术(Substitution)v置换技术(Transposition)u现代密码算法vDESv其他密码算法200616u要求的计算强度小u以字母表为主要加密对象u替换
9、和置换技术u数据安全基于算法的保密u密码分析方法基于明文的可读性以及字母和字母组合的频率特性200617u太平洋战争中，美军破译了日本海军使用的JN25密码，一举扭转了太平洋战争中的劣势。u1949年，香农Information Theory of Secrecy System的发表标志着密码从“黑色艺术”进入科学研究领域，论文证明了一次一密是安全的，并给出两个密码设计原则：混淆与扩散。200618uDES(Data Encryption Standard)uIDEAuRC5uAESuBlowfishuCAST-128u200619u加密:E:(X,K)Y,y=E(x,k)XYKEYXKDu解
10、密:D:(Y,K)X,x=D(y,k)200620u序列(流)密码与分组密码v序列密码(stream cipher)也叫流密码，是对单个明文位(Bit-by-bit)变换的操作v分组密码(block cipher)是对一个大的明文块(Block-by-block)进行固定变换的操作200621200622200623uConfusion(混淆)v为了防止分析者利用明文与密文之间的依赖关系进行破译，密码的设计应该增加明文与密文之间关系的复杂性uDiffusion(发散)v小扰动的影响波及到全局，密码的设计应保证密钥的每位数字能够影响密文中的多位数字。v密文没有统计特征，明文一位影响密文的多位，增
11、加密文与明文之间关系的复杂性200624u电子簿模式(electronic codebook mode)ECBu密码块链接(cipher block chaining)CBCu密码反馈方式(cipher feedback)CFBu输出反馈方式(output feedback)OFB200625u相同明文相同密文u同样信息多次出现造成泄漏u信息块可被替换u信息块可被重排u密文块损坏仅对应明文块损坏u适合于传输短信息200626但是，通过采用流密码流密码的设计思想，在加密过程中采用合理的记忆组件记忆组件，能够消除这些局限性。如果在构造分组密码系统的时候直接采用分组密码算法，则称这种工作模式为电码本
12、（ECB）模式。分组密码的上述缺陷导致了这种工作模式也具有相应的缺陷。因此，实际采用的分组密码工作模式是对电码本（ECB）模式的改进。u分组密码主要有两个优点分组密码主要有两个优点v 易于标准化v 易于实现同步u局限性局限性v 分组密码不便于隐藏明文的数据模式v 对于重放、插入、删除等攻击方式的抵御能力200627u需要共同的初始化向量IVu相同明文不同密文u初始化向量IV可以用来改变第一块u安全性好于ECB200628uCFB:分组密码流密码u需要共同的移位寄存器共同的移位寄存器初始值IVu对于不同的消息，IV必须唯一u一个单元损坏影响多个单元:(W+j-1)/j W为分组加密块大小，j为流
13、单元位数200629uOFB:分组密码流密码u需要共同的移位寄存器共同的移位寄存器初始值IVu一个单元损坏只影响对应单元200630信源编码器信道解码器接收者秘密信道密码分析者密钥源密钥源200631u基本思想：用简单算法的乘积来近似表达大尺寸的替换变换u多个简单算法的结合得到的加密算法比任何一个部分算法都要强u交替使用替换置换和排列(permutation)u混淆(confusion)和发散(diffusion)概念的应用200632200633u加密:Li =Ri-1;Ri=Li-1F(Ri-1,Ki)u解密:Ri-1=Li Li-1=RiF(Ri-1,Ki)=RiF(Li,Ki)2006
14、34u分组大小：越大安全性越高，但速度下降，64比较合理u密钥位数：越大安全性越高，但速度下降，64广泛使用，但现在已经不够用128u步数：典型16步u子钥产生算法：算法越复杂，就增加密码分析的难度u每一步的子函数：函数越复杂，就增加密码分析的难度u快速软件实现：包括加密和解密算法u易于分析：便于掌握算法的保密强度以及扩展办法。200635u1977年由美国的标准化局(NBS，现为NIST)采纳u64位分组、56位密钥u历史：vIBM在60年代启动了LUCIFER项目，当时的算法采用128位密钥v改进算法，降低为56位密钥，IBM提交给NBS(NIST)，于是产生DESu16轮的Feistel
15、结构密码200636uDES是对称密钥加密的算法，DES算法大致可以分成四个部分：v初始置换v迭代过程v逆初始置换v子密钥生成200637明文（位）初始置换（IP）LPTRPT16轮16轮逆初始置换（FP）密文（位）200638输入（64位）58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 7输出（6
16、4位）初始变换IPL0（32位）R0（32位）200639LiLi-1Ri-1Ri Li-1 f(Ri-1,Ki)200640 左半部分 32 位 右半部分32位 新的左半部分 新的右半部分 密钥移位 置换后的密钥 f+200641密钥变换扩展置换S盒替换P盒替换异或与交换200642A(32位)扩展置换E48位结果48位Ki+选择函数组选择函数组(S1S8)32位结果置换运算P加密时A=Ri-1压缩置换EK(56位)20064320064457 49 41 33 25 17 9 1 58 50 42 34 26 1810 2 59 51 43 35 2719 11 3 60 52 44 36
17、63 55 47 39 31 33 15 7 62 54 46 38 30 2214 6 61 53 45 37 2921 13 5 28 20 12 414 17 11 24 1 5 3 28 15 6 21 1023 19 12 4 26 816 7 27 20 13 241 52 31 37 47 5530 40 51 45 33 4844 49 39 56 34 5346 42 50 36 29 32i1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16LS 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1200645A32位32 1 2 3 4
18、5 4 5 6 7 8 9 8 9 10 11 12 1312 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 1选择运算E选择运算E的结果48位200646u在密码函数中有在密码函数中有8个个S盒，称为盒，称为8个不同的个不同的选择函数。每个选择函数。每个S盒都是将盒都是将6位作为输入，位作为输入，得到一个得到一个4位块作为输出位块作为输出u S 盒是盒是DES 的最敏感部分，其原理至今未的最敏感部分，其原理至今未公开。人们担心公开。人们担心S 盒隐藏陷门，使得只有他盒隐藏陷门，使
19、得只有他们才可以破译算法，但研究中并没有找到们才可以破译算法，但研究中并没有找到弱点。弱点。200647S(1):14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 0700 15 07 04 14 02 13 01 10 06 12 11 09 05 03 0804 01 14 08 13 06 02 11 15 12 09 07 03 10 05 0015 12 08 02 04 09 01 07 05 11 03 14 10 00 06 132006488个选择函数的输出（32位）位）16 7 20 2129 12 28 17 1 15 23 26
20、5 18 31 10 2 8 24 1432 27 3 919 13 30 622 11 4 25置换P加密函数的结果X（32位）位）200649uBiham和和Shamir的研究发现，只要将的研究发现，只要将DES算法的第算法的第3 个盒与第个盒与第7个盒对调，就会使个盒对调，就会使DES算法在某类攻击算法在某类攻击 下，其安全性下降一下，其安全性下降一个级数。个级数。Biham,E.and Shamir,A.,”Differential Cryptanalysis of DES-like Cryptosystems”,Journal of Cryptology,Vol.4#1,1991,p
21、p.3-27200650u数据的初始置换和末置换对算法的安全性无意义。v假设没有初始置换和末置换的算法称为EDS算法。如果能够破解该算法，即给定算法的一对明密文对，能够很容易找到密钥E,则E也是对应DES算法的密钥。假定DES明文对（m,c),对m做初始置换的逆运算得m,对c做末置换的逆运算得c,将（m,c)用EDS算法的破解软件进行破解，故E也是DES算法的密钥。v如果用k1加密后再用k2加密，k1的末置换与k2的初始置换相抵消，现在通常用交互使用加密与解密运算的方法。200651u穷举攻击v56位密钥的使用，理论上，97年$100000的机器可以在6小时内用穷举法攻破DESv实际攻破的例子
22、，97年1月提出挑战，有人利用Internet的分布式计算能力，组织志愿军连接了70000多个系统在96天后攻破uDES算法的本质v关键在于8个S-BOXu针对DES的密码分析v穷举攻击。用于任何分组密码，攻击复杂度只依赖于分组长度和密钥长度v差分分析法v线性分析法200652u Biham和Shamir于1991年提出u 属于选择明文攻击选择明文攻击u 基本思想：通过分析特定明文差对结果密文差明文差对结果密文差的影响来获得可能性最大的密钥u 适用于攻击迭代分组密码。对较低轮次的DES攻击较成功，如8轮的DES在PC机上几分钟就可以用差分攻击破译。u 针对每一个DES步骤，用差分法可以推导出该
23、步的密钥。通过分析DES的8个S盒，对于明文对的某一差别，在其导致的所有各种可能的密文对的差别中，总有一种具有较高的概率，达到这种较高概率的明文对称为正确对，正确对暗示了最后一轮加密函数正确的子密钥，当偿试了足够多的正确对以后，由能够发现具有最大概率的正确的子密钥。对于DES算法，当得出K16以后，则确定了56位密钥中的48位，其余8位可以通过穷尽分析得到。u 247对选择明文，经过247量级的计算可攻破u 只有当尝试的明文对的数目超过某一阀值后，才能够从大量的候选值中发现正确的子密钥。此外此方法需要一个计数器为248个可能的子密钥分配不同的概率，数据量过大，使其实际上不可行。200653u线
24、性分析法vMatsui和Yamagishi于1992年v思想：用线性近似线性近似描述DES变换。寻找一个给定密码算法的有关明文比特、密文比特和密钥比特的有效的线形近似表达式，通过选择充分多的明密文对来析取密钥的某些比特。v根据247已知明文，可以找到DES的密钥200654uS盒设计u弱密钥或半弱密钥v弱密钥：密钥K使每个左右两部的密钥所有位都是0或1。v半弱密钥：这些密钥将明文加密成相同的密文uDES结构的互补对称性v由于互补对称性，攻击者可在选择明文攻击时仅需要试验其可能性密钥256的一半，互补对称性告诫不要使用互补密钥()()kkDESMDESM200655u双重DESu三重DESv三个
25、密钥v两个密钥200656200657200658C=Ek2Ek1P =T=Ek1P=Dk2C 对于一对已知的（P、C）u 对于所有的k1，计算Ek1P，将256个结果排序u 对于所有的k2，计算Dk2C，将256个结果排序u 进行匹配搜索，每找到一对，再用其他（P、C）对进行检验，直到找到正确的k1和k2密钥的空间为2112,但是只需要257个DES操作200659u三个密钥200660u两个密钥200661uIDEA算法 uRC5 u高级加密标准（AES）200662uIDEA算法可用于加密和解密。主要有三种运算：异或、模加、模乘，容易用软件和硬件来实现。uIDEA的速度：现在IDEA的软
26、件实现同DES的速度一样块。uIDEA的密码安全分析：IDEA的密钥长度是128位，是DES的密钥长度的两倍。在穷举攻击的情况下，IDEA将需要经过2128次加密才能恢复出密钥。200663u是由瑞士苏黎士联邦工业大学的Xuejia Lai和James L.Massey于1991年提出的。u属于对称密码体系u基本运算v异或v模216加法；v修改过以适应216范围的乘法X：计算32位结果，用216+1取余。200664u IDEA工作原理64位输入 第一轮 64位输出第二轮第17轮密钥扩展 128位密钥 K1K2K3K4K5K6K49K50K51K52200665XaXaKaXdXdKdXcXc
27、KcXbXbKb200666XaXaXdXdXcXcKeKfXbXbMangler 函数Yout=(Ke X Yin)+Zin)X KfZout=(Ke X Yin)+YoutYinYoutZinZout200667v IDEA将128位密钥扩展成52个16位的循环密钥，加解密的密钥扩展方式是不同的。v 加密循环密钥的产生方式为：（1）将主密钥分成8个16比特块，便得到K1-K8；（2）将主密钥循环左移24位，再按（1），便得到K9-K16；（3）再将（2）重复4次，得到32个循环密钥匙；（4）将主密钥循环左移22位，从最左开始取4个16比特块作为K49-K52v 解密循环密钥的产生方式为：在
28、奇数循环中，解密密钥是对应加密密钥的逆元。在偶数循环中，根据运算的可逆性可知两种密钥对应相同，如解密密钥K47与加密密钥K5相同。u能抵抗差分攻击(1)在著名的邮件加密软件PGP中采用了IDEA算法200668u RC5是是Ron.Rivest 于于1994年设计的一种新的年设计的一种新的分组算法。它的前身分组算法。它的前身RC2、RC4分别是可变分别是可变密钥长度的分组和流加密算法。密钥长度的分组和流加密算法。RC5是可变是可变密文长度、可变轮数、可变密钥长度的分组密文长度、可变轮数、可变密钥长度的分组加密算法加密算法 u RC5加密算法的特点有：加密算法的特点有：u 基本运算是微处理器上常
29、见的初等运算基本运算是微处理器上常见的初等运算 u 字的位数作为字的位数作为RC5的参数的参数 u 安全性依赖于旋转运算和不同运算的混合安全性依赖于旋转运算和不同运算的混合 u 存储要求低，适合在智能卡上实现存储要求低，适合在智能卡上实现 u 轮数和密钥长度可以变化轮数和密钥长度可以变化 1.RC5算法由密钥扩展算法、加密算法、解密算法由密钥扩展算法、加密算法、解密算法组成算法组成 200669u1997年NIST宣布征集AES算法v要求:与三重DES比，要快且至少一样安全,分组128位,密钥128/192/256位u1998年确定第一轮15个候选者u1999年确定第二轮五个候选者:MARS,RC6,Rijndael,Serpent,Twofishu2000年10月Rijndael胜出200670u不属于Feistel结构u加密、解密相似但不对称u支持128/192/256(/32=Nb)数据块大小u支持128/192/256(/32=Nk)密钥长度u有较好的数学理论作为基础u适合在所有32位机到IC卡上的实现u结构简单、速度快200671u消除了DES中出现的弱密钥的可能u也消除了IDEA中发现的弱密钥u能有效抵抗目前已知的攻击算法v线性攻击v差分攻击
