第4章 復号の可能性とフェルマーの小定理

 

第1章の例では234を(キー5で)暗号化すると155になりました。第2章の例では155を(キー5で)復号化すると342になりました。

つまり第2章のような復号化では元の通信文234は復元できないのです。

実は暗号化と復号のキーを5ではなく19を選ぶとうまく復元できます。

234を19乗するのはなかなか大変なことですが

23419=((234)×234×234

≡ 155×218×218 ≡ 232×218×218

≡ 345 (mod 407)

つまり暗号文は345になります。

次に複号化は

34519=(345×(345×345

≡ 174×174×345

≡ 137×158×345

≡ 234 (mod 407)

となり、めでたく元の文234が復元されました。

このことは発信側と受信側が共通のキー(暗証番号のようなもの)

である19を知っていれば、同じ手順で暗号化も復号化もできる、という

ことになります。

なぜこのように元の通信文が復元できるのでしょうか?

これは、 19×19≡1 (mod 360)がいえること、および

フェルマーの小定理を使えば証明できます。なお407は二つの素数

11と37の積であり、360は(11―1)×(37―1)である

ことがポイントになっています。次は元の文Mが復元できることの

証明ですが、意欲のある人は読んでください。

――――――――

「p,q を素数とし(p≠q)、E×D≡1 (mod (p-1) (q-1))ならば

任意の M に対し、 (ME)D≡M (mod pq)」 となる。

(証明)

E×D≡1 (mod (p-1)(q-1)) …(1)

を仮定。

(1) より

(ME)D-M = ME×D-M = M(1+k(p-1)(q-1))-M

= M(Mk (p-1)(q-1)-1) … (2)

ここで M と q が互いに素なら Mk(p-1)(q-1) と q も互いに素。

よってフェルマーの小定理より Mk(p-1)(q-1)-1 = nq (qの倍数)。

よって (2) 式 = Mnq。 よって(2)は q で割り切れる。

また M と q が互いに素でなければ M は q の倍数。よって

やはり (2) は q の倍数。

同様にして (2) は p の倍数でもある。よって (2) は pq の倍数。

よって

(ME)D ≡ M (mod pq)

Back