课件资源05公钥密码学与

—公 学与

公 体传统的私钥（private/secret/singlekey）加密 安

密钥分配－在没有信任的KDC保管密钥下，如何实数字签名－如何确认一个消息是否由发送方发出。可能是3000使用两个

年由斯坦福大学的WhitfieldDiffie和Martin 学新方向”一文 WDiffieandME manNewDirectionsinCryptographyIEEETransactiononInformationTheoryVIT-22No6Nov1976PP644-654RLRivestAShamirLAdlemanAmethodforobtainingdigitalsignaturesandpublic-key cryptosystemsCommunicationsoftheACM Vol21No2Feb1978PP120-1261和验证签名（verifysignature）

对称对称加公钥加密 密两个（其中一个必须 的 算 算加密 加密一个（必须是 收发双方必须共享密每一个用户都可以发送消使

人 ）加密X->Y:Y=:Y->X:X=DKUa(Y)=X=DKRa(EKUa(X))=2/ ）算加数字签密钥交是是是椭圆曲是是是Diffie-否否是否是否

的密钥太大了(>512bits) 软件实现的DES大约比RSA快100 用于 )

公 体ap-1modp= :合{amodp,2amodp,…,(p-1)amodp},对于p,(p-1)!=12…(p-[(amodp)(2amodp)…((p-1)amodp)]mod[a2a…(p-1)a]mod[a(p-1)!]mod注意到(p-1)!与p互素,因此定理成立也称为Fermat小定理，在公钥和素性测试中很有

Euler函数在对n剩余的约化集（reducedsetofresidues）是剩余类中与n互素的剩余例如对于n=10，完整的剩余类是{012345678，剩余的约化集是{1373有aø(n)modn=1如 :数考虑集合S={(ax1modn),(ax2modn),…,(axø(n)modn)}(aximodn)与n(aximodn)两两不等(aximodn)=(axjmodn)ximodn=xjmodS有ø(n从而xi=(aximodn)((axi))modn(a(n)xi)mod注意到xi与n互素从而得到结论

aø(n)modn (a,n)=1）aø(n)+1modn= (a,n)=1的要求难以满a是明文，n是参数，anaan天无绝 akø(n)+1modn=a，k这里n=pq，p,q是素数，且对任何整数y和素数方程y=axmodp

Fermat定理：ap-1modp=Euler定理：aø(n)modn=推论：akø(n)+1modnan=pq， ）公 体

和密文在0~n-1之间n是一个正整数 (Galois)求幂需要O((logn))操作（易因子分解需要O(e)操作（难4RSAp注意到：ø(N)=(p-1)(q-这里), 1 e.d=1modø(N)and

计算：C=MemodN用 M=Cdmod必须注意，消息M必须小于模N 需要则因为Euler定理及其推论aø(N)modN=1,这里 Mkø(N)+1modNM这里和Cd=(Me)d=M1+kø(N)=Mmod

选择素数：p=17和计算N=pq计算ø(N)=(p–1)(q-选择 (e,160)=1;选择d：de=1mod160并且d160,d=23因为23×7=161=160+1发布公钥私钥对于消息M=88

C=887mod187=

amodna modn ：M=1123mod187=

mbb

仅需要O(log2K)关于模n例如：7574.713.710mod例如：31293128.315.34mod5ped素数p,q必须不能轻易地从模N=pq指数（exponents）ed

N:两素数的乘积（N=p.q），p，q必Miller-Rabin算e：与Miller-Rabin算扩展Euclid算d:d=e-1扩展Euclid算快速模幂算C=M快速模幂算快速模幂算M=C快速模幂算RSA用三种方

数学方法有3N=p.qø(N，然后直接决定ø(N，并找到直接找90年代大数分解的进展（MIPS年:百万条指令/秒1年完成日年算7二次筛法（Quadratic一般数域筛位的十进制素数。模n的长度要求至少是512比特 国际数字签名标准ISO/IEC9796中规定n的长度位512比特位。p和q的长度应仅相差几位，对1024bits的密钥而言，应该在10

Fermat定理：amodp=Euler定理：amodn=6 W.DiffeandM.E man,NewDirectionsinCryptography,IEEETransactiononInformationThe