RSA加密之早期攻击

• 对于目前的RSA加密来说，只介绍一些正常的RSA加密题型，而不会详细归纳RSA加密中考察某个数论知识点的题目。（当然如果是leak类型的题目还是会归纳的，但是如果是单单考察一个求$\phi(n)$的公式，那我觉得没什么必要）
• 接下来就介绍一下针对RSA加密的早期攻击方式，以便后续的RSA加密的学习。接下来就先来了解一下RSA加密的早期攻击：对于RSA加密早期的攻击，本篇博客中主要学习的是共模攻击、循环攻击、共明文攻击，对于相关明文攻击个人认为篇幅比较多，所以单开一篇博客进行论文的细读，进行学习。

共模攻击

• 共模攻击英文全称为Common Modulus Attack，出现该攻击的原因是由于一个早期提出的密码学协议共模协议，该协议的具体内容为：

  • 由一个密钥机构（即可信第三方）生成一个RSA模数，并向系统内的用户分发使用同一模数的和法密钥对。
  • 在该协议中，用户的私钥仅为$(d,N)$，因此用户并不知道模数$N$的因数分解即不知道$(p,q)$的值。
  • 该方案的初衷是只有中央密钥机构掌握该公共模数的分解信息。

• 在1983年，Simmons在这篇文章A "weak" privacy protocol using the RSA crypto algorithm. 指出，当同一明文使用具有相同模数且公钥指数互素的两个不同公钥进行加密时，会存在协议失效的问题。接下来具体说明一下：

  • 给定两个密文$c_1,c_2$，以及两个公钥对$(e_1,n)，(e_2,n)$，其中公钥对中$(e_1,e_2)=1$。Simmons证明了在这种已知条件下，可以很容易地计算出原始明文。
  • 由于$(e_1,e_2)$互素，那么我们就可以轻易地求出整数$a_1$和$a_2$，$a_1e_1+a_2e_2=1$（可以由裴蜀定理得到该式子）
  • 对于任意明文$m$，给定的$c_1=m^{e_1}~mod(~N),c_2=m^{e_2}~mod(~N)$，只需要计算$c_1^{a_1}*c_2^{a_2}~mod(~N)$，即可得到明文。
  • 因为在$Z_N$中有：$c_{1}^{a_1}*c_{2}^{a_2}=m^{a_1e_1}*m^{a_2e_2}=m^{a_1e_1+a_2e_2}=m~mod(~N)$
  • 这类攻击可以由任何能够获取公钥并且观察到这两个密文的人实施

• 在1984年，DeLaurentis在这篇文章A further weakness in the common modulus protocolfor the RSA cryptoalgorithm证明了共模协议是完全不安全的。他指出只要掌握任意一组公钥—私钥对，就足以计算出在相同模数下对应与任何其他公钥的有效私钥，具体定理如下：

  • 设$(e,N)$是一个有效的RSA公钥，其私钥对应的是$(d,N)$；设$(e_1,N)$是另一个有效的公钥，并且满足$e_1≠e$。

  • 在已知$(e,d,N,e_1)$的情况下，公钥$(e_1,N)$对应有效的解密指数$d_1$能在关于$log(N)$的多项式时间内计算得到。

  • $d_1$的计算公式如下：$d_1=e_1^{-1}~mod(~\frac{ed-1}{gcd(e_1,ed-1)})$

  • 证明如下：

    • 由于$\phi(N)$是$\lambda(N)$的倍数，所以密钥等式就可以写成$ed-1=k\lambda(N)$，$k$是一个正整数。
    • 对于有效的公钥指数$e_1$，必须满足$gcd(e_1,\lambda(N))=1$，因此就有$gcd(e_1,k\lambda(N))=gcd(e_1,k)=k'$，也就有$k'|k$。
    • 设$\tilde{k}=\frac{k}{k'}≥1$，所以就有$\frac{ed-1}{gcd(e_1,ed-1)}=\frac{k\lambda(N)}{k'}=\tilde{k}\lambda(N)$。
    • 因此对于私钥指数$d_1$就满足$e_1d_1=1+k_1(\tilde{k}\lambda(N))$，其中$k_1$是正整数。
    • 因此就有$e_1d_1\equiv1~(~mod~\lambda(N))$，所以$d_1$是公钥$(e_1,N)$的一个有效私钥指数。
    • 所以可以在关于$log(N)$的多项式时间内计算得到$d_1$

  • 此外DeLaurentis利用一个归因与Simmons的思想证明了：在已知单个公钥-私钥对的情况下，可以使用概率多项式时间的Las Vegas算法对模数进行分解（Las Vegas算法是结果一定正确，只是运行时间是随机的随机算法）。在给定$e$和$d$的条件下，只需要计算$\phi(N)$的一个倍数，即$ed-1=k\phi(N)$，然后应用Miller的结论（该结论就是在已知$\phi(N)$的某个倍数时，可以以概率方式分解$N$），因此共模协议不安全。

广播攻击

• 另一个出现协议失效的情况就是几个相关的明文消息被小公钥指数和不同的模数加密。同样的，对这个失效的协议攻击经常指的是Håstad's Broadcast attack，也就是Håstad广播攻击。该攻击分为两类，一类就是共明文攻击，另一类就是消息相关攻击。
• 这里主要介绍共明文攻击，该协议失效是出现在相同的明文$m$被几个公钥$(e,N_i)$加密，每个公钥都有相同的公钥指数$e$和不同的模数$N_i$。这个协议失效的攻击在1985年由Håstad发表的两篇文章On using RSA with low exponent in a public key network和Solving simultaneous modular equations of low degree
• 该攻击的具体定理如下：
  • 设$(e,N_1),...,(e,N_l),l≥e$，这些公钥对都是有效的RSA公钥，其中模数$N_i,i=1,...,l$两两互素
  • 设$N_0=min\{N_1,...,N_l\}$，$N=\Pi^{l}_{i=1}N_i$
  • 对于任何一个消息$m<N_0$，给定$c_i=m^e~mod~(~N_i)$和$(e,N_i),i=1,...,l$，明文$m$是能在关于$log(N)$的多项式时间内计算出来的。
  • 证明如下：
    • 由于模数$N_1,...,N_l$两两互素，由中国剩余定理可以用$c_i$和$N_i$得到$C\equiv m^e~mod(~N)$。
    • 因为$m<N_0$，这就使得$m^e<N_1N_2...N_l=N$，因此$C=m^e$。
    • 在整数范围内计算$C=m^e$的e次方根，即可得到明文$m$，由于所有计算都可以在关于$log(N)$的多项式时间内完成，因此结论成立。

循环攻击

• 循环攻击，英文名称为Cycling Attacks，

总结

共模攻击

• 关于协议错误如果还要拓展，可以参见：

  • Moore写的Protocol failures in cryptosystems. Proceedings of the IEEE
  • Simmons写的An RSA-related number-theoretic surprise. In Computer Systems Theory, Technology, and Applications,Monographs in Computer Science, chapter 39, pages 269–271. Springer New York, 2004

• 共模协议在早期曾被反复提出，是一种较早且多此出现的方案，但最终证明是完全不安全的。例如在下面论文中提到这种类型的协议曾被多次重新发明

  • DeLaurentis所写的A further weakness in the common modulus protocol for the RSA cryptoalgorithm
  • Håstad所写的On using RSA with low exponent in a public key network. In H. C. Williams, editor, CRYPTO, volume 218 of Lecture Notes in Computer Science, pages 403–408. Springer, 1985
  • Moore写的Protocol failures in cryptosystems. Proceedings of the IEEE

• 在已知RSA公钥和私钥指数的情况下，对RSA模数进行分解的确定性多项式时间算法，直到在发现概率型多项式时间算法二十多年之后才被找到。这种确定性方法利用了Coppersmith的小根方法来求解二元整数方程的小根，最早由May于2004年提出，随后又被Coron和May进一步改进。

  • May所写的Computing the RSA secret key is deterministic polynomial timeequivalent to factoring. In M. K. Franklin, editor, CRYPTO, volume3152 of Lecture Notes in Computer Science, pages 213–219. Springer,2004.
  • Coron 和 May所写的Deterministic polynomial-time equivalence ofcomputing the RSA secret key and factoring. *Journal of Cryptology*,20(1):39–50, 2007.

共明文攻击

循环攻击