应用密码学基础(微课视频版) 课件汇 李晓峰 01信息与安全 -06公钥密码

信息与安全概述什么是信息“信息”一词在英文、法文、德文、西班牙文中均是information”,日文中为“情报”，我国台湾称之为“资讯”，我国古代用的是“消息”。作为科学术语最早出现在哈特莱（R.V.Hartley）于1928年撰写的《信息传输》一文中。20世纪40年代，信息的奠基人香农（C.E.Shannon）

给出了信息的明确定义，许多研究者从各自的研究领域出发，给出了不同的定义。关于信息的描述信息奠基人香农（Shannon）认为“信息是用来消除随机不确定性的东西”，这一定义被人们看作是经典性定义并加以引用。控制论创始人维纳（NorbertWiener）认为“信息是人们在适应外部世界，并使这种适应反作用于外部世界的过程中，同外部世界进行互相交换的内容和名称”，它也被作为经典性定义加以引用。经济管理学家认为“信息是提供决策的有效数据”。电子学家、计算机科学家认为“信息是电子线路中传输的信号”。我国著名的信息学专家钟义信教授认为“信息是事物存在方式或运动状态，是这种方式或状态直接或间接的表述”。美国信息管理专家霍顿（F.W.Horton）给信息下的定义是：“信息是为了满足用户决策的需要而经过加工处理的数据。”简单地说，信息是经过加工的数据，或者说，信息是数据处理的结果。一个例子你看到了什么？你想到了什么？你想告诉大家什么？(你想发送的信息)你怎么告诉大家？(编码和传输)别人收到了什么？(接受编码)别人得到了什么？(解码)别人想到了什么？信息在不同阶段的有着不同的表述形式计算机中的一个例子计算机中的字符字符：中、英、控制字符,字符编码输入编码点阵编码轮廓编码五笔编码拼音编码“时”的五笔编码:jfy计算机中的字符编码“信息”研究的前提如何度量“信息”，这是研究的前提。发展1924Nyquist，CertainFactorsAffectingTelegraphSpeed,1928Nyquist,CertainTopicsinTelegraphTransmissionTheory1928Hartley,TransmissionofInformation1948Shannon，AMathematicsTheoryofCommunication，开创了信息论何为安全可以看出安全是一种状态，是一种“感觉”，这种对“安全的感觉”在不同时期有变化，在不同情境下也有所不同。概括起来有5个安全属性：机密性(Confidentiality)：保护信息不被泄露或暴露给未授权的实体。完整性(Integrity)：保护数据已防止未授权的改变、删除或替代。可认证(Authentication)：提供某个实体（人或系统）的身份的保证。非否认(Non-repudiation)：防止参与某次通信交换的一方事后否认本次交换曾经发生过。访问控制(Accesscontrol)：保护资源以免对其进行非法使用或操纵。如何看待各种资料中提到的各种安全模型BLP、Biba、RBAC等等不同的安全模型，是站在不同的系统和层级视角，根据不同的安全目标，对达到这个安全目标的过程或者方法进行抽象，突出主要矛盾，形成的一个精简且包括核心要素的保护方法描述。何为安全的“密码”柯克霍夫斯原则现代密码系统的基本设计原则是一个德语教授在其《军事密码学》一书中提出，他指出“密码系统的安全性应该仅仅取决于所使用的密钥的机密性，而不是对该方案本身的保密”，这也就是现在被大家广泛接受的“柯克霍夫斯原则”。完全保密(Perfectsecrecy)or香农安全(ShannonSecurity)完全保密系统，通俗来讲，就是当我们获得密文后，对于我们了解明文，没有任何帮助。换句话说，消息M的概率为P(M),在知道密文E的情况下，消息M的概率为P(M|E)，一个完全保密系统就是说对于所有可能的E和M，有P(M)=P(M|E),这个公式的含义也可以说成，消息M的概率与在知道密文E后消息M的概率一样,也可以理解为“保密”意味着密文不给出任何明文或密文的信息。1949CommunicationTheoryofSecrecySystems香农的这篇文章开启了现代密码学文章的中文译稿参见“信息安全经典翻译”开源项目：http://uisu.gitee.io/infsecclat/关于完全保密的数学定义，有很多变种。但是不同定义之间，都可以证明是等价的。完全保密——一次一密一次一密的重要特征是其密钥是一个随机序列，密钥只使用一次，且密钥的长度等于明文序列的长度。一次一密理论上不可攻破的密码系统。也就是说一次一密系统是一种完全保密系统，或者说是完全保密系统的一个一类实现。在历史上AT&T曾经实现过一个一次一密的加密机Vernam，在本资料的扩展阅读部分有此加密机的信息线索，感兴趣的同学可以阅读。完全保密的不现实性一个必要条件：密钥空间不小于明文空间语义安全(SematicSecurity)

相等变为近似近似到什么程度算可以？近似到什么程度？计算困难问题，或者说计算所所需资源大到“结果没有价值”我们只要保证破解是个需要消耗大量资源的事情即可，比如需要投入100万台计算机，运行100年。也就是说，如果破译者在选择最有效的算法前提以下，破解一个密码体制依然需要很大的资源，而这个资源是破译者无法承受的，那么我们称为这个密码体制是计算安全的。计算复杂性理论（Computationalcomplexitytheory）加密的常识性1.不要使用保密的算法。2.使用低强度加密比不进行任何加密更危险，这是因为给使用者错误的安全感。16世纪苏格兰女王玛丽对密码盲信，将刺杀伊丽莎白女王计划写入密信，被送上了断头台就是一个典型的事例。3.任何加密总有一天都会被破解。4.加密只是安全的一部分。一个非常安全的加密系统，我们仍然可以使用其他方法让这个安全的加密系统无效，例如社会工程(socialengineering)的例子，攻击者通过内线电话，打给单位职工，冒充网管，说要进行系统测试，让您修改为指定的密码。密码学的研究内容密码设计密码分析密码测评**密码测评因为具有一些独立的研究内容，作者把其独立出来，在其他资料里未看到这个分法。密码体制常见的密码困难假设(Commoncryptographichardnessassumptions)Integerfactorization(整数分解)RabincryptosystemBlumBlumShubgeneratorOkamoto–UchiyamacryptosystemHofheinz–Kiltz–ShoupcryptosystemRSAproblem(weakerthanfactorization)RSAcryptosystemQuadraticresiduosityproblem(strongerthanfactorization)(二次剩余问题)Goldwasser–MicalicryptosystemDecisionalcompositeresiduosityassumption(strongerthanfactorization)7PailliercryptosystemHigherresiduosityproblem(strongerthanfactorization)BenalohcryptosystemNaccache–SterncryptosystemPhi-hidingassumption(strongerthanfactorization)Cachin–Micali–StadlerPIRDiscretelogproblem(DLP)(离散对数问题)ComputationalDiffie–Hellmanassumption(CDH;strongerthanDLP)Diffie–HellmankeyexchangeDecisionalDiffie–Hellmanassumption(DDH;strongerthanCDH)ElGamalencryptionShortestVectorProblem(最短向量问题)NTRUEncryptNTRUSign密码分析（cryptanalysis）密码分析员对密码系统的攻击分为以下几种[3]：1.密码分析员掌握除了密钥外，密码系统的加密和解密算法.2.仅知密文攻击(ciphertext-onlyattack)，密码分析员能够获得密文.3.已知明文攻击(known-plaintextattack)，密码分析员能够获得某些明文和这些明文对应的密文.4.选择明文攻击(chosen-plaintextattack，简写为CPA)，密码分析员能够有选择地获得明文和这些明文对应的密文.5.选择密文攻击(chosen-ciphertextattack，简写为CCA)，密码分析员可以像合法用户那样发送加密的信息.6.密码分析员可以改变、截取或重新发送信息。按照分析的方法，可以分为：穷举法，字典攻击。数学攻击：统计攻击、差分攻击、线性攻击、代数攻击、相关攻击。物理攻击：侧信道分析(sidechannelattack)和与硬件相关的能量分析、时间分析、声音分析、电磁辐射。通常理论上安全的算法，但由于物理实现上的不足，而使得安全性出现问题，这就对硬件设计、密码芯片设计提出更高要求。谢谢Q&A密码学研究内容研究内容密码设计密码体制密码测评（笔者建议）密码设计就是研究如何设计一种满足“安全目标的”密码系统，包括密码设计的方法学和具体的密码设计。按照不同的分类方法，可以分为公钥密码体制(publickeycryptosystem)和对称密码体制(secretkeycryptosystem/symmetriccryptosystem)。也可以分为流密码（也称序列密码，streamciphers）和分组密码（blockchiphers）等。密码算法设计中的通用要求可逆性(reversible)：这是基本要求，其实就是要求有解密算法的存在。对合性(involution)：这是要求加解密算法中的基础计算部分是可以重用的，这样可以使算法实现的工作量减半，这是从实现角度方面考虑的结果。密码体制基于计算困难问题的密码体制设计我们从香农的讨论中知道，我们可以构造一个完全保密(perfectsecrecy)密码算法，但是这类密码算法的一个要求就是密钥长度和明文一样长，显然这不具有实操性。那么我们是否能把“数学上的安全”降低为“计算安全”，也就是说，我们并不保证“完全安全”，我们只要保证破解是个需要消耗大量资源的事情即可，比如需要投入100万台计算机，运行100年。也就是说，如果破译者在选择最有效的算法前提以下，破解一个密码体制依然需要很大的资源，而这个资源是破译者无法承受的，那么我们称为这个密码体制是计算安全的。常见的密码困难假设Integerfactorization(整数分解)RabincryptosystemBlumBlumShubgeneratorOkamoto–UchiyamacryptosystemHofheinz–Kiltz–ShoupcryptosystemRSAproblem(weakerthanfactorization)RSAcryptosystemQuadraticresiduosityproblem(strongerthanfactorization)(二次剩余问题)Goldwasser–MicalicryptosystemDecisionalcompositeresiduosityassumption(strongerthanfactorization)7PailliercryptosystemHigherresiduosityproblem(strongerthanfactorization)BenalohcryptosystemNaccache–SterncryptosystemPhi-hidingassumption(strongerthanfactorization)Cachin–Micali–StadlerPIRDiscretelogproblem(DLP)(离散对数问题)ComputationalDiffie–Hellmanassumption(CDH;strongerthanDLP)Diffie–HellmankeyexchangeDecisionalDiffie–Hellmanassumption(DDH;strongerthanCDH)ElGamalencryptionShortestVectorProblem(最短向量问题)NTRUEncryptNTRUSign密码分析密码分析（英语：cryptanalysis，来源于希腊语kryptós，即“隐藏”，以及analýein，即“解开”），是一门研究在不知道通常解密所需要的秘密信息的情况下对信息进行解密的学问。通常，这需要寻找一个秘钥。也就是通常我们说的破解密码。对密码系统的攻击（按能力）1.密码分析员掌握除了密钥外，密码系统的加密和解密算法.2.仅知密文攻击(ciphertext-onlyattack)，密码分析员能够获得密文.3.已知明文攻击(known-plaintextattack)，密码分析员能够获得某些明文和这些明文对应的密文.4.选择明文攻击(chosen-plaintextattack，简写为CPA)，密码分析员能够有选择地获得明文和这些明文对应的密文.5.选择密文攻击(chosen-ciphertextattack，简写为CCA)，密码分析员可以像合法用户那样发送加密的信息.6.密码分析员可以改变、截取或重新发送信息。对密码系统的攻击（按方法）穷举法，字典攻击。数学攻击：统计攻击、差分攻击、线性攻击、代数攻击、相关攻击。物理攻击：侧信道分析(sidechannelattack)和与硬件相关的能量分析、时间分析、声音分析、电磁辐射。通常理论上安全的算法，但由于物理实现上的不足，而使得安全性出现问题，这就对硬件设计、密码芯片设计提出更高要求。密码测评如何评价密码算法的安全性，如何评价好坏，有多好，多坏，以及如何评价一个加密算法在产品实现中的安全性，都是系统实现中很重要的问题。密码测评（cipherevaluation）是与密码分析有着很多相同点，但是又不同的概念，特别是随着密码的产业化应用，这种不同越来越重要，并且相互不能等同。概念辨析Evaluationisaprocessintendedforhighlightsomeunconformitiesordeficienciesofacryptosystemwhichcanbeusedbyacracker.TheevaluationofacryptographicmodulecanbydoneusingNISTFIPS140-2standard(structuredonfourthlevels)andtheevaluationofaproductcanbedoneusingCommonCriteria(ISO15408)8,methodologyadoptedbyUSA,CanadaandEU(structuredonseventhlevels).Crackingrepresentsanoperationhelpingtodesignatechnique,methodoralgorithmthatpermittherecoveryofthesystemkeyoroftheplaintexthavingareducedcomplexitythanbruteforceattackmethod:-theevaluatorwantstofindtheminimumquantityofoutputinformationthathelphimtodetermine,usingsomestrongmathematicaltools,aseriesofinformationaboutthecipheralgorithm,usedkeyand/orplaintext;-thecrackerwantstofindthemaximumquantityofinformationthathelphimtodeducetheplaintext.谢谢Q&A古典密码何为“古典”在香农1949年发表“Communicationtheoryofsecrecysystems”之前，密码设计都是通过一些经验和技巧，并没有系统的理论的指导，所以通常将这篇文章之前的设计的密码称为“古典”密码。简单替换密码

(SimpleSubstitutionCipher)换位(固定周期d)

(Transposition(FixedPeriodd))我们用下面一张图来解释加密过程:凯撒密码Caesarcipher例利用凯撒密码对"LIXIAOFENGSHILAOSHI"进行加密。首先需加密的都是大写，我们使用Ascii码对其编码，并且去掉空格，变为"LIXIAOFENGSHILAOSHI",A∼Z的Ascii码为65∼90，所以计算时编码要减去65。移位变换(shifttransformation)/加法密码Vigenère及其变种(VigenèreandVariations)乘法密码仿射变换(affinetransformation)多表代换密码游乐场密码(ThePlayfairCipher)自动密钥密码(AutokeyCipher)谢谢Q&A流密码一次一密是香农安全的但是因为要求“|k|≥|m|”,所以实践起来很“困难”或者说“不实用”。对k的随机性要求是否能降低?“看起来”随机，而不是真“随机”伪随机工程实践我国密码管理局在2021年发布了行业标准GM/T0005-2021随机性检测规范，在规范里对15中随机性检测规范进行了描述。美国国家标准局（NIST）在年也修订发布了随机数和伪随机数测试指南“AStatisticalTestSuiteforRandomandPseudorandomNumberGeneratorsforCryptographicApplications”流密码明文流密钥流密文流运算很简单，重点是如何产生“随机”密钥流线性同余发生器

LCG(linearcongruentialgenerator)可以一下式子产生一个周期不超过m的伪随机数序列，x0为种子(seed)，也就是密钥，这种方法称为线性同余发生器，缩写为LCG。产生的序列是加密明文或解密密文的密钥。LCG不用在密码学中，因其在1977年被J.A.Reeds破译，也就是找到预测的方法，但是其在一些需要产生随机数的场合下依然有应用，比如在一些测试中。线性反馈移位寄存器

LSFR(LinearFeedbackshiftregister)利用线性反馈移位寄存器(LinearFeedbackshiftregister，缩写为LFSR)可以产生一个无限长序列。例子相同初始状态，不同连接方式，周期不同同等数量的寄存器，不同的反馈方法，输出序列的周期不同，那么这就引出一个问题，最长周期是多少？如何能输出最长周期？有限域上的多项式有限域GF(2)元素{0,1}运算：异或（+），与（ⅹ，aⅹb直接写为ab)形成多项式环多项式与序列n个寄存器的LFSR一般性图形化表示LFSR特征多项式

(characteristicpolynomial)GF（2）多项式环的性质LFSR的矩阵表示有时为了计算方便，我们也可以使用矩阵来表示LFSR的时间序列。如果将n位LFSR在初始时刻的状态看为一个n维向量：那么迁移到下一个时刻的状态向量为：根据LFSR反馈函数，我们知：状态迁移矩阵可以表示为：那么序列的运算都可以对应到矩阵运算上，包括破解，已有的大量矩阵的理论和工具我们都可以使用。流密码的应用流密码有很多实际应用，比如用于DVD(DigitalVideodisk)的加密CSS(contentscramblesystem)，有广泛用于汽车的PKE(PassiveKeylessentry)，大家注意，并不是所有PKE使用的都是流加密，PKE有些方案使用的分组加密。还有，蓝牙系统E0加密算法，GSM中的A5加密算法，5G中的ZUC算法等等。谢谢Q&A分组密码

（BlockCipher）分组密码概述分组密码就是将数据序列划分为一定长度的组，然后在密钥的控制下，将数据分组变换为等长数据序列或者组。1949年香浓(C.D.Shannon)在其论文《保密系统的通信理论》中提到密码设计的基本方法，扩散(Diffusion)、混淆(Confusion,也有翻译为“扰乱”或“混乱”)和乘积迭代。这对后来的密码设计影响巨大。Feistel结构当前占绝大多数的对称分组密码都是基于Feistel分组密码结构而设计，Feistel于1973年在ScientificAmerican发表的论文“CryptographyandComputerPrivacy”中，对其Feistel密码(也称为LUCIFER密码)设计思路进行了说明。Feistel结构图Feistel结构有个重要的优点就是加解密运算结构都是相同的，将轮密钥逆序输入算法就可以解密。SPN在AES(Rijndael)、3-Way等一系列分组密码算法中，采用了由Feistel结构发展起来的substitution–permutationnetwork(SPN)。SPN结构通常由一系列的替代（S-boxes）和置换（P-boxes）操作组成。替代操作是一种非线性操作，它通过一个预定义的函数将输入的比特串映射到输出的比特串，这个函数通常是不可逆的，从而增加了密码算法的安全性。置换操作则是对输入的比特串进行重新排列，通过打乱比特的位置来增加数据的扩散性。SPN结构SPN与Feistel的比较SPN结构的优点：快速的扩散速度：SPN结构通过其设计可以实现更快的数据扩散，这意味着密钥和明文的统计特征可以更快地分散到整个密文中，从而提高了密码体制的安全性。高效的运算速度：SPN结构的运算速度较快，因为它只涉及到简单的查找表和排列函数操作。灵活性高：SPN结构可以根据不同的需求进行定制，可以通过替换S盒和P盒来调整算法的安全性和性能，这为密码算法的设计提供了更大的灵活性。SPN结构的缺点：加解密过程不一致：与Feistel结构相比，SPN结构的加密和解密过程通常不一致，这可能导致实现时需要更多的资源和更复杂的电路设计。设计复杂性：SPN结构的设计可能相对复杂，需要精心设计S盒和P盒以确保安全性，这可能增加了设计和分析的难度。Feistel结构的优点：加解密相似性：Feistel结构的加密和解密操作非常相似，这使得实现这种密码所需的代码或电路大小能几乎减半，从而节省了资源。易于分析：如果Feistel算法能被无疑义地解释清楚，那么就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。Feistel结构的缺点：扩散速度较慢：Feistel结构相较于SPN结构，扩散速度较慢，通常需要更多的轮数来达到相同的安全级别。轮函数的局限性：Feistel结构的轮函数不必是可逆的，这可能限制了某些密码分析技术的应用，但同时也可能导致安全性的降低。DESDES是DataEncryptionStandard的缩写，中文翻译为“数据加密标准”，其明文分组长度为64比特，密钥长为56比特（加校验位也是64比特），密文长度64比特。DES结构图IP和IP-1f函数E扩展S盒P密钥生成DES初始密钥K是一个64位的二进制块，其中有8位奇偶校验位，对DES的64比特初始密钥进行“置换选择1(PC-1)”有两个作用：一是将分别位于8、16、24、32、40、48、56、64的校验位去掉。二是对剩余56比特进行换位。DES密钥生成LSi𝐷i和𝐸i是将换位后的56比特密钥分为两半，各为28比特。LSi是循环左移，循环左移几位，由下表来定义。DES解密填充PKCS5Padding加密时，先把数据字节长度对8取余，余数为m，若m>0,则补足8-m个字节，字节数值为8-m，即差几个字节就补几个字节，字节数值即为补充的字节数，若为0则补充8个字节的8。解密后时，取最后一个字节，值为m，则从数据尾部删除m个字节，剩余数据即为加密前的原文。运行模式ECBCBCCFBCTRZUC简介ZUC密码算法是我国自主研发的一种流密码算法，用于提供数据的加密与解密安全保护。其设计初衷是为了在3G和4G移动通信中保护用户信息的安全性。ZUC算法采用了流密码算法的设计思想，并具有比较高的安全性和效率。ZUC算法的核心是一个LFSR（线性反馈移位寄存器）和一个非线性置换运算，结合两者的运算来生成伪随机数流，进而实现数据的加密和解密。ZUC算法的关键参数有128位的密钥和128位的初始向量，通过这些参数来确定密钥流和明文流之间的关系，从而对数据进行加密和解密操作。总的来说，ZUC密码算法在保护通信安全方面具有一定的优势。ZUC结构谢谢Q&A公钥密码公钥密码体制1976年W.Diffie和N.E.Hellman发表了著名的文章“NewDirectionsinCryptography”，奠定了公钥密码的基础，与传统的密码系统不同的是不需要额外分发密钥的可信信道，加密密钥和解密密钥是本质上不同的，知道一个密钥不能有效地计算出来另外一个。传统密码系统与公钥密码系统最大的不同是，不要一个保密信道来传输大家共同使用的密钥，这个保密信道的构建在互联网环境下，通常很难构建，或者构建成本极高。传统加密体系和公钥加密体系框图的对比陷门单向函数公钥密码体系的思想很好理解，但是要构造这样一个体系，并且能够抵抗住密码分析者的攻击却不是一件容易的事情，要求密码分析者从公开的各种信息中无法获得密钥信息和有效的解