-
φ （ファイ）を解くことでトラップドアが得られます。
-
N の因数分解ができれば、φ(N) は簡単に見つかります。
-
たとえば 77 は 7×11 と素因数分解できます。
-
このため φ(77) = 6×10 となり、60 になります。
-
ステップ3: φ 関数を冪乗余に結び付ける方法は
どうなるでしょう?
-
このため彼はオイラーの定理を調べて、
-
次のようなφ 関数と冪乗余の関係を理解しました。
-
m の φ(n) 乗を n で割ると余りは 1 になります。
-
たとえば、共通因数のない、2 つの数を選びます。
-
この2数を n, m とします。
-
m=5、n=8 とします。
-
ここで m を φ(n)、つまり 4 で冪乗し、n で割ります。
-
こうすると余りは常に 1 になります。
-
ここで、この等式を 2 つの単純な規則で変形します。
-
【1】 数 1 を任意の指数 k で冪乗すると、
答は常に 1 になります。
-
同様に、指数 φ(a) を任意の数 k で掛算しても
答は 1 になります。
-
【2】 数 1 を任意の数 m で掛算すると、
答は常に m になります。
-
同様に、左辺を m で掛算すると、右辺は m になります。
-
そして、これは、m の k × φ(n) + 1 乗と単純化できます。
-
これがブレークスルーです。
-
これで φ(n) を使って e×d を求める等式が得られました。
-
このため、d を求めるのは簡単です。
-
ただし n の因数を知らない人には不可能です。
-
つまり、d をアリスの秘密鍵すべきです。トラップドアです。
-
これを使えば e の暗号化効果を打ち消すことができます。
-
これらがどう機能するか、簡単な例で見てみましょう。
-
例えばボブは、空いている桁も埋めてメッセージを数値に
変換します。
-
これをmと呼びましょう。
-
アリスは次のように、自分の公開鍵と秘密鍵を作ります。
-
まずアリスはよく似た大きさの 2 つの素数乱数を作り、
-
それらを掛算して n を得ます。この場合 3127 です。
-
それから、アリスは φ(n) を計算します。
-
n の因数分解が分かっているので簡単です。
-
これは 3016 になります。
-
次にアリスは小さな公開指数 e を選びます。
-
条件は、これが奇数であり、
Φ(n) と共通因数を持たないことです。
-
この場合 e に 3 を選びます。
-
最後に自分の秘密指数 d を計算します。
-
この場合 (2 × φ(n ) + 1) / 3 で 2011 になります。
-
ここで、彼女は n と e の値以外は隠します。
-
これは n と e が公開鍵だからです。
-
これらは閉じていない錠と見なせます。
-
これらをボブに送り、ボブがメッセージに錠を掛けるように指示します。
-
ボブは自分のメッセージ m の e 乗を n で割った余りを計算することで、
-
メッセージに鍵を掛けます。
-
この値、つまり暗号化されたメッセージを c と呼びましょう。
-
これをボブはアリスに送ります。
-
最後にアリスは自分のトラップドアを通じてアクセスできる秘密鍵 d を使って、
-
ボブのメッセージを、復号します。
-
c を d 乗してから n で割り算して余りを求めると、
-
ボブのメッセージ m が復号されます。
-
イブたち部外者はたとえ c、n、e を盗み見ても、
-
d を計算するのは困難です。
-
イブたちは φ(n) を計算する必要がありますが、
-
それには n の素因数分解が必要です。
-
n が十分に大きければ、
-
最強のコンピュータネットワークを使っても数百年かかります。
-
この手法は、発表後すぐに機密にされました。
-
しかし、1977 年に Rivest、Shamir、Adleman によって
再発見されました。
-
このため、この手法は、彼らの頭文字を使って
RSA 暗号と呼ばれています。
-
RSA は世界でもっとも普及している
公開鍵アルゴリズムになっています。
-
そして歴史上もっとも多く出回っている
ソフトウェアでもあります。
-
地球上のインターネットユーザーは全員、意識しようとしまいと、
-
RSAまたはその変種を使用しています。
-
その強度は、素因数分解の難しさにかかっています。
-
それは、素数の分布に関する奥の深い問題の結果です。
-
この問題は、数千年たってもまだ未解決のままです。
