信息安全学第2章 信息安全核心：密码技术

海军工程大学主要内容2.1密码的起源和相关概念2.2古典密码体制2.3对称密码体制2.4非对称密码体制2.5小结2.1密码的起源和相关概念2.1.1密码的起源密码的起源，尚无确实可靠的资料。目前公认的是公元前五世纪斯巴达人使用一种叫“天书〞〔Skytale〕的器械。它用一根木棍，将羊皮条紧紧缠在木棒上，密信自上而下写在羊皮条上，然后将羊皮条解开送出。除非把羊皮条重新缠在一根同样直径的木棍上，才能把密信的内容读出来。这是最早的一种移位密码。2.1密码的起源和相关概念2.1密码的起源和相关概念2.1密码的起源和相关概念2.1密码的起源和相关概念今后密码装置和密码通信的特点是：体积向微型化方向开展，速度向更高方向开展，操作向全自动化方向开展，编码向程序化方向开展，密钥量向无穷方向开展，加解密向后台化方向开展，通信向网络化方向开展，所有操作向实时化方向开展。2.1密码的起源和相关概念2.1.2密码学相关概念密码学〔Cryptology〕:是一门关于发现、认识、掌握和利用密码内在规律的科学，由密码编码学和密码分析学组成。密码编码学〔Cryptography〕:是研究密码编码的科学。密码分析学〔Cryptanalytic〕:是研究密码破译的科学。2.1密码的起源和相关概念明文〔消息〕〔Plaintext〕:原始数据/信息密文〔Ciphertext〕:经过变换的数据加密〔Encryption〕:变换过程解密〔Decryption〕:实施与加密变换相反的变换密钥〔Key〕:加密和解密通常都是在一组密钥控制下进行，分别称为加密密钥和解密密钥2.1密码的起源和相关概念2.1密码的起源和相关概念被动攻击〔PassiveAttack〕:对一个密码通信系统采取截获密文进行分析的攻击

主动攻击〔ActiveAttack〕:攻击者采用删除、增加、重放、伪造等主动手段向密码通信系统注入假消息的攻击2.1密码的起源和相关概念一个密码系统，通常简称为密码体制〔Cryptosystem〕传统密码体制〔ConventionalCryptographicSystem〕所用的加密密钥和解密密钥相同，或实质上等同，即从一个密钥易于推出另一个，我们称其为单钥或对称密码体制〔One-keyorSymmetricCryptosystem〕。如果加密密钥与解密密钥不相同，即从一个难以推出另一个，那么称该密码体制为双钥密码体制〔Two-keyCryptosystem〕或非对称密码体制〔AsymmetricCryptosystem〕。2.1密码的起源和相关概念密码体制〔Cryptosystem〕，由五元组〔M,C,K,E,D〕构成:明文空间M，它是全体明文的集合;密文空间C，它是全体密文的集合；2.1密码的起源和相关概念密钥空间K，它是全体密钥的集合,其中每一个密钥K均由加密密钥Ke和解密密钥Kd组成，即有K=<Ke,Kd>;加密算法E，它是一簇由M到C的加密变换，即有C=E(M,Ke);解密算法D，它是一簇由C到M的解密变换，即有M=D(C,Kd)=D(E(M,Ke),Kd)2.1密码的起源和相关概念由五元组〔M,C,K,E,D〕构成密码体制模型如图

2.1密码的起源和相关概念根据对明密文的处理方式和密钥的使用不同，可将密码体制分为分组密码〔BlockCipher〕体制和序列密码〔Streamcipher〕体制。2.1密码的起源和相关概念

密码分析者攻击密码的方法主要有穷举攻击、统计分析攻击和数学分析攻击。2.1密码的起源和相关概念穷举攻击〔Exhaustiveattack〕，是指密码分析者采用遍历〔ergodic〕全部密钥空间的方式对所获密文进行解密，直到获得正确的明文；统计分析攻击〔Statisticalanalysisattack〕，是指密码分析者通过分析密文和明文的统计规律来破译密码；数学分析攻击〔Mathematicalanalysisattack〕，是指密码分析者针对加解密算法的数学根底和某些密码学特性，通过数学求解的方法来破译密码2.1密码的起源和相关概念根据可利用的数据资源来分类，密码分析者破译密码的类型可分为仅知密文攻击、明文攻击、选择明文攻击和选择密文攻击。

2.1密码的起源和相关概念

仅知密文攻击〔Ciphertext-onlyattack〕是指密码分析者仅根据截获的密文来破译密码。这是密码分析者在拥有最少可利用数据资源的情况下最强的密码攻击。明文攻击〔Known/plaintextattack〕是指密码分析者根据已经获得的某些明文-密文对来破译密码。近代密码学要求，一个密码仅当它能经得起明文攻击时才是可行的。

2.1密码的起源和相关概念

选择明文攻击〔Chosen-plaintextattack〕是指密码分析者能够选择明文并获得相应的密文。这种状态对密码分析者十分有利。选择密文攻击〔Chosen-ciphertextattack〕是指密码分析者能够选择密文并获得相应的明文。这种攻击主要针对公开密钥密码体制，尤其是攻击数字签名。2.1密码的起源和相关概念2.1密码的起源和相关概念一个密码不能被密码分析者根据可利用的资源所破译，称为计算上不可破译〔Computationallyunbreakable〕密码。对于我们来说，计算上不可破译的密码才是常见的和可实现的。2.2古典密码体制2.2古典密码体制2.2.1代替密码代替密码〔Substitutioncipher〕就是发送者将明文中每一个字符替换为密文中的另外一个字符，然后使用通信手段发送出去。接收者对密文进行逆替换以恢复出明文的过程

2.2古典密码体制

根据保密性能，我们归纳经典代替密码有以下三种类型：单表代替密码、多表代替密码和一次一密钥代替密码。2.2古典密码体制1.单表代替密码单表代替密码〔Monoalphabeticsubstitutioncipher〕：就是所有的明文字母，都用一个固定的代替表进行加密。

2.2古典密码体制

单表代替密码的特点是：代替表固定不变，重复使用，因此存在明文相同时，密文必相同；明文相异时，密文必相异的规律，我们称为明密异同规律。运用该规律，结合文字中字母出现的不平衡性和跟随性，易于找到代替表的明密字母对应关系。因此，单表代替密码是一种低级的代替密码。2.2古典密码体制构造单表代替的方法有以下几种：(1)混字法，就是简单代替密码(simplesubstitutioncipher)，将记有字母表中每个字母的卡片打乱秩序后重新排列，并与明文字母相对应，可构成一张单表代替表(2)移位法，就是移位代替密码〔Shiftsubstitutioncipher〕，就是将明文字母表字母循环左移k位，构成密文字母表2.2古典密码体制(3)乘法密码〔Multiplicativecipher〕又称为采样密码〔Decimationcipher〕，因为密文字母表是将明文字母表按下标每隔k位取出一个字母排列而成〔字母表首尾相接〕。(4)仿射密码，将移位密码与乘法密码组合可得到更多的选择方式或密钥。(5)多字符代替密码，如果每次对L>1个字母进行代替就是多字符代替密码〔Polygramsubstitutioncipher〕，该密码由Playfair在1854年创造。2.2古典密码体制2.多表代替密码多表代替密码〔Polyalphabeticsubstitutioncipher〕是以一系列〔两个以上〕代替表依次对明文消息的字母进行代替的加密方法。设T是从A到A上的所有一一映射构成的变换集合，是由k∈K确定的一个至少由T中的两个不同元素组成的变换序列，，对于明文加密编码为

解密译码为那么称这种密码系统是多表代替密码。2.2古典密码体制经典的多表代替密码有：Vigenère、Beaufort、Running-Key、Vernam和转轮密码〔RotorCipher〕等。2.2古典密码体制(1)Vigenère密码Vigenère密码是法国密码学家BlaisedeVigenère于1858年提出的，它是一种以移位代替〔当然也可用一般的字母代替表〕为根底的周期代替密码。假设，对，，其中的定义同代替密码，那么由确定的密码就是Vigenère密码。2.2古典密码体制例2.4

令q=26，m=polyalphabeticcipher，密钥字k=about，即周期d=5，求密文c。2.2古典密码体制解：

加密密钥：k=about=(0,1,14,20,19)加密算法：加密代替表参见表密文为：ppzstlqvuueuwwviqvyk由密文可知，同一明文字母p在不同位置被加密为不同的密文字母p和q。2.2古典密码体制(2)Beaufort密码Beaufort密码是按modq减法运算的一种周期代替密码，即：

所以，它与Vigenère密码相似，只是密文字母表为英文字母表逆序排列进行循环右移次而成。

2.2古典密码体制(3)Vernam密码当字母表字母数q=2时，滚动密钥密码就变成Vernam密码，它是美国电报公司的G.W.Vernam在1917年创造的。它将英文字母编成5bit二元数字，称之为五单元波多码〔BaudotCode〕。2.2古典密码体制选择随机二元序列作为密钥，用表示。明文字母变换成二元码后也可表示成二元序列加密运算就是将k和m的相应位逐位相加，即i=1,2,…解密运算就是将密文序列与密钥序列逐位模2加，即i=1,2,…2.2古典密码体制(4)转轮密码转轮密码是用一组转轮或接线编码轮〔WiredCodeWheel〕所组成的机器，用以实现长周期的多表代替密码。它是机械密码时代的最杰出的成果，曾广泛应用于军事通信中。

2.2古典密码体制2.2古典密码体制3.一次一密钥系统2.2古典密码体制对任意正整数N，假设是一个独立同分布的随机变量序列，且在上取值并服从均匀分布，即

对明文，由确定的加密过程为其中，i=0，1，…，N-1，那么此密码系统就是著名的一次一密钥系统。。对于明文2.2古典密码体制

置换密码〔Permutationcipher〕，就是按照约定的规那么，将明的字母、数码或符号在不改变原来形状的根底上，进行位置的错乱。有时也称为换位密码〔Transpositioncipher〕。2.2.2置换密码，。对于明文2.2古典密码体制

置换密码表述如下：设k是上的一个置换，称是由k导出的上的一个换位变换，假设对，。对于明文，由加密编码所确定的密码称为换位密码。2.2古典密码体制例2.5应用简单图形置换密码加密以下明文：435725850031503047374377242924942.2古典密码体制解：简单图形置换密码的变化因素是：图形的选择，方格的数量，以及变化的线路。下面我们采用横填纵读法进行加密，即横向填写明文，纵向读出来为密文。参见表43572585003150304737437724292494密文：485329350744503427003923472517742.2古典密码体制例2.6对以下明文用置换密码加密：Transpositionisthesimplestcipher.2.2古典密码体制解：将明文长度分为L=5，最后一段缺乏5那么加字母x。将各段位置下标按下述置换表：进行置换，得到密文如下：Ntsariptsoiisnostiehemslppthicxexxr2.2古典密码体制利用下述代替表：可将密文解密。L=5时可能的代替表总数为5！=120。可以证明，在给定L下，所有可能的置换构成一个L！阶对称群

2.2古典密码体制

2.3对称密码体制

对称密码体制是指所用的解密算法就是加密算法的逆运算，加密密钥就是解密密钥这样一类加密体制。它通常用来加密带有大量数据的报文和文卷通信的信息，因为这两种通信可实现高速加密算法。

2.3对称密码体制

该体制的特点是：在秘密密钥密码体制中发送者和接收者之间的密钥必须平安传送，而双方用户通信所用的秘密密钥必须妥善保管。

2.3对称密码体制

该体制代表包括美国的数据加密标准(DataEncryptionStandard，DES[DES，1977])以及瑞士的国际数据加密算法(InternationalDataEncryptionAlgorithm，IDEA[Lai，1990])等。2.3对称密码体制

2.3.1DESDES是美国国家标准局在20世纪70年代开发的一种新型加密算法。1977年1月15日，DES成为美国联邦信息处理标准FIPSPUB46。DES采用分组乘积密码体制，就是使用屡次移位和代替的混合运算编制的密码。DES是世界上最早公认的实用密码算法标准。

2.3对称密码体制根据FIPSPUB81定义，DES的工作模式有四种：电子密码本〔ECB〕、密码分组链接〔CBC〕、输出反响〔OFB〕和密文反响〔CFB〕。ANSI银行标准中规定加密用ECB和CBC方式，鉴别用CBC和n-位的CFB方式。2.3对称密码体制

1.DES的加密原理DES是一种二元数据加密的分组算法，即对64位二进制数据加密，产生64位密文数据，使用密钥为64位，实用56位，另外8位用作奇偶校验。加密的过程是先对64位明文分组进行初始置换，然后分成左、右两部份，经过16次迭代，进行循环移位与变换，最后再进行逆变换得出密文。加密与解密使用相同的密钥，因而属于对称密码体制。2.3对称密码体制

(1)DES的初始置换IP与初始置换的逆置换初始置换作用是对输入进行预白化，到达消除明文的格式和固定输入作用。逆初始置换作用是对输出进行后白化，到达消除密文格式和可能的密钥泄露。白化，就是对输入进行白噪声化处理，即高斯化处理，使得结果呈现白噪声特征。对输入进行白化叫做预白化，对输出进行白化叫做后白化。2.3对称密码体制要加密的输入块的64位，首先要经过初始置换IP的作用。即置换了的输入要把原输入的第58位作为它的第1位，原输入的第50位作为它的第2位，……，原输入的第7位作为它的最后一位。逆初始置换，是以预输出作为它的输入,参见表2.3对称密码体制

(2)密码函数密码函数的运算见图所示，它是DES密码的关键部件，它包含四种密码功能：扩展函数、模2加运算、S盒运算和置换函数P运算。2.3对称密码体制①扩展函数E扩展函数E的功能，就是将一个32位的输入块，扩展为48位的输出块。这48位的输出块分成8个6位的块，它是按照下表依次选择它的输入中的位取得的2.3对称密码体制②模2加运算

模2加功能是将E(R)的各位与密钥K各位逐位模2加，得到输出，具体如下：

2.3对称密码体制

③S盒运算密码函数中，共有8个S盒，称为8个不同的选择函数，分别用表示，见下表。每个S盒，都是将6位作为输入，得到一个4位块作为输出。2.3对称密码体制④置换函数P运算置换函数P把S盒输出的32位数据打乱重排，得到32位的加密函数结果。置换函数P与S盒互相配合提高了DES的平安性。这种函数由下表给出。16720212912281711523265183110282414322739191330622114252.3对称密码体制具体加密过程是：输入的明文64位数据，首先经过初始置换IP后把其左半1至32位记为，右半33至64位记为，即成了置换了的输入，然后把与密钥发生器产生的密钥进行运算，其结果记为，再与进行模2加得，把记为放在左边，把记为放在右边，从而完成第一次迭代运算；在此根底上，重复上述迭代过程，一直迭代至第16次，所得的第16次迭代结果左右不交换，即记为放在左边，记为放在右边，成为预输出，最后经过初始置换的逆置换运算后即得密文。2.3对称密码体制

综上所述，DES加密过程可用如下的数学公式描述：2.3对称密码体制3.DES的应用与意义DES已经使用了二十多年，由于DES存在每五年评估一次的要求，经过1982年、1987年、1993年三次评估，DES的使用已经面临较严峻的问题，先后遭到密码理论分析、密码硬件破译、网络资源攻击〔DESCHALL〕以及DES专用破译机攻击。2.3对称密码体制2.3对称密码体制2.3对称密码体制2.3.2IDEA1.IDEA概述

IDEA(InternationalDataEncryptionAlgorithm)是由中国密码学者来学嘉(XuejiaLai)于1990年在瑞士苏黎士联邦工业大学学习期间和JamesL.Massey共同提出的，并于1992年正式使用IDEA名称。

2.3对称密码体制该算法在形式上与DES类似，也是使用循环加密方式，把64位的明文加密成64位的密文，或反之。所不同的是，IDEA使用128位的密钥，强度高于DES；加密和解密时使用的密钥不一样(但从同一个密钥派生出来，所以仍属于对称密码体制)；而且IDEA的设计倾向软件实现。到目前为止，从公开发表的文献看，除穷举法外，尚未找到破译IDEA方法。2.3对称密码体制2.IDEA根本运算IDEA的根本操作是将两个16位的值映射成一个16位的值，这些操作是：〔1〕半加⊕；〔2〕模216的加法+；〔3〕修改正以适应范围的乘法×；先计算32位的结果，然后用216+1取余。IDEA的根本运算可表示为：2.3对称密码体制3.IDEA工作原理IDEA的根本工作原理如以以下图所示2.3对称密码体制IDEA的加密过程包含17个循环，其中奇数循环使用4个密钥，而偶数循环使用2个密钥，它们在处理方法上也不一样。为了验证IDEA的加密和解密过程，可作如下变换：将新的、、和作为这个循环的输入，便可得到旧的、、和的值。因此，IDEA的加密和解密可理解为是对不同的值使用同一个处理过程。2.3对称密码体制4.IDEA加密过程64位数据分组被分成4个16位子分组：x1、x2、x3和x4。这4个子分组成为算法的第一轮的输入。总共有8轮。在每一轮中，这4个子分组相互间相异或，相加，相乘，且与6个16位子密钥相异或，相加，相乘。在轮与轮间，第二和第三个子分组交换。最后在输出变换中4个子分组与4个子密钥进行运算。2.3对称密码体制2.3.3高级加密标准AES1997年起，美国NIST在全球范围内组织了旨在代替DES的先进加密标准〔AdvancedEncryptionStandard，AES〕评估工作，2000年10月终于诞生了AES。最终推荐的高级加密标准AES是由比利时密码专家JoanDaemen和VincentRijmen提出的Rijndael〔中文音译“荣代尔〞〕加解密算法，2001年11月26日，美国NIST正式应用AES作为美国FIPSPUB197。2.3对称密码体制1.Rijndael数学根底定义2.1一个由组成的字节b可表示为系数为{0，1}的二进制多项式：

定义2.2在上的加法定义为二进制多项式的加法，且其系数模2。定义2.3在上的乘法〔用符号·表示〕定义为二进制多项式的乘积模一个次数为8的不可约二进制多项式，此不可约多项式为〔十六进制为‘11B’〕

上面定义的乘法在上满足结合律，且有一个本原元〔‘01’〕。2.3对称密码体制定义2.4在上的二进制多项式b(x)的乘法逆为满足方程式的二进制多项式a(x)，记为定义2.5函数xtime(x)定义为上的x·b(x)。其运算如下：x·b(x)的结果就是把字节b左移一位；假设那么结果需异或‘1B’。定义2.6有限域上的多项式是系数取自元素的多项式，这样，一个4字节向量与一个次数小于4的多项式相对应。定义2.7上的多项式的加法定义为相应项系数相加。因为在域上的加是简单的按位异或，所以在域上的两向量的加也就是简单的按位异或。2.3对称密码体制定义2.8上的多项式和相乘模的积〔表示为〕为，其系数由下面4个式子得到：，，，，利用定义(2.8)有。2.3对称密码体制2.Rijndael加密算法

Rijndael算法是一个可变数据块长和可变密钥长的迭代分组加密算法，数据块长和密钥长可分别为128、192或256比特。2.3对称密码体制(1)状态、密钥和圈数数据块要经过屡次数据变换操作，每一次变换操作产生一个中间结果，这个中间结果叫状态。状态可表示为二维字节数组，它有4行，Nb列，且Nb等于数据块长度除以32。如表所示。2.3对称密码体制密钥也可类似地表示为二维字节数组，它有4行，Nk列，且Nk等于密钥块长除32。算法变换的圈数Nr由Nb和Nk共同决定，具体值列在表中2.3对称密码体制(2)圈变换加密算法的圈变换由4个不同的变换组成。用伪C语言可写为：Round(State，RoundKey){ByteSub(State)；ShiftRow(State)；MixColumn(State)；AddRoundKey(State，RoundKey)；}加密算法的最后一圈变换与上面的略有不同，定义如下：FinalRound(State，RoundKey){ByteSub(State)；ShiftRow(State)；AddRoundKey(State，RoundKey)；}2.3对称密码体制字节代替〔ByteSub〕变换ByteSub变换是作用在状态中每个字节上的一种非线性字节变换。这个变换表〔或称S-box〕是可逆的且由以下两局部组成：1)把字节的值用它的乘法逆代替，其中‘00’的逆就是它自己。2)经上一步处理后的字节值进行如下定义的仿射变换：2.3对称密码体制行移位〔ShiftRow〕变换在ShiftRow变换中，状态的后3行以不同的移位值循环右移。行1移C1字节，行2移C2字节，行3移C3字节。移位值C1，C2和C3与加密块长Nb有关，具体列在表中按指定位移量进行循环移位的状态行移位运算记为：ShiftRow〔State〕2.3对称密码体制列混合〔MixColumn〕变换在MixColumn变换中，把状态中的每一列看作上的多项式与一固定多项式c(x)相乘然后模多项式，其中c(x)为：

上述多项式与互素，因此是可逆的。这一乘法可写成矩阵乘法。令我们有：

2.3对称密码体制这一运算在状态的所有列上的变换记为：MixColumn(State)。MixColumn变换的逆变换与其类似，每列用一个特定的多项式相乘就得到变换了。定义如下：由此给出：

2.3对称密码体制圈密钥加法

在这个操作中，圈密钥被简单地使用异或操作按位应用到状态中，圈密钥根据密钥编制通过密钥得到。圈密钥长等于数据块长。2.3对称密码体制(3)密钥编制圈密钥根据密钥编制得到。密钥编制包括密钥扩展和圈密钥选择，遵循以下原那么：●圈密钥的比特总数为数据长度与圈数加1的积。●密钥编制为扩展密钥。●圈密钥通过如下方法由扩展密钥求得：第一个圈密钥由前面的个字组成，第二个圈密钥由接下来的个字组成，以此类推。2.3对称密码体制密钥扩展

扩展密钥是一个4字节的数组，且记为。密钥包含在开始的个字中，其它的字由它前面的字经过处理后得到。有小于等于6和大于6两种密钥编制。2.3对称密码体制圈密钥选择圈密钥i由圈密钥缓冲区到的字组成。见表Nb=6且Nk=4的密钥扩展与圈密钥选取2.3对称密码体制(4)加密算法Rijndael加密算法由以下局部组成：●一个初始化了的圈密钥加法。●Nr－1圈变换。●最后一圈变换。2.3对称密码体制用伪码表示有：Rijndael(State，CipherKey){KeyExpansion(CipherKey，ExpandKey)；AddRoundKey(State，ExpandKey)；For(i=1；i<Nr；i++)Round(State，ExpandedKey+Nb﹡i)；FinalRound(State，ExpandedKey+Nb﹡Nr)；}密钥扩展可以事先进行，且Rijndael密码可以用这一扩展密钥来进行描述：Rijndael(State，ExpandKey){AddRoundKey(State，ExpandKey)；For(i=1；i<Nr；i++)Round(State，ExpandedKey+Nb﹡i)；FinalRound(State，ExpandedKey+Nb﹡Nr)；}2.3对称密码体制3.Rijndael解密算法

Rijndael解密算法的结构与Rijndael加密算法的结构相同，其中的变换为加密算法变换的逆变换，且使用了一个稍有改变的密钥编制。2.3对称密码体制(1)变换的逆变换ShiftRow的逆是状态的后3行分别移动个字节、个字节、个字节。ByteSub的逆是Rijndael的S-box的逆作用到状态的每个字节。MixColumn的逆类似于MixColumn，状态的每列都乘以一个固定的多项式：AddRoundKey就是它自己的逆。2.3对称密码体制(2)逆圈变换的定义逆圈变换的定义如下：I-Round(State，I-RoundKey){InvByteSub(State)；InvShiftRow(State)；InvMixColumn(State)；AddRoundKey(State，I-RoundKey)；}最后一圈的逆变换如下：I-FinalRound(State，I-RoundKey){InvByteSub(State)；InvShiftRow(State)；AddRoundKey(State，I-RoundKey)；}2.3对称密码体制(3)解密算法现在解密算法可以表述如下：I-Rijndael(State，CipherKey){I-KeyExpansion(CipherKey，I-ExpandKey)；AddRoundKey(State，I-ExpandKey+Nb﹡Nr)；For(i=1；i<Nr；i++)I-Round(State，I-ExpandedKey+Nb﹡i)；I-FinalRound(State，I-ExpandedKey)；}2.3对称密码体制其中解密算法的密钥扩展定义为：加密算法的密钥扩展；把InvMixColumn应用到除第一和最后一圈外的所有圈密钥上。用伪C码表示如下：I-KeyExpansion(CipherKey，I-ExpandKey){Key-Expansion(CipherKey，I-ExpandKey)；For(i=1；i<Nr；i++)InvMixColumn(I-ExpandedKey+Nb﹡i)；}2.4非对称密码体制2.4.1引言传统的密码系统所存在的缺点，主要表现为下面两点：主要存在两个缺点：一是密钥管理和分配问题；二是认证问题。1976年，Diffie和Hellman发表了“NewDirectionsinCryptography〞[Diffie，1976]，提供了一个新的思想，即密码系统的加密密钥、解密密钥是可以不同的，由加密密钥和密文不能容易地求得解密密钥或明文，从而可以公开这种系统的加密算法和加密密钥可以公开，系统保密平安性完全依赖于秘密的解密密钥。2.4非对称密码体制2.4.2公开钥密码的根本思想

公开钥密码系统的每个用户Ｕ选择一对密钥k、k′，分别称为公开钥和秘密钥，并构造出他自己的加密算法Ｅk和解密算法Ｄk′，Ｅk和Ｄk′应使得对每个可能的明文m成立：2.4非对称密码体制每个用户将他的加密密钥和加密算法公开，可以象号码薄一样公开让其他用户查找，而解密密钥那么由用户自己保密管理。如果用户Ａ要给用户Ｂ传送秘密信息m，Ａ首先从公开密钥本上查到Ｂ的公开钥，形成Ｂ的加密算法EB，用EB对明文m加密编码得密文公开钥，形成Ｂ的加密算法EB，用EB对明文m加密编码得密文：2.4非对称密码体制

并将c发送给Ｂ。Ｂ接收到密文后，用自己的秘密密钥确定的解密算法DB来恢复明文：

这就是一般的公开钥密码系统的加密、解密过程。2.4非对称密码体制一个公开钥密码系统满足前面的三个要求对平安性来说还不充分。Diffie曾建议使用单向陷门函数来作加密算法。定义定义在中取值的函数f称为一个单向函数，假设它满足：●对每个x∈，计算y=f(x)是容易的；●方程y=f(x)在中有解，但由y计算出x是困难的。2.4非对称密码体制单向陷门函数f是有一个秘密陷门的一类特殊的单向函数。它在一个方向上易于计算而反方向却存在计算是困难的。如果掌握了那个秘密，那么容易在另一个方向上计算出这个函数。组装一台计算机对于普通人来说就是单向陷门函数，对于专业人员来说那么是容易的。2.4非对称密码体制2.4.3几个典型的公开钥密码系统Diffie和Hellman在提出公开钥密码系统的崭新概念时，自己还未能解决实现这种系统的具体方法，但他们的思想很快导致了RSA和背包公开钥密码系统的诞生。三十多年来公开钥密码系统开展很快，不断地有新的或修改的公开钥密码系统提出，同时也有很多系统被破译。下面介绍几个有代表性的公开钥密码系统。2.4非对称密码体制1.RSA系统RSA系统是美国麻省理工学院〔MIT〕RonRivest、AdiShamir和LeonardAdleman于1978年提出的[RSA，1978]，它是第一个成熟的、迄今为止理论上最成功的公开钥密码系统。它的平安性根底是数论和计算复杂性理论中的下述论断：求两个大素数的乘积是计算上容易的，但要分解两个大素数的积求出它的素因子那么是计算上困难的，它属于NPI类。2.4非对称密码体制★RSA系统的构造是选择两个大素数p、q，计算n=pq，，其中为欧拉函数，并选择一个整数e，它满足，并求出满足：的整数d，这只要用欧几里德算法通过次运算就可求出d。那么RSA系统的公开钥为，秘密钥为，明文消息m满足，加密过程为解密过程为2.4非对称密码体制例2.8

使用RSA算法计算：如果p=11，q=17，选取e=7，求解密密钥d。假设令明文为m=5，求密文c。验证加解密的正确性。2.4非对称密码体制解：p=11，q=17，那么n=pq=187加密密钥e=7，与互素，那么，通过扩展的欧几里德算法〔参见节〕，可以求得解密密钥公开e和n，将d作为私钥保密，舍弃p和q。当m=5，那么加密为验证解密正确性所以，使用RSA可以正确进行公开密钥加解密。2.4非对称密码体制2.背包系统背包系统是第一个公开密钥加密算法。它由RalphMerkle和MartinHellman于1978年基于求解背包问题的难解性提出，它只能用于加密，后来，Shamir将它改进使之也能用于数字签名。背包算法的平安性起源于背包问题，它是一个NP完全问题。尽管该算法后来发现是不平安的，但由于它证明了如何将NP完全问题用于公开密钥密码学，所以背包问题值得进行学习。2.4非对称密码体制背包问题描述如下：给定一堆物品，每个重量不同，能否将这些物品中的几件放入一个背包中使