现代密码学知识点整理:Word格式.doc
《现代密码学知识点整理:Word格式.doc》由会员分享,可在线阅读,更多相关《现代密码学知识点整理:Word格式.doc(16页珍藏版)》请在冰点文库上搜索。
加密算法:
,密文为:
密钥量:
q
(2)乘法密码
加密算法:
,密文为:
解密算法:
密钥量:
(3)仿射密码
;
密文
(4)置换密码
,密文
密钥量:
仿射密码是置换密码的特例
3.几种典型的单表古典密码体制
(1)Caeser体制:
密钥k=3
(2)标准字头密码体制:
4.单表古典密码的统计分析
(1)26个英文字母出现的频率如下:
频率
约为0.12
0.06到0.09之间
约为0.04
约0.015到0.028之间
小于0.01
字母
e
t,a,o,i.n,s,h,r
d,l
c,u,m,w,f,g,y,p,b
v,k,j,x,q,z
出现频率最高的双字母:
th;
出现频率最高的三字母:
the】
(二)多表古典密码
1.定义:
明文中不同位置的同一明文字母在密文中对应的密文字母不同
2.基本加密运算
(1)简单加法密码
加密算法:
密文:
(2)简单乘法密码
密钥量:
1.简单仿射密码
2.简单置换密码
(3)换位密码
(4)广义置换密码
(5)广义仿射密码
3.几种典型的多表古典密码体制
(1)Playfair体制:
密钥为一个5X5的矩阵
加密步骤:
a.在适当位置闯入一些特定字母,譬如q,使得明文字母串的长度为偶数,并且将明文字母串按两个字母一组进行分组,每组中的两个字母不同。
b.明文对应的密文的确定:
同行或同列,则为后的字符,为后的字符;
若既不同行也不同列,则在所确定的矩形的其他两个角上,和同行,和同行。
(2)Vigenere体制
设明文,密钥则密文:
,
其中
当密钥长度比明文长度短时,密钥可周期性地重复利用。
(3)Vernam体制
设明文,密钥其中,则密文,其中
(4)Hill体制
设明文,密文,密钥为上的nXn街可逆方阵,则:
4.多表古典密码的统计分析
(1)分析步骤:
确定密钥字的长度;
确定密钥的内容
(2)确定密钥字的常用方法:
Kasisiki测试法和重合指数法
Kasisiki测试法可以找出可能密钥;
而重合指数法可以进一步确定密钥
kasisiki测试法步骤:
a.寻找密文中长度至少为3的相同的密文片段;
b.计算没对密文片段之间的距离为;
c.计算可能密钥
重合指数法:
其中分别为英文字母A,B,.....,Z在长度为n的英文字符串中出现的次数,及各字符出现的概率
第三章香农理论
1、密码体制各组成部分的熵之间的关系:
2、语言L的冗余度:
3、伪密钥
(1)定义:
密码分析者得到众多可能密钥中除正确密钥之外的一个密钥
(2)对于任意一个密文,用不同的密钥进行解密,如果得到的有意义的明文越多,则伪密钥也越多。
这是判断哪个密钥正确的难度就越大。
(3)对于一个密钥体制,设X是明文字母表,Y是密文字母表,并且|X|=|Y|,设是明文语言的冗余度,假设密钥的选取满足均匀分布,则对于任意一个场地为n的密钥字母串,当n充分大时,萎靡要的期望数目满足:
(4)唯一解距离
令,解之:
一个密钥体制的唯一解距离就是密码分析者在有足够的计算时间的情况下,能够唯一的计算出正确密钥所需的密文的平均长度。
明文语言的冗余度越大,唯一解距离就越小,密码分析者在唯密文攻击的情况下就越容易求得正确的密钥。
第三章DES
(一)DES算法
1.基本参数
分组加密算法:
明文和密文为64位分组长度
对称算法:
加密和解密除密钥编排不同外,使用同一算法
密钥长度:
有效密钥56位,但每个第8位为奇偶校验位,可忽略
密钥可为任意的56位数,但存在弱密钥,容易避开
采用混乱和扩散的组合,每个组合先替代后置换,共16轮
2.加密流程图
3.子密钥的产生
(二)分组密码的工作模式
1.分类
电码本(ECB)模式
密码分组链接(CBC)模式
密码反馈(CFB)模式
输出反馈(OFB)模式
计数器模式(CTR)
2.总评
(1)ECB模式简单、高速,但最弱,易受重发和替换攻击,一般不采用。
(2)CBC,CFC,OFB模式的选用取决于实际的特殊需求。
(3)明文不易丢信号,对明文的格式没有特殊要求的环境可选用CBC模式。
需要完整性认证功能时也可选用该模式。
(4)不易丢信号,或对明文格式有特殊要求的环境,可选用CFB模式。
(5)信号特别容易错,但明文冗余特别多,可选用OFB模式。
第四章AES
1.AES的理论基础
(1)AES的字节运算
AES中一个字节是用有限域GF(28)上的元素表示,通过倍成函数xtime()实现
(2)AES的字运算
AES中的32位字表示为系数在有限域GF(28)上的次数小于4的多项式,即
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)、列混淆(MixColumns)和轮密钥加(AddRoundKey);
最后一轮只3个阶段,缺少列混淆。
3.AES的解密
加密的逆过程
4.AES的安全性
(1)抗差分分析和线性分析(基于轨迹策略)
(2)抗穷举密钥攻击
(3)对密钥的选择没有任何限制,还没有发现弱密钥和半弱密的存在
第五章RSA
(一)公钥密码体制
1.为解决的两个问题:
密钥的分配;
数字签名
2.对公钥密码体制的攻击
(1)穷举法
(2)根据公钥计算私钥
(二)RSA算法
1.体制原理
(1)选取两个大素数p和q(保密)
(2)计算n=pq(公开),(保密)
(3)随机选取正整数e,,满足,e是公开的加密密钥。
(4)计算d,满足,d是保密的解密密钥。
(5)加密变换:
对明文,密文为
(6)解密变换:
对密文,明文为
【解密变换是加密变换的逆变换的证明】
2.p和q选择的限制
(1)p和q的长度应该差不多
(2)都应该包含大的素因子
(3)应该很小
(三)大素数生成
1.素数分布定定理:
设x>
0,π(x)为不大于x的素数的个数,则。
素数的分布极不均匀,素数越大,分布越稀疏。
】
2.Legendra符号
设p>
2是一个素数,对任意整数,
3.Jacobi符号
4.模n的大数幂乘的快速算法
5.素性测试
测试的主要依据:
2是一个素数,则对于任意整数,
第六章序列密码与移位寄存器
1.序列密码的基本原理
2.移位寄存器与移位寄存器序列
(1)基本构造
反馈移位寄存器序列:
反馈移位寄存器状态序列:
(2)线性移位寄存器的表示
生成矩阵:
(3)线性移位寄存器序列极小多项式与周期
定义:
对于一个移位寄存器序列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的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的序列。
是能产生并且阶数最小的线性移位寄存器的阶数。
则当时,有个线性综合解。
第七章数字签名
1.数字签名的特性:
可信的;
不可伪造的;
不可复制的;
不可改变的;
不可抵赖的。
2.基于公钥密码的数字签名
RSA数字签名描述如下:
(1)秘密选取两个大素数p和q。
(2)计算,n公开,保密
(3)随机选取正整数,满足,e是公开的密钥
(4)计算d,满足.d是保密密钥
(5)签名变换:
对于消息,则签名为:
(6)签名验证:
对于,如果,则确认s为消息m的有效签名。
第八章Hash函数
1.作用:
保证数据的完整性和认证性(主要用于鉴别)
2.定义:
Hash函数常用来构造数据的短“指纹”:
消息的发送者使用所有的消息产生一个附件也就是短“指纹”,并将该短“指纹”与消息一起传输给接收者。
【即使数据存储在不安全的地方,接收者重新计算数据的指纹,并验证指纹是否改变,就能够检测数据的完整性。
这是因为一旦数据在中途被破坏,或改变,短指纹就不再正确。
】
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函数的攻击方法
(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)算法描述
第九章密钥协议
1.密钥分配
(1)定义:
通信双方中的一方选取一个秘密密钥,然后传送给另一方。
(2)Kerboros密钥分配协议:
2.密钥协商
通信双方可以在一个公开的信道上通过相互传送一些消息来共同建立一个共享的秘密密钥。
协商中,双方共同建立的秘密密钥通常是双方输入消息的一个函数。
(2)Diffie-Hellman密钥协商
【此协议易受中间人攻击。
(3)端对端协议
3.秘密分享
(1)Shamir的(t,w)门限方案
门限方案描述:
(2)利用Lagrange插值公式重建(t,w)门限方案中的密钥
4.身份识别
Guillou-Quisquater身份识别方案:
16