信息安全数学基础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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息 安全 数学 基础 ppt 课件

链接地址:https://www.31ppt.com/p-1679155.html