《信息安全工程》课件第3章.ppt

1、第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 3.1信息论信息论 3.2数论数论 3.3有限域有限域 3.4指数运算和对数运算指数运算和对数运算 第第3 3章信息安全数学基础章信息安全数学基础 1Pr1niiob a(3.1.1)第第3 3章信息安全数学基础章信息安全数学基础 信源S的熵为 211()Pr logPr niiiH Sob aob a(3.1.2)设S以k个符号串的形式输出这些符号,即S输出的是包含k个符号的单词:12,kiiiaaa(1)kin令Lk表示记录S输出的包含k个符号的单词所需的最少比特数。我们有下面的定理用于衡量Lk

2、的值。第第3 3章信息安全数学基础章信息安全数学基础 定理定理3.1.1Shannon定理:lim()kkLH Sk证明证明:对所有的整数k0,下面的“三明治”型关系式成立:()()1kkH SLkH S定理所述的是其极限形式。第第3 3章信息安全数学基础章信息安全数学基础 说明:这是一种简单的证明方式,有的读者可能会认为其证明过程不太正式,详细的证明过程可参见王育民、李晖、梁传甲共同编写的信息论与编码理论一书中的定理3.3.8的证明过程。定理3.1.1说明了这样一个道理:为记录信源S的每个输出,所需的最小平均比特数为H(S)。第第3 3章信息安全数学基础章信息安全数学基础 3.1.2熵的性质

3、熵的性质如果S以概率1输出某个符号,例如a1,则熵函数H(S)有最小值0。这是因为:1211()PrlogIb10PrH Sob aob a这种情况说明,当我们确信信源S仅输出a1时,就没有必要浪费一些比特来记录它。如果S以相等的概率1/n输出每个符号,即S是一个均匀分布的随机信源,则熵函数H(S)可达到最大值lbn。这是因为在这种情况下,有:2211()loglogniH Snnn第第3 3章信息安全数学基础章信息安全数学基础 【例例3.1.1】考虑下面的“电话掷币”协议。假定Alice和Bob已经同意:(1)一个特殊的单向函数f,满足:对任意整数x,由x计算f(x)是容易的,而给出f(x)

4、,要找出对应的原像x是不可能的,不管x是奇数还是偶数;不可能找出一对整数(x,y),满足xy,但f(x)=f(y)。(2)f(x)中的偶数x代表“正面”,奇数x代表“背面”。第第3 3章信息安全数学基础章信息安全数学基础 “电话掷币”协议包含如下步骤：(1)Alice选择一个大随机数x并计算f(x)，然后通过电话告诉Bobf(x)的值；(2)Bob告诉Alice自己对x的奇偶性猜测;(3)Alice告诉Bobx的值;(4)Bob验证f(x)并查看他所做的猜测是否正确。第第3 3章信息安全数学基础章信息安全数学基础 不管是通过电话,还是通过连接的计算机,对Alice和Bob来说,该协议都是协商一

5、个随机比特。在该协议中,Alice随机选取一个大的整数xUN,通过单向函数f计算f(x),并将其送给Bob,最后在Bob随机猜测后披露x。在Bob看来,x作为整数不应该被当做一条新的信息,因为在接收到f(x)前,他已经知道x是N中的一个元素。Bob仅利用Alice输出中的有用部分,即运用x的奇偶性来计算与Alice的输出相符的随机比特。因此,我们有:H(Alice)=Probx 为奇数Pr1log2为奇数xob+Probx 为偶数Pr1log2为偶数xob=2log212+2log212=1 第第3 3章信息安全数学基础章信息安全数学基础 如果Alice和Bob重复执行n次“电话掷币”协议,他

6、们就能够协商一个n比特的串:若Bob猜对一次,则输出1;若猜错一次,则输出0。该协议的这种用法使得Alice和Bob都是一个每执行一次协议便输出1比特的信源。双方都相信所获得的比特串是随机的,因为任何一方都有自己的随机输入,并且知道另一方无法控制其输出。第第3 3章信息安全数学基础章信息安全数学基础 3.2数论数论3.2.1素数与互素数素数与互素数1.整除整除令b0,若b除尽a,则有a=mb,m是某个整数,以b|a表示,称b为a的一个因子或约数。例如,30的约数为1、2、3、5、6、10、15、30。对整数有下述关系式：(1)若a|1,则a=1;(2)若a|b且b|c,则a|c;(3)对任意b

7、0,有b|0为0;(4)若b|g且b|h,则对任意整数m和n,有b|(mg+nh)。第第3 3章信息安全数学基础章信息安全数学基础 2.素数与素分解素数与素分解任一整数p1,若它只有1和p为约数,则称其为素数,否则称其为合数。对任意整数a1,有唯一分解式:ttpppa.2121(3.2.1)其中,p1p20。式(3.2.1)可改写成如下形式:apapapp其中0(3.2.2)其中,P是所有可能的素数p的集合;对给定的a,大多数指数p为0。第第3 3章信息安全数学基础章信息安全数学基础 任一给定整数a,可由式(3.2.2)中的非零指数集给定。两个整数之积等价于其相应指数之和,即 pppkmnkm

8、n(对所有p)而对两个整数a，b有/ppa b(3.2.4)第第3 3章信息安全数学基础章信息安全数学基础 3.互素数互素数两个整数的最大公约数k以gcd(a,b)表示,其中k满足:(1)k|a,k|b;(2)对任意k,k|a,k|bk|k,即 gcd(,)max:/a bk k ak b且(3.2.5)由整数的唯一分解式(3.2.2)不难求出:gcd(,)min,pppka bkab(对所有p)(3.2.6)若gcd(a,b)=1,则称整数a、b互素。第第3 3章信息安全数学基础章信息安全数学基础 4.欧拉函数欧拉函数整数n的欧拉函数定义为小于n且与n互素的整数个数,以(n)表示。显然,对一

9、素数p有:()1np(3.2.7)若n=p1p2,p1和p2都是素数,则在modn的p1p2个剩余类中,与n不互素的元素集为p1,2p1,(p2-1)p1、p2,2p2,(p1-1)p2和0,即 1212()(1)(1)1np ppp1211()1p ppp12(1)(1)pp12()()pp(3.2.8)第第3 3章信息安全数学基础章信息安全数学基础 一般对任意整数 n，由式(3-2-1)可写成npiiti1，可证明其欧拉函数为 11()(1)tiinnp(3.2.9)第第3 3章信息安全数学基础章信息安全数学基础 3.2.2同余与模算术同余与模算术1.同余同余给定任意整数a和q,以q除a,

10、其商为s,余数为r,则可表示为a=sq+r,0rq,即sa q(mod)aa qqaq其中,s=q|a表示小于q|a的最大整数。定义r为amodq,则称r为amodq的剩余(Residue),记为ramodq。式(3.2.10)可改写为(3.2.11)(3.2.10)第第3 3章信息安全数学基础章信息安全数学基础 若两个整数a和b有amodq=bmodq,则称a与b在modq下同余(Congruent)。(整数集)的所有由式(3.2.10)决定的整数集称为同余类,可表示为 Zs /,ra asqr sZ(3.2.12)同余类中各元素之间彼此皆同余。第第3 3章信息安全数学基础章信息安全数学基础

11、 同余类中各元素之间彼此皆同余。同时，模运算有下述性质：(1)若/()n ab，则modabq。(2)(mod)(mod)aqbq意味(mod)abq。(3)(mod)abq等价于(mod)baq。(4)若(mod)abq且(mod)bcq，则有(mod)acq。第第3 3章信息安全数学基础章信息安全数学基础 2.模算术模算术(ModularArithmatic)在modq的q个剩余类集0,1,2,q-1上可以定义加法运算和乘法运算。加法:(mod)(mod)()modaqbqabq(3.2.13)(mod)(mod)()modaqbqabq乘法:(3.2.14)第第3 3章信息安全数学基础章

12、信息安全数学基础 3.2.3大素数求法大素数求法1.概述概述第第3 3章信息安全数学基础章信息安全数学基础 lim()ln()xxxx1(3-2-15)即()lnxxx(3.2.16)其中,(x)为小于等于正整数x的素数的个数。第第3 3章信息安全数学基础章信息安全数学基础 2.产生大素数的检验法产生大素数的检验法1)概率测试法概率测试法包括SolovayStrassen检验法和MillerRabin检验法等。它们都是利用数论理论构造一种检验法,对一个给定大整数N,每进行一次检验输出,给出Yes(N为素数,概率为1/2)或No(N必不是素数)。若N通过了r次检验,则N不是素数的概率将为=2-r

13、,N是素数的概率为1-;若r足够大,如r=100,则N几乎可认为是素数。当概率检验法得到的准素数是合数时(当然其出现的概率极小)，不会造成太大问题。因为一旦出现这种情况,RSA体制的加、解密就会异常，从而可以被发现。第第3 3章信息安全数学基础章信息安全数学基础 (1)SolovayStrassen检验法:令1nm,随机取n,并验证gcd(m,n)=1,且J(n,m)=2(m-1)/2modm。其中J(n,m)为Jacobi符号,即 J n mnpnpnpr(,)()()()12(3.2.17)m=p1p2pr(3.2.18)式(3.2.18)为m的素数分解式。式(3.2.17)中:的非平方剩

14、余是的平方剩余是符号iiipnpnLegendrepn11)(3.2.19)第第3 3章信息安全数学基础章信息安全数学基础 即 XnpXnpii22modmod有二个解无解(3.2.20)J n mnJnmnJ Rm nmnnmn(,)(,)()(),)()()()/()()/11211211 811 4为偶其它(3.2.21)若m为素数,则gcd(m,n)=1,且J(n,m)=2(m-1)/2modm。若m不是素数,则至多有1/2概率使上式成立。因此,随机地选择100个整数n进行检验,若式(3.2.21)均成立,则m不是素数的概率必小于2-10010-30,故可认为m是一素数,但实际上它不一

15、定是。第第3 3章信息安全数学基础章信息安全数学基础 (2)MillerRabin检验法:令N=2st+1,s1,t为奇数,任选a(正整数),检验:10mod1mod12sjnanatjt(3.2.22)若a满足式(3.2.22)中的两个条件,则N必为合数(由Fermat定理得出)。重复选不同的a,试验r次,理论证明,若r次均不满足式(3.2.22),则N不为素数的概率小于等于(1/4)r,r足够大时,可由素数分布式估计r值。对Nx,要求进行 xxx/()ln()/22(3.2.23)第第3 3章信息安全数学基础章信息安全数学基础 2)确定性素数检验法确定性分解算法是RSA体制实用化研究的基础

16、问题之一。当算法结果指示为Yes时,N必为素数。Lucas于1876年给出了定理3.2.3。定理定理3.2.3若N满足bN-11 mod n,且(3.2.24)对所有的素因数piN-1,则N为素数。此法要求N-1的因子分解,因而无实用价值。Demytko法是于1988年由Demytko提出的。该法是利用已知小素数,通过迭代给出一个大素数。其方法如定理3.2.4所示。(1)/1modinpbn第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 确定性算法的运行时间复杂度为 exp(loglog(logloglog()Cnn(3.2.25)美国Sandi

17、a实验室提出了适于分解离散对数和分解困难大素数的4个条件,可以参见Laih等在1995年的研究成果。有关产生强素数的算法问题同样可参看Laih等在1995年的研究成果 第第3 3章信息安全数学基础章信息安全数学基础 3)使用现有素数生成工具以上方法产生大素数比较麻烦,并不是工程人员所希望采用的。在实际工程实现中,要产生RSA的大素数,完全可以使用现有的一些素数生成小软件。这些软件在Google中不难下载到,而且几乎都是免费软件。在这些软件中,使用者可以输入所需要的素数规格,从而很容易地获取自己所需的大素数。第第3 3章信息安全数学基础章信息安全数学基础 3.3有限域有限域3.3.1基本概念基本

18、概念1.域、半群、拟群、群、环域、半群、拟群、群、环定义定义3.3.1 代数系统F,+,称为域(Field),其中的元素对运算“+”(加)和“”(乘)满足下述条件:(1)加法封闭性:,a bFabF,()()a b cFabcabc(2)加法结合律:(3)加法恒等元:惟一的 0F，对00aFaaa；第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 定义定义3.3.2 满足公理(1)，(2)的F,或公理(1)，(2)的F0，称作半群半群(semi-group)。定义定义3.3.3 满足公理(1)，(2)和(3)的F,或公理(1)，(2)和(3)的F,

19、0，称作拟群拟群(monoid)。定义定义3.3.4 满足公理(1)，(2)，(3)，(4)的F,G,或公理(1)，(2)，(3)，(4)的F0，G,称作群群(Group)。定义定义3.3.5 满足公理(1)，(2)，(3)，(4)，(5)的F,或公理(1)，(2)，(3)，(4)，(5)的F 0，称作可换群可换群(Abelian group)。第第3 3章信息安全数学基础章信息安全数学基础 定义定义3.3.6 域的另一等价定义。若F，满足：aF,是Abelian群；bF0，是Abelian群；c分配律成立。注注：“”并不一定为算术加法；“”并不一定为算术乘法。定义定义3.3.7 若F，中的元

20、素对运算“”(加)和“”(乘)满足下述条件则称其为环环(Ring)：aF,是可换群；bF0对12成立；c分配律成立。对3成立的环为单位元环单位元环(惟一性)。第第3 3章信息安全数学基础章信息安全数学基础 2.有限域有限域若集合F中的元素个数有限,则定义3.3.1定义3.3.4和定义3.3.7的那些代数系统就构成了有限域、有限半群、有限拟群、有限群、有限环等。有限域F,+,中,Fm,则 1110 n(3.3.1)1110nmnm(3.3.2)第第3 3章信息安全数学基础章信息安全数学基础 定义定义 3.3.9使式使式(3.3.2)成立的最小相加次数成立的最小相加次数p为域的特为域的特征征(Ch

21、aracteristic)。定理定理3.3.1有限域的特征必为素数。有限域的特征必为素数。证明证明:略去。由有限域特征的定义可以看出,若k,mp,则 11mk即即 1201,1,11p均不相同,后面将证明它们构成GF(p)。第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 3.有限域有限域GF(p)上上x的多项式代数的多项式代数 令Fpx为GF(p)上的多项式集合，在Fpx上可以定义下述多项式加法和乘法运算。x的任意多项式可表示为,.)(101110 x

22、FxuxuxuuxupNnnnNN)(pGFuN(3.3.3)其中uN1为u(x)的首项系数，uN1=1的多项式称首首一一(monic)多项式。deg u(x)为系数不为零的最高次项的次数。第第3 3章信息安全数学基础章信息安全数学基础 加加法法：两个多项式a xNa xnnnN()01和b xb xnnnK()01的和式定义为 c xa xb xabxcabnnnnnnnNK()()()(),()max()，011(3.3.4)乘法乘法：两个多项式 a xNa xnnnN()01和 b xb xnnnK()01的积式定义为 c xa x b xc xiiiNK()()()02 (3.3.5)

23、式中:011110babababaciiiii第第3 3章信息安全数学基础章信息安全数学基础 定义定义3.3.10在上述运算下,Fpx,+,构成环,称为多项式环。类似于整数环,在多项式环中也有Euclid除法定理。给定u(x),g(x)Fpx,存在唯一的g(x)商式和r(x)余式,使得:()()()()()()g xu xq x g xr xRu xdeg()deg()r xg x(3.3.6)第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 定义定义3.3.12 若 p(x)Fx，且除1 以外所有次

24、数低于 p(x)的多项式均除不尽 p(x)，则称 p(x)为既约多项式既约多项式。既约多项式像素数一样在 Fpx中起着重要的作用。两个多项式 u1(x)和 u2(x)，1212(),()()()()()1u x u xA x u xB x u x，则称 u1(x)和 u2(x)彼此为互互素素。类似于整数，任一给定 v(x)Fpx可惟一地分解为既约多项式之积。称其为多项式环中的惟一分解定理惟一分解定理。第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 第第

25、3 3章信息安全数学基础章信息安全数学基础 定义定义3.3.19令为一个扩域中的元素,则称系数在其基域上且使m()=0的最低次多项式m(x)为元素的最小多项式或最小函数。第第3 3章信息安全数学基础章信息安全数学基础 6.有限群有限群群中元素个数(即群的阶数)有限。在有限域中有两个群:一个是F对加法构成的群;另一个是F-0对乘法构成的群。它们都是有限群。有限群具有如下性质:(1)由子群和陪集的定义及拉格朗日定理可知,有限群的任一子群的阶数为群的阶数的因子。(2)有限群对定义的乘法运算构成循环群(CyclicGroup)。对aG,由群的阶有限可证明,a,a2,am-1,am1(乘法单位元),称m

26、为元素a的阶(Order),由拉格朗日定理可知,m|n(n为群G的阶)。若m=n,则a的所有幂给出G中的所有元素,称a为G的生成元,称G为循环群。循环群的生成元不一定唯一。循环群的任一子群的阶必为n的因数。第第3 3章信息安全数学基础章信息安全数学基础 G中元素的阶有下述一些性质：(1)a的阶为n，则。(2)a的阶为m，b的阶为n，且(m,n)=1，则ab的阶为mn。(3)a为n阶元素，k为任意整数，则ak的阶为n/(n,k)。第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 NmmpppmiiiJ()()2111(3.3.15)其中，pi是2m1

27、的素因子，即 121iJemiip (3.3.16)第第3 3章信息安全数学基础章信息安全数学基础 ei为一正整数。如m=2，2m-1=3 Np(2)32231；m=3，2m-1=7 Np(3)=73672；m=4，2m-1=15=53，Np(4)=15445232；m=5，2m-1=31，Np(5)=31530316；m=6，2m-1=63=732，Np(6)=63667236。第第3 3章信息安全数学基础章信息安全数学基础 定理定理3.3.8 GF(q)上的每一个 m 次既约多项式 p(x)都是xqx 的一个因式。定理定理3.3.9 xqx 的每一个既约因式的次数小于等于 m。定理定理3.

28、3.10 令 f(x)为 GF(q)上的多项式，若是 f(x)的一个根，则q也是 f(x)的一个根。若 f(x)为 GF(q)上的既约多项式，则它的所有根为,q,qm1，即它是 m 次既约多项式。且既约多项式的所有根的阶相同。称,q,qm1为多项式f(x)的共共轭轭根根组组。GF(pm)中元素可有多种表示方法，其中最常用的有下述三种：(1)多项式；(2)n 重系数；(3)生成元之幂。第第3 3章信息安全数学基础章信息安全数学基础 3.3.2 有限域上的线性代数有限域上的线性代数 一般实域、复域上研究GF(q=pm)上的研究。1.矢量空间矢量空间 域 F 上的矢量集合：V=v|v=(v0,vN1

29、)，unF ：矢量加法矢量加法对 u,vV，u=(u0,uN1)，v=(v0,vN1)有 uv=(u0v0,uN1vN1)(3-3-17):标乘标乘(Scalar)，对F，vV 有 v=(u0,uN1)(3-3-18)第第3 3章信息安全数学基础章信息安全数学基础 2.线性代数线性代数 在矢量空间V,中可以定义内积内积运算 uv=u0v0,uN1vN1,u,vV (3-3-21)内积运算具有下述性质：i 对称性对称性：uv=vu；(3-3-22)ii 双线性双线性：(uv)w=(u w)(vw)；(3-3-23)iii 若对所有 vV 有 uv=0，则 u=0。第第3 3章信息安全数学基础章信

30、息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 定义定义3.3.24 若A,满足下述条件则称其为一线性结合代数线性结合代数。aA 为域F 上的矢量空间；b对结合运算“”封闭(“”可为内积)；c对的结合律成立，即u,v,wA，有(uv)w=u(vw)；d双线性律：对c,d,F，u,v,wA 有 u(cvdw)=cuvduw；(3-3-24)(cvdw)u=cvudwu。(3-3-25)第第3 3章信息安全数学基础章信息安全数学基础 3.矩阵矩阵 给定GF(p)上可以定义一个LN阶矩阵G GgggggggggggggggNLLLNL0

31、0010201101112111 01 11 211011,(3-3-26)式中，LN，gijGF(p)，i=1,N1，j=1,L1。第第3 3章信息安全数学基础章信息安全数学基础 类似于一般域，对有限域上的矩阵也可定义行空间、行秩、列空间、列秩(等于行秩)、非异性、初等行变换、梯型典型式、线性方程组解空间、解空间的维数等概念。若g0,gL1是独立矢量组，则G的行空间为L维。以G为系数矩阵的齐次线性方程组的解空间必为NL维子空间，其基底为NL个独立矢量。此NL个独立矢量构成域F上的(NL)N阶矩阵 HhhhhhhhhhhhhNNLNNLNNL000101101111101 111011,，(3

32、-3-27)第第3 3章信息安全数学基础章信息安全数学基础 由解空间的定义知 gihj=0，i=0,1,L1，j=0,1,NL1。则有 GHT=HGT=0 (L(NL)阶零阵)(3-3-28)在 N维矢量空间 V 中有 CNCLNNHNLG维子空间维子空间生成生成阶矩阵阶矩阵行对偶正交)()(第第3 3章信息安全数学基础章信息安全数学基础 3.4 指数运算和对数运算指数运算和对数运算3.4.1 快速指数运算快速指数运算 快速指数算法是RSA(单一指数)、DSS和Schnorr(两个指数)、ElGamal(三个指数)签字等多种体制实用化的关键问题。本小节介绍一种二元算法。令=x，0 xm。x的二

33、元表示为 101122rrxaaa2logrm (3.3.1)则有:1101110)()(12222 rrraraaaaax(3.4.2)第第3 3章信息安全数学基础章信息安全数学基础 而2210()1iiiiaiaa(3-4-3)可做预计算:24222221221rrrr次乘法(3.4.4)对于给定的x，先将x以二进制数字表示，而后根据ai=1取出相应的与其它项相乘，这最多需要r1次乘法运算。第第3 3章信息安全数学基础章信息安全数学基础 3.4.2离散对数计算离散对数计算许多公钥体制都是基于有限域上的离散对数问题而提出的。Wells曾在1984年证明,对y1,q-1,其对数为 log()modyjyqjjq1112(3.4.5)式中,是GF(q)的本原根。但直接应用式(3.4.5)所需的计算时间会按指数增长。第第3 3章信息安全数学基础章信息安全数学基础 1 Pohlig-Hellman 和和Silver 算算法法 令 p：素数，本原GF(p)，0，计算x=y mod q。11niipp(pi为素数)(3.4.6)由孙子定理可求任意整数N的表示矢量为 11(mod),(mod)nnNbpbp第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础 第第3 3章信息安全数学基础章信息安全数学基础