网络安全密码学基础

网络信息安全

---第3章密码学基础电子信息工程学院计算机与科学技术系第3章密码学基础

本章主要讨论以下几方面的问题密码学的基本概念和术语对称和非对称密码及其区别古典密码学的基本方法DES算法、RSA算法的基本原理

悬赏：如果你能读懂这个消息，你就是一个成功的密码

破译者了，考试可以给你加点分。分这是密可加懂就的了试读你功者考能息成译你消个破给果个一码以如点农户与鸡快吃吧，这是你最后一顿！鸡躺倒并留遗书：爷已吃老鼠药，你们别想吃爷了，爷也不是好惹的！

当对手知道了你的决定之后，就能做出对自己最有利的决定。——纳什均衡理论保密、信息安全很重要！3.1密码学概述密码学是一门古老而深奥的学科，对一般人来说是非常陌生的。长期以来，只在很小的范围内使用，如军事、外交、情报等部门。计算机密码学是研究使用计算机进行信息加密、解密及其变换的科学，是数学和计算机的交叉学科，是一门新兴的学科。随着计算机网络和计算机通信技术的发展，计算机密码学得到前所未有的重视并迅速普及和发展起来。3.1.1密码学的发展史密码学的历史比较悠久，在四千年前，古希腊人就开始使用密码来保密传递消息。两千多年前，罗马国王JuliusCaesar（恺撒）就开始使用目前称为“恺撒密码”的密码系统，用来、传递保护重要军事情报。但是密码技术直到20世纪40年代以后才有重大突破和发展。特别是20世纪70年代后期，由于计算机、电子通信的广泛使用，现代密码学得到了空前的发展。3.1.1密码学的发展史几个著名的加密系统恺撒（Caesar）密码维吉尼亚密码（Vigenerecypher）

恩格玛（Enigma）密码机数据加密标准：DES公开密钥密码：RAS莱斯·德·维吉尼亚（BlaisedeVigenère，1523-1596），一名法国的外交官，同时也是一位密码学家。1586年在维吉尼亚密码原基础上进行了改进。

恺撒大帝是罗马共和国末期杰出的军事统帅、政治家。他公元前60年与庞培、克拉苏秘密结成前三巨头同盟，随后出任高卢总督，花了八年时

间征服了高卢全境（大约是现在的法国），还袭击了日耳曼和不列颠

恩格玛（Enigma）密码机密码学的发展史大体上可以归结为三个阶段第一阶段：1949年之前。这阶段的密码学的特点是：

密码学还不是科学，而是艺术

出现一些密码算法和加密设备

密码算法的基本手段出现，主要针对字符

简单的密码分析手段出现

数据的安全性基于算法的保密代表性的事件是：1883年荷兰密码学家Kerchoffs提出了密码学的一个基本原则：加密算法应建立在算法的公开，密码系统的安全性应该完全依赖于密钥的安全性。这个原则得到广泛承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。密码学的发展史大体上可以归结为三个阶段第二阶段是1949-1975年，密码学成为一门独立的科学，计算机的出现使基于复杂计算的密码成为可能。主要研究特点是：数据安全性基于密钥而不是算法的保密。第三阶段是1976年以后密码学中公钥密码学成为主要研究方向，该阶段具有代表性的事件是：1976年，斯坦福大学的Diffie和Hellman提出了不对称密钥1977年，Rivest，Shamir和Adleman提出了RSA公钥算法1977年，DES算法出现80年代，出现IDEA和CAST等算法90年代，对称密钥密码算法进一步成熟，Rijndael，RC6等出现，逐步出现椭圆曲线等其他公钥算法2001年，Rijndael成为DES算法的替代者2004年8月，山东大学信息安全研究所所长王小云，在国际会议上首次宣布了她及她的研究小组对MD5、HAVAL-128、MD4和RIPEMD等四个著名密码算法的破译结果，引起世界轰动。这阶段的主要特点是：公钥密码学使数据的安全性是基于密钥而不是算法。Caesar（恺撒）密码（一）：（换位加密法）明文集合：abcdefghijklmnopqwstunwxyz密文集合：DEFGHIGKLMNOPQRSTUVWXYZABC明文(m)：Caesarwas

agreatsoldier密文(c)：

FDHVDU

ZDVD

JUHDW

VROGLHU

密文集合是明文集合中的字母向后移动3位得到的3.1.1密码学的发展历史

Caesar（恺撒）

密码（二）：为26个英文字母依次分配一个序号CAESAR密码算法或变换（E）：c=(m+

k)mod26k=3CAESAR密码的密钥集合（K）：（1，2，3，4，…，25）26英文字母与数字对照表进行加密维吉尼亚（Vigenere）密码表

ABCDEFGHIJKLMNOPQRSTUVWXYZ

A

ABCDEFGHIJKLMNOPQRSTUVWXYZ

B

BCDEFGHIJKLMNOPQRSTUVWXYZA

C

CDEFGHIJKLMNOPQRSTUVWXYZAB………

O

OPQRSTUVWXYZABCDEFGHIJKLMN………

X

XYZABCDEFGHIJKLMNOPQRSTUVW

Y

YZABCDEFGHIJKLMNOPQRSTUVWX

Z

ZABCDEFGHIJKLMNOPQRSTUVWXY

维吉尼亚加密法：置换加密法给出一个用于加密的密钥（单词），比如:welcome加密过程：以明文字母选择列，以密钥字母选择行，两者的交点就

是加密生成的密文。

解密过程：以密钥字母选择行，从中找到密文字母，密文字母所在

列的列名即为明文字母。

例：以your为密钥，加密明文howareyou 明文P=

howareyou

密钥K=

youryoury 密文C=

fcqrpssfs维吉尼亚加密法：密钥控制下的矩阵加密法矩阵加密法的操作过程：给出1个密钥单词，其字符数假如为：9，并根据其每个字符在字母表中位置给出其序号。把明文按9列排成一个矩阵在明文矩阵的上方写密钥及其序号根据密钥中字符的序号，按列读出明文，即为加密的密文解密：根据密钥、密文算得行宽，写出矩阵，得到明文例如，用密钥单词compute，对明文MATHEMATICALMODELINGISUSEFUL加密：根据密钥的字符数7，把明文看成一个n行7列的矩阵

根据密钥字符的序号，依次按列读出就得到密文MTDSAIEUTCLSHAIEELEFMMNUAOIL

1、密码学的几个术语明文(PlainText)：

准备加密的消息(Message)；加密（Encryption）：

用某种方法伪装消息以隐藏它的内容的过程；密文(Cipher)：

被加密的消息；解密（Decryption）：

把密文转变为明文的过程；加密算法：

用来加密和解密的数学函数（变换函数）

比如：c=E(m),m=D(c),D(E(m))=m3.1.2

密码系统密钥(key):参与变换的参数，算法中的一个变量，或一些关键信息比如：c=EK(m)，m=DK(c)，DK(EK(m))=m密钥：加密密钥与解密密钥

密码学（Cryptology）：

密码学可看作数学的一个分支，包括：密码编码学密码分析学密码编码技术和密码分析技术是相互依存、相互支持、密不可分的两个方面。2、加密和解密的过程3一个密码系统或密码体制的组成：通常一个密码体制表示成一个五元组:（M，C，K，E，D）其中：

⑴M：是可能明文的有限集，称为明文空间⑵C：是可能密文的有限集，称为密文空间⑶K：是一切可能密钥构成的有限集，称为密钥空间⑷E：加密算法或加密函数：

Ek：M->C，或EK（M）=C

比如，Caesar密码中：C=EK（M）=（M+K）MOD26⑸D：解密算法或解密函数：

Dk:C->M，或DK（C）=M

比如，Caesar密码中：M=DK(C)=(C-K)MOD26

满足：Dk（Ek（M））=M密码系统的安全性基于密钥的安全性，而不是基于算法安全性，即密钥要保密，算法可以公开！3.1.3密码的分类1、按应用的技术或历史发展阶段划分：

密码的发展经历了：（1）手工密码（2）机械密码（3）电子机内乱密码（4）计算机密码2、按保密程度划分：

⑴理论上保密的密码；⑵实际上保密的密码；⑶不保密的密码

3.1.3密码的分类3、按密钥方式划分：⑴对称密码体制（如DES、AES）；⑵公开密钥密码体制（RSA、ECC）。4、按明文形态：⑴

模拟型密码⑵数字型密码5、按编制原理划分：⑴替换；⑵置换3.1.4近代加密技术1、对称加密算法对称加密算法（symmetricalgorithm），也称为传统密码算法或单钥算法。对称加密算法的主要特征：

其加密密钥与解密密钥相同或很容易相互推算出来。

整个通讯的安全性依赖于密钥的保密，而不是算法的保密对称加密算法的优缺点：主要优点:

加密速度快，计算量小、加密效率高，硬件容

易实现和大规模生产；

主要缺点：密钥的分发与管理比较困难，当通信的人数

增加时，密钥数目急剧膨胀：n(n-1)/2，100人50003.1.4近代加密技术对称加密过程发送方用自己的私有密钥对要发送的信息进行加密；发送方将加密后的信息通过网络传送给接收方；接收方用发送方进行加密的那把密钥，对接收到的加密信息进行解密，得到信息明文。秘密渠道对称加密算法分类：

序列密码算法分组密码算法对称加密算法用到的两种技术：混乱扩散非对称加密算法（AsynmetricAlgorithm）也称公开密钥算法。主要特征：公开密钥体制把加密密钥和解密密钥分离，并且通信的每一方都拥有这样的一对密钥；加密密钥可以像电话号码一样对外公开，由发送方用来加密要发送的原始数据；称为公钥解密密钥则由接收方秘密保存，作为解密时的私用密钥。加、解密过程发送方用接收方公开密钥对要发送的信息进行加密；发送方将加密后的信息通过网络传送给接收方；接收方用自己的私有密钥对接收到的加密信息进行解密，得到信息明文。2、非对称加密体制（公开密钥体制）公开密钥体制优缺点：主要优点：就是不需要对密钥通信进行保密，所需传输的只有公开密钥；主要缺陷：在于其加密和解密的运算时间比较长，这在一定程度上限制了它的应用范围。2、非对称加密体制公开密钥体制主要用途：

数据的加、解密：

发送消息方用接收方的公钥加密消息；接收方用自己的私钥解密消息。数字签名：

接收方用发送方的公钥来认证消息的真实性和来源。密钥交换：

用于通讯双方进行会话密钥的交换。3.1.5密码的破译密码分析密码分析是在不知道密钥的情况下，利用数学方法从密文中恢复出明文或找到密钥的方法;密码分析也可以发现密码体制的弱点。攻击对密钥或密文进行分析的尝试称为攻击。攻击方法分类：

密钥的穷尽搜索；

密码分析；其它方法。3.1.5密码的破译1、密钥的穷尽搜索破译密文就是尝试所有可能的密钥组合。

虽然大多数的密钥尝试都是失败的，但最终有一个密钥让破译者得到原文，这个过程称为密钥的穷尽搜索。在相同条件下，密钥越长，破译密码的难度就越大，密码系统就越可靠。比如，

PGP，使用128位密钥进行加密，所有密钥排列数是2128，每秒钟尝试1亿把密钥，也需要1014年完成。

3.1.5密码的破译2、密码分析

已知明文的破译方法在某些情况下，攻击者可能部分或全部地知道加密的明文。这种知情度可能使攻击者能够较轻松地使用该协议确定密钥和破译其它消息。典型的已知明文暴露的示例是：攻击者知道加密的内容是由包含标准头的文件类型组成的，或者攻击者知道消息与一个命名主题相关。在其它情况下，整个消息也可能会以破解密码以外的方式泄露，这有助于攻击者破解其它消息。3.1.5密码的破译2、密码分析已知明文的破译方法密码分析者掌握了一段明文和对应的密文，企图从中找出加密的密钥。实际中获得明文对应的密文是可能的。比如，电子邮件选定明文的破译方法选定明文的破译者知道了加密算法；他选定一段明文，设法让加密者加密选定的明文，并得到加密结果，即知道选定的明文和对应的密文。企图找出加密的密钥。

3.1.5密码的破译2、密码分析选定密文的破译方法破译者已知选定的密文和对应的、已解密的原文，即知道选择的密文和对应的明文；企图从中找出加密的密钥。差别比较分析破译方法破译者选定一组相似且差别微小的明文；设法让加密进行加密，并得到加密结果；企图从中找出加密的密钥；

3．其他密码破译方法“窥视”或“偷窃”密钥内容；从用户生活和工作环境的中获得未加密的保密信息，比如进行“垃圾分析”；用拷打、威胁、骚扰或其它强迫方式让用户而被迫泄露密钥和秘密。通过贿赂、收买、勾引或诱惑得到密钥和秘密。4、密码的破译举例-字母频率攻击

古代密码多数可以通过字母频率攻击来破解，以恺撒密码为例，可以通过计算机字母出现的频率推测出密钥k=3,比如：原文：pandasoftware密文：sdqgdvriwzduh⑴找出密文中出现频率最高的字母：“d”；⑵英语中最常出现的字母是“a”和“e”，分别进行检验；⑶若“d“是“e”：“d”在“e”的后面第25位，然后用25来

解密其它密文，即密文向左移动25位，得到明文如下：

原文：terhewsjxaevi

这个字母序列没有丝毫意义。⑷若“d”是“a”：因为“d”是“a”后的第3位，然后用3来解密其它密文，即密文向左移动3位，得到明文如下：

密文：sdqgdvriwzduh原文：pandasoftware破译成功！3.2古典密码学古典密码主要有：代换密码法与置换密码法3.2.1代换密码代换密码的特点是：依据一定的规则，明文字母被不同的密文字母所代替；明文的原有顺序在密文中被保留。

1、移位密码法移位密码基于数论中的模运算。如下：令m={a,b,c,……，z}，C={A,B,C,……，Z}，K={1，2，……，25}，加密变换：Ek（x）=（x+k）mod26解密变换：Dk（y）=（y-k）mod26Caesar（凯撒）密码就是当K=3时的代替密码法维吉尼亚加密法也是代替密码加密法。2、单表代换密码单表代换密码的基本思想是：列出明文字母与密文字母的一一对应关系。明文abcdefghijklm密文WJANDYUQIBCEF明文nopqrstuvwxyz密文GHKLMOPRSTVXZ例如：明文为:n

e

t

w

o

r

k

s

e

c

u

r

i

t

y,相应密文为：

G

D

P

T

H

M

C

O

D

A

R

M

I

P

X3、多表替换密码Vigenere密码是一种典型的多表替换密码算法。算法如下：设密钥：K=k1k2……kn，明文M=m1m2……mn,加密变换:ci≡（mi+ki）mod26,i=1,2,……,n解密变换：mi≡（ci-ki）mod26,i=1,2,……,n例如：明文：

M=cipherblock,密钥为：K=hit

3、多表替换密码

⑴根据密钥序列的个数3，把明文划分成长度为3的序列：

cipherblock⑵加密算法：每个序列中的字母分别与密钥序列中相应字母进行

模26运算，得密文：JQIOMKITHJS比如：⑴cip→2815⑵hit→7819⑶（2＋7）mod26=9→J⑷（8＋8）mod26=16→Q⑸（15＋19）mod26=8→I⑹cip→JQI26英文字母与数字对照表3.2.2置换密码置换密码的特点：是保持明文的所有字母不变，只是利用置换改变明文原来字母的排列顺序，比如置换密码体制定义如下：令m为一正整数，P=C={A,B,C,……Z}，对任意的置换π（密钥），定义:加密变换：Eπ（x1,x2,……,xm）=（xπ（1）,xπ（2）……,xπ（m））,解密变换：Dπ（y1,y2,……,ym）=（xπ-1（1）,xπ-1（2）……,xπ-1（m））,密钥控制下的矩阵换位加密法就是置换加密法

密钥控制下的矩阵加密法矩阵加密法的操作过程：给出1个密钥单词，其字符数假如为：9，并根据其每个字符在字母表中位置给出其序号。把明文按9列排成一个矩阵在明文矩阵的上方写密钥及其序号根据密钥中字符的序号，按列读出明文，即为加密的密文解密：根据密钥、密文算得行宽，写出矩阵，得到明文例如，用密钥单词compute，对明文MATHEMATICALMODELINGISUSEFUL加密：根据密钥的字符数7，把明文看成一个n行7列的矩阵

根据密钥字符的序号，依次按列读出就得到密文MTDSAIEUTCLSHAIEELEFMMNUAOIL置换密码算法的分析密文字符和明文字符相同，只是顺序被打乱密文和明文中的字母出现频率相同，使得分析者可以很使用多轮置换加密可提高安全性3.3对称密码学3.3.1对称密码概述加密和解密使用相同的密钥：KE=KD密钥必须使用秘密的信道进行分配对称密码算法可以分为两类：分组密码（BlockCipher）序列密码（StreamCipher）分组密码：将明文分成固定长度的组。典型分组长度是64位，用同一密钥和算法对每一分组加密。加密以分组为单位。序列密码/流密码：每次加密一位或一字节的明文，序列密码使用尽可能长的密钥。加密是以位或字节为单位。

3.3对称密码学接收方发送方mm加密E解密Dc=Ek(m)m=Dk(c)密钥分配（秘密信道）kk特点：⑴加密密钥与解密密钥相同；⑵密钥要通过秘密信道转送3.3.2Feistel密码结构1、扩散和混乱扩散和混乱是由Shannon提出的设计密码系统的两个基本方法。目的：抵抗攻击者对密码的统计分析。明文的某些统计特性-如果在密文中反映了出来-攻击者就可能得到加密密钥的一部分或一个可能的密钥集合扩散：就是将明文的统计特性扩散到密文中去。实现时使得密文的每一位由明文中的多位产生。这样明文的统计特性就被散布开了，攻击者难以通过统计分析得到有用的信息。通常扩散的方法：是通过多次置换或复杂的置换算法1、扩散和混乱混乱：就是使密文和密钥之间的统计关系变得尽可能复杂，使攻击者无法得到密钥。攻击者即便得到了密文之间的某些统计关系，也难以得到密钥。

通常的混乱方法：是通过多次代换或复杂的代换算法。2、Feistel密码结构及特点

（1）

将明文的分组分为左右两个部分：L0，R0；

数据的这两部分用一个函数F，进行n轮处理（迭代运算）

把经过n轮处理后的两部分，再结合起来生成密文分组；（2）第i轮把其上一轮产生的Li-1和Ri-1，用密码K产生的子密钥Ki作为输入，进行处理。一般说来，子密钥Ki与K不同，Ki是用子密钥生成算法从密钥K生成的；其第i轮迭代的函数为：Li=Ri-1

Ri=Li-1

⊕F(Ri-1,Ki)其中：Ki是第i轮的子密钥，“⊕”表示异或运算，F表示轮函数。（3）每一轮的处理的结构都相同：每一轮都是先对数据的右半部分应用处理函数F；然后对函数输出结果和数据的左半部分取异或（XOR）。（4）处理函数F：对每轮处理都有相同的通用结构；由循环子密钥Ki来区分。（5）在置换之后，执行由数据两部分互换构成的交换；（6）解密过程与加密过程基本相同。规则如下：用密文作为算法的输入，但以相反顺序使用子密钥Ki；（7）加密和解密不需要用两种不同的方法。异或运算（XOR)运算规则：操作数同，则为0；操作数异，则为1一个简单的加密算法—异或运算：

密文：01

10解密：密钥：

0101

明文：

0011已知明文、密文，怎样求得密钥？C=MKM=CK异或运算（不带进位加法）： 明文:

0011

加密： 密钥:

0101

密文：

01

10K=CM3.3.3DES算法1、DES算法概述IBM公司于70年代初提出，1977年1月被美国政府规定为用来对数据进行加密的国家标准（DataEncryptionStandard）。目前，DES算法在ATM、磁卡及智能卡（IC卡）、加油站、高速公路收费站等领域被广泛应用。DES是一种对称密钥算法，DES的整个体制是公开的，系统的安全性依赖于密钥，密钥可以是任意的56bit数(加上奇偶校验，通常写成64bits)是一种分组加密算法，明文、密文都是按64bits进行分组基本思想：混乱（Confusion）和扩散（Diffusion）使用标准的算术和逻辑运算。2、DES算法的基本过程：

初始置换IP

将明文组分为左右两

部分，每部分32位，以

L0，R0表示进行16轮运算（）：

将数据和密钥结合

16轮后，左、右两部

分连接在一起再进行一个末置换，

得到密文初始置换IPk1k2k16IP-1L0R0L1=R0R1=L0(R0,K1)L2=R1R2=L1(R1,K2)L15=R14R15=L14(R14,K15)R16=L15(R15,K16)L16=R1564位明文64位密文2、DES算法流程如图所示第1步：变换明文。对给定的64位的明文M，首先通过一个初始置换IP表来重新排列M，从而构造出64位的M0：

M0=IP(M)=L0＋R0，

其中：L0表示M0的前32位，R0表示M0的后32位。第2步：按照规则进行运算，规则为：Li=Ri-1Ri=Li⊕F(Ri-1,Ki)（i=1,2,3,…,16）其中：F表示一种算法，Ki是第I轮运算时用的子密钥。第3步：对L16＋R16，利用IP-1作逆置换，就得到了密文。3DES算法实现加密需要3个步骤初始置换IPk1k2k16IP-1L0R0L1=R0R1=L0(R0,K1)L2=R1R2=L1(R1,K2)L15=R14R15=L14(R14,K15)R16=L15(R15,K16)L16=R1564位明文64位密文4、DES的6个关键点：IP置换表IP-1逆置换表，运算过程，函数F，子密钥Ki的生成，⑥S盒的工作原理。

①IP表置换表：4×16

输入的64位数据按IP表置换进行重新组合。然后把输出分成：

L0和R0两部分。

（1）IP置换表和IP-1逆置换表初始置换将明文的第58位换到第1位；第50位换到第2位第42位换到第3位；第1位换到第40位（1）IP置换表和IP-1逆置换表②IP-1逆置换表：4×16逆置换将16次迭代后得到的L16和R16：

第1位换到第58位；第2位换到第50位第3位换到第42位；第40位换到第1位经过初始置换后，将置换后明文分成两部分。进行16轮完全

相同的运算。在运算过程中数据与子密钥ki结合。下面是第一轮运算过程：k1L0R0L1=R0R1=L0(R0,K1)

函数的输出经过一个异或运算，和左半部分结合，其结果

成为新的右半部分，原来的右半部分成为新的左半部分。（2）运算过程第i轮的运算过程：假设Li和Ri是第i轮

运算结果的左半部

分和右半部分，Ki是第i轮的48位子

密钥，第i轮迭代过程可

以如右图所示。Li-1(32bit)Ri-1(32bit)扩展置换ES盒代替P-盒置换Ri(32bit)Li(32bit)Ki48bitRi=Li-1(Ri-1,Ki)Li=Ri-132位48位48位32位32位32位1、函数f有两个输入：⑴32位的Ri-1

；⑵

48位Ki

，2、函数f要处理：⑴1个运算；⑵四个变换；⑶函数f

f函数的处理流程图

①E变换的算法是从Ri-1的32位中选取某些位，加上原32位，构成48位，即E将32位扩展为48位。变换规则见下表。

32|1234|54|5678|98|9101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|1子密钥Ki的生成DES算法由64（56）位密钥产生16轮的48位子密钥。在每一轮运算过程中，使用不同的子密钥。每一轮子密钥生成过程见右图：64位密钥置换选择1C0(28位)D0(28位)循环左移循环左移C1(28位)D1(28位)置换选择2循环左移循环左移Ci(28位)Di(28位)置换选择256位k148位ki48位56位压缩置换。将56位输入置换为48位。将64位密钥减至56位。然后进行一次密钥置换。各轮循环移动的次数由轮数决定。57，49，41，33，25，17，9，1，58，50，42，34，26，18，10，

2，59，51，43，35，27，19，11，3，60，52，44，36，63，55，47，39，31，23，15，7，62，54，46，38，30，22，14，6，61，53，45，37，29，21，13，5，28，20，12，4置换选择1：4×14由于不考虑每个字节的第8位，DES的密钥由64位减至56位。每个字节的第8位可作为奇偶校验以确保密钥不发生错误。64位密钥置换选择1

经过置换选择1，将输出的56位密钥分成两部分，每部分28位。然后，根据轮数，将两部分分别循环左移1位或2位。如表所示。每轮移动的位数，见下表

轮1

2345678910111213141516位数1122222212

222

221C0(28位)D0(28位)循环左移循环左移C1(28位)D1(28位)64位密钥置换选择1第1轮：对C0作左移1位得到C1，对D0作左移1位得到D1，对C1D1应用PC2进行选位，得到K1。PC2如下

第2轮：对C1和D1作左移1位得到C2和D2，进一步对C2、D2应用进行选位，得到K2。如此继续，分别得到K3，K4，…，K16。

移动后，从56位输出中选出48位，称为压缩换位。如表所示。压缩换位14，17，11，24，1，5，3，28，15，6，21，10，23，19，12，4，26，8，16，7，27，20，13，2，41，52，31，37，47，55，30，40，51，45，33，48，44，49，39，56，34，53，46，42，50，36，29，32

64位密钥置换选择1C0(28位)D0(28位)循环左移循环左移C1(28位)D1(28位)置换选择256位k148位④S盒替换将48-bit输入转为32-bit的输出48-位输入32-位输出S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8

S代换运算由8个不同的替换盒（S盒）完成。每个S盒有6位输入，4位输出。

48位的输入被分为8个6位的分组，每一分组对应一个S-盒,用来进行代替操作。经过S盒代替，形成8个4位分组，把48位的输入变成32位输出。其过程如下：48-bit组被分成8个6-bit组，每一个6-bit组作为一个S盒的输入，输出为一个4-bit组。由输入的位数计算机其输出结果：每个S盒是一个4×16的矩阵：行号、列号由0开始由6-bit输入数计算出两个数：用6-bit数的首、末两位得到的数：m，去选择行用6-bit数中间的四位得到的数：n，去选择列m、n的交叉点即为输入的数的变换结果

例如，假设S-盒6的输入为：110011。第1位和最后一位组合形成了11，是十进制的3，它对应着

S-盒6的第3行。中间的4位组合形成了1001，是十进制的9，它对应着S-盒6

的第9列。而S-盒6的第3行第9列处的数是14，得到输出值为：1110。输入6位，如何得到4位？以S-盒6说明12，1，10，15，9，2，6，8，0，13，3，4，14，7，5，11，10，15，4，2，7，12，9，5，6，1，13，14，0，11，3，8，

9，14，15，5，2，8，12，3，7，0，4，10，1，13，11，6，

4，3，2，12，9，5，15，10，11，14，1，7，6，0，8，13⑤P-盒置换

16，7，20，21，29，12，28，17，1，15，23，26，5，18，31，10，

2，8，24，14，32，27，3，9，19，13，30，6，22，11，

4，25例如，第21位移到了第4位，第4位移到了第31位。⑷末置换

末置换是初始置换的逆过程。

DES在最后一轮迭代过程后，左半部分和右半部分并不交换，而是将R16和L16并在一起形成一个分组作为末置换的输入。末置换40，8，48，16，56，24，64，32，39，7，47，15，55，23，63，31，38，6，46，14，54，22，62，30，37，5，45，13，53，21，61，29，36，4，44，12，52，20，60，28，35，3，43，11，51，19，59，27，34，2，42，10，50，18，58，26，33，1，41，9，49，17，57，25DES解密

DES的解密和加密使用相同的算法。解密过程中使用的子密钥顺序与加密过程中使用的密钥顺序相反。Li-1=Ri(Li,Ki)Ri-1=Li2、DES算法的安全性

DES算法正式公开发表以后，引起了一场激烈的争论。1977年Diffie和Hellman提出,若制造一个每秒能测试106个密钥的大规模芯片，这种芯片的机器大约一天就可以搜索DES算法的整个密钥空间；制造这样的机器需要两千万美元。1993年R.Session和M.Wiener给出了一个非常详细的密钥搜索机器的设计方案，它基于并行的密钥搜索芯片。此芯片每秒测试5×107个密钥，5760个这样的芯片组成的系统平均1.5天即可找到密钥，如果利用10个这样的系统，搜索时间可以降到2.5小时。制作10个这样的系统大概需要100万元。1997年1月28日，美国的RSA数据安全公司在互联网上开展了一项名为“密钥挑战”的竞赛：悬赏一万美元，破解一段用56位密钥加密的DES密文。计划公布后引起了网络用户的强烈响应。一位名叫RockeVerser的程序员设计了一个可以通过互联网分段运行的密钥穷举搜索程序，组织一个称为DESHALL的搜索行动，成千上万的志愿者加入到计划中；在计划实施的第96天，即挑战赛计划公布的第140天，1997年6月17日晚上10点39分，美国盐湖城Inetz公司的职员MichaelSanders成功地找到了密钥，在计算机上显示了明文：“Theunknownmessageis:Strongcryptographymakestheworldasaferplace”。世界在Internet面前变得不安全起来了。Internet仅仅应用了闲散的资源，毫无代价地破解了DES的密码，这是对密码方法的挑战，也是Internet超级计算能力的显示。尽管DES有这样那样的不足，但是作为第一个公开密码算法的密码体制成功地完成了它的使命，它在密码学发展历史上具有重要的地位。3、增强的DES加密算法DES一个致命的缺陷就是密钥长度短，而DES又不支持变长密钥，对于当前的计算能力，56位的密钥长度已经抗不住穷举攻击。但算法可以一次使用多个密钥，从而等同于更长的密钥。对DES进行复合，强化它的抗攻击能力；3、增强的DES加密算法

C=EK2[EK1[M]]↔M=DK1[DK2[C]]MEK1XEK2C(a)加密CDK2XDK1M(b)解密

二重DES

两个密钥的三重DES

C=EK1[DK2[EK1[M]]]↔M=DK1[EK2[DK1[C]]]MDK2BEK1C(a)加密(b)解密EK1ACEK2ADK1MDK1B三个密钥的三重DES

C=EK3[DK2[EK1[M]]]↔M=DK1[EK2[DK3[C]]]MDK2BEK1C(a)加密(b)解密EK3ACEK2ADK3MDK1B4、国际数据加密算法--IDEA1990年瑞士联邦技术学院的XueJiaLai和著名密码学家JamesMassey开发出PES，即建议的加密标准的，是IDEA的雏形1991年设计者对PES强化成为IPES，即改进的建议加密标准1992年更名为IDEA，即国际数据加密标准明文分组：64位，密钥长度：128位类似于DES，IDEA也是一种数据块加密算法，它设计了一系列加密轮次，每轮加密都使用从完整的加密密钥中生成一个子密钥。5、高级加密标准—AES算法1997年4月15日，NIST（美国国家标准技术局）征集AES（AdvancedEncryptionStandard）以代替DES算法。1998年8月20日举办了首届AES候选会议，选出了15个候选算法。1999年8月9日，NIST宣布了第二轮AES的优胜者：MARS，RC6，Rijndael，SERPENT，Twofish。2000年10月2日，NIST最终确定Rijndael作为AES算法。（比利时密码专家JoanDaemen和VincentRijmen）

2001年11月26日NIST正式宣布AES为美国政府的新加密标准，该决定在2002年5月26日生效。AES算法特点

(1)密钥长度可变：Rijndael的信息块长度和加密密钥长度都是可变的，都可以是128位，192位和256位(2)混合的运算：AES每轮要经过四次变换：

ByteSub()字节代换

ShiftRows()行移位

MixColumns()列混合

AddRoundKey()轮密钥的添加

(3)能有效抵制目前已知的攻击算法

3.4非对称密码体制3.4.1、公开密钥加密算法（RSA）概述 非对称密码体制的算法中最着名的代表是RSA系统。公开密钥加密算法RSA，于1978年，由美国麻省理工学院(MIT)的Rivest(李维斯特)、Shamir(沙米尔)、Adleman(艾德曼)在题为《获得数字签名和公开钥密码系统的方法》的论文中提出。RSA一种分组密码体制。其名称RSA来自于三个发明者的姓名首字母。公开密钥加密算法（RSA）的安全性它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决。

RSA算法设计者

公钥和私钥是一对大素数P、Q的函数，从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积。

RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。RSA的安全性一直未能得到理论上的证明。但它经历了各种攻击，至今未被完全攻破。因此可以确定RSA算法的安全性3.4.2RSA算法的实现步骤RSA算法描述如下：（1）选取不同且足够大的两个素数：p和q；（2）计算这两个素数的乘积：n

=p×q；（3）计算：φ（n）=(P－1)(q－1)；（4）选择一个随机数e，满足：1＜e＜φ(n)，并且e

和φ(n)互质，即gcd（e,φ(n)）=1。e即为加密密钥（5）计算：d×e≡1modφ(n)，可得到数d，d即为解密密钥（6）公钥PK={n,e}，私钥SK={n,d}(7)加密：用（n,e）计算：c=memodn

（8）解密：用（n,d)

计算：m=cdmodn

关于：d×e≡1modφ(n)的说明"≡"是数论中表示同余的符号。公式中，"≡"符号的左边必须和符号右边同余，也就是两边模运算结果相同。显而易见，不管φ(n)取什么值，"≡"的右边：1modφ(n)的结果都等于1；因此，"≡"的左边d×e的积做模运算后的结果也必须等于1。计算出d的值，让这个同余等式能够成立。RSA算法流程图

密钥的生成选择p,q为互异素数计算n=p*q，(n)=(p-1)*(q-1)选择整数e使e与(n)互质计算d，使满足d*e=1mod(n)公钥PK={n,e}私钥SK={n,d}RSA算法举例：取P=47,q=71,则n=p*q=3337,(n)=(p-1)*(q-1)=46*70=3220随机选取e，使e与(n)互质，取e=79,

则由：e*d

mod(n)=1，79*dmod3220

=1得d=1019则可得：公钥pk={n,e}={3337,79}私钥sk={n,d}={3337,1019}取：p=3，q=11，得出：n=p×q=3×11=33；φ(n)=(p-1)(q-1)=2×10=20；可以用试算的办法来寻找d：由e×d≡1modφ(n)→e×d=k×ф（n）＋1取e=3，则有：

3d=k×20＋1，将1，2，3，…，依次代入k，求出d。当取k=1，得d=7（当取k=4，得d=27)即，当e=3，d=7时，e×d≡1modφ(n)同余等式成立。从而我们可以设计出一对公私密钥：加密密钥（公钥）为：(e,n)=(3,33)；解密密钥（私钥）为：(d,n)=(7,33)。如何计算d

?1、计算公钥与私钥①选择素数：

p=17q=11②计算：n=pq=17×11=187③计算：ø（n）=（p–1）（q-1）=16×10=160④选择e：

gcd（e,160）=1;选择e=7⑤确定d：

d×e≡1mod160且d<160，d=23

因为23×7=161=1×160+1⑥公钥：KU={7,187}⑦私钥：KR={23,187}假设给定的消息为：M=88，则加密:C=887mod187=11解密:M=1123mod187=88一个实际的例子来帮助理解RSA算法2、英文数字化。将明文信息数字化，并将明文按两个数字分组。假定明文英文字母编码表为按字母顺序排列数值，即：若要对sias加密，则分组后的明文信息：19，09，01，193、明文加密用户B的加密密钥{7,187},将数字化明文分组信息加密成密文。s,i,a,s=19，09，01，19由C=Memodn得：4、密文解密

用户B的解密密钥{23,187}，收到密文，若将其解密，只需要计算：M≡Cdmodn，即：用户B得到明文信息为：19，09，01，19。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“sias”。当然，RSA的实际运用要比这复杂得多，由于RSA算法的公钥、私钥的长度（模长度）要到1024位甚至2048位才能保证安全，因此，p、q、e的选取、公钥私钥的生成，加密解密模指数运算都有一定的计算程序，需要仰仗计算机高速完成。思考1：对英文字母能用其它方法编码吗？思考2：如何对汉字信息使用RSA加密算法加密？

RSA算法的安全性在RSA密码应用中，公钥KU是被公开的，即e和n的数值可以被分析者得到。破解RSA密码的问题就是从已知的e和n（n等于pq），想法求出d，这样就可以得到私钥来破解密文。从公式：d*e≡1mod((p-1)(q-1))，可以看出，密码破解的实质问题是：从pq的数值，去求出(p-1)和(q-1)。换句话说，只要求出p和q的值，我们就能求出d的值而得到私钥。当p和q是一个大素数的时候，从它们的积pq去分解因子p和q，这是一个公认的数学难题。比如当pq大到1024位时，迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。RSA从提出到现在三十余年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。然而，虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。此外，RSA的缺点还有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。因此，使用RSA只能加密少量数据，大量的数据加密还要靠对称密码算法。2009年12月12日，编号为RSA-768（768bits）数被成功分解。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。RSA-768表示如下：1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

=

3347807169895689878604416984821269081770479498371376856891

2431388982883793878002287614711652531743087737814467999489

×

3674604366679959042824463379962795263227915816434308764267

60322838157396665112792333734171433968102700927987363089173.6.2算法攻击举例

常见的攻击包括：1.字母频率攻击；2.对RSA算法的攻击；3.对单向散列算法的“生日”攻击；4.字典攻击和重放攻击。3.6.2.2对RSA算法的攻击这些算法代表了人们对大数分解（也就是对RSA攻击）的探索历程。最好的算法具有超多项式率（次指数率）的时间复杂度，NFS具有最接近于多项式率的表现。大数分解仍然是困难的，可是随着数论和计算能力的发展，它变得容易了。1977年，RonRivest说过分解一个125位的数需要花费4*1013年。在1994年RSA129被分解了，是利用internet上一些计算机的空闲CPU周期一共花了8个月完成的。1995年，Blacknet密钥被分解，用了几十台工作站和一台MarPar，历时3个月。随着时间的推移，可能被分解的密钥长度还会增加。下面是几种针对RSA有效的攻击方法，攻击的是加密协议环节上的漏洞，而不是RSA本身的。

对RSA算法的攻击选择密文攻击由于RSA密文是通过公开渠道传播的，攻击者可以获取密文。我们假设攻击者为A，密文收件人为T，A得到了发往T的一份密文c，他想不通过分解质因数的方法得到明文。换句话说，他需要m=cd。为了恢复m，他找一个随机数r，r<n，当然他有T的公匙(e,n)。他计算：x=remodn（用T的公匙加密r）y=x*cmodn（将临时密文x与c相乘）t=r-1modn

A知道RSA具有下面的一个特性：如果x=remodn，那么r=xdmodn选择密文攻击 因此他想办法让T对y用T自己的私钥签名（实际上就是把y解密了），然后将结果u=ydmodn寄回给A。A只要简单地计算：m=t*umodn上面结论的推导是这样的：t*umodn=(r-1)*(xd)(cd)modn=(cd)modn=m 要防止这种攻击的办法就是不要对外来的随机信息签名，或者只对信息的MD5特征值签名。在这里就很容易明白为什么要强调MD5的单向性了，因为MD5的结果是不能预定的，就是说A难以凑出一份刚好能产生y这样的MD5特征值的明文来让T签名。

对RSA算法的攻击过小的加密指数e e是一个小数并不降低RSA的安全性。从计算速度考虑，e越小越好。可是，当明文也是一个很小的数时就会出现问题。例如我们取e=3，而且我们的明文m比n的三次方根要小，那么密文c=memodn就会等于m3。这样只要对密文开三次方就可以得到明文。公共模数攻击 还有一些对RSA的攻击，像公共模数攻击。它是指几个用户公用一个模数n，各自有自己的e和d，在几个用户之间公用n会使攻击者能够不用分解n而恢复明文。

对RSA算法的攻击RSA的计时攻击法 这是一种另辟蹊径的方法，是由PaulKocher发表的。可以发现，RSA的基本运算是乘方取模，这种运算的特点是耗费时间，精确取决于乘方次数。这样如果A能够监视到RSA解密的过程，并对它计时，他就能算出d来。Rivest说，抵御这种攻击最简单的方法就是使RSA在基本运算上花费均等的时间，而与操作数无关。其次在加密前对数据做一个变换（花费恒定时间），在解密端做逆变换，这样总时间就不再依赖于操作数了。字典攻击和重放攻击字典攻击 对于用单向函数加密的口令文件而言，攻击者可以编制一个包括100万个常用口令的口令表，然后用单向函数对这100万个口令进行运算，并将结果保存起来。只要攻击者偷出加密后的口令文件，将它与自己的可能的口令文件进行比较，再观察哪个能匹配，就可以成功破解口令了。重放攻击 重放攻击指的是收集特定的IP包，篡改其数据，然后再一一重新发送，欺骗接收的