|
RSA算法是非对称算法,由Ronald Rivest、Adi Shamir、Leonard Adleman三人共同在1977年公开发表。在RSA加密算法中,公钥和私钥都可以用于加密消息,用于加密消息的密钥与用于解密消息的密钥相反。RSA算法提供了一种保护网络通信和数据存储的机密性、完整性、真实性和不可否认性的方法。目前,SSH、OpenPGP、S/MIME和SSL/TLS都依赖于RSA进行加密和数字签名功能。RSA算法在浏览器中使用,能够在不可信任的互联网中建立安全连接。RSA签名验证是网络连接系统中最常见的执行操作之一。
|
|
|
RSA算法基于大整数因子分解的困难性,该算法的步骤如下:
|
|
|
|
|
第三步,计算小于n并且与n互素的整数的个数,即欧拉函数φ(n)=(p-1)(q-1)。
|
|
|
第四步,选取一个随机数e,且满足1<e<φ(n),并且e和φ(n)互素,即gcd(e,φ(n))=1。
|
|
|
|
第六步,保密d、p和q,而公开n和e,即d作为私钥,而n和e作为公钥。
|
|
|
下面,举一个RSA加密的具体实例。设素数p=3,q=17,并令e=13,则RSA的加密操作如下:
|
|
|
第一步,计算n,n=pq=3×17=51,得出公钥n=51,e=13。
|
|
|
第二步,计算φ(n)和d,φ(n)=(p-1)(q-1)=2×16=32。因为d=e-1modφ(n),所以,其中k是p-1和q-1的最大公约数。由此算出d=(2×32+1)/13=5,即解密密钥d=5。
|
|
|
第三步,加密和解密处理计算。假设Bob的公开密钥是e=13、n=51,Alice需要将明文“2”发送给Bob,则Alice首先用Bob的公开密钥加密明文,即:
|
|
|
C=Memodn=213mod 51=8192 mod 51=32
|
|
|
然后,Bob收到Alice发来的密文C后,用自己的私钥d解密密文C,即:
|
|
|
M=Cdmodn=325mod 51=1024×1024×32 mod 51=512 mod 51=2
|
|
|
RSA安全性保证要做到选取的素数p和q足够大,使得给定了它们的乘积n后,在事先不知道p或q的情况下分解n是计算上不可行的。因此,破译RSA密码体制基本上等价于分解n。基于安全性考虑,要求n长度至少应为1024比特,然而从长期的安全性来看,n的长度至少应为2048比特,或者是616位的十进制数。
|
|
|