对称密码体制

2023/10/24Page:1对称密码体制杨秋伟湖南大学计算机与通信学院2023/10/24Page:2对称密码体制对称密码体制的特征加密密钥和解密密钥相同对称密码体制的主要研究课题密钥的产生密钥的管理加密器EK解密器DK密文明文明文K密钥产生器K2023/10/24Page:3对称密码体制组成流密码分组密码数据加密标准(DES)高级加密标准(AES)2023/10/24Page:4流密码：流密码引论流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如按位)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。核心问题是密钥流的产生——密钥流生成器的设计保持收发两端密钥流的精确同步是实现可靠解密的关键技术2023/10/24Page:5流密码：流密码的基本概念流密码的基本思想：假设存在着明文串x=x0x1x2…利用密钥k和密钥流发生器f产生一个密钥流z=z0z1z2…。其中，zi=f(k,δi)，δi是加密器中的记忆元件在时刻i的状态，f是以密钥k和δi作为输入参数的函数；加密：y=y0y1y2…=Ez0(x0)Ez1(x1)Ez1(x1)…；内部记忆元件yi=Ezi(xi)xiyik2023/10/24Page:6流密码：同步流密码

同步流密码：加密器中记忆元件的存储状态δi独立于明文字符。同步流密码加密器密钥流产生器加密变换器加密变换器一般采用二元逻辑运算XOR，即有限域GF(2)上讨论的二元加密流密码，变换表示为：yi=zi⊕xi一次一密乱码本是加法流密码的原型2023/10/24Page:7流密码：流密码的密钥流产生器密钥流产生器的内涵输入：密钥k和加密器中的记忆元件在时刻i的状态δi；输出：密钥流zi状态δi密钥k状态δi+1密钥流zi2023/10/24Page:8流密码：密钥流生成器的设计原则足够长的周期高线性复杂度统计性能良好足够的“混乱”强调密钥的作用，增加密钥与密文之间关系的复杂性足够的“扩散”小扰动的影响波及到全局密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性抵抗不同形式的攻击2023/10/24Page:9流密码：有限状态自动机(FA)

具有离散输入和输出(输入集和输出集均有限)的一种数学模型有限状态集S={si|i=1,2,…,l}有限输入字符集X={Xi|i=1,2,…,m}有限输出字符集Y={Yk|k=1,2,…,n}转移函数Yj＝f1(sj,Xj)Sj+1

＝f2(sj,Xj)

即在状态sj，输入字符Xj时，输出为Yj，状态转移为Sj+1。2023/10/24Page:10流密码：有限状态自动机举例例一S={s1,s2,s3},X={x1,x2,x3},Y={y1,y2,y3}转移函数f1x1x2x3s1s2s3y1y2y3y3y1y2y2y3y1f2x1x2x3s1s2s3s2s3s1s1s2s3s3s1s22023/10/24Page:11流密码：有限状态自动机举例若输入为x1x2x1x3x3x1初始状态s1输出为

y1y1y2y1y3y12023/10/24Page:12流密码：基于FA的密钥流产生器同步流密码的密钥流产生器可看为一个参数为k的FA：输出集Z，状态集Σ，状态转移函数φ和输出函数ψ，初态

0设计的关键是φ(phifai)和ψ(psipsai)φ

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

为线性函数非线性反馈移位寄存器：f

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

给定序列{ki}i

0，幂级数称为该序列的生成函数定理：令{ki}i

0

(f)，f(x)是反馈多项式，令k(x)是{ki}i

0的生成函数，则其中2023/10/24Page:20流密码：LFSR的生成函数

定理证明2023/10/24Page: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。2023/10/24Page:22流密码：LFSR的周期m序列：序列{ki}0≤i≤n的周期达到最大2n-1时，称该序列为m序列。定理：以f(x)为特征多项式的LFSR的输出序列是m序列的充要条件为f(x)是本原的。m序列的性质n级m序列的周期为2n－1，周期随n增加而指数级递增；只要知道n次本原多项式，m序列极易生成；m序列极不安全，只要泄露2n位连续数字，就可完全确定出反馈多项式系数。阶为2n-1的n次不可约多项式2023/10/24Page:23流密码：LFSR的周期m序列的破译已知ki,ki+1,…,ki+2n，由递推关系式可得出下式式中有n个线性方程和n个未知量，故可惟一解出ci，0

i

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

…ki…2023/10/24Page:26流密码：J-K触发器J-K触发器是一个非线性器件，有两个输入端j和k，输出为qi。输出不仅依赖于输入，还依赖于前一个输出位qi-1，即其结构及逻辑真值表如下所示JKqk00110101qk-101⊕⊕⊙JKR=qk-1qk2023/10/24Page:27流密码：J-K触发器的非线性序列生成器{ak}和{bk}被称为非线性序列生成器的驱动序列。性质：设{ak}和{bk}分别为x级和y级m序列。当x和y互素，且a0+b0=1时，序列{ck}的周期为(2x-1)(2y-1)。LFSR1LFSR2{ak}{bk}JK{ck}2023/10/24Page:28流密码：多路选择序列有n种输入序列b0(t),…,

bn-1(t)，在地址序列a1(t),…,am-1

(t)的控制下决定输出取自某个输入比特。——

Pless生成器例如取m级LFSR生成m序列作地址控制，取n级LFSR生成的m序列作为输入序列。可供选择的输入2023/10/24Page:29对称密码体制组成流密码分组密码数据加密标准(DES)高级加密标准(AES)2023/10/24Page:30对称密码体制：分组密码分组密码的工作原理将明文分成n个块，m1,m2,…,mn；对每个块执行相同的变换，从而生成n个密文块，c1,c2,…,cn。分组密码的工作模式：明文分组固定，消息的数据量不同，数据格式各式各样。为了适应各种应用环境，有四种工作模式。电子编码薄模式(EBC)密码分组链接模式(CBC)密码反馈模式(CFB)输出反馈模式(OFB)2023/10/24Page:31分组密码：分组密码的工作模式比较模式描述用途电码本模式(ECB)每个明文组独立地以同一密钥加密。传送短数据密码分组链接模式(CBC)加密算法的输入是当前明文组与前一密文组的异或。传送数据分组；认证。密码反馈模式(CFB)每次只处理输入的j比特，将上一次的密文用作加密算法的输入以产生伪随机输出，该输出再与当前明文异或以产生当前密文。传送数据流；认证。输出反馈模式(OFB)与CFB类似，不同之处是本次加密算法的输入为前一次加密算法的输出。有扰信道上(无线通讯)传送数据流2023/10/24Page:32分组密码：分组密码的经典工作模式电子编码薄模式密码分组链接模式输出反馈模式2023/10/24Page:33分组密码：分组密码的扩散与压缩分组密码的基本过程将明文分成m个块，M1,M2,…,Mm；对每个块执行相同的变换，从而生成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)

2023/10/24Page:34分组密码：分组密码的扩展与压缩将明文x和密文y表示成分别小于2m和2n的整数，并用分量形式描述。每个分量分别用xi，yi

GF(2)表示，即：若n>m，则为有数据扩展的分组密码；若n<m，则为有数据压缩的分组密码。分组密码就是将||x||映射为||y||，(||x||∈{0,1,…,2m-1},||y||∈{0,1,…,2n-1})即为到其自身的一个置换

，即

y=

(x)2023/10/24Page:35分组密码：分组密码的置换设明文分组长度为n比特，则明文分组的取值为2n。为了使加密运算可逆，每一个明文对应的密文唯一，这样的变换是可逆的，并称明文到密文的变换为置换。基本的置换左循环移位(Shiftleftcircular)代换、右循环移位(Shiftrightcircular)代换模2n加1(Additionwithmodule)代换线性变换(Lineartransformation)换位(Transposition)代换连线交叉或坐标置换仿射变换(Affinetransform)2023/10/24Page:36分组密码：Feistel网络Feistel网络将nbit明文分成为左右各半、长为n/2bit的段，以L和R表示。然后进行多轮迭代，其第i轮迭代的输出为前轮输出的函数

Li

=Ri-1

Ri

=Li-1

f(Ri-1,ki)

式中，ki是第i轮用的子密钥，f是任意密码轮函数。Feistel网络的特征保证加密和解密可采用同一算法实施。在设计整个分组密码的代换网络时，要求输出的每比特密文都和输入的明文及密钥各比特有关，这对增加密码强度有好处。2023/10/24Page:37分组密码：迭代分组密码迭代分组密码：若以一个简单函数f，进行多次迭代，就称其为迭代密码。每次迭代称作一轮(Round)，相应函数f称作轮函数。每一轮输出都是以前一轮输出作为输入参数的函数，即yi=f[yi-1,

ki]，其中ki是第i轮迭代用的子密钥，由秘密密钥k通过密钥生成算法产生。子密钥产生器fffy0=xy1yi-1y2yik1k2ki-1k2023/10/24Page:38分组密码：分组密码的填充问题问题的由来分组加密法是作用于有固定大小的明文/密文块。如果明文的大小不是块大小的整数倍怎样处理？？？分组密码的填充：添加足够多的特殊字符，使得明文长度是块大小的整数倍。

填充必须可逆一种可行的填充方法用文件结束字符表示明文分组的最后一个字节；每一个分组都必须以0、1或者0、1交替的模式填充，即使明文以分组的边界结束，也必须添加一个整分组。2023/10/24Page:39分组密码：分组密码的评估分组密码如何才算是安全？？密钥必须足够大，使强力攻击失效或者得不偿失—恺撒密码；如果加密法通过了随机测试，在一定时间内能给人以安全性。雪崩条件(avalanchecondition)：任何输入位或密钥位与输出位之间不应有任何连续，即密文中不能有内容含有关于密钥或明文的提示。精确密文雪崩标准：无论密文块的任意一位有变，密文块每个位发生改变的概率为50%；精确密钥雪崩标准：对于一个长度固定的明文块，当密钥的任意一位发生改变时，密文款每个位发生改变的概率为50%。2023/10/24Page:40对称密码体制组成流密码分组密码数据加密标准(DES)高级加密标准(AES)2023/10/24Page:41对称密码体制：数据加密标准( DES)的历史20世纪70年代中期，美国政府认为需要一个功能强大的标准加密系统，提出开发这种加密法的请求；1973年5月15日，国家标准局(NationalBureauofStandards,NBS)开始公开征集标准加密算法，并公布了它的设计要求 算法必须提供高度的安全性算法必须有详细的说明，并易于理解算法的安全性取决于密钥，不依赖于算法算法适用于所有用户算法适用于不同应用场合算法必须高效、经济算法必须能被证实有效算法必须是可出口的2023/10/24Page:42对称密码体制：数据加密标准( DES)的历史IBM提出的Lucifer加密系统在此次征集中获得了胜利；1977年，根据美国国家安全局的建议进行了一些修改后，Lucifer成为数据加密标准(dataencryptionstandard,DES)；1980年，DES成为美国标准化协会(ANSI)标准；1983年，国际化标准组织赞同DES作为国际标准，称之为DEA-1；1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作；DES最后被高级加密标准(advancedencryptionstandard,AES)代替。2023/10/24Page:43DES：数据加密标准(DES)的特征数据加密标准(DES)的特征分组加密算法：明文和密文为64位分组长度；对称算法：加密和解密除密钥编排不同外，使用同一算法；密钥长度：64位，但每个字节第8位为奇偶校验位，可忽略；密钥可为任意的56位数，但存在弱密钥，尽量避开；采用混乱和扩散的组合，每个组合先替代后置换，共16轮；只使用了标准的算术和逻辑运算，易于实现。2023/10/24Page:44DES：加/解密流程输入64比特明文数据初始置换IP在密钥控制下十六轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特2023/10/24Page:45DES：算法处理流程初始置换IP第1轮置换选择1循环左移置换选择2k1第2轮置换选择2循环左移k2第16轮k16置换选择2循环左移32位对换逆初始置换IP－164位密文48位64位明文64位密钥2023/10/24Page:46DES：初始置换IP和IP-1IP和IP-1在密码意义上作用不大，因为输入组x与其输出组y=IP(x)(或IP-1(x))是已知的一一对应关系。它们的作用在于打乱原来输入x的ASCII码字划分的关系，并将原来明文的校验位x8,x16,

,x64变成为IP输出的一个字节。IPIP—12023/10/24Page:47DES：乘积变换乘积变换是DES算法的核心部分将经过IP置换后的数据分成32bit的左右两组；每次迭代时只对右边的32bit进行一系列的加密变换，在此轮迭代即将结束时，把左边的32bit与右边得到的32bit逐位模2相加，作为下一轮迭代时右边的段；将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段；在每一轮迭代时，右边的段要经过选择扩展运算E、密钥加密运算、选择压缩运算S、置换运算P和左右混合运算。2023/10/24Page:48DES：乘积变换工作流程Li-1(32位)Ri-1(32位)扩展运算E(48位)模2求和(48位)密钥产生器压缩运算S(32位)置换运算P(32位)模2求和(32位)Li(32位)Ri(32位)2023/10/24Page:49DES：选择扩展运算选择扩展运算E：将输入的32bitRi-1扩展成48bit的输出令s表示E原输入数据比特的原下标，则E的输出是将原下标s

0或1(mod4)的各比特重复一次得到的，即对原第32,1,4,5,8,9,12,13,16,17,20,21,24,25,28,29各位都重复一次,实现数据扩展。扩展2023/10/24Page:50DES：加密运算和压缩运算密钥加密运算：将子密钥产生器输出的48bit子密钥ki与选择扩展运算E输出的48bits数据按位模2相加。选择压缩运算S：将前面送来的48bit数据自左至右分成8组，每组为6bit；而后并行送入8个S一盒，每个S盒为一非线性代换网络，有4个输出。48bit寄存器32bit寄存器S1S2S3S4S5S6S7S86位4位选择函数组2023/10/24Page:51DES：压缩运算-s盒s盒的工作原理基于s-表：以表S1为例子说明使用方法

01234567891011121314150

1441312151183106125907101574142131106121195382411481362111512973105031512824917511314100613S11

0110

0

1020010输入6位输出4位2023/10/24Page:52DES：置换和左右混合置换运算P：对S1至S8盒输出的32bit数据进行坐标置换。左右混合运算：置换P输出的32bit数据与左边32bit，即Ri-1，逐位模2相加，所得到的32bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。2023/10/24Page:53DES：子密钥产生器子密钥产生器：在64bit初始密钥中有8位为校验位，其位置号为8、16、32、48、56和64。其余56位为有效位，用于子密钥计算。置换选择PC1：将这56位送入置换选择PC1进行坐标置换；循环移位置换：将上述结果分成两组28bit，分别送入C和D寄存器中。在各次迭代中，C和D寄存器分别将存数进行左循环移位置换；置换选择PC2：每次移位后，将C和D寄存器原存数送给置换选择PC2。置换选择PC2将C中第9、18、22、25位和D中第7、9、15、26位删去，并将其余数字置换位置后送出48bit数字作为第i次迭代时所用的子密钥ki。2023/10/24Page:54DES：子密钥产生器2023/10/24Page:55DES：加/解密数学描述加密过程L0R0

IP(64bit明文)Li

Ri-1Ri

Li-1

f(Ri-1,

ki)i=1,...,16(64bit密文)

IP-1(R16L16)解密过程：DES的加密运算是可逆的，其解密过程可类似地进行。R16L16

IP(64bit密文)Ri-1

Li

Li-1

Ri

f(Li-1,ki)i=16,...,1(64bit明文)

IP-1(R0L0)2023/10/24Page:56DES：公开性和脆弱性DES的脆弱性DES的安全性完全依赖于所用的密钥，56位不太可能提供足够的安全性DES的半公开性S盒的设计原理至今未公布，可能隐含有陷井几种攻击的计算代价强力攻击：255次尝试差分密码分析法：247次尝试线性密码分析法：243次尝试2023/10/24Page:57DES：算法分析互补性：若明文组x逐位取补，密钥k逐位取补，且y=DESk(x)，则有，称这种特性为算法上的互补性。这种互补性会使DES在选择明文破译下所需的工作量减半。弱密钥：DES算法在每次迭代时都有一个子密钥供加密用。如果给定初始密钥k，各轮的子密钥都相同，即有k1=k2=…=k16，就称给定密钥k为弱密钥(Weakkey)。半弱密钥：两个不同密钥将同一明文加密成相同密文，一个用来加密，一个用来解密。2023/10/24Page:58DES：算法分析RSA数据安全公司提供10000美元奖金。现已被DESCHALL小组经过近四个月的努力，通过Internet搜索了3×1016个密钥，找出了DES的密钥，恢复出明文。1998年5月美国ElectronicFrontierFoundation)宣布，他们以一台价值20万美元的计算机改装成的专用解密机，用56小时破译了56bits密钥DES。1991年研究表明DES搜索机成本如下。资本成本时间成本$1万2.5天$10万6小时$100万35分钟$1000万3.5分钟2023/10/24Page:59对称密码体制：DES的差分密码分析差分攻击是一种选择明文攻击，对DES中的非线形的s-box的分析s-box输入为6bit，输出为4bit，设为s(x)；选择二进制数a,b和c都为6bit，d为4bit；a异或b＝c，则s(a)异或s(b)=d的概率远远大于1/16(抗差分攻击的分组密码此概率恒等1/2n，n为s-box输出位数)；由此性质可得部分密钥的信息，通过穷举就可以得出密钥。2023/10/24Page:60对称密码体制：分组密码的差分密码分析差分密码分析是一种攻击迭代分组密码的选择明文统计分析破译法，与一般统计分析法不同之处是，它不是直接分析密文或密钥的统计相关性，而是分析明文差分和密文差分之间的统计相关性。给定一个r轮迭代密码，对已知n长明文对X和X’，定义其差分为

X=X

(X’)-1，其中，

表示n-bits组X的集合中定义的群运算，(X’)-1为X’在群中的逆元。在密钥k作用下，各轮迭代所产生的中间密文差分为

Yi=Yi(Y’i)-10

i

r

2023/10/24Page:61对称密码体制：分组密码的差分密码分析i=0时，Y0=X，Y’0=X’，

Y0=

X。i=r时，

Y=

Yr，ki是第i轮加密的子密钥，Yi=f(Yi－1,ki)。由于X

X’，因此，

Yi

e(单位元)，即

Yi

F2n－{e}。每轮迭代所用子密钥ki与明文统计独立，且可认为服从均匀分布。

Y’0=X’Y’1

Y’2

Y’r－1

Y’r

Y0=X

Y1

Y2

Yr－1

Yr

f

f

…

fk(1)

k(2)

k(r)

f

f

…

f

X=

Y0

Y1

Y2

Yr－1

Y=

Yr2023/10/24Page:62对称密码体制：分组密码的差分密码分析输入一对X和X‘，则差分△X已知。同理，输出△Y已知；由于扩展置换E和P-盒已知，则△A和△C已知；虽然无法知道B和B’，但是△B=△A；对任意给定的△A，△C值不一定相同。将△A和△C联合起来，可以猜测的A异或ki及△A异或ki的位值，应为A和△A已知，故可推测ki的信息。XE△XE(X)ki⊕△AS-盒PY△B△C△Y2023/10/24Page:63对称密码体制：分组密码的差分密码分析差分密码分析的r-轮特征明文对Y0和Y0’的差分序列a0,…,ar(其中ai是第i轮输出Yi和Yi’的差分)r-轮特征a0,…,ar条件下，轮函数输出特定差分的概率pi=P(△F(Y)=ai|△Y=ai-1)

即为输入差分为ai-1的条件下，轮函数F的输出差分为ai的概率。r-轮特征的概率r-轮特征a0,…,ar条件下，r-轮特征的概率为p=p0

×

p1

×…×

pr2023/10/24Page:64对称密码体制：分组密码的差分密码分析差分密码分析步骤找出一个(r-1)-轮特征，使它的概率达到最大；均匀选择Y0并计算Y0’，使得Y0和Y0’的差分为a0，找出在实际密钥加密下所得到的密文Yr和Yr’。若最后一轮的子密钥kr有2m个可能krm，则设置2m个计数器；用每个子密钥解密Yr和Yr’，得到Yr-1和Yr-1’，如果差分是ar-1，则对应计数器加一；