第二部分密码学基础教材

第二部分密码学基础密码学概述对称密码学单向散列函数公钥密码系统876543密码学概述密码学的发展基本术语保密通信系统模型密码体制密码分析密码算法的安全性密码学的发展密码技术是一门古老的技术，大概自人类社会出现战争便产生了密码(Cipher)

由于密码长期以来仅用于政治、军事、公安、外交等要害部门，其研究本身也只限于秘密进行。所以密码被蒙上神秘的面纱。在军事上，密码成为决定战争胜负的重要因素之一。有些军事评论家认为，盟军在破译密码方面的成功，使二次世界大战提前几年结束。密码学是研究如何对敏感信息进行保护的一门重要学科。

随着计算机和通信技术的迅速发展和普及应用，出现了电子政务、电子商务、电子金融等重要的应用信息系统。在这些系统中必须确保信息的安全传递和存储密码学的发展1949年之前：古典密码（classicalcryptography)密码学多半是具有艺术特征的字谜，出现一些密码算法和机械的加密设备。密码算法的基本手段是：替代和置换(substitution&permutation)出现，针对的是字符。密码破译的手法逐渐形成，二次世界大战尤为明显。1949～1975年:计算机使得基于复杂计算的密码成为可能1949年Shannon：TheCommunicationTheoryofSecretSystems1967年DavidKahn的《The

Codebreakers》1971-73年IBMWatson实验室的Horst

Feistel等的几篇技术报告数据的安全基于密钥而不是算法的保密密码学的发展1976年以后:1976年Diffie和Hellman发表了“密码学的新方向”（NewDirectionsinCryptography）提出了不对称密钥密码，奠定了公钥密码学的基础。1977年Rivest,Shamir&Adleman提出了RSA公钥算法。公钥技术是二十世纪最伟大的思想之一改变了密钥分发的方式可以广泛用于数字签名和身份认证服务90年代逐步出现椭圆曲线等其他公钥算法公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！密码学的发展1976年以后，对称密钥密码算法进一步发展1977年DES正式成为标准80年代出现“过渡性”的“postDES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出现2001年Rijndael成为DES的替代者，有了新的分组密码加密标准AES密码学的发展—总结未来会有什么密码？物理密码计算密码古典密码艺术密码基本术语

密码体制是密码技术中最为核心的一个概念。密码体制被定义为一对数据变换：基本术语密码技术的基本思想是伪装信息，伪装就是对数据施加一种可逆的数学变换。伪装前的数据称为明文(Plaintext),伪装后的数据称为密文(Ciphertext)。伪装的过程称为加密(Encryption),去掉伪装恢复明文的过程称为解密(Decryption)。加/解密要在密钥(Key)的控制下进行。将数据以密文的形式存储在计算机的文件中或送入网络信道中传输，而且只给合法用户分配密钥。这样即使密文被非法窃取，因不法分子没有密钥而不能得到明文。基本术语

密码员对明文进行加密操作时所采用的一组规则称作加密算法(EncryptionAlgorithm)。

所传送信息的预定对象称为接收者(Receiver)。

接收者对密文解密所采用的一组规则称为解密算法(DecryptionAlgorithm)。

密码学(Cryptology):是研究信息系统安全保密的科学。密码编码学(Cryptography):主要研究对信息进行编码,实现对信息的隐蔽。

密码分析学(Cryptanalytics):主要研究对密文（对明文加密后而得的信息）的破译和对明文的伪造密码学的分类

密码学编码学：密码的设计分析学：密码的破译其它安全管理，安全协议设计，秘密分存现代：数字化现金，量子密码，馄饨密码等相互依存相互支持密不可分保密系统通信模型密码学的目的：郭靖和黄蓉两个人在不安全的信道上进行悄悄话通信，而第三者欧阳克不能理解与破坏他们通信的内容。密码体制定义:(密码体制）它是一个五元组（P,C,K,E,D)：（1）P是可能明文的有限集；（明文空间）（2）C是可能密文的有限集；（密文空间）（3）K是一切可能密钥构成的有限集（密钥空间）（4）E加密算法。（5）D解密算法。对于任意k∈K,有一个加密算法ek∈E和相应的解密算法dk∈D，使得ek:P→C和dk:C→P分别为加密解密函数，满足dk(ek(x))=x,这里x∈P。空间集合的大小与安全有什么关系？攻击动画密码体制分类方法可从三种不同的角度进行分类（1）从明文到密文的变换替换(substitution)置换(permutation)……（2）钥匙的数目对称、单钥加密法双钥、公钥加密（3）明文的处理方式分组加密（块加密算法）流方式加密传统：加密解密

分类传统密码：人工计算机密码现代双钥：公钥/私钥字符:流密码分组:分组密码单钥单钥单钥传统：加密解密

分类传统密码：人工计算机密码现代双钥：公钥/私钥字符:流密码分组:分组密码单钥单钥单钥密码体制分类方法-1基于密钥的算法，按照密钥的特点分类：

对称密钥算法（symmetriccipher)：又称传统密钥算法（conventionalcipher)，就是加密密钥和解密密钥相同，或实质上等同，即从一个易于推出另一个。又称秘密密钥算法或单密钥算法。

非对称密钥算法（asymmetriccipher):加密密钥和解密密钥不相同，从一个很难推出另一个。又称公开密钥算法（public-keycipher)。公开密钥算法用一个密钥进行加密，而用另一个密钥进行解密。其中的加密密钥可以公开，又称公开密钥（publickey)，简称公钥。解密密钥必须保密，又称私人密钥（privatekey)私钥，简称私钥。三种方法分析1.三种方法各有什么特点？2.可否将一些方法混合使用，以充分利用其各自的特点？三种方法分析密码体制分类方法-2按照加密过程中对明文的处理方法：

分组密码（blockcipher)：将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。

流密码（streamcipher)：又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。

序列密码是手工和机械密码时代的主流密码分析发现X和K的过程被称为密码分析

分析的策略取决于加密的技术以及可利用的信息，在加密算法设计和攻击时都需要用到的技术根据可利用信息的不同，可分为4类：（1）只有密文（2）已知部分明文-密文对（3）选择明文（4）选择密文*（1）（2）（3）常见、（4）不常见对密码系统的攻击类型对密码系统的攻击类型自适应选择明文攻击

自适应选择明文攻击(adaptive-chosen-plaintextattack)：是选择明文攻击的一种特殊情况，指的是密码分析者不仅能够选择被加密的明文，也能够依据以前加密的结果对这个选择进行修正。自适应选择密文攻击密码破译的手段密码破译的原则:遵循观察与经验

方法:采用归纳与演绎

步骤:分析、假设、推测和证实

三大要素：语言的频率特征：e连接特征:q…u,Iex,重复特征:th,tion,tious单表替换密码的破译通过字母的使用频率破译密码算法的安全性

无条件安全（Unconditionallysecure）无论破译者有多少密文,他也无法解出对应的明文，即使他解出了，他也无法验证结果的正确性。

计算上安全（Computationallysecure）破译的代价超出信息本身的价值破译的时间超出了信息的有效期。直觉：什么是一个好的加密算法假设密码(password)k是固定的明文和密文是一个映射关系：单射，即

Ek(x1)≠Ek(x2)ifx1≠x2通常情况是：明文非常有序好的密码条件下，我们期望得到什么样的密文

随机性如何理解随机性

静态：特殊的点动态：小的扰动带来的变化不可知考虑设计一个加密算法打破明文本身的规律性

随机性(可望不可及)非线性(一定要)统计意义上的规律多次迭代

迭代是否会增加变换的复杂性是否存在通用的框架，用于迭代复杂性带来密码分析的困难和不可知性

实践的检验和考验柯克霍夫（Kerckhoffs）原则柯克霍夫（Kerckhoffs）原则：密码系统的安全性取决于密钥，而不是密码算法，即密码算法要公开。这是荷兰密码学家Kerckhoff于1883年在名著《军事密码学》中提出的基本假设。遵循这个假设的好处是：①它是评估算法安全性的惟一可用的方式。因为如果密码算法保密的话，密码算法的安全强度无法进行评估。②防止算法设计者在算法中隐藏后门。因为算法公开后，密码学家可以研究分析是否存在漏洞，同时也接受攻击者的检验。③有助于推广使用。当前网络应用十分普及，密码算法的应用不再局限于传统的军事领域，只有算法公开，才可能被大多数人接受并使用，同时，对用户而言，只需掌握密钥就可以使用。对称密码学古典密码1.移位密码2.仿射密码3.

维吉利亚(Vigenere)密码4.置换密码对称加密体制1序列密码2分组密码3数据加密标准－DES艺术密码与古典密码艺术密码可以通过多种方式来实现，主要方式包括：文字变形、在艺术作品中加入巧妙的手笔、符号的适当排列等等古典密码本质上是一种以线性代数为基础的密码形式，主要包括置换密码体制和代换密码体制。许多文献直接将艺术密码归为古典密码艺术密码实例水浒传－吴用智赚玉麒麟芦花丛中一扁舟，俊杰俄从此地游，义士若能知此理，反躬难逃可无忧。古典密码1.移位密码移位密码的加密方法是将明文字母按某种方式进行移位，如著名的恺撒密码。在移位密码中，将26个英文字母依次与0,1,2,…,25对应，密文字母c可以用明文字母m和密钥k按如下算法得到：c=m+k(mod26)给定一个密文字母c,对应的明文字母m可由c和密钥k按如下算法得到：m=c-k(mod26)按照密码体制的数学形式化定义，移位密码体制描述为五元组(P，C，K，E，D)，其中：

P=C=K=Z26={0，1，2，…，25}，E={ek:Z26

Z26|ek(m)=m

+k(mod26)}，

D={dk:Z26

Z26|dk(c)=c

k(mod26)}。古典密码2.仿射密码仿射密码和移位密码一样,

也是一种替换密码.

不同的是,

移位密码中,

我们使用的是模n加;

而在下面的仿射密码中,

我们使用的是模n乘.

在安全性方面,

仿射密码同移位密码一样,

都是极其差的,

不仅因为他们的原理简单,

更要命的是这两种替换密码没有隐藏明文的字频信息,

这很容易导致破解者轻易的攻破.

古典密码2.仿射密码仿射密码算法如下：(1)

明密文字母表为Z26

(2)

秘匙

K

=

(a,b)

∈

Z26_

×

Z26

.

其中Z26_表示小于26且与26互素(或叫互质)的正整数的集合,这点非常重要的.（为什么？）

(3)

加密变换为

y

=

(ax

+

b)

mod

26

;

(4)解密变换为:

x

=

a-1(y-b)

mod

26

若a,b两数的乘积对正整数n取模的结果为1.

则称a,b

互为另外一个的模逆.

比如:

3*7

=

21;

21

%

20

=

1

;

所以3,7

互为

20

的

模逆.

9*3

=

27;

27

%

26

=

1

;

所以9,3

互为

26

的

模逆.古典密码例假设k1=9和k2=2，明文字母为q,则对其用仿射密码加密如下：先把文字母为q转化为数字13。由加密算法得

c=9

13+2=119(mod26)=15再把c=15转化为字母得到密文P。解密时，先计算k1

1。因为9

3≡1(mod26)，因此k1

1=3。再由解密算法得

m=k1

1(c

k2)(mod26)=3

(c-2)=3c-6(mod26)

≡45+20(mod26)=13(mod26)。对应的明文字母为q。古典密码3.

维吉利亚(Vigenere)密码Vigenere是法国的密码学专家，Vigenere密码是以他的名字命名的。该密码体制有一个参数n。在加解密时同样把英文字母用数字代替进行运算，并按n个字母一组进行变换。明、密文空间及密钥空间都是n长的英文字母串的集合，因此可表示P=C=K=(Z26)n。加密变换如下：设密钥k=(k1,k2,…,kn)，明文P=(m1,m2,…,mn)，加密函数ek(P)=(c1,c2,…,cn)，其中ci=(mi+ki)(mod26),i=1,2,…,n。对密文c=(c1,c2,…,cn)，密钥k=(k1,k2,…,kn)，解密变换为dk(c)=(m1,m2,…,mn)，其中mi=(ci

ki)(mod26),i=1,2,…,n。古典密码例设n=6，密钥是cipher，这相应于密钥k=(2,8,15,7,4,17)，明文是thiscryptosystemisnotsecure。试用Vigenere密码对其加密。解首先将明文按每6个分为一组，然后与密钥进行模26“加”得：197818217241519141824281574172815741721152325680238212215

18194128181314191842201742815741728157417281520119191291522825819222519

相应的密文是：VPXZGIAXIVWPUBTTMJPWIZITWZT古典密码4.置换密码置换密码是把明文中各字符的位置次序重新排列来得到密文的一种密码体制。实现的方法多种多样。在这里，我们介绍一类较常见的置换密码。其加解密方法如下：把明文字符以固定的宽度m(分组长度)水平地(按行)写在一张纸上（如果最后一行不足m，需要补充固定字符），按1，2，…，m的一个置换

交换列的位置次序，再按垂直方向(即按列)读出即得密文。解密就是将密文按相同的宽度m垂直在写在纸上，按置换

的逆置换交换列的位置次序，然后水平地读出得到明文。置换

就是密钥。古典密码例设明文Jokerisamurderer，密钥

=(41)(32)(即

(4)=1，

(1)=4，

(3)=2，

(2)=3)),即按4，3，2，1列的次序读出得到密文，试写出加解密的过程与结果。解：加密时，把明文字母按长度为4进行分组，每组写成一行，这样明文字母Jokerisamurderer被写成4行4列，然后把这4行4列按4，3，2，1列的次序写出得到密文。过程与结果如图2-3-1所示。解密时，把密文字母按4个一列写出，再按

的逆置换重排列的次序，最后按行写出，即得到明文。明文：

Jokerisamurderer按4字母一行写出joke

risa

murd

erer按列写出的顺序4321

按列写出密文：eadrksreoiurjrme密文：

eadrksreoiurjrme按4字母一列写出

ekoj

asirdrum

rere交换列的顺序4321

按行写出明文：

jokerisamurderer古典密码—总结在现代密码学中，假定密码方案遵从Kerckhoffs原则，因此，对密文的破解取决于加密密钥。就古典密码而言，由于算法相对简单，算法复杂度也不高，一种可能的攻击方法是对所有可能的密钥进行尝试的强力攻击，称为穷举搜索攻击。移位密码：密钥空间K=Z26={0，1，2，…，25}，因此，最多尝试26次即可恢复明文。仿射密码：密钥空间为K={(k1，k2)|k1，k2

Z26,其中gcd(k1,26)=1}，k1可能的取值有1，3，5，7，9，11，15，17，19，21，23，25，因此，最多尝试12×26次即可恢复明文。对于古典密码方案而言，由于密钥空间非常有限，因此，很难抵抗穷举搜索攻击。另一方面，就英文而言，一些古典密码方案不能很好地隐藏明文消息的统计特征，攻击者也可以利用这一弱点进行破译。结论：古典密码方案并不适合Kerckhoffs原则，密码方案的保密性基于算法的保密。对称加密体制序列密码分组密码数据加密标准－DES这个世界的问题在于聪明人充满疑惑，而傻子们坚信不疑。--罗素对称加密体制在这种密码体制中，对于大多数算法而言，解密算法是加密算法的逆运算，加密密钥和解密密钥相同，满足关系：M=Dk(C)=Dk(Ek(M))。对称密码体制的开放性差，要求通信双方在通信之前，商定一个共享密钥，彼此必须妥善保管。对称密码体制分为两类。一类是对明文的单个位（或字节）运算的算法，称为序列密码算法，也称为流密码算法(StreamCipher)。另一类算法是把明文信息划分成不同的块（或小组）结构，分别对每个块进行加密和解密，称为分组加密算法(BlockCipher)。滚动密钥生成器………….滚动密钥生成器………….Ezi(Mi)Dzi(Ci)KKiKCiMiKi………同步流密码体制模型:密钥流与明文串相互独立MiEzi(Mi)Dzi(Ci)流密码的基本思想：产生一个密钥流k=k1k2…,根据下面规则加密明文M=m1m2…;C=C1C2…=EK1(m1)EK2(m2)

…序列密码(流密码)滚动密钥生成器………….滚动密钥生成器………….KZiKYiXiZiXi………+加法流密码体制模型+序列密码序列密码序列密码分为同步序列密码和自同步序列密码两种。同步序列密码要求发送方和接收方必须是同步的，在同样的位置用同样的密钥才能保证正确地解密。如果在传输过程中密文序列有篡改、删除、插入等错误导致同步失效，则不可能成功解密，只能通过重新同步来实现恢复。在传输期间，一个密文位的改变只影响该位的恢复，不会对后继位产生影响。自同步序列密码的密钥的产生与密钥和已产生的固定数量的密文位有关，因此，密文中产生的一个错误会影响到后面有限位的正确解密。因此，自同步密码的密码分析比同步密码更加困难。序列密码具有实现简单、便于硬件计算、加解密处理速度快、低错误（没有或只有有限位的错误）传播等优点，但同时也暴露出对错误产生不敏感的缺点。序列密码序列密码的安全强度依赖于密钥流产生器所产生的密钥流序列的特性，关键是密钥生成器的设计及收发两端密钥流产生的同步技术。1.伪随机序列在序列密码中，一个好的密钥流序列应该满足：①良好的伪随机性，如极大的周期，极大的线性复杂度，序列中0和1的分布均匀；②产生的算法简单；③硬件实现方便。产生密钥流序列的方法可以是使用自然现象随机生成或标准C库函数中函数rand()。产生伪随机数的一个不错的选择是使用数论中的难题。最常用的是BBS伪随机序列生成器：产生两个大素数p和q

，且，设n=pq

，并选择一个随机整数x(x与n互素)设初始输入，BBS通过如下过程产生一个随机序列：①；②是的最低有效比特。序列密码2.线性反馈移位寄存器通常，产生密钥流序列的硬件是反馈移位寄存器。一个反馈移位寄存器由两部分组成：移位寄存器和反馈函数：anan-1a2a1f(a1,

a2,…,an)…输出序列f(a1,a2,…,an)=cna1cn-1a2….c1an+++序列密码序列密码对于n级线性反馈移位寄存器，不可能产生全0状态，因此，最大可能周期为。选择线性反馈移位寄存器作为密钥流生成器的主要原因有：①适合硬件实现；②能产生大的周期序列；③能产生良好的统计特性的序列；④它的结构能够应用代数方法进行很好的分析。实际应用中，通常将多个LFSR组合起来构造非线性反馈移位寄存器，n级非线性反馈移位寄存器产生伪随机序列的周期最大可达到，因此，研究产生最大周期序列的方法具有重要意义。序列密码3.

RC4RC4是由麻省理工学院的RonRivest教授在1987年为RSA公司设计的一种可变密钥长度、面向字节流的序列密码。RC4算法很简单，它以一个数据表为基础，对表进行非线性变换，从而产生密码流序列。包含两个主要算法：密钥调度算法(Key-SchedulingAlgorithm，KSA)和伪随机生成算法(PseudoRandomGenerationAlgorithm，PRGA)。序列密码KSA的作用是将一个随机密钥(大小为40~256位)变换成一个初始置换表S。过程如下：S11S表中包含256个元素S[0]~S[255]，对其初始化，令

S12用主密钥填充字符表K，如果密钥的长度小于256个字节，则依次重复填充，直至将K被填满。

S13令

j=0；S14对于

i从0到255循环①

②交换

S[i]和S[j]

。序列密码PRGA的作用是从S表中随机选取元素，并产生密钥流。过程如下：S21i=0,j=0；S22i=i+1(mod256)；S23j=j+S[i]mod256S24交换S[i]和S[j]

；S25t=S[i]+S[j]mod256

；S26输出密钥字k=S[t]

。虽然RC4要求主密钥K至少要40位，为了保证安全强度，目前至少要达到128位。分组密码分组密码概述分组密码是将明文消息序列m1，m2，…，

m1k,

…

分成等长的消息组(m1，

m2，…，

mn)，

(mn+1，

mn+2，…，

m2n),…在密钥控制下，按固定的算法Ek一组一组进行加密。加密后输出等长密文组（y1，

…，ym),(ym+1，

…，y2m),…加密算法密钥k明文(x1，

x2，…，

xn)密文(y1，y2，…，yn)加密一组明文的过程分组密码分组加密的本质就是由密钥控制的从明文空间M（长为n的比特串的集合）到密文空间C（长为r的比特串的集合）的一个1-1映射。为了保证密码算法的安全强度，一般说来，加密变换的构造应遵循下列几个原则：①分组长度足够大②密钥量空间足够大③加密变换足够复杂④加密和解密运算简单，易于实现⑤加密和解密的逻辑结构最好一致分组密码古典密码中最基本的变换是代替（substitutioncipher)和移位(置换permutationcipher)，其目的是产生尽可能混乱的密文。代替变换就是经过复杂的变换关系将输入位进行转换，记为S，称为S盒；移位变换就是将输入位的排列位置进行变换，记为P，称为P盒。分组密码由多重S盒和P盒组合而成，如图所示。S盒的直接作用是将输入位进行某种变换，起到混乱作用，P盒的直接作用就是移动输入位的排列位置关系，起到扩散的作用。分组密码实现分组密码设计算法的具体操作包括以下三个方面：1.代替将明文位用某种变换关系变换成新的位，使得产生的密文是一堆杂乱无章的乱码，分组密码中采用复杂的非线性代替变换就可达到比较好的混乱效果。2.移位指让明文中的每一位(包括密钥的每一位)直接或间接影响输出密文中的许多位，以便隐蔽明文的统计特性。这种效果也称为“雪崩效应”。3.乘积变换在分组密码算法设计中，为了增强算法的复杂度，常用的方法是采用乘积变换的思想，即加密算法不仅仅是简单的一次或两次基本的S盒和P盒变换，而是通过两次或两次以上S盒和P盒的反复应用，也就是迭代的思想，克服单一密码变换的弱点，构成更强的加密结果，以强化其复杂程度。数据加密标准-DES1971年末IBM公司提出了一种称为Lucifer的密码算法1977年7月15日该算法被正式采纳作为美国联邦信息处理标准生效，即数据加密标准（DataEncryptionStandard，DES）。实现分组密码设计算法的具体操作包括以下三个方面：1.

DES加密算法流程数据加密标准-DES

DES加密过程64位明文××××××××××××××××密钥（1）密钥（2）密钥（3）密钥（16）

算法概要Li=Ri-1

Ri=Li-1⊕f(Ri-1,Ki)Ri-1压缩置换扩展置换S-盒代替Li-1Li密钥密钥移位移位P-盒转换Ri数据加密标准-DES数据加密标准-DES(1)初始置换IP初始置换如图所示，方法是将64位明文的位置顺序打乱，表中的数字代表64位明文的输入顺序号，表中的位置代表置换后的输出顺序，表中的位置顺序是先按行后按列进行排序。初始置换表中的位序特征：64位输入按8行8列进行排列，最右边一列按2,4,6,8和1,3,5,7的次序进行排列，往左边各列的位序号依次紧邻其右边一列各序号加8。数据加密标准-DES(2)乘积变换（16轮迭代）乘积变换部分要进行16轮迭代，如图所示。将初始置换得到的64位结果分为两半，记为L0和R0，各32位。设初始密钥64位，经密钥扩展算法产生16个48位的子密钥，记为K1，K2，…，K16，每轮迭代的逻辑关系为：其中，f

函数是每轮变换的核心变换

。数据加密标准-DES(3)逆初始置换IP-1逆初始置换IP-1与初始置换正好相反，如图所示。比如，处在第一位的比特位置换后排在第58位，第二位排在第50位。逆初始置换表中的位序特征：64位输入依然按8行8列进行排列，1,2,3,4,5,6,7,8按列从下往上进行排列，然后是9到16排在右边一列，依次进行排4列，然后从33开始排在第一列的左边，从41开始排在第二列的左边，交叉进行。数据加密标准-DE