太原理工大学信息安全技术与应用-第二章密码技术基础

信息安全技术与应用,第2章密码技术基础,引言,密码技术是实现网络信息安全的核心技术，是保护数据最重要的工具之一。密码技术以保持信息的机密性，实现秘密通信为目的。密码技术建立在密码学的基础之上，密码学包括两个分支：密码编码学和密码分析学。,信息安全技术与应用,信息安全技术与应用,2.1密码学理论基础,信息安全定义信息安全是为防范计算机网络硬件、软件、数据偶然或蓄意破环、篡改、窃听、假冒、泄露、非法访问和保护网络系统持续有效工作的措施总和；信息安全保护范围信息安全、网络安全、计算机系统安全和密码安全涉及的保护范围不同；,信息论基础知识,信息论是一门关于信息的本质，用数学理论研究、描述度量信息的方法，以及传递处理信息的基本理论的科学。信息是人们通过对事物的了解消除的不确定性。信息的各种不同的信号形式是可以识别、转换、复制、存储、处理、传播和传输的。传播或传输信息的过程称为通信。,信息安全技术与应用,信息熵,信息量是表示事物的可确定度、有序度、可辨度（清晰度）、结构化（组织化）程度、复杂度、特异性或发展变化程度的量。熵是表示事物的不确定度、无序度、模糊度、混乱程序的量。香农的信息熵公式为：H(X)=P(Xi)I(Xi)=P(Xi)log2P(Xi)i=1,2,n,信息安全技术与应用,数论基础知识,数论是研究整数性质的一个数学分支，同时也是密码技术的基础。数论中许多基本内容在现代密码体制、数字签名、密钥分配与管理、身份认证等方面都有非常重要的应用。,信息安全技术与应用,整除,定义2.1设a,b是任意两个整数，其中a0。如果存在整数q使得b=aq成立，那么就说b可以被a整除，记为a|b且称b是a的倍数。a是b的因数(或称约数、除数、因子)。b不能被a整除可以记作。,信息安全技术与应用,素数,定义2.2设整数p0。如果它除了1，p显然因数外没有其他的因数，则p为素数，也叫不可约数，或称p是不可约的。若a0,1且a不是素数，则a称为合数。,信息安全技术与应用,最大公因数,定义2.3设是k个整数，如果，则称b是的公因数。定义2.4若是k个不全为零的整数，它们的公因数中最大的一个公因数叫做最大公因数，记作：()或。当时，称互素或互质。,信息安全技术与应用,最小公倍数,定义2.5设是k个整数。若m是这k个数的倍数，则m叫做这k个数的一个公倍数的所有公倍数中的最小正整数叫做最小公倍数，记为或。,信息安全技术与应用,同余,定义2.6设n是一个正整数，对任意两个整数a、b，若n|(a-b)，则称a和b模n同余，记为ab(modn)，整数n称为模数。性质：（1）自反性：aa(modn)；（2）对称性：若ab(modn)，则ba(modn)；（3）传递性：若ab(modn)，bc(modn),则ac(modn)；,信息安全技术与应用,定理2.9整数a、b对模数m同余的充分必要条件是m|(a-b)定理2.10设m是一个正整数，a、b是两个整数，则ab(modm)的充要条件是存在一个整数k使得：a=b+km定理2.11设m是一个正整数，是四个整数如果，则：（1）；（2）。,信息安全技术与应用,欧拉（Euler）函数,定义2.7设m是一个正整数，则m个整数0，1，m-1中与m互素的整数的个数，记作，通常叫做欧拉(Euler)函数。定理2.12若p是素数，则。定理2.13若p是素数，k是大于等于1的整数，则。定理2.14若m，n是互素的两个正整数，则定理2.15任意整数,根据定理2.2有标准分解式，则,信息安全技术与应用,定理2.16（欧拉定理）设m是大于1的整数，如果a是满足（a,m）=1的整数，则例2.6设m=11，a=2，有(2,11)=1，故定理2.17（费马小定理）设p是素数，则,信息安全技术与应用,计算复杂性基础知识,计算复杂性理论是研究用计算机求解问题的难易程度问题是指一个要求给出解释的一般性提问，通常含有若干个未定参数或自由变量。算法是指完成一个问题的求解过程所采用的方法和计算步骤。如果把问题P的任意一个实例作为算法A的输入，A在有限步骤之内总能输出关于此实例的正确答案，就说算法A可解问题P。对于一个问题P，如果存在一个算法A可解问题P，称问题P是算法可解的。,信息安全技术与应用,算法复杂性,算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。以某个特定的基本步骤为单元，完成计算过程所需的总单元数称为算法的时间复杂性，或时间复杂度，记为T(n)；以某个特定的基本存储空间为单元，完成计算过程所用的存储单元数，称为算法的空间复杂性或空间复杂度，记为S(n)一个算法的计算复杂性用符号“O”表示其数量级。,信息安全技术与应用,问题的复杂性,问题的复杂性是指这个问题本身的复杂程度，是问题固有的性质问题的复杂性由在图灵机上解其最难实例所需的最小时间与空间决定，还可以理解为由解该问题的最有效的算法所需的时间与空间来度量。在确定型图灵机上可用多项式时间求解的问题，称为易处理的问题。易处理的问题的全体称为确定性多项式时间可解类，记为P类。,信息安全技术与应用,NPC问题,对于很难找到多项式时间算法的问题，或者根本没有多项式时间的算法问题，如果给定该问题的一个答案，可以在多项式时间内判断答案的正确性，从而验证一个解是否正确的问题称为NP问题。NP问题的全体称为非确定性多项式时间可解类，记为NP类。NP类中还有一类问题称为NP完全类，记为NPC。NPC是NP类中困难程度最大的一类问题现在的密码算法的安全性都是基于NPC问题的,信息安全技术与应用,2.2密码系统与加密标准,将明文（Plaintext）转换成密文（Ciphertext）的过程称为加密（Encryption），加密变换时使用的数学方法称为加密算法；将密文转换成明文的过程称为解密（Decryption），解密变换时使用的数学方法称为解密算法，解密算法是加密算法的逆过程；研究信息加密的技术和研究破解密码的密码分析技术统称为密码学；控制加密和解密的参数称为密钥，密钥是一串随机字符；密钥全体称为密钥空间，密钥越长，加密就越健壮。,信息安全技术与应用,信息安全技术与应用,对称加密体制,加密和解密使用同一密钥就称为对称式加密、常规加密、单密钥、秘密密钥、共享密钥体制；加密和解密使用的密钥称为对称密钥或秘密密钥；优点是加密和解密速度快，可对大量信息加密；缺点是密钥管理和分发不安全，至少有两人持有密钥，所以任何一方都不能完全确定对方手中的密钥是否已经透露给第三者。,信息安全技术与应用,非对称加密体制,加密和解密使用不同密钥就称为非对称、公开密钥、双密钥加密体制；两个密钥必需配对使用，分别称为公钥和私钥，组合在一起称为密钥对；公钥可以对外公布，私钥只有持有人知道；优点是密钥管理和分发安全，支持信息加密与数字签名；缺点是加密速度慢，不适合对大量信息加密。,信息安全技术与应用,分组密码与序列密码体制,分组密码将固定长度的明文分组加密为相同长度的密文分组；分组密码体制的密文与被加密的明文分组在整个明文中的位置无关；序列密码体制以位或字节为加密单位，以流的形式处理序列密码体制的密文与被加密的明文在整个明文中的位置有关。,信息安全技术与应用,替代与置换技术,经典加密主要采用了替代（Substitution）与置换（Permutation）技术；替代技术将明文中的元素用其他元素替代而形成密文；置换技术将明文中的元素重新排列；著名的凯撒密码（CaesarCipher）和维吉尼亚密码（VigenereCipher）使用了替代技术；替代具有扰乱作用，置换具有扩散作用；扰乱（Confusion）和扩散（Diffusion）是保障算法强度的两个关键机制，也是现代密码系统设计的基础。,信息安全技术与应用,扰乱和扩散,通常明文信息具有一定的统计特征，统计特征有可能反映到密文中，采用统计分析有可能解析出密钥；扰乱机制使密文的统计特征与明文和加密密钥的关系尽可能复杂化；扩散机制使明文和密钥的每个字符影响尽可能多的密文字符取值，扩散明文和密钥的统计特征；如加密算法满足下列任意一个条件，则称算法在计算上是安全的；（1）破译密码的成本超过被加密信息的价值；（2）破译密码的时间超过被加密信息的生命周期。,2.3信息加密算法,信息安全技术与应用,对称密钥-数据加密标准DES,DES(DataEncryptionStandard)是典型的对称密钥加密体制，1976年美国国家标准局颁布，后被国际标准化组织接受作为国际标准；加密和解密使用同一算法，用56位密钥对64位分组加密，输出不同的64位分组；DES加密算法还有一些变形，例如，高级数据加密标准AES（AdvancedEncryptionStandard）、三重DES、广义DES等；DES运算速度快，但密钥短，降低了保密强度；其安全性依赖于密钥的管理，多用于民用领域。,信息安全技术与应用,对称密钥-国际数据加密算法IDEA,国际数据加密算法IDEA（InternationalDataEncryptionAlgorithm）由XuejiaLai和JamesL.Massey在DES的基础上发展得到；采用128位密钥，比DES具有更高的速度，加密速度可达100MB/s；IDEA适合对大量明文信息快速加密，于1990年正式公布。,RSA加密算法,1.生成密钥（1）任意选取两个不同的大素数p,q。（2）计算n=p*q,在这指的是Euler函数。（3）任意选取一个大整数e，满足且整数e用做加密钥。（4）计算解密钥d,满足。即d是e关于模乘的逆元，由e的定义，d存在唯一值。（5）输出公钥,保存私钥。,信息安全技术与应用,2.加密操作选定,把明文分成长度为k的组块。对每个明文分组m，m在0到(n-1)之间。加密操作为：3.解密操作得到密文分组c，解密操作为：,信息安全技术与应用,信息安全技术与应用,RSA公开密钥加密算法,在Diffie-Hellman算法的基础上，Rivest、Shamir和Adleman三人1977年提出了RSA公开密钥算法算法以发明人的首字母命名；RSA密钥管理简单，公开密钥可以象电话号码公开，用户只需一个私有密钥即可实现保密通信；RSA加密速度慢，比DES大约慢1000倍左右，主要用于短信息加密。,信息安全技术与应用,非对称密钥加密体制,Diffie和Hellman于1976年首次提出了公开密钥加密体制的思想；公开密钥加密体制主要有Diffie-Hellman算法、RSA算法、ElGamal算法、数字签名算法DSA（DigitalSignatureAlgorithm）和椭圆曲线加密算法等；公开密钥加密体制提供了加密和验证的能力，既能用于数据加密也能用于数字签名；加密：用公钥加密，用私钥解密；签名：用私钥签名，用公钥验证。,算法描述,假定有两个全局公开的参数：素数q和q的一个原根r，对于用户A和B交换密钥的方法描述如下：（1）用户A选择一个作为私有密钥的随机数XAq，并计算公开密钥，A将XA秘密保存而将YA公开给用户B；（2）用户B选择一个作为私有密钥的随机数XBq，并计算公开密钥，B将XB秘密保存而将YB公开给用户A；（3）用户A计算密钥，用户B计算密钥；,信息安全技术与应用,；,由于：由此，用户A和B得到一个共享的密钥K=KA=KB。因为XA，XB保密，由离散对数难解性可知，仅通过公开信息q,r,YA,YB是很难破解出K的。,信息安全技术与应用,ElGamal加密算法,密钥对产生方法如下：选择一个素数p，两个随机数g和x，g,x0,p-1，计算y=gx(modp)，则公钥k1=(y,g,p)，私钥k2=x。(1)加密变换。对于消息m，秘密选取一个随机数k0,p-1，且gcd(k,p-1)=1，然后计算：c1=gkmodp;c2=mykmodp。c1与c2并联构成密文，即密文c=(c1，c2)，因此密文的长度是明文的两倍。(2)解密变换。由加密变换可知：c2(c1x)-1=myk(gxk)-1=mgxkg-xkmmodp所以：m=c2(c1x)-1modp。,信息安全技术与应用,2.4信息加密产品简介,PGP（PrettyGoodPrivacy）是当前国际上非常著名的基于公用密钥或非对称密钥加密体制的开放源码信息保密通信软件;最早由支持开放源码和崇尚隐私的PhilZimmermann开发;1991年发布到InternetWeb站点;,信息安全技术与应用,信息安全技术与应用,PGP简介,PGP公司在其网站（,信息安全技术与应用,PGP加密与解密原理,PGP将对称密钥和非对称密钥加密体制的优点结合在一起，是一个混合加密系统；当使用PGP加密明文时，PGP首先压缩明文，在提高加密强度的同时，也提高了传输速度；PGP生成一次性会话密钥对明文加密，会话密钥