Tag: rsa

  • RSA Common Factor Attacks

    RSA Common Factor Attacks

    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…