对称密码体制[共92页]

《对称密码体制[共92页]》由会员分享，可在线阅读，更多相关《对称密码体制[共92页]（92页珍藏版）》请在金锄头文库上搜索。

1、2020/7/21,Page: 1,对称密码体制,杨秋伟 湖南大学 计算机与通信学院,2020/7/21,Page: 2,对称密码体制,对称密码体制的特征 加密密钥和解密密钥相同 对称密码体制的主要研究课题 密钥的产生 密钥的管理,2020/7/21,Page: 3,对称密码体制组成,流密码 分组密码 数据加密标准(DES) 高级加密标准(AES),2020/7/21,Page: 4,流密码：流密码引论,流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如按位)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。 流密码强度完全依赖于密钥序列的随机性(Randomne

2、ss)和不可预测性(Unpredictability)。 核心问题是密钥流的产生密钥流生成器的设计 保持收发两端密钥流的精确同步是实现可靠解密的关键技术,2020/7/21,Page: 5,流密码：流密码的基本概念,流密码的基本思想：假设存在着明文串x = x0 x1x2 利用密钥k和密钥流发生器f产生一个密钥流z = z0z1z2。其中，zi = f(k,i)，i是加密器中的记忆元件在时刻i的状态，f是以密钥k和i作为输入参数的函数； 加密： y = y0y1y2 = Ez0(x0) Ez1(x1) Ez1(x1)；,内部记忆元件,yi= Ezi(xi),xi,yi,k,2020/7/21,

3、Page: 6,流密码：同步流密码,同步流密码：加密器中记忆元件的存储状态i独立于明文字符。 同步流密码加密器 密钥流产生器 加密变换器 加密变换器一般采用二元逻辑运算XOR，即有限域GF(2)上讨论的二元加密流密码，变换表示为：yi = zixi 一次一密乱码本是加法流密码的原型,2020/7/21,Page: 7,流密码：流密码的密钥流产生器,密钥流产生器的内涵 输入：密钥k和加密器中的记忆元件在时刻i的状态i； 输出：密钥流zi,状态i,密钥k,状态i+1,密钥流zi,2020/7/21,Page: 8,流密码：密钥流生成器的设计原则,足够长的周期 高线性复杂度 统计性能良好 足够的“混

4、乱” 强调密钥的作用，增加密钥与密文之间关系的复杂性 足够的“扩散” 小扰动的影响波及到全局密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性 抵抗不同形式的攻击,2020/7/21,Page: 9,流密码：有限状态自动机(FA),具有离散输入和输出(输入集和输出集均有限)的一种数学模型 有限状态集S=si|i=1,2,l 有限输入字符集X=Xi|i=1,2,m 有限输出字符集Y=Yk|k=1,2,n 转移函数 Yjf1(sj, Xj) Sj+1 f2(sj, Xj) 即在状态sj，输入字符Xj时，输出为Yj，状态转移为Sj+1。,2020/7/21,Page: 10,流

5、密码：有限状态自动机举例,例一 S=s1,s2,s3,X=x1, x2,x3,Y=y1,y2,y3 转移函数,2020/7/21,Page: 11,流密码：有限状态自动机举例,若输入为x1x2x1x3x3x1 初始状态s1 输出为 y1y1y2y1y3y1,2020/7/21,Page: 12,流密码：基于FA的密钥流产生器,同步流密码的密钥流产生器可看为一个参数为k的FA：输出集Z，状态集，状态转移函数和输出函数，初态0 设计的关键是(phi fai)和(psi psai),2020/7/21,Page: 13,流密码：基于FA的密钥流产生器,一个良好的密钥流产生器 极大的周期 良好的统计特

6、性 抗线性分析 抗统计分析 具有非线性的的FA理论很不完善，通常采用线性以及非线性的。可将此类产生器分为驱动部分和非线性组合部分。 驱动部分控制状态转移 非线性组合部分提供统计特性良好的序列,2020/7/21,Page: 14,流密码：两种常见的密钥流产生器,LFSR：线性反馈移位寄存器流密码产生密钥流的主要组成部分。,2020/7/21,Page: 15,流密码：反馈移位寄存器的概念,基本概念 级数(Stages)：存储单元数n 状态(State)：n个存储单元的存数(ki, , ki+n-1) 反馈函数：f(ki, ki+1, , ki+n-1)是状态(ki, ki+n-1)的函数 线性

7、反馈移位寄存器(LFSR)：f 为线性函数 非线性反馈移位寄存器： f 为非线性函数,2020/7/21,Page: 16,流密码：反馈移位寄存器,寄存,移位,反馈,2020/7/21,Page: 17,流密码：线性反馈移位寄存器,f(x)为线性函数，输出序列满足下式,2020/7/21,Page: 18,流密码：LFSR的特征多项式,LFSR的特征多项式：以LFSR的反馈系数所决定的一元高次多项式 又称反馈多项式。 由于ciGF(2)(i = 1,2,n)，所以有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个。,2020/7/21,Page: 19,流密码：LFSR的生成函数,

8、给定序列 kii0，幂级数 称为该序列的生成函数 定理：令kii0(f)，f(x)是反馈多项式，令k(x)是kii0的生成函数，则 其中,2020/7/21,Page: 20,流密码：LFSR的生成函数,定理证明,2020/7/21,Page: 21,流密码：LFSR的周期,LFSR 周期的真正涵义？ 定义：设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或者阶。 定理：设序列ki的特征多项式p(x)定义GF(2)上，p是p(x)的周期，则ki的周期r | p。 定理：设序列ki的特征多项式p(x)定义GF(2)上，且p(x)是不可约多项式， p是p(x)的

9、周期，则ki的周期为p。,2020/7/21,Page: 22,流密码：LFSR的周期,m序列：序列ki0in的周期达到最大2n-1时，称该序列为m序列。 定理：以f(x)为特征多项式的LFSR的输出序列是m序列的充要条件为f(x)是本原的。 m序列的性质 n级m序列的周期为2n1，周期随n增加而指数级递增； 只要知道n次本原多项式，m序列极易生成； m序列极不安全，只要泄露2n位连续数字，就可完全确定出反馈多项式系数。,阶为2n-1的n次不可约多项式,2020/7/21,Page: 23,流密码：LFSR的周期,m序列的破译 已知ki, ki+1, ki+2n，由递推关系式可得出下式 式中有

10、n个线性方程和n个未知量，故可惟一解出ci，0in-1。,2020/7/21,Page: 24,流密码：非线性序列,LFSR虽然不能直接作为密钥流用，但可作为驱动源以其输出推动一个非线性组合函数所决定的电路来产生非线性序列。这就是所谓非线性前馈序列生成器。 LFSR用来保证密钥流的周期长度、平衡性等； 非线性组合函数用来保证密钥流的各种密码性质，以抗击各种可能的攻击。,2020/7/21,Page: 25,流密码：非线性前馈序列,前馈函数F(非线性组合函数) 输出序列的周期性、随机性、线性复杂度以及相关免疫性之间的关系,2020/7/21,Page: 26,流密码：J-K触发器,J-K触发器是

11、一个非线性器件，有两个输入端j和k，输出为qi。输出不仅依赖于输入，还依赖于前一个输出位qi-1，即 其结构及逻辑真值表如下所示,2020/7/21,Page: 27,流密码：J-K触发器的非线性序列生成器,ak和bk被称为非线性序列生成器的驱动序列。 性质：设ak和bk分别为x级和y级m序列。当x和y互素，且a0 + b0 =1时，序列ck的周期为(2x-1)(2y-1)。,2020/7/21,Page: 28,流密码：多路选择序列,有n种输入序列b0(t), bn-1(t) ，在地址序列a1(t),am -1 (t)的控制下决定输出取自某个输入比特。 Pless生成器 例如取m级LFSR生

12、成m序列作地址控制，取n级LFSR生成的m序列作为输入序列。,2020/7/21,Page: 29,对称密码体制组成,流密码 分组密码 数据加密标准(DES) 高级加密标准(AES),2020/7/21,Page: 30,对称密码体制：分组密码,分组密码的工作原理 将明文分成n个块，m1, m2, , mn； 对每个块执行相同的变换，从而生成n个密文块，c1, c2, , cn。 分组密码的工作模式：明文分组固定，消息的数据量不同，数据格式各式各样。为了适应各种应用环境，有四种工作模式。 电子编码薄模式(EBC) 密码分组链接模式(CBC) 密码反馈模式(CFB) 输出反馈模式(OFB),20

13、20/7/21,Page: 31,分组密码：分组密码的工作模式比较,2020/7/21,Page: 32,分组密码：分组密码的经典工作模式,电子编码薄模式,密码分组链接模式,输出反馈模式,2020/7/21,Page: 33,分组密码：分组密码的扩散与压缩,分组密码的基本过程 将明文分成m个块，M1, M2, , Mm； 对每个块执行相同的变换，从而生成m个密文块，C1, C2, , Cm。,2020/7/21,Page: 34,分组密码：分组密码的扩展与压缩,将明文x和密文y表示成分别小于2m和2n的整数，并用分量形式描述。每个分量分别用xi，yiGF(2) 表示，即： 若nm，则为有数据扩

14、展的分组密码； 若nm，则为有数据压缩的分组密码。 分组密码就是将|x|映射为|y|，(|x|0,1,2m-1,|y|0,1,2n-1)即为到其自身的一个置换，即 y = (x),2020/7/21,Page: 35,分组密码：分组密码的置换,设明文分组长度为n比特，则明文分组的取值为2n。为了使加密运算可逆，每一个明文对应的密文唯一，这样的变换是可逆的，并称明文到密文的变换为置换。 基本的置换 左循环移位(Shift left circular)代换、右循环移位(Shift right circular)代换 模2n加1(Addition with module)代换 线性变换(Linear

15、 transformation) 换位(Transposition)代换 连线交叉或坐标置换 仿射变换(Affine transform),2020/7/21,Page: 36,分组密码：Feistel网络,Feistel网络 将n bit明文分成为左右各半、长为n/2 bit的段，以L和R表示。然后进行多轮迭代，其第i轮迭代的输出为前轮输出的函数 Li =Ri-1 Ri =Li-1 f(Ri-1, ki) 式中，ki是第i轮用的子密钥，f是任意密码轮函数。 Feistel网络的特征 保证加密和解密可采用同一算法实施。 在设计整个分组密码的代换网络时，要求输出的每比特密文都和输入的明文及密钥各

16、比特有关，这对增加密码强度有好处。,2020/7/21,Page: 37,分组密码：迭代分组密码,迭代分组密码：若以一个简单函数f，进行多次迭代，就称其为迭代密码。每次迭代称作一轮(Round)，相应函数f称作轮函数。每一轮输出都是以前一轮输出作为输入参数的函数，即yi=fyi-1, ki，其中ki是第i轮迭代用的子密钥，由秘密密钥k通过密钥生成算法产生。,2020/7/21,Page: 38,分组密码：分组密码的填充问题,问题的由来 分组加密法是作用于有固定大小的明文/密文块。如果明文的大小不是块大小的整数倍怎样处理？ 分组密码的填充：添加足够多的特殊字符，使得明文长度是块大小的整数倍。 填充必须可逆 一种可行的填充方法 用文件结束字符表示明文分组的最后一个字节； 每一个分组都必须以0、1或者0、1交替的模式填充，即使明文以分组的边界结束，也必须添加一个整分组。,2020/7/21,Page: 39,分组密码：分组密码的评估,分组密码如何才算是安全？ 密钥必须足够大，使强力攻击失效或者得