2007年1月18日木曜日

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

続き
割り算の余りの世界は四則計算が自由に行える世界であったが,累乗でパワー炸裂.
暗号化には累乗の計算をする.

たとえば,昨日の
 0= 7=14=21=28=35=42=49=56=63=70=77=…
 1= 8=15=22=29=36=43=50=57=64=71=78=…
 2= 9=16=23=30=37=44=51=58=65=72=79=…
 3=10=17=24=31=38=45=52=59=66=73=80=…
 4=11=18=25=32=39=46=53=60=67=74=81=…
 5=12=19=26=33=40=47=54=61=68=75=82=…
 6=13=20=27=34=41=48=55=62=69=76=83=…
の世界で,
 4^2 = 4×4 = 16 = 2
 4^3 = 4^2×4 = 2×4 = 8 = 1   ← 4^2=2 を使う.
 4^4 = 4^3×4 = 1×4 = 4     ← 4^3=1 を使う.
 4^5 = 4^3×4^2 = 1×2 = 2    ← 4^3=1 と 4^2=2 を使う.
 4^6 = 4^3×4^3 = 1×1 = 1    ← 4^3=1 を使う.
4^6 をまともに計算すると,4096 だが,そんな大きな計算をするまでも無く,「7で割った余りが 1」といえる.
つまり,今日(木曜日)の 4^6=4096 日目は「金曜日」といえる.(1余るから)

(4^3)^5 = 4^3×4^3×4^3×4^3×4^3 = 4^15 = 4^(3×5) という性質と,今求めた4^3=1 を使うと,もっと巨大な指数でも
 4^2007 = 4^(3×669) = (4^3)^669 = 1^669 = 1
4^2007 をまともに計算すると,1209桁の巨大数だが,それを計算するまでも無く,「7で割った余りが 1」といえる.
つまり,「累乗でパワー炸裂」

7で割った余り 0,1,2,3,4,5,6 の累乗はこうなる.
0 や 1 は何乗してもかわらない.

 2^1 = 2
 2^2 = 4
 2^3 = 4×2 = 8 = 1
この先,2,4,1 の繰り返し.

 3^1 = 3
 3^2 = 9 = 2
 3^3 = 3^2×3 = 2×3 = 6
 3^4 = 3^3×3 = 6×3 = 18 = 4
 3^5 = 3^4×3 = 4×3 = 12 = 5
 3^6 = 3^5×3 = 5×3 = 15 = 1
この先,3,2,6,4,5,1 の繰り返し.

 4^1 = 4
 4^2 = 16 = 2
 4^3 = 4^2×4 = 2×4 = 8 = 1
この先,4,2,1 の繰り返し.

 5^1 = 5
 5^2 = 25 = 4
 5^3 = 5^2×5 = 4×5 = 20 = 6
 5^4 = 5^3×5 = 6×5 = 30 = 2
 5^5 = 5^4×5 = 2×5 = 10 = 3
 5^6 = 5^5×5 = 3×5 = 15 = 1
この先,5,4,6,2,3,1 の繰り返し.

 6^1 = 6
 6^2 = 36 = 1
この先,6,1 の繰り返し.

どれも累乗の計算では,同じ数字の繰り返しになる.
同じ数字の繰り返しになるから,累乗の計算はきわめて高速に実現する.
たとえば
 5^1000000 = 5^999996×5^4 = (5^6)^1165×2 = 1^1165×2 = 1×2 = 2

さて,7で割った余りの累乗の周期は,
 1, 2, 3, 6
の4通りあるが,
すべての数が元に戻るのは,周期が6の
 7乗,13乗,19乗,25乗,31乗,37乗,43乗,49乗,55乗,・・・
である.
この「元に戻る」性質を暗号と復号に使う.

RSA は Rivest Shamir Adleman 3人の頭文字だが,これを暗号に使うことを思いついたのはすごいなー

さて,暗号化には「累乗」を使うのだが,解読されない理由は
 「累乗の逆算ができない」
ことによる.確実に「元に戻す」には累乗を繰り返すしかないのだ.

たとえば,3乗で暗号化したとする.
ある数を3乗で暗号化したら,「6」になったとして,そのある数はなんだろうか.
上の計算表を見ると,
 3^3 = 6
 5^3 = 6
の2通りあって,決まらない.つまり
 「何を3乗して6になったのか確定しない」
のである.

古典的な暗号化では
 「暗号化の逆操作が復号」
なのだが,公開鍵暗号のポイントがこの
 「逆操作が不可能」
な点といえる.

つづく

0 件のコメント:

コメントを投稿

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