信息安全数学基础PPT课件.ppt

1、信息安全数学基础,信息科学与工程学院,网络信息的安全威胁 网上犯罪形势不容乐观； 有害信息污染严重； 网络病毒的蔓延和破坏； 网上黑客无孔不入； 机要信息流失与信息间谍潜入； 网络安全产品的自控权； 信息战的阴影不可忽视。,引 言,网络通信的困境,引 言,我们要保护什么呢？,引 言,网络安全体系的五类服务,引 言,网络安全体系的五类服务,访问控制服务：根据实体身份决定其访问权限； 身份鉴别服务：消息来源确认、防假冒、证明你 是否就是你所声明的你； 保密性服务：利用加密技术将消息加密，非授权 人无法识别信息； 数据完整性服务：防止消息被篡改，证明消息与 过程的正确性； 防抵赖服务：阻止你或其他主

2、体对所作所为的进 行否认的服务，可确认、无法抵赖。,引 言,引 言,解决方法：加密,如何实现保密性？,密码分析,Alice,Bob,加密 密钥,解密 密钥,Eve,引 言,解决方法：数字摘要,如何实现完整性？,消息篡改,公共网络,Alice,Bob,m,z,m,z,z=hk(m),y=hk(m),Eve,引 言,解决方法：数字签名,如何实现不可否认性？,否认,公共网络,Alice,Bob,Trent,谁是正确的？,举报,引 言,解决方法：密码技术,身份鉴别：就是确认实体是它所声明的，身份鉴别服务提供关于某个实体身份的保证，以对抗假冒攻击。,如何鉴别通信对象的身份？,本课程的相关知识点,简单的密

3、码学基础： 密码技术是信息安全的核心技术； 需要掌握一些密码学基础知识。 相关的数学知识： 密码技术的实现依赖于数学知识； 掌握密码技术涉及的相应数学基础知识点。 参考教材： (1) 密码学导引,机械工业出版社,Paul Garrett 著,吴世忠等译； (2) 信息安全数学基础,武汉大学出版社,李继国等 主编。,引 言,什么是密码技术？,窃听,公共网络,Alice,Bob,Eve,篡改,伪造,加密 密钥,解密 密钥,密文,密码学是一门古老而深奥的学科,包括密码编码学和密码分析学; 通信双方按照某种约定将消息的原形隐藏。 密码系统:明文,密文,加解密算法,密钥。,引 言,密码学的起源与发展 三

4、个阶段： 1949年之前：密码学是一门艺术； 19491975年：密码学成为科学； 1976年以后：密码学的新方向公钥密码学。 1949年之前(手工阶段的初级形式) 隐写术：隐形墨水、字符格式的变化、图像；,举例： 芦花丛中一扁舟，俊杰俄从此地游； 义士若能知此理，反躬难逃可无忧。 258 71539 258 314697 314697 15358 24862 17893,引 言,19491975年(机械阶段)：现代密码出现 1949年香农Shannon提出“保密系统信息理论”； 提出：数据的安全基于密钥而不是密码算法。 1976年以后(计算机阶段)：公钥密码诞生 1976年Diffie vo

5、id seed_LFSR(unsigned long seed) if(seed=0) seed=1; else ShiftRegister=seed; int modified_LFSR(void) if(ShiftRegister ,第四章 现代对称密码,作业： (1)计算线性同余发生器的坏种子： xn+1=6xn+9 mod 11 (2)求LFSR xn+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。 素数：一个没有真

6、因子的正整数。,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=1 gcd(9,15)=29-115=3,第五章 整除和同余,4.素数的产生

7、 (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=204

8、7=2389不是素数。 费马(Fermat)素数： 形如Fm=2m+1的素数(m为自然数) 至今只发现5个:3,5,17,257,65537 F5=4294967297=6416700417,5.2 整数模m 1.xy mod m x模m同余y 这种关系叫模m的同余。 等价的说法有xy mod m当且仅当m|x-y。 2.同余的性质 对于固定的整数m，模m同余是一个等价关系。 自反性：对于任意的x，总有xx mod m； 对称性：xy mod m yx mod m； 传递性：xy mod m,yz mod mxz mod m。 其他性质： (1) xy mod m axay mod m,xay

9、a mod m； (2) xy mod m axay mod am, a0； (3) (ab) mod m(a mod mb mod m) mod m。,第五章 整除和同余,3.命题 两个整数x和x，x=qm+r,x=qm+r,0r,r |m|，则xx mod m当且仅当rr mod m。 对于固定的模数m，如果xx，那么对于y有 x+y=x+y mod m xy=xy mod m,推论：同余直接继承了普通算术运算的一些性质。 分配律：x(y+z)xy+xz mod m 加法结合律：(x+y)+zx+(y+z) mod m 乘法结合律：(xy)zx(yz) mod m 1的性质：1xx1x m

10、od m 0的性质：0+xx+0x mod m,第五章 整除和同余,4.Z/m或者Zm 整数模m等价类的集合 给定整数x和模数m，x模m等价类： yZ: yx mod m 通常记为x或x，称为x模m的同余类或者剩余类。,第五章 整除和同余,例：对于模数12，有,模m等价类的集合表示形式：,模m等价类的集合,模m约简的集合,Z/m中的结论： m0 mod m x+(-x)0 mod m xkmx mod m (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互素的元素的集合。 例如：Z1

11、5X=1,2,4,7,8,11,13,14 Z11X=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,3 Z4X=1,3 Z5=0,1,2,3,4 Z5X=1,2,3,4 所以：Z20=0,4,8,12,16,5,9,13,17,21,10, 14,18,22,26,15,19,23,27,31 Z20X=9,13,17,21,19,2

12、3,27,31,第五章 整除和同余,定理2：若正整数m,n，满足gcd(m,n)=1，则有： (mn)=(m)(n)= 1 mod n,第五章 整除和同余,5.3 两个著名的定理 1.欧拉定理,对n1,如果gcd(x,n)=1，则有：x(n)=1 mod n,2.费马小定理 对任意的整数x和素数p，有 xp-11 mod p,3. 欧拉函数(n)的定义 对于正整数n，与其互素的小于等于n的正整数的个数表示为(n)，称为欧拉函数。 也可以理解为ZmX中的元素个数。,第五章 整除和同余,4. 欧拉函数(n)的计算,举例：计算(7)，(10)，(35),Z7X=1,2,3,4,5,6,所以(7)=6

13、,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=235 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30,问题：如何求欧拉函数？,其中：p1,p2,pm为素数,所有指数为正整数。,那么：,证明：,第五章 整除和同余,那

14、么(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，可以忽略 项；

15、 若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：计算x5 X E Y x 5 1 x 4 x x*1 x*x x2 2 x x2*x2 x4 1 x x4 0 x5 x4*x x5=x1(x4)1 (5=101,e0=1,e1=0,e2=1) 课内作业：计算21

16、000 mod 89,第六章 离散对数和原根,第六章 离散对数和原根,6.2 相关定义 1.离散对数： 对正整数n，若gl=x mod n，则l称为x的以g为 底模n的离散对数，记为loggx。 2.原根(本原根,生成元,本原元)： 对正整数n，如果g是模n的一个原根，那么对于 任意的xZnX，都存在d，使得gd=x mod n。 例：n=7时，3是否为其原根？ 可以验证，8没有原根，2是11的原根。,举例2：计算257%59,考虑欧拉定理，即258%59=1，所以： 257%59=2-1%59=30,第六章 离散对数和原根,3.阶(指数)： 对于n1，ZnX是一个有限集。若g是模n的原根，

17、则ZnX的元素列表可表示为：g,g2,g3, 对于任意的aZnX，即gcd(a,n)=1，会存在一个 正整数t满足：at=1 mod n，而满足该条件的最小正 整数t是a模n的指数或阶。 例如：Z7X=1,2,3,4,5,6 a=2,t=3；a=3,t=6 Z10X=1,3,7,9 a=3,t=4 4.定理： (1)一个模n的原根g具有最大的阶(n) (2)若g是模n的原根，l满足gl=1 mod n，则(n)|l (3)若g不是模n的原根，t满足gt=1 mod n，则t|(n),第六章 离散对数和原根,2.原根存在的条件 对于那些原根的整数n，它们具有如下形式： (1) n=pe ,p为奇

18、素数,e1； (如9) (2) n=2pe ,p为奇素数,e1； (如6) (3) n=2,4； 特别地，存在模素数的原根。,1.定理： (1)一个模n的原根g具有最大的阶(n) (2)若g是模n的原根，l满足gl=1 mod n，则(n)|l (3)若g不是模n的原根，t满足gt=1 mod n，则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

19、)/2 mod 11=32 mod 11=10 2(11-1)/5 mod 11=4 mod 11=4 所以：2是原根。 (2)当g=3时，3(11-1)/2 mod 11=243 mod 11=1 3(11-1)/5 mod 11=9 mod 11=9 所以：3不是原根。,作业：,(1)用快速指数算法计算256%1001。 (2)用快速指数算法计算23519%521。 (2)求以2为底模25的3的离散对数。 (3)证明2不是模23的原根。,第七章 公钥密码算法,所有的传统密码以及DES、AES等现代密码 都是一种对称算法，即解密密钥等价于加密密钥； 非对称密码算法中，加密密钥和解密密钥是不相

20、 同的，因而可以将加密密钥公开，将解密密钥保密。 公钥密码的思想1976年被提出； 典型的有：RSA,ElGamal,Knapsnack,ECC等。,对称密码与公钥密码的特点： (1)对称密码算法速度快； (2)非对称密码密钥管理简单。 实际网络应用中，采用非对称密码来交换对称密 码算法的密钥。,7.1 概述,第七章 公钥密码算法,对称密码算法,公钥密码算法,加密,第七章 公钥密码算法,公钥密码算法,签名,混合加密通信,第七章 公钥密码算法,7.2 陷门,每个非对称密码算大都依赖于数论中某些处理 过程的不可逆性，称为陷门。 RSA密码：因子分解难题；,ECC：椭圆曲线上的离散对数难题，aP=Q

21、；,易：a,PQ,难：P,Qa,第七章 公钥密码算法,7.3 RSA算法,由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=gx mod p，则 公钥为(y,g,p)，私钥为x,7.4 ElGamal算法,2.ElGamal加密消息m 选择随机数k，得到密文对(a,b)为： (a=gk mod p, b=

22、myk mod p) 解密消息：ba-x mod p=myk(gk)-x mod p=m,第七章 公钥密码算法,(1)Bob选择随机数k=4，计算得到的密文： a=gk mod p=24 mod 11=5 b=myk mod p=354 mod 11=5 (2)Alice对收到的密文(5,5)解密： ba-x mod p=55-4 mod 11=3,选p=11,g=2,私钥x=4,则公钥y=gx mod p=5 Bob要将消息m=3传送给Alice。,3.举例,第七章 公钥密码算法,第一个公钥算法，由Ralph Merkle和Martin Hellman开发，只能用于加密。 1.描述 b=a1

23、x1+a2x2+anxn 明文分组长度为n，消息为x1xn，密文为b。 举例1：明文：1 1 1 0 0 1 背包：1 5 6 11 14 20 密文：b=1+5+6+20=32 解密：32=1x1+5x2+6x3+11x4+14x5 +20 x6 奥妙在于背包问题有两种： 普通背包：难解；超递增背包：易解。,7.5 Knapsnack算法,26次测试,第七章 公钥密码算法,超递增背包： a1+a2+ai3)上的椭圆曲线群 Ep(a,b): y2=x3+ax+b (mod p),a,bGF(p) 4a3+27b20,第七章 公钥密码算法,2.椭圆曲线的基本性质,设P,QEp(a,b),则 P+

24、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 (mod p) y3=(x1-x3)-y1 (mod p),点Q的倍数定义如下： 在Q点做一条切线，与椭圆曲线相交于点S，则 2Q=Q+Q=-S 在Ep(a,b)中有P,Q,Q=kP,kp,则有,第七章 公钥密码算法,3.Diffie-Hellman密钥交换协议,通信双方事先不需要保密信道交换密钥，可以 协商共享密钥； 安全性基于离散对数难题。 Alice和Bob协商好一个大素数p和一个模p的原根g。,选x,g

25、x mod p,gy mod p,选y,窃听,公共网络,Alice,Bob,Eve,第七章 公钥密码算法,4.椭圆曲线上的密码算法,(1) Diffie-Hellman密钥交换： 先取素数p2180和两个参数a,b，得到满足方程 y2=x3+ax+b (mod p),4a3+27b20的椭圆曲线以及其 上面的点构成的Abel群EP(a,b)。G是EP(a,b)的生成元。,(2)椭圆曲线上的加密算法ECC： 选取椭圆曲线得到Abel群EP(a,b)，G是EP(a,b) 的生成元，公开。 将明文消息m通过编码嵌入到曲线上的点Pm，再对 点Pm做加密变换。,第七章 公钥密码算法,设用户Bob的私钥n

26、B,公钥为PB=nBG; Alice将消息m发送给Bob。,举例： 选E:y2=x3+x+6 (mod 11)，生成元G=(2,7) 首先计算2G： 因为：=(3x12+1)/2y1=(322+1)/(27) (mod 11) =8 于是：x3=2-x1-x2 (mod 11)=5 y3=(x1-x3)-y1 (mod 11)=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),1

27、1G=(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双线性映射(Weil pairing),1.双线性映射的性质,设(G1,+)和(G2,)为两个q阶循环群。 双线性对： G1G1G

28、2 满足如下的属性： 双线性：对于任意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) 通信方在没有对话的情况下得到共享密钥：

29、 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=x mod p 证明：首先，根据二项式定理：,当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,第八章

30、 同余方程,用归纳法证明： 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的因

31、子d，有： p|bd-1 或者p=1 mod n 证明： 根据费马小定理有 bp = b mod p bp-1 = 1 mod p p|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=b mod p，则(a/p)=(b/p)； 若a=b mod n，则(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

32、(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不能判定方程是否

33、有解； Jacobi符号=-1可以判定方程无解。 Legendre符号=1可以判定方程有解； Legendre符号=-1可以判定方程无解。,第九章 二次符号,举例1：测试x2=19 mod 101是否有解？ 解：(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=1237 mo

34、d 4327是否有解？ 解：(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=2 mod

35、3599是否有解？ 由于3599=5961，所以方程等价于 x2=2 mod 59 x2=2 mod 61 (2/59)= (-1)(592-1)/8 =-1 无解 (2/61)= (-1)(612-1)/8 =-1 无解 所以方程x2=2 mod 3599无解 而根据Jacobi符号有 (2/3599)= (2/59)(2/61) =1 因此：Jacobi符号=1不能判定方程是否有解,作业： (1)判断2是否为模1033的一个平方？ (2)判断方程x2=119 mod 1009是否有解？ (3)判定3是不是模2009的一个平方？,第十章 素性测试,10.1 Miller-Rabin素性检测算

36、法,许多密码算法和协议需要“随机”的大素数， 而大素数的生成，常用的方法是随机生成一个整 数n，然后对其进行素性测试。 方法：(1)穷举法； (2)概率素性测试。-概率素数(伪素数),1.强伪素数 如果p是一个素数，则Z/p中应该只有1的两个 平方根，即1和p-1。 设n是奇整数，因式分解为： n-1=2rm m为奇数 如果bm=1 mod n，或对某些0sr，满足 b2sm=-1 mod n，则n是基数为b的强伪素数。,第十章 素性测试,2.检测算法： 可以证明合数的确定性，但只能以一定的概 率说明素性性。步骤为： 首先，因式分解n-1=2rm m为奇数； 随机选1bn-1； 设s=0，计算

37、z=bm mod n,如果z=1，则停止，n以3/4的概率是素数， b是n是素数的证据。 否则继续：s=s+1，计算z=z2 mod n。 若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=528 r=8,m=5 首先验证b0=415 mod 1281=？ 41 5 1 41 4 41 400 2 41 1156 1 41 0 115641=

38、47396 mod 1281=-1 所以1281对基数41是强伪素数。,第十章 素性测试,第十章 素性测试,10.2 Lehmann素性检测算法,(1)随机选a1 1 若n为素数，可判定x2=b mod n有解 -1 若x2=b mod n无解,(b/n)=,(3)欧拉证明了，对素数p有： (b/p)=b(p-1)/2 mod p 相反，如果n不是素数，则b(n-1)/2 mod n对于不 同的b就是随机。 同样，如果(b/n)=b(n-1)/2 mod n，则整数n是基 数为b的欧拉伪素数，b称为欧拉证据。,第十章 素性测试,2.算法描述 (1)随机选an; (2)若gcd(a,n) 1，则

39、n为合数，终止。 (3)计算j=a(n-1)/2 mod n和J=(a/n): 若jJ，则n为合数，终止。 若jJ，n以50%概率为素数，继续； (4)对a选t次重复，n以(1-1/2t)概率为素数。,3.费马伪素数 (1)设gcd(n,b)=1，如果bn-1 =1 mod n ，则整 数n对于基数b是费马伪素数。 (2)一个非素数对于不同的基数有不同的表现。 举例：整数n为91=713，基数b分别2和3。,第十一章 因式分解,11.1 Pollards Rho算法,大整数分解是许多密码学算法和协议的安全 依据，如RSA密码体制。 方法：(1)穷举法； (2)分解算法。,可以较快地找到合数的较

40、小因子。 1.算法描述 给定整数n，设初始值x=2，y=x2+1； (1)计算g=gcd(x-y,n)； (2)若1n1/2不满足，则还需考虑b0，使得： b0n-1=1 mod n 且 gcd(b0k-1,n)=1,举例验证： (1) n=31 (2) n=103,3.推论 设n=u2m+1，n为奇数且u2m。 若存在一个b，使得b(n-1)/2=-1 mod n，则n为素数。 举例验证：n=13=322+1； n=41=523+1,第十一章 因式分解,11.4 二次筛法 因子基：前t个素数的集合S=2,3,5,7, S平滑：整数n的所有因子都小于等于S。 算法：试图分解整数n。 (1)选择

41、一个因子基S=2,3,5,7, ; (2)选取 ，取b=ai2%n; (3)若b是S平滑的，且为一个平方，则可通过 计算n的因子。 举例：n=143,第十二章 离散对数,12.1 离散对数问题,很多秘密技术的安全性都建立在离散对数 问题的困难上，如ECC密码体制。,1.离散对数 对正整数n，若bl=a mod n，则l称为a的以b为 底模n的离散对数，记为logba。 2.离散对数问题DLP 给定素数p，Zpx的生成元b和元素aZpx ，求解 x满足：bx=a mod p 3.广义离散对数问题GDLP 给定阶为n的有限循环群G，G的生成元b和元素 aG，求解x满足：bx=a mod n,第十二

42、章 离散对数,12.1 Baby-step Giant-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=xc mod p,i=i+1 举例：计算log211 mod 227 作业：利用Baby-step算法求log25 mod 29。,第十二章 离散对数,12.2Pollard的Pho方法 定义函数F： (ax,m+1,

43、n) 若xis1 F(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。求log49 mod 59。,第十二章 离散对数,12.3指数演算 原理：利用已知的因子基德离散对数进行运算 设b是循环群G的生成元，n=|G| (1)对于b，取因子基S=p1,p2,=2,3,5,； (2)考虑b的随机方幂，开始生成关系： logbp1,logbp2,(3)对给定的aG，选择随机整数k，并尝试： abk=p1k1ptkt mod n 如果成功，则可求解： logba=k1logbp1+ktlogbptk mod |G| 举例：设G=Z/X29，n=|G|=28，选原根b=11， 因子基S=2,3,5，求log117。,第十三章 协议经典算法,13.1 秘密共