RSA暗号 その2

解決策は、別のイギリス人数学者 兼 暗号研究家である
クリフォード・コックスが発見しました。

コックスは、トラップドア 一方向関数と呼ばれる、
特殊な 一方向関数の発見を目指していました。

これは、1つの方向では計算が簡単だが、
トラップドアと呼ばれる特殊な情報がないかぎり、

逆方向の計算は難しい関数です。

このために、彼は「べき剰余」、つまり
「べき乗」の剰余に目をつけました。

これは、すでにディファー=ヘルマン鍵交換の中で時計演算
として説明していますが、次のようになります。

ある数を何らかの指数でべき乗します。

それから「法」で割り算して、
余り（剰余）を出力するのです。

この方法を使用して、
メッセージを次のように暗号化します。

ボブにメッセージがあり、それが数字 m に
変換されるとします。

ボブはこの数を e 乗します。
ここで e は公開された指数です。

それからボブは結果を乱数 N で割り、
この割り算の余りを出力します。

こうしてある数 c が生まれます。

この計算の実行は簡単です。

しかし c 、e、N だけが分かっても、m がどんな数で
あったか、突き止めるのはとても困難です。

それは何らかの試行錯誤に頼るしかないからです。

このためこれは1方向関数で、m に簡単に適用できるが、
逆は困難です。これが数学的なロックです。

ここで、鍵はどうでしょうか?

鍵はトラップドアです。これは簡単に暗号化を解除できる、
ある種の情報です。

c を、次の条件を満たす指数 d でべき乗します。

m に適用された当初の処理が打ち消され、
元のメッセージ m が復元されるようにします。

どちらの演算も同じです。m を e でべき乗してから
d でべき乗しています。

これは、m を e X d でべき乗するのと同じです。

e を暗号化に使い、d を復号に使います。

このため、e と d の生成方法を知る必要があります。
しかも他人には d が分からないように。

これには、d を生成するための
第二の1方向関数が必要であり、

この作業のために、
彼はユークリッドの業績を見直しました。