信息安全数学基础最新版.ppt

信息安全数学基础,信息科学与工程学院,网络信息的安全威胁网上犯罪形势不容乐观；有害信息污染严重；网络病毒的蔓延和破坏；网上黑客无孔不入；机要信息流失与信息间谍潜入；网络安全产品的自控权；信息战的阴影不可忽视。,引言,网络通信的困境,引言,我们要保护什么呢？,引言,网络安全体系的五类服务,引言,网络安全体系的五类服务,访问控制服务：根据实体身份决定其访问权限；身份鉴别服务：消息来源确认、防假冒、证明你是否就是你所声明的你；保密性服务：利用加密技术将消息加密，非授权人无法识别信息；数据完整性服务：防止消息被篡改，证明消息与过程的正确性；防抵赖服务：阻止你或其他主体对所作所为的进行否认的服务，可确认、无法抵赖。,引言,引言,解决方法：加密,如何实现保密性？,密码分析,Alice,Bob,加密密钥,解密密钥,Eve,引言,解决方法：数字摘要,如何实现完整性？,消息篡改,公共网络,Alice,Bob,m,z,m,z,z=hk(m),y=hk(m),Eve,引言,解决方法：数字签名,如何实现不可否认性？,否认,公共网络,Alice,Bob,Trent,谁是正确的？,举报,引言,解决方法：密码技术,身份鉴别：就是确认实体是它所声明的，身份鉴别服务提供关于某个实体身份的保证，以对抗假冒攻击。,如何鉴别通信对象的身份？,本课程的相关知识点,简单的密码学基础：密码技术是信息安全的核心技术；需要掌握一些密码学基础知识。相关的数学知识：密码技术的实现依赖于数学知识；掌握密码技术涉及的相应数学基础知识点。参考教材：(1)密码学导引,机械工业出版社,PaulGarrett著,吴世忠等译；(2)信息安全数学基础,武汉大学出版社,李继国等主编。,引言,什么是密码技术？,窃听,公共网络,Alice,Bob,Eve,篡改,伪造,加密密钥,解密密钥,密文,密码学是一门古老而深奥的学科,包括密码编码学和密码分析学;通信双方按照某种约定将消息的原形隐藏。密码系统:明文,密文,加解密算法,密钥。,引言,密码学的起源与发展三个阶段：1949年之前：密码学是一门艺术；19491975年：密码学成为科学；1976年以后：密码学的新方向公钥密码学。1949年之前(手工阶段的初级形式)隐写术：隐形墨水、字符格式的变化、图像；,举例：芦花丛中一扁舟，俊杰俄从此地游；义士若能知此理，反躬难逃可无忧。25871539258314697314697153582486217893,引言,19491975年(机械阶段)：现代密码出现1949年香农Shannon提出“保密系统信息理论”；提出：数据的安全基于密钥而不是密码算法。1976年以后(计算机阶段)：公钥密码诞生1976年Diffievoidseed_LFSR(unsignedlongseed)if(seed=0)seed=1;elseShiftRegister=seed;intmodified_LFSR(void)if(ShiftRegister,第四章现代对称密码,作业：(1)计算线性同余发生器的坏种子：xn+1=6xn+9mod11(2)求LFSRxn+1=xn+xn-1+xn-2+xn-3的周期，其初态为:(x0,x1,x2,x3)=(0,1,0,0),5.1整除性1.定义d|n：d整除n，即存在整数k，使得n=kd。真因子d：d整除n，但d不是n，1。素数：一个没有真因子的正整数。,2.命题(1)正整数n是素数当且仅当它不能被任何整数d整除，其中：(2)互素：如果同时整除m和n的整数只有1，则称m和n互素。记作gcd(m,n)=1。,第五章整除和同余,(3)如果a|b并且b|c，则a|c；如果d|x并且d|y，则对于任意整数a和b有：d|(ax+by),(4)n和N是两个整数，且n|N，则对任意整数x有：(x%N)%n=x%n,3.定理m和n为不同时为0的整数，则m和n的最大公因子gcd(m,n)是以xm+yn表示的最小正整数。例如：gcd(3,5)=23-15=1gcd(9,15)=29-115=3,第五章整除和同余,4.素数的产生(1)采用素性检测法对随机产生的数进行检测。(2)迄今为止没有发现素数的模型或产生素数的有效公式。例如：中国古代数学家提出：若n|2n-2，则n为素数。但是当n=341时不成立。,第五章整除和同余,(3)一些特殊意义的素数：梅森(Mersenne)素数：形如Mn=2n-1的素数(n为素数)如3,7,127,8191,131071。至今发现27个:n=2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213,21701,23209,44497。M11=2047=2389不是素数。费马(Fermat)素数：形如Fm=2m+1的素数(m为自然数)至今只发现5个:3,5,17,257,65537F5=4294967297=6416700417,5.2整数模m1.xymodmx模m同余y这种关系叫模m的同余。等价的说法有xymodm当且仅当m|x-y。2.同余的性质对于固定的整数m，模m同余是一个等价关系。自反性：对于任意的x，总有xxmodm；对称性：xymodmyxmodm；传递性：xymodm,yzmodmxzmodm。其他性质：(1)xymodmaxaymodm,xayamodm；(2)xymodmaxaymodam,a0；(3)(ab)modm(amodmbmodm)modm。,第五章整除和同余,3.命题两个整数x和x，x=qm+r,x=qm+r,0r,r|m|，则xxmodm当且仅当rrmodm。对于固定的模数m，如果xx，那么对于y有x+y=x+ymodmxy=xymodm,推论：同余直接继承了普通算术运算的一些性质。分配律：x(y+z)xy+xzmodm加法结合律：(x+y)+zx+(y+z)modm乘法结合律：(xy)zx(yz)modm1的性质：1xx1xmodm0的性质：0+xx+0xmodm,第五章整除和同余,4.Z/m或者Zm整数模m等价类的集合给定整数x和模数m，x模m等价类：yZ:yxmodm通常记为x或x，称为x模m的同余类或者剩余类。,第五章整除和同余,例：对于模数12，有,模m等价类的集合表示形式：,模m等价类的集合,模m约简的集合,Z/m中的结论：m0modmx+(-x)0modmxkmxmodm(x+y)%m=(x%m)+(y%m)%m(xy)%m=(x%m)(y%m)%m,5.Z/mX或ZmX,ZmX=yZm|gcd(y,m)=1即：Zm中与m互素的元素的集合。例如：Z15X=1,2,4,7,8,11,13,14Z11X=1,2,3,4,5,6,7,8,9,10,第五章整除和同余,6.定理,定理1：设m,n是两个互素的正整数，如果x,y分别遍历模m,n的完全(简化)剩余系，则nx+my遍历模mn的完全(简化)剩余系。举例：分别用模4和模5的完全剩余系和简化剩系来表示模20的完全剩余系和简化剩余系。Z4=0,1,2,3Z4X=1,3Z5=0,1,2,3,4Z5X=1,2,3,4所以：Z20=0,4,8,12,16,5,9,13,17,21,10,14,18,22,26,15,19,23,27,31Z20X=9,13,17,21,19,23,27,31,第五章整除和同余,定理2：若正整数m,n，满足gcd(m,n)=1，则有：(mn)=(m)(n)=1modn,第五章整除和同余,5.3两个著名的定理1.欧拉定理,对n1,如果gcd(x,n)=1，则有：x(n)=1modn,2.费马小定理对任意的整数x和素数p，有xp-11modp,3.欧拉函数(n)的定义对于正整数n，与其互素的小于等于n的正整数的个数表示为(n)，称为欧拉函数。也可以理解为ZmX中的元素个数。,第五章整除和同余,4.欧拉函数(n)的计算,举例：计算(7)，(10)，(35),Z7X=1,2,3,4,5,6,所以(7)=6,Z10X=1,3,7,9,所以(10)=4,Z35X=1,2,3,4,6,8,9,11,12,13,16,17,18,19,22,23,24,26,27,29,31,32,33,34,所以：(35)=24,那么：(10000)=？,第五章整除和同余,因式惟一分解定理：正整数N可以因子分解为：,举例：N=30=235123456789101112131415161718192021222324252627282930,问题：如何求欧拉函数？,其中：p1,p2,pm为素数,所有指数为正整数。,那么：,证明：,第五章整除和同余,那么(10000)=？,10000=2454,所以(10000)=(2-1)23(5-1)53,=84125,=4000,验证(35)=24,35=57,所以(35)=(5-1)51-1(7-1)71-1,=46,=24,第五章整除和同余,小结：,(1)欧拉函数的定义,(2)欧拉函数(n)的计算方法,对于正整数n，与其互素的小于等于n的正整数的个数表示为(n)，称为欧拉函数。,作业：,计算(28)，(1234)。,第五章整除和同余,传统的指数运算效率低，需改进。1.思想在计算xe时，将e表示为一个二元整数e=e0+e121+e222+en2n那么：,因此，若ek=0，可以忽略项；若ek=1，则包含项。,2.实现算法为了计算xe，利用三元组(X,E,Y)，其初始值为：(X,E,Y)=(x,e,1),6.1指数运算,第六章离散对数和原根,为了计算xe，利用三元组(X,E,Y)，其初始值为：(X,E,Y)=(x,e,1)(1)若E是奇数，则Y=X*Y，E=E-1；(2)若E为偶数，则X=X*X，E=E/2；(3)当E=0时，Y的值xe。举例1：计算x5XEYx51x4xx*1x*xx22xx2*x2x41xx40 x5x4*xx5=x1(x4)1(5=101,e0=1,e1=0,e2=1)课内作业：计算21000mod89,第六章离散对数和原根,第六章离散对数和原根,6.2相关定义1.离散对数：对正整数n，若gl=xmodn，则l称为x的以g为底模n的离散对数，记为loggx。2.原根(本原根,生成元,本原元)：对正整数n，如果g是模n的一个原根，那么对于任意的xZnX，都存在d，使得gd=xmodn。例：n=7时，3是否为其原根？可以验证，8没有原根，2是11的原根。,举例2：计算257%59,考虑欧拉定理，即258%59=1，所以：257%59=2-1%59=30,第六章离散对数和原根,3.阶(指数)：对于n1，ZnX是一个有限集。若g是模n的原根，则ZnX的元素列表可表示为：g,g2,g3,对于任意的aZnX，即gcd(a,n)=1，会存在一个正整数t满足：at=1modn，而满足该条件的最小正整数t是a模n的指数或阶。例如：Z7X=1,2,3,4,5,6a=2,t=3；a=3,t=6Z10X=1,3,7,9a=3,t=44.定理：(1)一个模n的原根g具有最大的阶(n)(2)若g是模n的原根，l满足gl=1modn，则(n)|l(3)若g不是模n的原根，t满足gt=1modn，则t|(n),第六章离散对数和原根,2.原根存在的条件对于那些原根的整数n，它们具有如下形式：(1)n=pe,p为奇素数,e1；(如9)(2)n=2pe,p为奇素数,e1；(如6)(3)n=2,4；特别地，存在模素数的原根。,1.定理：(1)一个模n的原根g具有最大的阶(n)(2)若g是模n的原根，l满足gl=1modn，则(n)|l(3)若g不是模n的原根，t满足gt=1modn，则t|(n),6.3原根的特性,第六章离散对数和原根,1.定理：设n1,(n)=q1q2qk，则g是模n的一个原根的充要条件是：,6.4原根的测试,2.对于素数p，令p-1=q1q2qk，计算：,第六章离散对数和原根,举例：p=11,p-1=10=25(1)当g=2时，2(11-1)/2mod11=32mod11=102(11-1)/5mod11=4mod11=4所以：2是原根。(2)当g=3时，3(11-1)/2mod11=243mod11=13(11-1)/5mod11=9mod11=9所以：3不是原根。,作业：,(1)用快速指数算法计算256%1001。(2)用快速指数算法计算23519%521。(2)求以2为底模25的3的离散对数。(3)证明2不是模23的原根。,第七章公钥密码算法,所有的传统密码以及DES、AES等现代密码都是一种对称算法，即解密密钥等价于加密密钥；非对称密码算法中，加密密钥和解密密钥是不相同的，因而可以将加密密钥公开，将解密密钥保密。公钥密码的思想1976年被提出；典型的有：RSA,ElGamal,Knapsnack,ECC等。,对称密码与公钥密码的特点：(1)对称密码算法速度快；(2)非对称密码密钥管理简单。实际网络应用中，采用非对称密码来交换对称密码算法的密钥。,7.1概述,第七章公钥密码算法,对称密码算法,公钥密码算法,加密,第七章公钥密码算法,公钥密码算法,签名,混合加密通信,第七章公钥密码算法,7.2陷门,每个非对称密码算大都依赖于数论中某些处理过程的不可逆性，称为陷门。RSA密码：因子分解难题；,ECC：椭圆曲线上的离散对数难题，aP=Q；,易：a,PQ,难：P,Qa,第七章公钥密码算法,7.3RSA算法,由Rivest、Shamir和Adlemar开发，既能加密又可签名，易理解和实现，因而最流行。,密钥的生成：(1)选择两个大素数p和q，计算：n=pq以及(n)=(p-1)(q-1)；例如：p=11,q=17;n=187,(n)=1016=160(2)选择随机数1e10150，一个模p的原根g以及随机整数x(1xp)，计算y=gxmodp，则公钥为(y,g,p)，私钥为x,7.4ElGamal算法,2.ElGamal加密消息m选择随机数k，得到密文对(a,b)为：(a=gkmodp,b=mykmodp)解密消息：ba-xmodp=myk(gk)-xmodp=m,第七章公钥密码算法,(1)Bob选择随机数k=4，计算得到的密文：a=gkmodp=24mod11=5b=mykmodp=354mod11=5(2)Alice对收到的密文(5,5)解密：ba-xmodp=55-4mod11=3,选p=11,g=2,私钥x=4,则公钥y=gxmodp=5Bob要将消息m=3传送给Alice。,3.举例,第七章公钥密码算法,第一个公钥算法，由RalphMerkle和MartinHellman开发，只能用于加密。1.描述b=a1x1+a2x2+anxn明文分组长度为n，消息为x1xn，密文为b。举例1：明文：111001背包：156111420密文：b=1+5+6+20=32解密：32=1x1+5x2+6x3+11x4+14x5+20 x6奥妙在于背包问题有两种：普通背包：难解；超递增背包：易解。,7.5Knapsnack算法,26次测试,第七章公钥密码算法,超递增背包：a1+a2+ai3)上的椭圆曲线群Ep(a,b):y2=x3+ax+b(modp),a,bGF(p)4a3+27b20,第七章公钥密码算法,2.椭圆曲线的基本性质,设P,QEp(a,b),则P+O=P,P+Q=Q+P。若P+Q=O,则Q=-P为P的加法逆元。设P=(x1,y1),Q=(x2,y2),P-Q,则P+Q=(x3,y3)由以下规则确定：x3=2-x1-x2(modp)y3=(x1-x3)-y1(modp),点Q的倍数定义如下：在Q点做一条切线，与椭圆曲线相交于点S，则2Q=Q+Q=-S在Ep(a,b)中有P,Q,Q=kP,kp,则有,第七章公钥密码算法,3.Diffie-Hellman密钥交换协议,通信双方事先不需要保密信道交换密钥，可以协商共享密钥；安全性基于离散对数难题。Alice和Bob协商好一个大素数p和一个模p的原根g。,选x,gxmodp,gymodp,选y,窃听,公共网络,Alice,Bob,Eve,第七章公钥密码算法,4.椭圆曲线上的密码算法,(1)Diffie-Hellman密钥交换：先取素数p2180和两个参数a,b，得到满足方程y2=x3+ax+b(modp),4a3+27b20的椭圆曲线以及其上面的点构成的Abel群EP(a,b)。G是EP(a,b)的生成元。,(2)椭圆曲线上的加密算法ECC：选取椭圆曲线得到Abel群EP(a,b)，G是EP(a,b)的生成元，公开。将明文消息m通过编码嵌入到曲线上的点Pm，再对点Pm做加密变换。,第七章公钥密码算法,设用户Bob的私钥nB,公钥为PB=nBG;Alice将消息m发送给Bob。,举例：选E:y2=x3+x+6(mod11)，生成元G=(2,7)首先计算2G：因为：=(3x12+1)/2y1=(322+1)/(27)(mod11)=8于是：x3=2-x1-x2(mod11)=5y3=(x1-x3)-y1(mod11)=2所以：2G=(5,2),第七章公钥密码算法,同理，经计算后可知G的阶为13:G=(2,7),2G=(5,2),3G=(8,3),4G=(10,2)5G=(3,6),6G=(7,9),7G=(7,2),8G=(3,5)9G=(10,9),10G=(8,8),11G=(5,9),12G=(2,4)将明文对应于椭圆曲线上的点Pm。加解密过程为：1)设Bob的私钥nB=7，则公钥PB=7G=(7,2)2)Alice加密消息Pm=(10,9)，首先选取随机数k=3，计算：Cm=kG,Pm+kPB=(8,3),(10,2)3)Bob用私钥nB解密：Pm=(10,2)-7(8,3)=(10,9),第七章公钥密码算法,(3)椭圆曲线密码ECC与RSA相比：安全性高；密钥量小；灵活性好。,第七章公钥密码算法,7.7双线性映射(Weilpairing),1.双线性映射的性质,设(G1,+)和(G2,)为两个q阶循环群。双线性对：G1G1G2满足如下的属性：双线性：对于任意P,Q,RG1和a,bZqx(1)(P,P)=1;(2)(P+Q,R)=(P,R)(Q,P);(3)(R,P+Q)=(R,P)(P,Q);(4)(aP,bQ)=(abP,Q)=(P,abQ)=(P,Q)ab;非退化性：存在P,QG1，使得(P,Q)1可计算性：对于任意的P,QG1，存在一个高效的算法计算(P,Q)。,第七章公钥密码算法,(1)PKG选择s,公开G,sG;给用户分配私钥：Alice公钥为QA,私钥为sQA;Bob公钥为QB,私钥为sQB.,2.双线性对用于密钥分配,(2)通信方在没有对话的情况下得到共享密钥：PKG公开G,网络中用户的私钥分别为a,b,c；公钥为PA=aP,PB=bP,PC=cP。三方的共享密钥为：kABC=(PB,PC)a=(PA,PC)b=(PA,PB)c,第八章同余方程,1.费马小定理,8.1梅森数的分解,定理：p是一个素数，对任意的整数x有xp=xmodp证明：首先，根据二项式定理：,当0i1，对任意两个整数m,n，有：gcd(bm-1,bn-1)=bgcd(m,n)-1,证明：首先证明：如果d|n，则有：(bd-1)|(bn-1)和(ad-bd)|an-bn)这是因为：xN-1=(x-1)(xN-1+xN-2+x2+x+1),N=n/d,第八章同余方程,用归纳法证明：1)如果m=n，则命题为真；2)假设mn如果m=n=1,gcd(b-1,b-1)=b-1为真；因为mn，则有bn-m-1=(bn-1)-bn-m(bm-1)gcd(bm-1,bn-1)=gcd(bm-1,bn-m-1)这是因为：如果d|bn-1且d|bm-1，则d|(bn-1)-bn-m(bm-1)根据归纳法假设：gcd(bm-1,bn-1)=gcd(bm-1,bn-m-1)=bgcd(m,n)-1接下来只要证明gcd(m,n)=gcd(m,n-m)即可,第八章同余方程,(2)推论对给定的正整数b,n，如果素数p|bn-1，那么对n的因子d，有：p|bd-1或者p=1modn证明：根据费马小定理有bp=bmodpbp-1=1modpp|bp-1-1根据引理，有p|bgcd(n,p-1)-1(因为p|bn-1)设d=gcd(n,p-1)若d2，对整数b有：,第九章二次符号,9.3二次符号的性质,第九章二次符号,设p为奇素数，n为奇整数(1)若a=bmodp，则(a/p)=(b/p)；若a=bmodn，则(a/n)=(b/n)(2)(ab/p)=(a/p)(b/p)；若a,b与n互素，则(ab/n)=(a/n)(b/n)(3)(a2/p)=1；若gcd(a,n)=1，则(a2/n)=(a/n2)=1(4)(a+p/p)=(a/p)；(a+n/n)=(a/n)(5)(1/p)=1；(1/n)=1(-1/p)=(-1)(p-1)/2；(-1/n)=(-1)(n-1)/2(2/p)=(-1)(p2-1)/8；(2/n)=(-1)(n2-1)/8,第九章二次符号,(6)二次互反定理,如果p,q是不同的奇素数，那么(p/q)=(-1)(p-1)(q-1)/4(q/p),如果m,n是大于2的奇数，那么(m/n)=(-1)(m-1)(n-1)/4(n/m),9.4使用二次符号判定平方剩余,Jacobi符号=1不能判定方程是否有解；Jacobi符号=-1可以判定方程无解。Legendre符号=1可以判定方程有解；Legendre符号=-1可以判定方程无解。,第九章二次符号,举例1：测试x2=19mod101是否有解？解：(19/101)=(-1)(19-1)(101-1)/4(101/19)=(6/19)=(2/19)(3/19)(2/19)=(-1)(192-1)/8=-1(3/19)=(-1)(3-1)(19-1)/4(19/3)=-(1/3)=-1所以，(19/101)=(2/19)(3/19)=1因此，方程有解。,第九章二次符号,举例2：测试x2=1237mod4327是否有解？解：(1237/4327)=(-1)12364326/4(4327/1237)=(616/1237)=(8/1237)(7/1237)(11/1237)=1(8/1237)=(2/1237)=(-1)(12372-1)/8=(7/1237)=(-1)61236/4(1237/7)=(5/7)=(-1)46/4(2/5)=-1(11/1237)=(-1)101236/4(1237/11)=(5/11)=(-1)410/4(1/5)=1所以，(1237/4327)=-1(-1)1=1因此，方程有解。,第九章二次符号,举例3：测试x2=2mod3599是否有解？由于3599=5961，所以方程等价于x2=2mod59x2=2mod61(2/59)=(-1)(592-1)/8=-1无解(2/61)=(-1)(612-1)/8=-1无解所以方程x2=2mod3599无解而根据Jacobi符号有(2/3599)=(2/59)(2/61)=1因此：Jacobi符号=1不能判定方程是否有解,作业：(1)判断2是否为模1033的一个平方？(2)判断方程x2=119mod1009是否有解？(3)判定3是不是模2009的一个平方？,第十章素性测试,10.1Miller-Rabin素性检测算法,许多密码算法和协议需要“随机”的大素数，而大素数的生成，常用的方法是随机生成一个整数n，然后对其进行素性测试。方法：(1)穷举法；(2)概率素性测试。-概率素数(伪素数),1.强伪素数如果p是一个素数，则Z/p中应该只有1的两个平方根，即1和p-1。设n是奇整数，因式分解为：n-1=2rmm为奇数如果bm=1modn，或对某些0sr，满足b2sm=-1modn，则n是基数为b的强伪素数。,第十章素性测试,2.检测算法：可以证明合数的确定性，但只能以一定的概率说明素性性。步骤为：首先，因式分解n-1=2rmm为奇数；随机选1bn-1；设s=0，计算z=bmmodn,如果z=1，则停止，n以3/4的概率是素数，b是n是素数的证据。否则继续：s=s+1，计算z=z2modn。若sr且z=-1，停止，p以3/4的概率为素数；若z=1，p为合数，终止测试。若s=r，且没有一个z等于-1，则p为合数；以上步骤重复k次，若每个b都说明n以3/4的概率是素数，则n是素数的概率为1-(1/4)k。,第十章素性测试,举例：证明合数1281对基数41是强伪素数。解：1281-1=528r=8,m=5首先验证b0=415mod1281=？41514144140024111561410115641=47396mod1281=-1所以1281对基数41是强伪素数。,第十章素性测试,第十章素性测试,10.2Lehmann素性检测算法,(1)随机选a11若n为素数，可判定x2=bmodn有解-1若x2=bmodn无解,(b/n)=,(3)欧拉证明了，对素数p有：(b/p)=b(p-1)/2modp相反，如果n不是素数，则b(n-1)/2modn对于不同的b就是随机。同样，如果(b/n)=b(n-1)/2modn，则整数n是基数为b的欧拉伪素数，b称为欧拉证据。,第十章素性测试,2.算法描述(1)随机选an;(2)若gcd(a,n)1，则n为合数，终止。(3)计算j=a(n-1)/2modn和J=(a/n):若jJ，则n为合数，终止。若jJ，n以50%概率为素数，继续；(4)对a选t次重复，n以(1-1/2t)概率为素数。,3.费马伪素数(1)设gcd(n,b)=1，如果bn-1=1modn，则整数n对于基数b是费马伪素数。(2)一个非素数对于不同的基数有不同的表现。举例：整数n为91=713，基数b分别2和3。,第十一章因式分解,11.1PollardsRho算法,大整数分解是许多密码学算法和协议的安全依据，如RSA密码体制。方法：(1)穷举法；(2)分解算法。,可以较快地找到合数的较小因子。1.算法描述给定整数n，设初始值x=2，y=x2+1；(1)计算g=gcd(x-y,n)；(2)若1n1/2不满足，则还需考虑b0，使得：b0n-1=1modn且gcd(b0k-1,n)=1,举例验证：(1)n=31(2)n=103,3.推论设n=u2m+1，n为奇数且u2m。若存在一个b，使得b(n-1)/2=-1modn，则n为素数。举例验证：n=13=322+1；n=41=523+1,第十一章因式分解,11.4二次筛法因子基：前t个素数的集合S=2,3,5,7,S平滑：整数n的所有因子都小于等于S。算法：试图分解整数n。(1)选择一个因子基S=2,3,5,7,;(2)选取，取b=ai2%n;(3)若b是S平滑的，且为一个平方，则可通过计算n的因子。举例：n=143,第十二章离散对数,12.1离散对数问题,很多秘密技术的安全性都建立在离散对数问题的困难上，如ECC密码体制。,1.离散对数对正整数n，若bl=amodn，则l称为a的以b为底模n的离散对数，记为logba。2.离散对数问题DLP给定素数p，Zpx的生成元b和元素aZpx，求解x满足：bx=amodp3.广义离散对数问题GDLP给定阶为n的有限循环群G，G的生成元b和元素aG，求解x满足：bx=amodn,第十二章离散对数,12.1Baby-stepGiant-step算法p为素数，b是模p的一个本原根，m是不超过的最大正整数，计算步骤如下：,(1)计算(0,b0%p),(1,b1%p),(m-1,bm-1%p)(2)按照第二分量的大小排序；(3)计算c=b-m%p;初始化x=a;对0im，若x是表b0,b1,bm-1中的bj，则logba=mi+j;否则，x=xcmodp,i=i+1举例：计算log211mod227作业：利用Baby-step算法求log25mod29。,第十二章离散对数,12.2Pollard的Pho方法定义函数F：(ax,m+1,n)若xis1F(x,m,n)=(x2,2m,2n)若xis2(bx,m,n+1)若xis3计算步骤如下：(1)选取子集s1,s2,s3；(2)初始化(x,mx,nx,y,my,ny)=(1,0,0,1,0,0)；,(3)重复步骤：(x,mx,nx)=F(x,mx,nx)(y,my,ny)=F(F(y,my,ny)直到x=y，则logba=(my-mx)-1(nx-ny)mod|G|G为Zpx的一个子群，且包含模p的平方(循环子群)如p=59时，2为其本原根，4=22为其循环子群，则G由b=4生成，其阶|G|=29。求log49mod59。,第十二章离散对数,12.3指数演算原理：利用已知的因子基德离散对数进行运算设b是循环群G的生成元，n=|G|(1)对于b，取因子基S=p1,p2,=2,3,5,；(2)考虑b的随机方幂，开始生成关系：logbp1,logbp2,(3)对给定的aG，选择随机整数k，并尝试：abk=p1k1ptktmodn如果成功，则可求解：logba=k1logbp1+ktlogbptkmod|G|举例：设G=Z/X29，n=|G|=28，选原根b=11，因子基S=2,3,5，求log117。,第十三章协议经典算法,13.1秘密共享算法,秘密共享又称为门限方案，保证在协议中只有当足够多的一组成员达成一致时才能共享一个秘密。(k,n)门限方案：(1)在n个人中，每人共享秘密m的部分信息Di；(2)任何k-1部分信息不能恢复m；(3)由任何k部分信息Di可以很容易计算出m。具有代表性的有Shamir门限方案和Asmuth-Bloom门限方案。,第十三章协议经典算法,1.Shamir门限方案(1)构建k-1次多项式f(x)=m+a1x+a2x2+ak-1xk-1modp(2)计算D1=f(1),D2=f(2),Dn=f(n)(3)从其中选k个即可恢复m。给定k个Dj1,Dj2,Djk，可以计算出,则m=f(0)。,举例：设m=13，n=5，k=3，p=17，构建的k-1次多项式为：f(x)=13+10 x+2x2mod17则各秘密份额为：D1=8,D2=7,D3=10,D4=0,D5=11,第十三章协议经典算法,若已知D1=8,D3=10,D5=11，则有：,=88-1(x-3)(x-5)+10(-4)-1(x-1)(x-5)+118-1(x-1)(x-3)mod17,=120(x2-8x+15)+40(x2-6x+5)+165(x2-4x+3)mod17,=2x2+10 x+13mod17,所以：m=f(0)=13。,第十三章协议经典算法,2.Bloom门限方案(1)选取t个严格递增的m1,m2,mn，满足gcd(mi,mj)=1(2)计算：M=m1m2mnHk=m1m2mk-1mkhk-1=mnmn-1mn-(k-1)+1要求Hk(N+1)hk-1，N为一个大的整数(3)对于任意的秘密x(hk-1xx故可以通过x=xmodM获得x。假设已知(a1,m1),(a2,m2),(ak-1,mk-1)，则可以构造k-1项的同余方程组。能获得：x=a1n1M1+aknkMkmodM则有x=xmodM根据前面已知的Hk为k个不同mi的最小乘积，而hk-1为k-1个不同mi的最大乘积，则有：Mhk-1x故不能通过x=xmodM获得x。x可能的值有：hk-1xHk(Hk-hk-1)/hk-1=N个,第十三章协议经典算法,举例：已知k=3,t=4,m1=9,m2=11,m3=13,m4=14，则消息x=500的(3,4)门限方案为：a1=500mod9=5a2=500mod11=5a3=500mod13=6a4=500mod14=10(5,9)(5,11)(6,13)(10,14)假设已知(5,9)(5,11)(6,13)，构造方程：x=5mod9=a1modm1x=5mod11=a2modm2x=6mod13=a3modm3M=91113=1287,第十三章协议经典算法,M1=1113=143M2=913=117M3=911=99n1=143-1mod9=8-1mod9=-1n2=117-1mod11=7-1mod11=8n3=99-1mod13=8-1mod13=5所以：x=5143(-1)+51178+6995mod1287=-715+4680+2970mod1287=6935mod1287=500mod1287假设已知(5,9)(6,13)，构造方程：x=5mod9=a1modm1x=6mod13=a2modm2x=513(13-1mod9)+69(9-1mod13)=617mod117=32mod117所以x可能的值为：266,383,500,617,734,第十三章协议经典算法,13.2不经意传输协议算法(1)Alice有一个秘密，以某种方式传送给