密码学基础课件北大.ppt

密码学基础课件北大 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望内容内容u对称加密算法对称加密算法经典密码算法经典密码算法现代密码算法现代密码算法AESu随机数发生器随机数发生器对称加密算法的基本模型对称加密算法的基本模型u加密加密:E:(X,K)Y,y=E(x,k)XYKEYXKDu解密解密:D:(Y,K)X,x=D(y,k)对称加密算法研究对称加密算法研究u对称加密算法的特点对称加密算法的特点算法强度足够算法强度足够安全性依赖于密钥，不是算法安全性依赖于密钥，不是算法速度快速度快u两门学科两门学科密码学密码学密码分析密码分析用对称加密算法建立起来的安全通讯用对称加密算法建立起来的安全通讯密码学密码学u三种考虑角度三种考虑角度（1）从明文到密文的变换）从明文到密文的变换替换替换(substitution)置换置换(transposition)（2）钥匙的数目钥匙的数目对称、单钥加密法对称、单钥加密法双钥、公钥加密双钥、公钥加密（3）明文的处理方式）明文的处理方式分组加密（块加密算法）分组加密（块加密算法）流方式加密流方式加密密码分析密码分析u发现发现X和和K的过程被称为密码分析的过程被称为密码分析分析的策略取决于加密的技术以及可利用的分析的策略取决于加密的技术以及可利用的信息，在加密算法设计和攻击时都需要用到信息，在加密算法设计和攻击时都需要用到的技术的技术u根据可利用信息的不同，可分为根据可利用信息的不同，可分为5类：类：（1）只有密文）只有密文（2）已知部分明文）已知部分明文-密文对密文对（3）选择明文）选择明文（4）选择密文）选择密文*（1）（）（2）（）（3）常见、（）常见、（4）不常见）不常见加密算法的有效性加密算法的有效性uUnconditionally secure，绝对安全？绝对安全？永不可破，是理想情况，理论上不可破，密永不可破，是理想情况，理论上不可破，密钥空间无限，在已知密文条件下，方程无解。钥空间无限，在已知密文条件下，方程无解。但是我们可以考虑：但是我们可以考虑：破解的代价超过了加密信息本身的价值破解的代价超过了加密信息本身的价值破解的时间超过了加密信息本身的有效期破解的时间超过了加密信息本身的有效期uComputationally secure，满足上述两个条件满足上述两个条件直觉：什么是一个好的加密算法直觉：什么是一个好的加密算法u假设密码假设密码(password)k是固定的是固定的u明文和密文是一个映射关系：单射，即明文和密文是一个映射关系：单射，即 Ek(x1)!=Ek(x2)if x1!=x2u通常情况是：明文非常有序通常情况是：明文非常有序u好的密码条件下，我们期望得到什么样的好的密码条件下，我们期望得到什么样的密文密文随机性随机性u如何理解随机性如何理解随机性静态：特殊的点静态：特殊的点动态：小的扰动带来的变化不可知动态：小的扰动带来的变化不可知考虑设计一个加密算法考虑设计一个加密算法u打破明文本身的规律性打破明文本身的规律性随机性随机性(可望不可及可望不可及)非线性非线性(一定要一定要)统计意义上的规律统计意义上的规律u多次迭代多次迭代迭代是否会增加变换的复杂性迭代是否会增加变换的复杂性是否存在通用的框架，用于迭代是否存在通用的框架，用于迭代u复杂性带来密码分析的困难和不可知性复杂性带来密码分析的困难和不可知性实践的检验和考验实践的检验和考验已有密码算法的讨论已有密码算法的讨论u经典密码算法经典密码算法替换技术替换技术置换技术置换技术u现代密码算法现代密码算法DES其他密码算法其他密码算法uAES密码算法密码算法Rijndael经典密码算法经典密码算法u替换技术替换技术Caesar加密制加密制单表替换加密制单表替换加密制Playfair加密制加密制Hill加密制加密制多表加密制多表加密制u置换技术置换技术改变字母的排列顺序，比如改变字母的排列顺序，比如用对角线方式写明文，然后按行重新排序用对角线方式写明文，然后按行重新排序写成一个矩阵，然后按照新的列序重新排列写成一个矩阵，然后按照新的列序重新排列u转轮加密体制转轮加密体制u多步结合多步结合经典密码算法特点经典密码算法特点u要求的计算强度小要求的计算强度小uDES之前之前u以字母表为主要加密对象以字母表为主要加密对象u替换和置换技术替换和置换技术u数据安全基于算法的保密数据安全基于算法的保密u密码分析方法基于明文的可读性以及字母密码分析方法基于明文的可读性以及字母和字母组合的频率特性和字母组合的频率特性现代密码算法现代密码算法uDES(Data Encryption Standard)uIDEAuBlowfishuRC5uCAST-128u分组密码算法设计指导原则分组密码算法设计指导原则uDiffusion(发散发散)小扰动的影响波及到全局小扰动的影响波及到全局密文没有统计特征，明文一位影响密文的多密文没有统计特征，明文一位影响密文的多位，增加密文与明文之间关系的复杂性位，增加密文与明文之间关系的复杂性uConfusion(混淆混淆)强调密钥的作用强调密钥的作用增加密钥与密文之间关系的复杂性增加密钥与密文之间关系的复杂性u结构简单、易于分析结构简单、易于分析Feistel分组加密算法结构之动机分组加密算法结构之动机u分组加密算法，一一映射分组加密算法，一一映射u当当n较小时，等价于替换变换较小时，等价于替换变换u当当n较大时，比如较大时，比如n=64，无法表达这样的，无法表达这样的任意变换。任意变换。uFeistel结构很好地解决了二者之间的矛盾结构很好地解决了二者之间的矛盾Feistel分组加密算法结构之思想分组加密算法结构之思想u基本思想：用简单算法的乘积来近似表达基本思想：用简单算法的乘积来近似表达大尺寸的替换变换大尺寸的替换变换u多个简单算法的结合得到的加密算法比任多个简单算法的结合得到的加密算法比任何一个部分算法都要强何一个部分算法都要强u交替使用替换变换和排列交替使用替换变换和排列(permutation)u混淆混淆(confusion)和发散和发散(diffusion)概念概念的应用的应用Feistel结构图结构图Feistel结构定义结构定义u加密加密:Li =Ri-1;Ri=Li-1 F(Ri-1,Ki)u解密解密:Ri-1=Li Li-1=Ri F(Ri-1,Ki)=Ri F(Li,Ki)Feistel分组加密算法特点分组加密算法特点u分组大小。越大安全性越高，但速度下降，分组大小。越大安全性越高，但速度下降，64比较合理比较合理u密钥位数。越大安全性越高，但速度下降，密钥位数。越大安全性越高，但速度下降，64广泛使用，但现在已经不够用广泛使用，但现在已经不够用128u步数，典型步数，典型16步步u子钥产生算法。算法越复杂，就增加密码分析的子钥产生算法。算法越复杂，就增加密码分析的难度难度u每一步的子函数。函数越复杂，就增加密码分析每一步的子函数。函数越复杂，就增加密码分析的难度的难度u快速软件实现，包括加密和解密算法快速软件实现，包括加密和解密算法u易于分析。便于掌握算法的保密强度以及扩展办易于分析。便于掌握算法的保密强度以及扩展办法。法。Feistel分组分组加密算法加密算法之解密算法之解密算法Feistel分组加密算法之解密算法推导分组加密算法之解密算法推导DES算法算法u1977年由美国的标准化局年由美国的标准化局(NBS，现为现为NIST)采纳采纳u64位分组、位分组、56位密钥位密钥u历史：历史：IBM在在60年代启动了年代启动了LUCIFER项目，当时的项目，当时的算法采用算法采用128位密钥位密钥改进算法，降低为改进算法，降低为56位密钥，位密钥，IBM提交给提交给NBS(NIST)，于是产生于是产生DESDES算法基本结构算法基本结构DES:每一轮每一轮Li=Ri-1 Ri=Li-1 F(Ri-1,Ki)DES:Function FExpansion:32 48S-box:6 4 PermutationDES:32位到位到48位的扩展表位的扩展表32|01 02 03 04|0504|05 06 07 08|0908|09 10 11 12|1312|13 14 15 16|1716|17 18 19 20|2120|21 22 23 24|2524|25 26 27 28|2928|29 30 31 32|01DES:S-boxS(1):14 04 13 01 02 15 11 08 03 10 06 12 05 09 00 0700 15 07 04 14 02 13 01 10 06 12 11 09 05 03 0804 01 14 08 13 06 02 11 15 12 09 07 03 10 05 0015 12 08 02 04 09 01 07 05 11 03 14 10 00 06 13DES:Permutation16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04 25DES之每步密钥产生过程之每步密钥产生过程uPC-1在第一步之前在第一步之前uPC2u左移位数目表左移位数目表1或者或者2位位DES的强度的强度u56位密钥的使用位密钥的使用理论上的强度，理论上的强度，97年年$100000的机器可以在的机器可以在6小时内用穷举法攻破小时内用穷举法攻破DES实际攻破的例子，实际攻破的例子，97年年1月提出挑战，有人利月提出挑战，有人利用用Internet的分布式计算能力，组织志愿军连的分布式计算能力，组织志愿军连接了接了70000多个系统在多个系统在96天后攻破天后攻破uDES算法的本质算法的本质关键在于关键在于8个个S-BOXu针对针对DES的密码分析的密码分析差分分析法差分分析法线性分析法线性分析法差分分析法差分分析法u属于选择明文攻击属于选择明文攻击u基本思想：通过分析特定明文差对结果密基本思想：通过分析特定明文差对结果密文差的影响来获得可能性最大的密钥文差的影响来获得可能性最大的密钥u差分在差分在DES的的16步加密过程中的传递，每步加密过程中的传递，每一个一个S-BOX对于差分传递的概率特性对于差分传递的概率特性u子密钥不影响每一步的输入差分，但是影子密钥不影响每一步的输入差分，但是影响输出的差分响输出的差分u针对每一个针对每一个DES步骤，用差分法可以推导步骤，用差分法可以推导出该步的密钥出该步的密钥每一步的差分分析法每一步的差分分析法针对针对DES的密码分析的密码分析u差分分析法差分分析法247对选择明文，经过对选择明文，经过247量级的计算可攻破量级的计算可攻破u线性分析法线性分析法思想：用线性近似描述思想：用线性近似描述DES变换变换根据根据247已知明文，可以找到已知明文，可以找到DES的密钥的密钥二重二重DES C=EK2(EK1(P)P=DK1(DK2(C)针对两重分组加密算法的针对两重分组加密算法的中间相会攻击三重三重DESC=EK3(DK2(EK1(P)P=DK1(EK2(DK3(C)分组密码的用法分组密码的用法u电子簿模式电子簿模式(electronic codebook mode)ECBu密码块链接密码块链接(cipher block chaining)CBCu密码反馈方式密码反馈方式(cipher feedback)CFBu输出反馈方式输出反馈方式(output feedback)OFB电子簿模式电子簿模式ECBu相同明文相同明文相同密文相同密文u同样信息多次出现造同样信息多次出现造成泄漏成泄漏u信息块可被替换信息块可被替换u信息块可被重排信息块可被重排u密文块损坏密文块损坏仅仅对应对应明文块损坏明文块损坏u适合于传输短信息适合于传输短信息密码块链接密码块链接CBCu需要共同的初始化需要共同的初始化向量向量IVu相同明文相同明文不同密不同密文文u初始化向量初始化向量IV可以可以用来改变第一块用来改变第一块u密文块损坏密文块损坏两两明明文文块块损坏损坏u安全性好于安全性好于ECB密码反馈方式密码反馈方式CFBuCFB:分组密码分组密码流密码流密码u需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVu对于不同的消息，对于不同的消息，IV必须唯一必须唯一u一个单元损坏影响多个单元一个单元损坏影响多个单元:(W+j-1)/j W为分组加密块大小，为分组加密块大小，j为流单元位数为流单元位数输出反馈方式输出反馈方式OFBuOFB:分组密码分组密码流密码流密码u需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVu一个单元损坏只影响对应单元一个单元损坏只影响对应单元分组密码与序列分组密码与序列(流流)密码密码u定义：定义：分组密码分组密码(block cipher)是对一个大的明文块是对一个大的明文块(block)进行固定变换的操作进行固定变换的操作序列密码序列密码(stream cipher)也叫流密码，是对也叫流密码，是对单个明文位单个明文位(组组)的随时间变换的操作的随时间变换的操作u相互转换相互转换u序列密码序列密码异或异或One-time pad其他的密码算法其他的密码算法uIDEAuBlowfishuRC5uCAST-128uRC2uRC4IDEA算法算法u90年首次出现，年首次出现，91年修订，年修订，92公布细节公布细节u有望取代有望取代DESu128位密钥，位密钥，64位分组位分组u设计目标可从两个方面考虑设计目标可从两个方面考虑加密强度加密强度易实现性易实现性IDEA设计思想设计思想u得到得到confusion的途径的途径按位异或按位异或以以216(65536)为模的加法为模的加法以以216+1(65537)为模的乘法为模的乘法互不满足分配律、结合律互不满足分配律、结合律u得到得到diffusion的途径的途径乘加乘加(MA)结构结构u实现上的考虑实现上的考虑软件和硬件实现上的考虑软件和硬件实现上的考虑IDEA加密算法加密算法IDEA每一轮每一轮BLOWFISH算法算法u作者为作者为Bruce Schneier93uBLOWFISH算法特点算法特点采用了采用了Feistel结构，结构，16轮轮快速：快速：18时钟周期一个字节时钟周期一个字节紧凑：消耗不到紧凑：消耗不到5k内存内存简单：结构简单，易于实现和判定算法强度简单：结构简单，易于实现和判定算法强度安全性可变：通过选择不同的密钥长度选择安全性可变：通过选择不同的密钥长度选择不同的安全级别。从不同的安全级别。从32位到位到32*14=448位不位不等等子密钥产生过程复杂，一次性子密钥产生过程复杂，一次性BLOWFISH算法讨论算法讨论uBLOWFISH算法可能是最难攻破的传统加算法可能是最难攻破的传统加密算法，因为密算法，因为S-BOX密钥相关密钥相关u算法本身的特点算法本身的特点由于子密钥和由于子密钥和S-BOX产生需要执行产生需要执行521个个BLOWFISH加密算法，所以不适合于加密算法，所以不适合于密钥频繁变化的应用场合密钥频繁变化的应用场合子密钥和子密钥和S-BOX产生可以保存起来产生可以保存起来u与与Feistel分组密钥算法不同，每一步的两分组密钥算法不同，每一步的两个部分都参与运算，不是简单的传递个部分都参与运算，不是简单的传递u密钥变长带来灵活性密钥变长带来灵活性u速度快，在同类算法中相比较是最快的速度快，在同类算法中相比较是最快的RC5加密算法加密算法u作者为作者为Ron Rivestu算法特点算法特点三个参数三个参数参数参数w：表示字长，表示字长，RC5加密两字长分组，可用值加密两字长分组，可用值为为16、32、64参数参数r：表示轮数，可用值表示轮数，可用值0,1,255参数参数b：表示密钥表示密钥K的字节数，可用值的字节数，可用值0,1,255RC5版本：版本：RC5-w/r/b算法作者建议标定版本为算法作者建议标定版本为RC5-32/12/16RC5加密算法加密算法u三个基本运算三个基本运算字的加法，模字的加法，模2w +按位异或按位异或 左循环移位左循环移位 u算法：算法：LE0=A+S0RE0=B+S1for i=1 to r doLEi=(LEi-1REi-1)REi-1+S2*iREi=(REi-1LEi)LEi+S2*i+1RC5加、解密算法结构加、解密算法结构CAST-128加密算法加密算法uRFC 214497定义定义u密钥密钥48-128位，位，8位增量位增量u16轮轮Feistel分组结构分组结构u64位分组位分组u特殊处：特殊处：每一步两个子密钥每一步两个子密钥每一步的每一步的F不同不同CAST-128每步细节图每步细节图CAST-128算法之讨论算法之讨论uS-Box是固定的，但设计时尽量保证了非线是固定的，但设计时尽量保证了非线性。设计者认为，选择一个好的非线性性。设计者认为，选择一个好的非线性S-BOX比随机的比随机的S-BOX更可取更可取u子密钥的产生过程采用了与其他算法不同子密钥的产生过程采用了与其他算法不同的产生法来加强其强度。目标是对抗已知的产生法来加强其强度。目标是对抗已知明文攻击。明文攻击。Blowfish和和RC5算法使用了不算法使用了不同的技术来保证这一点。同的技术来保证这一点。uF函数具有好的函数具有好的confusion、diffusion等特等特性。子密钥相关、轮数相关增加了强度。性。子密钥相关、轮数相关增加了强度。RC2加密算法加密算法u设计者设计者Ron Rivestu分组长度分组长度64位，密钥长度位，密钥长度8到到1024位位u适合于在适合于在16位微处理器上实现位微处理器上实现uRC2在在S/MIME中用到的密钥为中用到的密钥为40、64、128位不等位不等RC4流加密算法流加密算法u设计者设计者Ron Rivestu工作方式工作方式OFBu算法特点：算法特点：简单、快速简单、快速随机序列的产生，用到随机序列的产生，用到8*8的的S盒盒AES介绍介绍u1997年年NIST宣布征集宣布征集AES算法算法要求要求:与三重与三重DES比，要快且至少一样安全比，要快且至少一样安全,分组分组128位位,密钥密钥128/192/256位位u1998年确定第一轮年确定第一轮15个候选者个候选者u1999年确定第二轮五个候选者年确定第二轮五个候选者:MARS,RC6,Rijndael,Serpent,Twofishu2000年底年底Rijndael胜出胜出Rijndael简介简介u不属于不属于Feistel结构结构u加密、解密相似但不对称加密、解密相似但不对称u支持支持128/192/256(/32=Nb)数据块大小数据块大小u支持支持128/192/256(/32=Nk)密钥长度密钥长度u有较好的数学理论作为基础有较好的数学理论作为基础u结构简单、速度快结构简单、速度快Rijndael简介简介(续续)u数据数据/密钥的矩阵表示密钥的矩阵表示a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33NrNb=4Nb=6Nb=8Nk=4 10 12 14Nk=6 12 12 14Nk=8 14 14 14u轮数轮数Rijndael算法结构算法结构u假设：假设：State表示数据，以及每一轮的中间结果表示数据，以及每一轮的中间结果RoundKey表示每一轮对应的子密钥表示每一轮对应的子密钥u算法如下：算法如下：第一轮之前执行第一轮之前执行AddRoundKey(State,RoundKey)Round(State,RoundKey)ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey);FinalRound(State,RoundKey)ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey);Rijndael:AddRoundKey操作操作u按字节在按字节在GF(28)上相加上相加(XOR)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35=b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35Rijndael:ByteSub操作操作uByteSub(S-box)非线性、可逆非线性、可逆u独立作用在每个字节上独立作用在每个字节上u先取先取GF(28)上乘法的逆上乘法的逆,再经过再经过GF(2)上一个仿射变换上一个仿射变换a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35S-boxaijbijRijndael:ShiftRow操作操作u第一行保持不变第一行保持不变,其他行内的字节循环移其他行内的字节循环移位位Rijndael:MixColumn操作操作u列作为列作为GF(28)上多项式乘以多项式上多项式乘以多项式c(x)多项式多项式c(x)=03x3+01x2+01x+02 c-1(x)=0Bx3+0Dx2+09x+0Eu模模M(x)=x4+1每一轮操作每一轮操作Round(State,RoundKey)ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey);a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35Rijndael:Key schedule(1)u主密钥生成子密钥数组主密钥生成子密钥数组,(Nr+1)*Nb个字个字uNk=6KeyExpansion(byte Key4*Nk,word WNb*(Nr+1)for(i=0;iNk;i+)Wi=(Key4*i,Key4*i|+1,Key4*i+2,Key4*i+3);for(i=Nk;iNb*(Nr+1);i+)temp=Wi-1;if(i%Nk=0)temp=ByteSub(temp6KeyExpansion(byte Key4*Nk,word WNb*(Nr+1)for(i=0;iNk;i+)Wi=(Key4*i,Key4*i|+1,Key4*i+2,Key4*i+3);for(i=Nk;iNb*(Nr+1);i+)temp=Wi-1;if(i%Nk=0)temp=ByteSub(temp8)Rconi/Nk;else if(i%Nk=4)temp=ByteSub(temp8);Wi=Wi-Nktemp;Rijndael:加密结构加密结构Rijndael(State,CipherKey)KeyExpansion(CipherKey,ExpandedKey);AddRoundKey(State,ExpandedKey)For(i=1;iNr;+i)ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,ExpandedKey+Nb*i);ByteSub(State);ShiftRow(State);AddRoundKey(State,ExpandedKey+Nb*i);Rijndael:解密结构解密结构AddRoundKey()For(i=1;iNr;+i)ByteSub();ShiftRow();MixColumn();AddRoundKey()ByteSub();ShiftRow();AddRoundKey()I_AddRoundKey()I_ShiftRow();I_ByteSub();For(i=1;iNr;+i)I_AddRoundKey()I_MixColumn();I_ShiftRow();I_ByteSub();I_AddRoundKey()I_AddRoundKey()For(i=1;iNr;+i)I_ShiftRow();I_ByteSub();I_AddRoundKey()I_MixColumn();I_ShiftRow();I_ByteSub();I_AddRoundKey()Rijndael算法的抵抗攻击能力算法的抵抗攻击能力u消除了消除了DES中出现的弱密钥的可能中出现的弱密钥的可能u也消除了也消除了IDEA中发现的弱密钥中发现的弱密钥u能有效抵抗目前已知的攻击算法能有效抵抗目前已知的攻击算法线性攻击线性攻击差分攻击差分攻击随机数产生随机数产生u随机数用途，重要的角色，例如随机数用途，重要的角色，例如认证过程中，避免重放攻击认证过程中，避免重放攻击会话密钥会话密钥RSA公钥算法公钥算法u随机数的基本特点随机数的基本特点随机性随机性均匀分布，有大量的测试方案均匀分布，有大量的测试方案独立性，难以测试，只能测试足够独立独立性，难以测试，只能测试足够独立不可预测性不可预测性u随机选择随机选择(Randomization)在算法设计中的意义在算法设计中的意义伪随机数产生器伪随机数产生器线性一致法线性一致法(linear congruential method)基于密码学产生的随机数基于密码学产生的随机数(一一)之循环加密法之循环加密法基于密码学产生的随机数基于密码学产生的随机数(二二)之之DES输出反馈模型输出反馈模型基于密码学产生的随机数基于密码学产生的随机数(三三)之之ANSI X9.17BBS伪随机数伪随机数产生器产生器u通过了通过了“下一位下一位”测试测试(next-bit test)不存在多项式时间的算法使得在已知前不存在多项式时间的算法使得在已知前k位的位的情况下预测出第情况下预测出第k+1位的概率大于位的概率大于0.5uBBS的安全性同样基于分解的安全性同样基于分解n的难度的难度