信息安全数学基础ppt课件.ppt

《信息安全数学基础ppt课件.ppt》由会员分享，可在线阅读，更多相关《信息安全数学基础ppt课件.ppt（210页珍藏版）》请在三一办公上搜索。

1、信息安全数学基础,信息科学与工程学院,网络信息的安全威胁 网上犯罪形势不容乐观； 有害信息污染严重； 网络病毒的蔓延和破坏； 网上黑客无孔不入； 机要信息流失与信息间谍潜入； 网络安全产品的自控权； 信息战的阴影不可忽视。,引 言,网络通信的困境,引 言,我们要保护什么呢？,引 言,网络安全体系的五类服务,引 言,网络安全体系的五类服务,访问控制服务：根据实体身份决定其访问权限；身份鉴别服务：消息来源确认、防假冒、证明你 是否就是你所声明的你；保密性服务：利用加密技术将消息加密，非授权 人无法识别信息；数据完整性服务：防止消息被篡改，证明消息与 过程的正确性；防抵赖服务：阻止你或其他主体对所作

2、所为的进 行否认的服务，可确认、无法抵赖。,引 言,引 言,解决方法：加密,如何实现保密性？,密码分析,Alice,Bob,加密密钥,解密密钥,Eve,引 言,解决方法：数字摘要,如何实现完整性？,消息篡改,公共网络,Alice,Bob,m,z,m,z,z=hk(m),y=hk(m),Eve,引 言,解决方法：数字签名,如何实现不可否认性？,否认,公共网络,Alice,Bob,Trent,谁是正确的？,举报,引 言,解决方法：密码技术,身份鉴别：就是确认实体是它所声明的，身份鉴别服务提供关于某个实体身份的保证，以对抗假冒攻击。,如何鉴别通信对象的身份？,本课程的相关知识点,简单的密码学基础：

3、密码技术是信息安全的核心技术； 需要掌握一些密码学基础知识。相关的数学知识： 密码技术的实现依赖于数学知识； 掌握密码技术涉及的相应数学基础知识点。参考教材： (1) 密码学导引,机械工业出版社,Paul Garrett 著,吴世忠等译； (2) 信息安全数学基础,武汉大学出版社,李继国等 主编。,引 言,什么是密码技术？,窃听,公共网络,Alice,Bob,Eve,篡改,伪造,加密密钥,解密密钥,密文,密码学是一门古老而深奥的学科,包括密码编码学和密码分析学;通信双方按照某种约定将消息的原形隐藏。密码系统:明文,密文,加解密算法,密钥。,引 言,密码学的起源与发展三个阶段：1949年之前：密

4、码学是一门艺术；19491975年：密码学成为科学；1976年以后：密码学的新方向公钥密码学。1949年之前(手工阶段的初级形式)隐写术：隐形墨水、字符格式的变化、图像；,举例： 芦花丛中一扁舟，俊杰俄从此地游； 义士若能知此理，反躬难逃可无忧。 258 71539 258 314697 314697 15358 24862 17893,引 言,19491975年(机械阶段)：现代密码出现1949年香农Shannon提出“保密系统信息理论”；提出：数据的安全基于密钥而不是密码算法。1976年以后(计算机阶段)：公钥密码诞生1976年Diffie&Hellman的“New Directions

5、in Cryptography”提出了不对称密钥密码；1977年Rivest, Shamir & Adleman提出了RSA公钥算法；90年代出现椭圆曲线ECC等其他公钥算法。,引 言,对称密钥密码算法进一步发展1977年DES正式成为标准；80年代出现“过渡性”的“post DES”算法，如IDEA、RCx、CAST等；90年代对称密钥密码进一步成熟，Rijndael、RC6、MARS、Twofish、Serpent等出现；2001年Rijndael成为DES的替代者AES。2004年6月美国NIST提出最新信息加密技术-量子密码。 2004年山东大学王小云教授成功破解处理电子签名的MD5。

6、,引 言,密码算法的分类按照保密的内容分受限制的算法：保密性基于保持算法的秘密。基于密钥的算法：保密性基于密钥的保密。Kerchoffs原则1883年Kerchoffs第一次明确提出了编码的原则：保密性完全依赖于密钥，算法应该公开。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为古典密码和现代密码的分界线。,引 言,基于密钥的算法，按照密钥的特点分类：对称密码算法：又称秘密密钥算法或单密钥算法，加密密钥和解密密钥相同，或可以容易地从一个推出另一个。特点：加密速度快；密钥管理复杂，主要用于加密信息。非对称密钥算法：又称公开密钥算法，加密密钥和解密密钥不相同，而且很难从一个推出另一

7、个。特点：密钥管理简单，但加密速度慢，用于加密会话密钥和用于数字签名。实际网络应用中，常采用非对称密码来交换对称密码算法的密钥。,引 言,经典的古典密码算法主要有：代替密码：将明文字符用另外的字符代替，典型的有恺撒密码、仿射密码、维吉尼亚密码等；换位密码：明文的字母保持相同，但顺序打乱。,经典的现代密码算法有很多种，最通用的有：DES：数据加密标准，对称密码算法，用于加密；AES: 高级加密标准，对称密码算法，用于加密；,引 言,RSA：最流行的公钥密码算法，加密和数字签名；ECC：椭圆曲线密码，采用ElGamal算法，公钥密码算法，安全性高，密钥量小，灵活性好；DSA：数字签名算法，是数字签

8、名的一部分，公钥密码算法，数字签名。MD5(SHA-1)：数字摘要算法，数字签名，保证消息的完整性。,引 言,理论安全：攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。Shannon用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密密码本，不实用。 实际安全：如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行。,引 言,密码系统的安全,四种基本攻击类型： 唯密文攻击：攻击者只有一些密文； 已知明文攻击：攻击者知道

9、一些明文密文对； 选择明文攻击：攻击者可以选择明文密文对； 针对密钥的攻击：主要是针对公钥密码系统。 穷举攻击：攻击者采用尝试方法穷举可能的密钥。 当密钥空间较小时很有效。字典攻击是 利用一些常用的单词进行组合。 基本要求：任何一种加密系统都必须能够对抗唯 密文攻击。 目前的标准是：一个密码系统应当能够对抗选择 明文攻击。,引 言,密码系统的攻击,第一章 简单密码,经典的简单密码： 移位密码、一次一密乱码本、仿射密码。1.1 移位密码1.Caesar密码：最简单的移位密码。 原理：将消息中的每个字母前移3位或者后 移3位。 举例： all of gaul is devided into thr

10、ee parts DOO RI JDXO LU GLYLGHG LQWR WKUHH SDUWU2.移位密码： 改进Caesar密码：发送方和接收方协商一个密钥k，1k25，代表移动位数。,3.攻击： 穷举攻击：25种可能的密钥(密钥空间)；4.特点： 对称密码：加密密钥和解密密钥相同； 单表代替密码：所有的明文字母用同一种方法 加密，即子密钥相同。1.2 约简/整除算法1.n模m的约简： n除以m的余数r，0r|m| 记作：r=n%m 或者 r=n mod m，m称为模数。 计算：设a=|n|%|m|，则 当n0时，n%m=|m|-a； 当m0时，n%m=n%|m|。,第一章 简单密码,举例

11、： -10%7： 10%(-7)： -10%(-7)：,4，因为 -10=7(-2)+4,3，因为 10=-7(-1)+3,4，因为 -10=-72+4,注意： 任何整数模m的约简都是非负数。2.乘法逆 n模m的乘法逆t满足：nt%m=1 记作：t=n-1%m 举例： 2-1%5的值为： 3-1%100的值为：,3，因为 32%5=1,67，因为 673%100=1,第一章 简单密码,4.乘法逆元的计算 (1)穷举法：寻找满足条件的数。 技巧：若tn%m=-1，则n-1%m=m-t。 333%100=-1，所以3-1%100的值为67。,第一章 简单密码,3.命题 设m0,1为整数，x与m互素

12、，则x有模m的乘法逆元。特别地，满足表达式ax+bm=1的任意整数a就是一个x模m的乘法逆元。 假如y是x模m的乘法逆元，对于y，若m|y-y，那么y也是x模m的乘法逆元；反之亦然。,(2)欧几里德算法： 举例： 23-1%100 方法：100-423=8 23-28=7 8-17=1 7-71=0,所以： 1=3100-1323 1=-1323%100 23-1%100 = -13 = 87 1=3100%23 100-1%23=8-1%23 = 3算法：,1 =8-17 =8-1(23-28) =38-123 =3(100-423)-123 =3100-1323,1 -1 -1 3 3 -

13、13,所以：3100-1323 = 1,第一章 简单密码,1.3 欧几里得算法 用以寻找两个整数m和n的最大公因子d。 使用该算法将x和y的最大公因子表示为： ax+by=gcd(x,y)的形式。,1.举例描述 两个整数513和614 614-1513=101 513-5101=8 101-128=5 8-15=3 5-13=2 3-12=1,2.寻找整数a,b 1=3-12=3-1(5-13) =-15+23=-15+2(8-15) =28-35=28-3(101-128) =-3101+388 =-3101+38(513-5101) =38513-193101 =38513-193(614

14、-1513) =-193614+231513,最大公因子为1,第一章 简单密码,2.乘法逆元的计算,结论：当x和y互素时，gcd(x,y)为1，即可得到x-1%y为a，y-1%x为b。,第一章 简单密码,3.举例,所以：21-1%25的结果为6。例2：求1234-1%4321,例1：求21-1%25 解：25-121=4 21-54=1 4-14=0,第一章 简单密码,3.命题： (1)给定一非零整数m和任意整数n，存在唯一的 整数q和r，使得0r|m|且n=qm+r (2)设n和N为两个整数，对某个整数k有N=kn， 则对任意整数x有：(x%N)%n=x%n,1.3 一次一密乱码本OTP 1

15、.思想：密钥与消息一样长，且只能使用一次。 2.工作原理： 消息长度为n， x=(x1,x2,xn)； 随机密钥： k=(k1,k2,kn)； 加密：Ek(x)=(x1+k1)%26,(xn+kn)%26) 解密：Dk(y)=(y1-k1)%26,(yn-kn)%26),第一章 简单密码,3. 举例： 消息：n e v e r m o r e 密钥：e x c e l s i o r 密文：R B X I C E W F V,R(17)=(n(13)+e(4)%26F(5)=(r(17)+o(14)%26,4. 特点： 密钥的产生与分发管理复杂； 对称密码； 多表代替密码：明文中不同位置的字母

16、采用的加 密密钥不同。,第一章 简单密码,1.4 仿射密码 1.思想：对移位密码进行改进，扩大密钥空间。 2.原理： 加密：Ea,b(x)=(ax+b)%26 0a,b 25 解密：Da,b(y)= 3.特点： (1)当a=1时为移位密码； (2)加密密钥为(a,b)；解密密钥为(a-1,-a-1b)； (3)单表代替密码； (4)对称密码：由加密密钥可以推导出解密密钥；,第一章 简单密码,(5)密钥空间：由于a-1必须存在，所以可能的密钥数 为1226-1=311个。,第一章 简单密码,4.攻击方法： 穷举攻击：尝试311个可能的密钥。 选择明文攻击： Ea,b(0)=(a0+b)%26 E

17、a,b(1)=(a1+b)%26 已知明文攻击： Ea,b(x)=(ax+b)%26 Ea,b(y)=(ay+b)%26 唯密文攻击：字母频率攻击。,a=(x-y)-1(Ea,b(x)-Ea,b(y)%26b=(Ea,b(x)-ax)%26,b=Ea,b(0)a=(Ea,b(1)-b)%26,第一章 简单密码,举例： 已知明文：meet me at midnight 假设密文：HNNS HN DS HXEQXFOS (1)选择明文攻击 攻击者选择：a(0) D(3) d(3) E(4),第一章 简单密码,第一章 简单密码,第一章 简单密码,1.5 Vigenere密码 1.特点： 具有相对较大

18、的密钥空间； 对称密码；多表代替密码； 有周期性的弱点：若两个字符出现的间隔是密钥长度的倍数，则它们将以同样的方法加密。 2.加密和解密的原理：,(1)密钥是一个字符序列：k=(k0,k1,km-1)； 明文x=(x0,x1,xN)被分成长度为m的段。(2)加密函数：Ek(x0,x1,xN)=(y0,y1, yN) yi=(xi+ki%m)%26 解密函数：Dk(y0,y1, yN)=(x0,x1,xN) xi=(yi-ki%m)%26,第一章 简单密码,3.多轮加密,若一个明文使用密钥长度为m的维吉尼亚密码加密，得到的密文再用长度为n的密钥加密，其结果与用长度为lcm(m,n)的维吉尼亚密码

19、加密的结果一样。 若m,n互素，则lcm(m,n)=mxn，密钥长度很大。,第一章 简单密码,1.6最小公倍数lcm和最大公约数gcd,1.定义 对于两个整数d,n，若d整除n，或者说d是n的一个因子，记作：d|n 设m,n是两个非0的整数，则最大公约数d为最大的正整数，使得d|m和d|n，记作d=gcd(m,n)；最小公倍数N为最小的正整数，使得m|N和n|N，记作N=lcm(m,n)。 2.定理 m,n的最大公约数gcd(m,n)具有这样的特性：对于m,n的每一个公因子e满足e|gcd(m,n)； m,n的最小公倍数lcm(m,n)具有这样的特性：对于m,n的每一个公倍数N满足lcm(m,

20、n)|N；,第一章 简单密码,3.素数 素数p是那些不存在因子d的整数1dp1/2； 定理：每一个正整数都可以分解为素数的乘积， 而且这种分解是唯一的。 12=22x3 35=5x7,(1)对于每一个素数p，整除gcd(m,n)的p的方幂，是既整除m又整除n的p的方幂的最小值。 (2)两个方幂中较大的一个便组成了最小公倍数。 举例：3960=23x32x5x11 400=24x52 则： gcd(3960,400)=23x5=40 lcm(3960,400)=24x32x52x11=39600,第一章 简单密码,1.7 生日攻击,1.命题 在实验x中，不同结果x1,x2,xn的概率分别为p(x

21、1)=p1,p(xn)=pn。集合A为样本空间x1,xn的一个子集，且有p(A)=p。设0kN，则N次实验中A恰好出现k次的概率为：,举例：投币。假设一枚公平的硬币朝上或朝下的 几率是相等的，且每次投币是独立的。分析：记录一个n次投掷的过程：2n,任何单个序列出现的概率是1/2n,n次投掷恰好有k次正面朝上的概率是：,10次投掷中： 恰好5次正面朝上的概率为：252/10241/4 6-4或者4-6组合的概率是：420/10242/5,2.生日攻击 设=1,2,N为所有原子事件的样本空间，p(i)=1/N。n次实验后至少2次结果相同的概率至少为：1-e-n(n-1)/2N。因此，对于 出现两次

22、相同结果的概率至少为1/2。,第一章 简单密码,证明：先计算出没有两种完全相同结果出现的概 率p，则出现两次相同结果的概率p=1-p。,1次试验时，p1=1； 2次试验时，两次结果相同的概率为1/N，则 p2=1-1/N； 3次试验时，前两次结果肯定是不相同的，第3次与 前两次结果相同的概率为2/N，不同则 为1-2/N，根据条件概率有： p3=(1-1/N)(1-2/N) 类推： pn=(1-1/N)(1-2/N)(1-(n-1)/N) 取对数：lnpn=ln(1-1/N)+ln(1-2/N)+ln(1-(n-1)/N) 根据泰勒级数展开式： ln(1-x)=-(x+x2/2+x3/3+)-

23、x,第一章 简单密码,所以lnpn=ln(1-1/N)+ln(1-2/N)+ln(1-(n-1)/N) -(1/N+2/N+(n-1)/N) =-(1+2+n-1)/N =-n(n-1)/2N -n2/2N p=pne-n(n-1)/2N p=1-p1-e-n(n-1)/2N n次实验后至少2次结果相同的概率p1-e-n(n-1)/2N另外：要使得p1/2，则pln2 ,第一章 简单密码,作业： (1)为移位密码加密的消息解密： YRQ QEFP BUXJMIB FP IBPP BXPV (2)求-1000模88的约简。 (3)求29模100的乘法逆。 (4)已知明文攻击： Ea,b(3)=5

24、且Ea,b(6)=7，求解密密钥。 (5)求gcd(1112,1544)，并将其表示成如下形式： 1112x+1544y (6)求1001模1234的乘法逆。,第一章 简单密码,古典密码的两大机制： 代替密码：字母表范围内替换； 换位密码：在消息内变换字母的位置。2.1代替密码 1.描述 密钥是字母表的任意组合，有一个明密对应表； 密钥空间巨大：26!； 单表代替密码的两个特例：移位密码和仿射密码。 2.举例 首先选加密表；为了便于记忆，协商一个密钥： DO YOU LIKE THIS BOOK 去掉重复字母，再进行补充，形成加密表：,abcdefghijklmnopqrstuvwxyz DO

25、YULIKETHSBACFGJMNPQRVWXZ,第二章 代替与换位,第二章 代替与换位,2.2 换位密码 1.机制：单个字符不变而位置改变。 如将文本翻转：明文 computersystems 密文 SMETSYSRETUPMOC 2.特点： (1)密文长度与明文长度相同； (2)唯密文攻击可能得到多种不同的破译结果； 如 keeppeek；liveevilvile 3.分组换位密码 针对固定大小的分组进行操作。 举例：明文 can you understand (1)列换位法 设密钥k=4，将明文进行分组排列,密文： CODTAUEANURNYNSD,明文： canyouunderstan

26、d,明文：canyouunderstand,1 2 3 4,1 2 3 4,第二章 代替与换位,按列 读出,t y p e,密文： YNSDNURNCODTAUEA,明文： canyouunderstand,明文：canyouunderstand,1 2 3 4,3 4 2 1,YNSD NURN CODT AUEA,(2)密钥为字符串type,第二章 代替与换位,(3)矩阵换位法：置换矩阵作为密钥,明文：canyouunderstand,c a n y o u u n d e r s t a n d,n c y a u o n u r d s e n t d a,密文：NCYAUONURDS

27、ENTDA,按置换矩阵的阶4分组,c a n y o u u n d e r s t a n d,N C Y A U O N U R D S E N T D A,明文：canyouunderstand,解密置换矩阵：,说明：,第二章 代替与换位,第二章 代替与换位,2.3 频率攻击,1.原理：利用自然语言的频率攻击 字母出现的频率有规律： e:11.67 t:9.53 o:7.81 a:7.73 the:4.65 to:3.02 of:2.61 and:1.85 2.应用：对古典密码进行唯密文攻击。,3.举例：对仿射密码的攻击 密文：JFFGJFDMGFSJHYQHTAGHQGAFDCCFP

28、统计字母出现的次数： F6 G4 H3 J3 猜测：e(4)F(5) t(19)G(6) 则有：Ea,b(e)=F Ea,b(t)=G,第二章 代替与换位,Ea,b(x)=(7x+3)%26,解密函数为：E15,7(x)=(15x+7)%26,解密后的明文为： meet me after midnight in the alley,第二章 代替与换位,4.举例：对代替密码的攻击 KOS BMKKBS ISS YFSJ NFK BMES KOS,IDY IFP KF JSS MK.,e,ee,e,e,ee,t,t,t,tt,o,o,o,o,n,i,i,i,l,k,b,b,s,s,d,d,b,a,

29、y,分析：由ESROL得到er,s,o,l或re,s,o,l,loser 或 sorel,那么：由VIERD得到drive或irevd所以比较合理的明文是： loser drive,5.举例：对换位密码的攻击 ESROL VIERD,第二章 代替与换位,作业：,(1)解密由仿射密码加密的密文： VCLLCP BKLC LJKX XCHCP(2)解密用简单换位密码加密的密文： EAGGAR DAIREP,3.1 群 1.二元运算 定义：设s为集合，函数f:sss称为s上的二元运算或代数运算。满足： 可计算性：s中任何元素都可以进行这种运算； 单值性：运算结果唯一； 封闭性：s中任何两个元素运算结

30、果都属于s。 2.群的定义 定义：设是代数系统，为G上的二元运算，如果运算是可结合的，则称半群。 若为半群，并且二元运算存在单位元eG，则称为幺半群； 若为半群，并且二元运算存在单位元eG，G中的任何元素x都有逆元x-1G，称为群，简记为G。,第三章 置 换,举例： (1)是群，其中Z为整数集合，+是普通的加法，单位元是0，整数x的逆元是-x。 (2)是群，Z6=0,1,2,3,4,5，为模6加法。显然满足结合律，单位元是0；由于15=0，24=0，33=0，所以1和5互为逆元，2和4互为逆元，3和0的逆元仍然是3和0。 3.群中元素的阶 定义：设是群，aG，nZ，则a的n次幂为 e n=0

31、an= an-1a n0 (a-1)m n中，30=0，35=15，3-5=-15 在群中，20=0，23=0，2-3=0,第三章 置 换,阶的定义： (1)设是群，aG，使得等式ak=e成立的最小正整数k称为a的阶，记做|a|=k，a称为k阶元，若不存在这样的整数k，则a称为无限阶元。 例如： 在中，2和4是3阶元，3是2阶元， 1和5是6阶元，0是1阶元。 在中，0是1阶元，其他都是无限阶元。 (2)设为群，aG，且|a|=r。设k是整数，则ak=e当且仅当r|k。 (3)设为群，则群中任何元素a与其逆元a-1 具有相同的阶。,第三章 置 换,4.循环群和置换群 定义1：设为群，如果存在一

32、个元素aG，使得G=ak|kZ，则称G为循环群，记做G=，称a为生成元。若|a|=n，则G称为n阶循环群。 例如： 是循环群，其中Z6=0,1,2,3,4,5,， 为模6加法，生成元为1或5。 是循环群，生成元为1或-1。 是循环群，Zn=0,1,n-1,，生成 元为1。,第三章 置 换,定义3：设s=1,2,n，s上的n!个置换构成集合sn，则称sn与置换的复合运算构成的群为s上的n元对称群，的任意子群称为s上的n元置换群。,第三章 置 换,定义2：设s=1,2,n，s上的任何双射映射函数:ss称为s上的n元置换，记为：,3.2置换概念 1.置换 一个集合X的置换f定义为X到自身的一个双射函

33、数f。对应有n个元素的集合X，共有n!个置换。 问题：对于集合X，给定某个状态，经过多少次置换返回初始状态？ Sn=1,2,3,n-1,n表示n个元素的置换群 置换g为满足g(k)=ik的一个置换：,平凡置换e：没有移动任何元素的置换。 即对于所有的i，有e(i)=i。,置换与集合内容无关,第三章 置 换,2. 置换的合成或乘积 设g和h是两个置换，先应用h，再应用g， 记为：gh或gh 注意： gh hg 置换的合成满足结合律： (gh)k=g(hk)3. 逆置换 对于任意置换g，存在一个逆置换g-1，满足： gg-1=g-1g=e4. 图表记法 用来计算两个置换的乘积。如：,第三章 置 换

34、,5. 循环 最简单的置换是不同长度的循环。 一个k循环满足： f(i1)=i2, f(i2)=i3 , f(ik-1)=ik, f(ik)=i1，对于任意j(i1,i2,ik)，有f(j)=j。 举例：,则：,可见：gh hg，具有不可交换性。,记作：(i1,i2,ik),(1 2),(1 3),第三章 置 换,6. 结论 (1)如果g是一个k循环，那么gk=e。,注意：一个k循环有k种表示法。比较： (1 2 3)与(1 3 2),(1 2 3)= (2 3 1)= (3 1 2),如：,则：,即：对某个集合应用g操作k次，不会对集合产生 任何影响。,第三章 置 换,(2)置换的阶 是置换

35、被多次应用后却不产生任何实际影响所需要的重复次数。 若置换g是一个k循环，则有gk=e，g的阶为k。,(3)不相交的循环 若g=(i1,ik)和h=(j1,jl)分别为k循环和l循环，且i1,i2,ik和j1,j2,jl是不相交的列表，则有： gh=hg 这样的循环g和h称为不相交的循环。,第三章 置 换,一个置换g的阶k=不相交循环分解中各循环长度的最小公倍数。,如：,思考：如果一副50张的牌洗得好，重复洗8次后所 有的牌将返回初始位置。,阶为4,(4) 置换的不相交循环分解 任何置换都可以表示为不相交循环的乘积，并且本质上只有这一种表示方法。,=(1 4 5 7)(2 3)(6),第三章

36、置 换,3.3 切牌 最简单的切牌：选择一个随机点把一副牌一分为二，然后交换两部分。 n张牌：0,1,n-1 i+1,n-1,0,1,i 切牌过程为：fi(x)=(x+n-i-1)%n 如：n=6,i=1 0,1,2,3,4,5 2,3,4,5,0,1 置换过程为：,f1(x)=(x+4)%6,第三章 置 换,若n张牌的位置编号为： 1,2,n-1,n i+1,n-1,n,1,i则切牌过程为：fi(x)=(x+n-i-1)%n+1,第三章 置 换,如：n=6,i=2 1,2,3,4,5,6 3,4,5,6,1,2置换过程为：,f1(x)=(x+3)%6+1,2n张牌： 1,2,n,n+1,2n

37、-1,2n 两半交错：n+1,1,n+2,2,2n-1,n-1,2n,n 1,n+1,2,n+2,n-1,2n-1,n,2n命题：对一副有2n张牌1,2,2n-1,2n的完美快速 洗牌过程为：f(x)=(2x)%(2n+1)推论：若e为2模2n+1的阶，即e是满足2e=1 mod 2n+1的最小正整数。那么对一副有2n张牌经 过e次洗牌后，所有的牌都第一次返回到它们 的起始位置。,不好的洗牌,完美洗牌,第三章 置 换,3.4洗牌,然后按列读取这些数： 0,n,2n,mn-n,1,n+1,2n+1,mn-n+1,mn-1对于数x，行：x/n 列：x%n,3.5 分组交错 给定正整数m和n，针对m

38、n个元素，一个mn分组交换的置换定义为： 按行将mm个数据写成mn的矩阵的形式,第三章 置 换,然后按列读取这些数： 0,4,8,1,5,9,2,6,10,3,7,11对应的置换过程为：,例：12个数据 0,1,2,3,4,5,6,7,8,9,10,11， 进行34分组交错。,对应的循环分解为：,数据,置换位置,阶为5,按4行3列写出,第三章 置 换,命题：忽略两个不动点0和mn-1，mn分组交错 对集合1,2,3,mn-2的作用是： x (mx)%(mn-1)举例：36分组交错,3x%17,3x%17,分析：快速洗牌，去掉两个不动点 完美的快速洗牌： x (2x)%(2n+1),第三章 置

39、换,作业： (1)计算乘积,第三章 置 换,用不相交循环的乘积表示上述的结果，并确定阶。(2)S5中任意元素的最大阶是多少？S14呢？(3)确定对一副20张牌的完美快速洗牌的循环分解。(4)找出35的分组交错置换的循环分解。,第四章 现代对称密码,香农提出的现代密码设计准则： Kerchhoff原则：系统的安全性不依赖于对密文或 加密算法的保密，而依赖于密钥。 惟一需要保密的是密钥； 决定了古典密码学与现代密码学。 一个好的密码将融合混淆和扩散 混淆：混淆明文的不同部分； 扩散：对攻击者隐藏一些语言的局部特征； 现代密码将结合换位和代替： 代替密码在混淆上是有效的； 换位密码扩散性较好。,4.

40、1 数据加密标准DES(Data Encryption Standard) 1976年被采纳作为联邦标准，并授权在非密级的政府通信中使用，应用广泛。 DES是一个分组加密算法，对称密码，64位分 组，密钥长度为64位(实际长度为56位)。,第四章 现代对称密码,现代密码算法的特点： 只要保证密钥安全，就能保证加密信息的安全。对称密码算法：很好地融合了混淆和扩散； DES、AES、IEDA、RC6等非对称密码算法：基于数学难题； RSA、ECC、ElGamal等,DES的整个算法是公开的，系统的安全性靠密钥保证。算法包括三个步骤：初始置换IP、16轮迭代的乘积变换、逆初始变换IP-1。 1.初始

41、置换IP 初始置换IP可将64位明文M=m1m2m64的位置进行置换，得到乱序的64位明文组M0=m58m50m7。 2. 逆初始置换IP-1 逆初始置换IP-1将16轮迭代后的64比特数据的各字节按列写出，将前四列插到后四列中，再对各列进行逆序，然后将元素按行读出即可得到输出的密文组。 IP和IP-1的作用主要是打乱输入的ASCII码字划分关系，并将明文校验码变成IP输出的一个字节。,第四章 现代对称密码,第四章 现代对称密码,第四章 现代对称密码,第四章 现代对称密码,【举例】设64位明文M为：00000000 11111111 01010101 00010001 10001000 110

42、01100 00110011 10101010则经过IP置换后的M0为：00100110 01001110 00100110 01001110 10110010 11000010 10110010 11000010转换过程如下：,第四章 现代对称密码,3. 乘积变换 乘积变换是DES算法的核心部分。将经过IP置换后的数据分成32位的左右两组，在迭代过程中彼此左右交换位置。每次迭代时只对右边的32位进行一系列的加密变换，然后把左边的32位与右边得到的32位逐位进行异或操作，作为下一轮迭代时左边的段。,迭代公式为： Li=Ri-1，Ri=Li-1f(Ri-1,ki)：按位异或操作运算符，即按位作模

43、2相加运算。运算规则为：10=1，01=1，00=0，11=0,f的功能是将32比特的数据经过选择扩展运算 E、密钥加密运算、选择压缩运算S和置换运算P转换为32比特的输出。,第四章 现代对称密码,第四章 现代对称密码,(1)选择扩展运算E 选择扩展运算下可将输入的32比特Ri-1扩展成48位的输出。令s表示E原输入数据比特的下标，则E的输出是将原下标s为0或1(模4)的各比特重复一次得到的，实现数据扩展。,第四章 现代对称密码,(2) 密钥加密运算 密钥加密运算将48比特的子密钥ki与选择扩展运算E输出的48比特数据进行按位异或运算。【举例】设32比特数据Ri-1为 00000000 111

44、11111 00000000 11111111，48比特子密钥ki为 00000000 11111111 01010101 10101010 11001100 10001000，求Ri-1经过选择扩展运算E后与子密钥ki异或后的结果。,第四章 现代对称密码,16个子密钥ki的产生： 64比特初始密钥k经过换位函数PC-1将位置号为8,16,24,32,40,48,56和64的8位奇偶位去掉并换位；换位后的数据分为2组，经过循环左移位LSi和换位函数PC-2变换后得到每次迭代加密用的子密钥ki。,第四章 现代对称密码,第四章 现代对称密码,LSi表示求子密钥ki时将Ci-1和Di-1进行循环左移

45、，其移位位数为：,(3)选择压缩运算 选择压缩运算可将密钥加密运算后的48比特数据从左至右分成8组，每组为6比特，并行迭入8个S盒后压缩成32比特输出。每个S盒的输入为6比特，输出为4比特，以完成压缩变换。 对于某个S盒Si，假设其输入为b1b2b3b4b5b6， 在Si表中找到b1b6行，b2b3b4b5 列的整数，转换 为4位二进制就是输出的4比特数据。,第四章 现代对称密码,第四章 现代对称密码,第四章 现代对称密码,【举例】设S5的输入为b1b2b3b4b5b6=110110。 则(b1b6)2=(10)2=2，(b2b3b4b5)2=(1011)2=11在S5中找到行为2，列为11的

46、数据5转换为4位二进制为0101，所以S5的输出为0101。 (4)置换运算P S1S8盒的输出合成32比特数据后，用换位表p进行置换，得到的32比特数据就是f(Ri-1,ki)的输出。,第四章 现代对称密码,DES的解密算法和加密算法相同，只是在解密 过程中将子密钥的顺序颠倒。 DES的出现在密码史上是个创举。以前任何设计者对于密码体制细节都是严加保密的。自公布以来，它一直活跃在国际保密通信的舞台上，成为商用保密通信和计算机通信的最常用的加密算法。由于DES的安全性完全依赖于密钥，而其64位的密钥太短，因而出现了许多DES的改进算法，如三重DES、分组反馈连接式DES以及密码反馈模式DES等

47、。随着新的攻击手段和改进的加密算法的不断出现，DES也许将完成它的历史使命。 高级加密标准AES评选于2000年10月结束，Rijdael算法为AES的唯一算法。,第四章 现代对称密码,4. DES的安全性 (1)差分分析 1990年Biham和Shamir提出差分密码分析。是一种比穷举攻击有效的选择明文的攻击方法。 差分分析的攻击方法是针对DES和其他类似的有固定S盒的算法。DES的S盒恰好最适宜于抗差分分析。最佳差分分析的总结表明对16轮DES的攻击需选择明文247，分析的复杂性为237。 (2)线性密码分析 Mitsuru Matsui提出了线形密码分析。使用线性近似值来逼近分组密码的操

48、作。攻击完整的16轮DES，当已知明文的平均数为243时，可得到密钥，是最有效的攻击DES的方法。,第四章 现代对称密码,第四章 现代对称密码,4.2 序列密码 1.随机数生成器,(1)任意由确定过程生成的随机数序列，从实际意义上讲都不是随机的。 (2)pRNG(pseudo-random number generators):伪随机数发生器，其典型应用是一次一密乱码本。 (3)一个pRNG要求：在不知道密钥的情况下，由随机数序列中已知部分推测下一个数是“困难”的。 (4)伪随机数序列的周期：要求尽可能大 对于序列s0,s1,s2,若存在p，使得si+p=si 则称它为周期为p的周期序列。,第

49、四章 现代对称密码,2.线性同余发生器 最为广泛使用的伪随机数产生器。 (1)产生方式 sn+1=(asn+b) mod m Zm 其中0am,0bm，初值s0称为种子。 (2)分析 a,b,m的取值是产生高质量随机数的关键。 取a=2,b=7,m=17，则 sn+1=(2sn+7) mod 17 取种子s0=1，生成的伪随机序列为：,1,9,8,6,2,11,12,14,1,9,8,6,2,11,12,14,1,9,序列的周期为8，而且Z17中只有8个元素出现。,第四章 现代对称密码,取a=7,b=1,m=17,则sn+1=(7sn+1) mod 17 取种子s0=1，生成的伪随机序列为：,

50、1,8,6,9,13,7,16,11,10,3,5,2,15,4,12,0,1,8,序列的周期为16。(14未出现),取种子s0=14，则序列为：,14,14,14,14,(3)线性同余发生器的周期 定理1：只要种子是模p非零的，则线性同余发生器si+1=asi mod p的周期为a在乘法群Z/p中的阶l。 而且，l|p-1，且当a为模p的本原根时，l=p-1。,定理2：线性同余发生器si+1=asi+b mod p的周期为a在Zp中的阶，只要种子s0不等于坏种子 sbad=-(a-1)-1b mod p举例：求sn+1=7sn+2 mod 13的坏种子sbad。,第四章 现代对称密码,(4)