公開鍵暗号方式は、暗号化に使う鍵(公開鍵)と復号に使う鍵(秘密鍵)が別々で、公開鍵は人に配っても安全だという暗号方式です。安全性の根拠にしているのは、計算量の面で「実質的に解けない」数学の問題で、方式ごとに異なります。
RSAは、大きな2つの素数の積を、もとの素数に分けること(素因数分解)が非常に難しいことを根拠にしています。例えば、7 × 11 = 77 は簡単ですが、数百桁の整数を素因数に分けるのは、現実的な時間ではできません。
解説
公開鍵暗号方式は、暗号化に使う鍵(公開鍵)と復号に使う鍵(秘密鍵)が別々で、公開鍵は人に配っても安全だという暗号方式です。安全性の根拠にしているのは、計算量の面で「実質的に解けない」数学の問題で、方式ごとに異なります。
RSAは、大きな2つの素数の積を、もとの素数に分けること(素因数分解)が非常に難しいことを根拠にしています。例えば、7 × 11 = 77 は簡単ですが、数百桁の整数を素因数に分けるのは、現実的な時間ではできません。