5密码学-单钥.

第2讲密码学-对称密码体制张伟南京邮电大学计算机学院信息安全系[e-mail]189051800102020/1/122本讲内容对称密码体系的原理1Fiestel结构2DES3IDEA与AES42020/1/1231.对称密码原理对称密码技术也叫做单钥或传统密码技术特点：加密和解密时所用的密钥是相同的或者类似的，即由加密密钥可以很容易推导出解密密钥分组密码技术流密码技术在公钥密码技术出现之前，它是唯一的加密类型。2020/1/124传统密码体制明文密钥k密钥k明文密文加密器Ek解密器Dk安全信道2020/1/125公开密码体制明文私钥d公钥e明文密文加密器Ek解密器Dk2020/1/126分组密码类似“电码本密码”将明文编码后的数字序列划分成长为m的明文组各明文组在长为i的密钥组的控制下变换成长为n的密文组通常取n＝mnm扩展分组密码nm压缩分组密码典型分析密码结构-Feistel美国商用数据加密标准DES（DataEncryptionStandard）2020/1/127置换分组加密算法，一种置换置换p是S到自身S的双射。双射：一一映射并且映上p：S---SS={1,2,3,4,5}p(1)=3p(2)=5p(3)=4p(4)=2p(5)=1{12345}35421P=P-1={12345}541322020/1/128对合对合的自身到自身的双射，特点的是其逆为自身。f-1=ff(f(x))=x1231234SS4551231234SS4552020/1/129函数的复合函数f和g的复合g.fft的定义域是ft-1的值域abc1234STstuvUfgabcSstuvUg.f2020/1/1210复合和对合1两个对合的复合未必是对合2对合的复合得到更复杂的函数3对合的复合求逆容易EK=E1E2E3…EpEk-1=Ep….E3E2E1Ei为对合1234f12341234g12341234g.f12342020/1/1211乘积密码替代和移位单独使用不提供高等级的安全性替代和移位组合使用强密码复合Ek1Ek2Ek3….EktEki0=i=t为替代或者为移位密码一轮的概念2020/1/1212乘积密码EK1(m)=mk密码替代E2(m)=(m4m5m6m1m2m3)移位替代称为为加密过程加入混淆移位称为加入发散⊕2020/1/1213混淆和发散Confusion(混淆)强调密钥的作用增加密钥与密文之间关系的复杂性Diffusion(发散)小扰动的影响波及到全局密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性结构简单、易于分析2020/1/1214密码空间密钥的个数密钥的长度abc123abc123abc123ABCabc123abc123abc123DEF2020/1/1215密钥空间00011011000110111110010010010011密钥个数=转换可能=（22）！=24密钥空间2×（22）64bit单个密钥空间64×264=270～102164bit密钥个数（264）！2020/1/1216本讲内容对称密码体系的原理1Fiestel结构2DES3IDEA与AES42020/1/1217Feistel分组加密算法结构之动机分组加密算法，一一映射，一种置换当n较小时，等价于替换变换当n较大时，无法表达这样的任意变换。Feistel结构很好地解决了二者之间的矛盾如何计算密钥空间？密钥数2n如何计算密钥的长度？n×2n128bit2128＝3.4×10382020/1/1218Feistel分组加密算法结构之思想基本思想：基于“扩散”和“混淆”的思考，Feistel想出了替换和置换交替的方式构造密码，用简单算法的乘积来近似表达大尺寸的替换变换Feistel是一种设计原则，并非一个特殊的密码多个简单算法的结合得到的加密算法比任何一个部分算法都要强交替使用替换(substitution)变换和排列(permutation)混淆(confusion)和发散(diffusion)概念的应用2020/1/1219Feistel结构图2020/1/1220Feistel结构定义加密:Li=Ri-1Ri=Li-1F(Ri-1,Ki)i=1,2,…,n解密:Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)i=n,n-1,…,12020/1/1221Feistel分组加密算法解密算法2020/1/12232.典型分析密码结构-Feistel加密将明文分成左、右两部分:明文=(L0,R0)在每一轮i=1,2,...,n,计算Li=Ri1Ri=Li1F(Ri1,Ki)其中F是轮函数，Ki是子密钥密文=(Ln,Rn)2020/1/1224Feistel解密解密密文=(Ln,Rn)每一轮i=n,n1,…,1,计算Ri1=LiLi1=RiF(Ri1,Ki)其中F是轮函数，Ki是子密钥明文=(L0,R0)2020/1/1225Feistel分组加密算法之解密算法推导2020/1/1226Feistel分组加密算法特点1.分组大小，越大安全性越高，但速度下降，64比较合理2.密钥位数，越大安全性越高，但速度下降，64广泛使用，但现在已经不够用—〉1283.迭代轮数，典型16轮4.子钥产生算法，算法越复杂，就增加密码分析的难度5.每一轮的子函数，函数越复杂，就增加密码分析的难度6.快速软件实现，包括加密和解密算法7.易于分析，便于掌握算法的保密强度以及扩展办法。2020/1/1227本讲内容对称密码体系的原理1Fiestel结构2DES3IDEA与AES42020/1/1228DES算法1977年由美国标准化局(NBS，现为NIST)采纳历史：IBM在60年代启动了LUCIFER项目，当时的算法采用128位密钥改进算法，降低为56位密钥，IBM提交给NBS(NIST)，于是产生DES2020/1/12293.DESDES是16轮的Feistel结构密码DES的分组长度是64位DES使用56位的密钥DES的每一轮使用48位的子密钥每个子密钥是56位密钥的子集构成2020/1/1230DES算法基本结构2020/1/1231DES的3个基本函数初始换位（IP：InitialPermutation）把输入的64位数据的排列顺序打乱，每位数据按照下面规则重新组合58,50,12,34,26,18,10,2,60,52,44,36,28,20,12,4,62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,72020/1/1232加密算法的3个基本函数逆初始置换函数IP-1将L16与R16作为输入，进行逆初始换位得到密文输出IP-1是初始置换函数的逆运算2020/1/1233DES:每一轮F函数Li=Ri-1Ri=Li-1F(Ri-1,Ki)2020/1/1234LRexpandshiftshiftkeykeyS-boxescompressLR28282828282848324832323232DES的一轮4832KiPbox2020/1/1235DES:FunctionFExpansion:3248S-box:64Permutation2020/1/1236DES:32位到48位的扩展表32|01020304|0504|05060708|0908|09101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|012020/1/1237DES:S-boxS(1):140413010215110803100612050900070015070414021301100612110905030804011408130602111512090703100500151208020409010705110314100006132020/1/1238S盒转换B＝b1b2b3b4b5b66bit4bitb1b6对应S盒的行号0－3b2b3b4b5对应S盒的列号0－15对应于S0输入101010第2行第5列S0（2，5）＝6输出01102020/1/1239abcdefghijklmnop扩展为pabcdedefghihijklmlmnopa2020/1/1240DES之每步密钥产生过程PC-1在第一步之前PC2左移位数目表1(12916)2位(其他)2020/1/124116072021291228170115232605183110020824143227030919133006221104252020/1/1242DES的强度56位密钥的使用理论上的强度，97年$100000的机器可以在6小时内用穷举法攻破DES实际攻破的例子，97年1月提出挑战，有人利用Internet的分布式计算能力，组织志愿军连接了70000多个系统在96天后攻破DES算法的本质关键在于8个S-BOX针对DES的密码分析差分分析法线性分析法2020/1/1243差分分析法属于选择明文攻击基本思想：通过分析特定明文差对结果密文差的影响来获得可能性最大的密钥差分在DES的16步加密过程中的传递，每一个S-BOX对于差分传递的概率特性子密钥不影响每一步的输入差分，但是影响输出的差分针对每一个DES步骤，用差分法可以推导出该步的密钥2020/1/1244KM⊕M’=△MM⊕K=BM’⊕K=B’△B=B⊕B’=M⊕K⊕M’⊕K=△M2020/1/1245每一步的差分分析法2020/1/1246针对DES的密码分析差分分析法247对选择明文，经过247量级的计算可攻破线性分析法思想：用线性近似描述DES变换C=P⊕kP=C⊕K根据247已知明文，可以找到DES的密钥2020/1/1247二重DES1.C=EK2(EK1(P))P=DK1(DK2(C))2.EK2(EK1(P))＝EK3(P)？3.DES是群？(264)!1010202561017置换集合在复合下是不闭合的2020/1/1248针对两重分组加密算法的中间相会攻击2020/1/1249三重DES三重DES是人们在发现DES密钥过短，易于受到蛮力攻击而提出的一种替代加密算法。三重DES使用3个密钥，执行3次DES算法。加密过程为加密-解密-加密（EDE），可表示为如下的公式：C=EK3(DK2(EK1(M)))2020/1/1250三重DES1.C=EK3(DK2(EK1(P)))P=DK1(EK2(DK3(C)))2020/1/1251为了避免三重DES使用3个密钥进行三阶段加密带来的密钥过长的缺点（168bit），Tuchman提出使用两个密钥的三重加密方法，这个方法只要求112bit密钥，即令其K1=K3：C=EK1(DK2(EK1(M)))三重DES的第二阶段的解密并没有密码编码学上的意义。它的唯一优点是可以使用三重DES解密原来的单次DES加密的数据，即K1=K2=K3。C=EK1(DK1(EK1(M)))=EK1(M)三重DES的特点2020/1/1252DES算法分析1.DES算法最大弱点是密钥长度太短2.虽然可以通过3DES算法可以将密钥扩展到112比特(当K1=K3)或者168比特长度，但是，由于需要执行三次DES算法，其加密效率较低，无法满足NIST关于加密算法高效性的要求。3.DES算法的另外一个缺陷是在软件中运行的效率较低。4