RSA公钥密码算法.ppt

RSA的安全性 RSA的安全性是基于分解大整数的困难性假定 如果分解n=p×q，则立即获得?(n)=(p－1)(q－1)，从而能够确定e的模?(n)乘法逆d，即： d=e-1 mod ?(n) 只要能对n进行因子分解，便可攻破RSA算法。 破解RSA密码的困难性大于等于对n进行因子分解的困难性。 RSA-129的故事 Mirtin Gardner在1977年“Scientific American”的专栏文章中介绍了RSA码。为了显示这一技术的威力，RSA公司的研究人员用一个129位的数n 和一个4位数e 对一个关于秃鹰的消息作了编码。Gardner刊登了那个密文，同时给出了n 和e。RSA公司还悬赏100美元，奖给第一个破译这密码的人。 96869 61375 46220 61477 14092 22543 55882 90575 99911 24574 31987 46951 20930 81629 82251 45708 35693 14766 22883 98962 80133 91990 55182 99451 57815 154 17年之后，一批松散组成的因子分解迷，大约有600多人，分布在二十几个国家。他们经过八个月的努力最后于1994年4月为RSA-129找到了64位数和65位数两个素数因子。 11438 16257 57888 86766 92357 79976 14661 20102 18296 72124 23625 62561 84293 57069 35245 73389 78305 97123 56395 87050 58989 07514 75992 90026 87954 3541 = 34905 29510 84765 09491 47849 61990 38981 33417 76463 84933 87843 99082 0577 * 32769 13299 32667 09549 96198 81908 34461 41317 76429 67992 94253 97982 88533 “The magic words are squeamish ossifrage” 来自两个方面的威胁 人类计算能力的不断提高 分解算法的进一步改进。1996年RSA-130被破译，1999年破译了RSA-140，同年， RSA-155被破解，2005年， RSA-200被破解。 将来也可能还有更好的分解算法，因此在使用RSA算法时，整数n的大小要足够大，n至少应该是1024位，最好是2048位。 对其密钥的选取要特别注意其大小。估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。 几个建议 为了防止可以很容易地分解n，RSA算法的发明者建议p和q还应满足下列限制条件： P和q的长度应仅相差几位。对于1024位的密钥而言，p和q都应在1075到10100之间。 (p-1)和(q-1)都应有一个大的素因子。 Gcd(p-1,q-1)应该较小。 其它公钥密码算法 ElGamal密码 ElGamal密码是由ElGamal于1985年提出。该密码系统可应用于加/解密、数字签名等，其安全性是建立于离散对数(discrete logarithm)问题之上的，即给定g，p与y=gx mod p，求x在计算上不可行。 椭圆曲线密码体制(ECC) 椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。椭圆曲线在代数学和几何学上已经广泛研究了150多年之久，有丰富而深厚的理论积累。 学习是一件快乐的事情! 06 RSA算法 （RSA Algorithm） 主要内容 公钥密码体制的产生 数论基础 公钥密码体制的基本原理 RSA公钥密码体制 其它公钥密码算法 费马小定理 (Fermat) 如果p是一个素数,a不是p的倍数， 则：ap-1≡1 (mod p) 假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1 例：p=3，a=14，则有143-1≡1 (mod 3) 欧拉函数 Ф(n)：小于n且与n互素的正整数的个数 显然，对于素数p，有Ф(p)=p-1 定理：设有两个素数p和q，p ≠q，那么对于n=pq，有： Ф(n)= Ф(pq)= Ф(p)* Ф(q)=(p-1)*(q-1) Ф(15)= Ф(3*5) = Ф(3)* Ф(5) =(3-1)*(5-1) =8 欧拉定理(Euler) 对于任意互素的a和n，有