2007年1月21日日曜日

公開鍵暗号(RSA)をわかる3

続き

前回まで7で割った余りを考えていたが,暗号で使うには7ではなく,「2つの素数の積」で割った余りの世界を考える.
つまり 10=2×5 とか 15=3×5 とか.
ところが,実際に RSA を考えると,33=3×11 程度に大きくしないと実験ができない.

ここからは 33 で割った余りで考える.33で割った余りなので,余りの種類は,
 0,1,2,3,…,31,32
の33種類である.これらの累乗を考える.

たとえば 25の累乗.
 25^2 = 25×25 = 625 = 31
 25^3 = 25^2×25 = 31×25 = 775 = 16
 25^4 = 25^3×25 = 16×25 = 400 = 4
 25^5 = 25^4×25 = 4×25 = 100 = 1
 25^6 = 25^5×25 = 1×25 = 25
と25に戻る.これによって,巨大な指数も瞬時に計算できるのであった.
 25^2007 = 25^2005×25^2 = 25^(5×401)×31 = (25^5)^401×31 = 1^401×31 = 1×31 = 31

どの数も,自分自身に戻る累乗がある.これが暗号を元に戻す「復号」の原理になる.

他の数の累乗も,31乗までエクセルで計算して表にした.>pdf

一覧表を見ると,なんだかでたらめな数の羅列に見える.これを暗号化に使うわけだが,よく見ると一定の規則で繰り返している.
さらに 11乗,21乗,31乗 ではどの数も自分自身に戻っている.

何乗で元に戻るかは,計算で突き止められることが300年前(フェルマー)にわかっていた.
具体的にはこうなる.
「33で割った余り」の場合は,33 = 3×11 と素因数分解される.
3-1=2 と 11-1=10 の最小公倍数 10 の倍数,10,20,30,40,50,…
に1を足した,
 11,21,31,41,51,61,71,81,91乗… 
で元に戻る.
300年前フェルマーは,よもやこれが暗号に使うとは思いもしなかったろう.

「元に戻る累乗」の中で,暗号化と復号に使えるのは,
 (25^a)^b=25^(a×b)
となるものである.
つまり累乗が「a×b」とでき,2回の累乗に直せるもの.
たとえば,
 (25^3)^7=25^(3×7)=25^21
は2回の累乗(3乗と7乗)で元に戻るから暗号化に使えるが,25^11 は2回の累乗に分けられないので使えない.

実際は「3乗で暗号化,7乗で復号」のように使う.
 25^3=16
が暗号化,これを復号するのが7乗
 16^7=25

これによって,「暗号化と復号の方法が違う」という状態が作られる.
それも「累乗は元に戻せない」(前回)から,暗号化の方法だけを知っていても,戻す方法だけ秘密にしておけば,だれも解読できない.
つまり暗号化の方法を公開できる公開鍵暗号の完成である.

コンピュータ内部では文字も映像も音声もすべて整数(コード)で表現されている.
その数
 0,1,2,3,4,5,6,…
を3乗すると
 0,1,8,27,26,18,…
と予測もつかないようなコードに変換される.
しかしこれを7乗すると
 0,1,2,3,4,5,6,…
に復号されるというわけである.

これが公開鍵暗号RSAの「原理」である.
実際は「33」は数字が小さいので,暗号化「法33で3乗」から「法33で7乗で復号」がばれてしまう.

つづく

0 件のコメント:

コメントを投稿

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.