信息安全数学基础ppt课件市公开课一等奖百校联赛特等奖课件.pptx

信息安全数学基础信息安全数学基础信息科学与工程学院 第1页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月网络信息安全威胁网络信息安全威胁 网上犯罪形势不容乐观；网上犯罪形势不容乐观；有害信息污染严重；有害信息污染严重；网络病毒蔓延和破坏；网络病毒蔓延和破坏；网上黑客无孔不入；网上黑客无孔不入；机要信息流失与信息间谍潜入；机要信息流失与信息间谍潜入；网络安全产品自控权；网络安全产品自控权；信息战阴影不可忽略。信息战阴影不可忽略。引 言第2页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月网络通信困境网络通信困境引 言第3页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月信息信息完整完整用户用户认证认证网站网站认证认证密钥密钥管理管理不可不可抵赖抵赖数据数据安全安全我们要保护什么呢？我们要保护什么呢？引 言第4页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月网络安全体系五类服务网络安全体系五类服务访问控制技术身份判别技术加密技术信息判别技术访问控制服务对象认证服务保密性服务完整性服务防抵赖服务引 言第5页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月网络安全体系五类服务网络安全体系五类服务访问控制服务访问控制服务：依据实体身份决定其访问权限依据实体身份决定其访问权限；身份判别服务身份判别服务：消息起源确认、防假冒、证实你消息起源确认、防假冒、证实你 是否就是你所申明你；是否就是你所申明你；保密性服务保密性服务：利用加密技术将消息加密，非授权利用加密技术将消息加密，非授权 人无法识别信息人无法识别信息；数据完整性服务数据完整性服务：预防消息被篡改，证实消息与预防消息被篡改，证实消息与 过程正确性过程正确性；防抵赖服务防抵赖服务：阻止你或其它主体对所作所为进阻止你或其它主体对所作所为进 行否定服务，可确认、无法抵赖行否定服务，可确认、无法抵赖。引 言第6页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月引 言处理方法：处理方法：加密加密怎样实现保密性？怎样实现保密性？密码分析密码分析公共网络公共网络AliceBob加密加密密钥密钥解密解密密钥密钥Eve第7页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月引 言处理方法：处理方法：数字摘要数字摘要怎样实现完整性？怎样实现完整性？无法篡改无法篡改z消息篡改消息篡改公共网络公共网络AliceBobm,zm,zz=hk(m)y=hk(m)Eve假如假如yzm被篡改被篡改第8页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月引 言处理方法：处理方法：数字署名数字署名怎样实现不可否定性？怎样实现不可否定性？否定否定公共网络公共网络AliceBobTrent谁是正确？谁是正确？举报举报第9页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月引 言处理方法：处理方法：密码技术密码技术公共网络公共网络AliceBob假冒假冒Eve 身份判别：身份判别：就是确认实体是它所申明，身份判别服务就是确认实体是它所申明，身份判别服务提供关于某个实体身份确保，以反抗假冒攻击。提供关于某个实体身份确保，以反抗假冒攻击。怎样判别通信对象身份？怎样判别通信对象身份？第10页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月本课程相关知识点本课程相关知识点简单密码学基础：简单密码学基础：密码技术是信息安全关键技术；密码技术是信息安全关键技术；需要掌握一些密码学基础知识。需要掌握一些密码学基础知识。相关数学知识：相关数学知识：密码技术实现依赖于数学知识；密码技术实现依赖于数学知识；掌握密码技术包括对应数学基础知识点。掌握密码技术包括对应数学基础知识点。参考教材：参考教材：(1)密码学导引密码学导引,机械工业出版社机械工业出版社,Paul Garrett 著著,吴世忠等译；吴世忠等译；(2)信息安全数学基础信息安全数学基础,武汉大学出版社武汉大学出版社,李继国等李继国等 主编。主编。引 言第11页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月什么是密码技术？什么是密码技术？窃听窃听公共网络公共网络AliceBobEve篡改篡改伪造伪造加密加密密钥密钥解密解密密钥密钥密文密文密密码码学学是是一一门门古古老老而而深深奥奥学学科科,包包含含密密码码编编码码学学和密码分析学和密码分析学;通信双方按照某种约定将消息原形隐藏通信双方按照某种约定将消息原形隐藏。密码系统密码系统:明文明文,密文密文,加解密算法加解密算法,密钥密钥。引 言第12页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月密码学起源与发展密码学起源与发展三个阶段：三个阶段：1949年之前：密码学是一门艺术；年之前：密码学是一门艺术；19491975年：密码学成为科学；年：密码学成为科学；1976年以后：密码学新方向公钥密码学。年以后：密码学新方向公钥密码学。1949年之前年之前(手工阶段初级形式手工阶段初级形式)隐写术：隐形墨水、字符格式改变、图像；隐写术：隐形墨水、字符格式改变、图像；举例：举例：芦花丛中一扁舟，俊杰俄从此地游；芦花丛中一扁舟，俊杰俄从此地游；义士若能知此理，反躬难逃可无忧。义士若能知此理，反躬难逃可无忧。258 71539 258 314697 314697 15358 24862 17893 258 71539 258 314697 314697 15358 24862 17893 引 言第13页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月19491975年年(机械阶段机械阶段)：当代密码出现：当代密码出现1949年香农年香农Shannon提出提出“保密系统信息理论保密系统信息理论”；提出：数据安全基于密钥而不是密码算法。提出：数据安全基于密钥而不是密码算法。1976年以后年以后(计算机阶段计算机阶段)：公钥密码诞生：公钥密码诞生1976年年Diffie&Hellman“New Directions in Cryptography”提出了不对称密钥密码；提出了不对称密钥密码；1977年年Rivest,Shamir&Adleman提出了提出了RSA公钥算法；公钥算法；90年代出现椭圆曲线年代出现椭圆曲线ECC等其它公钥算法。等其它公钥算法。引 言第14页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月对称密钥密码算法深入发展1977年DES正式成为标准；80年代出现“过渡性”“post DES”算法，如IDEA、RCx、CAST等；90年代对称密钥密码深入成熟，Rijndael、RC6、MARS、Twofish、Serpent等出现；Rijndael成为DES替换者AES。年6月美国NIST提出最新信息加密技术-量子密码。年山东大学王小云教授成功破解处理电子署名MD5。引 言第15页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月密码算法分类密码算法分类按照保密内容分按照保密内容分受限制算法：保密性基于保持算法秘密。受限制算法：保密性基于保持算法秘密。基于密钥算法：保密性基于密钥保密。基于密钥算法：保密性基于密钥保密。Kerchoffs标准标准1883年年Kerchoffs第一次明确提出了编码标准：第一次明确提出了编码标准：保密性完全依赖于密钥，算法应该公开。保密性完全依赖于密钥，算法应该公开。这一标准已得到普遍认可，成为判定密码强度衡这一标准已得到普遍认可，成为判定密码强度衡量标准，实际上也成为量标准，实际上也成为古典密码古典密码和和当代密码当代密码分界分界限。限。引 言第16页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月基于密钥算法，按照密钥特点分类：基于密钥算法，按照密钥特点分类：对称密码算法：对称密码算法：又称秘密密钥算法或单密钥算又称秘密密钥算法或单密钥算法，加密密钥和解密密钥相同，或能够轻易地法，加密密钥和解密密钥相同，或能够轻易地从一个推出另一个。从一个推出另一个。特点：特点：加密速度快；密钥加密速度快；密钥管理复杂，主要用于加密信息。管理复杂，主要用于加密信息。非对称密钥算法：非对称密钥算法：又称公开密钥算法，加密密又称公开密钥算法，加密密钥和解密密钥不相同，而且极难从一个推出另钥和解密密钥不相同，而且极难从一个推出另一个。一个。特点：特点：密钥管理简单，但加密速度慢，密钥管理简单，但加密速度慢，用于加密会话密钥和用于数字署名。用于加密会话密钥和用于数字署名。实际网络应用中，常采取非对称密码来交换对实际网络应用中，常采取非对称密码来交换对称密码算法密钥。称密码算法密钥。引 言第17页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月经典经典古典密码古典密码算法主要有：算法主要有：代替密码：代替密码：将明文字符用另外字符代替，经典有恺将明文字符用另外字符代替，经典有恺撒密码、仿射密码、维吉尼亚密码等；撒密码、仿射密码、维吉尼亚密码等；换位密码：换位密码：明文字母保持相同，但次序打乱。明文字母保持相同，但次序打乱。经典经典当代密码当代密码算法有很各种，最通用有：算法有很各种，最通用有：DES：数据加密标准，对称密码算法，用于加密；数据加密标准，对称密码算法，用于加密；AES:高级加密标准，对称密码算法，用于加密；高级加密标准，对称密码算法，用于加密；引 言第18页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月RSA：最流行公钥密码算法，加密和数字署名；最流行公钥密码算法，加密和数字署名；ECC：椭圆曲线密码，采取椭圆曲线密码，采取ElGamal算法，公钥密码算法，公钥密码算法，安全性高，密钥量小，灵活性好；算法，安全性高，密钥量小，灵活性好；DSA：数字署名算法，是数字署名一部分，公钥密数字署名算法，是数字署名一部分，公钥密码算法，数字署名。码算法，数字署名。MD5(SHA-1)：数字摘要算法，数字署名，确保消数字摘要算法，数字署名，确保消息完整性。息完整性。引 言第19页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 理论安全：理论安全：攻击者不论截获多少密文，都无法攻击者不论截获多少密文，都无法得到足够信息来唯一地决定明文。得到足够信息来唯一地决定明文。Shannon用理用理论证实：欲达理论安全，加密密钥长度必须大论证实：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，于等于明文长度，密钥只用一次，用完即丢，即一次一密密码本，不实用。即一次一密密码本，不实用。实际安全：实际安全：假如攻击者拥有没有限资源，任何假如攻击者拥有没有限资源，任何密码系统都是能够被破译；不过，在有限资源密码系统都是能够被破译；不过，在有限资源范围内，攻击者都不能经过系统地分析方法来范围内，攻击者都不能经过系统地分析方法来破解系统，则称这个系统是计算上安全或破译破解系统，则称这个系统是计算上安全或破译这个系统是计算上不可行。这个系统是计算上不可行。引 言密码系统安全密码系统安全第20页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 四种基本攻击类型：四种基本攻击类型：唯密文攻击：唯密文攻击：攻击者只有一些密文；攻击者只有一些密文；已知明文攻击：已知明文攻击：攻击者知道一些明文密文对；攻击者知道一些明文密文对；选择明文攻击：选择明文攻击：攻击者能够选择明文密文对；攻击者能够选择明文密文对；针对密钥攻击：针对密钥攻击：主要是针对公钥密码系统。主要是针对公钥密码系统。穷举攻击：穷举攻击：攻击者采取尝试方法穷举可能密钥。攻击者采取尝试方法穷举可能密钥。当密钥空间较小时很有效。当密钥空间较小时很有效。字典攻击字典攻击是是 利用一些惯用单词进行组合。利用一些惯用单词进行组合。基本要求：基本要求：任何一个加密系统都必须能够反抗唯任何一个加密系统都必须能够反抗唯 密文攻击。密文攻击。当前标准是：当前标准是：一个密码系统应该能够反抗选择一个密码系统应该能够反抗选择 明文攻击。明文攻击。引 言密码系统攻击密码系统攻击第21页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第一章 简单密码经典简单密码：经典简单密码：移位密码、一次一密乱码本、仿射密码。移位密码、一次一密乱码本、仿射密码。1.1 移位密码移位密码1.Caesar密码：密码：最简单移位密码。最简单移位密码。原理：原理：将消息中每个字母前移将消息中每个字母前移3位或者后位或者后 移移3位。位。举例：举例：all of gaul is devided into three parts DOO RI JDXO LU GLYLGHG LQWR WKUHH SDUWU2.移位密码：移位密码：改进改进Caesar密码：密码：发送方和接收方协商一个发送方和接收方协商一个密钥密钥k，1k25，代表移动位数。，代表移动位数。第22页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月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|。第一章 简单密码第23页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月举例：举例：-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第一章 简单密码第24页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月4.乘法逆元计算乘法逆元计算 (1)穷举法：寻找满足条件数。穷举法：寻找满足条件数。技巧：若技巧：若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乘法逆元；反之亦然。乘法逆元；反之亦然。第25页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月(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-13231 -1 -1 3 3-13 0 11 -70 11 -10 11 -20 11 -4100 2310=所以：所以：3100-1323=1第一章 简单密码第26页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月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=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(614-1513)=-193614+231513最大公因子为最大公因子为1 1193614+231513=1第一章 简单密码第27页中南大学信息科学与工程学院计算机系 段桂华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。第一章 简单密码第28页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月3.举例举例 所以：所以：21-1%25结果为结果为6。例例2：求：求1234-1%4321 例例1：求：求21-1%25 解：解：25-121=4 21-54=1 4-14=0 第一章 简单密码第29页中南大学信息科学与工程学院计算机系 段桂华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.思想：思想：密钥与消息一样长，且只能使用一次。密钥与消息一样长，且只能使用一次。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)第一章 简单密码第30页中南大学信息科学与工程学院计算机系 段桂华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.特点：特点：密钥产生与分发管理复杂；密钥产生与分发管理复杂；对称密码；对称密码；多表代替密码：明文中不一样位置字母采取加多表代替密码：明文中不一样位置字母采取加 密密钥不一样。密密钥不一样。第一章 简单密码第31页中南大学信息科学与工程学院计算机系 段桂华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-1,-a-1b)；(3)单表代替密码；单表代替密码；(4)对称密码：由加密密钥能够推导出解密密钥；对称密码：由加密密钥能够推导出解密密钥；第一章 简单密码第32页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 (5)密钥空间：因为密钥空间：因为a-1必须存在，所以可能密钥数必须存在，所以可能密钥数 为为1226-1=311个。个。第一章 简单密码第33页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月4.攻击方法：攻击方法：穷举攻击：穷举攻击：尝试尝试311个可能密钥。个可能密钥。选择明文攻击：选择明文攻击：Ea,b(0)=(a0+b)%26 Ea,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)%26b=Ea,b(0)a=(Ea,b(1)-b)%26第一章 简单密码第34页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 举例：举例：已知明文：已知明文：meet me at midnight 假设密文：假设密文：HNNS HN DS HXEQXFOS (1)选择明文攻击选择明文攻击 攻击者选择：攻击者选择：a(0)D(3)d(3)E(4)第一章 简单密码 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解密密钥解密密钥第35页中南大学信息科学与工程学院计算机系 段桂华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加密密钥加密密钥第一章 简单密码第36页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第一章 简单密码1.5 Vigenere密码密码 1.特点：特点：含有相对较大密钥空间；含有相对较大密钥空间；对称密码；多表代替密码；对称密码；多表代替密码；有周期性弱点：若两个字符出现间隔是密钥长度有周期性弱点：若两个字符出现间隔是密钥长度倍数，则它们将以一样方法加密。倍数，则它们将以一样方法加密。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第37页中南大学信息科学与工程学院计算机系 段桂华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维吉尼亚密码加密，维吉尼亚密码加密，得到密文再用长度为得到密文再用长度为n密钥加密，其结果与用长度为密钥加密，其结果与用长度为lcm(m,n)维吉尼亚密码加密结果一样。维吉尼亚密码加密结果一样。若若m,n互素，则互素，则lcm(m,n)=mxn，密钥长度很大。，密钥长度很大。第38页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第一章 简单密码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,n)|N；第39页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第一章 简单密码3.素数素数 素数素数p是那些不存在因子是那些不存在因子d整数整数1d p1/2；定理：定理：每一个正整数都能够分解为素数乘积，每一个正整数都能够分解为素数乘积，而且这种分解是唯一。而且这种分解是唯一。12=22x3 35=5x7 (1)对于每一个素数对于每一个素数p，整除，整除gcd(m,n)p方幂，是既方幂，是既整除整除m又整除又整除np方幂最小值。方幂最小值。(2)两个方幂中较大一个便组成了最小公倍数。两个方幂中较大一个便组成了最小公倍数。举例：举例：3960=23x32x5x11 400=24x52 则：则：gcd(3960,400)=23x5=40 lcm(3960,400)=24x32x52x11=39600第40页中南大学信息科学与工程学院计算机系 段桂华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次概率为：次概率为：举例举例：投币。假设一枚公平硬币朝上或朝下投币。假设一枚公平硬币朝上或朝下 几率是相等，且每次投币是独立。几率是相等，且每次投币是独立。分析：分析：统计一个统计一个n次投掷过程：次投掷过程：2n任何单个序列出现概率是任何单个序列出现概率是1/2nn次投掷恰好有次投掷恰好有k次正面朝上概率是：次正面朝上概率是：第41页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月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。第一章 简单密码证实：证实：先计算出没有两种完全相同结果出现概先计算出没有两种完全相同结果出现概 率率p，则出现两次相同结果概率，则出现两次相同结果概率p=1-p。第42页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 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+)-x第一章 简单密码第43页中南大学信息科学与工程学院计算机系 段桂华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-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 第一章 简单密码第44页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月作业：作业：(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乘法逆。乘法逆。第一章 简单密码第45页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月 古典密码两大机制：古典密码两大机制：代替密码：代替密码：字母表范围内替换；字母表范围内替换；换位密码：换位密码：在消息内变换字母位置。在消息内变换字母位置。2.1代替密码代替密码 1.描述描述 密钥是字母表任意组合，有一个明密对应表；密钥是字母表任意组合，有一个明密对应表；密钥空间巨大：密钥空间巨大：26!；单表代替密码两个特例：移位密码和仿射密码。单表代替密码两个特例：移位密码和仿射密码。2.举例举例 首先选加密表；为了便于记忆，协商一个密钥：首先选加密表；为了便于记忆，协商一个密钥：DO YOU LIKE THIS BOOK 去掉重复字母，再进行补充，形成加密表：去掉重复字母，再进行补充，形成加密表：abcdefghijklmnopqrstuvwxyz DOYULIKETHSBACFGJMNPQRVWXZ第二章 代替与换位第46页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第二章 代替与换位2.2 换位密码换位密码 1.机制：机制：单个字符不变而位置改变。单个字符不变而位置改变。如将文本翻转：明文如将文本翻转：明文 computersystems 密文密文 SMETSYSRETUPMOC 2.特点：特点：(1)密文长度与明文长度相同；密文长度与明文长度相同；(2)唯密文攻击可能得到各种不一样破译结果；唯密文攻击可能得到各种不一样破译结果；如如 keeppeek；liveevilvile 3.分组换位密码分组换位密码 针对固定大小分组进行操作。针对固定大小分组进行操作。举例：明文举例：明文 can you understand (1)列换位法列换位法 设密钥设密钥k=4，将明文进行分组排列，将明文进行分组排列第47页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月canyouunderstand按列按列读出读出密文：密文：CODTAUEANURNYNSDCANYOUUNDERSTAND按行按行读出读出明文：明文：canyouunderstand明文：明文：canyouunderstand按按4 4个字符一行分组排列个字符一行分组排列按按4 4个字符一列分组排列个字符一列分组排列1 2 3 41 2 3 4第二章 代替与换位第48页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月按列按列 读出读出t y p ecanyouunderstand密文：密文：YNSDNURNCODTAUEACANYOUUNDERSTAND按行按行读出读出明文：明文：canyouunderstand明文：明文：canyouunderstand按按4 4个字符一行分组排列个字符一行分组排列按type(3,4,2,1)填入1 2 3 43 4 2 1 YNSD NURN CODT AUEA(2)密钥为字符串密钥为字符串type1234按密钥长度分组按密钥长度分组第二章 代替与换位第49页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月(3)矩阵换位法：置换矩阵作为密钥矩阵换位法：置换矩阵作为密钥明文：明文：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密文：密文：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解密置换矩阵：解密置换矩阵：说明：说明：第二章 代替与换位第50页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第二章 代替与换位2.3 频率攻击频率攻击1.原理：原理：利用自然语言频率攻击利用自然语言频率攻击 字母出现频率有规律：字母出现频率有规律：e:11.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 第51页中南大学信息科学与工程学院计算机系 段桂华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第52页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第二章 代替与换位4.举例：举例：对代替密码攻击对代替密码攻击 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.举例：举例：对换位密码攻击对换位密码攻击 ESROL VIERD第53页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月第二章 代替与换位作业：作业：(1)解密由仿射密码加密密文：解密由仿射密码加密密文：VCLLCP BKLC LJKX XCHCP(2)解密用简单换位密码加密密文：解密用简单换位密码加密密文：EAGGAR DAIREP第54页中南大学信息科学与工程学院计算机系 段桂华2010年年9月月3.1 群群 1.二元运算二元运算 定义：定义：设设s为集合，函数为集合，函数f:s ss称为称为s上二上二元运算或代数运算。满足：元运算或代数运算。满足：可计算性：可计算性：s中任何元素都能够进行这种运算；中任何元素都能够进行这种运算；单值性：运算结果唯一；单值性：运算结果唯一；封闭性：封闭性：