為什麼有效的整數分解算法會使 RSA 不安全？
我知道 RSA 依賴於整數分解問題：給定兩個素數 p 和 q，它們的乘積 p 。q 很容易計算。但不可行（即多項式時間）已知一種算法可以分解任意乘積 pq
為什麼有效的整數分解算法會使 RSA 不安全？
我知道 RSA 依賴於整數分解問題：給定兩個素數 $ p $ 和 $ q $ , 他們的產品 $ p . q $ 很容易計算。但不可行（即多項式時間）已知一種算法可以分解任意乘積 $ p.q $ .
因此，素數的乘法 $ p.q $ 被認為是單向函式。讓 $ e,m $ 為正整數。
讓我們定義 $ f:z_m \rightarrow z_m $ 經過 $ f(x):= x^e \mod m $
$ f(x) $ 可以使用平方和乘法算法有效地計算，另一方面，求解 $ y=x^e \bmod m $ 為了 $ x $ （即計算 $ e $ - 的根 $ y $ 模組 $ m $ ) 被認為很難。這就是 RSA 問題。因此，模冪運算被認為是一種單向函式。
此外，RSA Key Generation 給了我們提示
1）選擇兩個大的不同質數 $ p $ 和 $ q $ .
2)計算 $ m = p.q $
$ φ= (p-1)(q-1) $
選擇一個整數 e 使得 $ 1<e<φ $ 和 $ \operatorname{gcd}(e,φ) =1 $
5)計算 $ d=e^{-1} \bmod φ $ . （擴展算法計算 $ gcd(e,φ) $ 和 $ d $ .
6）發布 $ m $ 和 $ e $ 保持 $ d $ 私人的。
整數分解問題和 RSA 問題在計算上是困難的。多項式時間量子因式分解問題是已知的。為了防止明文攻擊和其他攻擊，RSA 在實踐中採用了消息的隨機填充。
已知對 RSA 實現的側通道攻擊可以確定私鑰，例如 $ d $ 和 $ m $ . RSA 的密鑰大小是指模數的位大小。蠻力攻擊是可能的（原則上），但不是必需的：攻擊者可以嘗試分解模數。