第02-01章 现代密码技术及其应用-概述

第02-01章现代密码技术及其应用

---概述主讲人：李学明单位：重庆大学计算机学院2013年1月2.1密码技术概述2.2古典密码2.3现代密码技术2.4消息鉴别2.5数字签名2.6消息隐藏与数字水印目录2.1密码技术概述2.1.1密码技术发展的四个里程碑2.1.2密码学基本概念2.1.3密码系统的安全性1、第一阶段：1949年以前，又称古典密码阶段密码学发展初期阶段，密码学未形成一门独立的科学；

特点：

1）利用手工、机械或初级电子设备方式实现加解密

2）采用替代与置换技术

3）保密性基于方法

4）缺少坚实的数学基础

5）未在学术界形成公开的讨论和研究

2.1.1密码技术发展的四个里程碑(1)2、第二阶段：1949～1976，密码学形成阶段

1）标志：

1949年，香农(30多岁)发表“保密通信的信息理论”

2)1967年，kahn发表“thecodebreakers”3)1971～1973，Feistel等(IBM)发表的技术报告

Lucifer-DES分组密码算法(IBM)4)采用电子计算机实现加解密

5)保密性基于密钥

6)有较强的数学基础

Kerckoffs假设：如果密码系统的强度依赖于攻击者不知道算法的内部机理，则该密码系统注定会失败算法不容易保密，可以通过反汇编、逆向设计、非技术手段获得算法实例：

1994年，RC4算法源码就被公开了

3、第三阶段：1976后，公钥密码体制的诞生与发展

1）标志：1976年，不对称密码

1976年,Diffie&Hellman,发表“NewdirectionsinCryptography”,提出不对称密码

2)1977年,RSA算法

1977年,MIT的Rivert、Shamir、Adleman发表RSA算法

3)1985年,ECC1985年,N.Koblitz和Miller提出将椭圆曲线用于公钥密码系统，并逐渐形成ECC体系

4、第四阶段：1984后，量子密码学产生阶段

1984年，bennettCH和BrassardG发表BB84协议

特点：

1)唯一理论上安全的,即使P=NP,其也是安全的；

2)其它都是计算安全的，基于计算复杂性，但当NP=P时，就无安全可言；第二、三、四阶段也称为现代密码学阶段；此外，混沌密码学的研究也成为一个新的研究热点主要内容

1、一般的加密系统模型

2、密码系统

3、密码学基本概念

4、密码分析简介

5、密码学的数学基础2.1.2密码学基本概念(1)1、一般的数据加密模型加密器E密钥源加秘密钥Ke明文m密文c=Eke(m)公开信道解密器D解密密钥Kd明文m=Dkd(c)破译者2.1.2密码学基本概念(1)2、密码系统(体制)

一个密码系统(体制)可用一个五元组来表示(M,C,K,E,D)(1)明文mi和明文空间M

明文：是易于理解的信息。对计算机而言，是指数字化的信息。可以是文本、图像等二进制序列。明文可被存储、传输、加工。明文空间：

M={m=(m1,m2,…,ml)|mi∈X,1≤i≤l},明文长度为lX称为明文字母表(2)密文Ci和密文空间C

密文：不易被理解的信息。对计算机而言，也是以二进制形式存在的信息。密文空间：

C={c=(c1,c2.,…,ct)|ci∈Y,1≤i≤t},

密文长度为tY称为密文字母表(3)密钥空间K={(Ke,Kd)}

密钥k:

加密算法E、解密算法D的运行控制参数

K={k=(k1,k2,…,ks)|ki∈B,1≤i≤s},

密钥长度为sB称为密钥源字母表(4)加密算法E

在Ke的控制下，完成M到C的加密变换规则本质上是M到C的映射(5)解密算法D

在Kd的控制下，完成C到M的解密变换规则本质上是C到M的映射加密:c=Eke(m)

解密:m=Dkd(c)=Dkd(Eke(m))3、密码系统的分类分类依据（1）保密内容（2）密钥数量（3）明文处理方式按保密内容来分

A、受限制的（restricted)算法保密性基于保持算法的秘密

B、基于密钥（key-based)的算法保密性基于对密钥的保密，算法是公开的按密钥数量来分

A、对称密码算法（symmetriccipher)：单密码体制

kd=ke，或kd与ke间存在某种易于发现的关系；最大的问题：ke需要在加密方和解密方间进行交换密钥的传输和分配是最大问题

B、非对称密钥算法（asymmetriccipher)：双密码体制

Kd≠ke，且Kd和ke间不存在某种易于发现的关系

不存在密钥交换问题。

Ke不需要保密，可以公开;只有Kd需要保密

按明文处理方式

A、分组密码（blockcipher)

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

B、流密码（streamcipher)

又称序列密码。序列密码每次加密一位或一字节的明文密钥搜索所需平均时间5、密码学的数学基础

(1)基础数论基础数论用于密码学才只有几十年时间，以RSA为典型

(2)近世代数群环域，布尔函数；如椭圆曲线密码理论数理逻辑，BAN逻辑用于协议分析

(3)非线性复杂理论混沌序列拟随机序列1、完善保密系统的含义（香农）

I(M;C)=H(M)-H(M|C)=0，则称相应的密码系统为完善保密系统。即知道密文，并不能获取更多明文的信息；也即是说，无论截取多少密文，也无法获得相关明文的信息密码系统设计的基本原则：

确保明文与密文间的互信息为0；即明文空间与密文空间完全无关2、定理：完善保密系统的必要条件:H(K)≥H(M)

该定理由香农在1949所证明：M和C要完全无关，密钥熵不能小于明文熵,密钥必须具有随机特性，即K应为真正的随机序列2.1.3密码系统的安全性2、密码系统的安全性分类

（1）无条件安全（Unconditionallysecure）

无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性。

Onetimepad：一次一密；

满足H(K)≥H(M)条件但不实用(2)计算上安全（Computationallysecure）破译的代价超出信息本身的价值破译的时间超出了信息的有效期破译的时间复杂度不是多项式的算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）主要内容

1、羊皮密码

2、替代密码

3、置换密码

4、一次一密方案

5、转轮机2.2古典密码1、羊皮密码

1)公元前400年，斯巴达人使用棍子和羊皮进行秘密通信。

2)他们把羊皮螺旋状地缠绕着棍子，然后沿着棍子的水平方向一行一行地写。写完后把纸条取下来，送到接收者手中。

3)羊皮上只有杂乱无章的字母，但当接收者把它绕在同样直径(直径可以看成是一种密钥)的棍子上时，一段清楚的文字就神奇般地显现出来。

4)该方法很可能是文字记载的最早加密算法。

5)该方法虽然很简单，但还是起到了一定的保密作用。2、置换密码根据一定规则重新安排明文，使重排后的明文失去可理解特性。

(m1,m2,…,ms)--->(mt1,mt2,…,mts)F的数量虽然有n!，但其不能抗攻击，甚至是唯密文攻击canyoudoitforme明文：Canyoudoitforme密文：coirautmndfeyoo输入方向输出方向美国南北战争3、替代密码将明文空间中的一个字符或字符串替换成密文空间中的一个字符或字符串1)单表替代密码(monoalphabeticsubstitutioncipher)2)同音替代密码(homophonicsubstitutioncipher)3)多表替代密码(polyalphabeticsubstitutioncipher)4)多字母替代密码(polygramsubstitutioncipher)(1)单表替代密码:一个名文字母对应一个密文字母恺撒密码caesercipher是一种单表替代密码英文字母向前或后移动若干位，对应的字母即为密文。其密码本为：明文:abcdefghijklmnopqrstuvwxyz

密文:defghijklmnopqrstuvwxyzabc

例：明文caeserwasagreatleader

密文geiwivaewekviexpiehiv

一般的单表替换密码可表示为：c=E(m)=(am+b)modn(仿射密码)

对恺撒密码：a=1,b=3,n=26

不能抗穷举攻击、统计攻击(明文的字母统计特性反映在密文中)(2)同音替代密码一个明文字母对应对个多个密文字母

(1)canada’slargelandmassand(6)scatteredpopulationmakeefficientcommunication(11)anecessity.Extensiverailway,road(16)andothertransportationsystems,as(21)wellastelephone,telegraph,and(26)cablenetworks,havehelpedto(31)linkcommunitiesandhaveplayed(36)avitalpartinthe(40)country’sdevelopmentforfuture

密码本：c:1、10、26、32、41(首字母为c的单词的所在位置);m:4、8…

明文：Iloveherforever

密文：392173792891443171413371314(e:9或13)(3)多表替代密码由多个单表替代密码构成。一个字母在不同位置上被替换成不同的密文字母。典型的Vigenere密码

Vigenere形式化描述：

t个密文本，加密为：

ci=fi(mi)=(mi+ki)mod26,其中ki为密钥,i=0,1,…,t-1t=1时，就是单表替代

对明文:m=(m0,m1,…,mt-1,mt,…)

密文为:c=(f0(m0),f1(m1,…,ft-1(mt-1),f0(mt),….)举例说明：

k=(6,14,15,7,4,17),t=6m=meetmeintheallyaftermidnightc=sstaqvobioirrznhjkkfbpheouwaabcdefghijklmnopqrstuvwxyz012345678910111213141516171819202122232425

(4)多字母替代密码明文字母串被替换成密文字母串，替代是以多个字母串为单位，而不是针对单个字母。典型例子为：playfair密码（英国在一战中使用过）用25个英文字母组成5阶方阵(J不用，默认为I)左边密钥矩阵是用firewallsecurity导出的1915年被德国破解加密方法：

1)明文以2个字母为单位进行加密：m1m2--->c1c22)若m1、m2在同一行，则c1、c2分别为紧靠m1、m2右端的字母(第一列为最后一列的右端)3)若m1、m2在同一列，则c1、c2分别为紧靠m1、m2下端的字母(第一行为最后一行的下端)4)若m1、m2既不在同一行，又不在同一列，则c1、c2分别为m1、m2确定的矩形的两个顶点所对应的字母，c1与m1同行，c2与m2同行

5)若m1=m2，则在m1和m2见插入无效字母(如x)6)若明文字母数为奇数，则在其末附加一个无效字母明文：playfaircipherwasbroke分组：playfaircipherwasbroke密文：qaltatrelefpwefubmwmni4、一次一密方案(one-timepad,OTP)(1)一次一密体制的含义：

A.密钥是真正的随机序列

B.密钥长度至少等于明文长度

C.一个密钥只用一次

(2)满足上述三个条件的密码系统是绝对安全的，不会被破译(香农在1949年已证明)(3)Verman密码(美国人摩波卡金其基础上设计出一次一密体制)

美国电报电话公司的Verman弗纳姆发明了弗纳姆密码。原理是利用电传打字机的五单位码与密钥字母进行模2相加(异或运算)

明文:m=(m1,m2,…,ms)

密钥:k=(k1,k2,…,ks)

密文:c=(c1,c2,….cs)加密：A--->00000;b--->00001;c--->0001