现代密码学03---对称密码

现代密码学林喜军中国海洋大学信息安全实验室对称密码学第3章23欢迎进入“现代密码学”的世界！本章内容43.1对称密码学概述3.2流密码3.3分组密码3.4分组密码的工作模式3.5对称密钥管理3.1对称密码学概述56密码体制的分类以加密为例密码体制对称密码非对称密码(公钥密码)流密码(序列密码)分组密码加解密使用相同的密钥加解密使用不同的密钥7随机性•一个故事在一次国际会议上，一个教授在黑板上写了一串数字，让大家看看，这串数字是否是随机的……8随机性½的重要性•假设你想做一个发布天气预报的网站，发布的信息是“下雨”或“不下雨”(注意，只有两种情况)你没有预测设备，但有一个气象台也发布同样的信息，你希望借助气象台来发布自己的信息。9•你具体应该怎么操作？下面分3种情况讨论：①如果气象台的预测挺准，预测正确的概率是0.9，你应该怎么办？•气象台说“下雨”，你就说“下雨”；气象台说“不下雨”，你就说“不下雨”•你预测正确的概率也将高达0.9②如果气象台的预测挺不准，预测正确的概率只有0.1，你应该怎么办？•气象台说“下雨”，你就说“不下雨”；气象台说“不下雨”，你就说“下雨”•你预测正确的概率同样可以高达0.910③如果气象台预测的正确概率是0.5，你应该怎么办？•气象台发布的信息对你已经毫无用处•你自己在家抛硬币，正确概率也是0.5•结论只要气象台提供信息的准确概率偏离½，就是有用的。恰是½的话，就毫无用处。这个特性在密码学上具有重要意义。11随机性随机性的概率论解释Q:如何产生单个随机数？产生每个数的概率都是1/n(等概率)Q:如何产生一串随机数？1.等概率产生每个数2.这些数在统计上相互独立Q:如何产生随机序列(随机比特串)？1.每个比特产生概率都是1/22.每个比特与其他比特统计上相互独立12一个哲学问题•哲学家们经常问这样的问题：•是否存在真正的随机性？•怎么知道一串序列是否是真随机的？•“101110100”比“101010101”更随机吗？是否存在真正的随机性，这是一个哲学问题量子力学告诉我们：现实世界中存在真随机性13计算机不能产生真正的随机数•对于相同的输入，在相同计算环境下，计算机只能产生相同的输出•计算机产生的一系列所谓的随机数是周期性的(周期可以很大)•任何周期性的东西都是可预测的，可预测的就不是真随机的•要想产生真正的随机数，需要随机的输入，但计算机本身无法提供随机输入14任何人考虑用数学的方法产生随机数肯定是不合理的JohnvonNeumann1903~195715计算机本身只能产生伪随机序列16随机序列的类型1.(一般)伪随机序列2.密码学意义上安全的伪随机序列3.真随机序列17随机序列的类型(一般)伪随机序列①1和0的数目应该大约相等②一些0和1组成的模式出现的不要“太频繁”，也不要“太不频繁”？……这表明它通过了所谓的随机性统计测试：性质1：伪随机序列应满足的性质：看上去是随机的结论：伪随机序列应该在统计上是随机的18随机序列的类型密码学意义上安全的伪随机序列即使知道了产生序列的算法、以前产生的所有比特，也不可能通过计算来预测下一个比特是什么（准确预测成功的概率很低）目的是防止攻击者在知道若干比特后，成功猜测后续比特什么叫不可预测性：性质2：并不是任何伪随机序列都能用于密码学，密码学意义上安全的伪随机序列还必须具备另一个性质：不可预测性19随机序列的类型真随机序列用完全同样的输入操作两次，得到的是两个不相关的序列什么叫不能被可靠地重复产生：性质3：如果一个序列具有下面的第3条性质，它就是真随机序列：不能被可靠地重复产生20随机序列的类型真随机序列Q:如何得到真随机序列？使用一种专门的设备(真随机数发生器)，输入是各种无法预测的信号：周围空气状况、电流的变化率…•输入是不断变化的，输出也就不可重复。•有人能预测产生的下一个数吗？他必须重构输入信号，这没人能做到21一次一密•加解密很简单•加密：明文流与密钥流对应比特异或•解密：密文流与密钥流对应比特异或1001010101101…1111010110101…0110000011000…密钥流明文流密文流22一次一密密钥流是真随机序列，且不重复使用(故得名一次一密)特点因为密钥流是真随机的，所以没人能预测下一个比特安全性23一次一密即使攻击者具有无限的计算资源和计算能力，也无法破译一次一密(理论上不可破译，无条件安全的)目前唯一得到证明的无条件安全的密码体制密钥是随机的，而且明文与密钥是统计上相互独立的，使得密文也是随机的，故而密钥的随机性很好的隐藏了明文的统计特性。原因24一次一密•为什么一次一密很好的隐藏明文的统计特性•密钥流是随机的，则每个密钥比特的概率满足：Pr[k=0]=1/2,Pr[k=1]=1/2•假设明文流某个比特的概率满足：Pr[m=0]=p,Pr[m=1]=1-p•对应的密文比特的概率：Pr[c=0]=?=Pr[k=0]*Pr[m=0]+Pr[k=1]*Pr[m=1]=1/2Pr[c=1]=?=Pr[k=0]*Pr[m=1]+Pr[k=1]*Pr[m=0]=1/2•因此，密文流一定是随机的25一次一密无条件安全（完善保密性）对于任意密文y和明文x，都有Pr[x|y]=Pr[x]即，不能通过分析密文获得明文的任何信息什么是无条件安全已知明文攻击若攻击者获得了一个密文c=(c1c2…)和对应明文m=(m1m2…)时，就很容易得出密钥k=(k1k2…)。若重复使用该密钥，一次一密就很不安全。如果重复使用同一个密钥加密不同的明文，很容易被破译26一次一密一次一密的缺点1.密钥是真随机的2.密钥长度至少等于明文长度；3.每个密钥只用一次。分发/存储这样的密钥序列，并确保其安全是很因难的；如何获得真随机序列也是一个现实的问题实用性不强的原因只使用异或运算，软硬件实现非常简单。但实用性不强限制了它在商业上的应用，在需要无条件安全的军事或政府领域仍有应用3.2流密码2728Q:一次一密不太实用，那能否找到一种方法，既降低密钥管理的难度，又达到所需的安全性？29流密码用一个较短的密钥生成密钥流，在攻击者(计算能力是有限的)看来是随机的(伪随机的)。不是无条件安全的，仅是计算上安全的流密码的基本思想输入：“较短的密钥”输出：源源不断的密钥流产生密钥流的任务由密钥流生成器完成30流密码密钥流生成器密钥密码学意义上安全的伪随机序列1001010101101…1111010110101…0110000011000…密钥流明文流密文流31流密码原理图信道ciDki(ci)cimiEki(mi)mi密钥流生成器kiki密钥流生成器kk安全信道通常，加解密使用“异或”运算设计流密码的关键：如何生成伪随机性“好”的密钥流，故而关键在于密钥流生成器的设计32流密码流密码的分类同步流密码密钥流只根据密钥产生与明文流无关自同步流密码密钥流不仅与密钥有关还与明文流有关33流密码分类同步流密码•特点：①密钥流只根据密钥产生，与明文流无关②双方的密钥流生成器具有相同密钥、相同初始状态，就能产生相同密钥流。③双方必须保持精确同步，才能正确解密。④没有差错传播。34流密码分类自同步流密码密钥流生成器。。。k()kiEmmici•特点：①密钥流不仅与密钥有关，还与明文流有关②把明文的每个比特扩散在密文的多个比特中,强化了抗统计分析的能力③具有有限的差错传播，具有自同步能力35流密码理论简介两个基本概念：游程、自相关函数•游程•若存在一段序列•两端为0中间连续k个1，称长为k的“1游程”。•两端为1中间连续k个0，称长为k的“0游程”。0110是长为2的“1游程”1000001是长为5的“0游程”101是长为1的“0游程”36流密码理论简介两个基本概念：游程、自相关函数•自相关函数•设a=a1a2a3…是周期为p的比特序列，则称函数为周期序列a的自相关函数。0,()1aaR0时，时，称为异相自相关函数,()aaR称为同相自相关函数,11()(1)iipaaaaiRp0101101101011101110000110011001010101101010110110101110111000011001100101010110137流密码理论简介两个基本概念：游程、自相关函数3时，自相关函数演示,11()(1)iipaaaaiRp…序列自身平移后，对应位异或38G1说明：序列中0、1出现的概率基本相同G2说明：0、1在每一位置上出现的概率基本相同G3说明：通过平移序列不能给出任何其它信息流密码理论简介哥伦布(Golomb)三假设：伪随机序列应满足的特性(G1)：在一个周期内，0与1出现的个数至多相差1。(G2)：在一个周期内，长度为i的游程个数占游程总数的1/2i，i=1,2,…。且在长度为i的游程中，“0游程”与“1游程”数目至多相差一个。(G3)：异相自相关函数是一个常数。39流密码理论简介•满足哥伦布三假设的序列就是“看上去随机”的序列•但密码学上使用的伪随机序列，除满足G1,G2,G3外，还应满足以下三个性质：(C1)周期p要长.如p1050.(C2)生成容易.(C3)具有不可预测性:当序列的任何部分泄露时,要分析整个序列,在计算上是不可行的.•C3决定了密码的强度,是流密码理论的核心•主要研究问题:线性复杂度、相关免疫性、不可预测性等.40密码流生成器的内部构造•通常所说的设计流密码，实际就是设计密钥流生成器•若密钥流是真随机的(一定是非周期的)，流密码体制实际上是一次一密体制，但这需要无限的存储单元。•实际中，多采用有限的存储单元和确定性算法来实现。41•密钥流生成器的组成①驱动部分为非线性组合部分提供统计特性“好”的序列(一般伪随机序列)②非线性组合部分将提供的输入序列组合成密码学特性“好”的序列(密码学意义上安全的伪随机序列)42密码流生成器的内部构造密钥流生成器驱动部分应该实现简单，且提供统计特性较好的序列。反馈移位寄存器(FSR)可以满足该要求，是流密码设计中的常用模块43密码流生成器的内部构造反馈移位寄存器(FSR)常见的两种密钥流生成器44密码流生成器的内部构造反馈移位寄存器(FSR)12rf3①移位寄存器②反馈函数45密码流生成器的内部构造反馈移位寄存器(FSR)•以密钥为初始状态（输入）•按照确定的递推关系（由反馈函数决定）•产生一个周期长、线性复杂度高、统计特性好的初始序列•并将输出提供给非线性组合等密码变换，以产生抗密码分析能力强的伪随机序列FSR的功能46密码流生成器的内部构造反馈移位寄存器(FSR)•若反馈函数是线性的，则称为线性反馈移位寄存器(LFSR)，否则称为非线性反馈移位寄存器(NFSR)42134级LFSR1212(,)fxxxx反馈函数3213级NFSR1313(,)fxxxx反馈函数47密码流生成器的内部构造反馈移位寄存器(FSR)•功能完全由反馈函数f决定•在每个时刻，各级都有一个值，称为内部状态•在时钟脉冲控制下，各级的值各向前移动一级(进入新的内部状态)•最前面一级作为输出，最后一级的值由f的输出填充FSR的工作原理48密码流生成器的内部构造反馈移位寄存器(FSR)a3a1a20010100111001110011110110101001初始状态：密钥49密码流生成器的内部构造布尔函数简介•反馈函数f是一个含有n个变量的布尔函数，通常表示为：xn+1=f(x1,x2,…,xn)一般地，定义n元布尔函数为映射：f(x1,x2,…,xn)记为f:{0,1}n→{0,1}50密码流生成器的内部构造布尔函数的两种表示方法x1x2f0000111011101212(,)fxxxx真值表多项式51密码流生成器的用途•用途很广：①流密码（用于加密）②生成随机序列/随机数③生成密钥（本质上也是一个随机数）…•当它用于生成随机序列时，又称作伪随机序列发生器•此时，密钥便称作种子52Q:为什么不直接使用种子作随机数?1.速度问题：收集种子通常很耗时2.熵(不确定性)：种子的熵通常比