公開鍵暗号方式、RSA、公開鍵、秘密鍵
奇妙なことですが,ドアを閉める鍵と開く鍵が全く異なる鍵にすることができる数学的な方法(後述のRSA)が確立しました。
ドアを閉めるのは誰に閉められても困りませんから,その鍵は公開してもかまいません。これを公開鍵といいます。一方、ドアを開く鍵は自分だけが持っていて他人には秘密にする必要があります。これを秘密鍵といいます。
鍵といっても物理的な鍵ではなく、1024ビット(方式により異なる)のビット列です。10進数にすれば数百桁になります。
このような方式を公開鍵暗号方式といいます。どのように暗号鍵と公開鍵を作るのかは省略しますが、公開鍵暗号方式は共通鍵暗号方式がもつ「鍵の送付」「鍵の管理」の欠点を解決できます。
公開鍵暗号方式で送信者Aが受信者Bに暗号文を送るときには、次のようになります。
・送信者は、Bの公開鍵で電文を暗号化する。
Bの公開鍵は公開してある。
それで、誰でもBに暗号文を送ることができる。
・受信者BはBの秘密鍵で復号する。
Bの秘密鍵は、Bだけがもっている。
第三者が電文を見ても、復号できない。
公開鍵暗号方式は、共通鍵暗号方式の欠点である「鍵の送付」「鍵の管理」を解決しています。
しかし、共通鍵暗号方式にくらべて暗号化や復号に時間がかかる欠点があります。長文を対象にするのは適していません。それで実際には、この二つの方式を巧みに組み合わせた方式が広く使われています(→ ハイブリッド暗号方式)。
公開鍵暗号方式の代表的なものにRSA(Rivest Shamir Adleman:開発者3人の名前)があります。
RSAは,「素数と素数の掛け算は簡単だが、その逆の素因数分解は難しい」という数学的な一方向性に基づいています。数百桁にもなる素数の積を素因数分解をするには膨大な計算が必要で、現在のコンピュータを使って現実的な時間内に答えを出すことは不可能です(参照:「公開鍵暗号方式の原理」)。
暗号理論は、アルゴリズムの計算量にコンピュータ性能が追い付かないことに基づいています。鍵の長さ(ビット数)を大にすれば計算量は増大しますが、理論的には同じことです。
近年量子コンピュータが実用化されようとしています。これが発展すると現在のコンピュータが数百年かかる計算を数秒で計算してしまうといわれ,現在の公開鍵暗号方式が役立たなくなるともいわれています。