第二章信息论及数学基础.ppt

信息论与数学基础,熵,“熵”是德国物理学家克劳修斯在年创造的一个定义，他用熵的定义来表示任何一种能量在空间中分布的均匀程度。能量分布得越均匀，熵就越大。如果对于我们所考虑的那个系统来说，能量完全均匀地分布，那么，这个系统的熵就达到最大值。,2.1信息论,1948年由香农（claudeelmwoodshannon）确立了信息论从通信的实质意义来讲，如果接收者收到的消息是已知的，则等于没有收到任何消息。因此，人们更感兴趣的是消息中所包含的未知成分，用概率论的术语来讲，就是具有不确定性的成分，香农将该成分称为信息，并进行了数量描述。,2.1信息论,信息量：对消息的所有可能含义进行编码时所需要的最少比特数例如对于一周中的时间或性别进行有效编码一条消息中的信息量可以通过熵来度量,1熵和不确定性,在1948年由克劳德艾尔伍德香农第一次引入到信息论中来。定义如果有一个系统S内存在多个事件S=E1,.,En，每个事件的机率分布P=p1,.,pn，则每个事件本身的信息为：Ie=log2pi（对数以2为底，单位是位元(bit)）Ie=lnpi（对数以e为底，单位是纳特/nats）,例如1）如英语有26个字母，假如每个字母在文章中出现次数平均的话，每个字母的信息量为：2）汉字常用的有2500个，假如每个汉字在文章中出现次数平均的话，每个汉字的信息量为,熵是整个系统的平均消息量，即：熵均大于等于零，HS=0设N是系统S内的事件总数，则熵HS=log2N。当且仅当p1=p2=.=pn时，等号成立，此时系统S的熵最大。安全角度看消息的熵值描述了明文的不确定性，熵值越小不确定越低，被攻击的可能性越大。信息熵大，意味着不确定性也大。,2.密码体制的安全性在密码学方面，1949年香农发表保密系统的通信理论，通常它被认为是密码学的先驱性著作。1976年狄菲和赫尔曼首次提出公开密钥体制，为密码学的研究开辟了新的方向。超大规模集成电路和高速计算机的应用,促进了保密编码理论的发展,同时也给保密通信的安全性带来很大的威胁。70年代以来把计算机复杂性理论引入密码学,出现了所谓P类、NP类和NP完全类问题。算法的复杂性函数呈指数型增长，因此密钥空间扩大，使密码的分析和搜索面临严重的挑战。密码学开始向纵深方向发展。,保密编码:为了防止窃译而进行的再编码称为保密编码。其目的是为了隐藏敏感的信息。常采用替换或乱置或两者兼有的方法。一个密码体制通常包括两个基本部分：加（解）密算法和可以更换的控制算法的密钥。密码根据它的结构分为序列密码和分组密码两类。序列密码是算法在密钥控制下产生的一种随机序列，并逐位与明文混合而得到密文。其主要优点是不存在误码扩散，但对同步有较高的要求。它广泛用于通信系统中。分组密码是算法在密钥控制下对明文按组加密。这样产生的密文位一般与相应的明文组和密钥中的位有相互依赖性，因而能引起误码扩散。它多用于消息的确认和数字签名中。,密码学还研究通过破译来截获密文的方法。破译方法有确定性分析法和统计性分析法两类。确定性分析法是利用一个或几个未知量来表示所期望的未知量从而破译密文。统计分析法是利用存在于明文与密文或密钥之间的统计关系破译密文。,3唯一解距离定义：进行强力攻击时，可能解密出唯一有意义的明文所需要的最少密文量。一般来说，唯一解距离越大，密码体制越好比解距长的密文可以合理的确定唯一的有意义的解密文本，比解距短的密文可能会有多个同样等效的解密文本，这样增加了选择正确的难度，可以获得安全性。定义：U=H(K)/D其中D是语言多余度，H(K)密码体制的熵。唯一解距很小，密码体制不安全；但不一定是唯一解距大就一定安全。,4语言信息率语言信息率：r=H(M)/N其中H(M)是熵，N是消息的长度语言的绝对信息率：R=log2L其中L是语言中字母数，R也是单个字母的最大熵。语言的多余度：D=R-r5混乱和散布混乱：也可以称为替换散布：也可以称为置换，位置的变化。,2.2复杂性理论,分析不同密码技术和算法的的“计算复杂性”的方法，通过对密码算法及技术进行比较，确定其安全性。1）算法的复杂性一个算法的复杂性由两个变量来描述：T(时间复杂度)、S（空间复杂度），T和S表示为n的函数，n是输入尺寸。一个算法的复杂度可以用O符号表示，O(n2)时间复杂度和空间复杂度与输入的尺寸有关,2）问题的复杂性P问题：能够在多项式时间内解决的问题（时间复杂度）NP问题：多项式时间内可验证的问题NP完全问题：特殊的问题，如果NP完全问题解决了，则NP问题也解决了。PSPACE问题：比NP复杂性更高的问题。3）NP完全问题1.整数分解的问题：大整数分解成素数相乘，整数越大越难分解,2.背包问题设长度为N的向量A=(a1,a2,an),任意给定一个正整数K,求解方程xiai=k,即求解向量x=(x1,x2,xn)当n很小可以用穷举法，但n很大时就不行了3.离散对数问题设x,r,n是正整数，已知x,r,n可以很快求出y=xrmod但反过来求r属于离散对数问题,2.3密码学的必要性,一个问题-密码学真的有必要吗CDUniverse信用卡数据泄漏案VisaInternational笔记本失窃案美加州大学资料库被黑事件,有一个影响很大的例子，就是2000年1月发生的CDUniverse信用卡数据库泄露案事件。一名据称是来自俄罗斯的攻击者成功地通过因特网拷贝了CDUniverse数据库中300000个信用卡号码，然后他试图向CDUniverse勒索保护费。CDUniverse拒绝支付这笔钱，结果该黑客就在Web上公布了25000个信用卡号码。对于CDUniverse的顾客来说，风险不大，因为信用卡是有保护的，这种保护将使用信用卡所要承担的风险限制在一个比较小的范围内，一般是50美元或者更少。,然而对于CDUniverse来说非常不幸，顾客对公司的信任度降低了，因面对他们的业务造成了显著影响。而如果已经使用密码技术加密了信用卡号码数据库，那么即使攻击者能够拷贝商家的数据库，他们恐怕也无法提取其中的信用卡号码。,VisaInternational笔记本失窃案,1996年11月，VisaInternational的一台笔记本电脑被盗。不幸的是这台笔记本电脑保存了超过314000个信用卡号码。公布的替换一张信用卡的成本是20美元，因此这一次盗窃造成的掘失大约为630万美元。同样，只要对存储在这台笔记本电脑硬盘上的信用卡信息进行了加密就不会有这样的问题发生，从而会节省上百万美元的费用。,美加州大学资料库被黑事件,一个例子把九阴真经发给我,网络环境下数据安全性的要求我要接受来自黄裳的九阴真经安全的要求：1）我能确保经文来自黄裳确保文件来自正确的方向2）我能确保经文在因特网上传输接收方确保文件在互联网上传输时，没有被修改3）没有别人能够看到经文，因为那是发送给我的，这样就防止了经文被窃只有指定的接收者可以看到经文，防止文件被窃4）黄裳事后不能否认发送了经文给我发送方不能否认发送过文件,2.4密码学,1.基本概念算法：是解决一个数学问题所需要的一组步骤。在计算机科学领域中，算法通常被看作程序的一个组成部分，通常作为一个例程或者一个库被引用。密码算法(cryptographicalgorithm)：是数学算法，设计密码算法是为了能够用不同的数据集合作为参数来调用它们，从而在这些数据集合上进行相应的运算,密码服务提供者(CryptographicServiceProvider，CSP)：从本质上讲就是可以通过一套定义良好的接口进行调用的，执行特定密码计算功能的密码算法(加密算法、签名算法等)库。密码学家(cryptologist)：是一些数学家和研究者，他们绞尽脑汁地发明新的密码算法。密码破译者就登场了。他们装备了强大的工具，全力以赴地分析算法的弱点，围绕算法的设计进行各种各样的拷问和攻击以求攻破该算法。密码学是计算机科学中有着两个平行、对立而又共生的子分支的分支学科。包括密码编码学(cryptography)和密码分析学(cryptanalysis)。,2.朦胧安全发明了一个加密算法，但却不提交给密码破译者审核但这些算法都是复杂的数学运算，一个人无法了解该运算的所有方面，因此无法了解所有可能的攻击。这种算法的安全就称为朦胧安全。朦胧算法不安全的例子1997年counterpanesysytem公司和UCberkeley合作破解了蜂窝电话保报文加密算法，这个算法用来加密信用卡号2000年adishamir破解了A5系列算法当中的一个，A5系列算法是整个欧洲和美国所使用的保护数字蜂窝通信的算法。,密码学是这样一个概念，某些计算在一个方向是容易的，然而在相反的方向确实及其困难的。例如：两个大的素数相乘的乘积确定，请确定这两个大的素数。求一个数的素因子被人们认为是一个极为困难的数学问题。不同密码算法是基于不同的数学难题，但密码算法都有一个陷门，可以利用陷门破解反方向的问题。,陷门:计算机操作的陷门设置是指进入程序的秘密人口,它使得知道陷门的人可以不经过通常的安全检查访问过程而获得访问。单向陷门函数是这样的函数，即除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，而在反方向上要计算是不可行的。网络上文件安全传输的表示,密文,2.5数论,1.模运算两位朋友在早上9：00相约，5个小时后在某地见面那么14：00和下午2：00可以表示同一时间。为什么会相等取模运算9+5=14=2（mod12）或表示为,若a=b+kn对某些整数k成立，则有,如果a,b都是正整数，b在0到n之间，称b为a模n的余数或a和b是模n的同于模运算也和其他运算一样，具有交换、结合、可分配特性。P44页,特性a=amodn若a=bmodn,则b=amodn若a=bmodn,b=cmodn,则a=cmodna=bmodn,c=dmodn,则a+c=(b+d)modna-c=(b-d)modna*c=(b*d)modnaxmodn可以将其分解成系列乘法和除法取模,2.素数素数是这样一种数，比1大但因子除了1和他本身，没有其他的数可以整数它。在密码学中，特别是公开密钥算法中，素数通常都是512位、1024位的大素数3.两数互素如果这两个数的最大公因子是1，则这两