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

（続き）　安全性について（ばれない？）

前回は法（割る数）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くらいだと，電卓の手作業でばれてしまう．その手順は
１．法33を素因数分解で 3×11 にする．
２．3-1=2 と 11-1=10 の最小公倍数 10 の倍数に1を足した 11,21,31,41,51乗で元に戻る．
３．3乗で暗号化したなら，7乗や17乗で戻るに違いない．

では，法4028033ならどうか．これは29乗を暗号化とする．復号するためにもうひとつの累乗を見つけるには，
１．法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倍くらいの桁数の計算が使われている．「無量大数」なんて，微々々・・・々たる物である．

（おわり）