RSA 靠著質數打天下，但也不是這麼的萬能。當遇到挑選的質數「不夠亂」的狀況的時候，就有機會被以 Common Factor 的方式攻擊。
假想有兩隻 public key pub1 跟 pub2，他們各有質數 p1, q1, p2, q2，當今天選擇的質數夠亂，我們會有下面類似的狀況：
n1 = 1809632459 × 2402636221 = 4347888492690697439
n2 = 1488286753 × 1800980219 = 2680375002352738907
對這兩個質數取 gcd，則會得到 1 這個結果：
gcd(4347888492690697439, 2680375002352738907) = 1
但是，當今天挑選質數的時候，恰恰好的，選擇到了相同的質數呢？
n1 = 1809632459 × 1488286753 = 2693252016528515627
n2 = 1488286753 × 1800980219 = 2680375002352738907
RSA 的漏洞便出現了，我們可以輕易的透過 gcd 取得公約數，也就是那個相同的質數：
gcd(2693252016528515627, 2680375002352738907) = 1488286753
Bingo! 我們取得了兩把 key 的其中一個質數，這代表著我們可以藉由已知的 n，已知的 p，推算出 q，因此就能夠復原出兩把 public key 的 private key！
了解更多
我在實驗室的 GitLab 上放置了一個可供把玩的 Python script，可以將以上的步驟自動化執行，從一群 key 中挑選出有 common factor 的 public key 並且復原出 private key。Repo 中有給定的題目敘述以及 12 把 public key，請參考：http://gitlab.nems.cs.nctu.edu.tw/louielu/ns-p1
英文版的 technical report 放置於 mlouielu/nctu-techreport。
References
[1] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital
signatures and public-key cryptosystems,” Communications of the ACM,
vol. 21, no. 2, pp. 120–126, 1978.
[2] R. L. Rivest and B. Kaliski, “Rsa problem,” in Encyclopedia of cryptography
and security. Springer, 2005, pp. 532–536.
[3] S. Shoen, “Understanding common factor attacks:an rsa-cracking puzzle.”
[Online]. Available: http://www.loyalty.org/ schoen/rsa/
[4] “The openssl project: open source toolkit for ttl/stl.” [Online]. Available:
https://www.openssl.org
[5] “python-rsa: Python-rsa is a pure-python rsa implementation.” [Online].
Available: https://stuvel.eu/rsa
[6] L. Louie,
“Network security project 1.”
http://gitlab.nems.cs.nctu.edu.tw/louielu/ns-p1
Leave a Reply