RSA暗号　～さんすう・数学のお勉強～

RSA暗号

●　フェルマーの小定理　●

　フェルマーの小定理って、こんなものでした。

＜５でわったあまりの世界＞

　たとえば、５でわったあまりの世界で考えましょう。（５は素数）

　５でわったあまりは

　　　　　　　０　，　１　，　２　，　３　，　４

だけですから、このあまりの世界には、数はたったの５つしかありません。

　たとえば、ふつうの世界の　７　と　１２　は、
どちらも　５でわったあまりが　２　ですから、同じ数と考えて

　　　　　　　７＝１２　　ではなくて　　７≡１２　（mod　５）

とあらわすことになっています。

　そして、　７　も　１２　も　このあまりの世界では　２　なのです。

　そうすると、フェルマーの小定理は、０をのぞくと

　　　　１×１×１×１≡１　（mod　５）　　つまり　　　１^４≡１　（mod　５）
　　　　２×２×２×２≡１　（mod　５）　　つまり　　　２^４≡１　（mod　５）
　　　　３×３×３×３≡１　（mod　５）　　つまり　　　３^４≡１　（mod　５）
　　　　４×４×４×４≡１　（mod　５）　　つまり　　　４^４≡１　（mod　５）

となるというものです。

　つまり、このあまりの世界では、（０は何回かけても０ですが）
０以外の数は、どれも４回かけると（４乗すると）１になるというのです。

　ためしに、計算してみましょう。

　　　　　１×１×１×１＝１　　　を　５でわったあまりは　１
　　　　　２×２×２×２＝１６　　を　５でわったあまりは　１
　　　　　３×３×３×３＝８１　　を　５でわったあまりは　１
　　　　　４×４×４×４＝２５６　を　５でわったあまりは　１

　たしかに、そうなっていますね。
　では、どうしてこんなことになるのでしょうか。

　たとえば、　２^４≡１　（mod　５）　はこんなふうに考えます。

　このあまりの世界の０をのぞいた数にどれも　２をかけます。

　　　　　２×１　，　２×２　，　２×３　，　２×４

　そうすると、これらは順番がいれかわっただけで、

　　　　　　１　　，　　２　　，　　３　　，　　４

とおなじものなのです。じっさい

　　　　　２×１　，　２×２　，　２×３　，　２×４　　は

　　　　　　２　　，　　　４　　，　　１　　，　　３　　　　です。

　きちんというには、まず　２×１　，　２×２　，　２×３　，　２×４　が
このあまりの世界で全部異なっていることをしめします。
　それには、ユークリッドの互除法でもとめる、２の逆の数（逆元）をつかうといいですね。
　すると、同じ数だけあって全部異なっているのですから、
順番を入れかえただけということになるのです。

　ですから、

　　　　（２×１）×（２×２）×（２×３）×（２×４）　≡　１×２×３×４　　（mod　５）

　つまり、

　　　　２^４×１×２×３×４　≡　１×２×３×４　　（mod　５）

　これの両辺に　１×２×３×４　の逆の数（逆元）をかけると

　　　　２^４≡１　（mod　５）

となります。

　そして、２^４≡１　（mod　５）　の　４　は、
このあまりの世界の数で、逆の数（逆元）をもつものが、

　　　　　　　０　，　１　，　２　，　３　，　４

の　５個のうち　０　をのぞいた　４個　だという　４です。

＜１１でわったあまりの世界＞

　同じようにして、今度は　１１　でわったあまりの世界で考えましょう。（１１は素数）

　１１でわったあまりは

　　　　０　，　１　，　２　，　３　，　４　，　５　，　６　，　７　，　８　，　９　，　１０

ですから、このあまりの世界には、数は　１１個　あります。

　そして、フェルマーの小定理は、０をのぞくと

　　　　　１^１０≡１　（mod　１１）
　　　　　２^１０≡１　（mod　１１）
　　　　　３^１０≡１　（mod　１１）
　　　　　４^１０≡１　（mod　１１）
　　　　　５^１０≡１　（mod　１１）
　　　　　６^１０≡１　（mod　１１）
　　　　　７^１０≡１　（mod　１１）
　　　　　８^１０≡１　（mod　１１）
　　　　　９^１０≡１　（mod　１１）
　　　　１０^１０≡１　（mod　１１）

となるというものです。

　つまり、このあまりの世界では、（０は何回かけても０ですが）
０以外の数は、どれも１０回かけると（１０乗すると）１になるというのです。

　そして、２^１０≡１　（mod　１１）　などの　１０　は、
このあまりの世界の数で、逆の数（逆元）をもつものが

　　　　０　，　１　，　２　，　３　，　４　，　５　，　６　，　７　，　８　，　９　，　１０

の　１１個のうち　０　をのぞいた　１０個　だという　１０です。

●　剰余　●

　公開鍵と秘密鍵のお話をおぼえていますか。

　公開鍵で９０度まわして（じっさいは累乗して）閉めたら、
その逆の数、つまり秘密鍵で－９０度まわして（じっさいは累乗して）
開けてもとにもどすのでした。

＜５５でわったあまりの世界＞

　では、この鍵を使って、いったい何を開けたり閉めたりするのでしょうか。

　じつは、あまりの世界なのです。

　それも、２つの素数　たとえば　５　と　１１　をかけた　５×１１＝５５
でわったあまりの世界を考えるのです。

　もちろん、じっさいには　もっと大きな素数をかけ算します。
　そして、５×１１＝５５　とかけ算するのはかんたんだけど、
反対に　５５＝５×１１　と素因数分解するのはむずかしいということを、
暗号に利用しているのです。

　さて、５５でわったあまりを、表にしてみましょう。

　　　　　Ｙ　　０　　　１　　　２　　　３　　　４
　　　　　○　　０　　　１　　　２　　　３　　　４
　　Ｘ　□　－－－－－－－－－－－－－－
　　０　０｜　　０　　１１　　２２　　３３　　４４
　　　　　｜
　　９　１｜　４５　　　１　　１２　　２３　　３４
　　　　　｜
　　７　２｜　３５　　４６　　　２　　１３　　２４
　　　　　｜
　　５　３｜　２５　　３６　　４７　　　３　　１４
　　　　　｜
　　３　４｜　１５　　２６　　３７　　４８　　　４
　　　　　｜
　　１　５｜　　５　　１６　　２７　　３８　　４９
　　　　　｜
　１０　６｜　５０　　　６　　１７　　２８　　３９
　　　　　｜
　　８　７｜　４０　　５１　　　７　　１８　　２９
　　　　　｜
　　６　８｜　３０　　４１　　５２　　　８　　１９
　　　　　｜
　　４　９｜　２０　　３１　　４２　　５３　　　９
　　　　　｜
　　２１０｜　１０　　２１　　３２　　４３　　５４

　この表は、Ｘ　と　Ｙ　のまじわったところに

　　　　５Ｘ＋１１Ｙ

を計算して、５５でわったあまりを書きこんだものです。

　そして、表の見方ですが、たとえば
１１でわると３あまり、５でわると２あまる数は
表の３の行と２の列の交わったところの数が　４７　ですから、
５５でわると　４７　あまる数です。

　さて、最初に（素数の場合の）フェルマーの小定理は
合成数５５の場合はどうなるかをみてみます。

　素数の場合は、０だけのぞきましたが、
今回は、５５＝５×１１　ですから、逆の数をもたないのは、
５や１１でわりきれる数全部です。

　そうすると、表の赤い数をのぞくことになります。

　そうすると、のこった数の　１，１２，２３，３４，４６，２，・・・は、ぜんぶで

　　　（１１－１）×（５－１）　＝　１０×４　＝　４０　（個）

あります。すると、フェルマーの小定理のように

　　　　　１^４０≡１　（mod　５５）
　　　　１２^４０≡１　（mod　５５）
　　　　２３^４０≡１　（mod　５５）
　　　　３４^４０≡１　（mod　５５）
　　　　４６^４０≡１　（mod　５５）
　　　　　２^４０≡１　（mod　５５）
　　　　　・・・・・・・・・・・・・・・・・
　　　　　・・・・・・・・・・・・・・・・・

となるというのが、オイラーの定理（の　５５の場合）です。

　ですから、４０をもとにして、公開鍵と秘密鍵を考えることもできます。
　その場合の鍵については、＜お勉強＞の「公開鍵と秘密鍵」を読んでください。
　でも、じっさいのRSA暗号では、　４０　より小さい　２０　、つまり

　　　（１１－１）×（５－１）　＝　１０×４　＝　４０

ではなく、

　　　（１１－１）＝１０　と　（５－１）＝４　の最小公倍数　２０

を使って鍵を作るのです。

　１０と４の最小公倍数というのは、
　　　　　　　１０の倍数（何倍かした数）でもあり
　　　　　　　　４の倍数（何倍かした数）でもあるもの
つまり、
　　　　　　　２０　，　４０　，　６０　，　・・・

といった数の最小のもの、つまり　２０　です。

　じつは、　４０　でなくても、　２０　で

　　　　　１^２０≡１　（mod　５５）
　　　　１２^２０≡１　（mod　５５）
　　　　２３^２０≡１　（mod　５５）
　　　　３４^２０≡１　（mod　５５）
　　　　４６^２０≡１　（mod　５５）
　　　　　２^２０≡１　（mod　５５）
　　　　　・・・・・・・・・・・・・・・・・
　　　　　・・・・・・・・・・・・・・・・・

がなりたつというのです。

　これから、このことをたしかめていきましょう。

●　累乗（るいじょう）　●

　鍵をまわして開けたり閉めたりすることは、
じっさいは鍵となる数だけ累乗（るいじょう）すること、つまり何乗かすること、
ようするにその回数分だけかけ算をくりかえすことです。

　そこで、フェルマーの小定理が役立つのです。
　公開鍵で閉めて秘密鍵で開けてもとどおりになる、
つまり何乗かしてもかわらない（もとどおり）というとくべつな数が重要なのです。

　たし算ならば　たしてもかわらない　０
　かけ算ならば　かけてもかわらない　１　

　では、この５５でわったあまりの世界で、
　累乗という計算で、累乗してもかわらない数　は何でしょう。
　（累乗するという計算は、たし算やかけ算とはちょっとちがいますが・・・）

　ためしに　４７　を例にとって、これを何乗したら　１　になるか
考えていきます。

　まず　４７　は　１１でわると３あまり、５でわると２あまる　数です。

　これを２乗した（２回かけた）　４７×４７＝４７^２　は
　　　　１１でわると３^２＝９あまり、５でわると２^２＝４あまる　数なので
　　　　表の　９の行と４の列の数をみると　９　です。
　つまり
　　　　４７^２＝２２０９　は　５５でわると　９　あまる数です。
　　　　４７^２≡９　（mod　５５）

　そこで、いったい何乗したら、表の　１の行と１の列の数　１　になるかを
最初に行と列に分けてそれぞれで考えて、後で合わせて考えます。

＜行＞

　最初は　３の行にあります。
　２乗すると　３^２＝３×３＝９の行にうつります。
　３乗すると　３^３＝９×３≡５　（mod　１１）の行にうつります。
　４乗すると　３^４≡５×３≡４　（mod　１１）の行にうつります。
　５乗すると　３^５≡４×３≡１　（mod　１１）の行にうつります。

　５乗すると　１の行　にうつれました。

　　　　　３^５≡１　（mod　１１）

　そして、６乗からあとは同じことのくりかえしになります。
　だから、５乗，１０乗，１５乗，２０乗，・・・　は、１の行になります。
　さらに、６乗，１１乗，１６乗，２１乗，・・・　は、もとの　３の行にもどります。

　３の場合は　５乗でよかったですが、
３以外の場合にも・・・となると　１０乗でいいというのが、
フェルマーの小定理です。

　行に関しては、０以外の行は　１０乗，２０乗，３０乗，・・・すれば　１の行　にうつれます。

　そして、０の行は何乗したって０の行ですから、
　０の行もふくめて　１１乗，２１乗，３１乗，・・・すれば　もとの行　にもどれます。

＜列＞

　最初は　２の列にあります。
　２乗すると　２^２＝２×２＝４の列にうつります。
　３乗すると　２^３＝４×２≡３　（mod　５）の列にうつります。
　４乗すると　２^４＝３×２≡１　（mod　５）の列にうつります。

　４乗すると　１の行　にうつれました。

　　　　　２^４≡１　（mod　５）

　そして、５乗からあとは同じことのくりかえしになります。
　だから、４乗，８乗，１２乗，１６乗，・・・　は、１の列になります。
　さらに、５乗，９乗，１３乗，１７乗，・・・　は、もとの　２の列にもどります。

　２の場合は　４乗でよかったですが、
２以外の場合にも　４乗でいいというのが、
フェルマーの小定理です。

　　　　　１^４≡１　（mod　５）
　　　　　２^４≡１　（mod　５）
　　　　　３^４≡１　（mod　５）
　　　　　４^４≡１　（mod　５）

　列に関しては、０以外の列は　４乗，８乗，１２乗，・・・すれば　１の列　にうつれます。

　そして、０の列は何乗したって０の列ですから、
　０の列もふくめて　５乗，９乗，１３乗，・・・すれば　もとの列　にもどれます。

＜行と列＞

　さて、行と列をあわせると、（０以外の行や列の数は）
いったい何乗したら、表の　１の行と１の列の数　１　に　うつれるのでしょうか。

　４７の場合では、
　　　５乗，１０乗，１５乗，２０乗，・・・　で、１の行にうつれ、
　　　４乗，８乗，１２乗，１６乗，・・・　で、１の列にうつります。

　ですから、５の倍数でもあって、４の倍数でもある数
つまり、５　と　４　の公倍数の　２０乗，４０乗，６０乗，・・・すれば、
表の　１の行と１の列の数　１　に　うつれることになります。

　じっさいには、次のようになります。

　　　　　Ｙ　　０　　　　１　　　　２　　　　３　　　　４
　　　　　○　　０　　　　１　　　　２　　　　３　　　　４
　　Ｘ　□　－－－－－－－－－－－－－－－－
　　０　０｜　　０　　　１１　　　２２　　　３３　　　４４
　　　　　｜
　　９　１｜　４５　　　　１　　　１２　　　２３　　　３４
　　　　　｜　　　　（２０乗）（　５乗）（１５乗）（１０乗）
　　７　２｜　３５　　　４６　　　　２　　　１３　　　２４
　　　　　｜
　　５　３｜　２５　　　３６　　　４７　　　　３　　　１４
　　　　　｜　　　　（１６乗）（　１乗）（１１乗）（　６乗）
　　３　４｜　１５　　　２６　　　３７　　　４８　　　　４
　　　　　｜　　　　（　４乗）（　９乗）（１９乗）（１４乗）
　　１　５｜　　５　　　１６　　　２７　　　３８　　　４９
　　　　　｜　　　　（　８乗）（１３乗）（　３乗）（１８乗）
　１０　６｜　５０　　　　６　　　１７　　　２８　　　３９
　　　　　｜
　　８　７｜　４０　　　５１　　　　７　　　１８　　　２９
　　　　　｜
　　６　８｜　３０　　　４１　　　５２　　　　８　　　１９
　　　　　｜
　　４　９｜　２０　　　３１　　　４２　　　５３　　　　９
　　　　　｜　　　　（１２乗）（１７乗）（　７乗）（　２乗）
　　２１０｜　１０　　　２１　　　３２　　　４３　　　５４

　そして、２１乗からあとは、おなじことのくりかえしになります。
　つまり、２１乗は　１乗と同じ　４７、
　　　　　２２乗は　２乗と同じ　９、・・・　です。

　４７以外の場合にも、
　行に関しては、０以外の行は　１０乗，２０乗，３０乗，・・・すれば　１の行　にうつれ、
　列に関しては、０以外の列は　４乗，８乗，１２乗，・・・すれば　１の列　にうつれます。

　ですから、１０の倍数でもあって、４の倍数でもある数
つまり、１０　と　４　の公倍数の　２０乗，４０乗，６０乗，・・・すれば、
表の　１の行と１の列の数　１　に　うつれることになります。

　さらに、０の行や０の列もふくめて、
２１乗，４１乗，６１乗，・・・すれば、表の　もとの数　に　もどれることになります。

　ここで、２１乗，４１乗，６１乗，・・・というのは、
２０でわったあまりが１という数です。

　では、最初にもどりましょう。
　この５５でわったあまりの世界で、　累乗という計算に関して、
累乗してもかわらない数　は何でしょう、ということでした。

　それは、２０でわったあまりの世界で　１　という数です。

●　公開鍵と秘密鍵　●

　では、今度は　２０でわったあまりの世界で、
公開鍵と秘密鍵をもとめてみましょう。
　（くわしくは、＜お勉強＞の「公開鍵と秘密鍵」を見てね。）

　　　　　Ｙ　　０　　　１　　　２　　　３
　　　　　○　　０　　　１　　　２　　　３
　　Ｘ　□　－－－－－－－－－－－
　　０　０｜　　０　　　５　　１０　　１５
　　　　　｜
　　４　１｜　１６　　　１　　　６　　１１
　　　　　｜
　　３　２｜　１２　　１７　　　２　　　７
　　　　　｜
　　２　３｜　　８　　１３　　１８　　　３
　　　　　｜
　　１　４｜　　４　　　９　　１４　　１９

　この表は、Ｘ　と　Ｙ　のまじわったところに

　　　　４Ｘ＋５Ｙ

を計算して、２０でわったあまりを書きこんだものです。

　そして、表の見方ですが、たとえば
５でわると３あまり、４でわると１あまる数は
表の３の行と１の列の交わったところの数が　１７　ですから、
２０でわると　１７　あまる数です。

　この２０でわったあまりの世界で、かけ算を考えます。

　かけ算を考えるのは、たとえば
２乗してからさらに３乗すると、２×３＝６乗することになるからです。

　　　　　　（（□）^２）^３　＝　□^６

　そして、２０＝２×２×５　なので、２や５でわりきれる数、つまり表でいうと赤い数は、
逆の数をもたないので、さいしょからのぞいておきます。

　のこった数をあらためて表にしましょう。

　　　　　Ｙ　　　１　　　　３
　　　　　○　　１　　　　３
　　Ｘ　□　－－－－－－－
　　　　　｜
　　４　１｜　　１　　　１１
　　　　　｜
　　３　２｜　１７　　　　７
　　　　　｜
　　２　３｜　１３　　　　３
　　　　　｜
　　１　４｜　　９　　　１９

　さて、これらの数が公開鍵（になりうるもの）でしたね。
　
　では、引き続き、公開鍵　のかけ算における逆の数、
つまり　秘密鍵　をもとめましょう。

　今度は、５でわったあまりの　１，２，３，４　と
４でわったあまりの　１，３　で考えると、
（最初から、前もそうすればよかったって・・・？
　じつは、これは証明をとばしているのでかんたんなだけです。）

　□＝　１，２，３，４　では、

　　　　　　１×１≡１　（mod　５）
　　　　　　２×３≡１　（mod　５）
　　　　　　３×２≡１　（mod　５）
　　　　　　４×４≡１　（mod　５）

　○＝１，３　では

　　　　　　１×１≡１　（mod　４）
　　　　　　３×３≡１　（mod　４）

　このことから、次のようにもとまります。

公開鍵	秘密鍵
Ｙ　　　１　　　　３　　　　　○　　１　　　　３　　Ｘ　□　－－－－－－－　　　　　｜　　４　１｜　　１　　　１１　　　　　｜　　３　２｜　１７　　　　７　　　　　｜　　２　３｜　１３　　　　３　　　　　｜　　１　４｜　　９　　　１９	Ｙ　　　１　　　　３　　　　　○　　１　　　　３　　Ｘ　□　－－－－－－－　　　　　｜　　４　１｜　　１　　　１１　　　　　｜　　３　２｜　１３　　　　３　　　　　｜　　２　３｜　１７　　　　７　　　　　｜　　１　４｜　　９　　　１９

　表の見方は、公開鍵が１７なら、その秘密鍵は１３です。

　そして、公開鍵と秘密鍵が同じではきけんなので、

　　　　　１　　１１

　　　　　９　　１９

は、けっきょく公開鍵としては使い物になりません。

●　暗号（あんごう）　●

　さて、いよいよ公開鍵を使って暗号文を作り、
それを秘密鍵を使って解読（かいどく）しましょう。

　じつは、１つ１つの文字は、コンピュータ内部で２進法の数におきかえられています。
　そして、その２進法の数をてきとうにくぎり直したりして、
それに　５５でわったあまりの数を対応させます。

　そして、その数を公開鍵を使って何乗かします。

　たとえば、４７　を　公開鍵１７を使って、１７乗します。

　　４７　は　１７乗すると　（５５でわったあまりが）　４２　になります。

　さてこれを、もとの　４７　にもどせるのは、
秘密鍵１３を持っているあなただけというわけです。

　　　（（４７）^１７）^１３＝（４７）^{１７×１３}

　　　　　　　　　　　＝（４７）^２２１

　　　　　　　　　　　＝（４７）^{２０×１１＋１}

　　　　　　　　　　　＝（（４７）^２０）^１１×（４７）^１

　　　　　　　　　　　≡　１×（４７）^１　　（mod　５５）

　　　　　　　　　　　≡４７

　上の計算で、１７×１３≡１　（mod　２０）　が、じっさいに

　　　１７×１３＝２２１　で　　２２１＝２０×１１＋１

になっており、２０乗するごとに１にもどるのでしたから、
１１回おなじことをくりかえして　１　になった次の２２１乗で、
きちんともとにもどることになります。

　最後に、くぎり直しの反対をして、もとの文字におきかえなおすと
解読できるというものです。

　暗号のお話は、どうでしたか。
　きちんと証明すべきところを、かなりとばしたので
ふんいきだけになってしまいましたね。

HOME（もどる）