《b第二周 信息论与数学基础(第2章).ppt》由会员分享，可在线阅读，更多相关《b第二周 信息论与数学基础(第2章).ppt（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、华南理工大学电子商务学院本科课程电子商务安全与保密第2章信息论与数学基础1信息论的概念n公式：H(x)=n含义：不确定性，即一条信息当中的信息量。/越大越好n一个只有一个字符的语言（熵-(1)*log2(1)=0）n完全随机语言:-(1/26)*log2(1/26)-log2(1/26)4.xx/一个字母对任意字母的映射n直观来说:从一个信息元推断其它信息元的可能性,熵越小,可能性越大n例子，如果信息不是男就是女，那么H(m)-1/2log2(1/2)+(-1/2)log2(1/2)=1n联合熵n条件熵2n信息率：r=H(M)/N，N是消息的长度n绝对信息率R=log2Ln语言的多余度D=R-
2、r/越少越好，减少被推测可能n英语的信息率估计是1.2，绝对信息率是4.7(L=26)，则冗余度估计是3.5n唯一解距离：进行强力攻击时，可能解出唯一有意义的明文所需要的最少密文量，定义为U=H(K)/D/越长越好，与冗余度成反比信息论的概念3密码体制的安全性密码体制的安全性n无条件安全或完善保密性（unconditionallysecurity）：n不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；n具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。n要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的
3、熵。n从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。n存在完善保密系统如：一次一密（one-timepad）方案；/量子密码。n实际上安全或计算安全性（computationalsecurity）n计算上是安全：即使算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。n从理论上证明破译它的计算量不低于解已知难题的计算量，因此（在现阶段）是安全的4 扩散和混淆是扩散和混淆是扩散和混淆是扩散和混淆是C.E.ShannonC.E.ShannonC.E.ShannonC.E.Shanno
4、n提出的设计密码体制的两种基本方提出的设计密码体制的两种基本方提出的设计密码体制的两种基本方提出的设计密码体制的两种基本方法，其目的是为了抵抗对手对密码体制的统计分析，可抵抗对法，其目的是为了抵抗对手对密码体制的统计分析，可抵抗对法，其目的是为了抵抗对手对密码体制的统计分析，可抵抗对法，其目的是为了抵抗对手对密码体制的统计分析，可抵抗对手从密文的统计特性推测明文和密钥。手从密文的统计特性推测明文和密钥。手从密文的统计特性推测明文和密钥。手从密文的统计特性推测明文和密钥。/The basic techniques for this are called confusion /The basic
5、techniques for this are called confusion /The basic techniques for this are called confusion /The basic techniques for this are called confusion(混淆混淆混淆混淆)and diffusion()and diffusion()and diffusion()and diffusion(扩散扩散扩散扩散).These roughly correspond).These roughly correspond).These roughly correspond)
6、.These roughly correspond to substitution(to substitution(to substitution(to substitution(替代替代替代替代)and permutation()and permutation()and permutation()and permutation(置换置换置换置换)扩散和混淆5扩散：为避免密码分析者对密钥逐段破译，密码的设计应该扩散：为避免密码分析者对密钥逐段破译，密码的设计应该扩散：为避免密码分析者对密钥逐段破译，密码的设计应该扩散：为避免密码分析者对密钥逐段破译，密码的设计应该保证密钥的每位数字能够影响密文
7、中的多位数字保证密钥的每位数字能够影响密文中的多位数字保证密钥的每位数字能够影响密文中的多位数字保证密钥的每位数字能够影响密文中的多位数字 ；同时，；同时，；同时，；同时，为了避免避免密码分析者利用明文的统计特性，密码的设为了避免避免密码分析者利用明文的统计特性，密码的设为了避免避免密码分析者利用明文的统计特性，密码的设为了避免避免密码分析者利用明文的统计特性，密码的设计应该使明文中的每计应该使明文中的每计应该使明文中的每计应该使明文中的每1 1个个个个bitbit影响密文的多个影响密文的多个影响密文的多个影响密文的多个bitbit，或说密文，或说密文，或说密文，或说密文中每中每中每中每1 1
8、个个个个bitbit受明文中多个受明文中多个受明文中多个受明文中多个bitbit影响，从而隐藏明文的统计特影响，从而隐藏明文的统计特影响，从而隐藏明文的统计特影响，从而隐藏明文的统计特性。性。性。性。混淆：为了避免密码分析者利用明文与密文之间的依赖关系混淆：为了避免密码分析者利用明文与密文之间的依赖关系混淆：为了避免密码分析者利用明文与密文之间的依赖关系混淆：为了避免密码分析者利用明文与密文之间的依赖关系进行破译，将密文和密钥之间的统计关系变得尽可能复杂。进行破译，将密文和密钥之间的统计关系变得尽可能复杂。进行破译，将密文和密钥之间的统计关系变得尽可能复杂。进行破译，将密文和密钥之间的统计关系
9、变得尽可能复杂。扩散和混淆6n最大公因子最大公因子：任意有限个整数的公因子中的最大一个。必然存在并且惟一，记为。n最小公倍数最小公倍数：任意有限个整数的公倍数中的最小一个。必然存在并且惟一，记为。n互素数：C=gcd（a，b）称C是两个整数a，b的最大公因子。要求最大公因子为正/gcd（a，0）=|a|如果gcd（a，b）=1则称a和b互素。数论基础7模运算模运算模运算模运算 1 1、设、设、设、设n n是一正整数，是一正整数，是一正整数，是一正整数，a a是整数，是整数，是整数，是整数，a=a=q q.n+rn+r 0 0 r rn q=n q=a/n a/n 其中其中其中其中 X X 为小
10、于或等于为小于或等于为小于或等于为小于或等于X X的最大整数。的最大整数。的最大整数。的最大整数。用用用用a mod n a mod n 表示余数表示余数表示余数表示余数r r a=a/n n+a mod n a=a/n n+a mod n 2 2、如果（、如果（、如果（、如果（a mod na mod n）=（b mod nb mod n）称两整数）称两整数）称两整数）称两整数a a，b b模模模模n n同余同余同余同余，记为记为记为记为 a a b b modmod n /n /例如例如例如例如时钟时钟的的的的1 mod 12=13 mod 12 1 mod 12=13 mod 12 称与
11、称与称与称与a a模模模模n n同余的数的全体同余的数的全体同余的数的全体同余的数的全体为为a a的同余的同余的同余的同余类类，记为记为aa，称，称，称，称a a为这为这 个同于个同于个同于个同于类类的表示元素。的表示元素。的表示元素。的表示元素。若若若若a 0 mod n a 0 mod n 则则 n|a /n|a /整除整除整除整除数论基础8 3 3、模运算性、模运算性、模运算性、模运算性质质 若若若若n|n|（a-ba-b）则则 a b mod na b mod n a b mod n a b mod n 则则 b a mod nb a mod n a b mod n b c mod n
12、 a b mod n b c mod n 则则 a c mod na c mod n (a mod n)+(b mod n)mod n(a mod n)+(b mod n)mod n=(=(a+ba+b)mod n)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)(a mod n)(b mod n)mod n=(b mod n)mod n=(a a b b)mod n)mod n (a+ba+b)mod n=()mod n=(b+ab+a)mod n )mod n 交换律
13、交换律交换律交换律 (a a b b)mod n=()mod n=(b b a a)mod n)mod n (a+b)+ca+b)+c mod n=mod n=a+(b+ca+(b+c)mod n )mod n 结结合律合律合律合律 a(b+ca(b+c)mod n=()mod n=(ab)+(acab)+(ac)mod n )mod n 分配律分配律分配律分配律数论基础94 4、加法逆元、加法逆元、加法逆元、加法逆元 定定定定义义Z Zn n为为小于小于小于小于n n的所有非的所有非的所有非的所有非负负整数集合，即整数集合，即整数集合，即整数集合，即Z Zn n=0,1,n-1=0,1,n-
14、1 对对于于于于x x Z Zn n，存在存在存在存在y y ZnZn，使使使使x+yx+y 0 mod n 0 mod n，记为记为y=-xy=-x 称称称称y y为为x x的的的的负负数，也称加法逆元。数，也称加法逆元。数，也称加法逆元。数，也称加法逆元。例如：例如：例如：例如：Z Z8 8=0=0，1 1，7 7 x+yx+y 0 mod 8 0 mod 8 (x,yx,y)(0,0)(1,7)(2,6)(3,5)(4,4)(0,0)(1,7)(2,6)(3,5)(4,4)性性性性质质：（：（：（：（a+ba+b）（a+ca+c）mod n mod n 则则 b c mod nb c m
15、od n 称称称称为为加法的可加法的可加法的可加法的可约约律律律律数论基础105、乘法逆元、乘法逆元 定定义Zn为小于小于n的所有非的所有非负整数集合，即整数集合，即Zn=0,1,n-1 对于于x Zn，gcd（x,n）=1，存在存在y Zn，使使xy 1 mod n，记为y=x-1，称称y为x的倒数，也称的倒数，也称y是是x在模在模n下的乘法逆元。下的乘法逆元。例如：例如：Z8=0，1，7 xy 1 mod 8 (x,y)(1,1)(3,3)(5,5)(7,7)性性质：（ab）（ac）mod n，且，且a有乘法逆元有乘法逆元 则则 b c mod n，称为乘法可约律，称为乘法可约律 逆元未必
16、一定存在逆元未必一定存在数论基础11n离散对数n模指数方程：已知a、b、n三个参数，求x，使满足ax b(mod n)n之所以称为离散对数：按指数方程和对数的关系,x=logab(mod n)n离散的两个方面：（1）结果x必须为整数；（2）必须考虑modn的影响数论基础12RSA算法n安全性依赖于大数的因子分解。是第一个较为完善的公钥算法，能够同时用于加密和数字签名，且易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥算法之一。目前仍然无法从理论上证明它的保密性能究竟如何，因为目前人们并没有从理论上证明破
17、译RSA的难度与大整数分解问题的难度等价。DESDES和和和和RSARSA标准的比较标准的比较标准的比较标准的比较加密机制加密机制加密机制加密机制DESDESRSARSA原理原理原理原理加密钥加密钥加密钥加密钥=解密钥解密钥解密钥解密钥加密钥加密钥加密钥加密钥 解密钥解密钥解密钥解密钥算法算法算法算法公开公开公开公开公开公开公开公开密钥配送密钥配送密钥配送密钥配送必要必要必要必要不必要不必要不必要不必要密钥数密钥数密钥数密钥数必须为通信对象数必须为通信对象数必须为通信对象数必须为通信对象数自己用的一个即可自己用的一个即可自己用的一个即可自己用的一个即可安全确认安全确认安全确认安全确认比较困难比
18、较困难比较困难比较困难容易容易容易容易加密速度加密速度加密速度加密速度可达可达可达可达100MB/S100MB/S可达可达可达可达10KB/S10KB/S13RSA算法n设分组长度为l bit，每个分组M被看作是一个l bit的二进制值。n取某一个整数n（大整数），使对所有M，有Mnn一般，n 的取值满足2ln2l+1。n加密算法nC=Memodn。n解密算法nM=Cdmodn=(Me)dmodn=Medmodn。n加密密钥（公开密钥）为KU=e,n。n解密密钥（私有密钥）为KR=d,n。n要求：ne,d,n使对所有M n都有：M=Medmodnn对所有Mfilesystem对应bc的src目录n/import-archivefiles对应junit-src.jar文件n把该下载包的jar放置到jrelibext目录下n下载jce_policy-1_4_2.zip,把其中的jar文件放置到jrelibsecurity目录下n运行RegressionTest，可以检验各种算法2223