对称密码体制

1、2021-5-25page: 1 对称密码体制 杨秋伟 湖南大学 计算机与通信学院 2021-5-25 page: 2 对称密码体制 o对称密码体制的特征对称密码体制的特征 n加密密钥和解密密钥相同 p对称密码体制的主要研究课题对称密码体制的主要研究课题 n密钥的产生 n密钥的管理 加密器 ek 解密器 dk 密文密文明文明文 明文明文 k 密钥产生器 k 2021-5-25 page: 3 对称密码体制组成 o流密码 o分组密码 o数据加密标准(des) o高级加密标准(aes) 2021-5-25 page: 4 流密码：流密码引论流密码引论 o流密码流密码是将明文划分成字符(如单个字母)

2、，或其编码的基本单元 (如按位)，字符分别与密钥流作用进行加密，解密时以同步产生的 同样的密钥流实现。 o流密码强度完全依赖于密钥序列的随机性随机性(randomness)和不可预测不可预测 性性(unpredictability)。 n核心问题是密钥流的产生密钥流生成器的设计 n保持收发两端密钥流的精确同步是实现可靠解密的关键技术 2021-5-25 page: 5 流密码：流密码的基本概念流密码的基本概念 o流密码的基本思想：流密码的基本思想：假设存在着明文串x = x0 x1x2 n利用密钥k和密钥流发生器f产生一个密钥流z = z0z1z2。其中， zi = f(k,i)，i是加密器中

3、的记忆元件在时刻i的状态，f是以密钥 k和i作为输入参数的函数； n加密加密： y = y0y1y2 = ez0(x0) ez1(x1) ez1(x1)； 内部记忆元件 yi= ezi(xi) xiyi k 2021-5-25 page: 6 流密码：同步流密码同步流密码 o同步流密码同步流密码：加密器中记忆元件的存储状态i独立于明文字符。 o同步流密码加密器同步流密码加密器 n密钥流产生器 n加密变换器 p加密变换器一般采用二元逻辑运算xor，即有限域gf(2)上讨论 的二元加密流密码，变换表示为：yi = zi xi p一次一密乱码本一次一密乱码本是加法流密码的原型 2021-5-25 p

4、age: 7 流密码：流密码的密钥流产生器流密码的密钥流产生器 o密钥流产生器的内涵密钥流产生器的内涵 n输入：密钥k和加密器中的记忆元件在时刻i的状态i； n输出：密钥流zi 状态状态i 密钥密钥k 状态状态i+1 密钥流密钥流zi 2021-5-25 page: 8 流密码：密钥流生成器的设计原则密钥流生成器的设计原则 o足够长的周期足够长的周期 o高线性复杂度高线性复杂度 o统计性能良好统计性能良好 o足够的足够的“混乱混乱” n强调密钥的作用，增加密钥与密文之间关系的复杂性 o足够的足够的“扩散扩散” n小扰动的影响波及到全局密文没有统计特征，明文一位影响密 文的多位，增加密文与明文之

5、间关系的复杂性 o抵抗不同形式的攻击抵抗不同形式的攻击 2021-5-25 page: 9 流密码：有限状态自动机有限状态自动机(fa) o具有离散输入和输出(输入集和输出集均有限)的一种数学模型 n有限状态集s=si|i=1,2,l n有限输入字符集x=xi|i=1,2,m n有限输出字符集y=yk|k=1,2,n n转移函数 o yjf1(sj, xj) o sj+1 f2(sj, xj) 即在状态sj，输入字符xj时，输出为yj，状态转移为sj+1。 2021-5-25 page: 10 流密码：有限状态自动机举例有限状态自动机举例 o例一例一 ns=s1,s2,s3,x=x1, x2,

6、x3,y=y1,y2,y3 n转移函数 f1x1x2x3 s1 s2 s3 y1 y2 y3 y3 y1 y2 y2 y3 y1 f2x1x2x3 s1 s2 s3 s2 s3 s1 s1 s2 s3 s3 s1 s2 2021-5-25 page: 11 流密码：有限状态自动机举例有限状态自动机举例 o若输入为 x1x2x1x3x3x1 o初始状态s1 o输出为 y1y1y2y1y3y1 2021-5-25 page: 12 流密码：基于基于fa的密钥流产生器的密钥流产生器 o同步流密码的密钥流产生器可看为一个参数为k的fa：输出集z， 状态集，状态转移函数和输出函数，初态0 o设计的关键是

7、(phi fai)和(psi psai) i k k zi 2021-5-25 page: 13 流密码：基于基于fa的密钥流产生器的密钥流产生器 o一个良好的密钥流产生器一个良好的密钥流产生器 n极大的周期 n良好的统计特性 n抗线性分析 n抗统计分析 o具有非线性的的fa理论很不完善，通常采用线性以及非线性的 。可将此类产生器分为驱动部分驱动部分和非线性组合非线性组合部分。 n驱动部分控制状态转移 n非线性组合部分提供统计特性良好的序列 2021-5-25 page: 14 流密码：两种常见两种常见的密钥流产生器的密钥流产生器 lfsr 非线性组合函数 zi lfsr1 lfsr2 lfs

8、r3 非 线 性 组 合 函 数 zi lfsr：线性反馈移位寄存器流密码产生密钥流的主要组成部分。 2021-5-25 page: 15 流密码：反馈移位寄存器的概念反馈移位寄存器的概念 o基本概念基本概念 n级数级数(stages)：存储单元数n n状态状态(state)：n个存储单元的存数(ki, , ki+n-1) n反馈函数：反馈函数：f(ki, ki+1, , ki+n-1)是状态(ki, ki+n-1)的函数 n线性反馈移位寄存器线性反馈移位寄存器(lfsr)：f 为线性函数 n非线性反馈移位寄存器：非线性反馈移位寄存器： f 为非线性函数 2021-5-25 page: 16

9、流密码：反馈移位寄存器反馈移位寄存器 f(ki, ki+1, , ki+n-1) ki+n-1 ki+n-2ki+1ki ki+n 输出序列 寄存 移位 反馈 2021-5-25 page: 17 流密码：线性反馈移位寄存器线性反馈移位寄存器 of(x)为线性函数线性函数，输出序列满足下式 1011 ( ,)002 i nii nini ni kf kkc kckic ，其中：，或1， 是模 加法。 ki+n-1ki+n-2ki+1ki cn-1cn-2c1c0ki+n 输出序列 2021-5-25 page: 18 流密码：lfsr的特征多项式的特征多项式 olfsr的特征多项式：的特征多项

10、式：以lfsr的反馈系数所决定的一元高次多项式 又称反馈多项式反馈多项式。 p由于cigf(2)(i = 1,2,n)，所以有2n组初始状态，即有2n个递推序 列，其中非恒零的有2n-1个。 21 121 0 ( )1. n nnj nnj j f xc xc xcxc xc x 2021-5-25 page: 19 流密码：lfsr的生成函数的生成函数 p给定序列 kii0，幂级数幂级数 称为该序列的生成函数生成函数 p定理：定理：令kii0(f)，f(x)是反馈多项式，令k(x)是kii0的生成函数， 则 其中 1 1 ( ) i i i k xk x ( ) ( ) ( ) a x k

11、x f x 1 11 ( )() jn njl njl jl a xcxa x 2021-5-25 page: 20 流密码：lfsr的生成函数的生成函数 o定理证明定理证明 , 00 min() 00 1 000 () 0 ( ) ( )()() () ( )()() ( ) n il il il j n j n lj l jl jnn jj n lj ln lj l jlj n l n j tj nt j nj k x f xk xc x ckx ckxckx a xc kxnlt a x 2021-5-25 page: 21 流密码：lfsr的周期的周期 olfsr 周期的真正涵义？周期

12、的真正涵义？ 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。 2021-5-25 page: 22 流密码：lfsr的周期的周期 om序列：序列：序列ki0in的周期达到最大2n-1时，称该序列为m序列。 o定理：定理：以f(x)为特征多项式的lfsr的输出序列是m序列的充要条件 为f(x)是本原的。

13、 om序列的性质序列的性质 nn级m序列的周期为2n1，周期随n增加而指数级递增； n只要知道n次本原多项式，m序列极易生成； nm序列极不安全，只要泄露2n位连续数字，就可完全确定出反 馈多项式系数。 阶为2n-1的n次不 可约多项式 2021-5-25 page: 23 流密码：lfsr的周期的周期 om序列的破译序列的破译 n已知ki, ki+1, ki+2n，由递推关系式可得出下式 n式中有n个线性方程和n个未知量，故可惟一解出ci，0in-1。 12 1 1 1 0 21 21 11 . . . . . . . . . . . . ni ni ni nninini niii niii

14、 k k k c c c kkk kkk kkk 2021-5-25 page: 24 流密码：非线性序列非线性序列 olfsr虽然不能直接作为密钥流用，但可作为驱动源以其输出推动 一个非线性组合函数非线性组合函数所决定的电路来产生非线性序列。这就是所 谓非线性前馈序列生成器非线性前馈序列生成器。 nlfsr用来保证密钥流的周期长度、平衡性等； n非线性组合函数用来保证密钥流的各种密码性质，以抗击各种 可能的攻击。 2021-5-25 page: 25 流密码：非线性前馈序列非线性前馈序列 o前馈函数前馈函数f(非线性组合函数) o输出序列的周期性、随机性、线性复杂度以及相关免疫性之间的 关系

15、 lfrs f ki 2021-5-25 page: 26 流密码：j-k触发器触发器 pj-k触发器触发器是一个非线性器件，有两个输入端j和k，输出为qi。输出 不仅依赖于输入，还依赖于前一个输出位qi-1，即 p其结构及逻辑真值表如下所示 121112 (), ii qxx qxx xjk 其中分别为 和 的输入。 jkqk 0 0 1 1 0 1 0 1 qk-1 0 1 1k q j k r = qk-1 qk 2021-5-25 page: 27 流密码：j-k触发器的非线性序列生成器触发器的非线性序列生成器 oak和bk被称为非线性序列生成器的驱动序列。 o性质性质：设ak和bk分

16、别为x级和y级m序列。当x和y互素，且a0 + b0 =1时，序列ck的周期为(2x-1)(2y-1)。 lfsr1 lfsr2 ak bk j k ck 2021-5-25 page: 28 流密码：多路选择序列多路选择序列 p有n种输入序列b0(t), bn-1(t) ，在地址序列a1(t),am -1 (t)的控制下 决定输出取自某个输入比特。 pless生成器生成器 n例如取m级lfsr生成m序列作地址控制，取n级lfsr生成的m 序列作为输入序列。 )()()( 110 tbtbtb n )( )( )( 1 1 0 ta ta ta m 制 控 址 地 可供选择的输入 2021-5

17、-25 page: 29 对称密码体制组成 o流密码 o分组密码 o数据加密标准(des) o高级加密标准(aes) 2021-5-25 page: 30 对称密码体制：分组密码分组密码 o分组密码的工作原理分组密码的工作原理 n将明文分成n个块，m1, m2, , mn； n对每个块执行相同的变换，从而生成n个密文块，c1, c2, , cn。 p分组密码的工作模式分组密码的工作模式：明文分组固定，消息的数据量不同，数据 格式各式各样。为了适应各种应用环境，有四种工作模式。 n电子编码薄模式(ebc) n密码分组链接模式(cbc) n密码反馈模式(cfb) n输出反馈模式(ofb) 2021

18、-5-25 page: 31 分组密码：分组密码的工作模式比较分组密码的工作模式比较 模式描述用途 电码本模式(ecb)每个明文组独立地以同一密钥加密。传送短数据 密码分组链接模式 (cbc) 加密算法的输入是当前明文组与前一密文组 的异或。 传送数据分组； 认证。 密码反馈模式(cfb)每次只处理输入的j比特，将上一次的密文用 作加密算法的输入以产生伪随机输出，该输 出再与当前明文异或以产生当前密文。 传送数据流；认 证。 输出反馈模式(ofb)与cfb类似，不同之处是本次加密算法的输 入为前一次加密算法的输出。 有扰信道上(无线 通讯)传送数据流 2021-5-25 page: 32 分组

19、密码：分组密码的经典工作模式分组密码的经典工作模式 电子编码薄模式 密码分组链接模式 输出反馈模式 2021-5-25 page: 33 分组密码：分组密码的扩散与压缩分组密码的扩散与压缩 o分组密码的基本过程分组密码的基本过程 n将明文分成m个块，m1, m2, , mm； n对每个块执行相同的变换，从而生成m个密文块，c1, c2, , cm。 解密加密 密钥k=(k0, k1, kt-1 )密钥k=(k0, k1, kt-1 ) 明文x=(x0, x1, xm-1) 密文x=(y0, y1, yn-1) 明文x=(x0, x1, xm-1) 2021-5-25 page: 34 分组密码

20、：分组密码的扩展与压缩分组密码的扩展与压缩 p将明文x和密文y表示成分别小于2m和2n的整数，并用分量形式描述。 每个分量分别用xi，yigf(2) 表示，即： n若nm，则为有数据扩展数据扩展的分组密码； n若n n / 2 okk1,kc = 0(p ) kk1,kc = 1(p ) nt ) kk1,kc = 0(p ) 2021-5-25 page: 69 对称密码体制：分组密码的线形密码分析分组密码的线形密码分析 o一个重要的数学结论一个重要的数学结论(线性密码分析的思想，抗线性密码分析的强 度就是非线性度) n如果明文和密文的关系是n维线性关系，且系数是密钥，则n个 明文-密文对(

21、而不是2n个)就可以破解密钥； n如果明文与密文的关系是n维r次函数关系，且系数是密钥，则 nr 个明文-密文对就可以破解密钥； n如果虽然次数r较大，但明文与密文的关系“非常逼近”一个n 维线性关系，则n个明文-密文对就可以“基本上”破解密钥。 2021-5-25 page: 70 对称密码体制：两重两重des 2021-5-25 page: 71 对称密码体制：三重三重des 2021-5-25 page: 72 对称密码体制组成 o流密码 o分组密码 o数据加密标准(des) o高级加密标准(aes) 2021-5-25 page: 73 对称密码体制：高级加密标准高级加密标准(aes)

22、的由来的由来 p1997年1月，美国nist向全世界密码学界发出征集21世纪高级加密 标准(advanced encryption standard, aes)算法的公告，并成立了 aes标准工作研究室，1997年4月15日的例会制定了对aes的评估 标准。 2021-5-25 page: 74 对称密码体制：高级加密标准的评估标准高级加密标准的评估标准 o高级加密标准(aes)的评估标准 naes是公开的； naes为单钥体制分组密码； naes的密钥长度可变，可按需要增大； naes适于用软件和硬件实现； naes可以自由地使用/按符合美国国家标准(anst)策略的条件 使用； n满足以上

23、要求的aes算法，需按下述条件判断优劣：a. 安全性， b. 计算效率， c. 内存要求， d. 使用简便性，e. 灵活性。 2021-5-25 page: 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日公布rijndael算法作为候选算法。比利时

24、的joan daemen和vincent rijmen 设计的 rijndael 算法：是一个迭代分组密 码，块长为128/192/256 bits，密钥长度为128、192、256 bits，相 应的轮数为10/12/14。 2021-5-25 page: 76 aes：aes的特征的特征 oaes特征特征 naes是分组密码，属于square结构 n加密、解密相似但不对称 n密钥长度和分组长度均可变，密钥长度和分组长度可以独立地 指定为128比特、192比特或256比特 n有较好的数学理论作为基础 n结构简单、速度快 n能在多种平台上以较快的速度实现 2021-5-25 page: 77

25、aes：消息分组和密钥分组消息分组和密钥分组 o消息分组和密钥分组分别按字节进行划分按字节进行划分(一个字节8比特)，为简单 起见，只讨论密钥长度128比特、消息长度192比特的情形。 n明文分组 = a00, , a30, , a05, , a35 n密钥分组 = k00, , k30, , k03, , k33 a00a01a02a03a04a05 a10a11a12a13a14a15 a20a21a22a23a24a25 a30a31a32a33a34a35 k00k01k02k03 k10k11k12k13 k20k21k22k23 k30k31k32k33 2021-5-25 pag

26、e: 78 aes：迭代轮数与密钥、消息分组的关系迭代轮数与密钥、消息分组的关系 orijndael算法同算法同des一样，由多基本的变换单位一样，由多基本的变换单位“轮轮”多次迭代而成。多次迭代而成。 o迭代轮数与密钥、消息分组的关系表，其中迭代轮数与密钥、消息分组的关系表，其中 n以nr表示迭代轮数 nnb表示消息分组按字节划分的矩阵列数(行数等于4) nnk表示密钥分组按字节划分的矩阵列数(行数等于4) nrnb=4nb=6nb=8 nk=4 10 12 14 nk=6 12 12 14 nk=8 14 14 14 2021-5-25 page: 79 aes：轮变换轮变换 o轮变换轮变

27、换round(state, roundkey) nstate：轮消息矩阵，既作为输入，又作为输出； nroundkey：轮密钥矩阵，它由输入密钥通过密钥表导出。 o轮变换由四个不同的变换组成轮变换由四个不同的变换组成(除最后一轮除最后一轮) o最后一轮记为最后一轮记为finalround(state, roundkey) n它等于不使用mixcolumns函数的round(state, roundkey) round(state, roundkey) subbytes(state); shiftrows(state); mixcolumns(state); addroundkey(state,

28、 roundkey); 2021-5-25 page: 80 aes：subbytes(state) osubbytes为state的每一个字节提供一个非线形变换非线形变换，任一非零字 节xgf(28)被下面的变换所代换(仿射变换仿射变换) y = ax-1 + b 2021-5-25 page: 81 aes： subbytes(state) o查表法查表法定时分析攻击定时分析攻击 n计算x-1 (x, x-1) n计算y包含矩阵a和向量b，(x, y) a00a01a02a03a04a05 a10a11a12a13a14a15 a20a21a22a23a24a25 a30a31a32a33

29、a34a35 b00b01b02b03b04b05 b10b11b12b13b14b15 b20b21b22b23b24b25 b30b31b32b33b34b35 s-box aij bij 2021-5-25 page: 82 aes：shiftrows(state) oshiftrows在state的每行运算，它只重排了元素的位置而不改变元素 本身，实质为换位密码，换位密码，以128比特的明文长度为例 n对在第i行的元素，换位变换就是“循环向右移动” 4 i个位置。 o字节移位关系表 nbc1c2c3 4321 6321 8314 2021-5-25 page: 83 aes：mixco

30、lumns(state) omixcolumns在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互素互素 2021-5-25 page: 84 aes：addroundkey操作操作 o按比特在f2上相加(xor) a00a01a02a03a04a05 a10a11a12a13a14a15 a20a21a22a23a24a25 a30a31a32a33a34a35 k00k0

31、1k02k03k04k05 k10k11k12k13k14k15 k20k21k22k23k24k25 k30k31k32k33k34k35 = b00b01b02b03b04b05 b10b11b12b13b14b15 b20b21b22b23b24b25 b30b31b32b33b34b35 2021-5-25 page: 85 aes：密钥编排密钥编排 o密钥编排密钥编排 n密钥编排是指从种子密钥得到轮密钥的过程，它由密钥扩展和轮 密钥选取两部分组成 o轮密钥的比特数等于分组长度乘以轮数加1 = 32 nb (nr + 1)； o种子密钥被扩展成为扩展密钥； o轮密钥从扩展密钥中取，其中

32、第1轮轮密钥取扩展密钥的前nb个字， 第2轮轮密钥取接下来的nb个字，如此下去。 2021-5-25 page: 86 aes：keyexpansion(key, w) okeyexpansion(key, w) nkey用于存储扩展前的密钥； nw用于存储扩展后的密钥； o以以128比特的密钥为例比特的密钥为例 n输入的密钥key直接被复制到密钥数组的前四个字，w0, w1, w2, w3； nw数组中下标不为4的倍数的元素按以下规则扩展 wi = wi -1 wi - 4 2021-5-25 page: 87 aes：keyexpansion(key, w) n下标为4的倍数的元素按以下规

33、则扩展 o将一个字的四个字节循环左移一个字节，即将b0, b1, b2, b3变为 b1, b2, b3, b0； o基于subbytes对输入字中的每个字节进行代替；s盒盒 o将步骤1和步骤2的结果再与轮常量rconi相异或。 orconi = (rci, 00, 00, 00) nrc1 = 01 nrci = 2 . (rci - 1) 2021-5-25 page: 88 aes：keyexpansion() - nk6 keyexpansion(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 6 keyexpansion(byte key