计算机安全与保密1-2

计算机安全与保密辽宁大学信息学院王妍[e-mail]教材《实用密码学与计算机数据安全》（第二版），李克洪，王大玲，董晓梅主编，东北大学出版社，2001。课程内容1绪论2密码学的数学基础3传统加密方法4对称密钥算法5公开密钥算法6序列密码7密码技术8网络安全问题9Internet安全技术10计算机病毒概论1绪论1.1计算机安全及信息保密的意义1.2计算机安全与信息保密研究的内容1.3密码学及计算机安全技术的发展1.1计算机安全及信息保密的意义Internet的迅速普及，利用计算机犯罪的案例与日俱增绝大多数的新用户缺乏网络和信息安全方面的经验网络技术的发展带来一系列问题攻击者非法接收甚至修改一些秘密信息非法用户冒充合法用户操纵计算机终端获取机密情报非法信息进入计算机系统合法信息遭到破坏文件、邮件传输携带病毒网络配置的复杂性导致的安全性问题系统自身的缺陷入侵者的攻击他们在不懈努力，试图攻破各种系统的安全方案出于政治的、经济的、商业的、或者个人的目的病毒及破坏性程序的制造者：善意地和恶意地破坏系统网络黑客：试图从网络内部或外部进行非法的入侵，攻击系统，达到破坏系统或窃取信息的目的网络和计算机技术的爱好者：为了显示其能力在Internet上大量公开的攻击手段和攻击程序……人为的破坏和误操作网络安全事件的报道（1）1986年，LBL实验室的计算机系统上发现黑客在克格勃指使下入侵美国军方计算机网络1988年，Morris在Internet上散布蠕虫病毒(Worm)，使当时网上10%（约6000台）的计算机瘫痪前苏联克格勃人员曾突破美国花旗银行装备的防火墙和其它高技术的防范措施，成功地通过计算机网络转移了1160万美元的巨资——“华尔街日报”报道(1995.8.21)据统计，到1996年网上的计算机平均每20秒钟被黑客成功地入侵一次——美国“金融时报”报道(1996.4.16)网络安全事件的报道（2）据FBI的报告称每年约有75%的美国公司因计算机犯罪而蒙受损失一起计算机犯罪的平均损失是50万美元，而普通刑事案件的平均损失仅为2千美元1998年7月21-22日，江西中国公用多媒体信息网（169）连续遭受攻击，导致全省169信息网系统瘫痪2000年初，Yahoo、eBay等著名网站相继遭受到的大规模的拒绝服务攻击导致服务中断，在全球范围内引起了巨大的震动网络安全事件的报道（3）统计表明，有关网络安全事件报告的数量迅速增加1988年：61989年：1321990年：2521991年：4061992年：7731993年：13341994年：23411996年：25731998年：37341999年：98592000年：217561.2计算机安全与信息保密研究的内容信息加密的算法、体制、协议及相关技术操作系统的安全数据库安全计算机网络安全电子商务安全计算机病毒的防治信息加密、解密的概念A、B保密通信：A如何能确信他的信不会被第三方窃取；B如何能确信他收到的信是A发给他的。明文：人们能够读懂的信息密文：人们难以理解的信息加密：将明文变换成密文的过程解密：密文还原成原来的明文的过程C=E（M）信源信宿信道明文M加密密文C密文C解密明文MM=D（C）算法与密钥算法：用于加密和解密的数学函数。密钥：一串适当长度的字符串或数字串，可以控制加密和解密的过程。密钥空间：密钥的取值范围。C=E（M）信源信宿信道明文M加密密文C密文C解密明文MM=D（C）加密密钥解密密钥加密和解密使用同一密钥：加密密钥=解密密钥=K加密函数为：EK(M)=C解密函数为：DK(C)=M且DK(EK(M))=M加密和解密使用不同密钥：加密密钥=K1，解密密钥=K2加密函数为：EK1(M)=C解密函数为：DK2(C)=M且DK2(EK1(M))=M对称算法（传统算法）：加密密钥与解密密钥相同分组算法：将明文分组，每次加密一组序列密码:每次加密一位或一字节的明文公开密钥算法（非对称算法）：加密与解密使用不同的密钥解密密钥很难由加密密钥计算得到加密密钥：公开密钥（PublicKey）解密密钥：秘密密钥（PrivateKey）密码分析密码学:密码编码学：研究加密、解密的算法密码分析学：研究在不知道密钥的情况下，恢复明文的科学1.3密码学及计算机数据安全技术的发展密码学的历史密码学的发展：传统密码学阶段：计算机出现以前计算机密码学阶段：1976年以后：公开密钥密码学古典实例（1）凯撒密码：公元前50年例：明文：Systemmodels密文：Vbvwhpprghov加密方法：简单代替明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ密文：DEFGHIJKLMNOPQRSTUVWXYZABC古典实例（2）双轨密码：1861~1865年例：明文：DiscreteandSystem密文：DsrtadytmIceensse加密方法：Dsrtadytmiceensse古典实例（3）网格加密法：中国例：密文：王先生：来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。弟：李明2001年11月7日网格加密法：中国例：密文：王先生：来信收悉，你的盛情难以报答。我已在昨天抵达广州。秋雨连绵，每天需备伞一把。大约本月中旬即可返回，再谈。弟：李明2001年11月7日明文：情报在雨伞把中。兽栏法：明文：System密文：ABCDEFGHIJ.K..LM.N..OP.Q..RS:T::UV:W::XY:Z::.：：：：.密文字母表：2密码学的数学基础2.1信息论2.2复杂性理论2.3初等数论2.4因数分解2.5素数的产生2.6有限域内的离散对数2.7单向哈希函数2.1信息论2.1.1熵与疑义度2.1.2自然语言率2.1.3密码系统的安全性2.1.4确定性距离2.1.5混乱与扩散2.1.1熵与疑义度假设所有的消息都有相等的可能性。一条消息中的信息量：要将消息中所有可能的含意编码所需的最少的比特位数。例如：数据库中表示“星期”的字段包含不超过3bit的信息。000~110表示星期一到星期日，111不用。熵：用来形式化地衡量一条消息M中的信息量，记为H(M)。当用比特来衡量时，为log2n，其中n为消息的状态个数，假设所有状态有相等的出现概率。疑义度：消息的熵同时也可衡量其不确定性（疑义度），即将消息隐藏在密文中时，要破译它所需的明文比特数。2.1.2自然语言率自然语言率：对于给定的一种语言，其自然语言率为r=H(M)/N其中N为消息长度。英语的自然语言率：当N较大时，英语的自然语言率1.0比特/字母～1.5比特/字母绝对语言率：每个字符编码的最大比特数，这里假设每个字符序列出现的机会相等。若语言中有L个字母，则绝对语言率为：R=log2L为单个字母的最大熵。英语的绝对语言率：log2264.7比特/字母冗余度：语言的冗余度记为D，定义为：D=R-r其中，R为绝对语言率，r为自然语言率。英语：r=1.3比特/字母，则D=3.4比特/字母。2.1.3密码系统的安全性绝对安全的密码系统：一次一密（密钥与消息本身一样长，且密钥不重复使用）密码系统的熵：衡量密钥空间K的大小的一个标准，通常是密钥数以2为底的对数。H（K）=log2k2.1.4确定性距离对于长度为n的消息，能够将一段密文消息解密成与原始明文同种语言的可懂文本的密钥个数为：2H(K)-nD-1确定性距离：能够唯一地确定密钥的最短的密文长度的近似值。对称密码系统的确定性距离：定义为密码系统的熵除以语言的冗余度。U=H（K）/D理想安全的密码系统：确定性距离无限大的密码系统。2.1.5混乱与扩散混乱：在加密变换中，让密钥与密文的关系尽可能复杂的做法。实现混乱的方法：代替扩散：在加密过程中，尽可能将明文的统计特性在密文中消除。实现扩散的方法：换位2.2复杂性理论2.2.1算法复杂性2.2.2问题复杂性2.2.1算法复杂性算法的复杂性通常由两个变量来衡量：T（时间复杂性）和S（空间复杂性，或存储需求）。T和S都用n的函数来表示，其中n为输入的大小。2.2.2问题复杂性图灵机：一个有限状态机，具有无限的读写存储磁带，是一个理想化的计算模型。问题：易解的问题：可以在多项式时间内求解难解的问题：只能在指数时间内求解不确定的问题：找不出解决的算法，不考虑算法的时间复杂性2.3初等数论2.3.1模运算2.3.2素数2.3.3最大公因数2.3.4乘法逆元素2.3.5Fermat小定理及欧拉函数2.3.6中国剩余定理2.3.7二次剩余2.3.8Legendre（勒让得）符号2.3.9Jacobi（雅各比）符号2.3.10生成元2.3.11有限域中的计算2.3.1模运算同余：如果a=b+kn，k为整数，则ab（modn）amodn：a模n操作，表示a除以n的余数，为0到n－1之间的整数。例如：(7＋9)mod12=16mod12=4模运算（+、－、）满足交换律、结合律和分配律。按模计算原理：对中间结果作模运算与做完了全部运算后再做模运算结果相同。按模指数运算：ammodn将指数运算作为一系列乘法运算，每次做一次模运算。例：a8modn=((a2modn)2modn)2modn当m不是2的乘方时，将m表示成2的乘方和的形式。例如：25=(11001)2，即25=24+23+20a25modn=(a16a8a)modn=((((a2)2)2)2((a2)2)2a)modn=((((a2a)2)2)2a)modn适当存储中间结果，则只需6次乘法：(((((((a2modn)a)modn)2modn)2modn)2modn)a)modn2.3.2素数素数（质数）：大于1的整数，只能被1和本身整除。有无穷多个素数。如：2，73，2521，2365347734339，2756839-12.3.3最大公因数公因数：两个整数a，b的公因数定义为能同时整除a，b的所有整数。最大公因数：a与b的公因数中最大的一个公因数，记为gcd(a，b)。互素（互质）：两个整数称为互素的，如果它们除了1以外没有其他的公因数，即gcd(a,b)=1。最大公因数的求法：辗转相除法例如：求gcd(15,36)36=152+615=62+36=32+0因此，gcd(15,36)=3原理：若ab(modc)，则gcd(a,c)=gcd(b,c)这里，gcd(15,36)=gcd(15,6)=gcd(6,3)=3求最大公因数的Euclid算法2.3.4乘法逆元素求x，满足(a·x)modn=1,即xa-1(modn)当a与n互素时,方程xa-1(modn)有唯一解；当a与n不互素时,此方程无解。如果n为素数，则从1到n-1的任意整数都与n互素，即在1到n-1之间都恰好有一个关于模n的乘法逆元。求乘法逆元：扩展的Euclid算法例：求5关于模14的乘法逆元辗转相除：14=52+45=4+1逆推：1=5-4=5-（14-52）=53-14因此，5关于模14的乘法逆元为3。练习练习：求17关于模26的乘法逆元。答案：2326=17+91=9-817=9+8=9-(17-9)9=8+1=92-17=(26-17)2-17=262-173=17(-3)+262(1723-2615)2.3.5Fermat小定理及欧拉函数Fermat小定理：如果m为素数，a不能被m整除，则am-11(modm)模n的简化剩余集：模n的完全剩余集的一个子集，其中每个元素与n互素。欧拉函数：记为(n)，为模n的简化剩余集中元素的个数。如果n是素数，则(n)=n-1设n=p1r1p2r2