对称密码体制

[e-mail]2020/4/6Page:1对称密码体制杨秋伟湖南大学计算机与通信学院[e-mail]2020/4/6Page:2对称密码体制对称密码体制的特征加密密钥和解密密钥相同对称密码体制的主要研究课题密钥的产生密钥的管理加密器EK解密器DK密文明文明文K密钥产生器[e-mail]2020/4/6Page:3对称密码体制组成流密码分组密码数据加密标准(DES)高级加密标准(AES)[e-mail]2020/4/6Page:4流密码：流密码引论流密码是将明文划分成字符(如单个字母)，或其编码的基本单元(如按位)，字符分别与密钥流作用进行加密，解密时以同步产生的同样的密钥流实现。流密码强度完全依赖于密钥序列的随机性(Randomness)和不可预测性(Unpredictability)。核心问题是密钥流的产生——密钥流生成器的设计保持收发两端密钥流的精确同步是实现可靠解密的关键技术[e-mail]2020/4/6Page: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)[e-mail]2020/4/6Page:6流密码：同步流密码同步流密码：加密器中记忆元件的存储状态δi独立于明文字符。同步流密码加密器密钥流产生器加密变换器加密变换器一般采用二元逻辑运算XOR，即有限域GF(2)上讨论的二元加密流密码，变换表示为：yi=zi⊕xi一次一密乱码本是加法流密码的原型[e-mail]2020/4/6Page:7流密码：流密码的密钥流产生器密钥流产生器的内涵输入：密钥k和加密器中的记忆元件在时刻i的状态δi；输出：密钥流zi状态δi密钥k状态δi+1密钥流[e-mail]2020/4/6Page:8流密码：密钥流生成器的设计原则足够长的周期高线性复杂度统计性能良好足够的“混乱”强调密钥的作用，增加密钥与密文之间关系的复杂性足够的“扩散”小扰动的影响波及到全局密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性抵抗不同形式的攻击[e-mail]2020/4/6Page: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。[e-mail]2020/4/6Page:10流密码：有限状态自动机举例例一S={s1,s2,s3},X={x1,x2,x3},Y={y1,y2,y3}转移函数f1x1x2x3s1s[e-mail]2020/4/6Page:11流密码：有限状态自动机举例若输入为x1x2x1x3x3x1初始状态s1输出为[e-mail]2020/4/6Page:12流密码：基于FA的密钥流产生器同步流密码的密钥流产生器可看为一个参数为k的FA：输出集Z，状态集Σ，状态转移函数φ和输出函数ψ，初态0设计的关键是φ(phifai)和ψ(psipsai)φiψ[e-mail]2020/4/6Page:13流密码：基于FA的密钥流产生器一个良好的密钥流产生器极大的周期良好的统计特性抗线性分析抗统计分析具有非线性的φ的FA理论很不完善，通常采用线性φ以及非线性的ψ。可将此类产生器分为驱动部分和非线性组合部分。驱动部分控制状态转移非线性组合部分提供统计特性良好的序列[e-mail]2020/4/6Page:14流密码：两种常见的密钥流产生器LFSR非线性组合函数ziLFSR1LFSR2LFSR3非线性组合函数ziLFSR：线性反馈移位寄存器——流密码产生密钥流的主要组成部分。[e-mail]2020/4/6Page:15流密码：反馈移位寄存器的概念基本概念级数(Stages)：存储单元数n状态(State)：n个存储单元的存数(ki,…,ki+n-1)反馈函数：f(ki,ki+1,…,ki+n-1)是状态(ki,…,ki+n-1)的函数线性反馈移位寄存器(LFSR)：f为线性函数非线性反馈移位寄存器：f为非线性函数[e-mail]2020/4/6Page:16流密码：反馈移位寄存器f(ki,ki+1,…,ki+n-1)ki+n-1ki+n-2ki+1kiki+n输出序列寄存移位反馈[e-mail]2020/4/6Page:17流密码：线性反馈移位寄存器f(x)为线性函数，输出序列满足下式1011(,,)002iniinininikfkkckckic，其中：，或1，是模加法。ki+n-1ki+n-2ki+1kicn-1cn-2c1c0ki+n输出序列[e-mail]2020/4/6Page:18流密码：LFSR的特征多项式LFSR的特征多项式：以LFSR的反馈系数所决定的一元高次多项式又称反馈多项式。由于ciGF(2)(i=1,2,…,n)，所以有2n组初始状态，即有2n个递推序列，其中非恒零的有2n-1个。211210()1...nnnjnnjjfxcxcxcxcxcx[e-mail]2020/4/6Page:19流密码：LFSR的生成函数给定序列{ki}i0，幂级数称为该序列的生成函数定理：令{ki}i0(f)，f(x)是反馈多项式，令k(x)是{ki}i0的生成函数，则其中11()iiikxkx()()()axkxfx111()()jnnjlnjljlaxcxax[e-mail]2020/4/6Page:20流密码：LFSR的生成函数定理证明,00min()001000()0()()()()(())()()()()nilililjnjnljljljnnjjnljlnljljljnlnjtjntjnjkxfxkxcxckxckxckxaxckxnltax[e-mail]2020/4/6Page: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。[e-mail]2020/4/6Page: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次不可约多项式[e-mail]2020/4/6Page:23流密码：LFSR的周期m序列的破译已知ki,ki+1,…,ki+2n，由递推关系式可得出下式式中有n个线性方程和n个未知量，故可惟一解出ci，0in-1。121110212111...................[e-mail]2020/4/6Page:24流密码：非线性序列LFSR虽然不能直接作为密钥流用，但可作为驱动源以其输出推动一个非线性组合函数所决定的电路来产生非线性序列。这就是所谓非线性前馈序列生成器。LFSR用来保证密钥流的周期长度、平衡性等；非线性组合函数用来保证密钥流的各种密码性质，以抗击各种可能的攻击。[e-mail]2020/4/6Page:25流密码：非线性前馈序列前馈函数F(非线性组合函数)输出序列的周期性、随机性、线性复杂度以及相关免疫性之间的关系LFRSF…ki…[e-mail]2020/4/6Page:26流密码：J-K触发器J-K触发器是一个非线性器件，有两个输入端j和k，输出为qi。输出不仅依赖于输入，还依赖于前一个输出位qi-1，即其结构及逻辑真值表如下所示121112(),,iiqxxqxxxJK其中分别为和的输入。JKqk00110101qk-1011kq⊕⊕⊙JKR=[e-mail]2020/4/6Page: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}[e-mail]2020/4/6Page:28流密码：多路选择序列有n种输入序列b0(t),…,bn-1(t)，在地址序列a1(t),…,am-1(t)的控制下决定输出取自某个输入比特。——Pless生成器例如取m级LFSR生成m序列作地址控制，取n级LFSR生成的m序列作为输入序列。)()()(110tbtbtbn)()()(110tatatam制控址地可供选择的输入[e-mail]2020/4/6Page:29对称密码体制组成流密码分组密码数据加密标准(DES)高级加密标准(AES)[e-mail]2020/4/6Page:30对称密码体制：分组密码分组密码的工作原理将明文分成n个块，m1,m2,…,mn；对每个块执行相同的变换，从而生成n个密文块，c1,c2,…,cn。分组密码的工作模式：明文分组固定，消息的数据量不同，数据格式各式各样。为了适应各种应用环境，有四种工作模式。电子编码薄模式(EBC)密码分组链接模式(CBC)密码反馈模式(CFB)输出反馈模式(OFB)[e-mail]2020/4/6Page:31分组密码：分组密码的工作模式比较模式描述用途电码本模式(ECB)每个明文组独立地以同一密钥加密。传送短数据密码分组链接模式(CBC)加密算法的输入是当