信息安全数学基础教学资料.ppt

《信息安全数学基础教学资料.ppt》由会员分享，可在线阅读，更多相关《信息安全数学基础教学资料.ppt（211页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息安全数学基础中南大学信息科学与工程学院计算机系 段桂华2010年年9月月网络信息的安全威胁网络信息的安全威胁 网上犯罪形势不容乐观；网上犯罪形势不容乐观；有害信息污染严重；有害信息污染严重；网络病毒的蔓延和破坏；网络病毒的蔓延和破坏；网上黑客无孔不入；网上黑客无孔不入；机要信息流失与信息间谍潜入；机要信息流失与信息间谍潜入；网络安全产品的自控权；网络安全产品的自控权；信息战的阴影不可忽视。信息战的阴影不可忽视。引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月中南大学信息科学与工程学院计算机系 段桂华2010年年9月月中南大学信息科学与工程学院计算机系 段桂华2010年年9

2、月月中南大学信息科学与工程学院计算机系 段桂华2010年年9月月网络安全体系的五类服务网络安全体系的五类服务访问控制服务访问控制服务：根据实体身份决定其访问权限根据实体身份决定其访问权限；身份鉴别服务身份鉴别服务：消息来源确认、防假冒、证明你消息来源确认、防假冒、证明你 是否就是你所声明的你；是否就是你所声明的你；保密性服务保密性服务：利用加密技术将消息加密，非授权利用加密技术将消息加密，非授权 人无法识别信息人无法识别信息；数据完整性服务数据完整性服务：防止消息被篡改，证明消息与防止消息被篡改，证明消息与 过程的正确性过程的正确性；防抵赖服务防抵赖服务：阻止你或其他主体对所作所为的进阻止你或

3、其他主体对所作所为的进 行否认的服务，可确认、无法抵赖行否认的服务，可确认、无法抵赖。引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月引 言解决方法：解决方法：加密加密如何实现保密性？如何实现保密性？密码分析密码分析公共网络公共网络AliceBob加密加密密钥密钥解密解密密钥密钥Eve中南大学信息科学与工程学院计算机系 段桂华2010年年9月月引 言解决方法：解决方法：数字摘要数字摘要如何实现完整性？如何实现完整性？无法篡改无法篡改z消息篡改消息篡改公共网络公共网络AliceBobm,zm,zz=hk(m)y=hk(m)Eve如果如果yzm被篡改被篡改中南大学信息科学与工程学

4、院计算机系 段桂华2010年年9月月引 言解决方法：解决方法：数字签名数字签名如何实现不可否认性？如何实现不可否认性？否认否认公共网络公共网络AliceBobTrent谁是正确的？谁是正确的？举报举报中南大学信息科学与工程学院计算机系 段桂华2010年年9月月引 言解决方法：解决方法：密码技术密码技术公共网络公共网络AliceBob假冒假冒Eve 身份鉴别：身份鉴别：就是确认实体是它所声明的，身份鉴别服就是确认实体是它所声明的，身份鉴别服务提供关于某个实体身份的保证，以对抗假冒攻击。务提供关于某个实体身份的保证，以对抗假冒攻击。如何鉴别通信对象的身份？如何鉴别通信对象的身份？中南大学信息科学与

5、工程学院计算机系 段桂华2010年年9月月本课程的相关知识点本课程的相关知识点简单的密码学基础：简单的密码学基础：密码技术是信息安全的核心技术；密码技术是信息安全的核心技术；需要掌握一些密码学基础知识。需要掌握一些密码学基础知识。相关的数学知识：相关的数学知识：密码技术的实现依赖于数学知识；密码技术的实现依赖于数学知识；掌握密码技术涉及的相应数学基础知识点。掌握密码技术涉及的相应数学基础知识点。参考教材：参考教材：(1)密码学导引密码学导引,机械工业出版社机械工业出版社,Paul Garrett 著著,吴世忠等译；吴世忠等译；(2)信息安全数学基础信息安全数学基础,武汉大学出版社武汉大学出版社

6、,李继国等李继国等 主编。主编。引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月什么是密码技术？什么是密码技术？窃听窃听公共网络公共网络AliceBobEve篡改篡改伪造伪造加密加密密钥密钥解密解密密钥密钥密文密文密密码码学学是是一一门门古古老老而而深深奥奥的的学学科科,包包括括密密码码编编码码学和密码分析学学和密码分析学;通信双方按照某种约定将消息的原形隐藏通信双方按照某种约定将消息的原形隐藏。密码系统密码系统:明文明文,密文密文,加解密算法加解密算法,密钥密钥。引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月密码学的起源与发展密码学的起源与发展三个阶段：

7、三个阶段：1949年之前：密码学是一门艺术；年之前：密码学是一门艺术；19491975年：密码学成为科学；年：密码学成为科学；1976年以后：密码学的新方向公钥密码学。年以后：密码学的新方向公钥密码学。1949年之前年之前(手工阶段的初级形式手工阶段的初级形式)隐写术：隐形墨水、字符格式的变化、图像；隐写术：隐形墨水、字符格式的变化、图像；举例：举例：芦花丛中一扁舟，俊杰俄从此地游；芦花丛中一扁舟，俊杰俄从此地游；义士若能知此理，反躬难逃可无忧。义士若能知此理，反躬难逃可无忧。258 71539 258 314697 258 71539 258 314697 314697314697 1535

8、8 24862 17893 15358 24862 17893 引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月19491975年年(机械阶段机械阶段)：现代密码出现：现代密码出现1949年年香农香农Shannon提出提出“保密系统信息理论保密系统信息理论”；提出：数据的安全基于密钥而不是密码算法。提出：数据的安全基于密钥而不是密码算法。1976年以后年以后(计算机阶段计算机阶段)：公钥密码诞生：公钥密码诞生1976年年Diffie&Hellman的的“New Directions in Cryptography”提出了不对称密钥密码；提出了不对称密钥密码；1977年年Riv

9、est,Shamir&Adleman提出了提出了RSA公钥算法；公钥算法；90年代出现椭圆曲线年代出现椭圆曲线ECC等其他公钥算法。等其他公钥算法。引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月对称密钥密码算法进一步发展对称密钥密码算法进一步发展1977年年DES正式成为标准；正式成为标准；80年代出现年代出现“过渡性过渡性”的的“post DES”算法，如算法，如IDEA、RCx、CAST等；等；90年代对称密钥密码进一步成熟，年代对称密钥密码进一步成熟，Rijndael、RC6、MARS、Twofish、Serpent等出现；等出现；2001年年Rijndael成为成为

10、DES的替代者的替代者AES。2004年年6月美国月美国NIST提出最新信息加密技术提出最新信息加密技术-量子密码。量子密码。2004年山东大学王小云教授成功破解处理电子年山东大学王小云教授成功破解处理电子签名的签名的MD5。引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月密码算法的分类密码算法的分类按照保密的内容分按照保密的内容分受限制的算法：保密性基于保持算法的秘密。受限制的算法：保密性基于保持算法的秘密。基于密钥的算法：保密性基于密钥的保密。基于密钥的算法：保密性基于密钥的保密。Kerchoffs原则原则1883年年Kerchoffs第一次明确提出了编码的原则：第一次明

11、确提出了编码的原则：保密性完全依赖于密钥，算法应该公开。保密性完全依赖于密钥，算法应该公开。这一原则已得到普遍承认，成为判定密码强度的这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为衡量标准，实际上也成为古典密码古典密码和和现代密码现代密码的的分界线。分界线。引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月基于密钥的算法，按照密钥的特点分类：基于密钥的算法，按照密钥的特点分类：对称密码算法：对称密码算法：又称秘密密钥算法或单密钥算又称秘密密钥算法或单密钥算法，加密密钥和解密密钥相同，或可以容易地法，加密密钥和解密密钥相同，或可以容易地从一个推出另一个。从一个推

12、出另一个。特点：特点：加密速度快；密钥加密速度快；密钥管理复杂，主要用于加密信息。管理复杂，主要用于加密信息。非对称密钥算法：非对称密钥算法：又称公开密钥算法，加密密又称公开密钥算法，加密密钥和解密密钥不相同，而且很难从一个推出另钥和解密密钥不相同，而且很难从一个推出另一个。一个。特点：特点：密钥管理简单，但加密速度慢，密钥管理简单，但加密速度慢，用于加密会话密钥和用于数字签名。用于加密会话密钥和用于数字签名。实际网络应用中，常采用非对称密码来交换对实际网络应用中，常采用非对称密码来交换对称密码算法的密钥。称密码算法的密钥。引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月经典

13、的经典的古典密码古典密码算法主要有：算法主要有：代替密码：代替密码：将明文字符用另外的字符代替，典型的将明文字符用另外的字符代替，典型的有恺撒密码、仿射密码、维吉尼亚密码等；有恺撒密码、仿射密码、维吉尼亚密码等；换位密码：换位密码：明文的字母保持相同，但顺序打乱。明文的字母保持相同，但顺序打乱。经典的经典的现代密码现代密码算法有很多种，最通用的有：算法有很多种，最通用的有：DES：数据加密标准，对称密码算法，用于加密；数据加密标准，对称密码算法，用于加密；AES:高级加密标准，对称密码算法，用于加密；高级加密标准，对称密码算法，用于加密；引 言中南大学信息科学与工程学院计算机系 段桂华2010

14、年年9月月RSA：最流行的公钥密码算法，加密和数字签名；最流行的公钥密码算法，加密和数字签名；ECC：椭圆曲线密码，采用椭圆曲线密码，采用ElGamal算法，公钥密码算法，公钥密码算法，安全性高，密钥量小，灵活性好；算法，安全性高，密钥量小，灵活性好；DSA：数字签名算法，是数字签名的一部分，公钥数字签名算法，是数字签名的一部分，公钥密码算法，数字签名。密码算法，数字签名。MD5(SHA-1)：数字摘要算法，数字签名，保证消数字摘要算法，数字签名，保证消息的完整性。息的完整性。引 言中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 理论安全：理论安全：攻击者无论截获多少密文，都无法

15、攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。得到足够的信息来唯一地决定明文。Shannon用用理论证明：欲达理论安全，加密密钥长度必须理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，大于等于明文长度，密钥只用一次，用完即丢，即一次一密密码本，不实用。即一次一密密码本，不实用。实际安全：实际安全：如果攻击者拥有无限资源，任何密如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上

16、安全的或来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行。破译这个系统是计算上不可行。引 言密码系统的安全密码系统的安全中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 四种基本攻击类型：四种基本攻击类型：唯密文攻击：唯密文攻击：攻击者只有一些密文；攻击者只有一些密文；已知明文攻击：已知明文攻击：攻击者知道一些明文密文对；攻击者知道一些明文密文对；选择明文攻击：选择明文攻击：攻击者可以选择明文密文对；攻击者可以选择明文密文对；针对密钥的攻击：针对密钥的攻击：主要是针对公钥密码系统。主要是针对公钥密码系统。穷举攻击：穷举攻击：攻击者采用尝试方法穷举可能的密钥。攻击者

17、采用尝试方法穷举可能的密钥。当密钥空间较小时很有效。当密钥空间较小时很有效。字典攻击字典攻击是是 利用一些常用的单词进行组合。利用一些常用的单词进行组合。基本要求：基本要求：任何一种加密系统都必须能够对抗唯任何一种加密系统都必须能够对抗唯 密文攻击。密文攻击。目前的标准是：目前的标准是：一个密码系统应当能够对抗选择一个密码系统应当能够对抗选择 明文攻击。明文攻击。引 言密码系统的攻击密码系统的攻击中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第一章 简单密码经典的简单密码：经典的简单密码：移位密码、一次一密乱码本、仿射密码。移位密码、一次一密乱码本、仿射密码。1.1 移位密码移位

18、密码1.Caesar密码：密码：最简单的移位密码。最简单的移位密码。原理：原理：将消息中的每个字母前移将消息中的每个字母前移3位或者后位或者后 移移3位。位。举例：举例：all of gaul is devided into three parts DOO RI JDXO LU GLYLGHG LQWR WKUHH SDUWU2.移位密码：移位密码：改进改进Caesar密码：密码：发送方和接收方协商一个发送方和接收方协商一个密钥密钥k，1k25，代表移动位数。，代表移动位数。中南大学信息科学与工程学院计算机系 段桂华2010年年9月月3.攻击：攻击：穷举攻击：穷举攻击：25种可能的密钥种可能的

19、密钥(密钥空间密钥空间)；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|。第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月

20、举例：举例：-10%7：10%(-7)：-10%(-7)：4，因为-10=7(-2)+43，因为 10=-7(-1)+34，因为-10=-72+4注意：注意：任何整数模任何整数模m的约简都是非负数。的约简都是非负数。2.乘法逆乘法逆 n模模m的乘法逆的乘法逆t满足：满足：nt%m=1 记作：记作：t=n-1%m 举例：举例：2-1%5的值为：的值为：3-1%100的值为：的值为：3，因为 32%5=167，因为 673%100=1第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月4.乘法逆元的计算乘法逆元的计算 (1)穷举法：寻找满足条件的数。穷举法：寻找满足条件的数

21、。技巧：若技巧：若tn%m=-1，则则n-1%m=m-t。333%100=-1，所以所以3-1%100的值为的值为67。第一章 简单密码 3.命题命题 设设m0,1为整数，为整数，x与与m互素，则互素，则x有模有模m的的乘法逆元。特别地，满足表达式乘法逆元。特别地，满足表达式ax+bm=1的任意的任意整数整数a就是一个就是一个x模模m的乘法逆元。的乘法逆元。假如假如y是是x模模m的乘法逆元，对于的乘法逆元，对于y，若，若m|y-y，那么那么y也是也是x模模m的乘法逆元；反之亦然。的乘法逆元；反之亦然。中南大学信息科学与工程学院计算机系 段桂华2010年年9月月(2)欧几里德算法欧几里德算法：举

22、例：举例：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-13231 -1 -1 3 3-13 0 11 -70 11 -10 11 -20 11 -4100 2310=所以：所以：3100-1323=1第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月1.3 欧几里得算法欧

23、几里得算法 用以寻找两个整数用以寻找两个整数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=12.寻找整数寻找整数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(6

24、14-1513)=-193614+231513最大公因子为最大公因子为1 1193614+231513=1第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月2.乘法逆元的计算乘法逆元的计算 两个整数两个整数x和和y x-yq1=r1 x1-y1q2=r2 x2-y2q3=r3 xn-1-yn-1qn=0 xn yn结论：结论：当当x和和y互素时，互素时，gcd(x,y)为为1，即可得到，即可得到x-1%y为为a，y-1%x为为b。第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月3.举例举例 所以：所以：21-1%25的结果为的结果为6。例例

25、2：求：求1234-1%4321 例例1：求：求21-1%25 解：解：25-121=4 21-54=1 4-14=0 第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月3.命题：命题：(1)给定一非零整数给定一非零整数m和任意整数和任意整数n，存在唯一的，存在唯一的 整数整数q和和r，使得，使得0r|m|且且n=qm+r(2)设设n和和N为两个整数，对某个整数为两个整数，对某个整数k有有N=kn，则对任意整数则对任意整数x有：有：(x%N)%n=x%n1.3 一次一密乱码本一次一密乱码本OTP 1.思想：思想：密钥与消息一样长，且只能使用一次。密钥与消息一样长，且只

26、能使用一次。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)第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月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 VR(17)=(n(13)+e(4)%26F(5)=(r(17)+o(14)%264.特点：特点：密

27、钥的产生与分发管理复杂；密钥的产生与分发管理复杂；对称密码；对称密码；多表代替密码：明文中不同位置的字母采用的加多表代替密码：明文中不同位置的字母采用的加 密密钥不同。密密钥不同。第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月1.4 仿射密码仿射密码 1.思想：思想：对移位密码进行改进，扩大密钥空间。对移位密码进行改进，扩大密钥空间。2.原理：原理：加密：加密：Ea,b(x)=(ax+b)%26 0a,b 25 解密：解密：Da,b(y)=3.特点：特点：(1)当当a=1时为移位密码；时为移位密码；(2)加密密钥为加密密钥为(a,b)；解密密钥为；解密密钥为(a-

28、1,-a-1b)；(3)单表代替密码；单表代替密码；(4)对称密码：由加密密钥可以推导出解密密钥；对称密码：由加密密钥可以推导出解密密钥；第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 (5)密钥空间：由于密钥空间：由于a-1必须存在，所以可能的密钥数必须存在，所以可能的密钥数 为为1226-1=311个。个。第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月4.攻击方法：攻击方法：穷举攻击：穷举攻击：尝试尝试311个可能的密钥。个可能的密钥。选择明文攻击：选择明文攻击：Ea,b(0)=(a0+b)%26 Ea,b(1)=(a1+b)%2

29、6 已知明文攻击：已知明文攻击：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)%26b=Ea,b(0)a=(Ea,b(1)-b)%26第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 举例：举例：已知明文：已知明文：meet me at midnight 假设密文：假设密文：HNNS HN DS HXEQXFOS (1)选择明文攻击选择明文攻击 攻击者选择：攻击者选择：a(0)D(3)d(3)E(4)第一章

30、 简单密码 Ea,b(0)=(a0+b)%26 Ea,b(3)=(a3+b)%263=b%264=(3a+b)%26b=3a=3-1%26=9加密密钥加密密钥a-1%26=3-a-1b=-33%26=17解密密钥解密密钥中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 (2)已知明文攻击已知明文攻击 攻击者获得：攻击者获得：m(12)H(7)h(7)O(14)Ea,b(12)=(a12+b)%26 Ea,b(7)=(a7+b)%267=(12a+b)%2614=(7a+b)%26a=(-75-1)%26=9b=(14-79)%26=3加密密钥加密密钥第一章 简单密码中南大学信息科学

31、与工程学院计算机系 段桂华2010年年9月月第一章 简单密码1.5 Vigenere密码密码 1.特点：特点：具有相对较大的密钥空间；具有相对较大的密钥空间；对称密码；多表代替密码；对称密码；多表代替密码；有周期性的弱点：若两个字符出现的间隔是密钥有周期性的弱点：若两个字符出现的间隔是密钥长度的倍数，则它们将以同样的方法加密。长度的倍数，则它们将以同样的方法加密。2.加密和解密的原理：加密和解密的原理：(1)密钥是一个字符序列：密钥是一个字符序列：k=(k0,k1,km-1)；明文明文x=(x0,x1,xN)被分成长度为被分成长度为m的段。的段。(2)加密函数：加密函数：Ek(x0,x1,xN

32、)=(y0,y1,yN)yi=(xi+ki%m)%26 解密函数：解密函数：Dk(y0,y1,yN)=(x0,x1,xN)xi=(yi-ki%m)%26中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第一章 简单密码3.多轮加密多轮加密(3)举例：举例：明文m=meet me in the alley after midnight 密钥k=goph er go phe rgoph ergop hergophe 密文c=SSTA QV OB IOI RRZTF EWZSG TMUTWVOX21217 20 若一个明文使用密钥长度为若一个明文使用密钥长度为m的维吉尼亚密码加的维吉尼亚密

33、码加密，得到的密文再用长度为密，得到的密文再用长度为n的密钥加密，其结果与的密钥加密，其结果与用长度为用长度为lcm(m,n)的维吉尼亚密码加密的结果一样。的维吉尼亚密码加密的结果一样。若若m,n互素，则互素，则lcm(m,n)=mxn，密钥长度很大。，密钥长度很大。中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第一章 简单密码1.6最小公倍数最小公倍数lcm和最大公约数和最大公约数gcd 1.定义定义 对于两个整数对于两个整数d,n，若，若d整除整除n，或者说，或者说d是是n的的一个因子，记作：一个因子，记作：d|n 设设m,n是两个非是两个非0的整数，则最大公约数的整数，则最

34、大公约数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,n)|N；中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第一章 简单

35、密码3.素数素数 素数素数p是那些不存在因子是那些不存在因子d的整数的整数1d p1/2；定理：定理：每一个正整数都可以分解为素数的乘积，每一个正整数都可以分解为素数的乘积，而且这种分解是唯一的。而且这种分解是唯一的。12=22x3 35=5x7 (1)对于每一个素数对于每一个素数p，整除，整除gcd(m,n)的的p的方幂，的方幂，是既整除是既整除m又整除又整除n的的p的方幂的最小值。的方幂的最小值。(2)两个方幂中较大的一个便组成了最小公倍数。两个方幂中较大的一个便组成了最小公倍数。举例：举例：3960=23x32x5x11 400=24x52 则：则：gcd(3960,400)=23x5=

36、40 lcm(3960,400)=24x32x52x11=39600中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第一章 简单密码1.7 生日攻击生日攻击 1.命题命题 在实验在实验x中，不同结果中，不同结果x1,x2,xn的概率分别为的概率分别为p(x1)=p1,p(xn)=pn。集合。集合A为样本空间为样本空间x1,xn的一个子集，且有的一个子集，且有p(A)=p。设。设0kN，则，则N次实验次实验中中A恰好出现恰好出现k次的概率为：次的概率为：举例举例：投币。假设一枚公平的硬币朝上或朝下的投币。假设一枚公平的硬币朝上或朝下的 几率是相等的，且每次投币是独立的。几率是相等的，

37、且每次投币是独立的。分析：分析：记录一个记录一个n次投掷的过程：次投掷的过程：2n任何单个序列出现的概率是任何单个序列出现的概率是1/2nn次投掷恰好有次投掷恰好有k次正面朝上的概率是：次正面朝上的概率是：中南大学信息科学与工程学院计算机系 段桂华2010年年9月月10次投掷中：次投掷中：恰好恰好5次正面朝上的概率为：次正面朝上的概率为：252/10241/4 6-4或者或者4-6组合的概率是：组合的概率是：420/10242/52.生日攻击生日攻击 设设=1,2,N为所有原子事件的样本空间，为所有原子事件的样本空间，p(i)=1/N。n次实验后至少次实验后至少2次结果相同的概率至次结果相同的

38、概率至少为：少为：1-e-n(n-1)/2N。因此，对于。因此，对于 出现两次相同结果的概率至少为出现两次相同结果的概率至少为1/2。第一章 简单密码证明：证明：先计算出没有两种完全相同结果出现的概先计算出没有两种完全相同结果出现的概 率率p，则出现两次相同结果的概率，则出现两次相同结果的概率p=1-p。中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 1次试验时，次试验时，p1=1；2次试验时，次试验时，两次结果相同的概率为两次结果相同的概率为1/N，则，则 p2=1-1/N；3次试验时，次试验时，前两次结果肯定是不相同的，第前两次结果肯定是不相同的，第3次与次与 前两次结果相同

39、的概率为前两次结果相同的概率为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+)-x第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月所以所以lnpn=ln(1-1/N)+ln(1-2/N)+ln(1-(n-1)/N)-(1/N+2/N+(n-1)/N)=-(1+2+n

40、-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，则，则p1/2 lnpln1/2 -n2/2Nln1/2 -n2/2Nln2 第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月作业：作业：(1)为移位密码加密的消息解密：为移位密码加密的消息解密：YRQ QEFP BUXJMIB FP IBPP BXPV (2)求求-1000模模88的约简。的约简。(3)求求29模模100的乘法逆

41、。的乘法逆。(4)已知明文攻击：已知明文攻击：Ea,b(3)=5且且Ea,b(6)=7，求解密密钥。，求解密密钥。(5)求求gcd(1112,1544)，并将其表示成如下形式：，并将其表示成如下形式：1112x+1544y (6)求求1001模模1234的乘法逆。的乘法逆。第一章 简单密码中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 古典密码的两大机制：古典密码的两大机制：代替密码：代替密码：字母表范围内替换；字母表范围内替换；换位密码：换位密码：在消息内变换字母的位置。在消息内变换字母的位置。2.1代替密码代替密码 1.描述描述 密钥是字母表的任意组合，有一个明密对应表；密钥

42、是字母表的任意组合，有一个明密对应表；密钥空间巨大：密钥空间巨大：26!；单表代替密码的两个特例：移位密码和仿射密码。单表代替密码的两个特例：移位密码和仿射密码。2.举例举例 首先选加密表；为了便于记忆，协商一个密钥：首先选加密表；为了便于记忆，协商一个密钥：DO YOU LIKE THIS BOOK 去掉重复字母，再进行补充，形成加密表：去掉重复字母，再进行补充，形成加密表：abcdefghijklmnopqrstuvwxyz DOYULIKETHSBACFGJMNPQRVWXZ第二章 代替与换位中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第二章 代替与换位2.2 换位密码换

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

44、文进行分组排列中南大学信息科学与工程学院计算机系 段桂华2010年年9月月canyouunderstand按列按列读出读出密文：密文：CODTAUEANURNYNSDCANYOUUNDERSTAND按行按行读出读出明文：明文：canyouunderstand明文：明文：canyouunderstand按按4 4个字符一行分组排列个字符一行分组排列按按4 4个字符一列分组排列个字符一列分组排列1 2 3 41 2 3 4第二章 代替与换位中南大学信息科学与工程学院计算机系 段桂华2010年年9月月按列按列 读出读出t y p ecanyouunderstand密文：密文：YNSDNURNCODT

45、AUEACANYOUUNDERSTAND按行按行读出读出明文：明文：canyouunderstand明文：明文：canyouunderstand按按4 4个字符一行分组排列个字符一行分组排列按type(3,4,2,1)填入1 2 3 43 4 2 1 YNSD NURN CODT AUEA(2)密钥为字符串密钥为字符串type1234按密钥长度分组按密钥长度分组第二章 代替与换位中南大学信息科学与工程学院计算机系 段桂华2010年年9月月(3)矩阵换位法：置换矩阵作为密钥矩阵换位法：置换矩阵作为密钥明文：明文：canyouunderstandc a n y o u u n d e r s t

46、a n dn c y a u o n u r d s e n t d a密文：密文：NCYAUONURDSENTDA按置换矩阵的阶按置换矩阵的阶4 4分组分组c a n y o u u n d e r s t a n dN C Y A U O N U R D S E N T D A明文：明文：canyouunderstand解密置换矩阵：解密置换矩阵：说明：说明：第二章 代替与换位中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第二章 代替与换位2.3 频率攻击频率攻击1.原理：原理：利用自然语言的频率攻击利用自然语言的频率攻击 字母出现的频率有规律：字母出现的频率有规律：e:11

47、.67 t:9.53 o:7.81 a:7.73 e:11.67 t:9.53 o:7.81 a:7.73 the:4.65 to:3.02 of:2.61 and:1.85 the:4.65 to:3.02 of:2.61 and:1.85 2.应用：应用：对古典密码进行唯密文攻击。对古典密码进行唯密文攻击。3.举例：举例：对仿射密码的攻击对仿射密码的攻击 密文：密文：JFFGJFDMGFSJHYQHTAGHQGAFDCCFP 统计字母出现的次数：统计字母出现的次数：F6 G4 H3 J3 猜测：猜测：e(4)F(5)t(19)G(6)则有：则有：Ea,b(e)=F Ea,b(t)=G 中南

48、大学信息科学与工程学院计算机系 段桂华2010年年9月月第二章 代替与换位 Ea,b(4)=(a4+b)%26 Ea,b(19)=(a19+b)%265=(4a+b)%266=(19a+b)%26a=15-1%26=7b=3加密密钥加密密钥a-1%26=15-a-1b=-153%26=7解密密钥解密密钥Ea,b(x)=(7x+3)%26解密函数为：解密函数为：E15,7(x)=(15x+7)%26解密后的明文为：解密后的明文为：meet me after midnight in the alley中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第二章 代替与换位4.举例：举例：对代

49、替密码的攻击对代替密码的攻击 KOS BMKKBS ISS YFSJ NFK BMES KOSIDY IFP KF JSS MK.t th he et th he ee eeeeee ee eeeeet tt tt ttttto oo oo oo on ni ii ii il ll ll lk kb bb bs ss sd dd db ba ay y 分析：由分析：由ESROL得到得到er,s,o,l或或re,s,o,lloser 或或 sorel 那么：由那么：由VIERD得到得到drive或或irevd所以比较合理的明文是：所以比较合理的明文是：loser drive5.举例：举例：对换位

50、密码的攻击对换位密码的攻击 ESROL VIERD中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第二章 代替与换位作业：作业：(1)解密由仿射密码加密的密文：解密由仿射密码加密的密文：VCLLCP BKLC LJKX XCHCP(2)解密用简单换位密码加密的密文：解密用简单换位密码加密的密文：EAGGAR DAIREP中南大学信息科学与工程学院计算机系 段桂华2010年年9月月3.1 群群 1.二元运算二元运算 定义：定义：设设s为集合，函数为集合，函数f:s ss称为称为s上的二上的二元运算或代数运算。满足：元运算或代数运算。满足：可计算性：可计算性：s中任何元素都可以进行这种