第4讲 密码学概论

第4讲密码学概论课程主要内容密码体制基本形式移位密码替换密码仿射密码一次一密方案密码分析2§1密码体制基本形式Alice加密机解密机Bob安全信道密钥源Oscarxyxk1密钥源k2不安全信道密码分析加密通信的模型密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。3密码系统的定义：密码体制是这样的一个5元组

{M，C，K，E，D}，且满足如下的条件：1.M是所有可能明文(消息)的集合；（明文空间）2.C是所有可能的密文的集合；（密文空间）3.K是一个可能密钥的有限集；（密钥空间）4.满足以下定义：§1密码体制基本形式4密码系统的定义：加密：解密：并且有：注意：所有算法的安全性基于密钥的安全性，而不是基于算法细节的安全性，即算法可以公开！§1密码体制基本形式5§1密码体制基本形式1）Alice要将明文Ｘ在不安全信道上发给Bob，设X=x1x2…

xn，其中xi∈P,Alice用加密算法ek作yi=ek(xi)(1≤i≤n)，结果的密文是Y=y1y2…yn

在信道上发送，Bob收到后解密：xi=dk(yi)得到明文X=x1x2…

xn。2）加密函数ek必须是单射函数，就是一对一的函数。3）若P=C，则ek为一个置换。4）好的密钥算法是唯密钥而保密的。5）若Alice和Bob在一次通信中使用相同的密钥，则这个加密体制为对称的，否则称为非对称的。61、用于转换纯文本到密码的类型

替代（substitution）移位（transposition）2、密钥的种类对称，单密钥，秘密密钥不对称，双密钥,公开密钥加密

3、以处理纯文本文件的方法分组密码（blockcipher）流密码（streamcipher）密码系统(CryptographySystem)的分类§1密码体制基本形式7单钥体制(对称密码)K1＝K2－－－根据密钥的种类分类：明文abc加密器密文#@&解密器明文abc相同

双钥体制(非对称密码)K1≠K2明文abc加密器密文#@&解密器明文abc不同

8

密码编码学是密码体制的设计学，而密码分析学则是在未知密钥的情况下从密文推演出明文或密钥的技术。密码编码学与密码分析学合起来即为密码学密码学及相关概念

如果不论截取者获得了多少密文，但在密文中都没有足够的信息来惟一地确定出对应的明文，则这一密码体制称为无条件安全的，或称为理论上是不可破的。但是在无任何限制的条件下，目前几乎所有实用的密码体制均是可破的。因此，人们关心的是要研制出在计算上(而不是在理论上)是不可破的密码体制。如果一个密码体制中的密码不能被可以使用的计算资源破译，则这一密码体制称为在计算上是安全的。9密码体制的特征:对密文破译攻击极为困难；在有效地防破译的前提下，密钥长度应很小；加密、解密的操作流程简便易行；错码率及错码的扩散程度低；加密后原信息的长度不受影响。§1密码体制基本形式10数据加密标准DES（DataEncryptionStandard）公开密钥密码体制（publickeycrypto-system）成为近代密码学发展史上的两个重要里程碑。近代密码学发展§1密码体制基本形式一个密码系统采用的基本工作方式称为密码体制。密码体制从原理上可分为两大类：

对称密钥密码体制（单钥、常规）非对称密钥密码体制（双钥、公开）11在发端，明文X用加密算法E和加密密钥K得到密文

C

EK(P)在传送过程中可能出现密文截取者。截取者又称为攻击者或入侵者。P’或K’在收端，利用解密算法D和解密密钥K，解出明文为

DK(C)

DK(EK(P))

P对称（常规）密码体制12

k

k明文

密文

解密后的明文

加密Ｅ解密Ｄ密钥产生器加密和解密表示为：ＥＫ(Ｍ)＝ＣＤＫ(Ｃ)＝Ｍ解密算法是加密算法的逆运算；加密密钥和解密密钥相同；加密算法强度高；密钥传递需专用通道；对称密钥密码体制13

由对称算法可分为两类：

序列算法（streamalgorithm）或序列密码(streamcipher)：明文中的单个位（有时对字节）运算的算法。

分组算法（blockalgorithm）或分组密码（blockcipher）：把明文信息分割成块结构，逐块予以加密和解密；块的长度由算法设计者预先确定。对称密钥密码体制14基本思想加密密钥（即公开密钥）PK公开解密密钥（即私有密钥）SK保密加密算法E和解密算法D也都是公开私有密钥SK由公开密钥PK决定，但却不能根据PK计算出SK每个用户产生一对密钥PK和SK公开密钥密码体制15收方破译者发方解密算法P’K’公开密钥体制模型加密算法密钥通道密钥源公开密钥密码体制16公

开

密

钥

算

法

描

述EPK（DSK（X））＝X，不能用PK解密在计算机上可以容易地产生成对的PK和SK从已知的PK不可能推导出SK，即从PK到SK是“计算上不可能的”。加密和解密算法都是公开的。DSK（EPK（X））＝XEPK（DSK（X））＝X公开密钥密码体制17

单钥密码体制中，收发双方使用同一密钥，系统的保密性主要取决于密钥的安全性。系统的密钥管理、传输和分配是一个重要且十分复杂的问题。体制的优点是：保密强度高，运算速度快；缺点是密钥数目大，密钥分配困难，无法实现不可否认服务。

公钥密码体制中，加密密钥KU是公开的，解密密钥KP必须保密。公钥体制的密钥产生、分配和管理相对简单，尤适用于计算机网络系统中。公钥体制的特点：实现信息公开加密，实现不可否认服务，但缺点是加解密运算复杂其速度较慢。两种密码体制的对比18密码学应用用加密来保护信息采用数字证书来进行身份鉴别数字指纹采用密码技术对发送信息进行验证利用数字签名来完成最终协议信息加密信息认证数字签名密钥管理19----密码学数据加密我需要转帐，这是我的帐号和密码。业务服务器田景成38ighwejb.。成景田这是什么？！我们用相关的密码协议建立一个安全的加密信道，这个加密信道的密钥只有你我知道。20----密码学数据加密加密解密明文明文密文KK加密解密KKK的密文B公钥B私钥21----密码学身份认证我是田景成，你是网上银行服务器吗？嗨，我是网上银行服务器。你真的是田景成吗？你真的是网上银行服务器吗？业务服务器田景成使用对方公钥验证对方签名确定对方身份。22----基于非对称密钥的挑战应答方式田景成认证服务器1、获得公钥（数字证书）；5、DP(ED(r))=r’2、请求登录3、随机数r4、ED(r)＋证书P6、比较r和r’拥有正确私钥，则认为其声明身份与证书中的身份一致。23----密码学数据完整性转帐200万到关晓阳的帐号。业务服务器田景成成景田转帐100万到关晓阳的帐号，转帐100万到成景田的帐号。篡改田景成，你传送的数据在传送过程中被修改过，请重新发送你的要求。有了签名，改了可能会被人发现。24----密码学数据完整性明文摘要数字摘要算法散列算法明文摘要◎相等？明文摘要A公钥加密摘要的密文A私钥明文解密25----密码学不可否认性和审计我的钱呢？田景成什么也没捞到！成景田银行职员转走了！转哪去了？岂有此理，我要告你们！你们没有我的签名。您自己忘了！我们查看了系统审计库，你的200万转到了关晓阳帐号。这是所有交易的数字签名。261、机密性:提供只允许特定用户访问和阅读信息，任何非授权用户对信息都不可理解的服务[通过数据加密实现]密码学的作用总结4、抗否认性:提供阻止用户否认先前的言论或行为的服务。[通过对称加密或非对称加密，以及数字签名等，并借助可信的注册机构或证书机构的辅助，提供这种服务]3、数据完整性:提供确保数据在存储和传输过程中不被未授权修改（窜改、删除、插入和重放等）的服务。[通过数据加密、数据散列或数字签名来实现]2、鉴别:提供与数据和身份识别有关的服务。[通过数据加密、数据散列或数字签名来实现]27

移位密码是采用移位法进行加密的。它把明文中的字母重新排列，本身不变，但位置变了，移位密码是靠重新安排字母的次序，而不是隐藏他们。

常见的移位密码主要有：倒置法列换位法矩阵换位法。§2移位密码28（1）完全倒置法把明文中的字母按顺序倒过来写，然后以固定长度的字母组发送或记录。 明文：computersystems 密文：smetsysretupmoc（2）分组倒置法把明文中的字母按固定长度分组后每组字母串倒过来写。 明文：computersystems

分组：computersystems 密文：pmocretutsyssme§2移位密码---倒置法29（1）列换位法将明文字符分割成为若干个（例如5个）一行的分组，并按一组后面跟着另一组的形式排好，形式如下： c1c2c3c4c5 c6c7c8c9c10……最后，不全的组可以用不常使用的字符或a,b,c…填满。密文是取各列来产生的：

c1c6…c2c7…c3c8….c4c9….c5c10….§2移位密码---换位法30例：明文：WHATYOUCANLEARNFROMTHISBOOK进行排列：

WHAT

Y

OUCAN

FRO

MT

H

I

SBO

OKXX

X则密文为：WOFHOHURIKACOSXTAMBXYNTOX

这里的密钥是数字5。§2移位密码---换位法31（2）矩阵换位法把明文中的字母按给定的顺序安排在一矩阵中，然后用另一种顺序选出矩阵的字母来产生密文。例：明文ENGINEERING按行排在3×4矩阵中，最后一行不全用ABC…填充，如下所示。给定置换1234ENGINEERINGA§2移位密码---换位法32现在根据给定的置换，按第2列、第4列、第1列、第3列的次序排列，就得到密文：NIEGERNENAIG在这个加密方案中，密钥就是矩阵的行数m和列数n，即m*n＝3*4，以及给定的置换矩阵:

也就是：k=（m*n，f）1234NIEGERNENAIG§2移位密码---换位法33其解密过程是将密文根据3*4矩阵，按行、列的顺序写出，再根据给定置换产生新的矩阵，恢复明文为：ENGINEERING1234ENGINEERINGA1234NIEGERNENAIG§2移位密码---换位法34

替换密码是使用替换法进行加密所产生的密码。替换密码就是明文中每一个字符被替换成密文中的另外一个字符，代替后的各字母保持原来位置。接收者对密文进行逆替换就恢复出明文来。在替换法加密体制中，使用了密钥字母表。它可以由明文字母表构成，也可以由多个字母表构成。在传统密码学中，有四种类型的代替密码：（1）单表（简单）替换密码

就是明文的一个字符用相应的一个密文字符替换。加密过程中是从明文字母表到密文字母表的一一映射。

例：恺撒（Caesar)密码。§3替换密码35（2）同音（多名码）替换密码与简单替换密码系统相似，唯一的不同是单个字符明文可以映射成密文的几个字符之一，同音替换的密文并不唯一。（3）多字母组替换密码字符块被成组加密，例如“ABA”可能对应“RTQ”，ABB可能对应“SLL”等。例：Playfair密码。（4）多表替换密码

由多个单字母密码构成，每个密钥加密对应位置的明文。

例：维吉尼亚密码。§3替换密码361、恺撒（Caesar)密码又叫循环移位密码。它的加密方法就是把明文中所有字母都用它右边的第k个字母替代，并认为Z后边又是A。这种映射关系表示为如下函数：

F(a)=(a+k)mod26

其中：a表示明文字母；k为密钥。§3.1单表替换密码37设k＝3；则有明文：abcdefghijklmnopqrstuvwxyz密文：defghijklmnopqrstuvwxyzabc

对于明文P＝computer

systems

有密文C＝frpsxwhuv

bvwhpv显然，由密文C恢复明文非常容易，只要知道密钥K，就可构造一张映射表。其加密和解密均可根据此映射表进行。凯撤密码的优点是密钥简单易记。但它的密码文与明码文的对应关系过于简单，密钥空间为26，故安全性很差。§3.1单表替换密码382、密钥短语密码选择一组有助于记忆的英文字符串作为密钥，从中筛选无重复的字符按原顺序记下字符串，写在明文字母表下，然后将未出现在字符串的字母按顺序依次写在密钥短语后。如选择密钥短语networksecurity，则有：明文：abcdefghijklmnopqrstuvwxyz密文：networkscuiyabdfghjlmpqvxz若明文为dataaccess则密文为wnln

nttojj§3.1单表替换密码39

多表替换密码是一种用多组替换表依次对明文消息的字母进行替换的加密方法。

维吉尼亚（Vigenere）密码是一种常用的多表替换密码。这种替代法是循环地使用有限个字母来实现替代的一种方法。这种加密的加密表是以字母表移位为基础把26个英文字母进行循环移位，排列在一起，形成26×26的方阵。该方阵被称为维吉尼亚表。采用的算法为 F(a)=(a+Bi)mod26（其中i=(1，2，…，26)）

优点：能抵抗简单的字母频率分析攻击。§3.2多表替换密码40§3.2多表替换密码---Vigenere密码表41加密过程：以明文字母选择列，以密钥字母选择行，两者的交点就是加密生成的密文。解密过程：以密钥字母选择行，从中找到密文字母，密文字母所在列的列名即为明文字母。例：以your为密钥，加密明文howareyou 明文P=howareyou 密钥K=youryoury 密文C=fcqrpssfs§3.2多表替换密码---Vigenere密码42

多字母替换密码每次加密一组（两个以上）字母串。Playfair密码为此类密码，其密钥是由25个英文字母（j与i相同）组成的5阶方阵。密钥方阵P导出取决于给定密钥，重复不写，余下按字母顺序填充。明文划分如下：将明文字母串按两个字母一组进行分组，每组中的两个字母不同。每一对明文字母m1和m2，对应的密文为c1和c2。每一对明文字母m1和m2，按下面的规则进行加密:§3.3多字母替换密码43（1）若m1和m2在P的同一行，则密文c1和c2分别是m1和m2右边的字母。第一列看作最后一列的右边。（2）若m1和m2在P的同一列，则密文c1和c2分别是m1和m2下边的字母。第一行看作最后一行的下边。（3）若m1和m2在P的不同行、不同列，则密文c1和c2是m1和m2确定的长方形的另两个顶点的字母。其中c1与m1同行，c2与m2同行。（4）若m1＝m2，则在m1和m2之间加一个无效字母(如x)。（5）若明文字母为奇数个，则在末尾加一个无效字母。§3.3多字母替换密码44例：以firewallsecurity为密钥，加密明文howareyou。由密钥导出密钥矩阵为明文分组处理howareyoux则密文khfuewgkcz§3.3多字母替换密码45仿射密码亦称为线性替换密码，是由移位替换密码（加法密码）和乘法密码组合而成。(1)加法密码：加密c＝Ek(m)=m+k(modq)解密m=Dk(c)=c-k(modq)(2)乘法密码：加密c＝Ek(m)=km(modq)解密m=Dk(c)=k-1c(modq)其中密钥k必须与q互素。§4仿射密码46例：密钥k=7，则乘法密码的明文字母到密文字母的替换表若明文howareyou则密文xuyapcmuk(3)仿射密码

加密c＝Ek(m)=k1+k2m(modq)

解密m=Dk(c)=k2-1(c-k1)(modq)§4仿射密码47例：密钥k=(3,7)，则加密函数Ek(m)=3+7m(mod26)，相应的解密函数是Dk(c)=7-1(c-3)(mod26)=15(c-3)(mod26)=15c-19(mod26)

若加密明文为hot，则：§4仿射密码解密：加密：48(4)置换密码加密c＝Ek(m)=π(m)解密m=Dk(c)=π-1(c)置换π的表示：π＝密钥空间很大，|π|=26!≈4×1026

移位密码体制是置换密码体制的一个特例，它仅含26个置换做为密钥空间。(0123..2324250'1'2'3'..23'24'25')§4仿射密码49例：设m=6，取密钥而若明文为cryptography首先分成6个字母长的明文组：crypto|graphyπ(crypto)＝(ytcopr)π(graphy)＝(ahgypr)求得的密文是：ytcoprahgypr§4仿射密码50一次一密方案是一种理想的加密方案，由AT&T公司的GilbertVernam在1917年提出。它使用的密钥是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并被粘成一个密码本。它最初的形式是用于电传打字机。

1）发送者用密码本中的每一密钥字母准确地加密一个明文字符。加密是明文字符和一次密码本密钥字符的模26加法。每个密钥仅对一个消息使用一次。发送者对所发送的消息加密，然后销毁密码本中用过的一页或