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-1はNで割り切れる。

具体例で確認してみる。いま、N=10とする。1以上10以下の自然数のうち10と互いに素な数は、1,3,7,9の4つである。従って、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)とは、xをNで割った余りが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つの異なる素数pとqを用意し、それらの積をNとする。実際の暗号化では巨大な素数から選ばれるので、Nを素因数分解し元の素数pとqを求めることはほぼ不可能となる。ここでは説明の都合上、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を取る。7をBの全ての数に掛けると、\{7,21,49,63,77,91,119,133\}となる。これらを20で割った余りは、\{7,1,9,3,17,11,19,13\}となる。これはBを並べ替えたものである。ここまでの議論で、Bの2番目の要素3にr=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^rをNで割った余りを求める。これが暗号化された値bになる。いまの場合、23^7を33で割った余りなので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*}

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

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

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

まとめ

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

参考文献

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

    • Kumada Seiya

    Kumada Seiya

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

    最近の記事

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

    アーカイブ

    カテゴリー

    PAGE TOP