1、给定一大素数p（比如，p在21024数量级），p1含另一大素数因子。攻击者Eve截获了密文c。分析者没有办法在有效时间内将n分解出来。若截获了密文c，又知道n个物品重量b1，b2，b3，bn，求解明文m就是背包问题。当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。基中的向量的个数称为格的维数。计算npq和z(p1)(q1)。这个漏洞还有更深刻的隐患，比如在消息认证过程中容易产生伪造。至于（p，q），可以是Bob的另一部分私钥，也可以是对所有人（包括Bob）都保密的。一个潜在问题：如果Oscar获得了这对（z,y)，他能用自己的签名来替代Alice的签名如果n已通过足够的测试,则
2、接受n,否则转向步骤2;这个漏洞还有更深刻的隐患，比如在消息认证过程中容易产生伪造。若已知y，g，p，求x满足y=gxmodp，称为求解离散对数问题。（模除运算/(modn)是一个数论运算）1977年由美国麻省理工学院的三位教授（3）卸载：如果S0，则令S:=S-ak，返回（1）。至于（p，q），可以是Bob的另一部分私钥，也可以是对所有人（包括Bob）都保密的。一个根的(modp)、(modq)值是p-mp、mq；C=18191223(mod 2867)如何判定一个给定的整数是素数？)ln)(ln(ln(exp(ppO.logln)ln)(lnln(lnexp()ln)(ln(lnexp(;
3、2)(ln(lnexp()ln)(ln(lnexp(2log2pppppppppppp)lnlnln(expnnO)lnlnln2(expppO)ln(ln)(ln92.1(exp(3231nnO(1)给定x，计算y=f(x)是容易的选择两个大的素数p和q。=18191024 1819128 181964 18194 18192 18191(mod 2867)容易，只需要不超过N1次加法。是满足下列条件的函数f：至少在在当前的计算水平之下是不能实现的。7560mod561=1这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。if bi=1a1+a2
4、+a3+aN-1Ua1MUa2(modM)=b2，由n的值求解（p，q）的值，即求解n的大整数分解n=pq，是一个公认的数学难题（虽然至今并没有证明），暂时还没有有效的算法。格中的任何其它向量都能唯一地表示为这几个向量的整数线性组合。Hellman1976提出，同时R.m(2,1)(modp)=p-mp；找到一个e满足ed1(mod z)。用RSA算法加密与解密的过程：例：明文=“RSA ALGORITHM”(1)明文用数字表示 空白=00，A=01,B=02,Z=26(两位十进制数表示)1819 0100 0112 0715 1809 2008 1300(2)利用加密变换公式 C=mPK m
5、od r,即C=18191223 mod 2867=2756PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223(mod 2867)=18191024 1819128 181964 18194 18192 18191(mod 2867)=27562756 2001 0542 0669 2347 0408 1815选择两个大素数p和q，通常要求每个均大于10100。u计算npq和z(p1)(q1)。u选择一与z互素的数、令其为d。u找到一个e满足ed1(mod z)。选好这些参数后，将明文划分成块，使得每个明文
6、报文P长度m满足0mn。加密P时，计算CPe(mod n)，解密C时计算PCd(mod n)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。为实现加密，需要公开(e,n)，为实现解密需要(d,n)。如何计算ab mod n？如何判定一个给定的整数是素数？如何找到足够大的素数p和q?要点1：(a x b)mod n=(a mod n)x(b mod n)mod n 要点2：a16=aaaaaaaaaaaaaaaa =a2,a4,a8,a16更一般性的问题：amm的二进制表示为bkbk-1b0,则 计算am mod nam mod n=a(2i)mod n =a(2i)mo
7、d nbi0bi0ikiibm207560mod561=1Miller and Rabin,WITNESS算法WITNESS(a,n)判定n 是否为素数，a是某个小于n的整数1.令bkbk-1b0 为(n-1)的二进制表示，2.d 13.for i k downto 04.do x d5.d (d d)mod n6.if d=1 and x 1 and x n-17.then return TRUE8.if bi=19.then d (d a)mod n10.if d 111.then return TRUE12.return FALSE 返回值：TRUE:n一定不是素数FALSE:n可能是素
8、数应用：随机选择a n,计算s次，如果每次都返回FALSE，则这时n是素数的概率为(1-1/2s)如何判定一个给定的整数是素数？(3)gcd(p1-1,q1-1)应该很小。格的最小向量问题(SVP)。为了抵抗现有的整数分解算法，对RSA模n的素因子最后，要判断哪一个根是真正的明文。注意到，寻找k满足akSak+1只需要对比N次。为了克服基本RSA的这个安全性漏洞，人们将基本RSA进行改造，引入Hash函数。=1024+128+64+4+2+1计算npq和z(p1)(q1)。(3)K为有限密钥空间，是一些可能密钥的有限集合；（密文c是背包重量，由n个物品重量b1，b2，b3，bn中的某些物品重量
9、相加而成。a1，a2，a3，an。基中的向量的个数称为格的维数。由于模运算的对称性，可以证明，then return TRUE选择两个正整数e和d，满足：此时加密密钥便称为公开密钥，记为Pk。加密P时，计算CPe(mod n)，解密C时计算PCd(mod n)。如何找到足够大的素数p和q?（2）在知道公开密钥和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文：CEKUb（M）x=(x1,x2,xN)，xi0,1，1.随机选一个奇数n(伪随机数发生器)2.随机选择一个整数a n3.执行概率素数判定测试,如果n 未测试通过,则 拒绝数值n,转向步骤14.如果n已通过足够的测试,则接
10、受n,否则转向步骤2;说明：随机选取大约用 ln(N)/2的次数，如ln(2200)/2=70 好在生成密钥对时才用到，慢一点还可忍受。确定素数p和q以后，只需选取e,满足gcd(e,(n)=1,计算d=e-1 mod (n)（扩展的欧拉算法）如何找到足够大的素数p和q?p和q在长度上应仅差几个数位，即p和q应是1075 到10100（p-1）和（q-1）都应包含一个较大的素数因子gcd(p-1,q-1)应比较小如果en 且 dn1/4,则d可以很容易确定建议RSA的数字签名应用真 若y=sig(x)假 若ySig(x)RSA的数字签名方案签名消息的加密传递问题 这个计算量称为亚指数计算量。最
11、后，要判断哪一个根是真正的明文。四、公钥密码Rabin传统加密算法无法实现抗抵赖的需求1819 0100 0112 0715 1809 2008 1300这一体制的出现在密码学史上是划时代的事件，它为解决计算机信息网中的安全提供了新的理论和技术基础。如何判定一个给定的整数是素数？C=18191223(mod 2867)Ronald Rivest随机选择a n,计算s次，要点2：a16=aaaaaaaaaaaaaaaa记为x=logg y mod p。签名消息的加密传递问题若已知变换课文C，又知道n个物品重量a1，a2，a3，an，求解明文m就是超递增背包问题。=m1a1+m2a2+m3a3+m
12、nan(modM)=1024+128+64+4+2+1当log2p1024时，亚指数计算量不小于2100数量级。4个根中有一个是明文m。为实现加密，需要公开(e,n)，为实现解密需要(d,n)。如何判定一个给定的整数是素数？了解非对称密码体制的提出背景、基本思想当格的维数比较大时（比如，维数大于200），当前的所有格归约算法都不是有效算法。攻击者Eve截获了密文c。（3）c=c2/c1(modn)，则c所对应的明文一定是m=m2/m1(modn)。执行概率素数判定测试,如果n 未测试通过,则 拒绝数值n,转向步骤1如果n已通过足够的测试,则接受n,否则转向步骤2;选取整数n=pq,M=A=Zn
13、Verk(x,y)=真 xye(mod n)最后，要判断哪一个根是真正的明文。then return TRUE公钥密码系统的应用类型随机选择a n,计算s次，另外两个根的和也等于n。为了抵抗现有的整数分解算法，对RSA模n的素因子这个漏洞还有更深刻的隐患，比如在消息认证过程中容易产生伪造。但是他不知道n的分解式n=pq，无法计算mp和mq，进一步无法计算4个根。(3)gcd(p1-1,q1-1)应该很小。另外两个根的和也等于n。如果w=0，则到（4）。C=18191223(mod 2867)选择两个大素数p和q，通常要求每个均大于10100。例：明文=“RSA ALGORITHM”).(mod);(mod4141qcmpcmpqpp
