SSブログ

No.311 - 高校数学で理解するRSA暗号の数理(2) [科学]

\(\newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\mr}[1]{\mathrm{#1}} \newcommand{\br}[1]{\textbf{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\sb}{\subset} \newcommand{\sp}{\supset} \newcommand{\al}{\alpha} \newcommand{\sg}{\sigma}\newcommand{\cd}{\cdots}\)

4. RSA暗号の証明


4.1 RSA暗号

RSA暗号の公開鍵・秘密鍵の作成方法と暗号化・復号化の計算式を定理として記述すると次の通りです。

\(p\) と \(q\) を相異なる素数とし、\(n=pq\) とする。

\(e\) を \(m=(p-1)(q-1)\) と素な数、\(d\) を、\(de\equiv1\:(\mr{mod}\:m)\) を満たす数とする。この前提で、

暗号化:\(P^e\equiv C\:(\mr{mod}\:n)\) ならば
復号化:\(C^d\equiv P\:(\mr{mod}\:n)\) である。

( \(P\):平文。\(C\):暗号文 )


RSA暗号において、暗号化・復号化に必要なのは公開鍵の \((e,\:n)\) と 秘密鍵の \(d\) であり、それらを生成するのに使った \(p\) と \(q\) は不要です。というより、\(p\) と \(q\) ないしは \((p-1)(q-1)\) が漏れると暗号が破られてしまうので、これらの数は鍵を生成した後は破棄(情報を安全に抹消)する必要があります。

以下に、上の「復号化の式」が成り立つことを証明します。まず合同式の累乗 1.2 を使って「暗号化の式」の両辺を \(d\) 乗すると、

\(C^d\equiv P^{de}\:(\mr{mod}\:pq)\) \(\cd\:(1)\)

となります。ここで、\(de\equiv1\:(\mr{mod}\:(p-1)(q-1))\) なので、\(de=k(p-1)(q-1)+1\) と表現できます。従って、

\(P^{de}=P^{k(p-1)(q-1)+1}\)

となります。累乗を分解すると、

\(P^{de}=(P^{(p-1)(q-1)})^k\:\cdot\:P\) \(\cd\:(2)\)

です。一方、フェルマの小定理 3.1 により、

\(P^{p-1}\equiv1\:(\mr{mod}\:p)\)

となります。合同式の累乗の定理 1.2 により、この式の両辺を \(q-1\) 乗すると、

\(P^{(p-1)(q-1)}\equiv1\:(\mr{mod}\:p)\) \(\cd\:(3)\)

が得られます。さらに、フェルマの小定理 3.1 により、

\(P^{q-1}\equiv1\:(\mr{mod}\:q)\)

ですが、両辺を \(p-1\) 乗して、

\(P^{(p-1)(q-1)}\equiv1\:(\mr{mod}\:q)\) \(\cd\:(4)\)

となります。ここで、\(p\) と \(q\) は互いに素なので、1.5 の合同式の定理を \((3),\:(4)\)に適用すると、

\(P^{(p-1)(q-1)}\equiv1\:(\mr{mod}\:pq)\)

を導くことができます。この式の両辺を 1.2 を使って \(k\) 乗すると、

\((P^{(p-1)(q-1)})^k\equiv1\:(\mr{mod}\:pq)\)

であり、さらに両辺に合同式の乗算 1.1c を使って \(P\) をかけると、

\((P^{(p-1)(q-1)})^k\:\cdot\:P\equiv P\:(\mr{mod}\:pq)\) \(\cd\:(5)\)

となります。従って、\((1),\:(2),\:(5)\) を合わせると、

\(C^d\equiv P\:(\mr{mod}\:pq)\)

となり、RSA暗号の復号化の式が証明できました。

最小公倍数
以上の証明の過程を改めて振り返ってみると、「\(m\) が \((p-1)\) の倍数であり、かつ \((q-1)\) の倍数」であれば、RSA暗号は成立することが分かります。つまり「\(m\) が \((p-1)\) と \((q-1)\) の公倍数」であれば成立する。そのような \(m\) は、

\(m=n_p(p-1)\)
\(m=n_q(q-1)\)

の2通りに表現できます。すると、\(de\equiv1\:(\mr{mod}\:m)\) なので、

\(de=k_p(p-1)+1\)
\(de=k_q(q-1)+1\)

と2通りに表せます。ここから、

\(P^{de}=P^{k_p(p-1)+1}\)
\(\phantom{P^{de}}=P\cdot(P^{p-1})^{k_p}\)
\(\phantom{P^{de}}\equiv P\:(\mr{mod}\:p)\)

\(P^{de}=P^{k_q(q-1)+1}\)
\(\phantom{P^{de}}=P\cdot(P^{q-1})^{k_q}\)
\(\phantom{P^{de}}\equiv P\:(\mr{mod}\:q)\)

\(P^{de}\equiv P\:(\mr{mod}\:pq)\)
\(C^{d\phantom{e}}\equiv P\:(\mr{mod}\:pq)\)

となって、平文が復元できます。この考察から分かるのは、\(m\) の最小値は「\((p-1)\) と \((q-1)\) の最小公倍数」ということです。最小公倍数を \(\mr{lcm}\) で表すと、

\(m=\mr{lcm}(p-1,q-1)\)

であればRSA暗号は成立します。そして一般に、

\(\mr{lcm}(a,b)=\dfrac{a\times b}{\mr{gcd}(a,b)}\)

です。最大公約数・\(\mr{gcd}\) は「2. ユークリッドの互除法」を使って高速に計算できるので \(p\) や \(q\) が巨大数であっても最小公倍数・\(\mr{lcm}\) は計算可能です。

累乗の剰余を求めるアルゴリズム
RSA暗号では、暗号化と復号化で "累乗(冪乗)の剰余"(冪剰余と呼ぶ)を求める計算が出てきます。この計算で使う公開鍵 \((e,\:n)\) も秘密鍵 \(d\) も、また平文や暗号文も、実用的には\(10\)進数で\(300\)桁とか、そういった巨大な数です。

しかし巨大な数であっても、累乗の剰余計算ができるアルゴリズムがあります。その一つとして、ここでは「2分割法」で説明します。前回の「RSA暗号の例題」であげた、

\(C=82^{133}\) \(\mathbf{mod}\) \(143=4\)

の例で説明します。考え方としては「2.ユークリッドの互除法」と同じで、問題をより "小さな問題" に置き換えるというものです。つまり、\(133\)乗を求める代わりに

\(C_1=82^{66}\) \(\mathbf{mod}\) \(143\)

が求まったとしたら、\(C\) は、

\(C=(C_1\cdot C_1\cdot82)\) \(\mathbf{mod}\) \(143\)

で計算できます。さらに、その \(C_1\) は、

\(C_2=82^{33}\) \(\mathbf{mod}\) \(143\)

が求まったとしたら、

\(C_1=(C_2\cdot C_2)\) \(\mathbf{mod}\) \(143\)

で計算できます。この2分割を次々と続けていくと、\(82\)の\(16\)乗、\(8\)乗、\(4\)乗、\(2\)乗、\(1\)乗を \(143\) で割った剰余が求まれば良いことになります。これを逆にたどって電卓で \(82^k\) \(\mathbf{mod}\) \(143\:(k=1,\) \(2,\) \(4,\) \(8,\) \(16,\) \(33,\) \(66,\) \(133)\) を順次計算してみると、

\(\,82^k\) \(\mathbf{mod}\) \(143\)
\(\,82^1\) \(82\,\)
\(\,82^2\) \(3\,\)
\(\,82^4\) \(9\,\)
\(\,82^8\) \(81\,\)
\(\,82^{16}\) \(126\,\)
\(\,82^{33}\) \(103\,\)
\(\,82^{66}\) \(27\,\)
\(\,82^{133}\) \(4\,\)

となり、答の \(4\) が求まりました。これをプログラム言語で記述すると次の通りです。


4.2 2分割法による冪剰余計算

\(P^e\) \(\mathbf{mod}\) \(n\) を求める関数 RSA(Javascriptで記述)。

function RSA( P, e, n ) {
 if( e == 1 ) return P % n; //①
 else {
  var h=RSA(P, Math.floor(e/2), n); //②
  var c=( h * h ) % n; //③
  if( e % 2 == 0 ) return c; //④
  else return ( c * P ) % n; //⑤
 }
}


次はこのアルゴリズムの補足説明です。

①  e が 1 なら P % n が答なので、それを関数値として返す。% は Javascript の剰余演算子で、\(P\) \(\mathbf{mod}\) \(n\) と同じ意味。

②  e が 1 でないときは、e を半分(約半分)にして答を求める。Math.floor() は小数点以下を切り捨てる Javascript の組み込み関数。Javascript では実数と整数の区別がないので必要。

③  その "半分の答" を2乗し、剰余を求めて仮の答 c とする。

④  e が偶数なら c が正しい答。それを関数値として返す。

⑤  e が奇数なら c にさらに P を掛け、剰余を求めて関数値として返す。

\(e,\:n,\:d\) が10進数で300桁程度の巨大数とします。\(2^{1000}\) は約300桁の数なので、"2分割法" を使うと1000回程度の剰余計算を繰り返すこと答が求まります。この程度の計算は現在のコンピュータで可能です。ただし可能といっても 1000回の繰り返しはさすがに大変なので、実用的にはこれを高速化する手法がいろいろと開発されています。

2. ユークリッドの互除法」で、公開鍵 \((e,\:n)\) の \(e\) と秘密鍵 \(d\) について、たとえ巨大数であっても高速に算出できることを書きました。それに加えて、暗号化・復号化で使われる「巨大数の累乗の剰余計算」も算出可能であり、RSA暗号の全体が "計算可能" であることが証明できました。


今までのまとめ


実用的な RSA暗号を構成するときに必要なのは、巨大な素数 \(p,\:q\) (\(10\)進数で150桁程度かそれ以上)です。こういった素数をどうやって作り出すか、また素数であることの判定をどうやってするかの計算手法については割愛します。

今までのRSA暗号についての説明全体をまとめると、以下の2点になるでしょう。

◆  RSA暗号は数論(整数論)の基礎から構成されている(合同、ユークリッドの互除法、フェルマの小定理、・・・・・)。

◆  RSA暗号における公開鍵・秘密鍵の生成式、暗号化・復号化の式は、実用的に計算可能である。

RSA暗号は現代の情報化社会にとって必須のものであり、社会インフラの重要な構成要素です。それは、数学が実用的に、かつ直接的に社会に役立っている例なのでした。

 
RSA暗号とオイラー関数・オイラーの定理 
 

RSA暗号の成立性の証明はこれまでで尽きていますが、以降はRSA暗号と関係が深い「オイラー関数」を説明し、次に「オイラーの定理」を導いて、そこからRSA暗号の原理を導出します。まずその前提としての「中国剰余定理」です。


5. 中国剰余定理


5~6世紀頃の中国で成立した算術書『孫子算経』に、

3で割ると2余り
5で割ると3余り
7で割ると2余る数は何か

という問題が書かれています。答は23ですが、これを一般化した定理を「中国剰余定理」と呼んでいます。

5.1 中国剰余定理

与えられた \(k\) 個の整数、\(m_1,\:m_2,\:\cd,\:m_k\) は、どの2つをとっても互いに素とする。このとき任意に与えられた\(k\) 個の整数、\(a_1,\:a_2,\:\cd\:,\:a_k\) についての \(k\) 個の式、

\(x\equiv a_1\:(\mr{mod}\:m_1)\)
\(x\equiv a_2\:(\mr{mod}\:m_2)\)
 \(\vdots\)
\(x\equiv a_k\:(\mr{mod}\:m_k)\)

同時に満たす解 \(x\) が存在し、この解は \(M=m_1m_2\:\cd\:m_k\)を法として唯一である。


\(x_1\) と \(x_2\) の2つの解があったとします。すると、\(\mr{mod}\:m_1\) の式から、

\(x_1\equiv a_1\:(\mr{mod}\:m_1)\)
\(x_2\equiv a_1\:(\mr{mod}\:m_1)\)

となり、1.1b により、

\(x_1-x_2\equiv0\:(\mr{mod}\:m_1)\)

となります。同様に、\(\mr{mod}\:m_2\) の式から、

\(x_1-x_2\equiv0\:(\mr{mod}\:m_2)\)

が言えます。\(m_1\) と \(m_2\) は互いに素なので、ここで 1.5 を適用すると、

\(x_1-x_2\equiv0\:(\mr{mod}\:m_1m_2)\)

となります。以上のことは \(m_3\) から \(m_k\) までの全ての式についても言えるので、1.5 を順次適用することにより、

\(x_1-x_2\equiv0\:(\mr{mod}\:m_1m_2\:\cd\:m_k)\)

となります。つまり、

\(x_1\equiv x_2\:(\mr{mod}\:M)\)

です。従って、解 \(x\) が複数あったとしても、それらは全て \(M\) を法として合同になります\((\)= 解は \(M\) を法として唯一)。


ここで

\(M_i=\dfrac{M}{m_i}\)

とおくと、\(\mr{gcd}(m_i,M_i)=1\) なので、2.3 により、

\(M_i\cdot N_i\equiv1\:(\mr{mod}\:m_i)\)

となる \(N_i\) が存在します。これを使って、

\(x=\displaystyle\sum_{i=1}^{k}a_iM_iN_i\)

とおくと、それが解になります。なぜなら \(M_i\) の作り方から \(i\) 番目の項以外の項は \(m_i\) で割り切れるので、\(i\) 番目の項単独で「\(m_i\) を法として \(x\) と合同」になります。つまり、

\(x\equiv a_iM_iN_i\:(\mr{mod}\:m_i)\)

です。一方、合同の性質の 1.4 において \(y=1\) とおくと 1.4 は、

\(ax\equiv b\:(\mr{mod}\:m)\) かつ、
\(\phantom{a}x\equiv1\:(\mr{mod}\:m)\) のとき、
\(a\phantom{x}\equiv b\:(\mr{mod}\:m)\)

となります。1.4 の「\(x\) が \(m\) と互いに素」という条件は、\(x\equiv1\:(\mr{mod}\:m)\) で満たされています。このことを適用すると、

\(x\equiv a_iM_iN_i\:(\mr{mod}\:m_i)\)
\(M_i\cdot N_i\equiv1\:(\mr{mod}\:m_i)\)

という2つの条件から、

\(x\equiv a_i\:(\mr{mod}\:m_i)\)

となります。これが全ての \(i\) について成り立つ。従って \(x\) が解であることが証明できました。また前段で証明したように全ての解は \(M\) を法として合同なので、\(x\) が唯一の解です。


中国剰余定理の意味を直感的に理解するために、\(k=2\)、\(m_1=3\)、\(m_2=4\)、\(M=12\) とし、\(x\) の全て解についての対応表を作ってみると次の通りになります。

\(\overset{\:}{x}\,\) \(\mr{mod}\:3\) \(\mr{mod}\:4\)
\(\,0\,\) \(0\,\) \(0\,\)
\(\,1\,\) \(1\,\) \(1\,\)
\(\,2\,\) \(2\,\) \(2\,\)
\(\,3\,\) \(0\,\) \(3\,\)
\(\,4\,\) \(1\,\) \(0\,\)
\(\,5\,\) \(2\,\) \(1\,\)
\(\,6\,\) \(0\,\) \(2\,\)
\(\,7\,\) \(1\,\) \(3\,\)
\(\,8\,\) \(2\,\) \(0\,\)
\(\,9\,\) \(0\,\) \(1\,\)
\(\,10\,\) \(1\,\) \(2\,\)
\(\,11\,\) \(2\,\) \(3\,\)

この表をみると、\(0,\:1,\:2\) を繰り返し並べ(\(\mr{mod}\:3\) の列)、\(0,\:1,\:2,\:3\) を繰り返し並べると(\(\mr{mod}\:4\) の列)、\(3\) と \(4\) が互いに素の関係にあるために、\((0,\:0)\) は \(3\times4=12\) 回繰り返さないと現れないことが分かります。その間、\(x\) は\(12\)未満の全ての数をとり、 \((\mr{mod}\:3,\:\mr{mod}\:4)\) の全ての組み合わせが現れる。このため、 \((\mr{mod}\:3,\:\mr{mod}\:4)\) の1つの組み合わせに対して解 \(x\) が唯一になるわけです。この状況は \(k\) の値にかかわらず、\(m_i\:(1\leq i\leq k)\) のどの2つをとっても互いに素である限り変わらない。

「互いに素」なゆえに成立するこのイメージは、次のオイラー関数の証明に役立ちます。


6. オイラー関数


Leonhard_Euler.jpg
レオンハルト・オイラー
(Wikipediaより)
オイラー(1707-1783)はスイスのバーゼルに生まれた18世紀ヨーロッパの大数学者です。その業績は多岐に渡り、オイラー ・・・(何とか)という定理や公式、関数、数式、等式、図などがどっさりとあります。

以下の「オイラー関数」は、一般に関数名をギリシャ文字の \(\varphi\)(ファイ)で表記するので「オイラーの \(\varphi\) 関数」とも呼ばれています。数論ではたびたび出てくる関数です。

余談ですが、オイラーは20歳台後半で右目を失明しました。ここに掲載した肖像画にもそれが現れています。


6.1 オイラー関数

オイラー関数 \(\varphi\) の定義は以下のとおり。

\(\varphi(m)\) : \(m\) 以下で、\(m\) とは互いに素な自然数の個数

\(p\)、\(q\) を相異なる素数とするとき、オイラー関数は次の性質をもつ。

(素数のオイラー関数値)

  6.1a \(\varphi(p)=p-1\)

(素数の積のオイラー関数値)

  6.1b \(\varphi(pq)=(p-1)(q-1)\)

(素数の累乗のオイラー関数値)

  6.1c \(\varphi(p^{\al})=p^{\al}-p^{\al-1}\)

なお「互いに素」は、すなわち「最大公約数が \(1\)」であり、\(\mr{gcd}(1,1)=1\)なので、\(\varphi(1)=1\)。


まず 6.1a ですが、素数 \(p\) は \(p\) 未満のすべての自然数と互いに素です。従って、\(\varphi(p)=p-1\) です。

次に \(pq\) 以下の数で、\(p\) で割り切れるのは \(pq\) を含んで \(q\) 個、\(q\) で割り切れるのは \(pq\) を含んで \(p\) 個です。\(pq\) 以下の数の全体は \(pq\) 個なので、\(pq\) 以下の数で \(p\) でも \(q\) でも割り切れない数の個数(= \(pq\) と互いに素な数の個数)は、

\(\varphi(pq)=pq-p-q+1\)
\(\phantom{\varphi(pq)}=(p-1)(q-1)\)

です(6.1b)。上の式の1行目で、\(-p\) と \(-q\) には \(pq\) の分が重複しているので \(+1\) してあります。

さらに、\(p^{\al}\) 以下の数で、\(p\) の倍数は全て \(p^{\al}\) と共通の約数 \(p\) を持ちます。\(p^{\al}\) 以下の \(p\) の倍数の個数は \(p^{\al}\) を含んで、

\(\dfrac{p^{\al}}{p}=p^{\al-1}\)

なので、\(\varphi(p^{\al})\)は、

\(\varphi(p^{\al})=p^{\al}-p^{\al-1}\)

となります(6.1c)。このオイラー関数に関しては、次の「乗法性」が重要です。


6.2 オイラー関数の乗法性

\(\mr{gcd}(m,n)=1\)( \(m\) と \(n\) は互いに素 )のとき

\(\varphi(mn)=\varphi(m)\varphi(n)\)


一般に、関数のこのような性質を "乗法性"、このような関数を "乗法的関数" と呼んでいます。証明は3段階で行います。キーワードは「中国剰余定理」と「1対1対応」です。

第1段
\(0\leq i < m\)、\(0\leq j < n\) である数を選び \((i,j)\) のペアを作ります。\(i\) の選択肢は \(m\) 個、\(j\) の選択肢は \(n\) 個で、それぞれ独立して選ぶので、相異なる \((i,j)\) のペアの数は \(mn\) 個です。

仮定により \(m\) と \(n\) は互いに素です。従って、それぞれの \((i,j)\) のペアについて中国剰余定理 5.1 により、

\(x\equiv i\:(\mr{mod}\:m)\)
\(x\equiv j\:(\mr{mod}\:n)\)

を同時に満たす \(x\) が、\(mn\) を法として唯一存在します。つまり \(0\leq x < mn\) の範囲では \(x\) が一意に決まります。これは \(\bs{(i,j)}\) のペアに \(\bs{x}\) を対応づけられることを意味します。

逆に、\(0\leq x < mn\) である \(x\) を1つ選ぶと、それに対して \(\mr{mod}\:m\) と \(\mr{mod}\:n\) を求めて \((i,j)\) のペアと対応づけられる。つまり、

\(mn\) 個の \((i,j)\) のペアと \(mn\) 個の \(x\) の間に1対1対応が作れる

ことになります。

第2段
第1段の方法で作った「1対1に対応する \((i,j)\) のペアと \(x\)」については、

\(i\) が \(m\) と素であるなら、\(x\) も \(m\) と素

になります。なぜなら、もし \(x\) と \(m\) に共通の約数 \(a\) があったとすると(= \(a|x\) でかつ \(a|m\) )、中国剰余定理の前提から

\(x=km+i\)

と表せるので \(a|i\) となり、\(a\) が \(i\) と \(m\) の共通の約数にもなってしまって「\(i\) が \(m\) と素」という仮定に反するからです。全く同様に、

\(j\) が \(n\) と素であるなら、\(x\) も \(n\) と素

です。この2つを合わせると、

\((i,j)\) のペアにおいて「\(i\) が \(m\) と素」で、かつ「\(j\) が \(n\) と素」であれば、「1対1対応がつけられた \(x\) は \(m\) と \(n\) の2つの数と素」

になります。「\(x\) が \(m\) と \(n\) の2つの数と素」であることは「\(x\) が \(mn\) と素」ということにほかなりません。つまり、

\((i,j)\) のペアで「\(i\) が \(m\) と素」であり、かつ「\(j\) が \(n\) と素」であれば「\((i,j)\) と1対1対応がつけられた \(x\) は \(mn\) と素」

です。その逆に「\(x\) が \(mn\) と素」であるなら「\(x\) は \(m\) と \(n\) の2つの数と素」です。そうすると中国剰余定理の前提から「\(i\) は \(m\) と素」でかつ「\(j\) は \(n\) と素」になります。つまり、まとめると、

\((i,j)\) のペアのうち「\(i\) が \(m\) と素で、\(j\) が \(n\) と素であるペア」は、「\(mn\) と素である \(x\)」と1対1の対応関係がつけられる

ことになります。そして1対1の対応関係がつく集合の要素の数は等しい。ここが証明の根幹です。

第3段
オイラー関数の定義により、

\(m\) と素である \(i\) の個数は \(\varphi(m)\)

\(n\) と素である \(j\) の個数は \(\varphi(n)\)

です。\(i\) と \(j\) は独立に選んでいるので、

\((i,j)\) のペアのうち、「\(i\) が \(m\) と素」で「\(j\) が \(n\) と素」のペアの個数は、\(\varphi(m)\varphi(n)\)

です。さらにオイラー関数の定義により、

\(mn\) と素な \(x\) の個数は \(\varphi(mn)\)

になります。第2段で証明したように「\(i\) が \(m\) と素」で「\(j\) が \(n\) と素」である \((i,j)\) のペアと、\(mn\) と素である \(x\) は1対1の対応関係にあります。従ってその個数は等しく、

\(\varphi(mn)=\varphi(m)\varphi(n)\)

となって、証明が完成しました。


オイラー関数の乗法性を直感的に理解するために、中国剰余定理のところであげた表を使って \(\varphi(12)=\varphi(3)\varphi(4)\) のイメージを示したのが次です。\(●\) 印を付けたのはそれぞれ、\(12,\:3,\:4\) とは素な数です。

\(mn=12\) \(m=3\) \(n=4\)
\(0\,\) \(0\,\) \(0\,\)
\(●\:1\,\) \(●\:1\,\) \(●\:1\,\)
\(\phantom{●}2\,\) \(●\:2\,\) \(\phantom{●}2\,\)
\(\phantom{●}3\,\) \(\phantom{●}0\,\) \(●\:3\,\)
\(\phantom{●}4\,\) \(●\:1\,\) \(\phantom{●}0\,\)
\(●\:5\,\) \(●\:2\,\) \(●\:1\,\)
\(\phantom{●}6\,\) \(\phantom{●}0\,\) \(\phantom{●}2\,\)
\(●\:7\,\) \(●\:1\,\) \(●\:3\,\)
\(\phantom{●}8\,\) \(●\:2\,\) \(\phantom{●}0\,\)
\(\phantom{●}9\,\) \(\phantom{●}0\,\) \(●\:1\,\)
\(\phantom{●}0\,\) \(●\:1\,\) \(\phantom{●}2\,\)
\(●11\,\) \(●\:2\,\) \(●\:3\,\)


このオイラー関数の乗法性(6.2)と素数の累乗のオイラー関数値(6.1c)を用いると、一般の自然数 \(N\) のオイラー関数値を求めることができます。つまり素因数分解の一意性により、\(p_i\) を素数として、

\(N=p_1^{\al_1}\:p_2^{\al_2}\:\cd\:p_r^{\al_r}\)

と表現できます。ここでオイラー関数の乗法性(6.2)を繰り返して使うと、

\(\varphi(N)=\varphi(p_1^{\al_1})\:\varphi(p_2^{\al_2})\:\cd\:\varphi(p_r^{\al_r})\)

となります。また、素数の累乗のオイラー関数値(6.1c)によって、

\(\varphi(p_i^{\al_i})=p_i^{\al_i}-p_i^{\al_i-1}\)

です。以上を合わせると、任意の数 \(N\) のオイラー関数値を求める公式は、

\(\varphi(N)\)\(=\)\((p_1^{\al_1}-p_1^{\al_1-1})\cdot\:\cd\:\cdot(p_r^{\al_r}-p_r^{\al_r-1})\)
\(=\)\(\dfrac{p_1^{\al_1}}{p_1}(p_1-1)\cdot\:\cd\:\cdot\dfrac{p_r^{\al_r}}{p_r}(p_r-1)\)
\(=\)\(\dfrac{N}{p_1p_2\:\cd\:p_r}\cdot(p_1-1)\cdot\:\cd\:\cdot(p_r-1)\)

となります。つまり、\(N\) の素因数分解ができれば \(\varphi(N)\) は簡単に求まります。逆に言うと\(\bs{N}\) の素因数分解が困難なら \(\bs{\varphi(N)}\) を求めるのも困難になる。このことが RSA暗号が成立する背景となっています。

ちなみに、上のオイラー関数の公式の末尾の形(色を塗った部分)は、オイラーより以前に江戸時代の和算家・久留島くるしま義太よしひろ(? - 1758)が発見しています。久留島義太は、関孝和、建部たけべ賢弘かたひろとともに三大和算家と呼ばれた人ですが、自分では書物を残すことがなかったので、業績は知人や弟子がまとめたものにしかありません。その一人、仙台藩の天文学者・戸板保佑やすすけの『久氏遺稿』の中に公式の記述ができます(鳴海 風「小説になる江戸時代の数学者」- 日本数学会「市民講演会」2007.3.31 による)。

その書物には \(\varphi(360)\) を求める例示があります(暗算でも出来ます)。つまり \(360=6\cdot6\cdot10\) なので素因数は \(2,\:3,\:5\) だけです。従って \(360\) を \(2\cdot3\cdot5=30\) で割って(答は \(12\))、\(1\cdot2\cdot4=8\) を掛けると \(\varphi(360)=96\) が求まる。このことが書かれています。この求め方は公式そのものです。

公式には \(p_i\) の累乗の部分(\(\al^i\))が全く現れません。ちょっと不思議な感じもする公式です。

日本の数学者の中には「久留島・オイラーの関数」と呼ぶ人もいます。"オイラー何とか" という名前の定理や公式はいろいろあるので、その方が分かりやすいかもしれません。


7. オイラーによるフェルマの小定理の一般化(オイラーの定理)


オイラー関数を使うと、オイラーが発見した「一般化されたフェルマの小定理」の証明ができます。

7.1 オイラーの定理

\(a\) を \(m\) とは素な数とするとき

\(a^{\varphi(m)}\equiv1\:(\mr{mod}\:m)\)


\(a\) や \(m\) に何らかの制約があるわけではなく、2つの数が「互いに素」という条件だけで成立する美しい定理です。これがフェルマの小定理の一般化であることは、\(p\) を素数として \(m=p\) とおけばフェルマの小定理そのものになることから分かります。

この証明を2段階に分けて行います。まず第1段階で \(m\) が素数の累乗の時に成立することを証明し、第2段階でその結果を使って \(m\) が一般の数の場合を証明します。

7.2 

\(p\) を素数とする。

\(m=p^{\al}\) のとき、7.1 は成り立つ。


\(\al\) についての数学的帰納法で証明します。まず \(\al=1\) のときはフェルマの小定理そのものなので成立します。次に \(\al=k-1\:(k\geq2)\) のときに成立すると仮定します。つまり、

\(a^{\varphi(p^{k-1})}\equiv1\:(\mr{mod}\:p^{k-1})\)

が成り立つとします。そうすると、ある数 \(b\) が存在して、

\(a^{\varphi(p^{k-1})}=1+bp^{k-1}\)

と表現できます。この式の左辺に 6.1c(素数の累乗のオイラー関数値)を適用すると、

\(a^{p^{k-1}-p^{k-2}}=1+bp^{k-1}\)

となります。この両辺を \(p\) 乗し、右辺は2項定理で展開すると、

\(\begin{eqnarray} &&a^{p^k-p^{k-1}}&=(1+bp^{k-1})^p\\ &&&=1+{}_p\,C_1(bp^{k-1})^1\\ &&&\phantom{=1}+{}_p\,C_2(bp^{k-1})^2+\:\cd\\ \end{eqnarray}\)

が得られます。この展開した右辺において、第2項は \({}_p\,C_1=p\) なので \(bp^k\) となり、\(p^k\) で割り切れます。また第3項以降は \(2\leq i\leq p\) として \({}_p\,C_ib^ip^{(k-1)i}\) と表せますが、\(k,\:i\geq2\) のとき \((k-1)(i-1)\geq1\) であり、この式を変形すると \((k-1)i\geq k\) となるので、第3項以降も \(p^k\) で割り切れます。つまり、展開した第1項の \(1\) 以外は \(p^k\) で割り切れることになります。従って、

\(\begin{eqnarray} &&a^{p^k-p^{k-1}}&\equiv1\:(\mr{mod}\:p^k)\\ &&a^{\varphi(p^k)}&\equiv1\:(\mr{mod}\:p^k)\\ \end{eqnarray}\)

となります。この結果、7.2 は \(\al=k-1\) のときに成立するなら \(\al=k\) のときにも成立することが証明でき、数学的帰納法が完成しました。


7.2 を使って 7.1 を証明します。\(p_i\) を相異なる素数とし、任意の数 \(m\) を、

\(m=p_1^{\al_1}\:p_2^{\al_2}\:\cd\:p_r^{\al_r}\)

とおきます。すると 7.2 により、\(1\leq i\leq r\) のそれぞれの \(i\) において、

\(a^{\varphi(p^{\al_i})}\equiv1\:(\mr{mod}\:p^{\al_i})\) \(\cd\:(1)\)

が成立します。ここで、

\(n_i=\dfrac{m}{p^{\al_i}}\) \((m=n_i\cdot p^{\al_i})\)

とおくと、オイラー関数の乗法性(6.2)により、

\(\varphi(m)=\:\varphi(n_i)\:\varphi(p^{\al_i})\)

となります。ここで、この式と合同式の累乗(1.2)を使って \((1)\) 式の両辺を \(\varphi\:(n_i)\) 乗すると、

\(a^{\varphi(m)}\equiv1\:(\mr{mod}\:p^{\al_i})\) \(\cd\:(2)\)

が得られました。\((2)\) 式は \(1\leq i\leq r\) の \(i\) においてそれぞれ成立します。\(p_i\) は相異なる素数だったので、ここで 1.5 を順次適用すると、

\(a^{\varphi(m)}\equiv1\:(\mr{mod}\:m)\)

となり、7.1 が正しいことが証明されました。


7.1 の証明の過程を振り返ってみると、次の 7.3 が成り立つことが分かります。

7.3 オイラーの定理・その2

任意の数 \(m\) の素因数分解を、相異なる素数 \(p_i(1\leq i\leq r)\) を使って、

\(m=p_1^{\al_1}p_2^{\al_2}\:\cd\:p_r^{\al_r}\)

と表す。\(\psi(m)\) を \(r\) 個の \(\varphi(p_i^{\al_i})\) の最小公倍数とする(\(\psi\) はギリシャ文字のプサイ)。つまり、

\(\psi(m)=\mr{lcm}(\varphi(p_1^{\al_1}),\:\cd\:,\varphi(p_r^{\al_r}))\)

とすると、\(m\) と素である数 \(a\) について、

\(a^{\psi(m)}\equiv1\:(\mr{mod}\:m)\)

が成り立つ(\(\mr{lcm}=\) 最小公倍数)。


これは 7.1 の証明の後半(= 7.2 を使って証明する部分)からすぐに分かります。\(\psi(m)\) の定義から、

\(\psi(m)=k_i\cdot\varphi(p_i^{\al_i})\:\:(1\leq i\leq r)\)

と書き表すことができます。一方 7.2 より、

\(a^{\varphi(p_i^{\al_i})}\equiv1\:(\mr{mod}\:p_i^{\al_i})\)

が成り立ちます。この合同式の両辺を 1.2(合同式の累乗) に従って \(k_i\) 乗すると、

\(a^{k_i\varphi(p_i^{\al_i})}\equiv1\:(\mr{mod}\:p_i^{\al_i})\)

となり、これから、

\(a^{\psi(m)}\equiv1\:(\mr{mod}\:p_i^{\al_i})\)

が得られます。この式は \(1\leq i\leq r\) であるすべての \(i\) について成立し、また \(p_i^{\al_i}\) は互いに素なので、1.5 を順次適用することで、

\(a^{\psi(m)}\equiv1\:(\mr{mod}\:m)\)

となり、7.3 が証明できました。この証明の過程から、\(\psi(m)\) が最小公倍数でなくても、公倍数であれば成立することが分かります。なお \(\psi(m)\) は一般的な表記ではなく、ここで便宜上使った記号です。


オイラーの定理(7.1)と、オイラーの定理・その2(7.3)を

\(\begin{eqnarray} &&m&=3\cdot7=21\\ &&a&=2\\ \end{eqnarray}\)

として具体的に書いてみると次の通りです。

\(\begin{eqnarray} &&\varphi(m)&=\varphi(3)\cdot\varphi(7)\\ &&&=2\cdot6\\ &&&=12\\ &&&\\ &&2^{12}&=4096\\ &&&=195\cdot21+1\\ &&&\equiv1\:(\mr{mod}\:21)\\ &&&\\ &&\psi(m)&=\mr{lcm}(\varphi(3),\varphi(7))\\ &&&=\mr{lcm}(2,6)\\ &&&=6\\ &&&\\ &&2^6&=64\\ &&&=3\cdot21+1\\ &&&\equiv1\:(\mr{mod}\:21)\\ \end{eqnarray}\)

オイラーの定理の別証明
いままでは「オイラー関数の乗法性」を導出して、それをもとにオイラーの定理(とその最小公倍数版)を証明しました。しかし単にオイラーの定理だけを証明したいのなら、以下のようにフェルマの小定理(3.1)のときと同じ論法で可能です。


\(n\) 以下の自然数で \(n\) と互いに素である \(\varphi(n)\) 個の数を、数列として、

\(b_1,\:\:b_2,\:\:b_3,\:\cd\:,\:b_{\varphi(n)}\)

と並べます。これらはすべて相異なる数です。次に \(n\) とは素な数 \(a\) を選び、数列の全部にかけ算をして新たな数列、

\(ab_1,\:\:ab_2,\:\:ab_3,\:\cd\:,\:ab_{\varphi(n)}\)

を作ります。そして、それぞれの数を \(n\) で割った剰余を \(r_i\) とします。つまり、

\(\begin{eqnarray} &&ab_1&\equiv r_1\:(\mr{mod}\:n)\\ &&ab_2&\equiv r_2\:(\mr{mod}\:n)\\ &&ab_2&\equiv r_3\:(\mr{mod}\:n)\\ &&&\vdots\\ &&ab_{\varphi(n)}&\equiv r_{\varphi(n)}\:(\mr{mod}\:n)\\ \end{eqnarray}\)

です。\(a\) も \(b_i\) も \(n\) と素なので \(r_i\) が \(0\) になることはなく、\(1\leq r_i < n\) です。そして、このようにすると\(\bs{r_i}\) は全て \(\bs{n}\) と素になります。なぜなら、剰余の式を、

\(ab_i=k_in+r_i\)

とするとき、\(r_i\) と \(n\) に共通の約数があるなら、その約数は \(ab_i\) の約数にもなり「\(a\) も \(b_i\) も \(n\) と互いに素」という、そもそもの仮定に反するからです。

さらに、\(1\leq i,\:\:j\leq\varphi(n)\) である \(i,\:j\) について、

\(i\neq j\) であれば、必ず \(r_i\neq r_j\)

になります。なぜなら、もし \(r_i=r_j\) とすると、1.1b(合同式の減算)より、

\(a(b_i-b_j)\equiv0\:(\mr{mod}\:n)\)

です。仮定より \(a\) は \(n\) と互いに素なので 1.3 により(\(1.3\) で \(b=0\) の場合)、

\((b_i-b_j)\equiv0\:(\mr{mod}\:n)\)

となりますが、\(1\leq b_i,\:\:b_j\leq n\) なので、

\(b_i=b_j\)

となり、\(b_1,\:\:b_2,\:\:b_3,\:\cd\:,b_{\varphi(n)}\) が相異なる数という仮定に反してしまうからです。つまり\(i\neq j\) であれば、必ず \(r_i\neq r_j\) です。

ということは、\(\varphi(n)\) 個の数、\(r_i\) は「すべてが \(n\) とは素である、相異なる数」であり、つまり \(\varphi(n)\) 個の数、\(b_i\)を並び替えたものです。従って、

\(r_i\) を全部かけ算したものを \(R\)
\(b_i\) を全部かけ算したものを \(B\)

と書くとすると、

\(R=B\)
 \((r_1r_2\:\cd\:r_{\varphi(n)}=b_1b_2\:\cd\:b_{\varphi(n)})\)

となります。そこで、1.1c(合同式の乗算)を上の \(\varphi(n)\) 個の合同式に適用して左辺と右辺を全てかけ合わせると、

\(a^{\varphi(n)}\cdot B\equiv R\:(\mr{mod}\:n)\)  つまり、
\(a^{\varphi(n)}\cdot B\equiv B\:(\mr{mod}\:n)\)

が得られます。ここで、そもそもの定義から \(B\) は \(n\) と素なので 1.3 を使うと、

\(a^{\varphi(n)}\equiv1\:(\mr{mod}\:n)\)

となって証明が完成しました。


8. RSA暗号の一般形


オイラー関数とオイラーの定理(オイラーによるフェルマの小定理の一般化)を用いると、RSA暗号(4.1)の一般形を次のように記述できます。

8.1 RSA暗号の一般形

\(n\) を任意の自然数とし、\(e\:,d\) を、
 \(de\equiv1\:(\mr{mod}\:\varphi(n))\) を満たす数とする。この前提で、

 暗号化:\(P^e\equiv C\:(\mr{mod}\:n)\) ならば
 復号化:\(C^d\equiv P\:(\mr{mod}\:n)\)

である。また、

 暗号化:\(P^e\equiv C\:(\mr{mod}\:n)\) ならば
 復号化:\(C^d\equiv P\:(\mr{mod}\:n)\)

も成り立つ。

この一般形にすると、復号化の式の証明はいたってシンプルになります。\(de=k\varphi(n)+1\)とおくと、

\(C^d\equiv P^{de}\:(\mr{mod}\:n)\)
\(\phantom{C^d}=P^{k\varphi(n)+1}\)
\(\phantom{C^d}=P\cdot(P^{\varphi(n)})^k\)
\(\phantom{C^d}\equiv P\:(\mr{mod}\:n)\)

となり証明できます。\(d,\:\:e\) を入れ替えても成り立ちます。最後の式の変形のところでは 7.11.2(合同式の累乗)を使っています。また 7.3 で証明したように、\(\varphi(n)\) の代わりに \(\psi(n)\) (= \(n\) の素因数それぞれのオイラー関数値の最小公倍数)としても、RSA暗号の一般形は成立します。

実際のRSA暗号は \(p\) と \(q\) を素数として \(n=pq\) とおいたものですが(6.1b)、数学的には \(n\) の素因数分解が分かると(素因数の累乗があってもよい) \(\varphi(n)\) はすぐに計算できるので(6. オイラー関数)暗号が構成できることになります。それが 8.1 の一般形の意味です。

しかし実用的な暗号のためには、素因数分解が困難であり(= \(n\) の素因数ができるだけ大きな数であり)、また暗号化・復号化の高速計算のためには \(n\) が小さいほど良いので、RSA暗号がその最適解なのでした。


全体のまとめ


最後に、RSA暗号についての説明全体をまとめると、以下のようになるでしょう。

◆  RSA暗号は数論(整数論)の基礎から構成されている。その基礎には、ユークリッド、孫子算経、フェルマ、オイラーなどによる数学史の重要な発見が詰まっている。

◆  RSA暗号における公開鍵・秘密鍵の生成式、暗号化・復号化の式には巨大数の演算が現れるが、それは実用的に計算可能である。

◆  RSA暗号の原理は、整数の "加減乗除" と "累乗(冪乗)" の知識をベースとして、そこから論理を積み重ねることで理解可能である。つまり「高校数学程度の知識で理解」できる。

この最後の点が、ここに「RSA暗号の数理」を掲載した目的でした。



補足:デジタル署名
公開鍵暗号は暗号化の鍵を公開するため、誰でも通信相手の公開鍵を使って暗号を作れます。\(A\) さんと \(B\) さんが RSA暗号で暗号化通信をするとし、

\(A\)
 公開鍵 \((e_A,\:\:n_A)\)、秘密鍵 \(d_A\)
\(B\)
 公開鍵 \((e_B,\:\:n_B)\)、秘密鍵 \(d_B\)

とします。\(B\) から \(A\) にメッセージ \(M\) を送るには、

 \(M^{\:\large e_{\overset{\:}{A}}}\equiv C\:\:(\mr{mod}\:n_A)\)

となる暗号文 \(C\) を送ればよく、\(C\) は \(d_A\) を知っている人しか解読できません。しかし、秘密鍵 \(d_A\) でしか解読できない暗号文は誰にでも作れます。つまり "なりすまし" ができる。\(A\) としては確かに \(B\) から来た暗号文だという確証が必要です。この確証を得る手段がないと、公開鍵暗号は成立しません。

その確証の手段が「デジタル署名」で、これは「ハッシュ関数」という技術にもとづいて作ります。

 ハッシュ関数 

ハッシュ関数は「任意長の入力データを固定長のハッシュ値に変換する関数」です。固定長は、たとえば256ビットです。これは暗号学的に信頼できる標準的なものがあって、アメリカ国立標準技術研究所(NIST)によって公開されている SHA-2、SHA-3 がその例です(SHA : Secure Hash Algorithm)。

ハッシュ関数には「入力メッセージのわずかな違いも、出力されるハッシュ値に大きな変化を及ぼす」という特性があります。SHA-2 の仕様の一つである SHA256(ハッシュ値:256ビット)で実際にやってみると、

A rolling stone gathers no moss.
A rolling stone gathers no moss

という2つの文章の違いは、最後にピリオドがあるか(前)、無いか(後)だけですが、2つのハッシュ値を16進数で並べて書くと、

4F73D0D6A45EF8B201707281CB421EE90413D4C1A5CA846BABF502A4BB202DE8 709EAFF33947303FBBC0810DD8F099C317BACC057F4BF91E081DB2B099457FCA

であり、全く違うことが分かります。もし入力データが同じであれば、ハッシュ関数は厳密に同じハッシュ値を出力します。

安全なハッシュ関数の条件は、まずハッシュ値から入力データを推測できないことです(=一方向性)。また、同じハッシュ値をもつ別の入力データを推測できないことです(=衝突困難性)。SHA-2、SHA-3 はそのような条件をクリアした、安全なアルゴリズムです。

以降、ハッシュ関数を \(H(\:)\) と書きます。RSA暗号を使ったデジタル署名のアルゴリズムは次の通りです。

 デジタル署名 

\(B\) から \(A\) にメッセージ \(M\) を送る手順です。


\(\bs{B}\) の署名手順

①  \(M^{\:\large e_{\overset{\:}{A}}}\equiv C\:\:(\mr{mod}\:n_A)\) となる暗号文 \(C\) を計算する。

②  \(M\) のハッシュ値 \(h=H(M)\) を求め、
 \(h^{\:\large d_{\overset{\:}{B}}}\equiv C_h\:\:\:\:(\mr{mod}\:n_B)\)
となる、\(C_h\)(=デジタル署名)を計算する。

③  \((C,\:\:C_h)\) のペアを暗号文として \(A\) に送る。

\(\bs{A}\) の検証手順

①  \(C^{\:\large d_{\overset{\:}{A}}}\equiv M\:\:(\mr{mod}\:n_A)\) となるメッセージ \(M\) を復号する。

②  \(C_h^{\:\large e_{\overset{\:}{B}}}\equiv H(M)\:\:(\mr{mod}\:n_B)\) であれば、メッセージは \(B\) から送られたもの(かつ、改竄されていない)と確認できる。この式を満たすハッシュ値 \(C_h\) は、秘密鍵 \(d_B\) を知っている \(B\) にしか作成できない。


RSA暗号は暗号化と復号化が対称形の計算なので、デジタル署名の作成と検証はシンプルです。




nice!(0) 

nice! 0