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

,单击此处编辑母版标题样式,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,华南理工大学电子商务学院本科课程,电子商务安全与保密,第,2,章 信息论与数学基础,1,信息论的概念,公式：,H(x,)=,含义：不确定性，即一条信息当中的信息量。,/,越大越好,一个只有一个字符的语言（熵-(1)*,log,2,(1),=0,）,完全随机语言:,-,(1/26)*,log,2,(1/26),-,log,2,(1/26),4.,xx,/,一个字母对任意字母的映射,直观来说:从一个信息元推断其它信息元的可能性,熵越小,可能性越大,例子，如果信息不是男就是女，,那么,H(m,),-,1/2log,2,(1/2)+(-1/2)log,2,(1/2)=1,联合熵,条件熵,2,信息率：,r=H(M)/N,，,N,是消息的长度,绝对信息率,R=log,2,L,语言的多余度,D=R-r/,越少越好，减少被推测可能,英语的信息率估计是,1.2,，绝对信息率是,4.7(L=26),，则冗余度估计是,3.5,唯一解距离：进行强力攻击时，可能解出唯一有意义的明文所需要的最少密文量，定义为,U=H(K)/D/,越长越好，与冗余度成反比,信息论的概念,3,密码体制的安全性,无条件安全或完善保密性（,unconditionally security,）,：,不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；,具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。,要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。,从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。,存在完善保密系统,如：一次一密（,one-time pad,）方案；,/,量子密码。,实际上安全或计算安全性（,computational security）,计算上是安全：即使算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。,从理论上证明破译它的计算量不低于解已知难题的计算量，因此（在现阶段）是安全的,4,扩散和混淆是,C.E.Shannon,提出的设计密码体制的两种基本方法，其目的是为了抵抗对手对密码体制的统计分析，可抵抗对手从密文的统计特性推测明文和密钥。,/The basic techniques for this are called confusion(,混淆,)and diffusion(,扩散,).These roughly correspond to substitution(,替代,)and permutation(,置换,),扩散和混淆,5,扩散：为避免密码分析者对密钥逐段破译，密码的设计应该保证密钥的每位数字能够影响密文中的多位数字；同时，为了避免避免密码分析者利用明文的统计特性，密码的设计应该使明文中的每,1,个,bit,影响密文的多个,bit,，或说密文中每,1,个,bit,受明文中多个,bit,影响，从而隐藏明文的统计特性。,混淆：为了避免密码分析者利用明文与密文之间的依赖关系进行破译，将密文和密钥之间的统计关系变得尽可能复杂。,扩散和混淆,6,最大公因子,：任意有限个整数 的公因子中的最大一个。必然存在并且惟一，记为 。,最小公倍数,：任意有限个整数 的公倍数中的最小一个。必然存在并且惟一，记为 。,互素数：,C=,gcd,（,a,，,b,）称,C,是两个整数,a,，,b,的最大公因子。,要求最大公因子为正,/,gcd,（,a,，,0,）,=|a|,如果,gcd,（,a,，,b,）,=1,则称,a,和,b,互素。,数论基础,7,模运算,1,、设,n,是一正整数，,a,是整数，,a=,q,.,n+r,0,r,n q=,a/n,其中,X,为小于或等于,X,的最大整数。,用,a mod n,表示余数,r,a=a/n n+a mod n,2,、如果（,a mod n,）,=,（,b mod n,）称两整数,a,，,b,模,n,同余,，,记为,a,b,mod,n /,例如时钟的,1 mod 12=13 mod 12,称与,a,模,n,同余的数的全体为,a,的同余类，记为,a,，称,a,为这,个同于类的表示元素。,若,a 0 mod n,则,n|a /,整除,数论基础,8,3,、模运算性质,若,n|,（,a-b,）则,a b mod n,a b mod n,则,b a mod n,a b mod n b c mod n,则,a c mod n,(a mod n)+(b mod n)mod n,=(,a+b,)mod n,(a mod n)-(b mod n)mod n=(a-b)mod n,(a mod n),(b mod n)mod n=(,a,b,)mod n,(,a+b,)mod n=(,b+a,)mod n,交换律,(,a,b,)mod n=(,b,a,)mod n,(,a+b)+c,mod n=,a+(b+c,)mod n,结合律,a(b+c,)mod n=(,ab)+(ac,)mod n,分配律,数论基础,9,4,、加法逆元,定义,Z,n,为小于,n,的所有非负整数集合，即,Z,n,=0,1,n-1,对于,x,Z,n,，,存在,y,Zn,，,使,x+y,0 mod n,，记为,y=-x,称,y,为,x,的负数，也称加法逆元。,例如：,Z,8,=0,，,1,，,7,x+y,0 mod 8,(,x,y,)(0,0)(1,7)(2,6)(3,5)(4,4),性质：（,a+b,）（,a+c,）,mod n,则,b c mod n,称为加法的可约律,数论基础,10,5,、乘法逆元,定义,Z,n,为小于,n,的所有非负整数集合，即,Z,n,=0,1,n-1,对于,x,Z,n,，,gcd,（,x,n,）,=1,，,存在,y,Zn,，,使,x,y,1 mod n,，记为,y=x,-1,，,称,y,为,x,的倒数，也称,y,是,x,在模,n,下的乘法逆元。,例如：,Z,8,=0,，,1,，,7,xy,1 mod 8,(,x,y,)(1,1)(3,3)(5,5)(7,7),性质：,（,a,b,）（,a,c,）,mod n,，且,a,有乘法逆元,则,b c mod n,，称为乘法可约律,逆元未必一定存在,数论基础,11,离散对数,模指数方程：已知,a、b、n,三个参数，求,x，,使满足,a,x,b(mod n),之所以称为离散对数：按指数方程和对数的关系,x=,log,a,b(mod,n),离散的两个方面：（1）结果,x,必须为整数；（2）必须考虑,mod n,的影响,数论基础,12,RSA,算法,安全性依赖于大数的因子分解。是第一个较为完善的公钥算法，能够同时用于加密和数字签名，且易于理解和操作。,RSA,是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥算法之一。目前仍然无法从理论上证明它的保密性能究竟如何，因为目前人们并没有从理论上证明破译,RSA,的难度与大整数分解问题的难度等价。,DES,和,RSA,标准的比较,加密机制,DES,RSA,原理,加密钥,=,解密钥,加密钥,解密钥,算法,公开,公开,密钥配送,必要,不必要,密钥数,必须为通信对象数,自己用的一个即可,安全确认,比较困难,容易,加密速度,可达,100MB/S,可达,10KB/S,13,RSA,算法,设分组长度为,l,bit,，每个分组,M,被看作是一个,l,bit,的二进制值。,取某一个整数,n,（,大整数），使对所有,M,，有,M,n,一般，,n,的取值满足,2,l,n 2,l,+1,。,加密算法,C=M,e,mod,n。,解密算法,M=,C,d,mod,n,=(M,e,),d,mod,n,=M,ed,mod,n。,加密密钥（公开密钥）为,K,U,=,e,n,。,解密密钥（私有密钥）为,K,R,=,d,n,。,要求：,e,d,n,使对所有,M,n,都有：,M=M,ed,mod,n,对所有,M,filesystem,对应,bc,的,src,目录,/import-archive files,对应,junit-src.jar,文件,把该下载包的,jar,放置到,jre,libext,目录下,下载,jce_policy-1_4_2.zip,把其中的,jar,文件放置到,jre,libsecurity,目录下,运行,RegressionTest,，可以检验各种算法,22,23,