Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2012-05-28

RSAのひ・み・つ

RSAとは、今日最も広く普及している公開鍵暗号です。

公開鍵暗号というのは、暗号をかける鍵と、暗号を解く鍵が異なっている暗号のことです。

普通に考えれば、かける鍵と解く鍵は同じでなければならないような気がします。

(かける鍵と解く鍵が普通に同じである暗号は「共通鍵暗号」と言います)

ところが公開鍵暗号は、

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

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

といった、なんとも不思議な仕組みなのなです。

なぜこんなことができるのか、秘密を探ってみましょう。


■ 一巡する計算

普通の(物理的な)錠前は、同じ1本の鍵で開閉を行います。

なぜかというと、開ける動作を全く逆にしたものが、閉める動作になっているからです。

つまり普通の錠前は「一直線の往復」なのです。

もし、開ける鍵と閉じる鍵を別々にしたかったなら「一直線の往復」ではダメで、

「行きと帰りが異なる巡回コース」にしないといけません。

山手線のように(あるいは大阪環状線のように)ぐるっと一周回って元に戻る手順が必要なのです。

そこで、何か順番に演算を行っていったら、一周してもとにもどってくるような計算手順を探してみます。

例えば3桁のカウンターは+1を繰り返してゆくと、999に達した後、また0に戻ってきます。

3桁のカウンターとは、ある数を1000で割ったときの余りのことです。

こうしたカウンターであれば、確かに一巡して戻ってくるのですが、途中の計算が単純過ぎて暗号には使えません。

実際にRSAで用いているのは+1ではなくて、p回かけ算を繰り返す“p乗する”という計算です。


フェルマーの小定理

まずは分かりやすい、pが素数の場合を考えてみます。

pが素数の場合、ある整数aをp乗して、その結果をpで割った余りは、もとの数aに戻ってきます。

フェルマーの小定理

  a ^ p ≡ a (mod p)

    ※ p は素数、a は p の倍数でない整数(a と p は互いに素)

例えば 5 ^ 7 = 78125 で、78125 ÷ 7 = 11160 余り 5、

確かに 5 ^ 7 ≡ 5 (mod 7) となっています。

ある数をpで割った余りは、全部でp通りしかありません。

例えば7で割った余りは、0〜6の7通りです。

なので何回も掛け算(べき乗)を繰り返せば、いつかはp通り全部を尽くしてもとに戻ってくるはずです。

(p通り全部を尽くす以前に戻ってくることもあります。)

pが素数の場合は、ちょうどp回掛け算すれば、もとに戻ってくる・・・

それがフェルマーの小定理のおよその意味です。


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

n1234567
5^n mod 75462315

下段列の結果だけを見ると、1〜6までの数字が全く不規則に並んでいるように見えます。

実際この表で、上段列の数字から下段列の数字は計算できますが、

逆に下段列の数字から上段列の数字を一発で求める方法は知られていません。

(こうして一覧表を作ってみるしかありません)

上から下には簡単に行けるけど、逆に下から上に行くのは難しい、、、

こういった性質を持つ計算のことを「一方向性関数」と呼んでいました >> id:rikunora:20120514

公開鍵暗号が一方向性関数を用いているのは、「一方向だけに一巡して戻ってくる」ような状況を作りたかったからなのです。

もし逆回りが可能だったなら、わざわざ別の鍵を用意せずとも、同じ鍵を使って元に戻ってこれるでしょう。

それだと公開鍵暗号としての用を為しません。


■ 2つの数に分けてみる

それでは、a ^ p mod p という計算を使って「行きと帰りが異なる暗号」を作ってみましょう。

p回掛け算(べき乗)を繰り返すと元に戻ってくるのですから、

pを「何らかのうまい方法で」2つの数eとdに分けて、

「行き」にe回、「帰り」にd回掛け算すれば良いように思えます。

・pを「何らかのうまい方法で」2つの数、eとdに分ける。

 (eはencrypt=暗号化、dはdecrypt=復号化、という意味)

暗号化: 平文aに対して、 a ^ e mod p を暗号文cとする。

・復号化: 暗号文cに対して、c ^ d mod p すれば元の平文aに戻る。

要は、山手線のように一巡している計算を、

 ・東京 = 品川経由 => 渋谷暗号化、

 ・渋谷 = 池袋経由 => 東京 を復号化、

といった風に2分割しようという試みです。


ここで問題となるのは、pを2つの数、eとdに分ける「何らかのうまい方法」の中身です。

単純にp=e+dと分けてみても、うまくいきません。

試してみましょう。

3 ^ 7 mod 7 という計算は、一巡して 3 に戻ってくる。

7 を 3 + 4 という2つの数に分けてみる。

暗号化: 3 ^ 3 mod 7 = 27 mod 7 = 6

復号化: 6 ^ 4 mod 7 = 1296 mod 7 = 1 (?元に戻らない、失敗?)

なぜ足し算ではうまくいかないのか。

それは、a ^ p mod p という計算が、べき乗、剰余といった「掛け算、割り算」の体系だからです。

なので、気持ちの上では p=exd といった具合に、掛け合わせる2つの数に分けたいところです。

しかし、ここではpは素数ということだったので、

残念ながらそのままではexdという2つの整数の積に分けることができません。


オイラーの定理

そこで、pは素数という制限を外して、一般的な自然数nについて考えてみます。

  a ^ □ ≡ a (mod n)

    ※ n は素数とは限らない

    ※このとき □ はどうなるか?

この答は【オイラーの定理】として知られています >> wikipedia:オイラーの定理 (数論)

上の□に入る数は『1〜nまでの自然数で、nと互いに素である数の個数』+1となります。

『・・・』はオイラー関数といって、φ(n)という記号で表します >> wikipedia:オイラーのφ関数

もしnが素数だったら、1〜nまでの自然数は全てnと互いに素なので、□=nとなっています。

つまり、オイラーの定理は、先のフェルマーの小定理の一般化になっているわけです。

オイラーの定理の証明は、Wikipediaを見てもらった方が早いです。

あと、以下の解説が親切。

* Tiny Basic for Windows -- オイラーの定理オイラー関数

>> http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Euler.html


nが合成数、n=pxq(pとqは素数)だった場合、計算の「1周期」はどうなるか。

オイラーの定理によれば、『nと互いに素である数の個数』+1で一巡するとのことです。

数えてみましょう。

・1〜nまでの間に、pの倍数はq−1個ある。(n=pq自体は含まない)

・1〜nまでの間に、qの倍数はp−1個ある。(n=qp自体は含まない)

・pとqが素数であれば、2種類の倍数が重複することはない。

 『nと互いに素である数の個数』φ(n)

  = pq−(p−1)−(q−1)

  = pq−p−q+1

  =(p−1)(q−1)

つまり (p−1)(q−1)+1 で計算は一巡することになります。


■ 最小公倍数で一巡する

実際にp=3、q=5、n=3x5=15という数で試してみましょう。

計算の1周期は、(p−1)(q−1)+1=2x4+1=9で元に戻ってくるはずです。

f:id:rikunora:20120529030820p:image

この表を見ると、確かに a ^ 9 mod 15 = a となっており、9で一巡していることが分かります。

それだけでなく、表の中ほどの5でもすでに一巡しており、9は二巡目であることに気付くでしょう。

実はこれ、(p−1)と(q−1)の最小公倍数が1周期となっているのです。

なぜそうなるか。

直観的には、(p−1)と(q−1)に重なりがある分だけ、周期が短く詰まるといった感じです。

もう少し正確には、以下の理由によります。

フェルマーの小定理 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)の両方の倍数である最小公倍数Lについて、

 a ^ L = 1 (mod p) かつ a ^ L = 1 (mod q) になっている。

同じ数 a ^ L を、pで割っても1余り、qで割っても1余るのだから、pqで割っても1余るはずだ。

pq = n とすると、

 a ^ L = 1 (mod n)

両辺に a を掛けて

 a ^ (L + 1) = a (mod n)

結局のところ、最小公倍数L+1のところで、計算は一巡する。


■ 2つの数を探す

ようやくゴールが見えてきました。

最小公倍数L+1のところで一巡する計算を、2つの数eとdに分けて、eを暗号化、dを復号化に用いる。

復号化は元に戻ればよいのですから、計算はちょうど一巡だけでなく、二巡、三巡、・・・も候補に含まれます。

そのことを考慮に入れると、最終的な答はこうなります。

exd mod L = 1 となるような、2つの数eとdを探す。

ここでeとLは共通の約数を持ってはならない、互いに素である必要があります。


■ RSAの手順

以上をまとめると、こんな手順になります。

1.2つの素数p、qを選ぶ。

2.n=pxqを算出。

3.(p−1)と(q−1)の最小公倍数、Lを求める。

4.exd mod L = 1 となるような、2つの数eとdを探し出す。(eとLは互いに素)

これで準備完了。

・eとnの2つの数字が暗号化の鍵になります。

・dとnの2つの数字が復号化の鍵になります。

暗号化: 平文aに対して、 a ^ e mod n を暗号文cとする。

・復号化: 暗号文cに対して、c ^ d mod n すれば元の平文aに戻る。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rikunora/20120528/p1
リンク元