《现代密码学知识点整理:要点.pdf》由会员分享,可在线阅读,更多相关《现代密码学知识点整理:要点.pdf(16页珍藏版)》请在三一文库上搜索。
1、1 第一章基本概念 1.密钥体制组成部分: 明文空间,密文空间,密钥空间,加密算法,解密算法 2、一个好密钥体制至少应满足的两个条件: (1)已知明文和加密密钥计算密文容易;在已知密文和解密密钥计算明文容易; (2)在不知解密密钥的情况下,不可能由密文c 推知明文 3、密码分析者攻击密码体制的主要方法: (1)穷举攻击(解决方法 : 增大密钥量) (2)统计分析攻击(解决方法:使明文的统计特性与密文的统计特性不一样) (3)解密变换攻击(解决方法:选用足够复杂的加密算法) 4、四种常见攻击 (1)唯密文攻击:仅知道一些密文 (2)已知明文攻击:知道一些密文和相应的明文 (3)选择明文攻击:密码
2、分析者可以选择一些明文并得到相应的密文 (4)选择密文攻击:密码分析者可以选择一些密文,并得到相应的明文 【注:以上攻击都建立在已知算法的基础之上;以上攻击器攻击强度依次增加;密码 体制的安全性取决于选用的密钥的安全性】 第二章 古典密码 (一)单表古典密码 1 、定义:明文字母对应的密文字母在密文中保持不变 2、基本加密运算 设 q 是一个正整数, 1),gcd(|;1,.,2, 1 ,0 * qkZkZqZ qqq (1)加法密码 加密算法: kXmZZYX qq ;,;对任意,密文为:qkmmEc k mod)()( 密钥量: q (2)乘法密码 加密算法: kXmZZYX qq ;,;
3、 * 对任意 ,密文为: qkmmEc k mod)( 解密算法:qckcDm k mod)( 1 密钥量:)(q (3)仿射密码 加密算法: ),(;,| ),(; 21 * 2121 kkkXmZkZkkkZYX qqq 对任意;密文 2 qmkkmEc k mod)()( 21 解密算法:qkckcDm k mod)()( 1 1 2 密钥量:)(qq (4)置换密码 加密算法: kXmZZYX qq ;,;对任意上的全体置换的集合为,密文 )()(mmEc k 密钥量:!q 仿射密码是置换密码的特例 3. 几种典型的单表古典密码体制 (1)Caeser 体制:密钥k=3 (2)标准字头
4、密码体制: 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)简单加法密码 加密算法 : ),.,(,),.,(, 11n n n n q n q nn kkkXm
5、mmZZYX对任意设 , 密文: ),.,()( 11nnk kmkmmEc 密钥量: n q (2)简单乘法密码 密钥量: n q)( 1. 简单仿射密码 密钥量: nn qq)( 3 2. 简单置换密码 密钥量: n q ) !( (3)换位密码 密钥量:!n (4)广义置换密码 密钥量:)!( n q (5)广义仿射密码 密钥量: n nr q 3. 几种典型的多表古典密码体制 (1)Playfair体制: 密钥为一个5X5 的矩阵 加密步骤: a. 在适当位置闯入一些特定字母,譬如q, 使得明文字母串的长度为偶数,并 且将明文字母串按两个字母一组进行分组,每组中的两个字母不同。b. 明
6、文 21m m对应的密 文 21c c的确定: 21 mm 和同行或同列,则 1 c为 1 m后的字符, 2 c为 2 m后的字符;若 21 mm和既不同行也不同 列,则 21c c在 21m m所确定的矩形的其他两个角上, 1 c和 1 m同行, 2 c和 2 m同行。 (2)Vigenere 体制 设明文 n mmmm. 21 ,密钥 n kkkk. 21 则密文: nk cccmEc.)( 21 , 其中nikmc iii ,.2, 126mod)( 当密钥长度比明文长度短时,密钥可周期性地重复利用。 (3)Vernam体制 设 明 文. . . . 21i mmmm, 密 钥 21i
7、kkkk其 中 ,1)2(,iGFkm ii 则 密 文 21i cccc,其中1ikmc iii (4)Hill体制 设明文 n n Zmmmm 2621 ).(,密文 n n Zcccc 2621 ).(,密钥为 26 Z上的 nXn 街可逆方阵 nnij kK)(,则: 26mod 26mod 1 cKm mKc 4. 多表古典密码的统计分析 (1)分析步骤 :确定密钥字的长度;确定密钥的内容 4 (2)确定密钥字的常用方法:Kasisiki测试法和重合指数法 Kasisiki测试法可以找出可能密钥;而重合指数法可以进一步确定密钥 kasisiki测试法步骤: a. 寻找密文中长度至少为
8、3 的相同的密文片段;b. 计算没对密文 片段之间的距离为 i ddd,., 21 ; c. 计算可能密钥),.,gcd( 21i dddm 重合指数法: 065.0 )1( )1( )( 25 1 2 25 0 i i i ii c p nn ff xI 其中 ii pf 和分别为英文字母A,B,.,Z在长度为n 的英文字符串中出现的次数,及各字 符出现的概率 第三章 香农理论 1、密码体制各组成部分的熵之间的关系: )()()()|(CHMHKHCKH 2、语言 L的冗余度: |log 1 2 X H R L L 3、伪密钥 (1)定义 : 密码分析者得到众多可能密钥中除正确密钥之外的一个
9、密钥 (2)对于任意一个密文,用不同的密钥进行解密,如果得到的有意义的明文越多,则伪密 钥也越多。这是判断哪个密钥正确的难度就越大。 (3)对于一个密钥体制,设X 是明文字母表,Y 是密文字母表,并且|X|=|Y|,设 L R是明 文语言的冗余度,假设密钥的选取满足均匀分布,则对于任意一个场地为n 的密钥字母串, 当 n 充分大时,萎靡要的期望数目 n s满足: 1 | | L n n RX K s (4)唯一解距离 令0 n s,解之: |log |log 0 XR K n L 一个密钥体制的唯一解距离就是密码分析者在有足够的计算时间的情况下,能够唯一的计 算出正确密钥所需的密文的平均长度。
10、 明文语言的冗余度越大,唯一解距离就越小,密码分析者在唯密文攻击的情况下就越容易 求得正确的密钥。 第三章 DES 5 (一) DES算法 1. 基本参数 分组加密算法:明文和密文为64 位分组长度 对称算法:加密和解密除密钥编排不同外,使用同一算法 密钥长度:有效密钥56 位,但每个第8 位为奇偶校验位,可忽略 密钥可为任意的56 位数,但存在弱密钥,容易避开 采用混乱和扩散的组合,每个组合先替代后置换,共16 轮 2. 加密流程图 6 3. 子密钥的产生 (二)分组密码的工作模式 1. 分类 电码本 (ECB)模式 密码分组链接 (CBC)模式 密码反馈 (CFB)模式 输出反馈 (OFB
11、)模式 计数器模式 (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 的字运算 AE
12、S 中 的32 位 字 表 示 为 系 数 在 有 限 域GF(28) 上 的 次 数 小 于4的 多 项 式 , 即 01 2 2 3 3 )(axaxaxaxa 2.AES 加密 (1)AES密码是一种迭代式密码结构,但不是 Feistel 密码结构 (2)对于 AES算法,算法的轮数依赖于密钥长度: 将轮数表示为Nr,当 Nk =4 时,Nr 10; 当 Nk =6 时,Nr 12; 当 Nk =8 时 Nr14 。【其中: 密钥的列数记为Nk, Nk =密钥长度 (bits ) 32(bits) 。 Nk 可以取的值为4、6 和 8,对应的密钥长度分别为128 位、 192 位和 25
13、6 位】 (3)加密过程: (以 128 位为例) AES需迭代十轮,需要11 个子密钥。 前面 9 轮完全相同, 每轮包括 4 阶段, 分别是字节代换 (SubBytes ) 、 行移位 (Shift Rows) 、 7 列混淆( Mix Columns)和轮密钥加(Add Round Key) ;最后一轮只3 个阶段,缺少列混淆。 3.AES 的解密 加密的逆过程 4.AES 的安全性 ( 1)抗差分分析和线性分析(基于轨迹策略) ( 2)抗穷举密钥攻击 (3)对密钥的选择没有任何限制,还没有发现弱密钥和半弱密的存在 第五章 RSA (一)公钥密码体制 1. 为解决的两个问题:密钥的分配;
14、数字签名 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) 加密变换:对明文 n Zm,密文为nmc e mod (6) 解密变换:对密文 n Zc,明文为ncm d mod 【解密变换是加密变换的逆变换的证明】 2.p 和 q 选择的限制 (1)p 和 q 的长度应
15、该差不多 (2)11qp和都应该包含大的素因子 (3))1, 1gcd(qp应该很小 (三)大素数生成 1. 素数分布定定理: 设 x 0,(x) 为不大于x 的素数的个数, 则1 ln)( lim x xx x 。 【注:素数的分布极不均匀,素数越大,分布越稀疏。】 2.Legendra符号 设 p2 是一个素数,对任意整数0a, 的非平方剩余是模若 的平方剩余是模若 若 pa pa pa p a 1- 1 )(mod00 )( 3.Jacobi符号 4. 模 n 的大数幂乘的快速算法 5.StrassenSolovay素性测试 测试的主要依据:设p2 是一个素数,则对于任意整数0a,)(m
16、od)( 2/ )1( pa p ap 第六章 序列密码与移位寄存器 9 1. 序列密码的基本原理 2. 移位寄存器与移位寄存器序列 (1) 基本构造 反馈移位寄存器序列:,.,., 210t aaaa 反馈移位寄存器状态序列:,.,., 210t ssss (2)线性移位寄存器的表示 生成矩阵: (3)线性移位寄存器序列极小多项式与周期 定义:对于一个移位寄存器序列a,称其联系多项式中次数最低的多项式为a 的极小多 项式。 定义:满足f(x)|1-xr 的最小正整数r 为 f(x) 的周期,记为p(f(x),简记为p(f) 。 EG :1 234 xxxx的周期为5,因为1) 1)(1( 5
17、234 xxxxxx,故其极小多 10 项式为1 5 x (4)线性移存器序列的n 阶 m序列 定义: n 级线性反馈移存器的最长周期:12 n ,能达到最长周期的线性移存器序列称为m 序列。 本原多项式 : 若 n 次多项式 f(x)是不可约多项式且p(f)=qn-1,则称 f(x) 是 GF(q)上的本原多项式。 以本原多项式为联系多项式产生的非零序列均是m序列 m序列的伪随机性 m序列的游程分布规律 将 n 级 m序列的一个周期段首尾相接,其游程总数为 1 2 n N;其中没有长度大于n 的游 程;有 1 个长度为n 的 1 游程,没有长度为n 的 0 游程;没有长度为 n-1的 1 游
18、程,有1 个长度为n-1的 0 游程;有 kn2 2个长度为)21(nkk的 1 游程,有 kn 2 2个长度 为)21(nkk的 0 游程。 m序列密码的破译 (5)线性移存器递推式的求解 解方程法:已知序列a 是由 n 级线性移存器产生的,且知a 的连续 2n 位,可用解线 11 性方程组的方法得到线性递推式。 B-M迭代算法 流程图: 几个重要结论 A)设).( 110 )( N N aaaa是 GF(q)上的一个长度为N的序列, )(N a作为 B-M算法的输入。 设 NN lxf),(是 B-M算法的最终输入结果,则 NN lxf),(一定是 )(N a的线性综合解 B)设).( 1
19、10 )( N N aaaa是 GF(q)上的一个长度为N的序列。 )(N a有唯一线性综合解的充要 条件为 :Nl N 2 C)设).( 110 )( N N aaaa是 GF(q)上的一个长度为N 的序列。 N l是能产生 )( N a并且阶数最 小的线性移位寄存器的阶数。则当Nl N 2时, )( N a有 Nl N q 2 个线性综合解。 第七章数字签名 1. 数字签名的特性: 12 可信的;不可伪造的;不可复制的;不可改变的;不可抵赖的。 2. 基于公钥密码的数字签名 RSA数字签名描述如下: (1)秘密选取两个大素数p 和 q。 (2)计算) 1)(1()(,qpnpqn,n 公开
20、,)(n保密 (3)随机选取正整数)(1ne,满足1)(,gcd(ne,e 是公开的密钥 (4)计算 d,满足)(mod1ned.d 是保密密钥 (5)签名变换:对于消息 n Zm,则签名为:)(mod)(nmmSig d (6)签名验证:对于 n Zsm,,如果 )(modnsm e ,则确认s 为消息 m的有效签名。 第八章 Hash 函数 1. 作用 :保证数据的完整性和认证性( 主要用于鉴别 ) 2. 定义 :Hash函数常用来构造数据的短“指纹”:消息的发送者使用所有的消息产生一个附 件也就是短“指纹” ,并将该短“指纹”与消息一起传输给接收者。【即使数据存储在不安全 的地方,接收者
21、重新计算数据的指纹,并验证指纹是否改变,就能够检测数据的完整性。这 是因为一旦数据在中途被破坏,或改变,短指纹就不再正确。】 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 函数的攻击
22、方法 (1)穷举攻击:典型的生日攻击 (2)利用散列函数的代数结构:攻击其函数的弱性质。通常的有中间相遇攻击、修正分组 攻击和差分分析攻击等。 5. 基于分组密码的Hash函数 (1)基于分组密码的CBC工作模式liyxEy iiki 1)( 1 (2)基于分组密码的CFC工作模式liyExy ikii 1)( 1 13 6.MD4算法 (1)步骤 MD4 算法的输入可以是任意长度的消息x,对输入消息按512 位的分组为单位进行处理, 输出 128 位的散列值MD(x)。整个算法分为六个步骤。 步骤 1:消息的预处理 步骤 :2: 增加填充位 步骤 3: 附加消息长度值 填充方法是把64 比特
23、的长度分成两个32 比特的字, 低 32 比特字先填充, 高 32 比特字后填 充 步骤 4: 初始化 MD缓冲区 步骤 5: 以 512 位的分组 (16 个字 ) 为单位处理消息 步骤 6: 输出 (2)算法描述 第九章密钥协议 1. 密钥分配 (1)定义:通信双方中的一方选取一个秘密密钥,然后传送给另一方。 (2)Kerboros 密钥分配协议: 2. 密钥协商 (1)定义 : 通信双方可以在一个公开的信道上通过相互传送一些消息来共同建立一个共享 14 的秘密密钥。协商中,双方共同建立的秘密密钥通常是双方输入消息的一个函数。 (2)Diffie-Hellman密钥协商 【此协议易受中间人攻击。】 (3)端对端协议 3. 秘密分享 (1)Shamir 的( t,w )门限方案 门限方案描述:) 1(wpp是一个素数, 15 (2)利用 Lagrange 插值公式重建(t ,w) 门限方案中的密钥 4. 身份识别 Guillou-Quisquater身份识别方案: 16
链接地址:https://www.31doc.com/p-5219153.html