技術メモ

役に立てる技術的な何か、時々自分用の覚書。幅広く色々なことに興味があります。

RSA暗号を実装してみる（理論編）

数学 暗号理論

知識編で説明したように、RSA暗号の最大の特徴は暗号鍵から復号鍵を類推することが難しいというところにある。今回は、この特徴が数学的にどのように実現できているのかについて見ていく。
RSA暗号を実装してみる（知識編） - 技術メモ
RSA暗号を実装してみる（プログラム編） - 技術メモ

RSA暗号の原理

RSA暗号では暗号化の規則から復号化の規則を類推することが難しい。
その難しさの理由は、大きな２素数の積を素因数分解するのが事実上不可能というところを基礎とする。

この仕組みはフェルマーの小定理・オイラー関数から成り立っているが、このことを順を追って説明していこう。

フェルマーの小定理

p が素数，a が任意の自然数のとき
（１）\begin{eqnarray} a^{p}≡a \pmod{p} \end{eqnarray}
特に，a が p と互いに素な自然数のとき
（２）\begin{eqnarray} a^{p−1}≡1\pmod{p} \end{eqnarray}

証明

証明には数学的帰納法と鳩の巣原理を用いた方法がある。ここでは鳩ノ巣原理を使ったエレガントな方法で証明する。

aがpと互いに素でない時、すなわちa = np(n自然数)と表すことができる時、
(np)^p \equiv pとなり（１）の式は明らか。

aがpと互いに素な時、a,2a,3a,4a...(p-1)a をpで割った余りは1,2,3,4...(p-1) と一致する。
なぜならば、もしある自然数1\leq s,t\leq p-1, s\neq tがsa \equiv taを満たすとすると、
(s-t)a\equiv 0となり、1\leq s,t\leq p-1, s\neq tに反するからである。
したがって,

\begin{eqnarray}
a\times 2a\times 3a \cdots \times(p-1)a &\equiv& 1\times 2\times 3 \cdots \times(p-1) \\
(p-1)!\times a^{p-1} &\equiv& (p-1)! \\
a^{p-1} &\equiv& 1
\end{eqnarray}

オイラー関数

自然数nに対して、n未満でnと互いに素な自然数の個数を\varphi(n)で表し、オイラー関数と呼ぶ。
例えば、12未満で12と互いに素な自然数は\{1, 5, 7, 11\}なので\varphi(12) = 4

オイラー関数には以下のような性質がある。

(1)素数pに対して、\varphi(p)=p-1
(2)互いに素な自然数n,mに対して、\varphi(nm) = \varphi(n)\varphi(m)

これらより

異なる素数p,qに対して\varphi(pq) = (p-1)(q-1)

となる

RSA暗号に用いる定理

これまで説明したようなフェルマーの小定理やオイラー関数を使って、RSA暗号で以下の性質が利用される。

異なる２つの素数p, qについて、n=pqとする。
自然数d, eがde \equiv 1 \pmod{\varphi(n)}ならば、任意の自然数aに対して、a^{de}\equiv a \pmod{n}が成り立つ。

証明

aがnと互いに素でない時、明らかである

aがnと互いに素な時、nの約数p,qとも互いに素であり、
a^{de}\equiv a \pmod{p}かつa^{de}\equiv a \pmod{q}を示せば十分である。

まず、de \equiv 1 \pmod{\varphi(n)}より、
de-1=k(p-1)(q-1)　(kは非負整数)と表せる。
したがって、
\begin{eqnarray}
a^{de} = (a^{de-1})\times a = (a^{(p-1)(q-1)})^{k} \times a 
\end{eqnarray}
フェルマーの小定理から以下が成り立つ

(a^{(p-1)})^{k(q-1)}\times a \equiv a \pmod{p} \\
(a^{(q-1)})^{k(p-1)}\times a \equiv a \pmod{q}
よって
a^{de}\equiv a \pmod{p}かつa^{de}\equiv a \pmod{q}が示された。

RSA暗号の暗号化・復号化の手順

では、実際にどのように暗号化復号化するのだろうか。
受信側Aから送信側Bにメッセージ P を送ることを考える。（メッセージは何かしらの符号化で数字になってるとする）

(A1) A は異なる２つの巨大な素数 p, q を選ぶ。そして、n = pq を計算する。
(A2) n に対するオイラー数 ϕ(n) = (p − 1)(q − 1) を計算する。
(A3) ϕ(n) 以下で、ϕ(n) と互いに素となる自然数 e を探す。
(A4) ϕ(n) 以下で、ed ≡ 1 (mod ϕ(n))を満たす自然数 d を求める。
(A5) p, q, ϕ(n), d を秘匿して、n と e のみを公開する。
それでは、BがAに暗号を用いて通信を行うにはどうすればよいか。
(B1) B が A に送りたい平文を P (＜ｎ)とする。B は C = P^{e} \pmod{n} を計算して、C を A へ送る。
(A6) 暗号文 C を受信した A は D = C^{d} \pmod{n} によって復号化する。

上で説明した性質から D=P が成立するため、暗号・復号ができている。
( \begin{eqnarray} D &\equiv& C^{d} &\equiv& (P^{e})^{d} &=& P^{de} &\equiv& P \end{eqnarray})

復号化の困難性について

暗号鍵・復号鍵の具体的な内容についてはわかったと思うが、どうして暗号鍵から復号鍵を見つけることが難しいのだろう。
その理由は、e とn からd を導き出すことが難しいからだ。
d を知るには \varphi(n)を知らなければいけないが、 \varphi(n)を知るにはｎの素因数分解ができなければいけない。このｎの素因数分解はｎが巨大になればなるほど難しくなってくるが、このことが復号鍵を類推することを難しくしている。



難しそうに書いてみたけれど、ひとつひとつ見てみるとそんなに複雑ではない気もする。次は実際にコーディングに取り掛かる。


関連記事：

参考サイト：
情報数理：暗号理論入門　高畑弘(pdf)
フェルマーの小定理の証明と例題 | 高校数学の美しい物語
RSA 暗号がようやく分かった気がしたのでまとめてみる - tsujimotterのノートブック