第2章-密码学基础知识

2.1密码学的基本概念

2.2对称密码算法

2.3公钥密码算法第2章密码学基础知识2.1密码学的基本概念

密码学是一个非常庞大而复杂的信息处理系统，涉及信息的机密性、完整性、认证性、不可否认性等许多方面。密码学中加密和解密信息的主要目的是使得授权人员以外的人无法读取信息。

被加密的消息称为明文，明文经过加密变换成为另一种形式，称为密文。对明文进行加密操作时所采用的一组规则称为加密算法，对密文进行解密操作时所采用的一组规则称为解密算法。加密算法和解密算法都依赖于一组秘密参数，分别称为加密密钥和解密密钥。加密算法和解密算法统称为密码算法。

2.1.1保密通信模型2.1.2密码算法分类2.1.3古典密码简介2.1.4密码算法的安全性2.1密码学的基本概念2.1.1保密通信模型

在不安全的信道上实现安全的通信是密码学研究的基本问题。消息发送者对需要传送的消息进行数学变换处理，然后可以在不安全的信道上进行传输，接收者在接收端通过相应的数学变换处理可以得到信息的正确内容，而信道上的消息截获者，虽然可能截获到数学变换后的消息，但无法得到消息本身。图2-1展示了一个最基本的保密通信模型。2.1.2密码算法分类密码算法是否能进行可逆的加密变换对明文信息的处理方式不同按照密钥的使用策略的不同单向函数密码算法双向函数密码算法序列密码算法分组密码算法对称密码算法非对称密码算法2.1.3古典密码简介密码学的发展历史大致分为三个阶段：古典密码时期、近代密码时期和现代密码时期。古典密码历史悠久，主要分为替换密码和换位密码两种。替换密码，即明文中每一个字符被替换成密文中的另外一个字符。换位密码也称为置换密码，即明文的字母保持不变，但打乱其顺序。我们将举例介绍两种典型的古典密码：凯撒密码置换密码2.1.3古典密码简介凯撒密码基本思想是：通过把字母移动一定的位数来实现加密和解密比如，Alice要将明文“mobileinternetsecurity”加密成密文，传送给Bob。为了运算方便，先把字母进行数字化。图2-2展示了字母与数字的映射关系。2.1.3古典密码简介加密过程如下：Alice先将明文“mobileinternetsecurity”中的字母根据图2-2的映射关系转换为数字：（12，14，1，8，11，4，8，13，19，4，17，13，4，19，18，4，2，20，17，8，19，24）。加密之前，双方需要协商一个密钥。于是Alice与Bob商定加密方式为明文字母后移6位，即加密密钥及解密密钥同为K=6。开始加密：将明文字母映射得到的数字代入加密函数E(m)=m+6（mod26）中计算得到：（18，20，7，14，17，10，14，19，25，10，23，19，10，25，24，10，8，0，23，14，25，4），然后把这些数字根据图2-2的映射关系替换成字母即可得到密文“s，u，h，o，r，k，o，t，z，k，x，t，k，z，y，k，i，a，x，o，z，e”。这就是加密后的结果。2.1.3古典密码简介解密过程如下：解密其实就是上述加密过程的逆过程：Bob收到密文“suhorkotzkxtkzykiaxoze”，然后将密文按照图2-2的映射关系转换为：（18，20，7，14，17，10，14，19，25，10，23，19，10，25，24，10，8，0，23，14，25，4）。使用解密函数D(c)=c-6（mod26）将密文转换后的数字代入计算，得到（12，14，1，8，11，4，8，13，19，4，17，13，4，19，18，4，2，20，17，8，19，24），即可还原出明文“mobileinternetsecurity”。2.1.3古典密码简介2.置换密码置换密码是通过简单的换位来达成加密比如，Alice想用置换密码来加密与Bob传递信息，事先约定密钥为一串字母“KEYWORD”。如图2-3所示，把A到Z中前面的字母用KEYWORD替换，后面又补充了A到Z（去掉了KEYWORD中重复的字母）。这样就形成了加解密的字母置换表，实际中A到Z可以置换成任意的字母。这个字母置换的过程其实就是加密。相应地，解密过程的字母置换表就如图2-4所示，将A替换成H，B替换成I，依此类推即可实现解密。2.1.4密码算法的安全性对于所有的密码算法，安全性都是其最重要的评价标准。这里所说的“安全性”，是指该密码系统对于破译攻击的抵抗力强度。目前评价密码算法安全性的方法有两种：无条件安全和有条件安全，无条件安全又称为理论上安全，有条件安全又称为实际安全性。很多密码算法的安全性并没有在理论上得到严格证明，只是在算法思想得到实现之后，经过众多密码专家多年来的攻击都没有发现其弱点，没有找到破译它的有效方法，从而认为它在实际上是安全的。2.1.4密码算法的安全性密码算法还有一种安全称为“计算上是安全的”，即指破解此密码系统是可行的，但是使用已知的算法和现有的计算工具不可能完成攻击所需的计算量。计算安全性是将密码算法的安全性问题与公认的数学难题挂钩，例如，密钥求解问题和某个NP问题。在实际场景中考虑密码算法安全性时，还需考虑破解一个密码系统所花费的成本不能超过被加密信息本身的价值，且破译的时间不能超过被加密信息的有效生命周期。

2.2.1分组密码2.2.2序列密码2.2.3密码的工作模式2.2对称密码算法2.2.1分组密码

分组密码（BlockCipher），也称块密码，是将明文消息编码表示后的数字序列划分成固定大小的分组，然后在密钥的控制下对各组分别进行加密变换，从而获得等长的二进制序列的一类算法。在现代分组密码中，两个最重要的思想就是扩散和混乱。扩散，是指要将算法设计成明文中每一比特的变化尽可能多地影响到密文输出序列的变化，以便隐藏明文的统计特性，我们可以形象地将其描述为“雪崩效应”。混乱，是指在加解密变换过程中明文、密钥以及密文之间的关系要尽可能地复杂化，以防密码破译者通过建立并求解一些方程来进行破译。2.2.1分组密码分组密码的加密过程如下：①将明文分成m个明文组M1，M2，…，Mi，…，Mm。②对每个明文分组分别作相同的加密变换，从而生成m个密文组C1，C2，…，Ci，…，Cm。在上图所示的加密过程中，分组密码以32位为一个分组对明文进行划分，明文单词“this”经过加密变换后得到密文“}kc{”。这些加密算法是对整个明文进行操作的，即除了其中的文字以外，还包括空格、标点符号和特殊字符等。2.2.1分组密码分组密码的解密过程和加密过程类似，进行的操作和变换也只是对应于加密过程的逆变换。首先将收到的密文分成m个密文分组C1，C2，…，Ci，…，Cm，在相同的密钥作用下，对每个分组执行一个加密的逆变换，解密得到对应的明文分组M1，M2，…，Mi，…，Mm。2.2.1分组密码典型的分组密码算法：DES算法AES算法IDEA算法有兴趣的读者可翻阅相关密码学书籍查看分组密码的详细设计2.2.2序列密码

序列密码又称为流密码，它的起源可以追溯到20世纪20年代的Vernam密码，是对称密码算法的一种。

序列密码将明文消息字符串在密钥流的控制下逐位进行加密和解密，所以具有加解密速度快、实现简单、便于硬件实施、没有或只有有限的错误传播的特点。

因此，在实际应用中，特别是在专用或机密机构中，序列密码保持着一定的优势。序列密码典型的应用领域包括无线通信、外交通信。2.2.2序列密码序列密码一般包含以下几个组成部分：明文序列mi、密钥序列ki、用于控制密钥序列产生器的种子密钥K密文序列ci。在序列密码中，加解密运算是简单的模2加运算，其安全性强度主要取决于密钥序列的随机性。序列密码的加解密过程如图2-6所示。2.2.2序列密码在图2-6中，KG是密钥流生成器，它主要分为两部分：驱动部分:驱动部分一般使用线性反馈移位寄存器（LinearFeedbackShiftRegister，LFSR），用于产生控制生成器的状态序列，并控制生成器的周期和统计特性。组合部分:组合部分主要负责对驱动部分的各个输出序列进行非线性组合。2.2.2序列密码移位寄存器用来存储数据，当受到脉冲驱动时，移位寄存器中所有位右移一位，最右边移出的位是输出位，最左端的一位由反馈函数的输出来填充，此过程称为进动一拍。反馈函数f(a1,…,an)是n元(a1,…,an)的布尔函数。如图2-7所示，移位寄存器根据需要不断地进动m拍，便有m位的输出，形成输出序列o1

o2…om。2.2.2序列密码图2-8是一个n级线性反馈移位寄存器的模型，移位寄存器中存储器的个数称为移位寄存器的级数，移位寄存器存储的数据是寄存器的状态，状态的顺序从左到右依次为从最高位到最低位。在所有状态中，叫初态，并且从左到右依次称为第一级、第二级、…、第n级，也称为抽头1、抽头2、抽头3、….、抽头n。n级线性反馈移位寄存器主要是用来产生周期大、统计性能好的序列，可以产生2n-1个有效状态.2.2.2序列密码

非线性组合部分主要是增加密钥流的复杂程度，使密钥流能够抵抗各种攻击。以线性反馈移位寄存器产生的序列为基序列，经过不规则采样、函数变换等操作（即非线性变换），就可以得到安全又实用的密钥流。

不规则采样是在控制序列作用下，对被采样序列进行采样输出，得到的序列称为输出序列。控制序列的控制方式有钟控方式和抽取方式等，函数变换有前馈变换和有记忆变换等。

2.2.2序列密码下面简单介绍两种具有代表性的序列模型。

钟控模型图2-9展示了一种钟控发生器的模型。当LFSR-1输出1时，时钟信号被采样，即能通过“与门”，并驱动LFSR-2进动一拍；当LFSR-1输出0时，时钟信号不被采样，即不能通过“与门”，此时LFSR-2不进动，重复输出前一位。

2.2.2序列密码前馈模型Geffe发生器是前馈序列的一种典型模型，如图2-10所示，其前馈函数g(x)=(x1x2)⊕(x2x3)为非线性函数，即当LFSR-2输出1时，g(x)的输出位是LFSR-1的输出位；当LFSR-2输出0时，g(x)的输出位是LFSR-3的输出位。

2.2.2序列密码序列密码通常分为两类:同步序列密码:若密钥序列的产生独立于明文消息和密文消息，这样的序列密码称为同步序列密码。自同步序列密码:若密钥序列的产生是密钥及固定大小的以往密文位的函数，这样的序列密码称为自同步序列密码或非同步序列密码.2.2.2序列密码同步序列密码:如图2-11所示，ki表示密钥流，ci

表示密文流，mi表示明文流。在同步序列密码中，密钥流的产生完全独立于消息流(明文流或密文流)。在这种工作方式下，如果传输过程中丢失一个密文字符，发送方和接收方就必须使他们的密钥生成器重新进行同步，这样才能正确地加/解密后续的序列，否则加/解密将失败。2.2.2序列密码自同步序列密码:如图2-12所示，自同步流密码的每一个密钥字符是由前面n个密文字符参与运算推导出来的，其中n为定值。如果在传输过程中丢失或更改了一个字符，那么这一错误就要向前传播n个字符。因此，自同步流密码会出现错误传播现象。不过，在收到n个正确的密文字符之后，密码自身会实现重新同步。2.2.2序列密码A5算法是GSM系统中主要使用的序列密码加密算法，用于加密移动终端与基站之间传输的信息。该算法可以描述为由22bit长的参数（帧号码，Fn）和64bit长的参数（会话密钥，Kc）生成两个114bit长的序列（密钥流）的黑盒子。这样设计的原因是GSM会话每帧含228bit，通过与A5算法产生的228bit密钥流进行异或来达到保密。典型的序列密码算法:A5算法2.2.2序列密码A5算法是一种典型的基于线性反馈移位寄存器的序列密码算法，构成A5加密器主体的LFSR有三个，组成了一个集互控和停走于一体的钟控模型。其主体部分由三个长度不同的线性移位寄存器（A,B,C）组成，其中A有19位，B有22位，C有23位，它们的移位方式都是由低位移向高位。每次移位后，最低位就要补充一位，补充的值由寄存器中的某些抽头位进行异或运算的结果来决定，比如：运算的结果为“1”，则补充“1”，否则补充“0”。在三个LFSR中，A的抽头系数为：18，17，16，13；B的抽头系数为：21，20，16，12；C的抽头系数为：22，21，18，17。三个LFSR输出的异或值作为A5算法的输出值。A5加密器的主体部分如图2-13所示。典型的序列密码算法:A5算法2.2.2序列密码2.2.2序列密码在图2-13中，A的生成多项式为

fA（x）=x19+x18+x17+x14+1B的生成多项式为

fB（x）=x22+x21+x17+x13+1C的生成多项式为

fC（x）=x23+x22+x19+x18+1三个线性反馈移存器的生成多项式均为本原多项式。这三个加密器的移位是由时钟控制的，且遵循“服从多数”的原则，即从每个寄存器中取出一个中间位（图2-13中的x,y,z，位置分别为A,B,C的第9，11，11位）并进行判断，若在取出的三个中间位中至少有两个为“1”，则为“1”的寄存器进行一次移位，而为“0”的不进行移位。反之，若三个中间位中至少有两个为“0”，则为“0”的寄存器进行一次移位，而为“1”的不进行移位。显然，这种机制保证了每次至少有两个LFSR被驱动移位。2.2.3密码的工作模式分组密码算法每次加密的明文数据的大小是固定的。通常明文的长度会超过分组密码的分组长度，此时就需要对分组密码算法进行迭代，迭代的方法就称为分组密码的工作模式。常用的分组密码的工作模式有五种：电子密码本模式密文分组链接模式密文反馈模式输出反馈模式计数器模式2.2.3密码的工作模式电子密码本模式（ElectronicCodeMode，ECB）在该模式下，每个分组独立进行加解密运算，一次处理一组明文块，每次使用相同的密钥进行加密，不同分组间没有任何关联。而且这种方式不必按次序进行，可以先加密中间的分组，然后是尾部分组，最后再加密最开始的分组。2.2.3密码的工作模式密文分组链接模式（CipherBlockChaining，CBC）初始向量为IV，密钥为K。第一个明文分组被加密后，其结果被存储在反馈寄存器中，在下一明文分组进行加密之前，它将与保存在反馈寄存器中的前一个分组的密文进行异或并作为下一次加密的输入。同样地，加密后的结果仍然保存在反馈寄存器中，直到最后一个分组加密后直接输出。由此可见，每一分组的加密都依赖于所有前面的分组。在解密时，每个密文组分别进行解密，再与上一分组进行异或就可以恢复出明文。2.2.3密码的工作模式密文反馈模式（CipherFeedbackBlock，CFB）若设分组长度为n位，初始向量为IV（n位），密钥为K，则j比特位的CFB模式下（j在1~n之间），加密过程如下：设一个n位长的队列，队列初始值为IV，并把明文消息分成M个j位的比特块；依次对每个j位比特块明文Pj进行以下操作：用密钥K加密队列，把该密文最左端的j位与j位比特块明文Pj进行异或，即可获得其j位比特块的密文Cj；然后把该j位比特块密文Cj放入队列的最右端，并丢弃队列最左端的j位；最后把全部j位比特块密文C1…CM依次连起来，即可得到消息密文C。2.2.3密码的工作模式输出反馈模式（OutputFeedback，OFB）通过将明文分组和密码算法的输出进行异或来产生密文分组，但OFB是将前一个j比特输出分组送入队列最右边位置。解密是加密的一个逆过程。在OFB模式的加解密过程中，分组算法都以加密模式使用。由于反馈机制独立于明文和密文，这种方法有时也被称为“内部反馈”。2.2.3密码的工作模式计数器模式（CounterMode，CTR）采用与明文分组相同的长度来加密不同的明文组。在该模式中，分组密码没有直接被用来加密明文，而是用于加密计数器的输出。计数器首先被初始化为一个值，然后随着消息块的增加，计数器的值会依次递增1，计数器加1后与明文分组进行异或得到密文分组。

2.3.1公钥密码基本概念2.3.2RSA密码算法2.3.3椭圆曲线密码算法2.3.4NTRU公钥密码2.3公钥密码算法2.3.1公钥密码基本概念

对称密码算法在密钥分配方面面临着管理和分发的困难，而且对称加密算法无法实现抗抵赖的要求，公钥密码算法的出现解决了这一难题。1976年，Diffie和Hellman首次提出了公开密钥加密算法，在密码学的发展史上具有里程碑式的意义。

常见的公钥密码算法有：RSA、ElGamal公钥密码算法、椭圆曲线公钥密钥算法（ECC）、NTRU公钥加密算法和Rabin公钥加密算法等。2.3.1公钥密码基本概念

公钥密码算法解决了密钥的管理和分发问题，每个用户都可以公开自己的公钥，并由用户自己保存私钥，不被他人获取。A加密：X->Y：Y=E(PuB(X))A用B的公钥PuB对明文X进行加密得到YB解密：Y->X：X=D(PrB(Y))B用自己的私钥PrB对密文Y进行解密获得X上式中，X表示明文，Y表示加密后的密文，E表示加密，D表示解密。PuB是B的公钥，该密钥是公开的，A使用此密钥加密数据传给B；PrB是B的私钥，由B保存且不能被外人所知，B使用此密钥解密A用PuB加密过的数据。PuB和PrB是相互关联的，而且是成对出现的。2.3.2RSA密码算法RSA密码算法的安全性是基于大数分解的困难性。RSA算法的密钥产生和加解密过程如下所述。其中，m表示明文，c和s表示密文。密钥的产生过程如下：独立选取两个大素数p和q（各100~200位十进制数字，根据需要的密钥长度进行选择）；计算n=p*q，其欧拉函数值φ(n)=(p-1)(q-1)；随机选取一个整数e，满足1≤e＜φ(n)，并使最大公约数gcd(φ(n),e)=1；在模φ(n)下，计算e的逆：d=e-1mod(p-1)(q-1)；以n，e为公钥，d为私钥（p，q不再需要，可以销毁）。2.3.2RSA密码算法RSA算法用于加密和解密：加密过程：c=me

modn

解密过程：m=cd

modnRSA算法用于数字签名和验证：签名过程：s=md

modn验证过程：m=se

modn2.3.3椭圆曲线密码算法假设发送方为A，接收方为B，A需要将消息加密后传送给B。那么，首先需要考虑如何用椭圆曲线来生成用户B的公私密钥对，可以分为以下三步：

构造椭圆群设E：y2=x3+ax+b（modp）是GF(p)上的一个椭圆曲线（p>3），首先构造一个群Ep(a,b)。挑选生成元挑选Ep(a,b)中的一个生成元点G=(x0,y0)，G应满足使nG=O成立的最小的n是一个大素数。选择公私密钥选择整数kB（k<n）作为私钥，然后产生其公钥PB=kBG，则B的公钥为（E，n，G，PB），私钥为kB。2.3.3椭圆曲线密码算法下面介绍如何利用公私密钥对进行加解密的运算（以下的运算都是在modp下进行的）。1.加密过程（1）发送方A将明文消息编码成一个数m<p，并在椭圆群

Ep(a,b)中

选择一点Pt=（xt，yt）；（2）发送方A计算密文：C=mxt+yt；（3）发送方A选取一个保密的随机数r(0<r<n)，并计算rG；（4）依据接收方B的公钥PB，计算Pt+rPB；（5）发送方A对m进行加密，得到数据Cm={rG，Pt+rPB，C}。2.解密过程接收方B在收到A发来的加密数Cm={rG，Pt+rPB，C}之后，进行如下操作：（1）使用自己的私钥kB计算：Pt+rPB-kB(rG)=Pt+r(kBG)-kB(rG)=Pt（2）接收方B计算：m=(C-yt)/xt，得到明文m。2.3.4NTRU公钥密码NTRU是1995年由J.Hoffstein,J.Pipher和J.Silverman发明的一种密码算法。在数学上，NTRU比RSA或ElGamal密码还要复杂。由于它的复杂性和出现的时间相对较短，国内外密码学界针对NTRU的安全性研究仍在继续。2.3.4NTRU公钥密码NTRU密码算法的工作过程如下：密钥生成

在NTRU公钥密码算法中，接收方需要生成一组公/私密钥对。具体步骤如下：①选择公开参数。选择正整数参数N，p，q，其中p，q不必为素数，但是它们必须互素，且满足gcd(N,pq)=1。②选择多项式f(x)和g(x)。由接收方选择两个小系数多项式f和g，其中模q的随机多项式的系数一般随机地分布在区间[0,q]上，而所谓的小系数多项式的系数相对于模q的随机多项式要小得多。接收方需要对多项式f(x)和g(x)保密，因为任何一个多项式信息泄露都可能导致密文被破解。2.3.4NTRU公钥密码③计算逆元Fp(x)和Fq(x)。接收方计算多项式f(x)在模p和模q时的逆元Fp(x)和Fq(x)，即Fp(x)*f(x)=1(modp,modxN-1)和Fq(x)*f(x)=1(modq,modxN-1)。如果f(x)的逆元不存在，接收方需要重新选取f(x)。④计算公钥。计算h(x)=F