2007年1月22日月曜日

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

続き) 安全性について(ばれない?)

前回は法(割る数)33 の世界であった.

「元に戻る」だけなら,「法11」(11で割った余り)でもOKである.
「法11」で元に戻る累乗は 11-1=10 の倍数に1を足した
11,21,31,41,51乗・・・
であるから,この場合
21乗 = 3×7乗 = 3乗の7乗
で,暗号化 3乗,復号に 7乗などとできる.
実際,11未満の整数
0,1,2,3,4,5,6,7,8,9,10
は「法11で3乗」により
0,1,8,5,9,4,7,2,6,3,10
と入れ替わり,7乗で元に戻る.

しかし,「法11で3乗」を公開すると,「元に戻る累乗は 11-1=10 の倍数に1を足したもの」とばれる.
これは「法」をどんなに大きな素数にしても,簡単に計算できてしまうのである.

たとえば「法179424673」の場合,1794246725乗で元に戻るのが見つかり,5乗と358849345乗などがペアになるが(他にも多数の組み合わせはある),「法179424673で5乗」を公開すると,上記の計算方法でペアの累乗が簡単に見つかる.



そこで,RSA では,「法を巨大素数の積」とした.
前回の「法33」では,数字が小さいのでばれてしまう.また数字が大きくても,ひとつの素数では簡単にばれてしまう.
法を2つの巨大素数の積にすればばれないのである.

法33くらいだと,電卓の手作業でばれてしまう.その手順は
1.法33を素因数分解で 3×11 にする.
2.3-1=2 と 11-1=10 の最小公倍数 10 の倍数に1を足した 11,21,31,41,51乗で元に戻る.
3.3乗で暗号化したなら,7乗や17乗で戻るに違いない.

では,法4028033ならどうか.これは29乗を暗号化とする.復号するためにもうひとつの累乗を見つけるには,
1.法4028033を素因数分解で □×△ にする.
これは電卓で手作業では挫折する.素因数分解を効率的に行う方法は見つかっていないからである.地道に割るしかない.
基本的に5の倍数でない奇数で割っていくしかなく,1秒に1回割り算したとしても15分くらいはかかり,たいてい挫折する.
もちろんコンピュータを使えば,すぐにできるが.

しかし暗号鍵,復号鍵を作成するのは電卓で可能である.
素数とわかってる2つの数 2003,2011 を使って,法 2003×2011=4028033 を生成する.
2003-1=2002,2011-1=2010 の積は 4024020.
これを最大公約数で割れば,最小公倍数になる.
2数の最大公約数はユークリッドの互除法
2010-2002=8
2002-8×250=2
8-2×4=0
より最大公約数は2.これで最小公倍数は 4024020÷2=2012010.
これの倍数に1を足した
2012011,2024021,6036031,4048041乗
で元に戻る.これらを小さい素数で割ると,
6036031÷29=208139
が見つかるから,「法4024020で29乗」を暗号化として公開する.
自分に来た通信は「208139乗」で元に戻るが,秘密にしておけば,誰にもばれないというわけである.
累乗の計算はやはり数字が循環しているので,コンピュータを使えば一瞬である.さらに,「累乗の逆算はできない」ことから,暗号化の累乗から復号されることはない.
くろべえ「互除法」関連の記事

実際のRSA では10進数で600桁以上の「法」を用いる.
つまり300桁程度の2つの素数の積になっている.600桁以上というのは実際は1024ビットの2つの素数の積で,2進数2048桁ということである.つまり2進1024桁の2つの素数の積を用いている.
2進1024桁の整数 8.9×10^307個,ざっと10^308個のうち,素数は1.26×10^305個,ざっと 10^305個,つまりその付近では1000個に1個くらいの割合であるから,枯渇する心配は無い.そして2進2048桁(10進617桁)を素因数分解するには「一生かけてもおわらない.」
また,10^305個の素数を全部調べ上げるには,1秒に1兆個調べても,10^277年(=1兆年の1兆倍の1兆倍の1兆倍の・・・23回繰り返し)くらいかかるから不可能.
将来コンピュータの性能が1兆倍になれば,さらに桁数を増やすだけでよい.

では,そんな桁数の暗号化(累乗)は簡単にできるかという問題があるが,授業中に600桁以上の計算を実演した.パソコンでも専用のソフトがあれば,一瞬にできてしまう.
その部分をブラウザに実装したのが,「SSL」通信(画面右下に出る鍵マーク)である.

授業では Mathematicaを用いて実演した.
まず,
898846567431157953864652595394512366808988489471153286367150
405788663379027504815663542386612037680105600569399356966788
293948844072083112464237153197370621888839467124327426381511
098006230470597265414760425028844190753411712314407369565552
704136185816752553422931491199736229692398581524176781648121
12244609  (308桁)

179769313486231590772930519078902473361797697894230657273430
081157732675805500963132708477322407536021120113879871393357
658789768814416622492847430639474124377767893424865485276302
219601246094119453082952085005768838150682342462881473913110
540827237163350510684586298239947245938479716304835356329624
224079161  (309桁)
という2つの素数を用意.
Table[{n, PrimeQ[2^1023 + 174801 + 2 n]}, {n, 1, 1000}]
のような感じで探す.174801 はテキトーな奇数.n=600 で,308桁のほうの素数である.
これを見つけるには10秒少々かかった.しかし,これ以降の計算はどれも「一瞬」だった.

法はそれらをかけた617桁の
161585030356555036503574383443349759802220513348577420160651
727137623275694339454465986007057614567318443589804609490097
470597795752454605475440761932241415603154386836504980458750
988751948260533980288191920337841383961093213098780809190471
692380852352908229260181525214437879457705329043037761995619
652191822823623634928776756461332363549533876020394753726678
055149358656889405961500351422045210412960839584600291251374
625805429372624218122889047136958973668628514830471218228103
614668511146062797271725265295559237153014623098941448096252
763146554666598954680831687609191712092101784510604028160214
38831425811493049
である.これの素因数分解は一生かけてもできないが,暗号化と復号の累乗はすぐ計算される.

3乗で暗号化した場合,
673270959818979318764893264347290665842585472285739250669382
196406763648726414393608275029406727363826848290852539542072
794157482301894189481003174717672565013143278485437418578129
119799784418891584534133001407672433171221721244920038293632
051586884803784288584089688393491164407105537679324008315081
884132583862849719313762061947394072358319898305955355471742
483532947664680899268407654062727430221353027267847873096568
978771102044907024610998790601031308652152704849803403563005
564683241050183774416389454380324841943675211827942963137627
726874568975793321794058447251655160387054564305867848282016
847374561465387乗
で復号である.

SSL通信は「法」と3乗を相手のブラウザに送り込んで,自動的に通信を暗号化している.これは2048ビットは256バイトであるから,伝えること自体は手軽である.

授業では
111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111
111111
を3乗して
160540538001045163848704088231807804776018099926061080277542
645903469098065256577289644843016930657526240951465096849736
221916508454598412684458291636374288523458933953642127937934
853209649744354424270373957044955871278082196348676976669555
531495324083566500704856802178974375075961170532597821964123
295254293539411556851552353739744414503311688790990016011854
273509228084716592233268240760753742692370893335064909384399
906920680501185789453623160035937659357322423897329084689182
368762611363083424098082000448511773994573190898556461165647
036693799861484930248304327378957321678059597331749450921621
88335349515110955
を計算するのも一瞬だったし,これを復号する累乗の計算も一瞬だった.
つまり暗号化も復号も,自分のセレロン1.5GHzのパソコンで,時間を意識することが無かった.まぁ時間がかかるなら,ネットの通信には使えないのだけれど.

これを,復号の累乗して,111・・・11と戻るのは,わかっていても見ごたえがあるものである.

「一十百千万億兆・・・と桁数の読み方はあるが,それ以上知ってる?」
といわれて
「不可思議とか無量大数とかあるよ」
となんとなく覚えていても,途中は知らない.覚えても意味はないし.
塵劫記にある一番大きな単位,無量大数でも70桁くらいしかない.
インターネットのSSL通信(鍵マークの通信)では,見えないところで,その10倍くらいの桁数の計算が使われている.「無量大数」なんて,微々々・・・々たる物である.

(おわり)

0 件のコメント:

コメントを投稿

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