现代密码学知识点整理：

1第一章基本概念1.密钥体制组成部分：明文空间，密文空间，密钥空间，加密算法，解密算法2、一个好密钥体制至少应满足的两个条件：（1）已知明文和加密密钥计算密文容易；在已知密文和解密密钥计算明文容易；（2）在不知解密密钥的情况下，不可能由密文c推知明文3、密码分析者攻击密码体制的主要方法：（1）穷举攻击（解决方法:增大密钥量）（2）统计分析攻击（解决方法：使明文的统计特性与密文的统计特性不一样）（3）解密变换攻击（解决方法：选用足够复杂的加密算法）4、四种常见攻击（1）唯密文攻击：仅知道一些密文（2）已知明文攻击：知道一些密文和相应的明文（3）选择明文攻击：密码分析者可以选择一些明文并得到相应的密文（4）选择密文攻击：密码分析者可以选择一些密文，并得到相应的明文【注：以上攻击都建立在已知算法的基础之上；以上攻击器攻击强度依次增加；密码体制的安全性取决于选用的密钥的安全性】第二章古典密码（一）单表古典密码1、定义：明文字母对应的密文字母在密文中保持不变2、基本加密运算设q是一个正整数，}1),gcd(|{};1,...,2,1,0{*qkZkZqZqqq（1）加法密码加密算法：kXmZZYXqq;,;对任意，密文为：qkmmEckmod)()(密钥量：q（2）乘法密码加密算法：kXmZZYXqq;,;*对任意，密文为：qkmmEckmod)(解密算法：qckcDmkmod)(1密钥量：)(q（3）仿射密码加密算法：),(;},,|),{(;21*2121kkkXmZkZkkkZYXqqq对任意；密文2qmkkmEckmod)()(21解密算法：qkckcDmkmod)()(112密钥量：)(qq（4）置换密码加密算法：kXmZZYXqq;,;对任意上的全体置换的集合为，密文)()(mmEck密钥量：!q仿射密码是置换密码的特例3.几种典型的单表古典密码体制（1）Caeser体制：密钥k=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）简单加法密码加密算法:),...,(,),...,(,,11nnnnqnqnnkkkXmmmZZYX对任意设,密文：),...,()(11nnkkmkmmEc密钥量：nq（2）简单乘法密码密钥量：nq)(1.简单仿射密码密钥量：nnqq)(32.简单置换密码密钥量：nq)!(（3）换位密码密钥量：!n（4）广义置换密码密钥量：)!(nq（5）广义仿射密码密钥量：nnrq3.几种典型的多表古典密码体制（1）Playfair体制：密钥为一个5X5的矩阵加密步骤：a.在适当位置闯入一些特定字母，譬如q,使得明文字母串的长度为偶数，并且将明文字母串按两个字母一组进行分组，每组中的两个字母不同。b.明文21mm对应的密文21cc的确定：21mm和同行或同列，则1c为1m后的字符，2c为2m后的字符；若21mm和既不同行也不同列，则21cc在21mm所确定的矩形的其他两个角上，1c和1m同行，2c和2m同行。（2）Vigenere体制设明文nmmmm...21，密钥nkkkk...21则密文：nkcccmEc...)(21，其中nikmciii,...2,126mod)(当密钥长度比明文长度短时，密钥可周期性地重复利用。（3）Vernam体制设明文......21immmm，密钥......21ikkkk其中，1)2(,iGFkmii则密文......21icccc，其中1ikmciii（4）Hill体制设明文nnZmmmm2621)...(，密文nnZcccc2621)...(，密钥为26Z上的nXn街可逆方阵nnijkK)(，则：26mod26mod1cKmmKc4.多表古典密码的统计分析（1）分析步骤:确定密钥字的长度；确定密钥的内容4（2）确定密钥字的常用方法：Kasisiki测试法和重合指数法Kasisiki测试法可以找出可能密钥；而重合指数法可以进一步确定密钥kasisiki测试法步骤：a.寻找密文中长度至少为3的相同的密文片段；b.计算没对密文片段之间的距离为iddd,...,,21；c.计算可能密钥),...,,gcd(21idddm重合指数法：065.0)1()1()(2512250iiiiicpnnffxI其中iipf和分别为英文字母A,B,.....,Z在长度为n的英文字符串中出现的次数，及各字符出现的概率第三章香农理论1、密码体制各组成部分的熵之间的关系：)()()()|(CHMHKHCKH2、语言L的冗余度：||log12XHRLL3、伪密钥（1）定义:密码分析者得到众多可能密钥中除正确密钥之外的一个密钥（2）对于任意一个密文，用不同的密钥进行解密，如果得到的有意义的明文越多，则伪密钥也越多。这是判断哪个密钥正确的难度就越大。（3）对于一个密钥体制，设X是明文字母表，Y是密文字母表，并且|X|=|Y|，设LR是明文语言的冗余度，假设密钥的选取满足均匀分布，则对于任意一个场地为n的密钥字母串，当n充分大时，萎靡要的期望数目ns满足：1||||LnnRXKs（4）唯一解距离令0ns，解之：||log||log0XRKnL一个密钥体制的唯一解距离就是密码分析者在有足够的计算时间的情况下，能够唯一的计算出正确密钥所需的密文的平均长度。明文语言的冗余度越大，唯一解距离就越小，密码分析者在唯密文攻击的情况下就越容易求得正确的密钥。第三章DES5（一）DES算法1.基本参数分组加密算法：明文和密文为64位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：有效密钥56位，但每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，但存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共16轮2.加密流程图63.子密钥的产生（二）分组密码的工作模式1.分类电码本(ECB)模式密码分组链接(CBC)模式密码反馈(CFB)模式输出反馈(OFB)模式计数器模式(CTR)2.总评（1）ECB模式简单、高速，但最弱，易受重发和替换攻击，一般不采用。（2）CBC，CFC，OFB模式的选用取决于实际的特殊需求。（3）明文不易丢信号，对明文的格式没有特殊要求的环境可选用CBC模式。需要完整性认证功能时也可选用该模式。（4）不易丢信号，或对明文格式有特殊要求的环境，可选用CFB模式。（5）信号特别容易错，但明文冗余特别多，可选用OFB模式。第四章AES1.AES的理论基础(1)AES的字节运算AES中一个字节是用有限域GF(28)上的元素表示，通过倍成函数xtime（）实现(2)AES的字运算AES中的32位字表示为系数在有限域GF(28)上的次数小于4的多项式，即012233)(axaxaxaxa2.AES加密（1）AES密码是一种迭代式密码结构，但不是Feistel密码结构（2）对于AES算法，算法的轮数依赖于密钥长度:将轮数表示为Nr，当Nk=4时,Nr＝10;当Nk=6时,Nr＝12;当Nk=8时Nr＝14。【其中：密钥的列数记为Nk，Nk=密钥长度（bits）÷32(bits)。Nk可以取的值为4、6和8，对应的密钥长度分别为128位、192位和256位】（3）加密过程：（以128位为例）AES需迭代十轮，需要11个子密钥。前面9轮完全相同，每轮包括4阶段，分别是字节代换（SubBytes）、行移位（ShiftRows）、7列混淆（MixColumns）和轮密钥加（AddRoundKey）；最后一轮只3个阶段，缺少列混淆。3.AES的解密加密的逆过程4.AES的安全性（1）抗差分分析和线性分析（基于轨迹策略）（2）抗穷举密钥攻击（3）对密钥的选择没有任何限制，还没有发现弱密钥和半弱密的存在第五章RSA（一）公钥密码体制1.为解决的两个问题：密钥的分配；数字签名2.对公钥密码体制的攻击（1）穷举法（2）根据公钥计算私钥（二）RSA算法1.体制原理（1)选取两个大素数p和q（保密）8（2)计算n=pq(公开)，)1)(1()(qpn（保密）（3)随机选取正整数e,)(1ne,满足1))(,gcd(ne，e是公开的加密密钥。（4)计算d，满足))((mod1ned，d是保密的解密密钥。（5)加密变换：对明文nZm，密文为nmcemod（6)解密变换：对密文nZc，明文为ncmdmod【解密变换是加密变换的逆变换的证明】2.p和q选择的限制（1）p和q的长度应该差不多（2）11qp和都应该包含大的素因子（3）)1,1gcd(qp应该很小（三）大素数生成1.素数分布定定理：设x0,π(x)为不大于x的素数的个数,则1ln)(limxxxx。【注：素数的分布极不均匀，素数越大，分布越稀疏。】2.Legendra符号设p2是一个素数，对任意整数0a,的非平方剩余是模若的平方剩余是模若若papapapa1-1)(mod00)(3.Jacobi符号4.模n的大数幂乘的快速算法5.StrassenSolovay素性测试测试的主要依据：设p2是一个素数，则对于任意整数0a，)(mod)(2/)1(papap第六章序列密码与移位寄存器91.序列密码的基本原理2.移位寄存器与移位寄存器序列(1)基本构造反馈移位寄存器序列：,...,...,,,210taaaa反馈移位寄存器状态序列：,...,...,,,210tssss（2）线性移位寄存器的表示生成矩阵：（3）线性移位寄存器序列极小多项式与周期定义：对于一个移位寄存器序列a，称其联系多项式中次数最低的多项式为a的极小多项式。定义：满足f(x)|1-xr的最小正整数r为f(x)的周期，记为p(f(x))，简记为p(f)。EG：1234xxxx的周期为5，因为1)1)(1(5234xxxxxx，故其极小多10项式为15x（4）线性移存器序列的n阶m序列①定义：n级线性反馈移存器的最长周期:12n，能达到最长周期的线性移存器序列称为m序列。②本原多项式:若n次多项式f(x)是不可约多项式且p(f)=qn-1，则称f(x)是GF(q)上的本原多项式。以本原多项式为联系多项式产生的非零序列均是m序列③m序列的伪随机性④m序列的游程分布规律将n级m序列的一个周期段首尾相接，其游程总数为12nN；其中没有长度大于n的游程；有1个长度为n的1游程，没有长度为n的0游程；没有长度为n-1的1游程，有1个长度为n-1的0游程；有kn22个长度为)21(nkk的1游程，有kn22个长度为)21(nkk的0游程。⑤m序列密码的破译（5）线性移存器递推式的求解①解方程法：已知序列a是由n级线性移存器产生的，且知a的连续2n位，可用解线11性方程组的方法得到线性递推式。②B-M迭代算法流程图：几个重要结论A）设)...(110)(NNaaaa是GF(q)上的一个长度为N的序列，)(Na作为B-M算法的输入。设NNlxf),(是B-M算法的最终输入结果，则NNlxf),(一定是)(Na的线性综合解B）设)...(110)(NNaaaa是GF(q)上的一个长度为N的序列。)(Na有唯一线性综合解的充要条件为::NlN2C）设)...(110)(