b第二周 信息论与数学基础(第2章).ppt

1,华南理工大学电子商务学院本科课程电子商务安全与保密,第2章信息论与数学基础,2,信息论的概念,公式：H(x)=含义：不确定性，即一条信息当中的信息量。/越大越好一个只有一个字符的语言（熵-(1)*log2(1)=0）完全随机语言:-(1/26)*log2(1/26)-log2(1/26)4.xx/一个字母对任意字母的映射直观来说:从一个信息元推断其它信息元的可能性,熵越小,可能性越大例子，如果信息不是男就是女，那么H(m)-1/2log2(1/2)+(-1/2)log2(1/2)=1联合熵条件熵,3,信息率：r=H(M)/N，N是消息的长度绝对信息率R=log2L语言的多余度D=R-r/越少越好，减少被推测可能英语的信息率估计是1.2，绝对信息率是4.7(L=26)，则冗余度估计是3.5唯一解距离：进行强力攻击时，可能解出唯一有意义的明文所需要的最少密文量，定义为U=H(K)/D/越长越好，与冗余度成反比,信息论的概念,4,密码体制的安全性,无条件安全或完善保密性（unconditionallysecurity）：不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。存在完善保密系统如：一次一密（one-timepad）方案；/量子密码。实际上安全或计算安全性（computationalsecurity）计算上是安全：即使算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。从理论上证明破译它的计算量不低于解已知难题的计算量，因此（在现阶段）是安全的,5,扩散和混淆是C.E.Shannon提出的设计密码体制的两种基本方法，其目的是为了抵抗对手对密码体制的统计分析，可抵抗对手从密文的统计特性推测明文和密钥。/Thebasictechniquesforthisarecalledconfusion(混淆)anddiffusion(扩散).Theseroughlycorrespondtosubstitution(替代)andpermutation(置换),扩散和混淆,6,扩散：为避免密码分析者对密钥逐段破译，密码的设计应该保证密钥的每位数字能够影响密文中的多位数字；同时，为了避免避免密码分析者利用明文的统计特性，密码的设计应该使明文中的每1个bit影响密文的多个bit，或说密文中每1个bit受明文中多个bit影响，从而隐藏明文的统计特性。混淆：为了避免密码分析者利用明文与密文之间的依赖关系进行破译，将密文和密钥之间的统计关系变得尽可能复杂。,扩散和混淆,7,最大公因子：任意有限个整数的公因子中的最大一个。必然存在并且惟一，记为。最小公倍数：任意有限个整数的公倍数中的最小一个。必然存在并且惟一，记为。互素数：C=gcd（a，b）称C是两个整数a，b的最大公因子。要求最大公因子为正/gcd（a，0）=|a|如果gcd（a，b）=1则称a和b互素。,数论基础,8,模运算1、设n是一正整数，a是整数，a=q.n+r0rnq=a/n其中X为小于或等于X的最大整数。用amodn表示余数ra=a/nn+amodn2、如果（amodn）=（bmodn）称两整数a，b模n同余，记为abmodn/例如时钟的1mod12=13mod12称与a模n同余的数的全体为a的同余类，记为a，称a为这个同于类的表示元素。若a0modn则n|a/整除,数论基础,9,3、模运算性质若n|（a-b）则abmodnabmodn则bamodnabmodnbcmodn则acmodn(amodn)+(bmodn)modn=(a+b)modn(amodn)-(bmodn)modn=(a-b)modn(amodn)(bmodn)modn=(ab)modn(a+b)modn=(b+a)modn交换律(ab)modn=(ba)modn(a+b)+cmodn=a+(b+c)modn结合律a(b+c)modn=(ab)+(ac)modn分配律,数论基础,10,数论基础,11,数论基础,12,离散对数模指数方程：已知a、b、n三个参数，求x，使满足axb(modn)之所以称为离散对数：按指数方程和对数的关系,x=logab(modn)离散的两个方面：（1）结果x必须为整数；（2）必须考虑modn的影响,数论基础,13,RSA算法,安全性依赖于大数的因子分解。是第一个较为完善的公钥算法，能够同时用于加密和数字签名，且易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥算法之一。目前仍然无法从理论上证明它的保密性能究竟如何，因为目前人们并没有从理论上证明破译RSA的难度与大整数分解问题的难度等价。,DES和RSA标准的比较,14,RSA算法,设分组长度为lbit，每个分组M被看作是一个lbit的二进制值。取某一个整数n（大整数），使对所有M，有Mn一般，n的取值满足2ln2l+1。加密算法C=Memodn。解密算法M=Cdmodn=(Me)dmodn=Medmodn。加密密钥（公开密钥）为KU=e,n。解密密钥（私有密钥）为KR=d,n。要求：e,d,n使对所有Marchivefiles