ＲＳＡのひ・み・つ - 小人さんの妄想

ＲＳＡとは、今日最も広く普及している公開鍵暗号です。
公開鍵暗号というのは、暗号をかける鍵と、暗号を解く鍵が異なっている暗号のことです。
普通に考えれば、かける鍵と解く鍵は同じでなければならないような気がします。
（かける鍵と解く鍵が普通に同じである暗号は「共通鍵暗号」と言います）
ところが公開鍵暗号は、

　・暗号をかける鍵は暗号化専用で、解くことはできない。
　・暗号を解く鍵は復号化専用で、かけることはできない。

といった、なんとも不思議な仕組みなのなです。
なぜこんなことができるのか、秘密を探ってみましょう。

■ 一巡する計算
普通の（物理的な）錠前は、同じ１本の鍵で開閉を行います。
なぜかというと、開ける動作を全く逆にしたものが、閉める動作になっているからです。
つまり普通の錠前は「一直線の往復」なのです。
もし、開ける鍵と閉じる鍵を別々にしたかったなら「一直線の往復」ではダメで、
「行きと帰りが異なる巡回コース」にしないといけません。
山手線のように（あるいは大阪環状線のように）ぐるっと一周回って元に戻る手順が必要なのです。
そこで、何か順番に演算を行っていったら、一周してもとにもどってくるような計算手順を探してみます。
例えば３桁のカウンターは＋１を繰り返してゆくと、９９９に達した後、また０に戻ってきます。
３桁のカウンターとは、ある数を１０００で割ったときの余りのことです。
こうしたカウンターであれば、確かに一巡して戻ってくるのですが、途中の計算が単純過ぎて暗号には使えません。
実際にＲＳＡで用いているのは＋１ではなくて、ｐ回かけ算を繰り返す“ｐ乗する”という計算です。

■ フェルマーの小定理
まずは分かりやすい、ｐが素数の場合を考えてみます。
ｐが素数の場合、ある整数ａをｐ乗して、その結果をｐで割った余りは、もとの数ａに戻ってきます。

【フェルマーの小定理】
　　a ^ p ≡ a (mod p)
　　　　※ p は素数、a は p の倍数でない整数（a と p は互いに素）

例えば 5 ^ 7 = 78125 で、78125 ÷ 7 = 11160 余り 5、
確かに 5 ^ 7 ≡ 5 (mod 7) となっています。
ある数をｐで割った余りは、全部でｐ通りしかありません。
例えば７で割った余りは、０〜６の７通りです。
なので何回も掛け算（べき乗）を繰り返せば、いつかはｐ通り全部を尽くしてもとに戻ってくるはずです。
（ｐ通り全部を尽くす以前に戻ってくることもあります。）
ｐが素数の場合は、ちょうどｐ回掛け算すれば、もとに戻ってくる・・・
それがフェルマーの小定理のおよその意味です。

具体的に a=5, p=7 として、5^n mod 7 (n=1〜7) を調べると、こんな風になっています。

n	1	2	3	4	5	6	7
5^n mod 7	5	4	6	2	3	1	5

下段列の結果だけを見ると、1〜6までの数字が全く不規則に並んでいるように見えます。
実際この表で、上段列の数字から下段列の数字は計算できますが、
逆に下段列の数字から上段列の数字を一発で求める方法は知られていません。
（こうして一覧表を作ってみるしかありません）
上から下には簡単に行けるけど、逆に下から上に行くのは難しい、、、
こういった性質を持つ計算のことを「一方向性関数」と呼んでいました >> [id:rikunora:20120514]
公開鍵暗号が一方向性関数を用いているのは、「一方向だけに一巡して戻ってくる」ような状況を作りたかったからなのです。
もし逆回りが可能だったなら、わざわざ別の鍵を用意せずとも、同じ鍵を使って元に戻ってこれるでしょう。
それだと公開鍵暗号としての用を為しません。

■ ２つの数に分けてみる
それでは、a ^ p mod p という計算を使って「行きと帰りが異なる暗号」を作ってみましょう。
ｐ回掛け算（べき乗）を繰り返すと元に戻ってくるのですから、
ｐを「何らかのうまい方法で」２つの数ｅとｄに分けて、
「行き」にｅ回、「帰り」にｄ回掛け算すれば良いように思えます。

・ｐを「何らかのうまい方法で」２つの数、ｅとｄに分ける。
　（ｅはencrypt=暗号化、ｄはdecrypt=復号化、という意味）
・暗号化：平文ａに対して、　ａ ^ ｅ mod ｐを暗号文ｃとする。
・復号化：暗号文ｃに対して、ｃ ^ ｄ mod ｐすれば元の平文ａに戻る。

要は、山手線のように一巡している計算を、
　・東京 = 品川経由 => 渋谷を暗号化、
　・渋谷 = 池袋経由 => 東京を復号化、
といった風に２分割しようという試みです。

ここで問題となるのは、ｐを２つの数、ｅとｄに分ける「何らかのうまい方法」の中身です。
単純にｐ＝ｅ＋ｄと分けてみても、うまくいきません。
試してみましょう。

3 ^ 7 mod 7 という計算は、一巡して 3 に戻ってくる。
7 を 3 + 4 という２つの数に分けてみる。
暗号化: 3 ^ 3 mod 7 = 27 mod 7 = 6
復号化: 6 ^ 4 mod 7 = 1296 mod 7 = 1 (？元に戻らない、失敗？)

なぜ足し算ではうまくいかないのか。
それは、a ^ p mod p という計算が、べき乗、剰余といった「掛け算、割り算」の体系だからです。
なので、気持ちの上ではｐ＝ｅｘｄといった具合に、掛け合わせる２つの数に分けたいところです。
しかし、ここではｐは素数ということだったので、
残念ながらそのままではｅｘｄという２つの整数の積に分けることができません。

■ オイラーの定理
そこで、ｐは素数という制限を外して、一般的な自然数ｎについて考えてみます。

　　a ^ □ ≡ a (mod n)
　　　　※ n は素数とは限らない
　　　　※このとき □ はどうなるか？

この答は【オイラーの定理】として知られています >> wikipedia:オイラーの定理 (数論)
上の□に入る数は『1〜nまでの自然数で、nと互いに素である数の個数』＋１となります。
『・・・』はオイラー関数といって、φ(n)という記号で表します >> wikipedia:オイラーのφ関数
もしｎが素数だったら、1〜nまでの自然数は全てｎと互いに素なので、□＝ｎとなっています。
つまり、オイラーの定理は、先のフェルマーの小定理の一般化になっているわけです。
オイラーの定理の証明は、Wikipediaを見てもらった方が早いです。
あと、以下の解説が親切。
* Tiny Basic for Windows -- オイラーの定理・オイラー関数
>> http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Euler.html

ｎが合成数、ｎ＝ｐｘｑ（ｐとｑは素数）だった場合、計算の「１周期」はどうなるか。
オイラーの定理によれば、『nと互いに素である数の個数』＋１で一巡するとのことです。
数えてみましょう。

・1〜ｎまでの間に、ｐの倍数はｑ−１個ある。（ｎ＝ｐｑ自体は含まない）
・1〜ｎまでの間に、ｑの倍数はｐ−１個ある。（ｎ＝ｑｐ自体は含まない）
・ｐとｑが素数であれば、２種類の倍数が重複することはない。
　『nと互いに素である数の個数』φ(n)
　　＝ｐｑ−（ｐ−１）−（ｑ−１）
　　＝ｐｑ−ｐ−ｑ＋１
　　＝（ｐ−１）（ｑ−１）

つまり（ｐ−１）（ｑ−１）＋１で計算は一巡することになります。

■ 最小公倍数で一巡する
実際にｐ＝３、ｑ＝５、ｎ＝３ｘ５＝１５という数で試してみましょう。
計算の１周期は、（ｐ−１）（ｑ−１）＋１＝２ｘ４＋１＝９で元に戻ってくるはずです。

この表を見ると、確かに a ^ 9 mod 15 = a となっており、９で一巡していることが分かります。
それだけでなく、表の中ほどの５でもすでに一巡しており、９は二巡目であることに気付くでしょう。
実はこれ、（ｐ−１）と（ｑ−１）の最小公倍数が１周期となっているのです。
なぜそうなるか。
直観的には、（ｐ−１）と（ｑ−１）に重なりがある分だけ、周期が短く詰まるといった感じです。
もう少し正確には、以下の理由によります。

フェルマーの小定理 a ^ p ≡ a (mod p) の両辺を a で割ると、a ^ (p-1) = 1 (mod p) となる。
ここで(p-1)を m 倍したとしても、
　　a ^ {m(p-1)} = {a^(p-1)}・{a^(p-1)}・{a^(p-1)}・・・m回繰り返し
　= 1・1・1・・・m回繰り返し = 1 (mod p)
つまり、(p-1)の任意の倍数で 1 (mod p) となっている。
同様に、(q-1)の任意の倍数でも 1 (mod q) となっている。
ということは、(p-1)と(q-1)の両方の倍数である最小公倍数Ｌについて、
　a ^ L = 1 (mod p) かつ a ^ L = 1 (mod q) になっている。
同じ数 a ^ L を、ｐで割っても１余り、ｑで割っても１余るのだから、ｐｑで割っても１余るはずだ。
pq = n とすると、
　a ^ L = 1 (mod n)
両辺に a を掛けて
　a ^ (L + 1) = a (mod n)
結局のところ、最小公倍数Ｌ＋１のところで、計算は一巡する。