RSA-4

公開鍵暗号

（４）RSAの原理

RSA暗号は、公開鍵暗号の一つの具体的な方法としてRivest, ShamirとAdlemanにより1978年に開発されました。

原理

平文を、以下のnより小さい自然数の列に符号化します。平文の各ブロック（nより小さい自然数）をＭ、その暗号文をＣとします。

・暗号化鍵：(e, n)，復号化鍵：(d, n)．
　n=pq（２つの素数の積）．
　ed≡1 mod LCM(p-1, q-1)．
・暗号化アルゴリズム
　C≡M^emod n．
・復号化アルゴリズム
　M≡C^dmod n．

このとき、(n, e)が公開鍵、dが秘密鍵です。

実際にこの復号化アルゴリズムが、暗号化アルゴリズムの逆関数になっていることは、オイラーの定理よりわかります。

安全性

nとrが公開されているので、dはもちろん計算可能です。しかし、計算するにはnを素因数分解する必要があります。nを直接素因数分解することなしにRSA暗号を解読する方法もありますが、nの素因数分解以下の時間でできるものは発見されていないようです。

大きな数の素因数分解は、これまでに知られている計算方法では膨大な時間がかかります。今後も画期的にその時間を縮めることは難しいと思われています。それがRSA暗号の安全性の根拠です。

「世界中の正直な数学者（素因数分解のエキスパート）達を出し抜くような、悪人はたぶんいないだろう」、あるいは「そんなすごい方法をみつけるような人は、その方法で人の暗号を解読するより、発表して名声を手に入れる方を選ぶだろう」という楽観論という見方もできます。異星人でもあらわれない限りたぶんそうでしょう（＾＾；）

例解RSA