计算机网络安全原理（第2版）课件 第2章 密码学基础知识

第二章密码学基础知识内容提要密码学概述1典型对称密码系统234典型公开密码系统国密算法5密码分析密码案例1942年6月，在关系到日美太平洋战争转折点的中途岛海战中，日军出现了两起严重泄密事件：一是在战役发起前夕，日海军第二联合特别陆战队的一个副官，用低等级密码发电说：六月五日以后，本部队的邮件请寄到中途岛。二是日军军港的一个后勤部门，用简易密码与担任进攻中途岛任务的部队联系淡水供应问题。结果，以上两电均被设在珍珠港的美国海军破译，从而掌握了日军进攻中途岛的日期和兵力，致使日军在战役中遭到惨败。密码技术密码技术通过对信息的变换或编码，将机密的敏感信息变换成攻击者难以读懂的乱码型信息，以此达到两个目的：使攻击者无法从截获的信息中得到任何有意义信息；使攻击者无法伪造任何信息。密码技术不仅可以解决网络信息的保密性，而且可用于解决信息的完整性、可用性及不可否认性，是网络安全技术的核心和基石，是攻防都需了解的技术。概念：密码系统密码系统(Cryptosystem)，也称为密码体制，用数学符号描述为：S={M,C,K,E,D}M是明文空间，表示全体明文集合。明文是指加密前的原始信息，即需要隐藏的信息；C是密文空间，表示全体密文的集合。密文是指明文被加密后的信息，一般是毫无识别意义的字符序列；K是密钥或密钥空间。密钥是指控制加密算法和解密算法得以实现的关键信息，可分为加密密钥和解密密钥，两者可相同也可不同；密码算法是指明文和密文之间的变换法则，其形式一般是计算某些量值或某个反复出现的数学问题的求解公式，或者相应的程序。E是加密算法，D是解密算法。解密算法是加密算法的逆运算，且其对应关系是唯一的。典型密码系统组成发送者加密器c=E(k1,m)解密器m=D(k2,

c)接收者密钥产生器非法侵入者密码分析员（窃听者）密钥信道mccmm’=h(c)k1k2主动攻击被动攻击密钥信道概念：密码学密码学(cryptology)：是一门关于发现、认识、掌握和利用密码内在规律的科学，由密码编码学(cryptography)和密码分析学(cryptanalysis)组成。密码编码学对信息进行编码实现信息隐藏的一门学科。主要依赖于数学知识。主要方法有：换位、代换、加乱密码系统的安全策略密码系统可以采用的两种安全策略：基于算法保密和基于密码保护。基于算法保密的策略有没有什么不足之处？？算法的开发非常复杂。一旦算法泄密，重新开发需要一定的时间；不便于标准化：由于每个用户单位必须有自己的加密算法，不可能采用统一的硬件和软件产品；不便于质量控制：用户自己开发算法，需要好的密码专家，否则对安全性难于保障。密码系统的设计要求设计要求：系统即使达不到理论上不可破译，也应该是实际上不可破译的(也就是说，从截获的密文或某些已知的明文和密文对，要决定密钥或任意明文在计算上是不可行的)；加密算法和解密算法适用于所有密钥空间的元素；系统便于实现和使用方便；系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥（著名的Kerckhoff原则，现代密码学的一个基本原则）。密码体制分类密码体制从原理上分为两类：单钥密码体制(One-keySystem)或对称密码体制（SymmetricCryptosystem）双钥密码体制(Two-KeySystem)或公开密码体制（PublicKeyCryptosystem）密码学发展简史(1/4)一般来说，密码学的发展划分为三个阶段：第一阶段为从古代到1949年。这一时期可以看作是科学密码学的前夜时期，这阶段的密码技术可以说是一种艺术，而不是一种科学，密码学专家常常是凭知觉和信念来进行密码设计和分析，而不是推理和证明。密码学发展简史(2/4)一般来说，密码学的发展划分为三个阶段：第二阶段为从1949年到1975年。1949年Shannon发表的“保密系统的信息理论”为私钥密码系统建立了理论基础，从此密码学成为一门科学，但密码学直到今天仍具有艺术性，是具有艺术性的一门科学。这段时期密码学理论的研究工作进展不大，公开的密码学文献很少。密码学发展简史(3/4)一般来说，密码学的发展划分为三个阶段：第三阶段为从1976年至今。1976年diffie和hellman发表的文章“密码学的新动向”一文导致了密码学上的一场革命。他们首先证明了在发送端和接受端无密钥传输的保密通讯是可能的，从而开创了公钥密码学的新纪元。密码学发展简史(4/4)在密码学发展史上有两个重要因素：战争的刺激和科学技术的发展推动了密码学的发展。信息技术的发展和广泛应用为密码学开辟了广阔的天地。一、对称密码系统对称密码体制：概述对称密码体制（symmetriccryptosystem）的加密密钥和解密密钥相同，也叫单钥密码体制或者秘密密码体制。发送者加密器c=E(k

,m)解密器m=D(k,

c)接收者密钥产生器密钥信道mcmkk密钥信道对称密码体制：概述对称密码算法的设计思想：古典密码：以代换（或代替，Substitution）和置换（Permutation）运算为基础现代对称密码：多以混乱（confusion）和扩散（diffusion）运算为基础古典密码思想：代换与置换置换对明文字符按某种规律进行位置的交换而形成新的排列代换将明文字母替换成其他字母、数字或符号的方法扩散所谓扩散，就是将算法设计得使每一比特明文的变化尽可能多地影响到输出密文序列的变化，以便隐蔽明文的统计特性；将每一位密钥的影响也尽可能迅速地扩展到较多的输出密文比特中去。扩散的目的是希望密文中的任一比特都要尽可能与明文、密文相关联，或者说，明文和密钥中任何一比特的改变，对密文的每个比特都有影响，能够以50%的概率改变密文的每个比特扩散的举例说明无扩散技术的加密

p1:00000000c1:00000010p2:00000001c2:00000011有扩散技术的加密

p1:00000000c1:01011010p2:00000001c2:11101011混乱所谓混乱，是指在加密变换过程中使得明文、密钥以及密文之间的关系尽可能地复杂化，以防密码破译者采用统计分析法进行破译攻击。混乱可以用“搅拌机”来形象地解释，将一组明文和一组密钥输入到算法中，经过充分混合，最后变成密文。执行这种“混乱”作业的每一步都必须是可逆的，即明文混乱以后能得到密文，反之，密文经过逆向的混乱操作以后能恢复出明文。对称密码体制：概述对称密码体制对明文加密有两种方式：序列密码（或流密码，StreamCipher）分组密码(BlockCipher)序列密码（1/2）主要原理：以明文的比特为加密单位，用某一个伪随机序列作为加密密钥，与明文进行异或运算，获得密文序列；在接收端，用相同的随机序列与密文进行异或运算便可恢复明文序列。=10111101…---------------=00110010…

10001111…

00110010…=

10111101…密钥序列产生算法密钥序列种子密钥密钥序列产生算法密钥序列种子密钥序列密码（2/2）序列密码算法的安全强度完全取决于伪随机序列的好坏，因此关键问题是：伪随机序列发生器的设计。优点：错误扩散小（一个码元出错不影响其它码元）；速度快、实时性好；安全程度高。缺点：密钥需要同步分组密码（1/3）主要原理：在密钥的控制下一次变换一个明文分组；将明文序列以固定长度进行分组，每一组明文用相同的密钥和加密函数进行运算。加密算法解密算法密钥K=(k0,k1,…,kL-1)密钥K=(k0,k1,…,kL-1)明文X=(x0,x1,…,xm-1)明文X=(x0,x1,…,xm-1)密文Y=(y0,y1,…,ym-1)工作模式电码本模式(ElectronicCodebookMode，ECB)密码分组链接模式(CipherBlockChaining，CBC)密码反馈模式(CipherFeedback，CFB)计数器模式(Counter，CTR)输出反馈模式

(OutputFeedback，OFB)实际应用时，分组密码名称中常带上工作模式，如DES-CBC分组密码（2/3）分组密码（3/3）优缺点：容易检测出对信息的篡改，且不需要密钥同步，具有很强的适应性；（与序列密码相比）分组密码在设计上的自由度小。最典型分组密码是DES数据加密标准，它是单钥密码体制的最成功的例子。二、公开密码系统公开密码体制1976年，Diffie、Hellmann在论文“Newdirectionsincryptography”提出了双钥密码体制（奠定了公钥密码系统的基础），每个用户都有一对密钥：一个是公钥（PK），可以像电话号码一样进行注册公布；另一个是私钥（SK），由用户自己秘密保存；两个密钥之间存在某种算法联系，但由一个密钥无法或很难推导出另一个密钥。又称为公钥密码体制或非对称密码体制（asymmetriccryptosystem）。发送者加密器c=E(m,k1)解密器m=D(c,k2)接收者密钥产生器密钥信道mcmk1k2密钥信道公开密码体制：特点整个系统的安全性在于：从对方的公钥PK和密文中要推出明文或私钥SK在计算上是不可行的公开密码体制的主要特点是将加密和解密能力分开，可以实现：多个用户加密的消息只能由一个用户解读：保密通信；只由一个用户加密消息而使多个用户可以解读：数字签名认证。公开密码体制：实现技术根据其所依据的数学难题可分为4类：大整数分解问题类：RSA密码体制（最著名的双钥密码体制）椭圆曲线类（椭园曲线上的离散对数问题）离散对数问题类（基于有限域乘法群上的离散对数问题）背包问题三、对称和公开的混合使用链式加密对称和非对称结合内容提要密码学概述1典型对称密码系统234典型公开密码系统国密算法5密码分析一、DESDES密码体制DES是IBM公司于1970年研制的DES(DataEncryptionStandard)算法。该算法于1977年1月15日被美国国家标准局NBS颁布为商用数据加密标准，每5年被评估1次。DES加密过程64bit明文数据初始置换IP乘积变换（16次迭代）逆初始置换IP-164bit密文数据64bit密钥子密钥生成输入输出初始置换初始置换对输入的比特位置进行调整。通过初始置换表实现初始置换的功能举例来看，输入为8位01110010初始置换表为：则输出为：10001101输入位12345678输出位35612487DES加密过程64bit明文数据初始置换IP乘积变换（16次迭代）逆初始置换IP-164bit密文数据64bit密钥子密钥生成输入输出通过64bit密钥产生16个不同的子密钥，每个子密钥为48bit，在每一轮中使用。子密钥产生有专门的算法，图4.1416次迭代通过初始置换得到X0，X0被分为左右两部分，即X0

=L0R0

16次迭代：i=1,2,…,16

Xi-1=Li-1Ri-1，Li=Ri-1，Ri=Li-1

F(Ri-1,Ki)Li-1Ri-1F+LiRiKi每次迭代只对右边的32bit进行一系列的加密变换：扩展运算E、密钥加密运算、选择压缩运算S、置换运算T及左右异和运算。F(Ri-1,Ki)=P(S(E(Ri-1)Ki))每次迭代的最后，把左边的32bit与右边变换得到的32bit逐位模2加，作为下一轮迭代时右边的段将变换前的右边的段直接送到左边的寄存器中作为下一轮迭代时左边的段S是一组八个变换S1，S2，S3，…，S8，称为S盒，每个盒以6位输入，4位输出，S盒构成了DES安全的核心。S盒替换共8个S盒S盒的规则S-盒2S-盒3S-盒4S-盒6S-盒7S-盒8S-盒1S-盒5S-盒的构造P盒置换保证上一轮某个s盒的输出对下一轮多个s盒产生影响DES解密解密方法：把子密钥的顺序颠倒过来，即把K1～K16换为K16～K1,再输入密文，采用与加密同样的算法，就可还原明文DES的安全性DES系统的保密性主要取决于什么？密钥的安全性。穷举法破解有人认为S盒可能含有某种“陷门”，美国国家安全机关可以解密。如何将密钥安全、可靠地分配给通信双方，在网络通信条件下就更为复杂，包括密钥产生、分配、存储、销毁等多方面的问题，统称为密钥管理。密钥管理是影响DES等单钥密码体制安全的关键因素。因为即使密码算法再好，若密钥管理处理不当，也很难保证系统的安全性。DES的56位密钥可能太小1998年7月，EFE宣布攻破了DES算法，他们使用的是不到25万美元的特殊的“DES破译机”，这种攻击只需要不到3天的时间。以现有网络计算能力，破解非常容易DES的迭代次数可能太少（16次恰巧能抵抗差分分析）DES的安全性DES破解器1998年，电子前哨基金会（EFF）制造了一台DES破解器，它使用多个DeepCrack芯片搭成而成，造价约$250,000，包括1,856个自定义的芯片，在56个小时内利用穷尽搜索的方法破译了56位密钥长度的DES2025/3/1851二、3DES3DES在DES算法的基础上，于1985年提出了TripleDES（3DES）加密算法，在1999年被加入到DES系统当中。原理：3个密钥或2个密钥执行3次常规的DES加密。c=E(k3,D(k2,E(k1,m)))m=D(k1,E(k2,D(c,k3)))优点：3DES的密钥长度是192位，其中去除校验位的有效密钥长度为168位，足够抵抗穷举攻击。缺点：算法较慢，相当于执行3遍DES。3DES三、AESAES1997年4月15日美国国家标准技术研究所(NIST)发起征集AES（AdvancedEncryptionStandards）算法的活动，并专门成立了AES工作组基本要求：AES应该像DES和TDES那样是一个块加密方法，并且至少像TDES一样安全，但是其软件实现应该比TDES更加有效NIST指定AES必须：公开算法；分组大小为128比特的分组密码，支持密钥长度为128、192和256比特；通用性对AES候选方案的评审标准有3条：（1）全面的安全性，这是最为重要的指标。（2）性能，特别是软件实现的处理性能。（3）算法的知识产权等特征。

AES1998年确定第一轮15个候选者1999年确定第二轮五个候选者

MARSRC6RijndaelSerpentTwofishAES经过多轮评估、测试，NIST于2000年10月2日正式宣布选中比利时密码学家JoanDaemen和VincentRijmen提出的密码算法RijndaelNIST于2001年11月26日发布于FIPSPUB197，并在2002年5月26日成为有效的标准AESRijndael汇聚了安全、效率、易用、灵活等优点，使它能成为AES最合适选择不属于Feistel结构加密、解密相似但不完全对称支持128/192/256(/32=Nb)数据块大小支持128/192/256(/32=Nk)密钥长度有较好的数学理论作为基础结构简单、速度快AESAES算法与Rijndael算法常常将DES算法称为Rijndael算法严格地讲，Rijndael算法和AES算法并不完全一样，因为Rijndael算法是数据块长度和加密密钥长度都可变的迭代分组加密算法，其数据块和密钥的长度可以是128位、192位和256位。尽管如此，在实际应用中二者常常被认为是等同的AESRijndael算法采用替换/转换网络，每一轮包含三层非线性层：字节替换，由16个S-盒并置而成，主要作用是字节内部混淆；线性混合层：通过列混合变换和行移位变换确保多轮密码变换之后密码的整体混乱和高度扩散；轮密钥加层：简单地将轮（子）密钥矩阵按位异或到中间状态矩阵上S-盒选取的是有限域GF（28）中的乘法逆运算AES算法描述预处理：先对要加密的数据块进行预处理，使其成为一个长方形的字阵列，每个字含4个字节，占一列，每列4行存放该列对应的4个字节，每个字节含8bit信息。Nb表示分组中字的个数（也就是列的个数），Nk表示密钥中字的个数AES算法描述预处理：先对要加密的数据块进行预处理，使其成为一个长方形的字阵列，每个字含4个字节，占一列，每列4行存放该列对应的4个字节，每个字节含8bit信息。Nb表示分组中字的个数（也就是列的个数），Nk表示密钥中字的个数AES算法描述预处理多轮迭代：明文分组进入多轮迭代变换，迭代的轮数Nr由Nb和Nk共同决定，可查表AES加解密过程AES最后一轮不做列混合运算安全性：Rijndael算法进行8轮以上即可对抗线性密码分析、差分密码分析，亦可抵抗专门针对Square算法提出的Square攻击。当密钥长度分别为128比特、192比特和256比特时，对应的运算量分别为2127、2191和2255灵活性：Rijndael的密钥长度可根据不同的加密级别进行选择。Rijndael的循环次数允许在一定范围内根据安全要求进行修正。AES四、IDEAIDEA国际数据加密算法(IDEA,InternationalDataEncryptionalgorithm)中国学者来学嘉博士与著名密码学家JamesMassey于1990年提出的一种分组密码算法定义了三种基本运算：异或，整数加密，整数乘数，并设计了具有良好扩散功能的MA乘加结构IDEAIDEA安全性1992年进行了改进：抗差分攻击密钥为128bit，穷举攻击要试探2128个密钥，若用每秒100万次加密的速度进行试探，大约需要1013年。分组密码算法比较算法密钥长度分组长度循环次数DES566416三重DES112/1686448IDEA128648AES128/192/256128/192/25610/12/14五、流密码RC4RC4（RivestCipher4）是一种流密码算法，由RonRivest在1987年设计出的密钥长度可变的加密算法簇。起初该算法是商业机密，直到1994年，才公诸于众RC4基本概念RC4算法过程RC4算法过程RC4算法过程RC4安全性分析当密钥长度超过128位时，以当前的技术而言，RC4是很安全的，RC4也是唯一对2011年TLS1.0BEAST攻击免疫的常见密码。近年来RC4爆出多个漏洞，安全性有所下降。例如，2015年比利时鲁汶大学的研究人员MathyVanhoef与FrankPiessens，公布了针对RC4加密算法的新型攻击方法，可在75小时内取得cookie的内容。因此，2015年IETF发布了RFC7465，禁止在TLS中使用RC4，NIST也禁止在美国政府的信息系统中使用RC4。著名的分布式代码管理网站Github从2015年1月5日起也停止对RC4的支持RC4单钥密码体制的优缺点单钥密码技术可以用来做什么？加密和认证单钥密码体制具有加解密算法简便高效，加解密速度快、安全性很高的优点，应用非常广泛；存在一些问题，而且靠自身无法解决：密钥分配困难；需要密钥量大（n个用户之间互相进行保密通信，需要n(n-1)/2个密钥）内容提要密码学概述1典型对称密码系统234典型公开密码系统国密算法5密码分析一、RSARSA密码体制RSA公钥体制是1978年由麻省理工学院3位年青数学家：Rivest,Shamir,Adleman提出的基于数论的双钥密码体制。（开始被称作“MIT体制”）RSA体制基于“大数分解和素数检测”这一著名数论难题：将两个大素数相乘十分容易，但将该乘积分解为两个大素数因子却极端困难；素数检测就是判定一个给定的正整数是否为素数。84整数的因子分解问题（1/3）整数的因子分解问题：将两个素数11927和20903相乘，可以很容易地得出249310081。但是将它们的积249310081分解因子得出上述两个素数却要困难得多。即使最大型的计算机将一个大的乘积数分解还原为组成此数的两个素数也要很长时间。从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积。整数的因子分解问题（2/3）Rivest，Shamir，Adleman提出，分解一个130位的两个素数的乘积数需要几百万年的时间，为了证明这一点，他们找到1个129位数，并向世界挑战找出它的两个因子。RSA129：11431862575788886766923577997614661201021829672124236256256184293570693524573389783059712356395870558989075147599290026879543541整数的因子分解问题（3/3）世界各地600多个研究人员和爱好者通过Internet协调各自计算机的工作向这个129位数发动了进攻。花费了近一年的时间，终于分解出了这个数的两个素数，其中一个长64位，另一个长65位，这两个素数分别为：349052951084765094914784961990389813341776463849338784399082057732769132993266709549961988190834461413177642967992942539539798288533

说明两个问题：（1）整数的因子分解问题是一个计算开销非常大的问题；（2）Internet协同计算能力的强大。RSA密钥产生过程产生过程如下：生成两个大素数p

和q；计算这两个素数的乘积n=p*q；计算小于n并且与n互质的整数的个数，即欧拉函数φ(n)=(p-1)*(q-1)；随机选择一个加密密钥e，使e满足1<e<φ(n)，并且e和φ(n)互质；利用欧几里德扩展算法计算e的逆元d，以满足：

e*d

≡1modφ(n)公钥PK={e,n}；对应的私钥SK={d}欧拉函数在数论中，对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler’stotientfunction、φ函数、欧拉商数等，例如：φ(1)=1，唯一和1互质的数就是1本身；φ(8)=4，因为1,3,5,7均和8互质。欧拉函数给定一个正整数n，用ψ(n)表示比n小且与n互为素数的正整数的个数，称ψ(n)为欧拉函数ψ(n)＝r1a1-1(r1-1)r2a2-1(r2-1)…rnan-1(rn-1)

其中n=r1a1r2a2…rnan例如：

24=23*31

ψ(24)=23-1(2-1)*31-1(3-1)=8{1,5,7,11,13,17,19,23}

欧拉定理若整数a和n互素，则aψ(n)

=1(modn)举例说明：ψ(24)=8{1,5,7,11,13,17,19,23}是小于24并与24互素的数18=1mod24即：1ψ(24)=1mod2458=1mod24即：5ψ(24)=1mod2478=1mod24即：7ψ(24)=1mod24……RSA密钥产生过程产生过程如下：生成两个大素数p

和q；计算这两个素数的乘积n=p*q；计算小于n并且与n互质的整数的个数，即欧拉函数φ(n)=(p-1)*(q-1)；随机选择一个加密密钥e，使e满足1<e<φ(n)，并且e和φ(n)互质；利用欧几里德扩展算法计算e的逆元d，以满足：

e*d≡1modφ(n)公钥PK={e,n}；对应的私钥SK={d}欧几里德扩展算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：gcd(a,b)=gcd(b,amodb)RSA密钥产生过程产生过程如下：生成两个大素数p

和q；计算这两个素数的乘积n=p*q；计算小于n并且与n互质的整数的个数，即欧拉函数φ(n)=(p-1)*(q-1)；随机选择一个加密密钥e，使e满足1<e<φ(n)，并且e和φ(n)互质；利用欧几里德扩展算法计算e的逆元d，以满足：

e*d≡1modφ(n)公钥PK={e,n}；对应的私钥SK={d}RSA密钥产生的实例选择素数:p=17，q=11计算n=p*q=17*11=187计算φ(n)=(p–1)*(q-1)=16*10=160选择

e：gcd(e,160)=1；选择e=7确定d：d*e=1mod160andd<160；d=23因为23*7=161=1*160+1公钥PK={7,187}私钥SK={23}RSA的加解密操作为了对消息内容M进行加密，发送者:获得接收者的公钥PK={e,n}计算:C=Memodn为了解密密文C，接收者：使用自己的私钥SK={d}计算:M=Cd

modnRSA加解密操作实例假定：接收方公钥PK={7,187}接收方私钥SK={23}

给定消息M=88加密:C=887mod187=11解密:M=1123mod187=88应用一：加密通信用户将自己的公钥登记在一个公开密钥库或实时公开，私钥则被严格保密。信源为了向信宿发送信息，去公开密钥库查找对方的公开密钥，或临时向对方索取公钥，将要发送的信息用这个公钥加密后在公开信道上发送给对方。对方收到信息（密文）后，则用自己的私钥解密密文，从而读取信息。优点：省去了从秘密信道传递密钥的过程RSA的应用应用二：数字签名RSA的应用RSA公钥体制的优缺点优点：保密强度高密钥分配及管理简便可以用于数字签名实现身份认证缺点：运算复杂，速度慢：硬件实现时，RSA比DES要慢大约1000倍，软件实现时，RSA比DES要慢大约100倍。很多实际系统中，只用RSA来交换DES的密钥，而用DES来加密主体信息。RSA公钥体制的安全性依赖于未被证明的“整数的因子分解问题”假若数学理论进一步发展，发现“整数的因子分解问题”是一个可以快速解决的问题？以RSA为代表的公钥体制的加密操作是公开的，任何人都可以选择明文，并利用公开的公钥来攻击RSA公钥体制。明文空间必须足够大才能够防止穷尽搜索明文空间攻击；如果用公钥体制加密会话密钥，会话密钥必须足够的长。RSA攻击方法穷举攻击：尝试所有可能的密钥数学攻击：对两个素数乘积的因子分解（FAC问题）计时攻击：依赖于解密算法的运行时间选择密文攻击：利用了RSA算法的性质RSA安全性数学攻击RSA安全性计时攻击RSA安全性RSA安全性二、Diffie-Hellman密钥交换算法Diffie-Hellman密钥交换算法（简称为“DH算法”或“DH交换”）由WhitfieldDiffie和MartinHellman于1976提出，是最早的密钥交换算法之一，它使得通信的双方能在非安全的信道中安全的交换密钥，用于加密后续的通信消息。该算法被广泛应用于安全领域，如TLS和IPsec协议DHDiffie-Hellman算法的有效性依赖于计算离散对数的难度DH算法过程DH示例：假定素数q=97，取97的一个原根a=5。A和B分别选择私有密钥XA=36和XB=58，各自计算得到公钥分别为：YA=50，YB=44，秘密密钥K=75DH示例DH优点仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会除对全局参数的约定外，密钥交换不需要事先存在的基础设施DH缺点没有提供双方身份的任何信息，因此易受中间人攻击。这一缺陷可以通过数字签名和公钥证书来解决容易遭受阻塞性攻击。由于算法是计算密集性的，如果攻击者请求大量的密钥，被攻击者将花费大量计算资源来求解无用的幂系数而不是在做真正的工作DHDH三、ElGamal公钥密码体制ElGamal公钥密码体制是由T.ElGamal于1984年提出，算法既能用于数据加密也能用于数字签名。与Diffie-Hellman算法一样，其安全性也依赖于计算有限域上离散对数这一难题ElGamal密钥产生方法选择一个素数q，获取素数q的一个原根

。其中，q和

是公开的，并且可由一组用户共享生成一个随机数x作为其秘密的解密密钥，使得1≤x≤q–1，计算y=

xmodq，则公钥为(y,

,q)，私钥是xElGamal加密如果用户B要向A发送信息，则其利用A的公钥(y,

,q)对信息进行加密解密通过计算U=m1xmodq恢复密钥，然后恢复明文：m=m2×(U)-1modqElGamal安全分析ElGamal算法的安全性是建立在有限域上求离散对数问题的难解性上为了安全，一般要求在ElGamal密码算法的应用中，素数q按十进制数表示，那么至少应该有150位数字，并且q–1至少应该有一个大的素数因子。同时，加密和签名所使用的k必须是一次性的。如果k不是一次性的，时间长了就可能被攻击者获得。ElGamal四、ECC椭圆曲线密码（EllipticCurveCryptography,ECC）是一种公开密钥密码体制，于20世纪80年代由华盛顿大学的NealKoblitz和IBM的VictorMiller分别独立提出。ECC以椭圆曲线理论为基础，利用有限域上椭圆曲线的点构成的Abel群离散对数难解性，实现加密、解密和数字签名，将椭圆曲线中的加法运算与离散对数中的模乘运算相对应，就可以建立基于椭圆曲线的对应密码体制。ECCEC椭圆群上的离散对数问题（EllipticCurveDiscreteLogarithmProblem,ECDLP）指的是：从椭圆曲线E[K]上的解点所构成的交换群中可以找到一个n阶循环子群，当n是足够大的素数时，这个循环子群中的离散对数问题是困难的。具体而言，设A和B是椭圆曲线上的两个解点，以点A为生成元来生成n阶循环子群，x为一正整数，且

，若给定A和x，可以很容易地计算出B=xA，但要是已知A，B点，要想找出x则很困难ECDLP目前也只有特殊的几类椭圆曲线的ECDLP被解决，大多数仍然无解。对已解决的几类ECDLP，可以找到一条椭圆曲线Y，将明文编码后嵌入Y的解点中，再对Y进行加密，加密算法可以是我们以前熟知的算法。常见椭圆曲线密码有：用于加必的EC-ElGamal（EllipticCurveElGamal），用于密钥交换的ECDH（EllipticCurveDiffie-Hellman）和ECDHE（ECDHEphemeral），用于数字签名的ECDSA（EllipticCurveDigitalSignatureAlgorithm）等ECCECE：用于加密EC与EIGamalECDH：用于密钥交换ECDHE：动态分配密钥ECC与DH结合(ECDH)ECDSA：用于数字签名ECC与DSA结合（ECDSA）ECC的主要优势是密钥小，算法实施方便，计算速度快，非常适于无线应用环境（在IoT领域应用广泛），而且安全性高ECC安全性ECC依赖的椭圆曲线离散对数难题的计算复杂度是指数级，而RSA所采用的整数因式分解难题的计算复杂度是亚指数级，所以椭圆曲线密码从理论上来说更难以攻破，更安全ECC非对称密码比传统对称密码更安全？不是！任何加密方法安全性依赖于密钥的长度和破译密文所需要的计算量讨论非对称密码是一种通用的方法，传统对称密码已经过时？不是！非对称密码的计算量大，目前不能取代传统密码“非对称密码学仅限于用在密钥管理和签名此类应用上，这几乎是被广泛接受的事实”讨论传统对称密码中与密钥分配中心KDC的握手是一件麻烦的事情，非对称密码的密钥管理非常简单？不！只是有所简化，但也需要某种形式的协议，该协议一般包含一个中心代理，处理并不比传统密码中的那些工程更简单讨论内容提要密码学概述1典型对称密码系统234典型公开密码系统国密算法5密码分析发展历程国密算法是国家商用密码算法的简称。自2012年以来，国家密码管理局以《中华人民共和国密码行业标准》的方式，陆续公布了SM2/SM3/SM4/SM9、祖冲之（ZUC）等密码算法标准及其应用规范，并相继纳入ISO/IEC标准体系还有未公开的对称密码算法SM1/SM7国密算法主要的国密算法国密算法主要的国密算法国密算法主要的国密算法国密算法2015年4月起，陆续提交三个国密算法国际标准提案：SM3杂凑算法纳入ISO/IEC10118-3，SM2数字签名算法和SM9数字签名算法纳入ISO/IEC14888-3，SM4算法纳入ISO/IEC18033-3。2017年11月，SM2和SM9正式成为ISO/IEC国际标准。2018年4月，SM3正式成为ISO/IEC国际标准中的算法。国密算法加入国际标准2020年8月，ZUC序列密码算法作为“ISO/IEC18033-4:2011/AMD1:2020信息技术—安全技术—加密算法—第四部分：序列密码—补篇1：ZUC”正式发布（2018年4月提交的标准草案）国密算法加入国际标准2021.6:SM4分组密码算法作为ISO/IEC18033-3:2010补篇正式发布（2016.10正式提交，2017.4立项）国密算法加入国际标准北京大学关志副研究员的密码学研究组开发维护了一个国密算法的开源实现项目GmSSL（官网：/，后改为/gmssl/index.jsp），项目源码托管于GitHub（/guanzhi/GmSSL.git）支持所有公开的国密算法与OpenSSL兼容国密算法2020年1月1日《中华人民共和国密码法》正式实施国密算法2020年1月1日《中华人民共和国密码法》正式实施近年来，已有大量国内安全厂商在其各类安全产品中支持国密算法。密码法实施后，很多单位在招标采购时，也要求支持国密算法。国密算法内容提要密码学概述1典型对称密码系统234典型公开密码系统国密算法5密码分析密码分析学（cryptanalysis）密码分析学，俗称：密码破译截收者在不知道解密密钥和通信者所采用的加密算法的细节条件下，对密文进行分析，试图获取机密信息、研究分析解密规律的科学。密码分析除了依靠数学、工程背景、语言学等知识外，还要依靠经验、统计、测试、眼力、直觉判断能力等因素，有时还要靠运气。主要分析途径穷举破译法(ExhaustiveAttackorBrute-forceMethod)分析破译法穷举破译法解密思路：m=D(c,k2)方法一（

k2）：对截收的密文依次用各种可解的密钥试译，直接得到有意义的明文方法二（m）：在不变密钥下，对所有可能的明文加密直到得到与截收的密文一致为止只要有足够多的计算时间和存储容量，原则上穷举法破译总是可以成功的。因此，密码设计应使穷举不可行。分析破译法确定性分析法（数字分析法）：利用一个或几个已知量（如已知密文或明文密文对）用数学关系式表示出所求未知量（如密钥等）的方法统计分析法：利用明文的已知统计规律进行破译的方法。对截收的密文进行统计分析，总结出密文的统计规律，并与明文的统计规律进行对照比较，从而提取出明文和密文之间的对应或变换信息。

五种攻击唯密文攻击(CiphertextOnlyAttacks)已知明文攻击(KnownPlaintextAttacks)选择明文攻击(ChosenPlaintextAttacks)选择密文攻击(ChosenCiphertextAttack)选择文本攻击(ChosenTextAttack)2025/3/18149密码攻击唯密文攻击(CiphertextOnlyAttacks)在仅知已加密文字的情况下进行穷举攻击，可取得原始明文中的全部信息、部分信息或解密密钥。此时攻击的条件就是：已知算法，不知道密钥，要对密文进行强行破解。此方案适用于何种密码体制？同时适用于对称密码体制和非对称密码体制2025/3/18150密码攻击已知明文攻击(KnownPlaintextAttacks)前提条件：已知密文，已知明文，已知算法，求密钥。2025/3/18151密码攻击选择明文攻击(ChosenPlaintextAttacks)攻击者不但可以获取明文―密文对（如事先任意选择一定数量的明文，让被攻击的加密算法加密，并得到相应的密文），而且可以对这些明文-密文对进行选择，从而选择那些拥有更多特征的明文-密文对，以有利于对密码的分析通过这一过程获得关于加密算法的一些信息，以利于在将来更有效的破解由同样加密算法（以及相关密钥）加密的信息。在最坏情况下，攻击者可以直接获得解密用的钥匙。适用于什么样的密码机制？2025/3/18152密码攻击选择密文攻击(ChosenCiphertextAttack)指密码分析者可以选择一些密文，并得到相应的明文。任务目标是推出密钥。多用于攻击公钥密码体制，也可用于对称密码体制2025/3/18153选择文本攻击(ChosenTextAttack)选择明文攻击和选择密文攻击的组合，即密码分析者在掌握密码算法的前提下不仅能够选择明文并得到对应的密文，而且还能选择密文得到对应的明文。这种情况往往是密码分析者通过某种手段暂时控制加密机和解密机密码攻击分析破译法王小云院士：模差分比特分析法：MD4、MD5、RIPEMD、HAVAL-128、SHA12025/3/18155密码分析前面讲到的是传统的密码分析学，这类方法将密码算法看作是一个理想而抽象的数学变换，假定攻击者不能获取除密文和密码算法以外的其他信息。密钥越长，上述方法越难破解。就没有其它分析方法吗？密码分析思考：密码算法的设计安全性等于密码算法的实现安全性吗？旁路分析现实世界中，密码算法的实现总需要基于一个物理平台，即密码芯片。由于芯片的物理特性会产生额外的信息泄露，如密码算法在执行时无意泄露的执行时间、功率消耗、电磁辐射、Cache访问特征、声音等信息，或攻击者通过主动干扰等手段获取的中间状态比特或故障输出信息等，这些泄露的信息同密码的中间运算、中间状态数据存在一定的相关性，从而为密码分析提供了更多的信息，利用这些泄露的信息就有可能分析出密钥，这种分析方法称为旁路分析。旁路分析密码旁路分析中攻击者除了可在公开信道上截获消息，还可观测加解密端的旁路泄露，然后结合密码算法的设计细节进行密钥分析，避开了分析复杂的密码算法本身，使得一些传统分析方法无法破解的密钥成为可能。旁路分析旁路分析旁路分析旁路分析近几年来，密码旁路分析技术发展较快，出现了多种旁路分析方法。根据旁路泄露信息类型的不同，可分为计时分析、探讨分析、故障分析、功耗分析、电磁分析、Cache分析、声音分析；根据旁路分析方法的不同，可分为简单旁路分析、差分旁路分析、相关旁路分析、模板旁路分析、随机模型旁路分析、互信息旁路分析、Cache旁路分析、差分故障分析、故障灵敏度分析、旁路立方体分析、代数旁路分析、代数故障分析等。密码算法和协议的工程实现分析即使密码体系在理论上无懈可击，在工程实现上也可能千疮百孔，人们近年已经从密码体系固若金汤的错误迷思中清醒过来，越来越多的密码实现层面的漏洞被发现，2016年形成针对密码实现漏洞发掘的高潮。Heartbleed漏洞是密码协议实现时代码层面的问题Poodle攻击是密码协议实现时的兼容性问题Logjam是密码协议实现时的设计问题安卓上的MasterKey漏洞是因上层Java语言与下层C语言语义的不匹配对签名证书校验造成失效的问题2021.8.24：OpenSSL国密SM2爆出8.1分高危漏洞CVE-2021-3711细节：/news/secadv/20210824.txt成因：SM2解密时分配了一块内存，解密后的结果可能大于该分配内存的容量，造成内存越界写。该漏洞影响OpenSSL1.1.1l之前的所有包含SM2商密算法版本。业界一些基于OpenSSL改造过的商用国密算法版本也可能受该漏洞影响密码算法和协议的工程实现分析2022.3.15：OpenSSL拒绝服务漏洞(CVE-2022-0778)

任何使用了OpenSSL中的BN_mod_sqrt()函数的程序，在攻击者可以控制输入的前提下，均受此漏洞影响，易受攻击的场景包括：使用了服务器证书的TLS客户端，使用客户端证书的TLS服务器，从客户那里获取证书或私钥的托管服务提供商，认证机构解析来自订阅者的认证请求，以及任何存在解析ASN.1椭圆曲线参数的功能实现等密码算法和协议的工程实现分析本章小结作业参考内容一、柯克霍夫原则（Kerckhoffs’sPrinciple）Thesystemmustbepractically,ifnotmathematically,indecipherable;Itmustnotberequiredtobesecret,anditmustbeabletofallintothehandsoftheenemywithoutinconvenience;Itskeymustbecommunicableandretainablewithoutthehelpofwrittennotes,andchangeableormodifiableatthewillofthecorrespondents;柯克霍夫原则Itmustbeapplicabletotelegraphiccorrespondence;Itmustbeportable,anditsusageandfunctionmustnotrequiretheconcourseofseveralpeople;Finally,itisnecessary,giventhecircumstancesthatcommanditsapplication,thatthesystembeeasytouse,requiringneithermentalstrainnortheknowledgeofalongseriesofrulestoobserve.柯克霍夫原则用一句话总结：“密码系统的安全性应该仅仅依赖于密钥的安全（thesecurityofacrypto-systemshoulddependsolelyonthesecrecyofthekey）”。柯克霍夫原则香农（Shannon）：敌人了解你的系统柯克霍夫原则随着时代的发展，大家越发意识到柯克霍夫原则的重要性：对复杂的系统中的每一个细节进行保密既非常困难，同时一旦泄密也难以更换。而如果系统安全性仅仅依赖于很短的一串秘密信息，那么不但对其进行保密更为可行，且泄密之后可以用最小代价更新整个系统的安全性。因此，现代密码系统基本上都抛弃了传统的securitythroughobscurity理念，采用了开放式设计，所有系统实现均可公开，更多地把安全性防护集中在对密钥的机密性保护之上。柯克霍夫原则进入计算机时代的密码学应用中，没有哪个加密算法和协议还依赖于人工操作，芯片和内存成为了加密运算的主战场，人们开始逐渐将目光投向了网络和计算机世界中的机密信息保护，关心如何在新时代继续按照柯克霍夫原则来守卫关键系统的安全。可是，信息系统的变化，反过来却引发了一场针对柯克霍夫原则的风暴！柯克霍夫原则2008：普林斯顿大学，后来成为安全研究领域巨星的J.AlexHalderman（/）和NadiaHeninger（/~nadiah/）两位80后研究人员共同完成了一篇USENIXSecurity当年的最佳学生研究论文：利用物理技术冷却被攻击设备的内存，并将其转移到其它系统上读取其中信息：内存中的数据在低温下并不会马上消失，而是“逐渐凋零”柯克霍夫原则NadiaHeninger和HovavShacham很快在2009年的美密会上发表了另一篇论文ReconstructingRSAPrivateKeysfromRandomKeyBits，给出了一个非常具有震撼力的结论——攻击者只需要随机得到内存中RSA私钥27%的部分，就可以有很大的概率完全恢复整个私钥！柯克霍夫原则2014年的Heartbleed事件：仅仅因OpenSSL代码中存在的内存破坏漏洞导致的内存信息泄露，在密码学完全无关的维度上对密钥防护一击致命，可以说是反过来利用了Kerckhoffs'sPrinciple——攻击者只需要窃取数据量微不足道的密钥信息，就可以攻破整个密码系统的安全屏障！柯克霍夫原则Kerckhoffs‘sPrinciple诞生之初，对密钥的安全管理完全是交给人工解决的，可是到了互联网时代，密钥和其它数据一样，都成了CPU和内存中无数需要处理的bit中的普通成员，对这种高度敏感的bit信息的保护远远不够！柯克霍夫原则CCS2018:K-Hunt:PinpointingInsecureCryptographicKeysinExecutionTraces(/publications/ccs18.pdf)柯克霍夫原则需要精确地对程序中和密钥相关的敏感信息进行全面的标记、追踪和防护柯克霍夫原则二、计算上不可行讨论计算上不可行：一个动态变化的概念讨论讨论讨论讨论讨论关于京沪量子通信工程的争论从未停止讨论关于京沪量子通信工程的争论从未停止讨论关于京沪量子通信工程的争论从未停止讨论三、古典密码古典密码体制古典密码大都比较简单，可用手工或机械操作实现加解，现在已很少采用，但很多思想值得借鉴代换密码（SubstituteCipher）换位密码（TranspositionCipher）代换密码代换密码：将明文中字母由另一个或另一组字母替换。单表代换密码：只使用一个密文字母表，并且用密文字母表中的一个字母来代换明文字母表中的一个字母。具有代表性的密码是凯撒密码（JuliusCaesar）。多表代换密码：每次对明文的多个字母进行代换，其优点是容易将字母的自然频度隐蔽或均匀化。采用特定的映射，将明文字母映射为密文字母e.g.例子:

明文：ATTACKATDAWN

密文：XCCXQJXCMXBF单表代换密码（1/2）单表代换密码（2/2）如何破解单表置换密码算法？利用穷举法？非常困难，要尝试的次数：26!=4x1026利用统计法英文中字母出现的频率是已知的可以通过分析字母在文档出现频率来推断明文到密文的转换。例如，在密文中出现最频繁的字母很可能对应于字母‘e’还可以对二元字母组合和三元字母组合进行分析二元字母组合:如‘th’,‘an’,‘ed’三元字母组合:如‘ing’,‘the’,‘est’凯撒密码(1/2)原理：明文中的字母在密文中用该字母循环右移k位后所对应的字母替换，其中k就是密钥。例如，令k=3 ATTACKATDAWN

DWWDFNDWGDZQ凯撒密码(2/2)如何破解凯撒密码算法？利用穷举法位移量k在1到25之间，逐个尝试比普通的单表代换密码的破解要简单换位密码算法换位密码（TranspositionCipher）涉及到对明文字母进行一些位置变换，也称置换密码(Permutationcipher)，例如：将消息“ATTACKATDAWN”写为:ATCADWTAKTAN进一步得到密文ATCADWTAKTAN现代密码算法通常将代换和置换结合在一起使用换位密码算法{1234}3421密钥type4×4矩阵栅栏技术明文：canyoubelieveher问题？没有消除字母的使用频率，容易识别1234canyoubelievehercanyoubelievehernyacbe

u

oeviler

h

e密码位置明文位置

2025/3/18202e=000h=001i=010k=011l=100r=101s=110t=111heilhitler001000010100001010111100000101111101110101111100000101110000110101100001110110111001110101srlhssthsr加密:

明文密钥=密文Plaintext:Key:Ciphertext:Vernam或OTP加密2025/3/18203e=000h=001i=010k=011l=100r=101s=110t=111srlhssthsr110101100001110110111001110101111101110101111100000101110000001000010100001010111100000101heilhitler解密:

密文密钥=明文Ciphertext:Key:Plaintext:Vernam或OTP加密四、分组密码的五种加密模式分组密码的五种模式ECB模式

CBC模式

CFB模式

OFB