公开密钥密码阳振坤yzkicstpkueducn计算机科学技术.ppt

资源描述

《公开密钥密码阳振坤yzkicstpkueducn计算机科学技术.ppt》由会员分享，可在线阅读，更多相关《公开密钥密码阳振坤yzkicstpkueducn计算机科学技术.ppt（76页珍藏版）》请在三一办公上搜索。

1、1,四、公开密钥密码阳振坤计算机科学技术研究所,密码算法与应用基础,2,信息安全引论对称密钥密码对称密钥密码应用基础公开密钥密码数字签名与Hash函数公开密钥密码应用基础密钥交换与密钥管理,内容提要,3,信息安全的基本内容,保密性(Confidentiality)真实性(Authentication)完整性(Integrity)不可否认性(Nonrepudiation),4,公开密钥密码,基本思想数学基础 RSA算法基于离散对数的算法基于椭圆曲线的算法密钥分发总结,5,基本思想,加密与解密由不同的密钥完成加密:XY:Y=EKU(X)解密:YX:X=DKR(Y)=DKR(EKU(X)从

2、解密密钥得到加密密钥在计算上是不可行的加密与解密的顺序没有限制(不是必须的)X=DKR(EKU(X)=EKU(DKR(X)若X=Y且映射E:XY是映上的,则成立 EKU(X)=EKU(DKR(EKU(X)若X=Y且为有限集合(例如分组密码),则E:XY是映上的,从而成立,6,用公钥密码实现保密,用户拥有自己的密钥对(KU,KR)公钥KU公开,私钥KR保密AB:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X)=X,7,用公钥密码实现认证,条件:加密与解密的顺序没有限制认证:AALL:Y=DKRa(X)ALL:EKUa(Y)=EKUa(DKRa(X)=X认证+保密:AB:Z=EKUb

3、(DKRa(X)B:EKUa(DKRb(Z)=X,8,公钥密钥的应用范畴,加密/解密数字签名(身份认证)密钥交换,9,公钥密钥算法必须满足的条件,密钥对的生成在计算上是可行的用公钥加密明文在计算上是可行的用私钥解密密文在计算上是可行的从公钥获得私钥在计算上是不可行的从公钥和密文来获得明文在计算上是不可行的加密与解密的顺序没有限制(不是必须的)X=DKR(EKU(X)=EKU(DKR(X),10,One-way trapdoor function,对称密钥密码:Y=FK(X)easy if X&K are knownX=FK-1(Y)easy if Y&K are knownX=FK-1(Y)i

4、nfeasible if only Y is known公开密钥密码:Y=FK(X)easy if X&K are knownX=FK-1(Y)easy if Y&K are knownWhere,K and K are related keys.X=FK-1(Y)infeasible if Y&K are known but K is unknown.,11,公钥密码分析,强制破译通过公钥得到私钥破译公钥加密的对称密钥,12,数学基础,素数,最大公约数(gcd),互素模运算:a=qn+r,0rn(a mod n)=r 同余:ab mod n iff(a mod n)=(b mod n)(a

5、mod n)(b mod n)mod n=(ab)mod n(a mod n)(b mod n)mod n=(ab)mod nIf(ab)(ac)mod n and a is relatively prime to n,then bc mod n(ab)(ac)mod n n|(ab-ac)n|(a(b-c)n|(b-c)bc mod n,13,Fermat定理,Fermat定理:p素数,a是整数且不能被p整除,则:ap-1 1 mod p证明:考虑集合1,2,p-1,对每个数乘以a,得到集合a mod p,2a mod p,(p-1)a mod p,对于p,后者两两不同且都在1与p-1之间,

6、因此两个集合相同,于是:(p-1)!=12(p-1)(a mod p)(2a mod p)(p-1)a mod p)mod p a2a(p-1)a mod p ap-1(p-1)!mod p注意到(p-1)!与p互素,因此定理成立.推论:p素数,a是任意整数,则:ap a mod p,14,Euler数,Euler数(n)定义为小于n且与n互素的正整数个数p是素数,(p)=p-1若n的因子分解为n=Piai,ai0,Pi互不相同,则(n)=Piai(1-1/Pi)若gcd(m,n)=1,则(mn)=(m)(n),特别地,若pq且都是素数,(pq)=(p-1)(q-1)Euler定理:若a与n为

7、互素的正整数,则:a(n)1 mod n,15,Euler定理,a(n)1 mod n证明:R=x1,x2,x(n)为所有小于n且与n互素的正整数,考虑集合S=(ax1mod n),(ax2mod n),(ax(n)mod n)(aximod n)与n互素(aximod n)两两不等:(aximod n)=(axjmod n)ximod n=xjmod n S有(n)个元素故S也是所有小于n且与n互素的正整数,因此S=R,从而 xi=(aximod n)(axi)mod n(a(n)xi)mod n注意到xi 与n互素,从而得到结论.,16,Euler定理推论,推论:若n=pq,pq都是素数,

8、k是任意整数,则 mk(p-1)(q-1)+1 m mod n,对任意0mn证明:若m=0或n,结论是显然的;若m与n互素,注意到(n)=(p-1)(q-1),由Euler定理可得到结论;否则m必定是p或者q的倍数,不妨设m=sp,则0sq为正整数,m与q互素,由Euler定理得到:m(q)1 mod q(m(q)k(p)1 mod q mk(p-1)(q-1)=tq+1 t是整数等式两边乘以m=sp,得到:mk(p-1)(q-1)+1=(tq+1)sp=tspq+sp m mod n,17,中国剩余定理(1),中国剩余定理:m1,m2,mk是两两互素的整数,a1,a2,ak是任意整数,M=m

9、i,那么方程组 xai mod mi,1im关于模M有唯一解:x aiMi(Mi-1 mod mi)mod M,Mi=M/mi证明:m1,m2,mk两两互素因此gcd(Mi,mi)=1 Mi-1 mod mi存在正确性:Mi定义 Mi0 mod mj,任给ij,18,中国剩余定理(2),x aiMi(Mi-1 mod mi)mod mj ajMj(Mj-1 mod mj)mod mj aj mod mj 正确性唯一性:假如x,y都是解x y mod mi,对任意imi|(x-y),对任意i(mi)|(x-y),对任意j(m1,m2,mk两两互素)M|(x-y)x y mod M唯一性,19,(

11、用最广泛的公钥密码算法只在美国申请专利且已于2000年9月到期NSA声称在60年代中期发现了公钥算法英国的Clifford Cocks在1973年发表了与RSA几乎一样的算法,21,RSA算法描述,分组大小为k,2k n 2k+1加密:C=Me mod n 解密:M=Cd mod n=Med mod n公钥:KU=e,n,私钥:KR=d,n上述算法需要满足以下条件:能够找到e,d,n,使得Med mod n=M,对所有Mn 计算Me和Cd相对容易从e和n得到d是在计算上不可行的,22,RSA密钥生成原理,令n=pq,pq都是素数,(n)=(p-1)(q-1)是n的Euler数Euler定理推

12、论:若n=pq,pq都是素数,k是任意整数,则 mk(p-1)(q-1)+1 m mod n,对任意0mn只要选择e,d,满足ed=k(n)+1,即ed 1 mod(n)d e-1 mod(n)公钥:KU=e,n,私钥:KR=d,n,23,RSA密钥生成与使用,选择两个大素数p,q,pq 计算n=pq,(n)=(p-1)(q-1)选择整数e,使得gcd(e,(n)=1(两个随机数互素概率0.6)计算d e-1 mod(n)公钥:KU=e,n,私钥:KR=d,n加密:C=Me mod n 解密:M=Cd mod n,24,提高RSA解密速度:结论1,解密:M=Cd mod n需作大数的幂运算,速

13、度慢结论1:若pq都是素数,n=pq,则同余方程x xp mod px xq mod q对模n有唯一解 x=(xp-xq)(q-1mod p)q+xq 证明:pq是素数 gcd(p,q)=1 q-1mod p存在.唯一性由中国剩余定理保证.验证解:令r=q-1mod p,则r是整数,rq1 mod px=(xp-xq)rq+xq对于q,x=(xp-xq)r)q+xqxq mod q对于p,x=(xp-xq)(rq)+xq(xp-xq)+xqxp mod p,25,提高RSA解密速度:结论2,结论2:p素数,a是任意整数,则ak(a mod p)k mod(p-1)mod p,k是任意整数证明:

14、若a 0 mod p,结论是显然的.否则,令k=t(p-1)+r,t,r是整数,r=k mod(p-1),那么ak=at(p-1)+r at(p-1)ar mod p ar mod p(Fermat定理:ap-1 1 mod p)(a mod p)r mod p(a mod p)k mod(p-1)mod p,26,提高RSA解密速度:方法,解密:M=Cd mod n,n=pq,pq都是素数假如得到了Mp M mod pMq M mod q就得到了M=(Mp-Mq)(q-1mod p)q+Mq mod n由于M=Cd mod n,因此 Mp=Cd mod p=(C mod p)d mod(p-

15、1)mod p Mq=Cd mod q=(C mod q)d mod(q-1)mod q由于C mod p与C mod q要比C小,d mod(p-1)与d mod(q-1)也比d小,故解密速度会提高(48倍).,27,提高RSA加密速度?(1),同样的方法可以用于RSA的加密加密:C=Me mod n,n=pq,pq都是素数假如得到了Cp C mod pCq C mod q就得到了C=(Cp-Cq)(q-1mod p)q+Cq mod n由于C=Me,从而 Cp=Me mod p=(M mod p)e mod(p-1)mod p Cq=Me mod q=(M mod q)e mod(q-1)

16、mod q加密速度是否会提高?,28,提高RSA加密速度?(2),加密:C=Me mod n,n=pq,pq都是素数M0,1,2,2k-10,1,2,n-1,其中2kn2k+1定义上,加密E:0,1,2,n-10,1,2,n-1实际上,加密E:0,1,2,2k-10,1,2,n-1解密映射的定义域总是0,1,2,n-1M在较小的空间上,C在较大的空间上e一般可以选择比d小加密:Cp=Me mod p=(M mod p)e mod(p-1)mod p 解密:Mp=Cd mod p=(C mod p)d mod(p-1)mod p同样的方法对加密速度的提高不如对解密速度的提高显著,29,RSA的

17、安全性,强制破解基于数学的攻击基于运算时间的攻击,30,RSA加密解密计算量,加密:C=Me mod n 解密:M=Cd mod n幂运算位数增长快幂运算速度慢并且e,d都是很大的数(a mod n)(b mod n)mod n=(ab)mod n计算xm,其中m=2s,只需要计算s次,即计算:xmi,mi=2i,i=0,1,s,31,计算幂,计算d=am,m=bkbk-1b0(二进制表示)d1for ik downto 0 do d(dd)mod n if bi=1 then d(da)mod nreturn d,32,Euclid算法,gcd(a,b)=gcd(b,a+kb)a,b,k为

18、任意整数gcd(a,b)=gcd(b,a mod b)a0,b0Eclid(d,f):求最大共约数,假定df Xf,Yd if Y=0 then return X X X mod Y XY goto 上述的循环最多进行多少次?2log2(max(f,d),33,扩展Euclid算法,ExtEclid(d,f):求最大共约数或模逆,假定df(X1,X2,X3)(1,0,f),(Y1,Y2,Y3)(0,1,d)if Y3=0 then return X3,no inverse if Y3=1 then return 1,inverse is Y2 Q(X3/Y3)的整数部分(X1,X2,X3)(X

19、1-QY1,X2-QY2,X3-QY3)(X1,X2,X3)(Y1,Y2,Y3)goto fX1+dX2=X3,fY1+dY2=Y3若Y3=1,则 fY1+dY2=1 dY2=(-Y1)f+1 dY2 1 mod f Y2=d-1 mod f,34,素数模的平方剩余解,直接判断一个整数是否为素数是困难的命题:如果p是素数,则方程x2 1 mod p只有平凡解x 1 mod p.证明:x2 1 mod p p|(x2-1)p|(x+1)(x-1)p|(x+1),或者p|(x-1)x+1=kp,或者x-1=jp,k,j是整数x=kp-1,或者x=jp+1x 1 mod p,或者x-1 mod p,

20、35,Miller-Rabin素数测试算法,Miller-Rabin算法用来测试一个整数是否是素数WITNESS(a,n)设bkbk-1b0是(n-1)的二进制表示 d1 for ik downto 0 do xd d(dd)mod n/x2 1 mod n if(d=1&x1&xn-1)return TRUE if(bi=1)then d(da)/d=an-1 if(d1)return TRUE/Fermat定理 else return FALSEMiller-Rabin是概率测试(一次概率约0.5),36,素数生成,素数生成过程:随机选择一个奇数n(如通过伪随机数发生器)随机选择a,使an

21、进行素数测试(例如用Miller-Rabin算法),若n没有通过测试,抛弃n,转到如果通过了足够次数的测试,认为n是素数,否则转到.素数定理:(N)N/ln(N),(N)为不超过N的素数个数.随机整数N是素数的概率是1/ln(N),37,基于数学的攻击,公钥:KU=e,n,私钥:KR=d,n,n=pq分解n=pq(n)=(p-1)(q-1)d=e-1 mod(n)不求出p,q,直接求(n)d=e-1 mod(n)不求出(n),直接计算d已知的方法至少跟因子分解一样难度尚未发现多项式时间的因子分解算法因子分解的算法已经取得了长足进步如果en并且dn,则d容易被得到.目前已知最好的结果是=0

22、.292措施:选择足够大的n(1024位以上),并且使得e,d之间相差不太大,也不太小,38,同模攻击,如果A,B使用同样模n的RSA算法(e1,d1,n),(e2,d2,n),C把信息M用A,B的公钥分别加密并传给它们:Y1=Md1:AY2=Md2:B假如gcd(d1,d2)=1,则窃听者能获得明文.做法是:找到整数a1,a2,使得:a1d1+a2d2=1(gcd(d1,d2)=1)不妨假定a10,那么:M=(Y11)-a1Y2a2 mod n(Y11)-a1Y2a2=(Md1)1)-a1(Md2)a2=Md1a1+a2d2措施:避免在不同用户之间共享模.,39,其他攻击,RSA的同态性质:

23、EK(m1m2)=EK(m1)EK(m2)措施:加密前对信息处理,如通过hash或者单向函数如果(p-1)或者(q-1)只有小的素数因子,则n容易被分解,n被分解的计算量与(p-1)或者(q-1)的最大素因子成某种正比.措施:找到p1q1,使得p1,q1,2p1+1,2q1+1都是素数,然后选择p=2p1+1,q=2q1+1(安全素数).,40,基于运算时间的攻击,基于加密程序运行时间的攻击计算d=am,m=bkbk-1b0(二进制表示)d1for ik downto 0 do d(dd)mod n if bi=1 then d(da)mod nreturn d若bi=1,执行d(da)mod

24、 n,否则不执行.有少数的a,d,上述模乘速度很慢从左到右逐个确定bi,41,基于运算时间攻击的特征与防备,特征:一种全新的攻击手段选择明文的攻击适用于攻击其他公钥算法防备:计算d=am,m=bkbk-1b0(二进制表示)for ik downto 0 do d(dd)mod n if bi=1 then d(da)mod nreturn dConstant exponentiation timeRandom delayBlinding,42,RSA Blinding,RSA blinding:选择一个随机数r,使得gcd(r,n)=1,0rn加密:C=(Mr)e mod n C=CD mod

25、 n D=(r-1)e,r-1是r关于mod n的乘法逆解密:M=Cd mod n代价:每个块增加两个乘法,210%的性能损失其他解决措施(初始化向量),43,因子分解算法改进,Special number field sieve速度更快,44,Montre Carlo模型,YES-BIASED型Montre Carlo算法:一个YES的回答总是正确的,一个NO的回答则可能是正确,也可能是错误的.称一个YES-BIASED算法具有错误概率,是指它回答NO时出错的几率至多是 NO-BIASED型Montre Carlo算法Miller-Rabin属于YES-BIASED型Montre Carlo

26、算法,其出错概率是0.5,45,密钥分发,分发公钥Public announcement Publicly available directory Public-key authority Public key certificates 利用公钥分发对称密钥Simple secret key distribution Secret key distribution with confidentiality and auhtentication Hybrid scheme,46,Public announcement,直接把公钥散发出去使用PGP并且把公钥附上能被假冒,47,Publicly a

27、vailable directory,需要可信任的中央授权机构授权机构维护着动态name,public key列表用户在授权机构注册其public key(安全通道)用户可以替换其public key授权机构定期发布或更新整个目录用户可在网络上直接访问公共目录(安全通道),48,Public-key publication,若成功修改了公共目录,则攻击者可假冒用户,49,Public-key authority,需要可信任的中央授权机构每个用户知道授权机构的公钥 AAuth:(IDA,IDB,T1)AuthA:EKRauth(KUb,T1)AB:EKUb(IDA,N1)BAuth:(IDB,I

28、DA,T2)AuthB:EKRauth(KUa,T2)BA:EKUa(N1,N2)AB:EKUb(N2),50,Public-key Distribution Scenario,若成功修改了公共目录,则攻击者可假冒用户授权中心易成为性能及安全瓶颈,51,Public-key certificates,任何人可以阅读证书以确定证书拥有者的姓名和公钥任何人可以验证证书是由授权机构发出而非伪造的只有授权机构才可以发行和更新证书任何人可以验证证书的时效性(非失效证书)CA=EKRauth(T,IDA,KUa),52,Exchange of public-key certificates,泄漏私钥等价于

29、丢失证书证书的时间作为有效期,53,Simple secret key distribution,Merkle的建议:A生成KUa,KRa,AB:(IDA,KUa)B生成随机密钥Ks,BA:EKUa(Ks)A解密EKUa(Ks)得到Ks:DKRa(EKUa(Ks)A丢弃KUa,KRa,B丢弃KUa通讯前不需存在密钥,通讯后也不存在密钥能抵抗偷听,不能抵抗主动攻击(中间人攻击),54,Merkle协议的中间人攻击,A生成KUa,KRa,AB:(IDA,KUa)E截获,生成KUe,KRe冒充AB:(IDA,KUe)B生成随机密钥Ks,BA:EKUe(Ks)E截获,解密后再用EKUa加密KsA:EK

30、Ua(Ks)A丢弃KUa,KRa,B丢弃KUaE获得了Ks,故以后只需进行窃听.A,B并不知晓它们被攻击了,55,Secret key distribution with confidentiality and authentication,假定A和B已经获得了双方的公钥:AB:EKUb(IDA,N1)BA:EKUa(N1,N2)AB:EKUb(N2)AB:Y=EKUb(EKRa(Ks)B解密Y获得会话密钥Ks=DKUa(DKRb(Y),56,Secret key distribution with confidentiality and authentication:Map,57,Hybri

31、d Scheme,在IBM大型主机上使用仍然使用KDCKDC与每个用户都拥有公钥,私钥对KDC与每个用户共享主密钥(对称密钥密码)会话密钥的分发由主密钥完成主密钥更新由公钥完成PerformanceBackward compatibility,58,原根(primitive root),Euler定理表明,对两个互素的整数a,n,a(n)1 mod n因此存在最小正整数m(n)(m|(n),使得am 1 mod n若对某个a,m=(n),则称a是n的一个原根(primitive root).只有为2,4,p,2p的数才有原根,其中p是奇素数.对于素数p,若a是p的一个原根,则:a,a1,a2,

32、ap-1关于p两两不同余,从而构成了p的非0剩余类,即与1,2,(p-1)关于模p等价.,59,离散对数,若a是素数p的一个原根,则对任意整数b,b0 mod p,存在唯一的整数i,1i(p-1),使得:bai mod pi称为b以a为基模p的指数(离散对数),记作inda,p(b).容易知道:inda,p(xy)=inda,p(x)+inda,p(y)mod(p)inda,p(xr)=rinda,p(x)mod(p)离散对数的计算:ygx mod p已知g,x,p,计算y是容易的已知y,g,p,计算x是困难的,60,Diffie-Hellman密钥交换,双方选择素数q以及q的一个原根rA选择

33、Xq,计算XA=rXmod p,AB:XAB选择Yq,计算YB=rYmod p,BA:YBA计算:(YB)X(rY)XrXYmod pB计算:(XA)Y(rX)YrXYmod p双方获得一个共享密钥(rXYmod p)素数q以及q的原根r可由一方选择后发给对方不能抵抗replay攻击对中间人攻击的抵抗力远好于“Simple secret key distribution(Merkle的建议)”,61,Diffie-Hellman密钥交换的攻击,双方选择素数q以及q的一个原根r(假定E知道)A选择Xq,计算XA=rXmod p,AB:XAE截获XA,选Z,计算ZE=rZmod p,冒充AB:ZE

34、B选择Yq,计算YB=rYmod p,BA:YBE截获YB,冒充BA:ZEA计算:(ZE)X(rZ)XrZXmod pB计算:(ZE)Y(rZ)YrYZmod pE计算:(XA)ZrXZmod p,(YB)ZrYZmod pE无法计算出rXYmod pE永远必须实时截获并冒充转发,否则会被发现.,62,ElGamal加密算法,选择:一个素数p,p的一个原根r,一个整数a,令s=ra,公开p,r,s,保密a.对于明文信息x,加密:秘密选择随机数k,计算(rk mod p,xsk mod p)作为密文解密:(xsk)(rk)a)-1 xrakr-ak x mod p信息有扩张,63,椭圆曲线密码介

35、绍,1985年Miller,Koblitz 独立提出y2+axy+by=x3+cx2+dx+e曲线上的点连同无穷远点O的集合加法:若曲线三点在一条直线上,则其和为零倍数:一个点的两倍是它的切线与曲线的另一个交点,64,椭圆曲线密码示意图,65,有限域上椭圆曲线,有限域上椭圆曲线y2x3+ax+b mod p p是奇素数,且4a3+27b20 mod py2+xyx3+ax2+b mod 2m加法公式:P=(x1,y1),Q=(x2,y2)若x1=x2且y1=-y2,则P+Q=O,否则 P+Q=(x3,y3)x3=2-x1-x2y3=(x1-x3)-y1其中,=(y2-y1)/(x2-x1),如

36、果PQ=(3x12+a)/2y1,如果P=Q,66,Ep(a,b),椭圆曲线上的整数点在上述运算下成为一个交换群(Abelian群),记作Ep(a,b).关于|Ep(a,b)|,有如下不等式:p+1-2p1/2|Ep(a,b)|p+1+2p1/2该不等式表明:|Ep(a,b)|pG是Ep(a,b)的一个元素,使得nG=O的最小正整数n称为元素G的阶.,67,椭圆曲线密钥交换,双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择Xn,计算PA=XG,AB:PAB选择Yn,计算PB=YG,BA:PBA计算:X(PB)=XYGB计算:Y(PA)=YXG=XYG双方获得

37、了一个共享会话密钥(XYG)不能抵抗replay攻击对中间人攻击的抵抗力远好于“Simple secret key distribution(Merkle的建议)”,68,椭圆曲线密钥交换的攻击,双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数A选择Xn,计算PA=XG,AB:PAE截获PA,选Z,计算PE=ZG,冒充AB:PEB选择Yn,计算PB=YG,BA:PBE截获PB,冒充BA:PEA计算:XZE=XZGB计算:YZE=YZGE计算:ZPA=ZXG,ZPB=ZYGE无法计算出XYGE永远必须实时截获并冒充转发,否则会被发现.,69,椭圆曲线加密解密,选择E

38、p(a,b)的元素G,使得G的阶n是一个大素数,秘密选择整数r.计算P=rG,公开(p,a,b,G,P),保密r.加密M:选择随机数k,C=kG,M+kP)如果k使得kG或者kP为O,则要重新选择k.解密C:(M+kP)-r(kG)=M+krG-rkG=M加密信息有扩张,70,椭圆曲线密码的安全性,难点:从P和kP获得k对椭圆曲线研究的时间短椭圆曲线要求密钥长度短,速度快对比:ECC RSA,71,公开密钥密码总结,三类算法:RSA,ElGamal,ECCRSA基础:IFP(Integer Factorization Problem)加密、解密、密钥交换、数字签名使用最广泛ElGamal基础:

39、DLP(Discrete Logarithm Problem)加密、解密、密钥交换、数字签名,72,公开密钥密码总结,ECC基础:ECDLP(Elliptic Curve Discrete Logarithm Problem)加密、解密、密钥交换、数字签名密钥短,速度快正在开始广泛应用公钥算法加密解密速度慢误区:公开密钥密码算法更安全公开密钥密码使对称密钥密码过时了公钥的分发是简单和一目了然的,73,Euler公式证明(1),注意到当n是素数时,(n)=n-1,所以只要说明,对任意素数p和任意正整数n:(np)=p(n),若p整除n(np)=(p-1)(n),若p不整除n证明:把集合1,2

40、,n分成两子集X=x1,x2,x(n)和Y=y1,y2,yn-(n),X为所有与n互素的数,Y为其余.记Xk=kn+x1,kn+x2,kn+x(n),Yk=kn+y1,kn+y2,kn+yn-(n),0kp,显然全部的Xk,Yk的并集构成1,2,np.由Y的定义,Y与n有大于1的公因子,从而所有Yk与(np)有大于1的共因子.,74,Euler公式证明(2),若p整除n,由于X与n互素,容易知道Xk与n互素,故(np)=p|X|=p(n)若p不整除n,若Xk中一个元素kn+xi与(np)有大于1公因子,设q是其一个素数公因子,则q|n或者q=p,假如是前者,则q|n,q|(kn+xi)q|xi

41、,从而n与xi有公因子q,这与X的定义矛盾,因此q=p,这表明若某个Xk中的某个元素kn+xi与(np)有大于1公因子,则该公因子只能是p.注意到不超过(np)的所有p的倍数是px1,px2,px(n)和py1,py2,pyn-(n).,75,Euler公式证明(3),由于n与yj不互素,故存在素数q,使得q|n,q|yj,又由于p不整除n qp.由于xi与n互素,所以q不能整除xi,也不能整除pxi pxikn+yj(pxi不含因子q,而kn和yj含因子q)pyi kn+xj(xi不含因子q,而kn和pyj含因子q)这说明任一pxi(1i(n)位于某个Xk中,任一pyi(1in-(n)位于某个Yk中,故全部Xk中与n有公因子p的数是px1,px2,px(n),故(np)=p|X|-(n)=(p-1)(n)公式得证.,76,实习作业之二,实现Rijndael,具体要求与第一次作业相同,差别:算法是Rijndael(而不是DES)十一月七日前以email提交电子文档Email地址:参见网址:/,

展开阅读全文