第2章密码学基础分析解析ppt课件.ppt

《第2章密码学基础分析解析ppt课件.ppt》由会员分享，可在线阅读，更多相关《第2章密码学基础分析解析ppt课件.ppt（187页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息系统安全第2章 密码学基础 2.1 密码学基础知识 2.2 古典替换密码 2.3 对称密钥密码 2.4 公开密钥密码 2.5 消息认证信息系统安全密码的起源 古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。 古希腊的斯巴达人曾将军事情报刻在普通的木板上，用石蜡填平，收信的一方只要用火烤热木板，融化石蜡后，就可以看到密信。信息系统安全 密码学用于通信的另一个记录是斯巴达人于公元前400年应用锥形指挥棒在军官间传递秘密信息。信息系统安全我国古代的藏头诗、藏尾诗、漏格诗 水浒传 “吴用智赚玉麒麟”一回中的诗 卢花滩上有扁舟，俊杰黄昏独自游。 义到尽头原是命，反躬逃难必无忧。 明代

2、怪杰徐文长： 平湖一色万顷秋， 湖光渺渺水长流。 秋月圆圆世间少， 月好四时最宜秋。信息系统安全 王先生：来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。 王先生：来信收悉，你的盛情真是难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把方能上街，苦矣。大约本月中旬我才能返回，届时再见。信息系统安全密码学应用例子 在1962年的古巴导弹危机中,苏美剑拔弩张,形势严峻。据悉，美国人心生一计，故意用能被苏联截收、破译的密码告知其军队，准备与苏联开战。这一手果然吓住了赫鲁晓夫。 1994年, 美国的情报机构通过截获国际电

3、讯得知，法国与沙特阿拉伯正在进行一笔数亿美元的军火交易，美国先行一步从法国人手中抢下了这笔大生意。信息系统安全2.1 密码学基础知识2.1.1 引言密码学（Cryptology）是研究密码编制、密码破译和密钥管理的一门综合性应用科学。+密码编码学（Cryptography）密码分析学（Cryptanalytics）信息系统安全 伪装信息，使未授权者不能理解它的真实含义。 所谓伪装就是对信息进行一组可逆的数学变换。伪装前的原始信息称为明文（Plain Text）, 伪装后的信息称为密文（Cipher Text），伪装的过程称为加密（Encrypt）。去掉伪装还原明文的过程称为解密（Decrypt

4、）。加密在加密密钥（Key）的控制下进行。解密在解密密钥的控制下进行。用于对数据加密的一组数学变换称为加密算法。用于对密文解密的一组数学变换称为解密算法，而且解密算法是加密算法的逆。 密码的基本思想信息系统安全 明文（plaintext)：信息的原始形式，一般是信息的基本单元（字母、数字或符号等）的有限排列； 密文（cipher)：明文经过加密以后的结果形式 加密变换(encryption) ：从明文到密文的变换过程 解密变换(decryption) ：从密文还原成明文的过程 加密算法：对明文进行加密时采用的一组规则。 解密算法：对密文进行解密时采用的一组规则。 密钥（key)：用于加解密变换

5、的关键信息，视其用于加解密而分别称为加密密钥与解密密钥；信息系统安全2.1.2 密码体制加密函数E作用于明文M得到密文C，用数学表示为： E（M）=C. 相反地，解密函数D作用于C产生M D（C）=M. 先加密后再解密消息，原始的明文将恢复出来，下面的等式必须成立： D（E（M）=M信息系统安全明文明文加密算法解密算法信道CMMC攻击者加密钥解密钥KeKd信息系统安全2.1.3 密码分类（1）古典密码v 密码学还不是科学,而是艺术v 出现一些密码算法和加密设备v 简单的密码分析手段出现v 主要特点：数据的安全基于算法的保密古典密码的加密方法一般是代换与置换，使用手工或机械变换的方式实现。信息系

6、统安全古典密码的代表密码体制主要有：单表代替密码：Caesar密码；多表代替密码：Playfair密码、Hill密码、Vigenere密码；转轮密码：著名的Enigma密码，第二次世界大战中使用过。（1）古典密码信息系统安全20世纪早期的密码机信息系统安全2.1.3 密码分类（2）对称密钥密码v传统密码/常规密码/私钥密码/单钥密码v发送方和接收方共享一个共同的密钥v所有的传统密码算法都是私钥密码v20世纪70年代以前私钥密码是唯一类型v至今仍广泛应用对称密钥密码指加密过程和解密过程使用同一个密钥来完成。信息系统安全对称密钥密码模型信息系统安全 按照加密方式不同，对称密钥密码体制被分为流密码（

7、Stream Cipher）（或称序列密码）分组密码（Block Cipher）区别是：流密码是将明文消息按字符逐位加密；分组密码是将明文消息先进行分组，再逐组加密。 信息系统安全常用的密码分析攻击种类 已知：C1=EK（P1），C2=EK（P2），CI=EK（Pi）推导出：P1，P2，Pi；K或找出一个算法从Ci+1= EK（Pi+1）推出Pi+1 （1）唯密文攻击 v密码分析者有一些都用同一加密算法加密的密文，密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密钥来，以便可采用相同的密钥解出其他被加密的消息。信息系统安全（2）已知明文攻击 v密码分析者不仅可得到一些消息的密

8、文，而且也知道这些消息的明文。分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。已知：P1，C1=Ek（P1），P2，C2=Ek（P2），Pi，Ci=Ek（Pi）推导出：密钥k，或从Ci+1= Ek（Pi+1）推出Pi+1的算法。信息系统安全（3）选择明文攻击 v 分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。这比已知明文攻击更有效。因为密码分析者能选择特定的明文块去加密，那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密消息的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解密。

9、已知：P1，C1=Ek（P1），P2，C2=Ek（P2），Pi，Ci=Ek（Pi）其中P1，P2，Pi是由密码分析者选择的。推导出：密钥k，或从Ci+1= Ek（Pi+1）推出Pi+1的算法。信息系统安全（4）自适应选择明文攻击 v 这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择。在选择明文攻击中，密码分析者还可以选择一大块被加了密的明文。而在自适应选择密文攻击中，他可选取较小的明文块，然后再基于第一块的结果选择另一明文块，以此类推。信息系统安全（5）选择密文攻击v 密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，例如密码分析

10、者存取一个防窜改的自动解密盒，密码分析者的任务是推出密钥。（6）选择密钥攻击v 这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间的关系的有关知识。这种方法有点奇特和晦涩，不是很实际 ，在此不作介绍。信息系统安全2.2 古典替换密码2.2.1 简单代替密码v代替密码就是明文中每一个字符被替换成密文中的另外一个字符。接收者对密文进行逆替换就恢复出明文来。v简单代替密码就是明文的一个字符用相应的一个密文字符代替。信息系统安全（1） 移位密码“恺撒密码”据传是古罗马恺撒大帝用来保护重要军情的加密系统。它是一种替代密码，通过将字母按顺序推后起3位起到加密作用，如将字母A换作字母

11、D，将字母B换作字母E。据说恺撒是率先使用加密函的古代将领之一，因此这种加密方法被称为恺撒密码。 假如有这样一条指令： RETURN TO ROME 用恺撒密码加密后就成为： UHWXUA WR URPH 信息系统安全 替代密码(substitution cipher)的原理可用一个例子来说明。 abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABCcaesar cipherFDHVDU FLSKHU明文密文明文a变成了密文D信息系统安全（2） 乘数密码乘数密码的加密变换为Ek(m)= k * m mod q ,gcd(k,q)=1这种密码也称

12、采样密码， 是将明文字母表按序号每隔k位取出一个字母排列而成密文（字母表首尾相连）。显然，当(k,q)=1， 即k与q互素时才是一一对应的。信息系统安全为什么必须互素？v 素数也叫质数。一个大于1的自然数，如果除了1和它自身外，不能被其他自然数整除的数。v 若N个整数的最大公因数是1，则称这N个整数互质。例如8,10的最大公因数是2，不是1，因此不是整数互质。7,10,13的最大公因数是1，因此这是整数互质，也称为互素。信息系统安全v Ek(m)= k * m mod q ,gcd(k,q)=1v 以英文字母为例q为26，假设 k=13 v 0= 13*2 mod 26=13*4 mod 26

13、=v m可以为任何2的倍数，导致无法解密为什么必须互素？信息系统安全选k=9，则由明文密文字母对应表明文：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z密文：A J S B K T C L U D M V E N W F O X G P Y H Q Z I R 于是对明文：Multiplicativer cipher有密文： EYVPUFVUSAPUHK SUFLKX。 信息系统安全（3） 仿射密码加法和乘法相结合，移位密码和乘数密码的结合。Ek(m)=(k1m+k2) mod q 其中， (k1, q)=1, 以k1, k2表示密钥。当

14、k2=0时就得到乘数密码，当k1=1时就得到位移密码，q=26时可能的密钥数为2612-1=311个。k1取值范围 （1，3，5，7，9，11，15，17，19，21，23，25）信息系统安全（4） 基于统计的密码分析v简单代替密码由于使用从明文到密文的单一映射，所以明文字母的单字母出现频率分布与密文中相同，可以很容易地通过使用字母频率分析法进行只有密文的攻击。信息系统安全2.2.2 多表代替密码v 多表代替密码是一系列（两个以上）代换表依次对明文信息的字母进行代换的加密方法。 v 令明文字母表为Zq，令=(1, 2, )为代换序列，明文字母序列为m=m1,m2, , 则相应的密文字母序列为c

15、=Ek(m)=(m)=1(m), 2(m), ，若为非周期的无限序列，则相应的密码为非周期多表代换密码，否则，为周期多表代换密码。 v 一次一密密码信息系统安全v维吉尼亚是法国的密码专家，以他的名字命名的维吉尼亚密码加密算法是多表密码的典型代表。代表：维吉尼亚密码 加密方式一：数学公式计算 设明文 P = p1p2pn，密钥 k = k1k2kn，密文C = c1c2cn 加密：ci= pi+ki (mod 26)，=1，2，n； 说明：若明文长度大于n，则k重复使用。信息系统安全 加密方式二：查表法 （密钥k，明文P）密文C34信息系统安全 加密过程：P“encode and decode”

16、，k“mykey”字母序号字母序号encodeanddecode明文编码明文编码P =4132143401333421434密钥编码密钥编码k =122410424122410424122410424加密加密C =1637121827162423727162624728模运算模运算111102密文密文C =QLMSBQYXHBQAYHC35信息系统安全 解密过程： C“QLMSBQYXHBQAYHC”，k“mykey”字母序号字母序号123456789101112131415密文编码密文编码C=161112181162423711602472密钥编码密钥编码k=1224104241224104

17、24122410424加密加密C=4-13214-2340133-234-24143-22模运算模运算133324密文解码密文解码C=encodeanddecode36信息系统安全v 强度在于：每个明文字母对应着多个密文字母，明、密文字母不是一一对应关系v 字母的统计规律进一步降低本人建议：密钥与明文一样长Caesar密码37信息系统安全攻击：首先作单表代换假设，用频率分析方法然后猜测Vigenre密钥关键字长度 密钥： deceptivedeceptivedeceptive 明文： wearediscoveredsaveyourself 密文： Z I CVTWQNGRZGVTWAVZHCQ

18、YGLMGJ反攻击：用与消息一样长的非周期性的密钥。相应的攻击：密钥和明文有相同的字母频率分布对抗技术：选择与明文一样长而且没有统计关系的密钥。技术的关键：密钥构造方法。Vernam密码：用循环的带子构造密钥。(最终密钥还是重复)信息系统安全2.2.3 换位密码在换位密码中，明文的字母保持相同，但顺序被打乱了。Plaintext:COMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVECOMPUTERGRAPHICSMAYBESLOWBUTATLEASTITSEXPENSIVECiphertext:CAELPOPSEEMHLANPIOSSUCWTITSBI

19、VEMUTERATSGYAERBTX信息系统安全换位加密法(1)Skytail Skytail 示例示例给定消息THIS IS FUNNY S T F H U I N S N I YTHISISFUNNY信息系统安全换位加密法(2) Double ColumnDouble Column示例示例CTARMRILISNPNOHEYOGTHONPNNHONPCMRATTGOYEETGOYMRATCSILIRRSILITIYPRIGORIGOMSTHCRENALONMSTHCRENTIYPALON信息系统安全换位加密法(3)RAIL-FENCE RAIL-FENCE 加密法加密法明文: this is

20、 a test密文: tiehsstsiat按按zigzag模式模式填写；密文填写；密文按行提取按行提取thtisitasse信息系统安全Turning Grilles 旋转方格：德军在一战中使用过的方法n = 4v2 构造方形棋盘 （2v 行和列）V=3123456789987654321987654321987654321234567891Result:换位加密法(4)信息系统安全 加密htisisatehtisisatestofthemestofthemethodokyouthodokyouaredonenoaredonenoThisisatestofthemethodokyouared

21、onenon信息系统安全解密：对密文旋转格子，即可读出明文htisisatestofthemethodokyouaredonenoThisisatestofthemethodokyouaredonenon信息系统安全2.3 对称密钥密码v对称密钥密码又称单密钥密码，建立在通信双方共享密钥的基础上，是加密密钥和解密密钥为同一个密钥的密码系统。v 现代密码系统依赖于具体用户的一个或多个密钥 ，而不依赖其算法的保密性 。v 在确定密码系统强度和加密无法通过密码分析技术破解的可能性中，密钥的长度始终是一个非常重要的因素。 信息系统安全信息系统安全2.3.1 对称密钥密码加密模式（1）流密码（序列密码）

22、原理：对输入的明文串按比特进行连续变换，产生连续的密文输出。算法计算流程是对明文消息按一定长度进行分组划分，利用密钥k通过有限状态机产生伪随机序列，使用该序列作为加密分组明文消息的系列密钥，对各分组用系列不同的密钥逐比特进行加密得到密文序列。信息系统安全v 流密码算法 Stream Cipher 每次可以加密一个比特 适合比如远程终端输入等应用v 流密码可用伪随机数发生器实现 密钥做为随机数种子，产生密钥流keystream (不重复,或极大周期) XOR (plaintext，key-stream )v One-time Pad信息系统安全专题：XOR异或也叫半加运算，其运算法则相当于不带进

23、位的二进制加法：二进制下用1表示真，0表示假，则异或的运算法则为：00=0，10=1，01=1，11=0（同为0，异为1），这些法则与加法是相同的，只是不带进位。z=x yz=xxoryv 异或运算，英文为exclusive OR。它应用于逻辑运算，异或的数学符号为“”，计算机符号为“xor”。其运算法则为：ab = (a b) (a b)两个值不相同，则异或结果为真。反之，为假。 不同为1，相同为0。异或，就是“看看你们到底一样不一样。不一样就为1，一样就为0。”信息系统安全若x是二进制数0101，y是二进制数1011 则xy=1110部分计算机语言用1表示真，用0表示假，所以两个字节按位异

24、或如下 00000000 xor 00000000-00000000 下面是两个二进制数值进行异或计算： 11111111xor00000000-11111111信息系统安全1.进行异或计算前会把数值都转换为二进制的：5和2转为二进制分别为：0101 、0010 0101 xor 0010 - 0111 2.再把结果 0111 转换为十进制的：73.所以 5 2 = 75 2 = ？信息系统安全v 流密码的思想起源密钥流生成器种子密钥明文m1k1c1m2k2c2加密过程信息系统安全密钥流生成器种子密钥密文c1k1m1c2k2m2解密过程v 流密码的思想起源信息系统安全 设明文为m=m1m2 m

25、iGF(2), i0 设密钥为k=k1k2 kiGF(2), i0 设密文为c=c1c2 ciGF(2), i0 则加密变换为ci mi + ki (mod 2) i0 则解密变换为mi ci+ ki (mod 2) i0v 流密码的思想起源信息系统安全 思想起源：20世纪20年代的Vernam体制， 即“一次一密”密码体制。香农利用信息论证明“一次一密”密码体制在理论上不可破译 由有限的种子密钥生成无限长的随机密钥序列 流密码研究内容设计安全高效的伪随机伪随机序列发生器密钥流生成、存储和分发困难随机序列计算机无法实现评测标准：线性复杂度高；周期大v 流密码的思想起源信息系统安全什么是伪随机序

26、列？具有某种随机特性的确定的序列。它们是由移位寄存器产生确定序列，然而他们却具有某种随机特性的随机序列。因为同样具有随机特性，无法从一个已经产生的序列的特性中判断是真随机序列还是伪随机序列，只能根据序列的产生办法来判断。信息系统安全58XOR值真值表 例信息系统安全59v 明文为“university”，密钥流为key=(1001011 1011001 1000101 1010101 1110001 1001011 1011001 1000101 1010101 1110001) 信息系统安全2.3.1 对称密钥密码加密模式（2）分组密码v 分组密码算法 Block Cipher 明文被分为固

27、定长度的块(即分组)，对每个分组用相同的算法和密钥加解密 分组一般为n64比特，或更长 (Padding) 密文分组和明文分组同样长信息系统安全v 固定长度称之为分组长度，分组长度值取决于实际应用的环境。v 对于通过计算机来实现的分组密码算法，通常选取的分组长度为64位。v 这是一个折中的选择，考虑到分组算法的安全性，分组长度不能太短，应该保证加密算法能够应付密码分析；考虑到分组密码的实用性，分组程度又不能太长，要便于操作和运算。v 近年来，随着计算机计算能力的不断提高，分组长度为64位的分组密码的安全性越来越不能满足实际需要，为了提高加密的安全性，很多的分组密码开始选择128位作为算法的分组

28、长度。信息系统安全v 分组密码的加密过程是对一个分组长度为n位的明文分组进行加密操作，相应地产生一个n位的密文分组v 考虑到加密算法的可逆性(即保证解密过程的可行性)，每一个不同的n位明文分组都应该产生一个惟一的密文分组 加密过程对应的变换被称为可逆变换或非奇异变换 分组密码算法从本质上来说是定义了一种从分组的明文到相应的密文的可逆变换。信息系统安全2.3.2 数据加密标准DES Data Encryption Standardv DES的产生 1973年5月15日, NBS开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3

29、)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所有用户(5)算法适用于不同应用场合(6)算法必须高效、经济(7)算法必须能被证实有效(8)算法必须是可出口的信息系统安全1974年8月27日, NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在19711972年研制1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种政府机构1977年1月15日,“数据加密标准”FIPS PUB 46 发布1979年，美国银行协会批准使用1980年，美国国家标准局赞同DES作为私人使用的标准,称之为DEA（ANSI .392）。1983年，国际化标准组织ISO赞同D

30、ES作为国际标准，称之为DEA-1。该标准规定每五年审查一次，计划十年后采用新标准。最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。信息系统安全v Simplified DES方案，简称S-DES方案。v 加密算法涉及五个函数： 初始置换IP(initial permutation) 复合函数fk1，是由密钥K确定，具有置换和替代的运算。 转换函数SW 复合函数fk2 初始置换IP的逆置换IP-1 置换函数P8、P10（1） 简化的DES信息系统安全信息系统安全 S-DES加密算法数学来表示为：密文=IP-1*fk2*SW*fk1*IP 密文=IP-

31、1（fk2(SW(fk1(IP(明文) 其中 K1=P8(移位(P10(密钥K) K2=P8(移位(移位(P10(密钥K) 解密算法的数学表示 明文=IP-1（fk1(SW(fk2(IP(密文) 信息系统安全专题：移位移位运算符就是在二进制的基础上对数字进行平移。按照平移的方向和填充数字的规则分为：(右移)。 （1）左移 运算规则：按二进制形式把所有的数字向左移动对应的位数，高位移出(舍弃)，低位的空位补零。 语法格式：需要移位的数字 移位的次数 例如： 3 2，则是将数字3左移2位 计算过程： 3 运算规则：按二进制形式把所有的数字向右移动对应巍峨位数，低位移出(舍弃)，高位的空位补符号位，

32、即正数补零，负数补1。 语法格式： 需要移位的数字 移位的次数 例如：11 2，则是将数字11右移2位 计算过程： 11 211的二进制形式为：0000 0000 0000 0000 0000 0000 0000 1011，然后把低位的最后两个数字移出，因为该数字是正数，所以在高位补零。则得到的最终结果是0000 0000 0000 0000 0000 0000 0000 0010。转换为十进制是3。数学意义：右移一位相当于除2，右移n位相当于除以2的n次方。信息系统安全 S-DES的密钥生成： 设10bit的密钥为（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10) , 置换P1

33、0是这样定义的 P10(k1,k10) =(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) 相当于P10=（3 5 2 7 4 10 1 9 8 6） LS-1为循环左移一次， P8= (6 3 7 4 8 5 10 9)信息系统安全算法如下图 按照上述条件,若K选为(1010000010), 产生的两个子密钥分别为 K1=(1 0 1 0 0 1 0 0)，K2=(0 1 0 0 0 0 1 1)信息系统安全 S-DES的加密运算: 初始置换用IP函数: IP= 末端算法的置换为IP的逆置换: IP-1= 易见IP-1(IP(X)=X。信息系统安全简化的得DES方案加密细节如

34、右图信息系统安全 函数fk，是加密方案中的最重要部分，它可表示为：fk(L,R)=(LF(R,SK),R)； 其中L、R为8位输入的左右各4位,，F为从4位集到4位集的一个映射, 并不要求是1-1的。 SK为子密钥。对映射F来说：首先输入是一个4位数（n1,n2,n3,n4），第一步运算是扩张/置换（E/P）运算： E/P=( 4 1 2 3 2 3 4 1) 信息系统安全E/P=( 4 1 2 3 2 3 4 1)事实上，它的直观表现形式为：事实上，它的直观表现形式为：信息系统安全 8-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后,与E/P的结

35、果作异或运算得： 信息系统安全上述第一行的4位输入进S盒S0，产生2位的输出；第二行的4位输入进S盒S1，产生2位的输出。两个S盒按如下定义：信息系统安全S盒按下述规则运算： 将第1和第4的输入比特做为2 bit数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列。如此确定为S盒矩阵的（i,j）数。例如：（P0,0, P0,3）=(0 0)，并且(P0,1,P0,2)=(1 0)，确定了S0中的第0行2列（0，2）的系数为3，记为（1 1）输出。由S0, S1输出4 bit经置换 P4=(2 4 3 1)； 它的输出就是F函数的输出。信息系统安全把它们重记为8位：信息系统安全v DE

36、S是一种对二元数据进行加密的算法v 数据分组长度为64位,密文分组长度也是64位,使用的密钥为64位,有效密钥长度为56位,有8位用于奇偶校验v 解密时的过程和加密时相似,但密钥的顺序正好相反,DES的整个体制是公开的,系统的安全性完全靠密钥的保密（4）DES算法信息系统安全DES特点v 设计目标：用于加密保护静态储存和传输信道中的数据，安全使用10-15年v 综合应用了置换、代替、代数等多种密码技术v 分组密码。v明文、密文、密钥的分组长度为64位v采用feistel结构v 面向二进制的密码算法。v 加密解密共用一个算法。信息系统安全Li-1Ri-1一个分组专题：Feistel网络结构LiR

37、iFKi信息系统安全FeistelFeistel网络基本原理网络基本原理 p 明文分组分为左右两个部分L0和R0，数据的这两部分通过n次循环处理后，再结合起来生成密文分组；p 每i次循环都以上一次循环输出比特串的左右两个部分Li-1和Ri-1，以及K产生的子密钥Ki作为输入。（子密钥Ki是用子密钥生成算法从密钥K中生成的）p 所有循环的结构都相同，置换在数据的左半部分进行，先对数据的右半部分应用循环函数F，然后对函数输出结果和数据的左半部分取异或(XOR)；p 循环函数对每次循环都有相同的通用结构，仅仅是每次循环子密钥Ki不同；p 在置换之后，执行由数据左右两部分互换构成的交换； 信息系统安全

38、Feistel加密过程 信息系统安全 DES的加密解密原理 1v 64位密钥经子密钥产生算法产生出16个子密钥:K1K2K16,分别供第一次、第二次第十六次加密使用64位明文首先经过初始置换IP(Initial Permutation),将数据打乱重新排列并分成左右两半。左边32位构成L0，右边32位构成R0信息系统安全 DES的加密解密原理 2v 由加密函数f实现子密钥K1对R0的加密，结果得32位的数据组f(R0, K1)。 v f(R0, K1)再与L0模2相加，又得到一个32位的数据组作为第二次加密迭代的R1，以R0作为第二次加密迭代的L1。至此，第一次加密迭代结束。v 第二次加密迭代

39、至第十六次迭代分别用子密钥K2K16进行，过程与第一次相同。信息系统安全 DES的加密解密原理 3v 第十六次加密迭代结束后，产生一个64位的数据组。左边32位作为R16,右边32位作为L16,两者合并在经过逆初始置换IP-1,将数据重新排列，得到64位密文。加密过程全部结束。信息系统安全DES的加密解密原理图解输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据产生16个密钥Feistel结构信息系统安全2.3.3 分组密码的工作模式 DES的工作模式：电子密码本ECB (Electronic Codebook)密码分组链接CBC (Cipher Bl

40、ock Chaining)密码反馈CFB (Cipher Feedback)输出反馈OFB (Output Feedback)信息系统安全（1）电子密码本模式 电子密码本模式（Electronic Codebook ） 最基本的加密模式，也就是通常理解的加密。运用相同密钥，分别将每64位明文加密。信息系统安全信息系统安全信息系统安全信息系统安全v ECB简单和有效，可以并行实现。v 不能隐藏明文的模式信息，相同明文生成相同密文。v ECB可能受到的主动攻击是信息块被替换、重排、删除、重放。v ECB不存在误差传递现象，因此ECB工作模式适合于传输短信息。信息系统安全信息系统安全 明文被加密前要

41、与前面的密文进行异或运算后再加密。（2）密码分组链接CBC（Cipher Block Chaining）信息系统安全信息系统安全信息系统安全 相同的密文加密后会形成不同的密文，这是目前应用最广泛的模式。信息系统安全密文错误会导致错误扩散（Error Propagation）例如：如果一个分组丢失，后面的分组将全部作废(同步错误)。信息系统安全 一种将DES转化成流密码的技术。 对任意长度明文加密。 不再要求报文被填充成整个分组。 可以实时运行。（3）密码反馈模式CFB信息系统安全信息系统安全CFB加密过程v 加密：加密函数的输入是一个64位的移位寄存器，产生初始向量IV。v 加密函数高端j位与

42、明文P1的第一单元异或，产生j位密文C1进入移位寄存器低端v 继续加密，与P2输入异或，如此重复直到所有明文单元都完成加密。信息系统安全信息系统安全 和CFB相似 不过OFB用的是前一个n位密文输出分组反馈回移位寄存器 而CFB的密文单元被反馈回移位寄存器。（4）输出反馈模式OFB信息系统安全信息系统安全2.4 公开密钥密码公开密钥密码体制是现代密码学最重要的发明。信息系统安全v 密钥管理量的困难 传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间增大如：n=100 时C(100,2)=4,995；n=5000时C(5000,2)=1

43、2,497,500。v 数字签名的问题 传统加密算法无法实现抗抵赖、身份验证的需求。传统密钥存在的问题：信息系统安全2.4.1公开密钥理论基础v公钥密码又称为双钥密码和非对称密码，是加密密钥和解密密钥为两个独立密钥的密码系统。非对称算法密钥 K （Kd，Ke），Kd即私钥 Ke即公钥加密：E（P，Ke） C解密：D（C，Kd） P要求从 Ke 不等于 Kd信息系统安全1.公开密钥密码通信模型（1）对称密钥密码模型信息系统安全（2）公开密钥密码模型信息系统安全v 每个用户生成密钥对(Ke、Kd)Ke或Kd是一个或几个数(大数)Ke需要公开Kd得自己秘密保留(公钥 public key 私钥pri

44、vate key 密钥 secret key)v 公钥的发布从Ke推导Kd的困难性使Ke不怕被公开公开的目录服务公钥Ke要在专门机构（CA）登记信息系统安全2.公开密钥密码的核心思想v 单向陷门函数v 满足下列条件的函数f（1）给定 x 计算y=f(x)是容易的；（2）给定 y, 计算 x 使y=f(x)是困难的；（3）存在，已知时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。信息系统安全3.公开密钥的应用v认证性：用来认证v机密性：用来加密信息系统安全v 加密（如果有人要给用户A发送消息P）他先获得该用户的公开钥Ke加密C = E（P，Ke）v 传输v 解密D（C，Kd）

45、P除非拥有Kd，如该用户A，否则不能解开（1）公钥算法用来加密信息系统安全公钥算法加密模型信息系统安全公钥算法加密图示公钥私钥信息系统安全（2）公钥算法用来认证 如果你(Bob)已经公布自己的公钥Ke，则他人可鉴别你发出的消息（及你的身份） 对于消息P，使用你的私钥C = E（P，Kd） 他人可把密文C用你的公钥解密D（C，Ke）P 可以确信P必然是由你加密成C的，因为加密需要的私钥只有你有。信息系统安全公钥算法认证模型信息系统安全公钥算法认证图示公钥私钥信息系统安全v 如果你已经有他的公钥Ke，则可鉴别他的身份v 取随机秘密消息P加密C = E（P，Ke）v 把密文C交给所谓的”他”，请他来

46、解密除非”他”拥有Kd，否则不能解开D（C，Kd）Pv 比较他解出的明文P是否正确v 如果他能正确解密，则”他”是真他信息系统安全（3）结合使用加密和签名v 有消息要发给对方，要署名且保密传递v 发送方：先用自己的私钥签名v 发送方：再用对方的公钥加密v 发送v 接受方：先用自己的私钥解密v 接受方：先用对方的公钥验证签名是否有效信息系统安全专题：欧拉定理v 欧拉函数 正整数n，由小于n且和n互素的正整数构成的集合表示为 Zn（被称之为：n的完全余数集合）。Zn包含的元素个数记为(n)，称为欧拉函数。一些数论知识专题信息系统安全怎样求一个任意数的欧拉函数值 (1)若m是素数，则 =m-1； (

47、2)若mpq，其中p、q是素数且p 不等于q，则 = (p1)(q1)； (3)若 且P全是素数，则 )(m)(m)(m信息系统安全例：比24小而与24 互素的正整数为：1、5、7、11、13、17、19、23。故 这12个数是：1,2,4,5,8,10,11,13,16,17,19,208)24(12) 17)(13()7()3()21(信息系统安全v 欧拉定理 给定两个素数p和q，以及两个整数m、n，使得n=pq，且0mn，对于任意整数k下列关系成立，nmmmqpknkmod1)1)(1(1)(同余：两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作 。读作a同

48、余于b模m，或读作a与b模m同余。如：)(modmba ）（12mod1426 信息系统安全 素数p的原根(primitive root)定义：如果a是素数p的原根，则数a mod p, a2 mod p, , ap-1 mod p 是不同的并且包含1到p-1的整数的某种排列。 对任意的整数b，我们可以找到唯一的幂 i 满足 b ai mod p ， 专题：原根10pi信息系统安全v 设m=7，则v 设a=2，由于 ，而3 6 ，所以 2 不是模 7 的一个原根。v 设a=3，由于 , , , ,所以 3 是模 7 的一个原根。6）（m)7(mod1823)7(mod331)7(mod232)

49、7(mod633)7(mod434)7(mod535)7(mod136信息系统安全专题：离散对数若a是素数p的一个原根,则对任意整数b，b0 mod p，存在唯一的整数i, 1i(p-1),使得: bai mod p ，i称为b以a为基数的模p的指数(离散对数)，记作Ind a,p(b)。离散对数的计算: ygx mod p 已知g,x,p,计算y是容易的； 已知y,g,p,计算x是困难的。信息系统安全专题：大整数因子分解1348576390608747635243 * 194765638905075766535 = ?184646640969877389676366823893743 = X

50、 * Y求解X和Y是困难的，当乘积足够大，X和Y求解接近不可行算法时间复杂性:v 线性时间和多项式时间内是可行的。v 指数时间是不可行的。信息系统安全gcd (a,b) = gcd( b, a mod b ) 专题：EuclidEuclid算法算法欧几里德(Euclid)算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理信息系统安全例如，求 gcd（319，377）： 377319=1（余58）（377，319）=（319，58）； 31958=5（余29）， （319，58）=（58，29）； 5829=2（余0）， （58，29）= 29； gcd（319，