密码技术（五、三）之公钥密码（RSA）

2019-03-30 本文已影响0人 Invincibled

RSA

RSA是使用最广泛的的公钥密码算法，它的名字是由它的三位开发者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母组成的。
RSA可以被用于公钥密码和数字签名。
1983年，RSA公司为RSA算法在美国取得了专利，现在专利已经过期。

RSA加密

在RSA中，明文、密钥和密文都是数字。RSA的加密过程可以用下列公司来表达：
密文 = 明文^E mod N （RSA加密）
也就是说，RSA的密文是对代表明文的数字的E次方求mod N的结果。换句话说，也就是明文和自己做E次乘法，就是这么简单。
加密公式中出现两个函数——E和N，到底是什么？RSA的加密时求明文的E次方mod N，因此只要知道E和N两个数，任何人都可以完成加密的运算。所以说，E和N是RSA加密的密钥，也就是说，E和N的组合就是公钥。通常表示为 “公钥是（E，N）”或是“公钥是{E,N}”。

RSA解密

RSA的解密公式如下：
明文=密文 ^D mod N (RSA解密)
也就是说，对表示密文的数字的D次方求mod N就可以得到明文。因此D和N的组合就是私钥。只有知道D和N两个数的人才能够完成解密运算。

RSA的加密和解密.png

生成密钥对

略，由于此部分涉及比较多数学知识，暂时省略，如需要，请参考原著。

对RSA攻击

略，由于此部分涉及比较多数学知识，暂时省略，如需要，请参考原著。

其他公钥密码

EIGamal方式
EIGamal方式是由Taher EIGamal设计公钥算法。RSA利用了质因数分解困难度，而EIGamal方式则利用mod N下求离散度数的困难度。EIGamal方式有一个缺点，就是经过加密的密文长度会变成明文的两倍。密码软件GnuPG中就支持这种方式。
Rabin方式
Rabin方式是由M.O.Rabin设计的公钥算法。Rabin方式利用了mod N下求平方根的困难度。上文中，我们提到了破解RSA有可能不需要通过对大整数N进行质因数分解，而破译Rabin方式公钥密码的困难度与质因数分解则是相当的，这一点已经得到了证明。
椭圆曲线密码
椭圆曲线密码*（Elliptic Curve Cryptography，ECC）是备受关注的一种密钥密码算法。它的特点是所需要的密钥的长度比RSA短。椭圆曲线密码是通过将椭圆曲线上的特定点进行特殊的乘法运算来实现的，它利用了这种乘法运算的逆运算非常困难这一特性。

关于公钥密码的Q&A

疑问：
公钥密码比对称密码的机密性更高吗？
回答：
这个问题无法回答，因为机密性的高低是根据密钥长度而变化。

疑问：
密钥长度为256比特的对称密码AES，与密钥长度为1024比特的公钥密码RSA相比，RSAd额安全性更高吗？
回答：
不是。
公钥密码的密钥长度不能直接与对称密码的密钥长度进行比较，而且对不同密码算法的强度进行比较本来就不是一件容易的事。
在强度相对均衡前提下，下图是一个对比，大家可以参考一下。

具备同等抵御暴力破解强度的密钥长度比较.png

疑问：
因为有了公钥密码，今后对称密码会消失吗?
回答：
不会。
一般来说，在采用具备同等机密性的密钥长度情况下，公钥密码的处理速度只有对称密码的几百分之一。因此，公钥密码并不适合用来对很长的消息内容进行加密。根据目的不同，还可能会配合使用对称密码和公钥密码。

疑问：
随着越来越多的人在不断生成RSA密钥对，质数会不会被用光呢？
回答：
不需要担心。
512比特能够容纳的质数的数量大约为10的150次方，这个数量比整个宇宙中原子的数量还要多。

疑问：
RSA加密过程中，需要对大整数进行质因数分解吗？
回答：
不需要。
RSA在加密、解密、密钥生成的过程中都不需要对大整数进行质数分解。只有在需要由数N求p和q的密码破译过程中菜需要对大整数进行质因数分解，因此RSA的设计是将质因数分解这种困难的问题留给了密码的破译者。

疑问：
RSA的破译与大整数的质因数分解是等价的么？
回答：
2004年Alexander May证明了求RSA的私钥和对N进行质因数分解是等价的。

疑问：
要抵御质因数分解，N的长度需要达到多少比特呢?
回答:
N无论有多长，总有一天都能够被质因数分解，因此现在的问题是，在现实的时间内N是否能够被质因数分解。随着计算机性能提高，对一定长度整数质因数分解所需要的时间会逐步缩短，如果大型组织或者国家投入其计算资源，则时间还会进一步缩短。
RSA Challenge（RSA公司所举办互动）到2007年就结束了，有公开记录的被成功分解的最长的RSA数为RSA-768。
随着计算机技术进步等，以前认为是安全的密码会被破译，这一现象称为密码劣化 。针对这一点，NIST SP800-57中给出了如下方针。

1024比特的RSA不应该被用于新的用途
2048比特的RSA可在2030年之前被用于新用途
4096比特的RSA在2031年之后仍可被用于新的用途

该系列的主要内容来自《图解密码技术第三版》
我只是知识的搬运工
文章中的插图来源于原著