RSA 暗号の数学的背景を理解する

この記事は群馬大学電子計算機研究会 IGGG Advent Calendar 2019 - Adventar 1 日目の記事です。

もう冬ですね.アドベントカレンダーの季節です.内容は RSA 暗号です.

RSA 暗号は公開鍵暗号の一つで,因数分解の難しさを根拠にしている暗号です. この記事の目標としては,RSA 暗号の概略がわかり,「因数分解の難しさがどう暗号の難しさに寄与しているのか」を理解することです.

まずは RSA 暗号が使われている.公開鍵暗号通信について概略を理解します.

公開鍵暗号通信

ネットワーク上でデータを送信する際に,データを暗号化せずに送信したのでは, 中継するコンピュータによって通信が傍受されてしまう可能性があります. 公開鍵暗号通信は上記のような通信の問題を解決する暗号化による通信方式の一つです.

Alice が Bob にデータを送ることを考えます.

Bob が Alice に暗号鍵を送る.Alice が送信するデータを暗号化する.
Alcie が Bob に暗号化したデータを送る.
Bob が複合鍵を使って Alice から送られてきたデータを復号化する.

このような通信を行います.

暗号鍵と暗号データから元データが推測できない種類の暗号を用いれば通信の秘匿性を保証できます.

RSA 暗号は 2019 年現在現役で公開鍵暗号通信に使われている暗号です.

RAS 暗号

概要

RAS 暗号は指数演算と剰余演算を暗号化と復号化に用いる暗号化方式です.

整数 $x$ を用いて暗号化後 $y$ を計算するには整数鍵 $(k, n)$ を用いて $y \equiv x^{k} \mod n$ とします.

復号化する際には暗号鍵に対応する複合鍵 $(d,n)$ を用いて
${ y^{d} \equiv x^{k\cdot d} \mod n }$

$\equiv x \mod n$ と計算します.

復号鍵 d の存在について

復号化する際の都合のいい $(d,n)$ は必ず存在します.

$p,q$ を十分大きい素数とする. $n = p,q$ とおく.

復号化する際は $x^{k\cdot d} \equiv x \mod n$ である.

ここでオイラーの定理を用いる.

オイラーの定理
正の整数 a,m に対して a,m が互いに素のとき,以下の式が成り立つ. $a^{\phi(m)} \equiv 1 \mod m$ ただし, $\phi(\cdot)$ はオイラー関数とする.

この定理より以下の式が成り立つ. $x^{\phi(n)} \equiv 1 \mod n$ また, $n$ は素数の積であるということと,フェルマーの小定理を用いることによって, 任意の $x$ に対して上記の式が成り立つことが知られている.

これにより,ある整数 $u$ を用いて次式が成り立つ $x^{u\cdot \phi(n)+1} \equiv x \mod n$

復号化する際の式と比較すると, $d$ について.次式を満たせば所望の $d$ として十分である. $kd = u\phi(n)+1$ ここで $v = -u$ とおくと次のように書き直せる. $kd + v\phi(n)=1[tex:$

ここで $k$ は,鍵生成の際に自由に生成できる数であるから自由に制約をもたせることができる. $k$ を $\phi(n)=(p-1)(q-1)$ と互いに素な数として生成することにする. 具体的には $k$ を素数とする.

すると拡張ユークリッドの互除法により,次式を満たす整数 $k,v$ が存在する. これらが不定一次方程式の解であることを考えると $k,v$ は正の整数としても良い.

以上より, $n = pq, k は素数$ とすることにより,任意の暗号文 $x$ について復号鍵鍵 $d$ が必ず存在することが示されました.

復号鍵を求めるには一次不定方程式を解けばいいいわけですが,これには拡張ユークリッド互除法のアルゴリズムを用います. これは長くなるのでまたどこかで.

この暗号の安全性について

なんとなくメインの部分です.

第三者視点から見て,暗号を解読するには $\alpha x^{k} \equiv x \mod n$ となる $\alpha$ を求めれば良いです.

復号鍵という視点から暗号を解くことを考えると $\alpha = x^{d}$ という形をしていることが推測できます. $d$ を求める際には生成した方法を考えて以下の一次不定位方程式を解けば良いです.

$kd + v\phi(n)=1$

しかし,第三者視点では鍵を生成する際とは異なり $n=pq$ とした $p,q$ を知らないので $\phi(n)$ は容易に求まりません. $\phi(n)$ を求めるには実際に $n$ と互いに素な数を数えていくか,因数分解をするしかないですが, ここで $p,q$ を十分に大きい値とすることで $n$ は大きくなる. その場合,どちらの方法とも時間がかかる処理なので,現実的な時間で $\phi(n)$ を求めることができません. ひいては復号鍵 $d$ を現実的な時間で求めることができないことを意味します.