信息安全数学基础-2013-9新

《信息安全数学基础-2013-9新》由会员分享，可在线阅读，更多相关《信息安全数学基础-2013-9新（212页珍藏版）》请在装配图网上搜索。

1、信息安全信息安全information security层面的概念层面的概念:物理层面物理层面,运行层面运行层面,数据层面数据层面.信息安全是指为数据处理系统而采取的技术信息安全是指为数据处理系统而采取的技术的和管理的安全保护的和管理的安全保护,保护计算机硬件保护计算机硬件,软件软件,数据数据不因偶然的或恶意的原因而遭到破坏不因偶然的或恶意的原因而遭到破坏,更改更改,显露显露.属性的概念属性的概念:可用性可用性,完整性完整性,机密性机密性.计算机硬件计算机硬件软件软件破坏破坏更改更改显露显露信息安全的内容信息安全的内容:硬件安全硬件安全,软件安全软件安全,运行服务运行服务 安全安全,数据安全数

2、据安全.引 言网络通信的困境与安全威胁网络通信的困境与安全威胁网上黑客无孔不入网上黑客无孔不入 个人隐私泄露个人隐私泄露国家信息安全国家信息安全网上犯罪形势不容乐观网上犯罪形势不容乐观 有害信息污染严重有害信息污染严重 网络病毒的蔓延和破坏网络病毒的蔓延和破坏 引 言认证认证:消息来源确认消息来源确认,身份的验证身份的验证.保证信息安全要做什么呢保证信息安全要做什么呢 你是谁你是谁?我怎么相信你就是你我怎么相信你就是你?授权授权:根据实体身份决定其访问权限根据实体身份决定其访问权限.我能干什么我能干什么?你能干这个你能干这个,不能干那个不能干那个.保密保密:非授权人无法识别信息非授权人无法识别

3、信息.我与你说话时我与你说话时,别人能不能偷听别人能不能偷听?完整性完整性:防止消息被篡改防止消息被篡改.传送过程过程中别人篡改过没有传送过程过程中别人篡改过没有?不可否认不可否认:不能对所作所为进行抵赖不能对所作所为进行抵赖.我收到货后我收到货后,不想付款不想付款,想抵赖想抵赖,怎么样怎么样?我将钱寄给你后我将钱寄给你后,你不给发货你不给发货,想抵赖想抵赖,如何如何?引 言网络安全体系的五类服务网络安全体系的五类服务访问控制技术身份鉴别技术加密技术信息鉴别技术访问控制服务对象认证服务保密性服务完整性服务防抵赖服务引 言网络安全体系的五类服务网络安全体系的五类服务访问控制服务访问控制服务：根据

4、实体身份决定其访问权限根据实体身份决定其访问权限；身份鉴别服务身份鉴别服务：消息来源确认、防假冒、证明你消息来源确认、防假冒、证明你 是否就是你所声明的你；是否就是你所声明的你；保密性服务保密性服务：利用加密技术将消息加密，非授权利用加密技术将消息加密，非授权 人无法识别信息人无法识别信息；数据完整性服务数据完整性服务：防止消息被篡改，证明消息与防止消息被篡改，证明消息与 过程的正确性过程的正确性；防抵赖服务防抵赖服务：阻止你或其他主体对所作所为的进阻止你或其他主体对所作所为的进 行否认的服务，可确认、无法抵赖行否认的服务，可确认、无法抵赖。引 言引 言解决方法：解决方法：加密加密如何实现保密

5、性？如何实现保密性？密码分析密码分析公共网公共网络络AliceBob加密加密密钥密钥解密解密密钥密钥Eve引 言解决方法：解决方法：数字摘要数字摘要如何实现完整性？如何实现完整性？无法篡改无法篡改z消息篡改消息篡改公共网络公共网络AliceBobm,zm,zz=hk(m)y=hk(m)Eve如果如果yzm被篡改被篡改引 言解决方法：解决方法：数字签名数字签名如何实现不可否认性？如何实现不可否认性？否认否认公共网络公共网络AliceBobTrent谁是正确的？谁是正确的？举报举报引 言解决方法：解决方法：密码技术密码技术公共网络公共网络AliceBob假冒假冒Eve 身份鉴别：身份鉴别：就是确认

6、实体是它所声明的，身份鉴别服就是确认实体是它所声明的，身份鉴别服务提供关于某个实体身份的保证，以对抗假冒攻击。务提供关于某个实体身份的保证，以对抗假冒攻击。如何鉴别通信对象的身份？如何鉴别通信对象的身份？本课程的相关知识点本课程的相关知识点简单的密码学基础：简单的密码学基础：密码技术是信息安全的核心技术；密码技术是信息安全的核心技术；需要掌握一些密码学基础知识。需要掌握一些密码学基础知识。相关的数学知识：相关的数学知识：密码技术的实现依赖于数学知识；密码技术的实现依赖于数学知识；掌握密码技术涉及的相应数学基础知识点。掌握密码技术涉及的相应数学基础知识点。参考教材：参考教材：(1)密码学导引密码

7、学导引,机械工业出版社机械工业出版社,Paul Garrett 著著,吴世忠等译；吴世忠等译；(2)信息安全数学基础信息安全数学基础,武汉大学出版社武汉大学出版社,李继国等李继国等 主编。主编。引 言什么是密码技术？什么是密码技术？窃听窃听公共网络公共网络AliceBobEve篡改篡改伪造伪造加密加密密钥密钥解密解密密钥密钥密文密文 密码学是一门古老而深奥的学科密码学是一门古老而深奥的学科,包括密码编包括密码编码学和密码分析学码学和密码分析学;通信双方按照某种约定将消息的原形隐藏通信双方按照某种约定将消息的原形隐藏。密码系统密码系统:明文明文,密文密文,加解密算法加解密算法,密钥密钥。引 言密

8、码学的起源与发展密码学的起源与发展三个阶段：三个阶段：1949年之前：密码学是一门艺术；年之前：密码学是一门艺术；19491975年：密码学成为科学；年：密码学成为科学；1976年以后：密码学的新方向公钥密码学。年以后：密码学的新方向公钥密码学。1949年之前年之前(手工阶段的初级形式手工阶段的初级形式)隐写术：隐形墨水、字符格式的变化、图像；隐写术：隐形墨水、字符格式的变化、图像；引 言举例举例:日暮苍山兰舟小日暮苍山兰舟小,本无落霞缀清泉本无落霞缀清泉.去年叶落缘分定去年叶落缘分定,死水微漾人却亡死水微漾人却亡.kculdoog 图像隐写软件隐写软件图像隐写软件隐写软件OpenPuff 3

9、.20 引 言代替密码代替密码换位密码换位密码古典密码学古典密码学多字母代替多字母代替单字母代替单字母代替单表代替密码单表代替密码多表代替密码多表代替密码（流密码）（流密码）（分组密码）（分组密码）古典密码学分类古典密码学分类 19491975年年(机械阶段机械阶段)：现代密码出现：现代密码出现 1949年香农年香农Shannon提出提出“保密系统信息理论保密系统信息理论”；提出提出:数据的安全基于密钥而不是密码算法。数据的安全基于密钥而不是密码算法。1976年以后年以后(计算机阶段计算机阶段)：公钥密码诞生：公钥密码诞生 1976年年Diffie&Hellman的的“New Directio

10、ns in Cryptography”提出了不对称密钥密码；提出了不对称密钥密码；1977年年Rivest,Shamir&Adleman提出了提出了RSA公钥算法；公钥算法；90年代出现椭圆曲线年代出现椭圆曲线ECC、混沌密码等其他公钥、混沌密码等其他公钥算法。算法。引 言引 言1977年年DES正式成为标准正式成为标准;80年代出现年代出现IDEA,RCx,CAST等等;90年代年代Rijndael,MARS,Twofish,Serpent,RC6等出现等出现;2001年年Rijndael成为成为DES的替代者的替代者AES;2004年美国年美国NIST提出量子密码提出量子密码;2005年山

11、东大学王小云教授成功破解处理电子签年山东大学王小云教授成功破解处理电子签 名的名的MD5,SHA-1;2006年年1月我国公布了商用密码算法月我国公布了商用密码算法SMS4,应应 用于无线局域网中用于无线局域网中.对称密钥密码算法进一步发展对称密钥密码算法进一步发展密码算法的分类密码算法的分类按照保密的内容分按照保密的内容分受限制的算法：保密性基于保持算法的秘密。受限制的算法：保密性基于保持算法的秘密。基于密钥的算法：保密性基于密钥的保密。基于密钥的算法：保密性基于密钥的保密。Kerchoffs原则原则1883年年Kerchoffs第一次明确提出了编码的原则：第一次明确提出了编码的原则：保密性

12、完全依赖于密钥，算法应该公开。保密性完全依赖于密钥，算法应该公开。这一原则已得到普遍承认，成为判定密码强度的这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为衡量标准，实际上也成为古典密码古典密码和和现代密码现代密码的的分界线。分界线。引 言 基于密钥的算法，按照密钥的特点分类：基于密钥的算法，按照密钥的特点分类：对称密码算法：对称密码算法：又称秘密密钥算法或单密钥算又称秘密密钥算法或单密钥算法，加密密钥和解密密钥相同，或可以容易地法，加密密钥和解密密钥相同，或可以容易地从一个推出另一个。从一个推出另一个。特点：特点：加密速度快；密钥加密速度快；密钥管理复杂，主要用于加密信息。管

13、理复杂，主要用于加密信息。非对称密钥算法：非对称密钥算法：又称公开密钥算法，加密密又称公开密钥算法，加密密钥和解密密钥不相同，而且很难从一个推出另钥和解密密钥不相同，而且很难从一个推出另一个。一个。特点：特点：密钥管理简单，但加密速度慢，密钥管理简单，但加密速度慢，用于加密会话密钥和用于数字签名。用于加密会话密钥和用于数字签名。实际网络应用中，常采用非对称密码来交换对实际网络应用中，常采用非对称密码来交换对称密码算法的密钥。称密码算法的密钥。引 言 经典的经典的古典密码古典密码算法主要有：算法主要有：代替密码：代替密码：将明文字符用另外的字符代替，典型的将明文字符用另外的字符代替，典型的有恺撒

14、密码、仿射密码、维吉尼亚密码等；有恺撒密码、仿射密码、维吉尼亚密码等；换位密码：换位密码：明文的字母保持相同，但顺序打乱。明文的字母保持相同，但顺序打乱。经典的经典的现代密码现代密码算法有很多种，最通用的有：算法有很多种，最通用的有：DES：数据加密标准，对称密码算法，用于加密；数据加密标准，对称密码算法，用于加密；AES:高级加密标准，对称密码算法，用于加密；高级加密标准，对称密码算法，用于加密；引 言 RSA：最流行的公钥密码算法，加密和数字签名；最流行的公钥密码算法，加密和数字签名；ECC：椭圆曲线密码，采用椭圆曲线密码，采用ElGamal算法，公钥密码算法，公钥密码算法，安全性高，密钥

15、量小，灵活性好；算法，安全性高，密钥量小，灵活性好；DSA：数字签名算法，是数字签名的一部分，公钥数字签名算法，是数字签名的一部分，公钥密码算法，数字签名。密码算法，数字签名。MD5(SHA-1)：数字摘要算法，数字签名，保证消数字摘要算法，数字签名，保证消息的完整性。息的完整性。引 言 理论安全：理论安全：攻击者无论截获多少密文，都无法攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。得到足够的信息来唯一地决定明文。Shannon用理论证明：欲达理论安全，加密密钥长度必用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即须大于等于明文长度，密钥只用一次

16、，用完即丢，即一次一密密码本，不实用。丢，即一次一密密码本，不实用。实际安全：实际安全：如果攻击者拥有无限资源，任何密如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行。破译这个系统是计算上不可行。引 言密码系统的安全密码系统的安全 四种基本攻击类型：四种基本攻击类型：唯密文攻击：唯密文攻击：攻击者只有一些密文；攻击者只有一些密文；已知明文攻击：已知明

17、文攻击：攻击者知道一些明文密文对；攻击者知道一些明文密文对；选择明文攻击：选择明文攻击：攻击者可以选择明文密文对；攻击者可以选择明文密文对；针对密钥的攻击：针对密钥的攻击：主要是针对公钥密码系统。主要是针对公钥密码系统。穷举攻击：穷举攻击：攻击者采用尝试方法穷举可能的密钥。攻击者采用尝试方法穷举可能的密钥。当密钥空间较小时很有效。当密钥空间较小时很有效。字典攻击字典攻击是是 利用一些常用的单词进行组合。利用一些常用的单词进行组合。基本要求：基本要求：任何一种加密系统都必须能够对抗唯任何一种加密系统都必须能够对抗唯 密文攻击。密文攻击。目前的标准是：目前的标准是：一个密码系统应当能够对抗选择一个

18、密码系统应当能够对抗选择 明文攻击。明文攻击。引 言密码系统的攻击密码系统的攻击第一章 简单密码经典的简单密码：经典的简单密码：移位密码、一次一密乱码本、仿射密码。移位密码、一次一密乱码本、仿射密码。1.1 移位密码移位密码1.Caesar密码：密码：最简单的移位密码。最简单的移位密码。原理：原理：将消息中的每个字母前移将消息中的每个字母前移3位或者后位或者后 移移3位。位。举例：举例：all of gaul is devided into three parts DOO RI JDXO LV GHYLGHG LQWR WKUHH SDUWV2.移位密码：移位密码：改进改进Caesar密码：密

19、码：发送方和接收方协商一个发送方和接收方协商一个密钥密钥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

20、|，则，则 当当n0时，时，n%m=|m|-a；当当m1为整数，为整数，x与与m互素，则互素，则x有模有模m 的乘法逆元。特别地，满足表达式的乘法逆元。特别地，满足表达式ax+bm=1 的任意整数的任意整数a就是一个就是一个x模模m的乘法逆元。的乘法逆元。(2)假如假如y是是x模模m的乘法逆元的乘法逆元,对于对于y,若若m|y-y，那么那么y也是也是x模模m的乘法逆元；反之亦然。的乘法逆元；反之亦然。(3)给定一非零整数给定一非零整数m和任意整数和任意整数n，存在唯一的，存在唯一的 整数整数q和和r，使得，使得0r|m|且且n=qm+r(4)设设n和和N为两个整数，对某个整数为两个整数，对某个

21、整数k有有N=kn，则对任意整数则对任意整数x有：有：(x%N)%n=x%n4.欧几里德算法欧几里德算法第一章 简单密码 (1)定理定理 x和和y为不同时为为不同时为0的整数，则的整数，则x和和y的最大公因子的最大公因子gcd(x,y)是以是以ax+by表示的最小正整数。表示的最小正整数。例如：例如：gcd(3,5)=23-15=1 gcd(9,15)=29-115=3(2)欧几里德算法欧几里德算法 用以寻找两个整数用以寻找两个整数x和和y的最大公因子的最大公因子d。使用该算法将使用该算法将x和和y的最大公因子表示为：的最大公因子表示为：ax+by=gcd(x,y)的形式。的形式。(3)分析：

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第一章 简单密码最大公因子为最大公因子为1 1寻找整数寻找整数a和和b(4)乘法逆元的计算乘法逆元的计

23、算 两个整数两个整数x和和y x-yq1=r1 x1-y1q2=r2 x2-y2q3=r3 xn-1-yn-1qn=0 xn yn2121221011xxxM Myqyy1111011xxxMyqyy111011gcd(,)nnnnnnnxxxMMyqyyabxaxbyxx ycdy结论：结论：当当x和和y互素时，互素时，gcd(x,y)为为1，即可得到，即可得到x-1%y为为a，y-1%x为为b。第一章 简单密码(5)举例举例01010115011415114211156562515 256 21121252125210abcd 所以：所以：21-1%25的结果为的结果为6。例例2：求：求1

24、234-1%4321 例例1：求：求21-1%25 解：解：25-121=4 21-54=1 4-14=0 第一章 简单密码1.3 一次一密乱码本一次一密乱码本OTP 1.思想：思想：密钥与消息一样长，且只能使用一次。密钥与消息一样长，且只能使用一次。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 密钥：密钥：

25、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.特点：特点：密钥的产生与分发管理复杂；对称密码；密钥的产生与分发管理复杂；对称密码；多表代替密码：明文中不同位置的字母采用的多表代替密码：明文中不同位置的字母采用的 加密密钥不同。加密密钥不同。1.4 仿射密码仿射密码 1.思想：思想：对移位密码进行改进，扩大密钥空间。对移位密码进行改进，扩大密钥空间。2.原理：原理：加密：加密：Ea,b(x)=(a x+b)%26 0a,b 25 解密：解密：Da,b(y)=3.特点：特点：(1

26、)当当a=1时为移位密码；时为移位密码；(2)加密密钥为加密密钥为(a,b)；解密密钥为；解密密钥为(a-1,-a-1b)；(3)单表代替密码；单表代替密码；(4)对称密码：由加密密钥可以推导出解密密钥；对称密码：由加密密钥可以推导出解密密钥；11111,()()()%26a baa bEyEya ya b第一章 简单密码 (5)密钥空间：由于密钥空间：由于a-1必须存在，所以可能的密钥数必须存在，所以可能的密钥数 为为1226-1=311个。个。第一章 简单密码)()()()()()()()()()()1)0()()(111,0,110,1,11,10,1,10,xExExExExExExE

27、xExExEbaxbaxxEbaaababbabababa4.攻击方法：攻击方法：穷举攻击：穷举攻击：尝试尝试311个可能的密钥。个可能的密钥。选择明文攻击：选择明文攻击：Ea,b(0)=(a 0+b)%26 Ea,b(1)=(a 1+b)%26 已知明文攻击：已知明文攻击：Ea,b(x)=(a x+b)%26 Ea,b(y)=(a y+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第一章 简单密码 举例：举例：已知明文：已知明文：mee

28、t me at midnight 假设密文：假设密文：HNNS HN DS HXEQXFOS (1)选择明文攻击选择明文攻击 攻击者选择：攻击者选择：a(0)D(3)d(3)E(4)第一章 简单密码 Ea,b(0)=(a 0+b)%26 Ea,b(3)=(a 3+b)%263=b%264=(3a+b)%26b=3a=3-1%26=9加密密钥加密密钥a-1%26=3-a-1b=-33%26=17解密密钥解密密钥 (2)已知明文攻击已知明文攻击 攻击者获得：攻击者获得：m(12)H(7)h(7)O(14)Ea,b(12)=(a 12+b)%26 Ea,b(7)=(a 7+b)%267=(12a+b

29、)%2614=(7a+b)%26a=(-75-1)%26=9b=(14-79)%26=3加密密钥加密密钥第一章 简单密码第一章 简单密码1.5 Vigenere密码密码 1.特点：特点：具有相对较大的密钥空间；具有相对较大的密钥空间；对称密码；多表代替密码；对称密码；多表代替密码；有周期性的弱点：若两个字符出现的间隔是密钥有周期性的弱点：若两个字符出现的间隔是密钥长度的倍数，则它们将以同样的方法加密。长度的倍数，则它们将以同样的方法加密。2.加密和解密的原理：加密和解密的原理：(1)密钥是一个字符序列：密钥是一个字符序列：k=(k0,k1,km-1)；明文明文x=(x0,x1,xN)被分成长度

30、为被分成长度为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.多轮加密多轮加密(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的维吉尼亚密

31、码加的维吉尼亚密码加密，得到的密文再用长度为密，得到的密文再用长度为n的密钥加密，其结果与的密钥加密，其结果与用长度为用长度为lcm(m,n)的维吉尼亚密码加密的结果一样。的维吉尼亚密码加密的结果一样。若若m,n互素，则互素，则lcm(m,n)=mxn，密钥长度很大。，密钥长度很大。第一章 简单密码1.6最小公倍数最小公倍数lcm和最大公约数和最大公约数gcd 1.定义定义 对于两个整数对于两个整数d,n，若，若d整除整除n，或者说，或者说d是是n的的一个因子，记作：一个因子，记作：d|n 设设m,n是两个非是两个非0的整数，则最大公约数的整数，则最大公约数d为最为最大的正整数，使得大的正整数

32、，使得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；第一章 简单密码3.素数素数 素数素数p是那些不存在因子是那些不存在因子d的整数的整数1d p1/2；定理：定理：每

33、一个正整数都可以分解为素数的乘积，每一个正整数都可以分解为素数的乘积，而且这种分解是唯一的。而且这种分解是唯一的。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 生日攻击生日

34、攻击 1.命题命题 在实验在实验x中，不同结果中，不同结果x1,x2,xn的概率分别为的概率分别为p(x1)=p1,p(xn)=pn。集合。集合A为样本空间为样本空间x1,xn的一个子集，且有的一个子集，且有p(A)=p。设。设0kN，则，则N次实次实验中验中A恰好出现恰好出现k次的概率为：次的概率为：举例举例：投币。假设一枚公平的硬币朝上或朝下的投币。假设一枚公平的硬币朝上或朝下的 几率是相等的，且每次投币是独立的。几率是相等的，且每次投币是独立的。分析：分析：记录一个记录一个n次投掷的过程：次投掷的过程：2n任何单个序列出现的概率是任何单个序列出现的概率是1/2nn次投掷恰好有次投掷恰好有

35、k次正面朝上的概率是：次正面朝上的概率是：2nnk kNkppkN)1(10次投掷中：次投掷中：恰好恰好5次正面朝上的概率为：次正面朝上的概率为：252/10241/4 6-4或者或者4-6组合的概率是：组合的概率是：420/10242/52.生日攻击生日攻击 设设=1,2,N为所有原子事件的样本空间，为所有原子事件的样本空间，p(i)=1/N。n次实验后至少次实验后至少2次结果相同的概率至次结果相同的概率至少为：少为：1-e-n(n-1)/2N。因此，对于。因此，对于 出现两次相同结果的概率至少为出现两次相同结果的概率至少为1/2。2ln2nN第一章 简单密码证明：证明：先计算出没有两种完全

36、相同结果出现的概先计算出没有两种完全相同结果出现的概 率率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

37、/N)+ln(1-2/N)+ln(1-(n-1)/N)根据泰勒级数展开式：根据泰勒级数展开式：ln(1-x)=-(x+x2/2+x3/3+)-x第一章 简单密码所以所以lnpn=ln(1-1/N N)+ln(1-2/N N)+ln(1-(n-1)/N N)-(1/N+N+2/N+N+(n-1)/N N)=-(1+2+n-1)/N N =-n(n-1)/2N N -n2/2N N p=pne-n(n-1)/2N N p=1-p1-e-n(n-1)/2N N n次实验后至少次实验后至少2次结果相同的概率次结果相同的概率p1-e-n(n-1)/2N N另外：另外：要使得要使得p1/2，则，则p1/2

38、 ln lnpln1/2 -n2/2N Nln1/2 -n2/2N Nln2 2ln2nN第一章 简单密码作业：作业：(1)为移位密码加密的消息解密：为移位密码加密的消息解密：YRQ QEFP BUXJMIB FP IBPP BXPV (2)求求-1000模模88的约简。的约简。(3)求求29模模100的乘法逆。的乘法逆。(4)已知明文攻击：已知明文攻击：Ea,b(3)=5且且Ea,b(6)=7，求加密密钥。，求加密密钥。(5)求求gcd(1112,1544)，并将其表示成如下形式：，并将其表示成如下形式：1112x+1544y (6)求求1001模模1234的乘法逆。的乘法逆。第一章 简单密

39、码 古典密码的两大机制：古典密码的两大机制：代替密码：代替密码：字母表范围内替换；字母表范围内替换；换位密码：换位密码：在消息内变换字母的位置。在消息内变换字母的位置。2.1代替密码代替密码 1.描述描述 密钥是字母表的任意组合，有一个明密对应表；密钥是字母表的任意组合，有一个明密对应表；密钥空间巨大：密钥空间巨大：26!；单表代替密码的两个特例：移位密码和仿射密码。单表代替密码的两个特例：移位密码和仿射密码。2.举例举例 首先选加密表；为了便于记忆，协商一个密钥：首先选加密表；为了便于记忆，协商一个密钥：DO YOU LIKE THIS BOOK 去掉重复字母，再进行补充，形成加密表：去掉重

40、复字母，再进行补充，形成加密表：abcdefghijklmnopqrstuvwxyz DOYULIKETHSBACFGJMNPQRVWXZ第二章 代替与换位第二章 代替与换位2.2 换位密码换位密码 1.机制：机制：单个字符不变而位置改变。单个字符不变而位置改变。如将文本翻转：明文如将文本翻转：明文 computersystems 密文密文 SMETSYSRETUPMOC 2.特点：特点：(1)密文长度与明文长度相同；密文长度与明文长度相同；(2)唯密文攻击可能得到多种不同的破译结果；唯密文攻击可能得到多种不同的破译结果；如如 keeppeek；liveevilvile 3.分组换位密码分组换

41、位密码 针对固定大小的分组进行操作。针对固定大小的分组进行操作。举例：明文举例：明文 can you understand (1)列换位法列换位法 设密钥设密钥k=4，将明文进行分组排列，将明文进行分组排列按列按列读出读出密文：密文：CODTAUEANURNYNSD按行按行读出读出明文：明文：canyouunderstand明文：明文：canyouunderstand按按4 4个字符一行分组排列个字符一行分组排列按按4 4个字符一列分组排列个字符一列分组排列1 2 3 41 2 3 4第二章 代替与换位按列按列 读出读出t y p e密文：密文：YNSDNURNCODTAUEA按行按行读出读出

42、明文：明文：canyouunderstand明文：明文：canyouunderstand按按4 4个字符一行分组排列个字符一行分组排列按type(3,4,2,1)填入1 2 3 43 4 2 1 YNSD NURN CODT AUEA(2)密钥为字符串密钥为字符串type1234按密钥长度分组按密钥长度分组第二章 代替与换位(3)矩阵换位法：置换矩阵作为密钥矩阵换位法：置换矩阵作为密钥12342413f112343142f明文：明文：canyouunderstandc 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密文：

43、密文：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解密置换矩阵：解密置换矩阵：说明：说明：1123412341234241331421234ff 第二章 代替与换位第二章 代替与换位2.3 频率攻击频率攻击1.原理：原理：利用自然语言的频率攻击利用自然语言的频率攻击 字母出现的频率有规律：字母出现的频率有规律：e:11.67 t:9.53 o:7.81 a:7.73 e:11.67 t:9.53 o

44、: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 第二章 代替与换位 Ea,b(4)=(a 4+b)%26 Ea,b(19)=(a 19

45、+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第二章 代替与换位4.举例：举例：对代替密码的攻击对代替密码的攻击 KOS BMKKBS ISS YFSJ NFK BMES KOSIDY IFP KF JSS MK.t th he et th he ee eeeeee ee eeee

46、et 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.举例：举例：对换位密码的攻击对换位密码的攻击 ESROL VIERD第二章 代替与换位作业：作业：(1)解密由仿射密码加密的密文：解密由仿射密码加密的密文：VCLLCP BKLC LJKX XCHCP(2)解密用简单

47、换位密码加密的密文：解密用简单换位密码加密的密文：EAGGAR DAIREP3.1 群群 1.二元运算二元运算 定义：定义：设设s为集合，函数为集合，函数f:s ss称为称为s上的二上的二元运算或代数运算。满足：元运算或代数运算。满足：可计算性：可计算性：s中任何元素都可以进行这种运算；中任何元素都可以进行这种运算；单值性：运算结果唯一；单值性：运算结果唯一；封闭性：封闭性：s中任何两个元素运算结果都属于中任何两个元素运算结果都属于s。2.群的定义群的定义 定义：定义：设设是代数系统，是代数系统，为为G上的二元运上的二元运算，如果算，如果 运算是可结合的，则称运算是可结合的，则称半群。半群。若

48、若为半群，并且二元运算为半群，并且二元运算 存在单位元存在单位元e G，则称，则称为幺半群；为幺半群；若若为半群，并且二元运算为半群，并且二元运算 存在单位元存在单位元e G，G中的任何元素中的任何元素x都有逆元都有逆元x-1 G，称，称为群，简记为为群，简记为G。第三章 置 换 举例：举例：(1)是群，其中是群，其中Z为整数集合，为整数集合，+是普通是普通的加法，单位元是的加法，单位元是0，整数，整数x的逆元是的逆元是-x。(2)是群，是群，Z6=0,1,2,3,4,5，为模为模6加法。显然加法。显然 满足结合律，单位元是满足结合律，单位元是0；由于；由于1 5=0，2 4=0，3 3=0，

49、所以，所以1和和5互为逆元，互为逆元，2和和4互为逆互为逆元，元，3和和0的逆元仍然是的逆元仍然是3和和0。3.群中元素的阶群中元素的阶 定义：定义：设设是群，是群，a G，n Z，则，则a的的n次幂为次幂为 e n=0 an=an-1 a n0 (a-1)m n0,n=-m 举例：举例：在群在群中，中，30=0，35=15，3-5=-15 在群在群中，中，20=0，23=0，2-3=0第三章 置 换 阶的定义：阶的定义：(1)设设是群，是群，a G，使得等式，使得等式ak=e成立的成立的最小正整数最小正整数k称为称为a的阶，记做的阶，记做|a|=k，a称为称为k阶元，阶元，若不存在这样的整数

50、若不存在这样的整数k，则，则a称为无限阶元。称为无限阶元。例如：例如：在在中，中，2和和4是是3阶元，阶元，3是是2阶元，阶元，1和和5是是6阶元，阶元，0是是1阶元。阶元。在在中，中，0是是1阶元，其他都是无限阶元。阶元，其他都是无限阶元。(2)设设为群，为群，a G，且，且|a|=r。设。设k是整数，是整数，则则ak=e当且仅当当且仅当r|k。(3)设设为群，则群中任何元素为群，则群中任何元素a与其逆元与其逆元a-1 具有相同的阶。具有相同的阶。第三章 置 换 4.循环群和置换群循环群和置换群 定义定义1：设设为群，如果存在一个元素为群，如果存在一个元素a G，使得使得G=ak|k Z，则

51、称，则称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元置换

52、元置换群。群。第三章 置 换 定义定义2：设设s=1,2,n，s上的任何双射映射函数上的任何双射映射函数:ss称为称为s上的上的n元置换，记为：元置换，记为：12.(1)(2).()nn3.2置换概念置换概念 1.置换置换 一个集合一个集合X的置换的置换f定义为定义为X到自身的一个双射到自身的一个双射函数函数f。对应有。对应有n个元素的集合个元素的集合X，共有，共有n!个置换。个置换。问题：问题：对于集合对于集合X，给定某个状态，经过多少次，给定某个状态，经过多少次置换返回初始状态？置换返回初始状态？Sn=1,2,3,n-1,n表示表示n个元素的置换群个元素的置换群 置换置换g为满足为满足g(

53、k)=ik的一个置换：的一个置换：1231 2 3 nngiiii平凡置换平凡置换e：没有移动任何元素的置换。没有移动任何元素的置换。即对于所有的即对于所有的i，有，有e(i)=i。1 2 3 1 2 3 nen置换与集合置换与集合内容无关内容无关第三章 置 换2.置换的合成或乘积置换的合成或乘积 设设g和和h是两个置换，先应用是两个置换，先应用h，再应用，再应用g，记为：记为：g h或或gh 注意：注意：g h h g 置换的合成满足结合律：置换的合成满足结合律：(g h)k=g (h k)3.逆置换逆置换 对于任意置换对于任意置换g，存在一个逆置换，存在一个逆置换g-1，满足：，满足：g

54、g-1=g-1 g=e4.图表记法图表记法 用来计算两个置换的乘积。如：用来计算两个置换的乘积。如：1 2 33 2 1h1 2 32 3 1g第三章 置 换5.循环循环 最简单的置换是不同长度的循环。最简单的置换是不同长度的循环。一个一个k循环满足：循环满足：f(i1)=i2,f(i2)=i3,f(ik-1)=ik,f(ik)=i1，对于任意对于任意j(i1,i2,ik)，有，有f(j)=j。举例：举例：则：则：1 2 31 2 31 2 32 3 13 2 11 3 2g h 1 2 31 2 31 2 33 2 12 3 12 1 3h g 1 2 32 1 3可见：可见：g h h g

55、，具有不可交换性。，具有不可交换性。记作：记作：(i1,i2,ik)1 2 33 2 1(1 2)(1 3)第三章 置 换6.结论结论 (1)如果如果g是一个是一个k循环，那么循环，那么gk=e。1 2 32 3 11 2 3(1 2 3)2 3 1g注意：注意：一个一个k k循环有循环有k k种表示法。种表示法。比较：比较：(1 2 3)与与(1 3 2)1 2 31 2 31 2 31 2 32 3 12 3 12 3 11 2 3g g g(1 2 3)=(2 3 1)=(3 1 2)1 2 33 1 2(1 3 2)如：如：则：则：即：即：对某个集合应用对某个集合应用g g操作操作k

56、k次，不会对集合产生次，不会对集合产生 任何影响。任何影响。第三章 置 换(2)置换的阶置换的阶 是置换被多次应用后却不产生任何实际影响所是置换被多次应用后却不产生任何实际影响所需要的重复次数。需要的重复次数。若置换若置换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的阶

57、的阶k=不相交循环分解中各循环长度不相交循环分解中各循环长度的最小公倍数。的最小公倍数。1 2 3 4 5 6 7(1 4 5 7)(2 3)(6)4 3 2 5 7 6 1g如：如：思考：思考：如果一副如果一副5050张的牌洗得好，重复洗张的牌洗得好，重复洗8 8次后所次后所 有的牌将返回初始位置。有的牌将返回初始位置。阶为阶为4 4(4)置换的不相交循环分解置换的不相交循环分解 任何置换都可以表示为不相交循环的乘积，并任何置换都可以表示为不相交循环的乘积，并且本质上只有这一种表示方法。且本质上只有这一种表示方法。1 2 3 4 5 6 74 3 2 5 7 6 1g=(1 4 5 7)(2

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

59、i)%n+1第三章 置 换如：如：n=6,i=3 1,2,3,4,5,6 3,4,5,6,1,2置换过程为：置换过程为：1 2 3 4 5 65 6 1 2 3 4f3(x)=(x+3)%6+12n张牌：张牌：1,2,n,n+1,2n-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

60、的最小正整数。那么对一副有的最小正整数。那么对一副有2n张牌经张牌经 过过e次洗牌后，所有的牌都第一次返回到它们次洗牌后，所有的牌都第一次返回到它们 的起始位置。的起始位置。不好的洗牌不好的洗牌完美洗牌完美洗牌第三章 置 换3.4洗牌洗牌01211221121nnnnnmnnmnnmnnmn然后按列读取这些数：然后按列读取这些数：0,n,2n,mn-n,1,n+1,2n+1,mn-n+1,mn-1对于数对于数x，行：，行：x/n 列：列：x%n3.5 分组交错分组交错 给定正整数给定正整数m和和n，针对，针对mn个元素，一个个元素，一个m n分组交换的置换定义为：分组交换的置换定义为：按行将按

61、行将mm个数据写成个数据写成m n的矩阵的形式的矩阵的形式第三章 置 换012345678910110369147102581101234567891011然后按列读取这些数：然后按列读取这些数：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，进行进行3 4分组交错。分组交错。对应的循环分解为：对应的循环分解为：0 1 3 9 5 42 6 7 10 8 11数据数据置换位置置换位置阶为阶为5 501234567891011按按4 4行行3 3列写出列写出第三章 置 换命题：忽略

62、两个不动点命题：忽略两个不动点0和和mn-1，m n分组交错分组交错 对集合对集合1,2,3,mn-2的作用是：的作用是：x (mx)%(mn-1)举例：举例：3 6分组交错分组交错0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 170 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14 1701234567891011121314151617 0 1 3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 173x%173x%17 分析：快速洗牌，去掉两个不动点分析：快速洗牌，去掉两个不动点 完美的快速洗牌：完美的

63、快速洗牌：x (2x)%(2n+1)第三章 置 换作业：作业：(1)计算乘积计算乘积1 2 3 4 5 6 71 2 3 4 5 6 72 5 4 7 1 3 62 3 4 7 1 5 6 第三章 置 换 用不相交循环的乘积表示上述的结果，并确定阶。用不相交循环的乘积表示上述的结果，并确定阶。(2)S5中任意元素的最大阶是多少？中任意元素的最大阶是多少？S14呢？呢？(3)确定对一副确定对一副20张牌的完美快速洗牌的循环分解。张牌的完美快速洗牌的循环分解。(4)找出找出3 5的分组交错置换的循环分解。的分组交错置换的循环分解。第四章 现代对称密码 香农提出的香农提出的现代密码现代密码设计准则：

64、设计准则：KerchhoffKerchhoff原则：原则：系统的安全性不依赖于对密文或系统的安全性不依赖于对密文或 加密算法的保密，而依赖于密钥。加密算法的保密，而依赖于密钥。惟一需要保密的是密钥；惟一需要保密的是密钥；决定了古典密码学与现代密码学。决定了古典密码学与现代密码学。一个好的密码将融合混淆和扩散一个好的密码将融合混淆和扩散 混淆：混淆：混淆明文的不同部分；混淆明文的不同部分；扩散：扩散：对攻击者隐藏一些语言的局部特征；对攻击者隐藏一些语言的局部特征；现代密码将结合换位和代替：现代密码将结合换位和代替：代替密码代替密码在混淆上是有效的；在混淆上是有效的；换位密码换位密码扩散性较好。扩

65、散性较好。4.1 数据加密标准数据加密标准DES(Data Encryption Standard)1976年被采纳作为联邦标准，并授权在非密级年被采纳作为联邦标准，并授权在非密级的政府通信中使用，应用广泛。的政府通信中使用，应用广泛。DES是一个分组加密算法，对称密码，是一个分组加密算法，对称密码，64位分位分 组，密钥长度为组，密钥长度为64位位(实际长度为实际长度为56位位)。第四章 现代对称密码 现代密码算法的特点：现代密码算法的特点：只要保证密钥安全，就能保证加密信息的安全。只要保证密钥安全，就能保证加密信息的安全。对称密码算法：对称密码算法：很好地融合了混淆和扩散；很好地融合了混淆

66、和扩散；DES、AES、IEDA、RC6等等 非对称密码算法：非对称密码算法：基于数学难题；基于数学难题；RSA、ECC、ElGamal等等 DES的整个算法是公开的，系统的安全性靠的整个算法是公开的，系统的安全性靠密钥保证。算法包括三个步骤：初始置换密钥保证。算法包括三个步骤：初始置换IP、16轮轮迭代的乘积变换、逆初始变换迭代的乘积变换、逆初始变换IP-1。1.初始置换初始置换IP 初始置换初始置换IP可将可将64位明文位明文M=m1m2m64的位置进的位置进行置换，得到乱序的行置换，得到乱序的64位明文组位明文组M0=m58m50m7。2.逆初始置换逆初始置换IP-1 逆初始置换逆初始置换IP-1将将16轮迭代后的轮迭代后的64比特数据的各比特数据的各字节按列写出，将前四列插到后四列中，再对各列进行字节按列写出，将前四列插到后四列中，再对各列进行逆序，然后将元素按行读出即可得到输出的密文组。逆序，然后将元素按行读出即可得到输出的密文组。IP和和IP-1的作用主要是打乱输入的的作用主要是打乱输入的ASCII码字划分码字划分关系，并将明文校验码变成关系，并将明文校验码变成IP输出的一