对称密码体制

1、2022-4-1Page: 1对称密码体制杨秋伟湖南大学 计算机与通信学院2022-4-1Page: 2对称密码体制o对称密码体制的特征对称密码体制的特征n加密密钥和解密密钥相同p对称密码体制的主要研究课题对称密码体制的主要研究课题n密钥的产生n密钥的管理加密器EK解密器DK密文密文明文明文明文明文K密钥产生器K2022-4-1Page: 3对称密码体制组成o流密码o分组密码o数据加密标准(DES)o高级加密标准(AES)2022-4-1Page: 4流密码：流密码引论流密码引论o流密码流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如按位)，字符分别与密钥流作用进行加密，解密时以

2、同步产生的同样的密钥流实现。o流密码强度完全依赖于密钥序列的随机性随机性(Randomness)和不可预测不可预测性性(Unpredictability)。n核心问题是密钥流的产生密钥流生成器的设计n保持收发两端密钥流的精确同步是实现可靠解密的关键技术2022-4-1Page: 5流密码：流密码的基本概念流密码的基本概念o流密码的基本思想：流密码的基本思想：假设存在着明文串x = x0 x1x2n利用密钥k和密钥流发生器f产生一个密钥流z = z0z1z2。其中，zi = f(k,i)，i是加密器中的记忆元件在时刻i的状态，f是以密钥k和i作为输入参数的函数；n加密加密： y = y0y1y2

3、 = Ez0(x0) Ez1(x1) Ez1(x1)；内部记忆元件yi= Ezi(xi)xiyik2022-4-1Page: 6流密码：同步流密码同步流密码 o同步流密码同步流密码：加密器中记忆元件的存储状态i独立于明文字符。o同步流密码加密器同步流密码加密器n密钥流产生器n加密变换器p加密变换器一般采用二元逻辑运算XOR，即有限域GF(2)上讨论的二元加密流密码，变换表示为：yi = zi xip一次一密乱码本一次一密乱码本是加法流密码的原型2022-4-1Page: 7流密码：流密码的密钥流产生器流密码的密钥流产生器o密钥流产生器的内涵密钥流产生器的内涵n输入：密钥k和加密器中的记忆元件在

4、时刻i的状态i；n输出：密钥流zi状态状态i密钥密钥k状态状态i+1密钥流密钥流zi2022-4-1Page: 8流密码：密钥流生成器的设计原则密钥流生成器的设计原则o足够长的周期足够长的周期o高线性复杂度高线性复杂度o统计性能良好统计性能良好o足够的足够的“混乱混乱”n强调密钥的作用，增加密钥与密文之间关系的复杂性o足够的足够的“扩散扩散”n小扰动的影响波及到全局密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性o抵抗不同形式的攻击抵抗不同形式的攻击2022-4-1Page: 9流密码：有限状态自动机有限状态自动机(FA) o具有离散输入和输出(输入集和输出集均有限)的

5、一种数学模型n有限状态集S=si|i=1,2,ln有限输入字符集X=Xi|i=1,2,mn有限输出字符集Y=Yk|k=1,2,nn转移函数o Yjf1(sj, Xj)o Sj+1 f2(sj, Xj) 即在状态sj，输入字符Xj时，输出为Yj，状态转移为Sj+1。2022-4-1Page: 10流密码：有限状态自动机举例有限状态自动机举例o例一例一nS=s1,s2,s3,X=x1, x2,x3,Y=y1,y2,y3n转移函数f1x1x2x3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2x3s1s2s3s2s3s1s1s2s3s3s1s22022-4-1Page: 11流密码：有限

6、状态自动机举例有限状态自动机举例o若输入为x1x2x1x3x3x1o初始状态s1o输出为 y1y1y2y1y3y12022-4-1Page: 12流密码：基于基于FA的密钥流产生器的密钥流产生器o同步流密码的密钥流产生器可看为一个参数为k的FA：输出集Z，状态集，状态转移函数和输出函数，初态0o设计的关键是(phi fai)和(psi psai)ikkzi2022-4-1Page: 13流密码：基于基于FA的密钥流产生器的密钥流产生器o一个良好的密钥流产生器一个良好的密钥流产生器n极大的周期n良好的统计特性n抗线性分析n抗统计分析o具有非线性的的FA理论很不完善，通常采用线性以及非线性的。可将

7、此类产生器分为驱动部分驱动部分和非线性组合非线性组合部分。n驱动部分控制状态转移n非线性组合部分提供统计特性良好的序列2022-4-1Page: 14流密码：两种常见两种常见的密钥流产生器的密钥流产生器LFSR非线性组合函数ziLFSR1LFSR2LFSR3非线性组合函数ziLFSR：线性反馈移位寄存器流密码产生密钥流的主要组成部分。2022-4-1Page: 15流密码：反馈移位寄存器的概念反馈移位寄存器的概念o基本概念基本概念n级数级数(Stages)：存储单元数nn状态状态(State)：n个存储单元的存数(ki, , ki+n-1) n反馈函数：反馈函数：f(ki, ki+1, , k

8、i+n-1)是状态(ki, ki+n-1)的函数n线性反馈移位寄存器线性反馈移位寄存器(LFSR)：f 为线性函数n非线性反馈移位寄存器：非线性反馈移位寄存器： f 为非线性函数2022-4-1Page: 16流密码：反馈移位寄存器反馈移位寄存器f(ki, ki+1, , ki+n-1)ki+n-1ki+n-2ki+1kiki+n输出序列寄存移位反馈2022-4-1Page: 17流密码：线性反馈移位寄存器线性反馈移位寄存器of(x)为线性函数线性函数，输出序列满足下式1011( ,)002i nii nini nikf kkc kckic ，其中：，或1， 是模 加法。ki+n-1ki+n-

9、2ki+1kicn-1cn-2c1c0ki+n输出序列2022-4-1Page: 18流密码：LFSR的特征多项式的特征多项式oLFSR的特征多项式：的特征多项式：以LFSR的反馈系数所决定的一元高次多项式 又称反馈多项式反馈多项式。p由于ciGF(2)(i = 1,2,n)，所以有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个。211210( )1.nnnjnnjjf xc xc xcxc xc x 2022-4-1Page: 19流密码：LFSR的生成函数的生成函数 p给定序列 kii0，幂级数幂级数称为该序列的生成函数生成函数p定理：定理：令kii0(f)，f(x)是反馈多

10、项式，令k(x)是kii0的生成函数，则 其中11( )iiik xk x( )( )( )a xk xf x111( )()jnnjlnjljla xcxa x2022-4-1Page: 20流密码：LFSR的生成函数的生成函数 o定理证明定理证明,00min()001000()0( ) ( )()()()( )()()( )nilililj njn lj ljljnnjjn lj ln lj ljlj n lnjtj ntj njk x f xk xc xckxckxckxa xc kxnlta x 2022-4-1Page: 21流密码：LFSR的周期的周期oLFSR 周期的真正涵义？周

11、期的真正涵义？o定义定义：设p(x)是GF(2)上的多项式，使p(x)|(xp-1)的最小p称为p(x)的周期或者阶。o定理定理：设序列ki的特征多项式p(x)定义GF(2)上，p是p(x)的周期，则ki的周期r | p。o定理定理：设序列ki的特征多项式p(x)定义GF(2)上，且p(x)是不可约多项式， p是p(x)的周期，则ki的周期为p。2022-4-1Page: 22流密码：LFSR的周期的周期om序列：序列：序列ki0in的周期达到最大2n-1时，称该序列为m序列。o定理：定理：以f(x)为特征多项式的LFSR的输出序列是m序列的充要条件为f(x)是本原的。om序列的性质序列的性质

12、nn级m序列的周期为2n1，周期随n增加而指数级递增；n只要知道n次本原多项式，m序列极易生成；nm序列极不安全，只要泄露2n位连续数字，就可完全确定出反馈多项式系数。阶为2n-1的n次不可约多项式2022-4-1Page: 23流密码：LFSR的周期的周期om序列的破译序列的破译n已知ki, ki+1, ki+2n，由递推关系式可得出下式n式中有n个线性方程和n个未知量，故可惟一解出ci，0in-1。121110212111.ninininninininiiiniiikkkccckkkkkkkkk2022-4-1Page: 24流密码：非线性序列非线性序列oLFSR虽然不能直接作为密钥流用，

13、但可作为驱动源以其输出推动一个非线性组合函数非线性组合函数所决定的电路来产生非线性序列。这就是所谓非线性前馈序列生成器非线性前馈序列生成器。nLFSR用来保证密钥流的周期长度、平衡性等；n非线性组合函数用来保证密钥流的各种密码性质，以抗击各种可能的攻击。2022-4-1Page: 25流密码：非线性前馈序列非线性前馈序列o前馈函数前馈函数F(非线性组合函数)o输出序列的周期性、随机性、线性复杂度以及相关免疫性之间的关系 LFRSFki2022-4-1Page: 26流密码：J-K触发器触发器pJ-K触发器触发器是一个非线性器件，有两个输入端j和k，输出为qi。输出不仅依赖于输入，还依赖于前一个

14、输出位qi-1，即p其结构及逻辑真值表如下所示121112(),iiqxx qxx xJK其中分别为 和 的输入。JKqk00110101qk-10 11kqJKR = qk-1qk2022-4-1Page: 27流密码：J-K触发器的非线性序列生成器触发器的非线性序列生成器oak和bk被称为非线性序列生成器的驱动序列。o性质性质：设ak和bk分别为x级和y级m序列。当x和y互素，且a0 + b0 =1时，序列ck的周期为(2x-1)(2y-1)。LFSR1LFSR2akbkJKck2022-4-1Page: 28流密码：多路选择序列多路选择序列p有n种输入序列b0(t), bn-1(t) ，

15、在地址序列a1(t),am -1 (t)的控制下决定输出取自某个输入比特。 Pless生成器生成器n例如取m级LFSR生成m序列作地址控制，取n级LFSR生成的m序列作为输入序列。)()()(110tbtbtbn )()()(110tatatam制控址地可供选择的输入2022-4-1Page: 29对称密码体制组成o流密码o分组密码o数据加密标准(DES)o高级加密标准(AES)2022-4-1Page: 30对称密码体制：分组密码分组密码o分组密码的工作原理分组密码的工作原理n将明文分成n个块，m1, m2, , mn；n对每个块执行相同的变换，从而生成n个密文块，c1, c2, , cn。

16、p分组密码的工作模式分组密码的工作模式：明文分组固定，消息的数据量不同，数据格式各式各样。为了适应各种应用环境，有四种工作模式。n电子编码薄模式(EBC)n密码分组链接模式(CBC)n密码反馈模式(CFB)n输出反馈模式(OFB)2022-4-1Page: 31分组密码：分组密码的工作模式比较分组密码的工作模式比较模式描述用途电码本模式(ECB)每个明文组独立地以同一密钥加密。传送短数据密码分组链接模式(CBC)加密算法的输入是当前明文组与前一密文组的异或。传送数据分组；认证。密码反馈模式(CFB)每次只处理输入的j比特，将上一次的密文用作加密算法的输入以产生伪随机输出，该输出再与当前明文异或

17、以产生当前密文。传送数据流；认证。输出反馈模式(OFB)与CFB类似，不同之处是本次加密算法的输入为前一次加密算法的输出。有扰信道上(无线通讯)传送数据流2022-4-1Page: 32分组密码：分组密码的经典工作模式分组密码的经典工作模式电子编码薄模式密码分组链接模式输出反馈模式2022-4-1Page: 33分组密码：分组密码的扩散与压缩分组密码的扩散与压缩o分组密码的基本过程分组密码的基本过程n将明文分成m个块，M1, M2, , Mm；n对每个块执行相同的变换，从而生成m个密文块，C1, C2, , Cm。解密加密密钥k=(k0, k1, kt-1 )密钥k=(k0, k1, kt-1

18、 )明文x=(x0, x1, xm-1) 密文x=(y0, y1, yn-1) 明文x=(x0, x1, xm-1) 2022-4-1Page: 34分组密码：分组密码的扩展与压缩分组密码的扩展与压缩p将明文x和密文y表示成分别小于2m和2n的整数，并用分量形式描述。每个分量分别用xi，yiGF(2) 表示，即：n若nm，则为有数据扩展数据扩展的分组密码；n若n N / 2oKk1,kc = 0(p ) Kk1,kc = 1(p ) nT ) Kk1,kc = 0(p )2022-4-1Page: 69对称密码体制：分组密码的线形密码分析分组密码的线形密码分析o一个重要的数学结论一个重要的数学

19、结论(线性密码分析的思想，抗线性密码分析的强度就是非线性度)n如果明文和密文的关系是n维线性关系，且系数是密钥，则n个明文-密文对(而不是2n个)就可以破解密钥；n如果明文与密文的关系是n维r次函数关系，且系数是密钥，则nr 个明文-密文对就可以破解密钥；n如果虽然次数r较大，但明文与密文的关系“非常逼近”一个n维线性关系，则n个明文-密文对就可以“基本上”破解密钥。2022-4-1Page: 70对称密码体制：两重两重DES2022-4-1Page: 71对称密码体制：三重三重DES2022-4-1Page: 72对称密码体制组成o流密码o分组密码o数据加密标准(DES)o高级加密标准(AE

20、S)2022-4-1Page: 73对称密码体制：高级加密标准高级加密标准(AES)的由来的由来p1997年1月，美国NIST向全世界密码学界发出征集21世纪高级加密标准(Advanced Encryption Standard, AES)算法的公告，并成立了AES标准工作研究室，1997年4月15日的例会制定了对AES的评估标准。2022-4-1Page: 74对称密码体制：高级加密标准的评估标准高级加密标准的评估标准o高级加密标准(AES)的评估标准nAES是公开的；nAES为单钥体制分组密码；nAES的密钥长度可变，可按需要增大；nAES适于用软件和硬件实现；nAES可以自由地使用/按符

21、合美国国家标准(ANST)策略的条件使用；n满足以上要求的AES算法，需按下述条件判断优劣：a. 安全性，b. 计算效率， c. 内存要求， d. 使用简便性，e. 灵活性。2022-4-1Page: 75对称密码体制：高级加密标准高级加密标准(AES)的历史的历史o1997年4月15日NIST发起征集AES的活动(要求算法分组长度128比特，密钥长度128192256比特)；o1998年8月20日第一次AES候选大会，公布了15个候选算法；o1999年3月22日举行了第二次AES候选大会，选出5个候选算法；o2000年4月25日举行了第三次AES候选大会；o2000年10月2日公布Rijnd

22、ael算法作为候选算法。比利时的Joan Daemen和Vincent Rijmen 设计的 Rijndael 算法：是一个迭代分组密码，块长为128/192/256 bits，密钥长度为128、192、256 bits，相应的轮数为10/12/14。2022-4-1Page: 76AES：AES的特征的特征oAES特征特征nAES是分组密码，属于Square结构n加密、解密相似但不对称n密钥长度和分组长度均可变，密钥长度和分组长度可以独立地指定为128比特、192比特或256比特n有较好的数学理论作为基础n结构简单、速度快n能在多种平台上以较快的速度实现2022-4-1Page: 77AES

23、：消息分组和密钥分组消息分组和密钥分组o消息分组和密钥分组分别按字节进行划分按字节进行划分(一个字节8比特)，为简单起见，只讨论密钥长度128比特、消息长度192比特的情形。n明文分组 = a00, , a30, , a05, , a35n密钥分组 = k00, , k30, , k03, , k33a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k332022-4-1Page: 78AES：迭代轮数与密钥、消

24、息分组的关系迭代轮数与密钥、消息分组的关系oRijndael算法同算法同DES一样，由多基本的变换单位一样，由多基本的变换单位“轮轮”多次迭代而成。多次迭代而成。o迭代轮数与密钥、消息分组的关系表，其中迭代轮数与密钥、消息分组的关系表，其中n以Nr表示迭代轮数nNb表示消息分组按字节划分的矩阵列数(行数等于4)nNk表示密钥分组按字节划分的矩阵列数(行数等于4)NrNb=4Nb=6Nb=8Nk=4 10 12 14Nk=6 12 12 14Nk=8 14 14 142022-4-1Page: 79AES：轮变换轮变换o轮变换轮变换Round(State, RoundKey)nState：轮消息

25、矩阵，既作为输入，又作为输出；nRoundKey：轮密钥矩阵，它由输入密钥通过密钥表导出。o轮变换由四个不同的变换组成轮变换由四个不同的变换组成(除最后一轮除最后一轮)o最后一轮记为最后一轮记为FinalRound(State, RoundKey)n它等于不使用MixColumns函数的Round(State, RoundKey)Round(State, RoundKey) SubBytes(State); ShiftRows(State); MixColumns(State); AddRoundKey(State, RoundKey); 2022-4-1Page: 80AES：SubByte

26、s(State)oSubBytes为State的每一个字节提供一个非线形变换非线形变换，任一非零字节xGF(28)被下面的变换所代换(仿射变换仿射变换)y = Ax-1 + b2022-4-1Page: 81AES： SubBytes(State)o查表法查表法定时分析攻击定时分析攻击n计算x-1 (x, x-1)n计算y包含矩阵A和向量b，(x, y)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b2

27、4b25b30b31b32b33b34b35S-boxaijbij2022-4-1Page: 82AES：ShiftRows(State)oShiftRows在State的每行运算，它只重排了元素的位置而不改变元素本身，实质为换位密码，换位密码，以128比特的明文长度为例n对在第i行的元素，换位变换就是“循环向右移动” 4 i个位置。o字节移位关系表NbC1C2C34321632183142022-4-1Page: 83AES：MixColumns(State)oMixColumns在State的每列上作用，列作为GF(28)上的多项式，每次迭代的输出为一列s(x) = c(x) . s(x)

28、 mod(x4 + 1) 其中，c(x) = 03 . x3 + 01 . x3 + 01 . x3 + 02, 内的数表示字节c(x)与与x4 + 1互素互素2022-4-1Page: 84AES：AddRoundKey操作操作o按比特在F2上相加(XOR)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35 =b00b01b02b03b04b05b10b11

29、b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b352022-4-1Page: 85AES：密钥编排密钥编排o密钥编排密钥编排n密钥编排是指从种子密钥得到轮密钥的过程，它由密钥扩展和轮密钥选取两部分组成o轮密钥的比特数等于分组长度乘以轮数加1 = 32 Nb (Nr + 1)；o种子密钥被扩展成为扩展密钥；o轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，如此下去。2022-4-1Page: 86AES：KeyExpansion(key, w)oKeyExpansion(key, w)nkey用于存储扩展

30、前的密钥；nw用于存储扩展后的密钥；o以以128比特的密钥为例比特的密钥为例n输入的密钥key直接被复制到密钥数组的前四个字，w0, w1, w2, w3；nw数组中下标不为4的倍数的元素按以下规则扩展wi = wi -1 wi - 42022-4-1Page: 87AES：KeyExpansion(key, w)n下标为4的倍数的元素按以下规则扩展o将一个字的四个字节循环左移一个字节，即将b0, b1, b2, b3变为b1, b2, b3, b0；o基于SubBytes对输入字中的每个字节进行代替；S盒盒o将步骤1和步骤2的结果再与轮常量Rconi相异或。oRconi = (RCi, 00

31、, 00, 00)nRC1 = 01nRCi = 2 . (RCi - 1)2022-4-1Page: 88AES：KeyExpansion() - Nk6KeyExpansion(byte key4 * Nk, word wNb * (Nr + 1) for(i = 0; i Nk; i+) wi = (key4 * i, key4 * i + 1, key4 * i + 2, key4 * i + 3); for(i = Nk; i Nb * (Nr + 1); i+) temp = wi - 1; if(i % Nk = 0) temp = SubBytes(temp 6KeyExpansion(byte key4 * Nk, word wNb * (Nr + 1) for(i = 0; i Nk;