文档介绍：现代密码学与应用
——理论基础
主讲人:余艳玮
E-mail: ******@ustc.
2017/12/6
1
大纲
1 信息论
熵及其性质
语言信息率
密码系统的安全性
唯一解距离
两种基本技术:扩散和混淆
2 复杂性理论
算法的复杂性
问题的复杂性
2017/12/6
2
1 Shannon信息论
信息在信道传输中可能受到攻击,引入密码理论
阐明了密码系统,完善保密,理论保密和实际保密等概念
提出以扩散和混淆两种基本方法来设计密码
2017/12/6
3
什么是信息?
Wiener :“信息既不是物质,也不是能量,信息就是信息”。使信息成为一切系统的三大组成要素之一。
物质和能量是客观存在的、有形的,信息是抽象的、无形的。物质和能量是系统的“軀体”,信息则系统的“灵魂”。
信息要借助于物质和能量才能产生、传输、存储、处理和感知;物质和能量要借助于信息来表述和控制。
2017/12/6
4
信息的多样性
客观事物是多种多样、五花八门的,事物的状态和变化是多姿多彩、变幻无穷的,属性不同就出现了不同的信息,需要给出不同的信息定义,从而可创建不同的信息理论。
信息的不确定性引出概率信息和 Shannon信息论(Fisher等)。
信息的模糊性引出模糊信息和模糊信息论。
信息的量子属性引出量子信息和量子信息论。
信息的复杂性引出信息复杂度和复杂度的信息理论。
信息的感知属性引出感知信息和感知的信息理论。
信息的美学属性引出美学信息和美学的信息理论。
等等,不一而足。
2017/12/6
5
信息量度定义的困难性
在众多不同属性的信息中,只有少数几种信息有了合适的量度,如不确定信息。
大多数信息是可以感知、但无法度量,因为还未找到合适的信息量的定义,因而也就建立不起来像Shannon信息论那样的理论。
例如我们对情感信息中的喜、怒、哀、乐、爱、恨、恩、怨等都能感知,但我们还难于度量它们,我们还只能用一些比较模糊的形容词来描述不同程度的感情。如“你问我对你的爱有多深,我爱你有几分,你去想一想,你去看一看,月亮代表我的心。”我们还不能确切地给出“这份爱”有多少“比特”,“那份爱”比“这份爱”又多多少“比特”。对于美学信息也是如此。另外,这类信息具有很强的主观性,这就更增大了给出客观量度定义的困难性。
2017/12/6
6
香农简介
香农(1916-2001),生于美国密执安州的加洛德。1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部,在此工作了15年。
2017/12/6
7
香农理论简介(1)
奠定了香农信息基本理论的基础。他在文中用非常简洁的数学公式定义了信息时代的基本概念:熵。
“熵”的概念起源于热力学,是度量分子不规则热运动的单位。香农的伟大贡献在于,利用概率分布的理论给出“熵”的严格定义。
根据香农的定义,确定发生的事件如“太阳从东边升起”与确定不发生的事件如“太阳从西边升起”,其熵都是零。只有当发生与不发生的概率相同时,事件的熵才达到极大。
2017/12/6
8
香农理论简介(2)
在熵的基础上定义的信道容量也是通讯中一个至关重要的概念。由此,香农推出了一个公式,明确表达了在不同噪声情况下传输速率与失真的定量关系。从这一个公式导出的为达到无失真通讯的传输速率的极限,现已称为香农极限。打个比方来说,在周围干扰严重的情况下,要想使对方听清楚,你就只有慢慢地讲,甚至还要不断重复。
2017/12/6
9
香农理论应用
如今,这两个原理已广泛应用于信息处理和实际通信中。只要涉及信息的压缩与传递,就要用到香农的理论。
PC机上常用的WinZip (无损压缩算法)
手机通讯(有损压缩无损压缩,纠错)
在因特网上传递多媒体数据
(MP3音乐压缩格式)
2017/12/6
10