现代密码学知识点整理：教材

1、第一章 基本概念 1. 密钥体制组成部分：明文空间，密文空间，密钥空间，加密算法，解密算法2、一个好密钥体制至少应满足的两个条件：（1）已知明文和加密密钥计算密文容易；在已知密文和解密密钥计算明文容易；（2）在不知解密密钥的情况下，不可能由密文c推知明文3、密码分析者攻击密码体制的主要方法：（1）穷举攻击 （解决方法:增大密钥量）（2）统计分析攻击（解决方法：使明文的统计特性与密文的统计特性不一样）（3）解密变换攻击（解决方法：选用足够复杂的加密算法）4、四种常见攻击（1）唯密文攻击：仅知道一些密文（2）已知明文攻击：知道一些密文和相应的明文（3）选择明文攻击：密码分析者可以选择一些明文并得到

2、相应的密文（4）选择密文攻击：密码分析者可以选择一些密文，并得到相应的明文【注：以上攻击都建立在已知算法的基础之上；以上攻击器攻击强度依次增加；密码体制的安全性取决于选用的密钥的安全性】第2章 古典密码（1） 单表古典密码 1、定义：明文字母对应的密文字母在密文中保持不变2、 基本加密运算设q是一个正整数，（1）加法密码 加密算法： ，密文为： 密钥量：q（2） 乘法密码加密算法：，密文为：解密算法：密钥量：（3） 仿射密码加密算法：；密文 解密算法：密钥量：（4） 置换密码加密算法： ，密文密钥量：仿射密码是置换密码的特例3. 几种典型的单表古典密码体制（1） Caeser体制：密钥k=3（

3、2） 标准字头密码体制：4. 单表古典密码的统计分析（1）26个英文字母出现的频率如下：频率约为0.120.06到0.09之间约为0.04约0.015到0.028之间小于0.01字母et,a,o,i.n,s,h,rd,lc,u,m,w,f,g,y,p,bv,k,j,x,q,z【注：出现频率最高的双字母：th；出现频率最高的三字母：the】（二）多表古典密码1. 定义：明文中不同位置的同一明文字母在密文中对应的密文字母不同2.基本加密运算（1）简单加法密码加密算法:,密文：密钥量：（2）简单乘法密码密钥量：1. 简单仿射密码密钥量：2. 简单置换密码密钥量：（3）换位密码密钥量：（4）广义置换密

4、码密钥量：（5）广义仿射密码密钥量：3. 几种典型的多表古典密码体制（1） Playfair体制：密钥为一个5X5的矩阵加密步骤：a.在适当位置闯入一些特定字母，譬如q,使得明文字母串的长度为偶数，并且将明文字母串按两个字母一组进行分组，每组中的两个字母不同。b.明文对应的密文的确定：同行或同列，则为后的字符，为后的字符；若既不同行也不同列，则在所确定的矩形的其他两个角上，和同行，和同行。（2） Vigenere体制设明文，密钥则密文：，其中当密钥长度比明文长度短时，密钥可周期性地重复利用。（3） Vernam体制设明文，密钥其中，则密文，其中（4） Hill体制设明文，密文，密钥为上的nXn

5、街可逆方阵，则：4. 多表古典密码的统计分析（1） 分析步骤:确定密钥字的长度；确定密钥的内容（2） 确定密钥字的常用方法：Kasisiki测试法和重合指数法Kasisiki测试法可以找出可能密钥；而重合指数法可以进一步确定密钥kasisiki测试法步骤：a.寻找密文中长度至少为3的相同的密文片段；b.计算没对密文片段之间的距离为；c.计算可能密钥重合指数法： 其中分别为英文字母A,B,.,Z在长度为n的英文字符串中出现的次数，及各字符出现的概率第3章 香农理论1、 密码体制各组成部分的熵之间的关系： 2、 语言L的冗余度：3、 伪密钥（1） 定义:密码分析者得到众多可能密钥中除正确密钥之外的

6、一个密钥（2） 对于任意一个密文，用不同的密钥进行解密，如果得到的有意义的明文越多，则伪密钥也越多。这是判断哪个密钥正确的难度就越大。（3） 对于一个密钥体制，设X是明文字母表，Y是密文字母表，并且|X|=|Y|，设是明文语言的冗余度，假设密钥的选取满足均匀分布，则对于任意一个场地为n的密钥字母串，当n充分大时，萎靡要的期望数目满足：（4） 唯一解距离令，解之：一个密钥体制的唯一解距离就是密码分析者在有足够的计算时间的情况下，能够唯一的计算出正确密钥所需的密文的平均长度。明文语言的冗余度越大，唯一解距离就越小，密码分析者在唯密文攻击的情况下就越容易求得正确的密钥。第三章 DES （一）DES算

7、法 1.基本参数分组加密算法：明文和密文为64位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：有效密钥56位，但每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，但存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共16轮2. 加密流程图3. 子密钥的产生（2） 分组密码的工作模式1. 分类电码本(ECB)模式密码分组链接(CBC)模式密码反馈(CFB)模式输出反馈(OFB)模式计数器模式(CTR)2. 总评（1）ECB模式简单、高速，但最弱，易受重发和替换攻击，一般不采用。（2）CBC，CFC，OFB模式的选用取决于实际的特殊需求。（3）明文不易丢信号

8、，对明文的格式没有特殊要求的环境可选用CBC模式。需要完整性认证功能时也可选用该模式。（4）不易丢信号，或对明文格式有特殊要求的环境，可选用CFB模式。（5）信号特别容易错，但明文冗余特别多，可选用OFB模式。第4章 AES1. AES的理论基础(1) AES的字节运算 AES中一个字节是用有限域GF(28)上的元素表示 ，通过倍成函数xtime（）实现(2) AES的字运算 AES中的32位字表示为系数在有限域GF(28)上的次数小于4的多项式，即2. AES加密（1）AES密码是一种迭代式密码结构，但不是 Feistel 密码结构 （2）对于AES算法，算法的轮数依赖于密钥长度:将轮数表示

9、为Nr，当Nk =4时,Nr10;当Nk =6时,Nr12;当Nk =8时Nr14 。【其中：密钥的列数记为Nk， Nk =密钥长度（bits）32(bits) 。 Nk可以取的值为4、6和8，对应的密钥长度分别为128位、192位和256位】（3）加密过程：（以128位为例） AES需迭代十轮，需要11个子密钥。 前面9轮完全相同，每轮包括4阶段，分别是字节代换（SubBytes）、行移位（Shift Rows）、列混淆（Mix Columns）和轮密钥加（Add Round Key）；最后一轮只3个阶段，缺少列混淆。 3. AES的解密 加密的逆过程4. AES的安全性 （1）抗差分分析和

10、线性分析（基于轨迹策略） （2）抗穷举密钥攻击 （3）对密钥的选择没有任何限制，还没有发现弱密钥和半弱密的存在 第五章 RSA（1） 公钥密码体制1. 为解决的两个问题：密钥的分配；数字签名2. 对公钥密码体制的攻击（1） 穷举法（2） 根据公钥计算私钥 （2） RSA算法1. 体制原理（1) 选取两个大素数p和q（保密）（2) 计算n=pq(公开)，（保密）（3) 随机选取正整数e,满足，e是公开的加密密钥。（4) 计算d，满足，d是保密的解密密钥。（5) 加密变换：对明文，密文为（6) 解密变换：对密文，明文为【解密变换是加密变换的逆变换的证明】2. p和q选择的限制（1） p和q的长度应

11、该差不多（2） 都应该包含大的素因子（3） 应该很小（3） 大素数生成1. 素数分布定定理： 设x 0,(x)为不大于x 的素数的个数, 则。【注：素数的分布极不均匀，素数越大，分布越稀疏。】2.Legendra符号设p2是一个素数，对任意整数,3.Jacobi符号4.模n的大数幂乘的快速算法5.素性测试测试的主要依据：设p2是一个素数，则对于任意整数，第6章 序列密码与移位寄存器1. 序列密码的基本原理2. 移位寄存器与移位寄存器序列(1) 基本构造反馈移位寄存器序列：反馈移位寄存器状态序列：（2） 线性移位寄存器的表示生成矩阵： （3） 线性移位寄存器序列极小多项式与周期 定义：对于一 个

12、移位寄存器序列a，称其联系多项式中次数最低的多项式为a的极小多项式。定义：满足f(x)|1-xr 的最小正整数r为f(x)的周期，记为p(f(x)，简记为p(f)。EG：的周期为5，因为，故其极小多项式为（4） 线性移存器序列的n阶m序列定义：n级线性反馈移存器的最长周期:，能达到最长周期的线性移存器序列称为m序列。本原多项式:若n次多项式f(x)是不可约多项式且p(f)=qn-1，则称f(x)是GF(q)上的本原多项式。以本原多项式为联系多项式产生的非零序列均是m序列m序列的伪随机性m序列的游程分布规律将n级m序列的一个周期段首尾相接，其游程总数为；其中没有长度大于n的游程；有1个长度为n的

13、1游程，没有长度为n的0游程；没有长度为 n-1的1游程，有1个长度为n-1的0游程；有个长度为的1游程，有个长度 为的0游程。m序列密码的破译（5） 线性移存器递推式的求解 解方程法：已知序列a是由n级线性移存器产生的，且知a的连续2n位，可用解线性方程组的方法得到线性递推式。 B-M迭代算法 流程图：几个重要结论A） 设是GF(q)上的一个长度为N的序列，作为B-M算法的输入。设是B-M算法的最终输入结果，则一定是的线性综合解B） 设是GF(q)上的一个长度为N的序列。有唯一线性综合解的充要条件为:C） 设是GF(q)上的一个长度为N的序列。是能产生并且阶数最小的线性移位寄存器的阶数。则当

14、时，有个线性综合解。第七章 数字签名1. 数字签名的特性:可信的；不可伪造的；不可复制的；不可改变的；不可抵赖的。2. 基于公钥密码的数字签名RSA数字签名描述如下：（1） 秘密选取两个大素数p和q。（2） 计算，n公开，保密（3） 随机选取正整数，满足，e是公开的密钥（4） 计算d，满足.d是保密密钥（5） 签名变换：对于消息，则签名为：（6） 签名验证：对于，如果，则确认s为消息m的有效签名。第8章 Hash 函数1. 作用：保证数据的完整性和认证性(主要用于鉴别)2. 定义：Hash函数常用来构造数据的短“指纹”：消息的发送者使用所有的消息产生一个附件也就是短“指纹”，并将该短“指纹”与

15、消息一起传输给接收者。【即使数据存储在不安全的地方，接收者重新计算数据的指纹，并验证指纹是否改变，就能够检测数据的完整性。这是因为一旦数据在中途被破坏，或改变，短指纹就不再正确。】 3. Hash函数的性质：（1） 单向性 给定一个Hash值y，如果寻找一个消息x，使得y=h (x)是计算上不可行的，则称h是单向Hash函数 （2）若抗碰撞性任给一个消息x，如果寻找另一个不同的消息x，使得h(x) =h(x)是计算上不可行的，则称h是弱抗碰撞Hash函数. （3）强抗碰撞性 如果寻找两个不同的消息x和x，使得h(x)=h(x)是计算上不可行的，则称h是强抗碰撞Hash函数4. Hash函数的攻

16、击方法（1） 穷举攻击：典型的生日攻击（2） 利用散列函数的代数结构：攻击其函数的弱性质。通常的有中间相遇攻击、修正分组攻击和差分分析攻击等。 5. 基于分组密码的Hash函数（1） 基于分组密码的CBC工作模式 （2） 基于分组密码的CFC工作模式 6. MD4算法（1）步骤 MD4算法的输入可以是任意长度的消息x，对输入消息按512位的分组为单位进行处理，输出128位的散列值MD(x)。整个算法分为六个步骤。步骤1：消息的预处理步骤:2: 增加填充位步骤3: 附加消息长度值填充方法是把64比特的长度分成两个32比特的字，低32比特字先填充，高32比特字后填充步骤4: 初始化MD缓冲区步骤5: 以512位的分组(16个字)为单位处理消息步骤6: 输出（2） 算法描述第9章 密钥协议1. 密钥分配（1） 定义：通信双方中的一方选取一个秘密密钥，然后传送