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

（続き）

前回まで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乗で復号」がばれてしまう．

（つづく）