应用密码学课件

应用密码学

2024年4月6日2第一章概述2024年4月6日31课程相关介绍－－概念什么叫密码学？密码学(Cryptology)：是研究密码编制、密码破译和密码系统设计的的一门综合性科学，其包括密码编码学和密码分析学。密码编码学(Cryptography)：主要研究对信息进行编码,实现对信息的隐蔽。密码分析学(Cryptanalytics)：主要研究加密消息的破译或消息的伪造。2024年4月6日41课程相关介绍—密码学研究的内容编码学研究的主要内容：序列密码算法的编码技术分组密码算法的编码技术公钥密码体制的编码技术加密算法、数字签名方案、密钥分配方案认证方案单向函数等传统且主流的研究方向2024年4月6日51课程相关介绍—密码学研究的内容密码分析学研究的主要内容（1）密码算法的安全性分析和破译的理论、方法、技术和实践（2）密码协议的安全性分析的理论与方法（3）安全保密系统的安全性分析和攻击的理论、方法、技术和实践2024年4月6日61课程相关介绍－－密码学时干什么的？密码学是干什么的?密码学要解决的基本问题:

(1)信息的保密传输和存储问题;(2)信息的认证问题.

例:我收到你写给我1封信,那末我问:----信的内容是否被改动?----是否真是你写的信?----是否真是写给我信?----有没有人看过这封信？2024年4月6日71课程相关介绍—密码学的应用领域密码学能够解决的问题1.信息系统的安全与保密问题；2.电子商务、电子政务中的安全和保密问题；3.银行系统、证券系统、保险系统等的安全问题；4.商品、票据、信用卡等的防伪与审核问题。2024年4月6日82密码学发展1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学2024年4月6日92密码学发展－－第一阶段概述第1阶段－古典密码密码学还不是科学,而是艺术出现一些密码算法和加密设备密码算法的基本手段出现，针对的是字符简单的密码分析手段出现主要特点：数据的安全基于算法的保密2024年4月6日102密码学发展－－第一阶段中的例子第1阶段－古典密码几个典型的密码：卡撒密码、维几尼亚密码；几个典型的战例：一战时德国人的ADFGVX密码被法国密码分析家破译，间接的导致了德国一战的失败；二战德国人的恩尼格马密码被破，直接导致德军二战的失败2024年4月6日112密码学发展－－第一阶段中的实例Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。2024年4月6日122密码学发展－－第一、二阶段中的密码机20世纪早期密码机2024年4月6日132密码学发展－－第二阶段概述第2阶段1949~1975计算机使得基于复杂计算的密码成为可能相关技术的发展：1949年Shannon的《TheCommunicationTheoryofSecretSystems》1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson实验室的HorstFeistel等几篇技术报告主要特点：数据的安全基于密钥而不是算法的保密

2024年4月6日142密码学发展－－第三阶段大事记第3阶段1976~1976年：Diffie&Hellman的

“NewDirectionsinCryptography”提出了不对称密钥密码；1977年Rivest,Shamir&Adleman提出了RSA公钥算法1977年DES正式成为标准2024年4月6日152密码学发展－－第三阶段大事记80年代出现“过渡性”的“PostDES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出现90年代逐步出现椭圆曲线等其他公钥算法2001年Rijndael成为DES的替代者2004年著名的MD5算法被中国的王小云破译2024年4月6日163密码学的基本概念－－信息传输中的基本概念信息传递的一般问题信源、信道、信宿攻击的种类：中断（Interruption)（干扰）截取（Interception)(侦听）修改（Modification）伪造（Fabrication)角色：通信双方(发送方和接收方)、第三方（可信、不可信第三方）、敌手也叫攻击者A：信源B：信宿信道2024年4月6日173密码学的基本概念－－信息传输过程中的攻击例子窃听：对传输的信息的攻击A：信源发送方B：信宿接收方C：敌手攻击者2024年4月6日183密码学的基本概念－－信息传输过程中的攻击例子对窃听的防护：加密技术A：信源B：信宿C：敌手加密脱密2024年4月6日193密码学的基本概念－－基本概念明文：被隐蔽的消息称作明文，通常用m表示。其英文为Message和Plaintext

明文就是没有被加密的消息.密文：将明文隐蔽后的结果称作密文或密报，通常用c表示。其英文为Ciphertext

密文就是加密后的结果.2024年4月6日203密码学的基本概念－－基本概念加密（Encryption

）：将明文变换成密文的过程称作加密，该过程表示为脱密（Decryption

）：由密文恢复出明文的过程称作脱密,该过程表示为密钥(key)

：控制或参与密码变换的可变参数称为密钥。密钥又分为加密密钥和脱密密钥。加密密钥是加密时用的密钥;

脱密密钥是脱密时用的密钥;2024年4月6日213密码学的基本概念－－密码体制的概念密码体制的概念:一个密码体制(Cryptosystem)由四部分组成：

(1)明文空间M;----所有可能的明文构成的集合

(2)密文空间C;----所有可能的密文构成的集合

(3)密钥空间

----所有可用的密钥构成的集合

----又包括加密密钥和脱密密钥

(4)密码算法。包括加密算法和脱密算法.00011011F0F100112024年4月6日223密码学的基本概念－－加密函数分析----从加密函数的角度理解密码体制的概念----加密函数:

将明文m加密为密文c,即其(1)定义域是明文空间M;(2)值域是密文空间C;(3)加密函数就是加密算法;(4)控制参数就是加密密钥

2024年4月6日233密码学的基本概念－－脱密函数分析--针对脱密函数分析--

脱密函数:将密文c

脱密为明文m,即其(1)定义域是密文空间C;(2)值域是明文空间M;(3)脱密函数就是脱密算法;(4)控制参数就是脱密密钥.

2024年4月6日243密码学的基本概念－－加、脱密函数说明加、脱密密钥与成对使用;加密函数与脱密函数互为逆函数，即对所有明文m，都有

一个密文只能有一个脱密结果!mcDmEDdedkkk==)())((2024年4月6日253密码学的基本概念－－好的密码体制的条件好的密码体制满主的条件：

(1)即使达不到理论上是不可破的，也应当是实际上不可破的。（2）保密性不依赖于对加密体制或算法的保密,而依赖于密钥。(Kerckhoff假设)（3）加密算法和脱密算法适用于密钥空间中的所有元素。弱密钥除外!

（4）易于实现和使用。

----知道密钥时加、脱密快捷！2024年4月6日263密码学的基本概念－－密码分析学中的概念破译：对于一个密码体制，如果能够根据密文确定明文和密钥，或者根据明文或相应的密文确定密钥，我们就说这个密码体制时可破译的；否则，称其为不可破译的。2024年4月6日273密码学的基本概念－－攻击方法1、攻击密码体制的方法（1）穷举攻击：如果没有密钥会怎样?----谁都可脱密!如果可能的密钥太少会怎样?----若对每个可能的密钥都逐一测试，则一定可以碰到正确的密钥，利用它就可脱密!

这就是穷举攻击方法！

穷举攻击就是逐一利用每个可能的密钥对密文进行脱密测试，并将脱密结果合理的那个密钥判断为正确密钥。

00011011E00000001100011011E1111111002024年4月6日283密码学的基本概念－－攻击方法要想能抵抗穷举攻击,一个密码算法的可能密钥总数不能太少!一个密码算法的可能密钥的总数称为该密码算法的密钥变化量.目前,密钥变化量少于264的密码算法是不安全的!密钥变化量为2128的密码算法是安全的!为什么?2024年4月6日293密码学的基本概念－－攻击方法假设密钥变化量为2128≈10128×0.301＝1038.5考查该密码算法的抗穷举攻击能力。假想为计算机速度为10亿次/每秒10亿＝1091年＝365×24×3600＝3.15×107秒1年可以穷举的密钥量为：3.15×107×109＝3.15×1016个密钥2128个密钥需要1038.5/3.15×1016≈1022年才能穷举完。（一万亿亿年）2024年4月6日303密码学的基本概念－－攻击方法（2）统计分析攻击：密码分析者通过分析:

(A)

密文与明文之间,或

(B)

明文--密文对与密钥之间的统计规律来进行破译。一个设计的不太差的密码算法一般只能用这种方法进行攻击!2024年4月6日313密码学的基本概念－－攻击方法（3）解密变换攻击：密码分析者针对加密变换的数学基础，通过数学求解的方法来设法找到相应的脱密变换或等价的脱密变换实现攻击。这种攻击通常用于对公钥密码的攻击之中！对付这种攻击的手段就是：采用坚实的数学基础和足够复杂的加密算法。2024年4月6日323密码学的基本概念－－攻击方法对密码体制进行攻击时,攻击对象是什么?

(1)求出明文!(2)求出密钥,进而求出明文!2024年4月6日333密码学的基本概念－－攻击者的能力对敌手攻击能力的假设

Kerckhoff假设----假设敌手知道除使用的具体密钥之外的一切信息,目的是恢复明文!即一切秘密蕴于密钥之中!2024年4月6日343密码学的基本概念－－攻击者的能力假设敌手知道:

(1)所使用的密码体制;(2)知道明文的概率分布规律;(3)知道密钥的概率分布规律;(4)知道所有的破译方法!2024年4月6日353密码学的基本概念－－攻击方法按敌手可利用的知识的类别的多少,攻击方法可分为:2024年4月6日363密码学的基本概念－－加密方案的安全性加密方案的安全性无条件安全：无论提供的密文有多少，如果由一个加密方案产生的密文中包含的信息不足以唯一地决定对应的明文除了一次一密的方案外，没有无条件安全的算法安全性体现在：破译的成本超过加密信息的价值破译的时间超过该信息有用的生命周期2024年4月6日373密码学的基本概念－－攻击的复杂性分析攻击的复杂性分析数据复杂性（datacomplexity）用作攻击输入所需要的数据处理复杂性（processingcomplexity）完成攻击所需要的时间存储需求（storagerequirement）进行攻击所需要的数据量2024年4月6日383密码学的基本概念－－密码管理的相关法规密码管理的相关法规我国规定：（1）密码产品和安全产品必须经过审查后才能使用！（2）只审查具有设计资格的单位设计的密码方案！（3）军用密码的审查由总参机要局具体负责；党、政、外交用途的密码的审查由中央办公厅机要局具体负责；商品密码的审查由商品密码管理委员会具体负责！2024年4月6日39解放军信息工程大学电子技术学院是全国唯一具有核心密码设计资格的院校！2024年4月6日40国内密码学研究单位（一）军内科研单位

1.总参三部系统

2.总参机要系统（二）中央机要局系统科研单位

1.北京电子技术研究所

2.北京电子科技学院2024年4月6日41主要的民间密码研究单位1.中科院信息安全重点实验室2.西安电子科技大学3.信息产业部第30研究所4.北京邮电大学5.解放军信息工程大学信息工程学院6.上海交通大学7.武汉大学2024年4月6日42本课程概要（一）古典密码

介绍古典密码的两个典型密码体制，单表代替和多表代替。（二）Shannon理论

介绍熵、多余度、唯一解码量的概念及完善保密性。（三）分组密码

重点讲述DES算法及分组密码的工作模式，高级加密标准AES。2024年4月6日43（四）公钥密码

RSA公钥密码体制及相关的设计和分析方法，椭圆曲线公钥密码体制。（五）序列密码

线性移存器序列及其特性，BM算法等。（六）数字签名

数字签名基本概念，数字签名标准。44基本编码技术的分类

(1)代替密码利用预先设计的代替规则,对明文逐字符或逐字符组进行代替的密码.

分为单表代替和多表代替两种

(2)移位密码对各字符或字符组进行位置移动的密码.(3)加减密码将明文逐字符或逐字符组与乱数相加或相减的密码.45我们将重点介绍代替密码

46

一、单表代替密码：利用预先设计的固定代替规则,对明文逐字符或逐字符组进行代替的密码.

字符组称为一个代替单位.

这里代替规则又称为代替函数、代替表或S盒。它的固定性是指这个代替规则与密钥因素和被加密的明文字符的序号无关。即相同的明文字符组产生相同的密文字符组.47

例1:汉字和符号的区位码(单表代替)

2211227748例2

以十进值数为代替单位的代替函数则明文晨五点总攻先变换为区位码

19314669216755601505再被加密成密文

46241996849700954050单表代替的缺点:明文字符相同,则密文字符也相同明文0123456789密文5482109736即代替表为:49加密变换:

例3

加法密码

选定常数

q和k.

明文空间=密文空间=脱密变换：

其中读作n模q,它是n被q除后所得的余数.如18mod7=4上述加法称为模q加.50加密变换为：

特别地,若取q=10

和k=3,则脱密变换为：

此时,明文:晨五点总攻变换为区位码19314669216755601505后就被加密成密文42647992549088934838

缺点:密文差=明文差51

例4:Caesar密码(凯撒密码)

这是一种对英文字母的典型逐字母加密的的加法密码,其密钥k=3。

英文字母被编码为该字母的序号

英文ABCD…XYZ

数字

0123…232425加密变换为：脱密变换为：52

例5:标准字头密码(又称密钥字密码)

这是一种对英文字母的典型逐字母加密的密码,它利用一个密钥字来构造代替表。

如:

若选择cipher作为密钥字,则对应代替表为:明文ABCDEFGHIJKLMNOP…密文

CIPHERABDFGJKLMN…53例4：加密变换为:

二、多表代替密码

根据密钥的指示，来选择加密时使用的单表的方法，称为多表代替密码。但k不再是固定常数而是密钥。加密算法：

明文：晨五点总攻明文序列：19314669216755601505密钥序列：43215378432231091107密文序列：52529937648986692602若密钥序列是随机的,该密码就是绝对安全的.随机就是指序列的信号相互独立且等概分布.54将对英文字母的加密变换改为：

当将明、密文空间均改为这个密码就是一个著名的古典密码体制：维几尼亚密码（Vigenere密码体制）若明文序列为:密钥序列为：则密文序列为:其中：这也是序列密码的一般加密形式将英文字母编码为它的序号(0起算)55维几利亚密码的代替表为明文字母密钥字母密钥字母为d,明文字母为b时查表得密文字母为e56将对英文字母的加密变换改为：

当将明、密文空间均设为若明文序列为:密钥序列为：则密文序列为:其中：该密码称为维福特密码（Beaufort密码体制）此时脱密变换与加密变换完全相同，也是：57

如果将明、密文空间均改为将加密变换改为：若明文序列为：密钥序列为：则密文序列为：其中：这是众所周知的完全保密的密码体制这个密码就是著名的Vernam密码体制58

代替密码的安全性分析

1.单表代替的优缺点

优点:

明文字符的形态一般将面目全非

缺点:

(A)明文的位置不变;(B)明文字符相同,则密文字符也相同;

从而导致:(I)若明文字符e被加密成密文字符a,则明文中e的出现次数就是密文中字符a的出现次数;(II)明文的跟随关系反映在密文之中.

因此,明文字符的统计规律就完全暴露在密文字符的统计规律之中.形态变但位置不变59e：出现的频率约为0.127t，a，o，i，n，s，h，r：出现的频率约在0.06到0.09之间d，l：的出现频率约为0.04c，u，m，w，f，g，y，p，b：的出现频率约在0.015到0.028之间v，k，j，x，q，z：出现的频率小于0.0160例：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ61

代替密码的安全性分析

2.多表代替的优缺点

优点:

只要

(1)多表设计合理,即每行中元互不相同,每列中元互不相同.(这样的表称为拉丁方表)(2)密钥序列是随机序列，即具有等概性和独立性。这个多表代替就是完全保密的。

等概性:各位置的字符取可能字符的概率相同；

独立性：在其它所有字符都知道时，也判断不出未知的字符取哪个的概率更大。62

代替密码的安全性分析

2.多表代替的优缺点密钥序列是随机序列意味着：（1）密钥序列不能周期重复；（2）密钥序列必须与明文序列等长；（3）这些序列必须在通信前分配完毕；（4）大量通信时不实用；（5）分配密钥和存储密钥时安全隐患大。

缺点：周期较短时可以实现唯密文攻击。

解决方案：密钥序列有少量真随机的数按固定的算法生成，只要它很像随机序列即可。这种序列称为伪随机序列。63移位密码

对明文字符或字符组的进行位置移动的密码

例：设明文为：解放军电子技术学院移位方式：S[9]={2,5,7,3,4,8,9,1,6}即:第i个密文汉字就是第S[i]个明文汉字.则密文为放子术军电学院解技移位也是现代密码中必用的一种编码技术64

移位密码的安全性分析

1.移位密码的优缺点

优点:

明文字符的位置发生变化;

缺点:(A)明文字符的形态不变;

从而导致:(I)密文字符e的出现频次也是明文字符e的出现次数;有时直接可破!(如密文字母全相同)目前也有现成的破译方法.移位密码优缺点总结:位置变但形态不变.代替密码优缺点总结:形态变但位置不变.单表古典密码的统计分析原理：明文的统计规律在密文中能够反映出来，故信息泄露大。多表古典密码的统计分析原理：密钥相同时，相同的明文对应相同的密文。明文的统计规律26个英文字母：e

12%t---a---o---i---n---s---h---r

6%--9%d---l

4%c---u---m---w---f---g---y---p---b

1.5%--2.8%v—k---j---x---q---z

<1%汉字中单音节出现频率最常用，出现频率在百分之一以上的有14个音节，它们是：deshiyibuyouzhilejizhewoyenlitadao的是一不有之了机这我们里他到次常用音节有33个，它们是：zhongziguoshanggemenheweiyedagongjianjiuxiangzhulaishengdizainixiaokeyaowuyujiejinchanzuojiaxianquanshuo从三亿汉字的母体材料中，抽样二千五百万字进行双音节词词频统计，结果是：频率在一万次以上的双音节词有33个：我们三万次以上可以他们二万次以上进行没有工作人民生产这个发展就是问题国家中国这样革命自己不能由于这些所以因此作用一般什么如果情况必须方法因为主要要求社会汉字中双音节词出现频率

多表古典密码的统计分析步骤1：首先确定密钥的长度：利用Kasiski测试法和重合指数法(indexofcoincidence)步骤2：确定具体的密钥内容：交互重合指数法

寻找密文中相同的片段对，计算每对相同密文片段对之间的距离，不妨记为d1,d2,…,di，若令密钥字的长度为m，则m=gcd(d1,d2,…,di)。定理1若两个相同的明文片段之间的距离是密钥长度的倍数，则这两个明文段对应的密文一定相同。反之则不然。若密文中出现两个相同的密文段(密文段的长度m>2)，则它们对应的明文（及密钥）将以很大的概率相同。Kasiski测试法：Kasiski于1863年提出思考：以多大的概率成立？P(X1=X2|Y1=Y2)=1-P(X1!=X2;K1!=K2|Y1=Y2)由于密钥是等概独立的，每个密钥出现的概率为1/26，这相当于求满足X1+K1=X2+K2(mod26)的K1和K2出现的概率。若K1和K2中均有m个字母，且m>=3，则P(X1=X2|Y1=Y2)进一步判断密钥字的长度是否为

m=gcd(d1,d2,…,di).

定义1设X=x1x2…xn是一个长度为n的英文字母串，则x中任意选取两个字母相同的概率定义为重合指数，用表示。重合指数法(indexofcoincidence)：Wolfefriendman于1920年提出定理1设英文字母A，B,…，Z在X中出现的次数分别为：f0,f1,…,f25则从X中任意选取两个字母相同的概率为证明在X中任意选取两个字母共有种选取的可能；在X中的每个相同的字母中选取两个元素共有种选取的可能。故易证。证毕。已知每个英文字母出现的期望概率，分别记为p0,p1,…,p25，那么X中两个元素相同的概率为：

=0.065

对于英文的一个随机字母串，每个英文字母出现的期望概率均为1/26，则在X中任意选取两个元素相同的概率为=0.038.根据Kasiski测试法得到的m，可以将密文Y按照下列形式排列：表1将Y排列成m行n/m列的形式，设m=0(modn)

若m确实是密钥的长度，则上述矩阵中的每一行都是由同一个密钥ki加密得到，这说明每一行即是一个单表代替，这时计算每一行的重合指数，应该更接近0.065；若m不是密钥的长度，则上述矩阵中的每一行不是由同一个密钥ki加密得到，这说明每一行是一个等概随机的字母串（对密文的要求），这时计算每一行的重合指数，应该更接近0.038。用交互重合指数确定密钥的具体内容定义设X=x1x2…xn和Y=y1y2…yn，是两个长度分别为n和n’的字母串。X和Y的交互重合指数(mutualindexofcoincidence)定义为X中的一个随机元素与Y中的一个随机元素相同的概率，记为计算表1中的任意两行之间的交互重合指数中的一个随机元素与中的一个随机元素同为字母h(0<=h<26)的概率为

则称为和之间的相对位移(relativeshift)，用表示。由于计算具体密钥内容当相对位移不为0时，重合指数的取值范围[0.031,0.045]当相对位移为0时，重合指数取值为0.065。可以统计每两行中英文字母出现的概率f0,f1,…,f25

和f’0,f’1,…,f’25记为以g作密钥进行加法加密得到的密文，并穷举计算得到若，则应该接近0.065；若不然，应该接近[0.031,0.045]中的某个值。K1+i,i=0,……,25K1-k2=5计算具体密钥内容的复杂度分析

这样可以得到任意两行之间的相对位移。给定某一行，猜测其密钥值(只有26种可能),其它行的密钥由相对位移唯一确定,这时用穷举法只有26种可能,可得到密钥值。习题1、已知某密码的加密方法为：先用易位密码对明文M加密，再对该结果用维吉尼亚密码加密得密文C。若易位密码使用的加密密钥为置换T=（351246），维吉尼亚密码使用的加密密钥为AEF，密文C=vemaildytophtcmystnqzahj，求明文M。习题2、已知某密码的加密方法为：C=f2(f1(M))其中变换f1为：c=(7m+5)mod26；变换f2为置换T=（31254），今收到一份用这种密码加密的密文C=ficxsebfiz，求对应的明文M。f1的逆为：

m=15(c-5)mod26=(15c+3)mod26习题1解答：解：加密密钥为置换T=（351246），则脱密密钥为置换T’=（341526）用维吉尼亚密码脱密得结果vahaegduoolctykyoonmuade再使用易位密码脱密得明文Mhaveagoodluckytoyouandme87香农简介

香农(1916-2001),生于美国密执安州的加洛德。1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部，在此工作了15年。88香农简介

香农在信息论的领域中钻研了8年之久，终于在1949年在《贝尔系统技术杂志》发表了244页的长篇论著---《保密系统的通信理论》。次年，他又在同一杂志上发表了另一篇名著---《噪声下的通信》。89香农理论简介

第一篇文章奠定了香农信息基本理论的基础。他在文中用非常简洁的数学公式定义了信息时代的基本概念：熵。“熵”的概念起源于热力学，是度量分子不规则热运动的单位。香农的伟大贡献在于，利用概率分布的理论给出“熵”的严格定义。根据香农的定义，确定发生的事件如“太阳从东边升起”与确定不发生的事件如“太阳从西边升起”，其熵都是零。只有当发生与不发生的概率相同时，事件的熵才达到极大。90香农理论简介

在熵的基础上定义的信道容量也是通讯中一个至关重要的概念。由此，香农推出了一个公式，明确表达了在不同噪声情况下传输速率与失真的定量关系。从这一个公式导出的为达到无失真通讯的传输速率的极限，现已称为香农极限。打个比方来说，在周围干扰严重的情况下，要想使对方听清楚，你就只有慢慢地讲，甚至还要不断重复。91香农理论应用如今，这两个原理已广泛应用于信息处理和实际通信中。只要涉及信息的压缩与传递，就要用到香农的理论。PC机上常用的WinZip(无损压缩算法)手机通讯(有损压缩

无损压缩,纠错)在因特网上传递多媒体数据（MP3音乐压缩格式）92第三章Shannon保密理论

密码体制的数学模型随机事件的熵及其性质93通信系统信源编码器解码器接收者干扰源信道设计目的：在信道有干扰的情况下，使得接收者接收到的信息无差错或差错尽可能的小。94保密系统95保密系统设计目的：使得窃听者即使完全准确地接收带了信道上传输的信号也无法恢复出原始的信息。96密码体制的数学模型

明文(离散信源)空间的统计特性：无记忆和有记忆密钥源通常是无记忆的，并且满足均匀分布密文空间的统计特性由明文空间和密钥空间的统计特性决定假定信道无干扰，假定分析者能够截获密文，且知道所用的密码体制以及明文空间和密钥空间的统计特性97§3.2随机事件的熵及其性质主要内容:

如何定量刻划一个随机事件包含的信息量用熵的概念!

熵(entropy)这个数学工具自身的理论.98何为信息?什么能提供信息?

我将你原来不知道的结果告诉你,就是提供了信息!

例1

当我给你一封信时，你就从我这里获得了信息，因为你事先并不知道其中的内容。

例2

设电脑彩票由8个10进制数组成.在开奖之前，我们不知道特等奖号码的信息，因为特等奖的号码是不确定。特等奖号码的信息只有在开奖时才获得。一旦开奖，就获得了8个十进制数的信息。

这就是说，将未知的变成已知的时就获得了信息！

信息寓于不确定之中！99信息量我向你提供的信息量的大小就是你事先不知道结果的程度!也即是信息的不确定度。如果你事先全知道了,说明我提供的信息量等于0;如果你事先一无所知,说明我提供的信息量最多.不知道意味着在我告诉你之前你只能猜测!猜测就是按照每个可能结果的出现概率进行猜测!因此,你只知道这个事情的每个结果的发生概率!所以,我提供的信息量就是由你事先知道的每个可能结果的发生概率(即随机事件的概率分布)决定.100简单地说,信息就是:(1)当未知的变成已知的之后获取的信息;(2)当未知的还没变成已知之前包含的未知信息.信息寓于不确定之中！谁的信息!

通常的信息是指:(1)一个实验提供的信息;(2)一个随机事件包含的信息;(3)一个随机变量包含的信息.其中(1)和(2)的含义相同,它们比(3)的意义更

加广泛.101随机事件和随机变量定义1：设一个实验有共n个可能的结果，则每个可能结果都称为一个事件。这个实验也称为一个随机事件。性质1：设X是一个离散随机变量，它有n个可能的取值，设每种取值出现的概率为p(xi),则102一、随机事件的熵

一个事件可能发生，也可能不发生！但我们总在每个事件发生的概率都已知的条件下分析！

这个实验提供的信息就是：(1)实验前该实验所包含的未知信息；(2)实验后这个实验所提供的信息.

如何对信息量的大小进行定量刻划?

再看一下彩票的例子.103例3设电脑彩票由8个10进制数组成，在开奖之前，108个可能号码成为特等奖的概率相同,都是10-8.一旦开奖,我们就知道了特等奖的8个具体号码,因而就获得了8个十进制数的信息。

我们获得的信息量与开奖前每个可能号码成为特等奖的概率10-8有何关系?显然,有8=-log1010-8

信息量的定量刻划:

定义2

设是一个实验中事件发生的概率,则称为事件包含的自信息量.104熵的数学定义定义3.1(随机事件的熵):设一个实验X有

共n个可能的结果,则称的数学期望为实验X的熵(Entropy).其中约定

0log0=0.

105

因此,一个实验的熵就是该实验的每个可能结果包含的自信息量的平均值!

熵的单位与对数的底有关!

约定对数的底大于1!

当以2为底时,其单位称为比特(bit);

当以10为底时,其单位称为迪特(Det);106

例5设一个实验有a和b两个可能的结果,且实验结果是a和b的概率分别为1/4和3/4,试计算该实验的熵.解:根据熵的定义,有解毕107

下面介绍熵的性质.

定义3.4一个实值函数f称为在区间I上是凸

的,如果对任意的,都有如果对任意的,都有则称f称为在区间I上是严格凸的.108引理3.1(Jensen不等式)

设f是区间I上的一个连续的严格凸函数,并且

,

则有且上述等号成立的充要条件是109

推论1

f(x)=logb

x

(b>1)在区间x>0时是严格

凸的,因而当实数

满足且有：且等号成立的充要条件是诸pi全相等.证明：注意此推论中条件与Jensen不等式中条件不同，故证明如下。110

证明(记,)不妨设都>0,且则由Jensen不等式知显然,当时等号不成立;时,只有当诸全相等时,等号才成立.当111

定理3.1

设b>1,则有

且,都有(2)当且仅当,都有(1)(3)当且仅当存在使得证明(1)由可知故(1)成立.(2)由Jensen不等式的推论1可知(2)成立.,再由Jensen不等式的推论1112(3)充分性:此时必要性:由于诸设H(X)=0.若存在t,使,则,从而两个值,该矛盾说明诸只能取0和1这因而必要性成立..矛盾!113定理3.1说明:(1)结果确定的随机事件不提供信息量,因而提供的信息量最少!(2)可能结果等可能发生的随机事件提供的包含的信息量最大!这与我们的直觉是一致的!114

现实中的事件都不是孤立的!很多随机事件之间都有相互的联系和影响!那么,如何刻划和研究多个随机事件相互提供的信息呢?这就要引入两个实验的联合熵条件熵互信息等概念！115

因此,实验X与实验Y的联合熵(JointEntropy)就是事件(xi,yj)的自信息量的数学期望.它反映了联合分布p(x,y

)包含的信息量.

定义3.2(联合熵):实验X与实验Y的可能结果分别为和,定义X与Y的联合熵为116

定义3.3(条件熵):实验X与实验Y的可能结果分别为和.定义X与Y的条件熵为

(1)

称为在实验Y的结果为

yj的条件下,事件xi的条件自信息量.

为在实验Y的结果为yj的条件下,实验X的条件熵.

(2)称

117(3)

称为在实验X关于实验Y的条件熵.

反映了Y的结果是yj条件下,实验X包含的信息量.反映了Y的结果已知条件下,实验X平均包含的信息量.118联合熵与各自的熵的关系

定理3.2且等号成立的充要条件是X与Y独立.

两个实验提供的信息总量一定不超过这两个实验分别提供的信息量之和;当且仅当两个实验独立时,二者才相等.直观含义:119证明(1)因,故有下证.再由和得120因,故有即现分析等号何时成立?121将上述推理过程中出现≤的地方保留,就是(1)存在常数c,使对满足的i,j,都有第一个≤变成等号的条件是:因而有第二个≤变成等号的条件是:(2)当时必有,即122对所有的i,j都成立,故有说明对所有的i,j,都有即这就证明了:X与Y独立现设成立,则X与Y独立证毕123联合熵与条件熵的关系

定理3.3直观含义:

两个实验提供的信息总量等于第一个信息提供的信息量加上在第一个实验的结果已知条件下,第二个实验提供的信息量.124联合熵与条件熵的关系

定理3.3证明：由于故有同理可证证毕125联合熵与熵的关系故有定理3.2指出:定理3.3指出:推论3.1且等号成立X与Y独立.2024/4/6126§3.2伪密钥和唯一解距离主要内容:

利用Shannon信息论,研究密文、明文和密钥的信息量。分析唯密文攻击条件下要唯一确定密钥时至少需要的密文长度。2024/4/6127

定理3.4设M,K,C分别是明文空间、密钥空间和密文空间上的随机变量，则有截获密文后密钥的未知信息量等于明文与密钥总的未知信息量减去从已知的密文中获得的信息量。直观含义:2024/4/6128

定理3.4设M,K,C分别是明文空间、密钥空间和密文空间上的随机变量，则有根据条件熵与联合熵之间的关系,有证明:由于知道密文和密钥,自然也知道明文,因而密钥和密文都知道时提供的信息量H(K,C)等于密钥、密文和明文都知道时提供的信息量H(K,M,C),即下证之.由和条件熵与联合熵的关系知同理,有,故由密钥与明文独立知2024/4/6129截获密文C后,就可将密钥唯一确定等价于

下面根据这个条件,计算至少需要多少密文才能将密钥唯一确定.将密钥唯一确定所需要的最少的密文的数量,就称为该密码体制的唯一解距离.

要求唯一解距离,需要首先计算计算出n长明文M的熵H(M)和n长密文的熵H(C).定理3.4说明:截获密文C后,就可将密钥唯一确定等价于2024/4/6130(A)n长密文熵的计算我们需要做一个合理的假设:

假设:密文是随机的!设密文字母表为Y,则n长密文就是由字母表Y中n个字母组成的密文字母串.结论:设n长密文服从均匀分布,则n长密文的熵为

证明:因n长密文共有个,从而由n长密文服从均匀分布和熵的性质知2024/4/6131

如何刻划明文本身包含的未知信息量呢?我们给出如下的定义：

设明文字母表为X,则n长明文就是由字母表X中n个字母组成的明文字母串.(B)n长明文熵的计算2024/4/6132定义3.5（2）设L是一种语言,则称为该语言L的冗余度(Redundancy).定义3.5

(1)设L是一种语言,则称为该语言L的(单字母)熵.因此,当n很大时,近似有2024/4/6133例1如果由64个二进制数构成的某类密钥

的熵平均是56比特,则该类密钥的熵为0.875比特.例2如果由64个二进制数构成的某类密钥的熵平均是56比特,则该类密钥的冗余度是

1-0.875=0.125比特即:平均每个密钥比特有0.125个比特是多余的.2024/4/6134

下面转到分析需要截获多少密文才能将密钥唯一确定的问题.2024/4/6135定义3.6称将密钥唯一确定所平均需要的最少的密文的数量为该密码体制的唯一解码量.唯一解码量也称为唯一解距离.

将密钥唯一确定等价于H(K|C)=0.下面根据定理3.4的结论计算一个密码体制的唯一解码量.2024/4/6136当截获n长明文X(n)对应的n长密文Y(n)后,就可将密钥的信息全部确定等价于现设,则有从而即

也就是说,当截获个密文字母后,就可将密钥的信息全部确定.2024/4/6137

设已知密文C(n)及对应的明文M(n).由于明文M(n)是已知的,因而此时该明文的熵H(M(n))=0,因而RL=1.这就是说,当n=H(K)/RL=128时,就可将密钥的信息唯一确定.即此时唯一解距离为128.

结论:设明文的(单字母)冗余度为,则所有密码体制的唯一解距离均为

例:对于具有128比特密钥的密码体制,平均需要128比特的已知明文,就能将密钥唯一确定.其中已知明文就是已知一个密文和它对应的明文.解毕解:2024/4/6138

几点说明:

（1）由于唯一解距离量是用熵推出来的，因而它只是将密钥唯一确定所平均需要的密文长度。由于明文熵是每份明文所包含的信息量关于所有明文的平均值，因而有时需要的密文数量少，有时需要的数量多，但其平均值就是唯一解码距离。

（2）明文熵不同，唯一解距离也不同。明文熵就是你在攻击过程中每个字母所能利用的信息量。

（3）如何确定唯一密钥？确定过程实际上能否实现，这里并不关心。一般而言，穷举攻击所需的平均密文量就是该密码体制的唯一解距离。2024/4/6139

伪密钥首先介绍候选密钥、伪密钥和等效密钥的概念。

候选密钥：攻击者在求解正确密钥时，求出的可能密钥都称为候选密钥。

平均来看,当得到的密文数量小于唯一解距离时,候选密钥未必只有一个,此时,就会有多个候选密钥.

伪密钥：攻击者得到的候选密钥中的错误密钥称为伪密钥.

等效密钥：如果两个密钥对所有明文的加密结果都相同,则称这两个密钥为等效密钥.

两个等效密钥k1和k2对应的加密函数和就是一个函数,因而它们的加密效果完全相同.2024/4/6140§3.1密码体制的数学模型密码体制由明文空间、密文空间、密钥空间和密码算法四部分构成。

被加密的明文服从明文空间上的一个概率分布pm(x)；

被使用的密钥服从密钥空间上的一个概率分布pk(x);

密文也服从密文空间上的一个概率分布pc(x)；.

注意:

密钥的分布与明文的分布独立!2024/4/6141§3.3密码体制的完善保密性

定义3.7(完善保密性)对一个密码体制而言，如果明文与密文独立，即对所有明文空间中的任一点x

和密文空间中的任一点y,都有则称该密码体制具有完善保密性(Perfectsecrecy).或称该密码体制是完全保密的。

等价刻划:一个密码体制具有完善保密性当且仅当对所有明文空间中的任一点x

和密文空间中的任一点y,都有2024/4/6142

完善保密性的信息论刻划:

条件熵刻划:完善保密性等价于

互信息刻划:完善保密性等价于

下面在(1)明文空间、密文空间和密钥空间的点的个数相等;(2)密文在密文空间中出现的概率都>0这两个条件下给出完全保密的密码体制的充要条件.143明文处理方式分组密码（blockcipher)

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

流密码（streamcipher)

又称序列密码。序列密码每次加密一位或一字节的明文。144§4.1分组密码的基本原理

定义1

分组密码就是将明文数据按固定长度进行分组，然后在同一密钥控制下逐组进行加密，从而将各个明文分组变换成一个等长的密文分组的密码。其中二进制明文分组的长度称为该分组密码的分组规模.m1m2m3mnc1c2c3cn145实现原则:(1)必须实现起来比较简单,知道密钥时加密和脱密都十分容易,适合硬件和(或)软件实现.

(2)加脱密速度和所消耗的资源和成本较低,能满足具体应用范围的需要.

例:对高速通信数据的加密----硬件实现;嵌入到系统软件的加密程序----软件实现;智能卡内数据的加密----低成本实现146安全性设计原则1.混乱原则(又称混淆原则)(Confusion)

混乱原则就是将密文、明文、密钥三者之间的统计关系和代数关系变得尽可能复杂，使得敌手即使获得了密文和明文，也无法求出密钥的任何信息；即使获得了密文和明文的统计规律，也无法求出明文的新的信息。

可进一步理解为：（1）明文不能由已知的明文，密文及少许密钥比特代数地或统计地表示出来。（2）密钥不能由已知的明文，密文及少许密钥比特代数地或统计地表示出来。1472.扩散原则(Diffusion)扩散原则就是应将明文的统计规律和结构规律散射到相当长的一段统计中去(Shannon的原话)。

也就是说让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响。如果当明文变化一个比特时,密文有某些比特不可能发生变化,则这个明文就与那些密文无关,因而在攻击这个明文比比特时就可不利用那些密文比特.148分组密码的设计方法采用乘积密码：即通过将一个弱的密码函数迭代若干次，产生一个强的密码函数，使明文和密钥得到必要的混乱和扩散。在设计迭代函数时，充分利用代替密码和移位密码各自的优点，抵消各自的缺点，从而通过多次迭代，形成一个强的分组密码算法。149§4.2

DES分组密码算法(DateEncipherStandard)一、背景简介该算法是在美国NSA（国家安全局）资助下由IBM公司开发的密码算法，其初衷是为政府非机密的敏感信息提供较强的加密保护。它是美国政府担保的第一种加密算法，并在1977年被正式作为美国联邦信息处理标准。DES主要提供非军事性质的联邦政府机构和私营部门使用，并迅速成为名声最大，使用最广的商用密码算法。150背景发明人：美国IBM公司W.Tuchman和C.Meyer1971-1972年研制成功基础：1967年美国HorstFeistel提出的理论产生：美国国家标准局（NBS)1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案标准化：DES算法1975年3月公开发表，1977年1月15日由美国国家标准局颁布为数据加密标准（DataEncryptionStandard），于

1977年7月15日生效151背景美国国家安全局（NSA,NationalSecurityAgency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位1979年，美国银行协会批准使用DES1980年，DES成为美国标准化协会(ANSI)标准1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作152DES首次被批准使用五年，并规定每隔五年由美国国家保密局作出评估，并重新批准它是否继续作为联邦加密标准。最近的一次评估是在1994年1月，美国已决定1998年12月以后将不再使用DES。因为按照现有的技术水平，采用不到几十万美元的设备，就可破开DES密码体制。目前的新标准是AES，它是由比利时的密码学家JoanDaemen和VincentRijmen设计的分组密码—Rijndael（荣代尔）。153§1

DES分组密码算法

二、算法概述（一）基本参数

分组加密算法：明文和密文为64位分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：有效密钥56位，但每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，但存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共16轮只使用了标准的算术和逻辑运算，易于实现154输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据DES加密过程155加密框图156置换定义4.1

：设S是一个有限集合，φ是从S到S的一个映射。如果对任意的u，v，当u≠v时，φ(u)≠φ(v),则称φ是S上的一个置换。157初始置换与逆初始置换

输入和输出比特的序号从左向右编排为1,2,3,…,64含义:输出的第1比特是输入的第58比特,该表示方法实现方便.158IP和IP-1IPIP—1159（二）加密算法

Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）fDES的第i圈加密结构图Ki160DES加密算的圈函数----属于Feistel模型:

Li（32位）Ri（32位）Li-1（32位）Ri-1（32位）fDES的圈函数的结构它等价于两个对合变换:Ki161注意无论f函数如何选取，DES的圈函数是一个对合变换。162DES的F

函数123163①E盒扩展

扩展变换的作用是将输入的32比特数据扩展为48比特数据扩展164①E盒扩展

扩展方式:

(1)将输入的32比特每4比特为一组分为8块;(2)分别将第m-1块的最右比特和第m+1块的最左比特添到第m块的左边和右边,形成输出的第k个6比特块.

主要原因:硬件实现简单165DES的F

函数12166压缩替代S-盒－48位压缩到32位123456……………………4344454647481234……………………29303132167②S盒行和列的序号从0起算。168②S-盒的构造169S-盒的构造要求S-盒是算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门170DES的F

函数123171③P盒置换将S-盒变换后的32比特数据再进行P盒置换，置换后得到的32比特即为f函数的输出。含义:P盒输出的第1个元是输入的第16个元。基本特点：

（1）P盒的各输出块的4个比特都来自不同的输入块；

（2）P盒的各输入块的4个比特都分配到不同的输出块之中；

（3）P盒的第t输出块的4个比特都不来自第t输入块。172

例:利用DES算法和全0密钥对输入1000000119600000进行1圈加密的结果。

（1）输入的右半部分是19600000=00011001011000000000000000000000（2）经E盒扩展后变为000011110011

101100

000000

000000

000000

000000

（3）与全0子密钥模2加后变为000011110010

101100

000000

000000

000000

000000

（4）查S盒后的32比特输出为f8372c4d11111000001101110010

110001001101