信息安全数学基础讲义

信息安全数学基础信息科学与工程学院中南大学信息科学与工程学院计算机系段桂华2010年9月网络信息的安全威胁网上犯罪形势不容乐观；有害信息污染严重；网络病毒的蔓延和破坏；网上黑客无孔不入；机要信息流失与信息间谍潜入；网络安全产品的自控权；信息战的阴影不可忽视。引言中南大学信息科学与工程学院计算机系段桂华2010年9月网络通信的困境引言中南大学信息科学与工程学院计算机系段桂华2010年9月信息完整用户认证网站认证密钥管理不可抵赖数据安全我们要保护什么呢？引言中南大学信息科学与工程学院计算机系段桂华2010年9月网络安全体系的五类服务访问控制技术身份鉴别技术加密技术信息鉴别技术访问控制服务对象认证服务保密性服务完整性服务防抵赖服务引言中南大学信息科学与工程学院计算机系段桂华2010年9月网络安全体系的五类服务访问控制服务：根据实体身份决定其访问权限；身份鉴别服务：消息来源确认、防假冒、证明你是否就是你所声明的你；保密性服务：利用加密技术将消息加密，非授权人无法识别信息；数据完整性服务：防止消息被篡改，证明消息与过程的正确性；防抵赖服务：阻止你或其他主体对所作所为的进行否认的服务，可确认、无法抵赖。引言中南大学信息科学与工程学院计算机系段桂华2010年9月引言解决方法：加密如何实现保密性？密码分析公共网络AliceBob加密密钥解密密钥Eve中南大学信息科学与工程学院计算机系段桂华2010年9月引言解决方法：数字摘要如何实现完整性？无法篡改z消息篡改公共网络AliceBobm,zm,zz=hk(m)y=hk(m)Eve如果y≠zm被篡改中南大学信息科学与工程学院计算机系段桂华2010年9月引言解决方法：数字签名如何实现不可否认性？否认公共网络AliceBobTrent谁是正确的？举报中南大学信息科学与工程学院计算机系段桂华2010年9月引言解决方法：密码技术公共网络AliceBob假冒Eve身份鉴别：就是确认实体是它所声明的，身份鉴别服务提供关于某个实体身份的保证，以对抗假冒攻击。如何鉴别通信对象的身份？中南大学信息科学与工程学院计算机系段桂华2010年9月本课程的相关知识点简单的密码学基础：密码技术是信息安全的核心技术；需要掌握一些密码学基础知识。相关的数学知识：密码技术的实现依赖于数学知识；掌握密码技术涉及的相应数学基础知识点。参考教材：(1)密码学导引,机械工业出版社,PaulGarrett著,吴世忠等译；(2)信息安全数学基础,武汉大学出版社,李继国等主编。引言中南大学信息科学与工程学院计算机系段桂华2010年9月什么是密码技术？窃听公共网络AliceBobEve篡改伪造加密密钥解密密钥密文密码学是一门古老而深奥的学科,包括密码编码学和密码分析学;通信双方按照某种约定将消息的原形隐藏。密码系统:明文,密文,加解密算法,密钥。引言中南大学信息科学与工程学院计算机系段桂华2010年9月密码学的起源与发展三个阶段：1949年之前：密码学是一门艺术；1949～1975年：密码学成为科学；1976年以后：密码学的新方向－－公钥密码学。1949年之前(手工阶段的初级形式)隐写术：隐形墨水、字符格式的变化、图像；举例：芦花丛中一扁舟，俊杰俄从此地游；义士若能知此理，反躬难逃可无忧。25871539258314697314697153582486217893引言中南大学信息科学与工程学院计算机系段桂华2010年9月1949~1975年(机械阶段)：现代密码出现1949年香农Shannon提出“保密系统信息理论”；提出：数据的安全基于密钥而不是密码算法。1976年以后(计算机阶段)：公钥密码诞生1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了不对称密钥密码；1977年Rivest,Shamir&Adleman提出了RSA公钥算法；90年代出现椭圆曲线ECC等其他公钥算法。引言中南大学信息科学与工程学院计算机系段桂华2010年9月对称密钥密码算法进一步发展1977年DES正式成为标准；80年代出现“过渡性”的“postDES”算法，如IDEA、RCx、CAST等；90年代对称密钥密码进一步成熟，Rijndael、RC6、MARS、Twofish、Serpent等出现；2001年Rijndael成为DES的替代者AES。2004年6月美国NIST提出最新信息加密技术----量子密码。2004年山东大学王小云教授成功破解处理电子签名的MD5。引言中南大学信息科学与工程学院计算机系段桂华2010年9月密码算法的分类按照保密的内容分受限制的算法：保密性基于保持算法的秘密。基于密钥的算法：保密性基于密钥的保密。Kerchoffs原则1883年Kerchoffs第一次明确提出了编码的原则：保密性完全依赖于密钥，算法应该公开。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为古典密码和现代密码的分界线。引言中南大学信息科学与工程学院计算机系段桂华2010年9月基于密钥的算法，按照密钥的特点分类：对称密码算法：又称秘密密钥算法或单密钥算法，加密密钥和解密密钥相同，或可以容易地从一个推出另一个。特点：加密速度快；密钥管理复杂，主要用于加密信息。非对称密钥算法：又称公开密钥算法，加密密钥和解密密钥不相同，而且很难从一个推出另一个。特点：密钥管理简单，但加密速度慢，用于加密会话密钥和用于数字签名。实际网络应用中，常采用非对称密码来交换对称密码算法的密钥。引言中南大学信息科学与工程学院计算机系段桂华2010年9月经典的古典密码算法主要有：代替密码：将明文字符用另外的字符代替，典型的有恺撒密码、仿射密码、维吉尼亚密码等；换位密码：明文的字母保持相同，但顺序打乱。经典的现代密码算法有很多种，最通用的有：DES：数据加密标准，对称密码算法，用于加密；AES:高级加密标准，对称密码算法，用于加密；引言中南大学信息科学与工程学院计算机系段桂华2010年9月RSA：最流行的公钥密码算法，加密和数字签名；ECC：椭圆曲线密码，采用ElGamal算法，公钥密码算法，安全性高，密钥量小，灵活性好；DSA：数字签名算法，是数字签名的一部分，公钥密码算法，数字签名。MD5(SHA-1)：数字摘要算法，数字签名，保证消息的完整性。引言中南大学信息科学与工程学院计算机系段桂华2010年9月理论安全：攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。Shannon用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密密码本，不实用。实际安全：如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行。引言密码系统的安全中南大学信息科学与工程学院计算机系段桂华2010年9月四种基本攻击类型：唯密文攻击：攻击者只有一些密文；已知明文攻击：攻击者知道一些明文密文对；选择明文攻击：攻击者可以选择明文密文对；针对密钥的攻击：主要是针对公钥密码系统。穷举攻击：攻击者采用尝试方法穷举可能的密钥。当密钥空间较小时很有效。字典攻击是利用一些常用的单词进行组合。基本要求：任何一种加密系统都必须能够对抗唯密文攻击。目前的标准是：一个密码系统应当能够对抗选择明文攻击。引言密码系统的攻击中南大学信息科学与工程学院计算机系段桂华2010年9月第一章简单密码经典的简单密码：移位密码、一次一密乱码本、仿射密码。1.1移位密码1.Caesar密码：最简单的移位密码。原理：将消息中的每个字母前移3位或者后移3位。举例：allofgaulisdevidedintothreepartsDOORIJDXOLUGLYLGHGLQWRWKUHHSDUWU2.移位密码：改进Caesar密码：发送方和接收方协商一个密钥k，1≤k≤25，代表移动位数。中南大学信息科学与工程学院计算机系段桂华2010年9月3.攻击：穷举攻击：25种可能的密钥(密钥空间)；4.特点：对称密码：加密密钥和解密密钥相同；单表代替密码：所有的明文字母用同一种方法加密，即子密钥相同。1.2约简/整除算法1.n模m的约简：n除以m的余数r，0≤r|m|记作：r=n%m或者r=nmodm，m称为模数。计算：设a=|n|%|m|，则当n0时，n%m=|m|-a；当m0时，n%m=n%|m|。第一章简单密码中南大学信息科学与工程学院计算机系段桂华2010年9月举例：-10%7：10%(-7)：-10%(-7)：4，因为-10=7×(-2)+43，因为10=-7×(-1)+34，因为-10=-7×2+4注意：任何整数模m的约简都是非负数。2.乘法逆n模m的乘法逆t满足：n×t%m=1记作：t=n-1%m举例：2-1%5的值为：3-1%100的值为：3，因为3×2%5=167，因为67×3%100=1第一章简单密码中南大学信息科学与工程学院计算机系段桂华2010年9月4.乘法逆元的计算(1)穷举法：寻找满足条件的数。技巧：若t×n%m=-1，则n-1%m=m-t。33×3%100=-1，所以3-1%100的值为67。第一章简单密码3.命题设m≠0,±1为整数，x与m互素，则x有模m的乘法逆元。特别地，满足表达式ax+bm=1的任意整数a就是一个x模m的乘法逆元。假如y是x模m的乘法逆元，对于y’，若m|y-y’，那么y’也是x模m的乘法逆元；反之亦然。中南大学信息科学与工程学院计算机系段桂华2010年9月(2)欧几里德算法：举例：23-1%100方法：100-4×23=823-2×8=78-1×7=17-7×1=0所以：1=3×100-13×231=-13×23%10023-1%100=-13=871=3×100%23100-1%23=8-1%23=3算法：1=8-1×7=8-1×(23-2×8)=3×8-1×23=3×(100-4×23)-1×23=3×100-13×231-1-133-13011-7011-1011-2011-41002310=所以：3×100-13×23=1第一章简单密码中南大学信息科学与工程学院计算机系段桂华2010年9月1.3欧几里得算法用以寻找两个整数m和n的最大公因子d。使用该算法将x和y的最大公因子表示为：ax+by=gcd(x,y)的形式。1.举例描述两个整数513和614614-1·513=101513-5·101=8101-12·8=58-1·5=35-1·3=23-1·2=12.寻找整数a,b1=3-1·2=3-1·(5-1·3)=-1·5+2·3=-1·5+2·(8-1·5)=2·8-3·5=2·8-3·(101-12·8)=-3·101+38·8=-3·101+38·(513-5·101)=38·513-193·101=38·513-193·(614-1·513)=-193·614+231·513最大公因子为1193·614+231·513=1第一章简单密码中南大学信息科学与工程学院计算机系段桂华2010年9月2.乘法逆元的计算两个整数x和yx-y·q1=r1x1-y1·q2=r2x2-y2·q3=r3…xn-1-yn-1·qn=0xnyn2121221011xxxMMyqyy1111011xxxMyqyy111011gcd(,)nnnnnnnxxxMMyqyyabxaxbyxxycdy结论：当x和y互素时，gcd(x,y)为1，即可得到x-1%y为a，y-1%x为b。第一章简单密码中南大学信息科学与工程学院计算机系段桂华2010年9月3.举例0101011501141511421115656251525621121252125210abcd