RSA暗号

はじめに

 この数年、量子コンピュータの研究・開発が盛んである。米国のベンチャー企業の中には株式上場を行った企業もある。現在の量子コンピュータは実用化されていないが商用化されている(実用的な計算はできないがAmazonやIBMのクラウドサービスとして提供されている)という中途半端な状態にあるが、将来2000万量子ビットまで実装されれば2048ビットのRSA暗号を8時間で解くことができると主張する論文が昨年公開された。今回の記事では、このRSA暗号について解説する。量子コンピュータを用いた解法の紹介は回を改める。

RSA暗号とは

 1970年代にMITの3人(Ron Rivest、Adi Shamir、Leonard Adleman)が発明した暗号手法である。彼らの名前の頭文字を取りRSA暗号と呼ばれる。暗号手順は以下の通りである。

  1. 最初に2つの自然数(N,r)を決める。これを公開鍵と呼ぶ。これと対応する秘密鍵sも同時に決めておく。秘密鍵は復号時に使う。
  2. 暗号化する文字を適当な方法で数値に置き換える。例えば、50音順を11から始まる自然数に一対一に対応させる。「あ」は11、「い」は12になる。このとき、「そすう」を数値に直すと、「そ」は25、「す」は23、「う」は13なので、これらを並べて「252313」を作る。この数をaと置く。
  3. a^rを計算し、この値をNで割った余りをbとする。bが暗号化された値である。

復号手順は以下の通りである。

  1. 秘密鍵sを使い、b^sを計算する。その結果をNで割った余りが復号結果aである。
  2. aを元の文字列に戻す。

秘密鍵sを見つけるには、Nを素因数分解する必要がある(後述)。従って、2つの巨大な素数の積としてNを与えておけば、現在のコンピュータ(古典コンピュータ)ではsを見つけ出すことはほぼ不可能である。以上がRSA暗号の概要である。

 次に、RSA暗号を数学的に説明するため「オイラーの定理」を紹介する。

オイラーの定理

 オイラーの定理とは次のものである。

Nを2以上の自然数とする。1以上N以下の自然数のうちNと互いに素な(1以外の公約数を持たない)数の個数をmとする。このとき、Nと互いに素な任意の自然数aに対し、a^m-1Nで割り切れる。

具体例で確認してみる。いま、N=10とする。1以上10以下の自然数のうち10と互いに素な数は、1,3,7,94つである。従って、m=4となる。N=10と互いに素なa=3を選ぶと、a^m-1=3^{4}-1=80=10\times8となる。これはN=10で割り切ることができる。従って上の定理が成り立つ。
 後の説明のため上の定理を合同式を用いたものに書き換えておく。

Nを2以上の自然数とする。1以上N以下の自然数のうちNと互いに素な(1以外の公約数を持たない)数の個数をmとする。このとき、Nと互いに素な任意の自然数aに対し次式が成り立つ。

(1)    \begin{equation*} a^m\equiv1\;({\rm mod}\;\;N) \end{equation*}

ここで、x\equiv y\;(\rm{mod}\;\;N)とは、xNで割った余りがyであること表す。さらに、RSA暗号に使われる次の事実も紹介しておく。

Nを2以上の自然数とする。1以上N以下の自然数のうちNと互いに素な数を小さい順に\{b_1,\cdots,b_m\}と並べる。これを数列Bとする(常にb_1=1である)。このとき、Bの中の任意の値b_iを数列内の全ての数に掛け、Nで割った余りを並べると、数列Bを並べ替えたものが得られる。

これも具体例で確認する。N=5のとき、B=\{1,2,3,4\}である。Bから2を選ぶ。Bの全ての数に2を掛けると\{2,4,6,8\}となる。これをN=5で割った余りを並べると\{2,4,1,3\}となる。これはBを並べ替えたものである。同じことが2以外の数\{1,3,4\}を掛けた場合も成り立つ。
 ここでの注目点は、Bの中に必ず1という要素が存在することである。つまり、b_i\times b_j\equiv1\;({\rm mod}\;\;N)となるペア(b_i,b_j)が必ず存在するということである。この事実を後の説明で使用する。

RSA暗号の詳細

 上で紹介した定理を用いてRSA暗号を再度詳しく説明する。まず最初に2つの異なる素数pqを用意し、それらの積をNとする。実際の暗号化では巨大な素数から選ばれるので、Nを素因数分解し元の素数pqを求めることはほぼ不可能となる。ここでは説明の都合上、p=3,q=11とする。従って、N=33である。1以上33以下の自然数のうちN=33と互いに素な数の個数は20(=m)である。1以上20以下の自然数で20と互いに素な数の組はB=\{1,3,7,9,11,13,17,19\}である。Bの中から適当に数rを選ぶ。ここではr=7を取る。7Bの全ての数に掛けると、\{7,21,49,63,77,91,119,133\}となる。これらを20で割った余りは、\{7,1,9,3,17,11,19,13\}となる。これはBを並べ替えたものである。ここまでの議論で、Bの2番目の要素3r=7を掛けてm=20で割ると1余ることが分かる。

(2)    \begin{equation*} 3\times 7\equiv1\;(\rm{mod}\;\;20) \end{equation*}

上の式より秘密鍵s=3が決まる。つまり

(3)    \begin{equation*} rs\equiv1\;({\rm mod}\;\;m) \end{equation*}

が成り立つようにsを決めるのである。公開鍵は(N,r)、秘密鍵はsとなる。

 準備ができたので実際に暗号化を行う。ここでは「す」を暗号化してみる。

  1. 先と同じように50音順を11から始まる自然数に割り当てると「す」は23(=a)である。
  2. a^rNで割った余りを求める。これが暗号化された値bになる。いまの場合、23^733で割った余りなので23(=b)である。合同式で書けばb\equiv a^r\;({\rm mod}\;\;N)である。

ここで、式(1)のオイラーの定理を考える。m=20,N=33としたから

(4)    \begin{equation*} a^m\equiv1\;({\rm mod}\;\;N)\iff a^{20}\equiv1\;(\rm{mod}\;\;33) \end{equation*}

が成り立つ。ところで

(5)    \begin{equation*} b\equiv a^r\;(\rm{mod}\;\;33) \end{equation*}

が成り立つから、両辺をs=3乗すると

(6)    \begin{eqnarray*} b^s &\equiv&  a^{rs}\;(\rm{mod}\;\;33) \\ &\equiv& a^{21}\;(\rm{mod}\;\;33) \\ &\equiv& a^{20+1}\;(\rm{mod}\;\;33) \\ \end{eqnarray*}

となる。ここでr=7を用いた。最後の式にa^{20}\equiv1(式(4))を使うと

(7)    \begin{equation*} b^s\equiv a \;(\rm{mod}\;\;33) \end{equation*}

となる。つまり、暗号化された値bs乗しNで割った余りを求めれば、元の値aを得ることができる。rsの値が式(3)を満たすように決められているのでrsmで割ったとき必ず1余る数であることが保証され、上の変形が成り立つのである。
 
 さて、公開鍵(N,r)から秘密鍵sを見破るにはどのような情報が必要になるであろうか。

(8)    \begin{equation*} rs\equiv1\;({\rm mod}\;\;m) \end{equation*}

であったから、mが分かれば良さそうである。しかし、mN=pqを素因数分解しない限り求めることはできない。なぜなら、m=(p-1)(q-1)が成り立つからである。先に見たように実際の暗号化ではpqは巨大な素数が選択される。従って、Nを素因数分解することは現実的にはほぼ不可能であり、従ってmを求めることもできない。

まとめ

 今回は、RSA暗号について説明した。2040年ごろに2000万量子ビットが実現するだろうとDARPAが予想しているが、さてどうなるか?

参考文献

  • 素数ほどステキな数はない
  • Kumada Seiya

    Kumada Seiya

    仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

    最近の記事

    • 関連記事
    • おすすめ記事
    • 特集記事

    アーカイブ

    カテゴリー

    PAGE TOP