对称密码体制ppt课件

2020/4/26,Page:1,对称密码体制,杨秋伟湖南大学计算机与通信学院,2020/4/26,Page:2,对称密码体制,对称密码体制的特征加密密钥和解密密钥相同对称密码体制的主要研究课题密钥的产生密钥的管理,2020/4/26,Page:3,对称密码体制组成,流密码分组密码数据加密标准(DES)高级加密标准(AES),2020/4/26,Page:4,流密码：流密码引论,流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如按位)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。核心问题是密钥流的产生密钥流生成器的设计保持收发两端密钥流的精确同步是实现可靠解密的关键技术,2020/4/26,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/4/26,Page:6,流密码：同步流密码,同步流密码：加密器中记忆元件的存储状态i独立于明文字符。同步流密码加密器密钥流产生器加密变换器加密变换器一般采用二元逻辑运算XOR，即有限域GF(2)上讨论的二元加密流密码，变换表示为：yi=zixi一次一密乱码本是加法流密码的原型,2020/4/26,Page:7,流密码：流密码的密钥流产生器,密钥流产生器的内涵输入：密钥k和加密器中的记忆元件在时刻i的状态i；输出：密钥流zi,状态i,密钥k,状态i+1,密钥流zi,2020/4/26,Page:8,流密码：密钥流生成器的设计原则,足够长的周期高线性复杂度统计性能良好足够的“混乱”强调密钥的作用，增加密钥与密文之间关系的复杂性足够的“扩散”小扰动的影响波及到全局密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性抵抗不同形式的攻击,2020/4/26,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+1f2(sj,Xj)即在状态sj，输入字符Xj时，输出为Yj，状态转移为Sj+1。,2020/4/26,Page:10,流密码：有限状态自动机举例,例一S=s1,s2,s3,X=x1,x2,x3,Y=y1,y2,y3转移函数,2020/4/26,Page:11,流密码：有限状态自动机举例,若输入为x1x2x1x3x3x1初始状态s1输出为y1y1y2y1y3y1,2020/4/26,Page:12,流密码：基于FA的密钥流产生器,同步流密码的密钥流产生器可看为一个参数为k的FA：输出集Z，状态集，状态转移函数和输出函数，初态0设计的关键是(phifai)和(psipsai),2020/4/26,Page:13,流密码：基于FA的密钥流产生器,一个良好的密钥流产生器极大的周期良好的统计特性抗线性分析抗统计分析具有非线性的的FA理论很不完善，通常采用线性以及非线性的。可将此类产生器分为驱动部分和非线性组合部分。驱动部分控制状态转移非线性组合部分提供统计特性良好的序列,2020/4/26,Page:14,流密码：两种常见的密钥流产生器,LFSR：线性反馈移位寄存器流密码产生密钥流的主要组成部分。,2020/4/26,Page:15,流密码：反馈移位寄存器的概念,基本概念级数(Stages)：存储单元数n状态(State)：n个存储单元的存数(ki,ki+n-1)反馈函数：f(ki,ki+1,ki+n-1)是状态(ki,ki+n-1)的函数线性反馈移位寄存器(LFSR)：f为线性函数非线性反馈移位寄存器：f为非线性函数,2020/4/26,Page:16,流密码：反馈移位寄存器,寄存,移位,反馈,2020/4/26,Page:17,流密码：线性反馈移位寄存器,f(x)为线性函数，输出序列满足下式,2020/4/26,Page:18,流密码：LFSR的特征多项式,LFSR的特征多项式：以LFSR的反馈系数所决定的一元高次多项式又称反馈多项式。由于ciGF(2)(i=1,2,n)，所以有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个。,2020/4/26,Page:19,流密码：LFSR的生成函数,给定序列kii0，幂级数称为该序列的生成函数定理：令kii0(f)，f(x)是反馈多项式，令k(x)是kii0的生成函数，则其中,2020/4/26,Page:20,流密码：LFSR的生成函数,定理证明,2020/4/26,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)的周期，则ki的周期为p。,2020/4/26,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/4/26,Page:23,流密码：LFSR的周期,m序列的破译已知ki,ki+1,ki+2n，由递推关系式可得出下式式中有n个线性方程和n个未知量，故可惟一解出ci，0in-1。,2020/4/26,Page:24,流密码：非线性序列,LFSR虽然不能直接作为密钥流用，但可作为驱动源以其输出推动一个非线性组合函数所决定的电路来产生非线性序列。这就是所谓非线性前馈序列生成器。LFSR用来保证密钥流的周期长度、平衡性等；非线性组合函数用来保证密钥流的各种密码性质，以抗击各种可能的攻击。,2020/4/26,Page:25,流密码：非线性前馈序列,前馈函数F(非线性组合函数)输出序列的周期性、随机性、线性复杂度以及相关免疫性之间的关系,2020/4/26,Page:26,流密码：J-K触发器,J-K触发器是一个非线性器件，有两个输入端j和k，输出为qi。输出不仅依赖于输入，还依赖于前一个输出位qi-1，即其结构及逻辑真值表如下所示,2020/4/26,Page:27,流密码：J-K触发器的非线性序列生成器,ak和bk被称为非线性序列生成器的驱动序列。性质：设ak和bk分别为x级和y级m序列。当x和y互素，且a0+b0=1时，序列ck的周期为(2x-1)(2y-1)。,2020/4/26,Page:28,流密码：多路选择序列,有n种输入序列b0(t),bn-1(t)，在地址序列a1(t),am-1(t)的控制下决定输出取自某个输入比特。Pless生成器例如取m级LFSR生成m序列作地址控制，取n级LFSR生成的m序列作为输入序列。,2020/4/26,Page:29,对称密码体制组成,流密码分组密码数据加密标准(DES)高级加密标准(AES),2020/4/26,Page:30,对称密码体制：分组密码,分组密码的工作原理将明文分成n个块，m1,m2,mn；对每个块执行相同的变换，从而生成n个密文块，c1,c2,cn。分组密码的工作模式：明文分组固定，消息的数据量不同，数据格式各式各样。为了适应各种应用环境，有四种工作模式。电子编码薄模式(EBC)密码分组链接模式(CBC)密码反馈模式(CFB)输出反馈模式(OFB),2020/4/26,Page:31,分组密码：分组密码的工作模式比较,2020/4/26,Page:32,分组密码：分组密码的经典工作模式,电子编码薄模式,密码分组链接模式,输出反馈模式,2020/4/26,Page:33,分组密码：分组密码的扩散与压缩,分组密码的基本过程将明文分成m个块，M1,M2,Mm；对每个块执行相同的变换，从而生成m个密文块，C1,C2,Cm。,2020/4/26,Page:34,分组密码：分组密码的扩展与压缩,将明文x和密文y表示成分别小于2m和2n的整数，并用分量形式描述。每个分量分别用xi，yiGF(2)表示，即：若nm，则为有数据扩展的分组密码；若nN/2Kk1,kc=0(p)Kk1,kc=1(p)Kk1,kc=0(p),2020/4/26,Page:69,对称密码体制：分组密码的线形密码分析,一个重要的数学结论(线性密码分析的思想，抗线性密码分析的强度就是非线性度)如果明文和密文的关系是n维线性关系，且系数是密钥，则n个明文-密文对(而不是2n个)就可以破解密钥；如果明文与密文的关系是n维r次函数关系，且系数是密钥，则nr个明文-密文对就可以破解密钥；如果虽然次数r较大，但明文与密文的关系“非常逼近”一个n维线性关系，则n个明文-密文对就可以“基本上”破解密钥。,2020/4/26,Page:70,对称密码体制：两重DES,2020/4/26,Page:71,对称密码体制：三重DES,2020/4/26,Page:72,对称密码体制组成,流密码分组密码数据加密标准(DES)高级加密标准(AES),2020/4/26,Page:73,对称密码体制：高级加密标准(AES)的由来,1997年1月，美国NIST向全世界密码学界发出征集21世纪高级加密标准(AdvancedEncryptionStandard,AES)算法的公告，并成立了AES标准工作研究室，1997年4月15日的例会制定了对AES的评估标准。,2020/4/26,Page:74,对称密码体制：高级加密标准的评估标准,高级加密标准(AES)的评估标准AES是公开的；AES为单钥体制分组密码；AES的密钥长度可变，可按需要增大；AES适于用软件和硬件实现；AES可以自由地使用/按符合美国国家标准(ANST)策略的条件使用；满足以上要求的AES算法，需按下述条件判断优劣：a.安全性，b.计算效率，c.内存要求，d.使用简便性，e.灵活性。,2020/4/26,Page:75,对称密码体制：高级加密标准(AES)的历史,1997年4月15日NIST发起征集AES的活动(要求算法分组长度128比特，密钥长度128192256比特)；1998年8月20日第一次AES候选大会，公布了15个候选算法；1999年3月22日举行了第二次AES候选大会，选出5个候选算法；2000年4月25日举行了第三次AES候选大会；2000年10月2日公布Rijndael算法作为候选算法。比利时的JoanDaemen和VincentRijmen设计的Rijndael算法：是一个迭代分组密码，块长为128/192/256bits，密钥长度为128、192、256bits，相应的轮数为10/12/14。,2020/4/26,Page:76,AES：AES的特征,AES特征AES是分组密码，属于Square结构加密、解密相似但不对称密钥长度和分组长度均可变，密钥长度和分组长度可以独立地指定为128比特、192比特或256比特有较好的数学理论作为基础结构简单、速度快能在多种平台上以较快的速度实现,2020/4/26,Page:77,AES：消息分组和密钥分组,消息分组和密钥分组分别按字节进行划分(一个字节8比特)，为简单起见，只讨论密钥长度128比特、消息长度192比特的情形。明文分组=a00,a30,a05,a35密钥分组=k00,k30,k03,k33,2020/4/26,Page:78,AES：迭代轮数与密钥、消息分组的关系,Rijndael算法同DES一样，由多基本的变换单位“轮”多次迭代而成。迭代轮数与密钥、消息分组的关系表，其中以Nr表示迭代轮数Nb表示消息分组按字节划分的矩阵列数(行数等于4)Nk表示密钥分组按字节划分的矩阵列数(行数等于4),2020/4/26,Page:79,AES：轮变换,轮变换Round(State,RoundKey)State：轮消息矩阵，既作为输入，又作为输出；RoundKey：轮密钥矩阵，它由输入密钥通过密钥表导出。轮变换由四个不同的变换组成(除最后一轮)最后一轮记为FinalRound(State,RoundKey)它等于不使用MixColumns函数的Round(State,RoundKey),Round(State,RoundKey)SubBytes(State);ShiftRows(State);MixColumns(State);AddRoundKey(State,RoundKey);,2020/4/26,Page:80,AES：SubBytes(State),SubBytes为State的每一个字节提供一个非线形变换，任一非零字节xGF(28)被下面的变换所代换(仿射变换)y=Ax-1+b,2020/4/26,Page:81,AES：SubBytes(State),查表法定时分析攻击计算x-1(x,x-1)计算y包含矩阵A和向量b，(x,y),aij,bij,2020/4/26,Page:82,AES：ShiftRows(State),ShiftRows在State的每行运算，它只重排了元素的位置而不改变元素本身，实质为换位密码，以128比特的明文长度为例对在第i行的元素，换位变换就是“循环向右移动”4i个位置。字节移位关系表,2020/4/26,Page:83,AES：MixColumns(State),MixColumns在State的每列上作用，列作为GF(28)上的多项式，每次迭代的输出为一列s(x)=c(x).s(x)mod(x4+1)其中，c(x)=03.x3+01.x3+01.x3+02,内的数表示字节,c(x)与x4+1互素,2020/4/26,Page:84,AES：AddRoundKey操作,按比特在F2上相加(XOR),=,2020/4/26,Page:85,AES：密钥编排,密钥编排密钥编排是指从种子密钥得到轮密钥的过程，它由密钥扩展和轮密钥选取两部分组成轮密钥的比特数等于分组长度乘以轮数加1=32Nb(Nr+1)；种子密钥被扩展成为扩展密钥；轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，如此下去。,2020/4/26,Page:86,AES：KeyExpansion(key,w),KeyExpansion(key,w)key用于存储扩展前的密钥；w用于存储扩展后的密钥；以128比特的密钥为例输入的密钥key直接被复制到密钥数组的前四个字，w0,w1,w2,w3；w数组中下标不为4的倍数的元素按以下规则扩展wi=wi-1wi-4,2020/4/26,Page:87,AES：KeyExpansion(key,w),下标为4的倍数的元素按以下规则扩展将一个字的四个字节循环左移一个字节，即将b0,b1,b2,b3变为b1,b2,b3,b0；基于SubBytes对输入字中的每个字节进行代替；S盒将步骤1和步骤2的结果再与轮常量Rconi相异或。Rconi=(RCi,00,00,00)RC1=01RCi=2.(RCi-1),2020/4/26,Page:88,AES：KeyExpansion()-Nk6,KeyExpansion(bytekey4*Nk,wordwNb*(Nr+1)for(i=0;iNk;i+)wi=(key4*i,key4*i+1,key4*i+2,key4*i+3);for(i=Nk;iNb*(Nr+1);i+)temp=wi-1;if(i%Nk=0)temp=SubBytes(temp6,KeyExpansion(bytekey4*Nk,wordwNb*(Nr+1)for(i=0;iNk;i+)wi=(key4*i,key4*i+1,key4*i+2,key4*i+3);for(i=Nk;iNb*(Nr+1);i+)temp=wi-1;if(i%Nk=0)temp=SubBytes(temp8)Rconi/Nk;elseif(i%Nk=4)temp=SubBytes(temp