1.Introduction
最近读论文刚好用到了这个, 之前只是有耳闻, 没有仔细研究过, 这里就好好捋一下, 会逐步完善
不过貌似 CRT(中国剩余定理)的实现更容易被攻击
2. RSA: Overview
rsa 算法描述如下:
选择两个大素数 \(p,q\), 计算 \(N = p*q\)(最好保证 N 在 2048bit 以上, 最新的研究工作已经可以成功分解 762bit 的 N)
计算 \(\phi(N)=(p-1)*(q-1)\)
选择一个 \(e\)使得 \(gcd(e, \phi(n)) == 1\),e 由于是作加密使用, 故推荐使用小值, 推荐使用 3,65537(\(2^{16}+1\)),65537 只有两个 1bit, 所以在幂运算 (参加我的另一篇博客: 快速指数算法) 时只需要两次额外的乘法运算; 此外, 不需要担心使用固定值会造成的安全问题, RSA 的安全性不会受影响
计算 \(ed = 1 (\mod\phi(n))\), 得到 \(d\)值用于解密
公钥:(N, e), 私钥:(N, d)
一次 RSA 加解密:
\[c = m^e \mod N\\ m = d^d \mod N\\ \]
解释:
即 \(m = (m^e)^d = m^{1\mod\phi(N)}=m^{h*\phi(N)+1}\mod N\),
由欧拉定理 \(a^{\phi(n)}=1 \mod n\), 得到前式等价于
- \(1^h*m^1 = m\)
- 3. Using CRT
3.1 中国剩余定理
描述起来比较麻烦, 见中国剩余定理, 可以把大模数变小模数
3.2 在 RSA 中使用 CRT
RSA 中计算耗时最大的地方是解密的 \(c^d\)操作, 由于 d 值往往较大, 故计算难度较高, 可以使用中国剩余定理适当降低计算量.
计算私钥
下面几部分会被预计算并存入私钥:
- \(p,q\)
- \(dp = d \mod {
- p-1
- }\)
- \(dq = d \mod {
- q-1
- }\)
- \(q_{
- inv
- } = q^{
- -1
- } \mod p\)
这样最后的私钥就是 \((p,q,d,dp,dq,q_{inv})\)
解密
- \(m_1 = c^{
- dp
- } \mod p\)
- \(m_2 = c^{
- dq
- } \mod q\)
- \(h = q_{
- inv
- }(m_1-m_2)\mod p\)
当 \(m_1<m_2\)时, 有些实现会这样计算 \(h = q_{inv}[(m_1+\lceil{\frac{q}{p}}\rceil p)-m_2]\mod p\)
\(m = m_2+hq \mod {p*q}\)
这样做虽然要计算两次模幂, 但效率依然要比直接计算高得多. 因为不管是指数还是模数都要小得多
4. 列几个常见的算法库
- Bouncy Castle
- cryptlib https://en.wikipedia.org/wiki/Cryptlib
- Crypto++ https://en.wikipedia.org/wiki/Crypto++
- https://en.wikipedia.org/wiki/Libgcrypt
- https://en.wikipedia.org/wiki/OpenSSL
- https://en.wikipedia.org/wiki/WolfSSL#wolfCrypt
- https://en.wikipedia.org/wiki/GnuTLS
- mbed TLS https://en.wikipedia.org/wiki/Mbed_TLS
- https://en.wikipedia.org/wiki/LibreSSL
- 5 Reference
- RSA (cryptosystem) https://en.wikipedia.org/wiki/RSA_(cryptosystem)
来源: https://www.cnblogs.com/chuaner/p/13251743.html