クイックノート

ちょっとした発見・アイデアから知識の発掘を

暗号の仕組み~RSA暗号~

RSA暗号は代表的な公開鍵暗号の一つです。

公開鍵暗号ということは、
暗号化の鍵と、復号化の鍵が別になっていて、
誰でも暗号化できるけど、復号化は一人しかできない
ような状況を作れる暗号ということです。

公開鍵暗号として機能するためには、
最低限以下の3つの性質が担保される必要があります。

  • 暗号化して復号化すると元の文章に戻る
  • 暗号文から簡単に元の文章を推測できない
  • 公開鍵から秘密鍵を簡単に推測できない

上の二つの条件は、暗号として当然満たすべき性質で、
3つ目の条件は公開鍵暗号に独特の性質です。

では、RSA暗号は、どのようにこれらの性質を担保しているか、
みていきましょう。

文章が元に戻るとは

ある文章に対して、暗号化をして、復号化をすると
元に戻るということは、
何か操作したはずなのに、何もしていないのと同じ操作
をしたことになります。

そのため、暗号では、この何もしてないのと同じ操作を活用します。

RSAで使われているのは、
ある数字での割り算の余りが元の数字に戻ってくるような操作です。

何もしなければ当然同じ

話を簡単にするため、暗号文は数字だと考えましょう。
例えば、2という数字を暗号化することにします。
そして、割り算は、10で行うことにしましょう。

2に何もしなければ、2を10で割った余りは2です。

累乗すると余りが変わる

何もしないという操作は1乗する操作2^1と考えることができます。

では、2を何度かかけた数字の余りはどうなるでしょう。

累乗 累乗の値 10 で割った余り
2^1 2 2
2^2 4 4
2^3 8 8
2^4 16 6
2^5 32 2

このように、何乗するかによって、
10で割った余りは変わってきます。

一周して元に戻る

上の表を見てみると、余りが 2,4,8,6,2 となり、
元の2に戻ってきたことがわかります。

確かめてみればすぐにわかりますが、
この後も 2,4,8,6,2 を繰り返します。

このように、2の累乗は5乗、9乗、13乗と
4乗毎に基に戻ってくることが分かります。

どの数字も一定回数の累乗で元に戻る

上では2の累乗だけでしたが、
実はどの数字の累乗であっても、
5乗、9乗、...すると基に戻ることが分かります。

つまり、ある数字を5,9,...乗すると、
10で割った余りが元に戻る
ということです。
累乗という操作を行っているのに、元に戻ることから、
暗号化と復号化に使えそうな現象ですね。

これは、(一部は)オイラーの定理として知られています。

オイラーの定理

オイラーの定理とは

aとnを互いに素な正の整数としたとき、
 a^{\phi(n)} \mod n = 1
が成り立つ。
ただし、\phi(n)オイラーのファイ関数

というものです。

今の例の場合、n=10で、10と互いな素な正の整数は、
n=1,3,7,9 です。
また、フェルマーのファイ関数はこの互いに素な正の整数の数を表し、
 \phi(n) = 4 です。

つまり、1,3,7,9 については、オイラーの定理より、
4乗すると余りが1になるので、
もう一度かけると、つまり、5乗すると,
丁度あまりが、1,3,7,9になります。

互いに素でない場合

残りの10と互いに素でない正の整数 2,4,5,8 については、
一工夫必要です。

互いに素でないのは、共約数が含まれていることを指しており、
例えば、10と2では2が共役数となります。

この共約数2で10を割れば、5になりますが、
こうすることで、共約数がなくなり、互いに素な5と2を考えることができます。

累乗 累乗の値 10 で割った余り 5で割った余り
2^1 2 2 2
2^2 4 4 4
2^3 8 8 3
2^4 16 6 1
2^5 32 2 2

上の表を見ると、4乗で5で割った余りが1になっていることが分かります。
実は、\phi(5)=4であり、オイラーの定理から、
他の数字4,8も4乗で5で割った余りが1になることが分かります。

一方、10 と 5 については、共約数が5であり、
2で割ることを考えます。

 \phi(2) = 1 であり、オイラーの定理から、
1乗、つまり、何もしなくても、5を2で割った余りは1です。
これは、4乗しても余りが1になることを意味しています。

実は、10 のように二つの素数の積p,qで表される数字は、
\phi(n) = \phi(p) \times \phi(q)
が成り立ちます。

そのため、\phi(n) 乗すると、pかqで割った余りが1になっていて、
 \phi(n) + 1 乗で余りが元に戻るのです。

より完全な証明には中国剰余定理を用います。
が、ここでは省略します。

このような都合の良さもあってか、
RSA暗号では、nを決める時に2つの素数の積として決めています。

暗号化と復号化に分ける

一定回数(\phi(n)+1,2\phi(n)+1,\cdots)累乗すれば、
余りが元に戻ることが分かりました。

ある数のa乗のb乗を行うと、
a\times b乗を行うことと同じであることを思い出しましょう。

a\times b = m\phi(n)+1 (mは整数)となるようなa,bを選び、
暗号化では元の文章をa乗し、
復号化では暗号文をb乗すると、
元の文章のa\times b乗することになるので、
元の文章を得ることができます。

そして、このとき、暗号の鍵はaであり、
復号の鍵はbであるので、
異なる鍵を使った暗号化が可能になります。

暗号文の解読は難しい?

さて、累乗の回数を分けることで、
別々の鍵で暗号化と復号化ができ、
元の文章に戻せることも分かりましたが、
この暗号文は解読できないほど複雑なのでしょうか?

暗号化の手順をまとめると、
元の文章xに対して、暗号文は
y = x^a \mod n
となっています。

暗号化に必要な情報は累乗の回数aと、割る数nなので、
これらは公開されており、
a,n と暗号文yが与えられた時に、
元の文章xが推定されてしまわないかが問題となります。

これは、nの割り算の世界の中で、yのa乗根を求める問題ですが、
これは計算に時間がかかる問題とされています。

つまり、暗号化の方法を知っているからといって、
暗号文を解読することは難しいということになります。

公開鍵から秘密鍵は推測できない?

公開鍵と秘密鍵は無関係ではないので、
その関係性を使って、公開鍵から秘密鍵が推測できてしまうと、
暗号が意味を成さなくなってしまいます。

これは、公開鍵と秘密鍵の生成方法にもかかわる問題ですが、
まだ、RSA暗号の具体的な鍵の生成方法については説明していませんでした。

なので、まずは鍵の生成方法について見ていきましょう。

鍵の生成

上で説明したように、公開鍵a秘密鍵bの間には、
a\times b = m\phi(n)+1 (mは整数)
の関係が満たされることが必要でした。

この関係を満たすような鍵を生成するため、RSA暗号では、 次のような手順で鍵の生成を行います。

  1. 異なる2つの素数p,qを用意する
  2.  n= p \times q とする
  3. 公開鍵 a を\phi(n) = (p-1)(q-1)と互いに素な数から選ぶ
  4. 秘密鍵 b を  a \times b \phi(n)で割った余りが1になるように設定

実は、nを二つの素数の掛け算とすることで、
オイラーのファイ関数が (p-1)(q-1)のように単純な形で表せることが分かります。

弱点は素数

RSA暗号では、2つの素数p,qを使って鍵を生成してますが、
この素数が分かってしまうと、簡単に秘密鍵を計算できてしまいます。
それは、上の鍵の生成手順をなぞればいいだけなので当然ですね。

なので、この2つの素数p,qについても、
他の人には知られないように、しなければいけません。

他の人に直接公開されている情報は、n,a ですが、
a の方は、p,q に若干関係があるものの、
 (p-1)(q-1)と互いに素な数という多くの候補の中から選ばれたものなので、
a から、pやqを知ることは難しいと考えられます。

一方、nの方は、pとqの掛け算なので、
掛け算の分解、つまり、素因数分解をされてしまうと、
p,qがばれて、秘密鍵や暗号文の内容までばれてしまうことになります。

ところが、一般に素因数分解は計算に時間を要する問題とされているので、
暗号の安全性が担保されています。

また、ファイ関数の値(p-1)(q-1)についても、
秘密鍵がばれる要因となりえますが、
これも、元の素数p,qを知らない限りは、計算が困難であるため、
結局、素因数分解が解けない限りは暗号は安全だろうと考えられています。

RSA 暗号の特徴

RSA 暗号は、累乗の余りが元に戻ることを利用した暗号でした。

暗号化と復号化で、それぞれ累乗し、
その合計で丁度基に戻ってくるように設計されています。

一方、累乗は、逆に計算しても結果が同じになる性質があります。
 {x^a}^b = {x^b}^a = x^{ab}

つまり、暗号化をしてから復号化しても、
復号化してから暗号化しても、
元の文章に戻るということです。

通常、公開鍵を使って暗号化するのですが、
RSA暗号では秘密鍵を使って暗号化することもできることになります。

このRSA暗号の独特な性質は、電子証明書などの技術に生かされています。

プライバシーポリシー