b第二周-信息论与数学基础

华南理工大学电子商务学院

本科课程－－电子商务安全与保密第2章信息论与数学基础1第1页信息论概念公式：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联合熵条件熵2第2页信息率：r=H(M)/N，N是消息长度绝对信息率R=log2L语言多出度D=R-r//越少越好，降低被推测可能英语信息率预计是1.2，绝对信息率是4.7(L=26)，则冗余度预计是3.5唯一解距离：进行强力攻击时，可能解出唯一有意义明文所需要最少密文量，定义为U=H(K)/D//越长越好，与冗余度成反比信息论概念3第3页密码体制安全性无条件安全或完善保密性（unconditionallysecurity）：不论提供密文有多少，密文中所包含信息都不足以惟一地确定其对应明文；含有没有限计算资源（诸如时间、空间、资金和设备等）密码分析者也无法破译某个密码系统。要结构一个完善保密系统，其密钥量对数（密钥空间为均匀分布条件下）必须大于明文集熵。从熵基本性质可推知，保密系统密钥量越小，其密文中含有关于明文信息量就越大。存在完善保密系统 如：一次一密（one-timepad）方案；//量子密码。实际上安全或计算安全性（computationalsecurity）计算上是安全：即使算出和预计出破译它计算量下限，利用已经有最好方法破译该密码系统所需要努力超出了破译者破译能力（诸如时间、空间、资金等资源）。从理论上证实破译它计算量不低于解已知难题计算量，所以（在现阶段）是安全4第4页扩散和混同是C.E.Shannon提出设计密码体制两种基本方法，其目标是为了抵抗对手对密码体制统计分析，可抵抗对手从密文统计特征推测明文和密钥。//Thebasictechniquesforthisarecalledconfusion(混同)anddiffusion(扩散).Theseroughlycorrespondtosubstitution(替换)andpermutation(置换)

扩散和混同5第5页扩散：为防止密码分析者对密钥逐段破译，密码设计应该确保密钥每位数字能够影响密文中多位数字；同时，为了防止防止密码分析者利用明文统计特征，密码设计应该使明文中每1个bit影响密文多个bit，或说密文中每1个bit受明文中多个bit影响，从而隐藏明文统计特征。

混同：为了防止密码分析者利用明文与密文之间依赖关系进行破译，将密文和密钥之间统计关系变得尽可能复杂。

扩散和混同6第6页最大公因子：任意有限个整数公因子中最大一个。必定存在而且惟一，记为。最小公倍数：任意有限个整数公倍数中最小一个。必定存在而且惟一，记为。互素数：C=gcd（a，b）称C是两个整数a，b最大公因子。要求最大公因子为正//gcd（a，0）=|a|假如gcd（a，b）=1则称a和b互素。数论基础7第7页模运算

1、设n是一正整数，a是整数，a=q.n+r0≤r≤nq=a/n

其中X为小于或等于X最大整数。用amodn表示余数ra=a/nn+amodn2、假如（amodn）=（bmodn）称两整数a，b模n同余，记为a

b

modn//比如时钟1mod12=13mod12

称与a模n同余数全体为a同余类，记为[a]，称a为这个同于类表示元素。若a0modn则n|a//整除数论基础8第8页

3、模运算性质

①若n|（a-b）则abmodn

②abmodn则bamodn

③abmodnbcmodn则acmodn

④[(amodn)+(bmodn)]modn=(a+b)modn

⑤[(amodn)-(bmodn)]modn=(a-b)modn⑥[(amodn)×(bmodn)]modn=(a×b)modn⑦(a+b)modn=(b+a)modn交换律

(a×b)modn=(b×a)modn⑧[(a+b)+c]modn=[a+(b+c)]modn结合律⑨[a×(b+c)]modn=[(a×b)+(a×c)]modn分配律数论基础9第9页4、加法逆元定义Zn为小于n全部非负整数集合，即Zn={0,1,……n-1}

对于xЄ

Zn，存在y

Є

Zn，使x+y0modn，记为y=-x

称y为x负数，也称加法逆元。比如：Z8={0，1，……7}x+y0mod8(x,y)(0,0)(1,7)(2,6)(3,5)(4,4)

性质：（a+b）（a+c）modn则bcmodn

称为加法可约律数论基础10第10页5、乘法逆元定义Zn为小于n全部非负整数集合，即Zn={0,1,……n-1}

对于xЄ

Zn，gcd（x,n）=1，存在y

Є

Zn，使x×y1modn，记为y=x-1，称y为x倒数，也称y是x在模n下乘法逆元。比如：Z8={0，1，……7}x×y1mod8(x,y)(1,1)(3,3)(5,5)(7,7)

性质：（a×b）（a×c）modn，且a有乘法逆元则bcmodn，称为乘法可约律逆元未必一定存在数论基础11第11页离散对数模指数方程：已知a、b、n三个参数，求x，使满足ax≡b(modn)之所以称为离散对数：按指数方程和对数关系,x=logab(modn)离散两个方面：（1）结果x必须为整数；（2）必须考虑modn影响数论基础12第12页RSA算法

安全性依赖于大数因子分解。是第一个较为完善公钥算法，能够同时用于加密和数字署名，且易于了解和操作。RSA是被研究得最广泛公钥算法，从提出到现在已近二十年，经历了各种攻击考验，逐步为人们接收，被普遍认为是当前最优异公钥算法之一。当前依然无法从理论上证实它保密性能终究怎样，因为当前人们并没有从理论上证实破译RSA难度与大整数分解问题难度等价。

DES和RSA标准比较加密机制DESRSA原理加密钥=解密钥加密钥≠解密钥算法公开公开密钥配送必要无须要密钥数必须为通信对象数自己用一个即可安全确认比较困难轻易加密速度可达100MB/S可达10KB/S13第13页RSA算法设分组长度为l–bit，每个分组M被看作是一个l–bit二进制值。取某一个整数n（大整数），使对全部M，有M<n普通，n取值满足2l<n≤2

l+1。加密算法C=Memodn。解密算法M=Cdmodn=(Me)dmodn=Medmodn。加密密钥（公开密钥）为KU={e,n}。解密密钥（私有密钥）为KR={d,n}。

要求：{e,d,n}使对全部M<n

都有：

M=Med

modn对全部M<n，

Me

和Cd

计算相对简单。给定{e,n}

，要推断d在计算上不可行。14第14页欧拉函数欧拉函数（Euler’stotientfunction）欧拉函数φ(n)：表示小于或等于

n

且与n

互素正整数个数；欧拉函数性质：对任意素数

p，有φ(p)=p–1；比如：对p=7,φ(p)=6,与7素质且小于等于7正整数有1,2,3,4,5,6对任意两个素数

p、q，则对n=pq有：

φ(n)=φ(pq)=φ(p)φ(q)=(p–1)(q–1) 比如：n=6=2×3，φ(n)＝(p–1)(q–1)＝1×2＝2，与其互质且小于等于它正整数有：1,515第15页欧拉定理如a

和n

是互素整数，则有：等价形式(同余性质6)：（反过来写也等价，是RSA中解密公式理论基础）nanmod1)(ºfnanmoda)+1(ºf16第16页

若P是素数，a是正整数，且gcd（a,p）=1，则ap-11modp

或写成：P是素数，a是任一正整数，则apamodp费尔玛定理（Fermat定理）17第17页中国剩下定理18第18页求同余方程组x=1mod2,x=2mod3，x=3mod5唯一解。能够看出，上述方程满足中国剩下定理条件。能够求得M=30,M1=15,M2=10,M3=6,y1=y2

y3=1,则唯一解x=23=15+20+18（mod30）。在RSA解密方面，利用中国剩下定理，能够使速度加紧４倍。也就是分别相求modp和modq值，然后再求modn(=pq)，所以取模之后范围变小，所以速度更加快。中国剩下定理19第19页中国剩下定理攻击Elgamal类型署名20第20页中国剩下定理最简单方法是采取H(m,r)代替H(m)21第21页试验使用