第2章密码技术基础

1、信息安全技术与应用第第2章章密码技术基础密码技术基础引言引言 密码技术是实现网络信息安全的核心技术，是保护数据密码技术是实现网络信息安全的核心技术，是保护数据最重要的工具之一。最重要的工具之一。 密码技术以保持信息的机密性，实现秘密通信为目的。密码技术以保持信息的机密性，实现秘密通信为目的。 密码技术建立在密码学的基础之上，密码学包括两个分密码技术建立在密码学的基础之上，密码学包括两个分支：密码编码学和密码分析学。支：密码编码学和密码分析学。信息安全技术与应用信息安全技术与应用2.1 密码学理论基础密码学理论基础 信息安全定义信息安全定义信息安全是为防范计算机网络硬件、软件、数据偶然信息安全是

2、为防范计算机网络硬件、软件、数据偶然或蓄意破环、篡改、窃听、假冒、泄露、非法访问和或蓄意破环、篡改、窃听、假冒、泄露、非法访问和保护网络系统持续有效工作的措施总和；保护网络系统持续有效工作的措施总和； 信息安全保护范围信息安全保护范围信息安全、网络安全、计算机系统安全和密码安全涉信息安全、网络安全、计算机系统安全和密码安全涉及的保护范围不同；及的保护范围不同； 信息论基础知识信息论基础知识 信息论是一门关于信息的本质，用数学理论研究、描述信息论是一门关于信息的本质，用数学理论研究、描述度量信息的方法，以及传递处理信息的基本理论的科学。度量信息的方法，以及传递处理信息的基本理论的科学。 信息是人

3、们通过对事物的了解消除的不确定性。信息是人们通过对事物的了解消除的不确定性。 信息的各种不同的信号形式是可以识别、转换、复制、信息的各种不同的信号形式是可以识别、转换、复制、存储、处理、传播和传输的。传播或传输信息的过程称存储、处理、传播和传输的。传播或传输信息的过程称为通信。为通信。信息安全技术与应用信息熵信息熵 信息量是表示事物的可确定度、有序度、可辨度（清晰信息量是表示事物的可确定度、有序度、可辨度（清晰度）、结构化（组织化）程度、复杂度、特异性或发展度）、结构化（组织化）程度、复杂度、特异性或发展变化程度的量。变化程度的量。 熵是表示事物的不确定度、无序度、模糊度、混乱程序熵是表示事物

4、的不确定度、无序度、模糊度、混乱程序的量。的量。 香农的信息熵公式为：香农的信息熵公式为：H(X)=P(Xi) I(Xi)=P(Xi) log2 P(Xi) i=1,2,n信息安全技术与应用数论基础知识数论基础知识 数论是研究整数性质的一个数学分支，同时也是密码技数论是研究整数性质的一个数学分支，同时也是密码技术的基础。术的基础。 数论中许多基本内容在现代密码体制、数字签名、密钥数论中许多基本内容在现代密码体制、数字签名、密钥分配与管理、身份认证等方面都有非常重要的应用。分配与管理、身份认证等方面都有非常重要的应用。信息安全技术与应用整除整除 定义定义2.1设设a,b是任意两个整数，其中是任意

5、两个整数，其中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称为合数。称为合数。信息安全技术与应用最大公因数最

6、大公因数 定义定义2.3设设 是是k个整数，如果个整数，如果 ，则称则称b是是 的公因数。的公因数。 定义定义2.4 若若 是是k个不全为零的整数，它们的公个不全为零的整数，它们的公因数中最大的一个公因数叫做最大公因数，记作：因数中最大的一个公因数叫做最大公因数，记作： ( )或或 。 当当 时，称时，称 互素或互质。互素或互质。信息安全技术与应用kaaa,21kababab,21kaaa,21kaaa,21kaaa,21),gcd(21kaaa1),(21kaaakaaa,21最小公倍数最小公倍数 定义定义2.5 设设 是是k个整数。若个整数。若m是这是这k个数的倍个数的倍数，则数，则m叫做

7、这叫做这k个数的一个公倍数个数的一个公倍数 的所有公倍数中的最小正整数叫做最小公的所有公倍数中的最小正整数叫做最小公倍数，记为倍数，记为 或或 。信息安全技术与应用kaaa,21kaaa,21,21kaaa),(21kaaalcm同余同余 定义定义2.6 设设n是一个正整数，对任意两个整数是一个正整数，对任意两个整数a、b， 若若 n|(a-b) ，则称，则称a和和b模模n同余，记为同余，记为ab(mod n) ，整数，整数n称为模数。称为模数。 性质：性质：（1）自反性：）自反性： aa(mod n) ；（2）对称性：若）对称性：若 ab(mod n) ，则，则ba(mod n) ；（3）传

8、递性：若）传递性：若ab(mod n) ， bc(mod n) ,则则 ac(mod n) ；信息安全技术与应用 定理定理2.9整数整数a、b对模数对模数m同余的充分必要条件是同余的充分必要条件是m|(a-b) 定理定理2.10设设m是一个正整数，是一个正整数，a、b是两个整数，是两个整数， 则则 ab(mod m)的充要条件是存在一个整数的充要条件是存在一个整数k 使得：使得： a=b+km 定理定理2.11设设m是一个正整数，是一个正整数， 是四个整数是四个整数 如果如果 ， 则：（则：（1） ； （2） 。信息安全技术与应用2121,bbaa)(mod11mba )(mod22mba )

9、(mod2121mbbaa)(mod2121mbbaa欧拉（欧拉（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有标准分解式有标准分解式 ，则，则 信息

10、安全技术与应用)(m1)( pp) 1()(1pppkk)()()(nmmn2nkekeepppn2121)/11 ()/11)(/11 ()(21kpppnn 定理定理2.16（欧拉定理）设（欧拉定理）设m是大于是大于1的整数，如果的整数，如果a是满是满足（足（a,m）=1的整数，则的整数，则 例例2.6 设设m=11，a=2，有，有(2,11)=1， 故故 定理定理2.172.17（费马小定理）设（费马小定理）设p p是素数，则是素数，则信息安全技术与应用)(mod1)(mam10)11()11(mod1210)(modpaap计算复杂性基础知识计算复杂性基础知识 计算复杂性理论计算复杂性

11、理论是研究用计算机求解问题的难易程度是研究用计算机求解问题的难易程度 问题问题是指一个要求给出解释的一般性提问，通常含有若是指一个要求给出解释的一般性提问，通常含有若干个未定参数或自由变量。干个未定参数或自由变量。 算法算法是指完成一个问题的求解过程所采用的方法和计算是指完成一个问题的求解过程所采用的方法和计算步骤。步骤。 如果把问题如果把问题P的任意一个实例作为算法的任意一个实例作为算法A的输入，的输入，A在有在有限步骤之内总能输出关于此实例的正确答案，就说限步骤之内总能输出关于此实例的正确答案，就说算法算法A可解问题可解问题P。对于一个问题。对于一个问题P，如果存在一个算法，如果存在一个算

12、法A可可解问题解问题P，称问题，称问题P是是算法可解的算法可解的。信息安全技术与应用算法复杂性算法复杂性 算法的复杂性是算法效率的度量，是评价算法优劣的重算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。要依据。 以某个特定的基本步骤为单元，完成计算过程所需的总以某个特定的基本步骤为单元，完成计算过程所需的总单元数称为算法的时间复杂性，或时间复杂度，记为单元数称为算法的时间复杂性，或时间复杂度，记为T(n)； 以某个特定的基本存储空间为单元，完成计算过程所用以某个特定的基本存储空间为单元，完成计算过程所用的存储单元数，称为算法的空间复杂性或空间复杂度，的存储单元数，称为算法的空间复杂性或

13、空间复杂度，记为记为S(n) 一个算法的计算复杂性用符号一个算法的计算复杂性用符号“O”表示其数量级。表示其数量级。信息安全技术与应用问题的复杂性问题的复杂性 问题的复杂性是指这个问题本身的复杂程度，是问题固问题的复杂性是指这个问题本身的复杂程度，是问题固有的性质有的性质 问题的复杂性由在图灵机上解其最难实例所需的最小时问题的复杂性由在图灵机上解其最难实例所需的最小时间与空间决定，还可以理解为由解该问题的最有效的算间与空间决定，还可以理解为由解该问题的最有效的算法所需的时间与空间来度量。法所需的时间与空间来度量。 在确定型图灵机上可用多项式时间求解的问题，称为易在确定型图灵机上可用多项式时间求

14、解的问题，称为易处理的问题。易处理的问题的全体称为确定性多项式时处理的问题。易处理的问题的全体称为确定性多项式时间可解类，记为间可解类，记为P类。类。信息安全技术与应用NPC问题问题 对于很难找到多项式时间算法的问题，或者根本没有多对于很难找到多项式时间算法的问题，或者根本没有多项式时间的算法问题，如果给定该问题的一个答案，可项式时间的算法问题，如果给定该问题的一个答案，可以在多项式时间内判断答案的正确性，从而验证一个解以在多项式时间内判断答案的正确性，从而验证一个解是否正确的问题称为是否正确的问题称为NP问题。问题。 NP问题的全体称为非确定性多项式时间可解类，记为问题的全体称为非确定性多项

15、式时间可解类，记为NP类。类。 NP类中还有一类问题称为类中还有一类问题称为NP完全类，记为完全类，记为NPC。 NPC是是NP类中困难程度最大的一类问题类中困难程度最大的一类问题 现在的密码算法的安全性都是基于现在的密码算法的安全性都是基于NPC问题的问题的信息安全技术与应用2.2 密码系统与加密标准密码系统与加密标准 将明文（将明文（PlaintextPlaintext）转换成密文（）转换成密文（CiphertextCiphertext）的过程）的过程称为称为加密加密（EncryptionEncryption），），加密变换时使用的数学方法加密变换时使用的数学方法称为加密算法；称为加密算法

16、； 将密文转换成明文的过程称为将密文转换成明文的过程称为解密解密（DecryptionDecryption），解，解密变换时使用的数学方法称为解密算法，解密算法是加密密变换时使用的数学方法称为解密算法，解密算法是加密算法的逆过程；算法的逆过程； 研究信息加密的技术和研究破解密码的密码分析技术统称研究信息加密的技术和研究破解密码的密码分析技术统称为为密码学密码学； 控制加密和解密的参数称为控制加密和解密的参数称为密钥密钥，密钥是一串随机字符；，密钥是一串随机字符； 密钥全体称为密钥空间，密钥越长，加密就越健壮。密钥全体称为密钥空间，密钥越长，加密就越健壮。信息安全技术与应用信息安全技术与应用对称

17、加密体制对称加密体制 加密和解密使用同一密钥就称为加密和解密使用同一密钥就称为对称式加密对称式加密、常规、常规加密、单密钥、秘密密钥、共享密钥体制；加密、单密钥、秘密密钥、共享密钥体制；加密和解密使用的密钥称为加密和解密使用的密钥称为对称密钥对称密钥或或秘密密钥秘密密钥；优点是加密和解密速度快，可对大量信息加密；优点是加密和解密速度快，可对大量信息加密；缺点是密钥管理和分发不安全，至少有两人持有密缺点是密钥管理和分发不安全，至少有两人持有密钥，所以任何一方都不能完全确定对方手中的密钥钥，所以任何一方都不能完全确定对方手中的密钥是否已经透露给第三者。是否已经透露给第三者。信息安全技术与应用非对称

18、加密体制非对称加密体制 加密和解密使用不同密钥就称为加密和解密使用不同密钥就称为非对称非对称、公开密钥、公开密钥、双密钥加密体制；、双密钥加密体制；两个密钥必需配对使用，分别称为两个密钥必需配对使用，分别称为公钥公钥和和私钥私钥，组，组合在一起称为合在一起称为密钥对密钥对；公钥可以对外公布，私钥只有持有人知道；公钥可以对外公布，私钥只有持有人知道；优点是密钥管理和分发安全，支持信息加密与数字优点是密钥管理和分发安全，支持信息加密与数字签名；签名；缺点是加密速度慢，不适合对大量信息加密。缺点是加密速度慢，不适合对大量信息加密。信息安全技术与应用分组密码与序列密码体制分组密码与序列密码体制 分组密

19、码将固定长度的明文分组加密为相同长度的密分组密码将固定长度的明文分组加密为相同长度的密文分组；文分组； 分组密码体制的密文与被加密的明文分组在整个明文分组密码体制的密文与被加密的明文分组在整个明文中的位置无关；中的位置无关； 序列密码体制以位或字节为加密单位，以流的形式处序列密码体制以位或字节为加密单位，以流的形式处理理 序列密码体制的密文与被加密的明文在整个明文中的序列密码体制的密文与被加密的明文在整个明文中的位置有关。位置有关。信息安全技术与应用替代与置换技术替代与置换技术 经典加密主要采用了替代（经典加密主要采用了替代（SubstitutionSubstitution ）与置换（）与置换

20、（PermutationPermutation）技术；）技术； 替代技术将明文中的元素用其他元素替代而形成密文；替代技术将明文中的元素用其他元素替代而形成密文； 置换技术将明文中的元素重新排列；置换技术将明文中的元素重新排列； 著名的凯撒密码（著名的凯撒密码（Caesar CipherCaesar Cipher） 和维吉尼亚密码（和维吉尼亚密码（Vigenere CipherVigenere Cipher）使用了替代技术使用了替代技术； 替代具有扰乱作用，置换具有扩散作用；替代具有扰乱作用，置换具有扩散作用； 扰乱（扰乱（ConfusionConfusion）和扩散（）和扩散（Diffusio

21、nDiffusion）是保障算法强）是保障算法强度的两个关键机制，也是现代密码系统设计的基础。度的两个关键机制，也是现代密码系统设计的基础。信息安全技术与应用扰乱和扩散扰乱和扩散 通常明文信息具有一定的统计特征，统计特征有可能通常明文信息具有一定的统计特征，统计特征有可能反映到密文中，采用统计分析有可能解析出密钥；反映到密文中，采用统计分析有可能解析出密钥； 扰乱机制使密文的统计特征与明文和加密密钥的关系扰乱机制使密文的统计特征与明文和加密密钥的关系尽可能复杂化；尽可能复杂化； 扩散机制使明文和密钥的每个字符影响尽可能多的密扩散机制使明文和密钥的每个字符影响尽可能多的密文字符取值，扩散明文和密

22、钥的统计特征；文字符取值，扩散明文和密钥的统计特征； 如加密算法满足下列任意一个条件，则称算法在计算如加密算法满足下列任意一个条件，则称算法在计算上是安全的；上是安全的； （1 1）破译密码的成本超过被加密信息的价值；）破译密码的成本超过被加密信息的价值； （2 2）破译密码的时间超过被加密信息的生命周期。）破译密码的时间超过被加密信息的生命周期。2.3 信息加密算法信息加密算法信息安全技术与应用对称密钥对称密钥-数据加密标准数据加密标准 DES DES(Data Encryption Standard) DES(Data Encryption Standard) 是典型的对称是典型的对称密钥

23、加密体制，密钥加密体制，1976 1976 年美国国家标准局颁布，后年美国国家标准局颁布，后被国际标准化组织接受作为国际标准；被国际标准化组织接受作为国际标准； 加密和解密使用同一算法，用加密和解密使用同一算法，用5656位密钥对位密钥对6464位分组位分组加密，输出不同的加密，输出不同的6464位分组；位分组； DESDES加密算法还有一些变形，例如，高级数据加密加密算法还有一些变形，例如，高级数据加密标准标准AESAES（ Advanced Encryption Standard Advanced Encryption Standard ）、）、三重三重DESDES、广义广义DESDES等

24、；等； DESDES运算速度快，但密钥短，降低了保密强度；运算速度快，但密钥短，降低了保密强度； 其安全性依赖于密钥的管理，多用于民用领域。其安全性依赖于密钥的管理，多用于民用领域。信息安全技术与应用对称密钥对称密钥-国际数据加密算法国际数据加密算法IDEA 国际数据加密算法国际数据加密算法IDEA（International Data Encryption Algorithm）由由 Xuejia Lai 和和James L. Massey在在DES的基础上发展得到；的基础上发展得到； 采用采用128位密钥，比位密钥，比DES具有更高的速度，加密具有更高的速度，加密速度可达速度可达100MB/

25、s； IDEA 适合对大量明文信息快速加密，于适合对大量明文信息快速加密，于1990年正式公布。年正式公布。RSA加密算法加密算法 1.生成密钥生成密钥（1）任意选取两个不同的大素数）任意选取两个不同的大素数p,q。（2）计算）计算n=p*q , ,在这在这 指的是指的是Euler函数。函数。（3）任意选取一个大整数）任意选取一个大整数e，满足，满足 且且 整数整数e用做加密钥。用做加密钥。（4）计算解密钥）计算解密钥d,满足满足 。即。即d是是e关于模关于模 乘的逆元，由乘的逆元，由e的定义，的定义，d存在唯一值。存在唯一值。（5）输出公钥）输出公钥 ,保存私钥保存私钥 。信息安全技术与应用

26、) 1)(1()(qpn)(n)(1ne1),(gcd(en)(mod1*ned)(n,ne,nd 2.加密操作加密操作 选定选定 ,把明文分成长度为把明文分成长度为k的组块。对每个明文的组块。对每个明文分组分组m，m在在0到到(n-1)之间。加密操作为：之间。加密操作为： 3.解密操作解密操作 得到密文分组得到密文分组c，解密操作为：，解密操作为： 信息安全技术与应用log) 1(2nknmcemodncmdmod信息安全技术与应用RSA 公开密钥加密算法公开密钥加密算法 在在Diffie-Hellman 算法的基础上，算法的基础上，Rivest、Shamir 和和 Adleman 三人三人

27、1977年提出了年提出了RSA 公开密钥算法公开密钥算法 算法以发明人的首字母命名；算法以发明人的首字母命名； RSA 密钥管理简单，公开密钥可以象电话号码公密钥管理简单，公开密钥可以象电话号码公开，用户只需一个私有密钥即可实现保密通信；开，用户只需一个私有密钥即可实现保密通信； RSA加密速度慢，比加密速度慢，比DES大约慢大约慢1000倍左右，主要倍左右，主要用于短信息加密。用于短信息加密。信息安全技术与应用非对称密钥加密体制非对称密钥加密体制 Diffie 和和 Hellman 于于1976年首次提出了公开密钥加密体年首次提出了公开密钥加密体制的思想；制的思想； 公开密钥加密体制主要有公

28、开密钥加密体制主要有 Diffie-Hellman 算法、算法、RSA 算算法、法、 ElGamal 算法、数字签名算法算法、数字签名算法DSA（Digital Signature Algorithm ）和椭圆曲线加密算法等；和椭圆曲线加密算法等； 公开密钥加密体制提供了加密和验证的能力，既能用于公开密钥加密体制提供了加密和验证的能力，既能用于数据加密也能用于数字签名；数据加密也能用于数字签名；加密：用公钥加密，用私钥解密；加密：用公钥加密，用私钥解密；签名：签名：用私钥用私钥签名签名，用公钥验证。，用公钥验证。算法描述算法描述 假定有两个全局公开的参数：素数假定有两个全局公开的参数：素数q和

29、和q的一个原根的一个原根r，对于用户对于用户A和和B交换密钥的方法描述如下：交换密钥的方法描述如下： （1）用户）用户A选择一个作为私有密钥的随机数选择一个作为私有密钥的随机数XAq，并，并计算公开密钥计算公开密钥 ，A将将XA秘密保存而将秘密保存而将YA公公开给用户开给用户B； （2）用户）用户B选择一个作为私有密钥的随机数选择一个作为私有密钥的随机数XBq，并，并计算公开密钥计算公开密钥 ，B将将XB秘密保存而将秘密保存而将YB公开给用户公开给用户A； （3）用户）用户A计算密钥计算密钥 ，用户，用户B计算密钥计算密钥 ；信息安全技术与应用qrYAXAmodqrYBXBmodqYKAXBA

30、mod)(qYKBXABmod)(； 由于：由于： 由此，用户由此，用户A和和B得到一个共享的密钥得到一个共享的密钥K=KA=KB。因为。因为XA，XB保密，由离散对数难解性可知，仅通过公开信保密，由离散对数难解性可知，仅通过公开信息息q,r, YA,YB是很难破解出是很难破解出K的。的。信息安全技术与应用qqrqYKABAXXXBAmod)mod(mod)(qrqrBAABXXXXmod)(mod)(BXAXXKqYqqrBBAmod)(mod)mod( ElGamal加密算法加密算法 密钥对产生方法如下：选择一个素数密钥对产生方法如下：选择一个素数p，两个随机数，两个随机数g和和x，g,x

31、0,p-1，计算，计算y=gx (mod p)，则公钥，则公钥k1=(y,g,p)，私钥私钥k2=x。(1) 加密变换。对于消息加密变换。对于消息m，秘密选取一个随机数，秘密选取一个随机数k0,p-1，且，且gcd(k,p-1)=1，然后计算：，然后计算：c1=gk mod p ; c2=myk mod p。c1与与c2并联构成密文，即密文并联构成密文，即密文c=(c1，c2)，因此，因此密文的长度是明文的两倍。密文的长度是明文的两倍。(2) 解密变换。由加密变换可知：解密变换。由加密变换可知：c2(c1x)-1=myk (gxk )-1= mgxk g-xk m mod p 所以：所以：m= c2(c1x)-1 mod p。信息安全技术与应用2.4 信息加密产品简介信息加密产品简介 PGP（Pretty Good Privacy）是当前国际上非常著名的是当前国际上非常著名的基于公用密钥或非对称密钥加密体制的开放源码信息保基于公用密钥或非对称密钥加密体制的开