RSA Common Factor Attacks

RSA 靠著質數打天下,但也不是這麼的萬能。當遇到挑選的質數「不夠亂」的狀況的時候,就有機會被以 Common Factor 的方式攻擊。

假想有兩隻 public key pub1pub2,他們各有質數 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

如果你覺得這篇文章不錯,歡迎打賞 IOTA:MUYIDBBJZHJMSTMQZGHUSSGCKBBKRDKHQRNMLZONXPFYWSBCFOKEYOHBYFZKLVVFDTG9AOSZCBPUDWGTBNXYUDTDOD

Leave a reply:

Your email address will not be published.