RSA暗号とは？仕組みをわかりやすく解説！【プログラム付き】

2021 6/18

2021年6月18日

こんにちは！
今井(@ima_maru)です。

今回は「RSA暗号」についてです。

RSA暗号は現代の情報通信の要であり、当たり前に使われている暗号化技術です。

しかし、その仕組みは意外と知られていないものです。

以前、私は大学でRSA暗号について学んだのですがうろ覚えでしたので、インプットとアウトプットがてらこの記事を書こうと思います。

それでは解説していきます。

RSA暗号とは？

RSA暗号とは、巨大な素数を使った暗号化技術です。

公開鍵暗号方式に用いられる仕組みであり、現代の暗号通信で大きな役割を担っています。

RSA暗号は1977年に考案され、3人の考案者の頭文字をとって命名されました。

Rivest：ロナルド・リベスト
Shamir：アディ・シャミア
Adleman：レオナルド・エーデルマン

RSA暗号の仕組みはなんとなくわかる方もいれば、さっぱりわからない方もいるかと思います。

RSA暗号はどのくらい理解するかにもよりますが、本記事では「合同式の基礎」や「フェルマーの小定理」を用いて解説を行いますが、その定理までは深く解説しませんのでご了承ください。

すこし数式や文字が出てきますが、難しい言葉や数式をできるだけ使わずに、解説してみます。

RSA暗号の処理「暗号化」と「復号」

RSA暗号は以下の流れで動いています。

RSA暗号の流れ

公開鍵\(k1,N\)と秘密鍵\(k2\)を生成する（公開鍵と秘密鍵の生成方法で解説）
送りたいメッセージ\(M\)を暗号化して暗号文\(C\)を生成する
暗号文\(C\)を復号して送りたいメッセージ\(M\)を再度生成する

まずは、公開鍵\(k1,N\)と秘密鍵\(k2\)を生成します。
（これは下の「公開鍵と秘密鍵の生成方法」で解説）

これらの鍵はすべて整数の値です。

この\(k1\)と\(N\)が公開鍵になり、\(k2\)が秘密鍵になります。
（\(k1\)と\(k2\)の順番はどちらでもよいですが）

暗号文\(C\)を生成するには、メッセージ\(M\)を\(k1\)乗して\(N\)で割ります。

\(C = M^{k1} \bmod {N}\)
\((C = M^{k1}\)を\(N\)で割った余り)

こうして出てきた整数が暗号文\(C\)になります。

次に暗号文を復号するには、暗号文\(C\)を\(k2\)乗して\(N\)で割ります。

\(M = C^{k2} \bmod {N}\)
\((M = C^{k2}\)を\(N\)で割った余り)

そうすると、なんとメッセージ\(M\)が復号されるのです。

鍵の生成方法はあとで解説するとして、実際行われている暗号化と復号は、

\(C = M^{k1} \bmod {N}\)：暗号化
\(M = C^{k2} \bmod {N}\)：復号

の二つの処理だけです。

たった2行！
これで暗号化と複号ができているなんて不思議ですね。

実際にプログラムを書いてみます。

鍵の作り方や仕組みは以下で解説しますので、ひとまず流れだけさらっとご覧ください。

#include <iostream>
using namespace std;

int main()
{
	int k1 = 15; // 公開鍵
	int k2 = 47; // 秘密鍵
	int N = 391; // 公開鍵

	// 送りたいメッセージの入力
	int M;
	cout << "送りたいメッセージM(整数)：";
	cin >> M;
	cout << endl;

	// 暗号化：暗号文Cの生成
	int C = 1;

	for (int i = 0; i < k1; i++) {
		C *= M;
		C %= N;
	}

	cout << "C：" << C << " (暗号化)" << endl;

	// 復号：暗号文Cから送りたいメッセージM_=Mを復号する
	int M_ = 1;

	for (int i = 0; i < k2; i++) {
		M_ *= C;
		M_ %= N;
	}

	cout << "M_：" << M_ << " (復号)" << endl;

	return 0;
}

送りたいメッセージM(整数)：123

C：370 (暗号化)
M_：123 (復号)

本当に元に戻りました。

では、RSA暗号の仕組みからご説明します。

RSA暗号の原理と仕組み

RSA暗号は、合同式の以下の性質を利用した暗号化アルゴリズムです。

\(M^{n(p-1)(q-1)+1} \equiv M \pmod {pq}\)

この数式の証明を知りたい方は、下に書いてあるので見ていただくとして、「とりあえずこの原理が正しい」として話を進めましょう。

この数式を言葉で表すのであれば、以下のようになります。

整数 \(M\)を\(n(p-1)(q-1)+1\)乗して素数\(p\),\(q\)の積で割った余りと、
\(M\)を素数\(p\),\(q\)の積で割った余りは等しい。

ちょっと長くて難しいですね。

結局は何が言いたいかというと、以下のようなことになります。

\(M\)をある特定の整数乗して、ある特定の整数で割った余りがまた\(M\)に戻ってくるよ。
（\(M \lt pq\)の場合）

「何乗もするのに、余りを計算すると元の整数にもどってくる」という素数にまつわる整数の性質を表しています。

その「特定の整数の作り方」、つまり「鍵の作り方」に素数が大きく関わっています。

公開鍵と秘密鍵の生成方法も下で詳しく解説しますので、今は、公開鍵が「\(k1\)」と「\(N\)」、秘密鍵が「\(k2\)」であり、

\(k1k2=n(p-1)(q-1)+1\)
\(N=pq\)

という関係性だということをとりあえず頭に入れておいてください。

これらの鍵を先ほどの数式に当てはめると、

\(M^{n(p-1)(q-1)+1} \equiv M \pmod {pq}\) を、
\(M^{k1k2} \equiv M \pmod {N}\) と変換することができます。

これはただ文字を置き換えただけですね。
そしてこの数式が超重要！！

また、合同式の性質より、

\(M^{k1k2} \equiv M \pmod {N}\) を、

\(M^{k1} \equiv C \pmod {N}\) ：暗号化
\(C^{k2} \equiv M \pmod {N}\) ：復号

と2段階で変換することもできます。まさにこの2段階の変換こそがRSA暗号の暗号化と復号のアルゴリズムです。

2行の合同式でRSA暗号の仕組みのほぼすべてを表現しています。

まとめると、

送りたいメッセージ	\(M\)
暗号文(C)	\(M^{k1} \bmod {N}\)
復号した結果	\(C^{k2} \bmod {N} \) ※復号できているので実質\(M\)と同じ
暗号化	メッセージ\(M\)を\(k1\)乗して\(N\)で割った余りを求める処理
復号	暗号文\(C\)をさらに\(k2\)乗して\(N\)で割った余りを求める処理

この暗号化と復号という操作は、\(M^{k1k2} \equiv M \pmod {N}\) という原理をもとに作られています。

なので、公開鍵である\(k1\)と\(N\)だけを知っていても、暗号化はできるが、その暗号文\(C\)を復号することはできないのです。

復号するには、必ず\(k2\)が必要になります。

「自分で作った暗号文を復号できない」ってすごいですよね。
これが余りを求めるという不可逆的な操作のおかげです。

正確には、秘密鍵\(k2\)で暗号化して、公開鍵\(k1\)で復号するというやり方（\(k1\)と\(k2\)が逆の場合）もあるので、

「暗号文に使われていないほうの鍵を使わないと複号できないような仕組み」といったほうが良いでしょう。

この「暗号化をした鍵でも復号ができない」という不可逆性こそが、RSA暗号の面白いところであり、暗号として成り立っている仕組みそのものなのです。

RSA暗号の原理の証明（難しいので理解しなくてもよい）

ここでは難しいのですが、異なる素数\(p,q\)を使った、

\(M^{n(p-1)(q-1)+1} \equiv M \pmod {pq}\)

の証明をしていこうと思います。

証明に必要な知識は、

合同式の基礎
フェルマーの小定理

です。詳しく知りたい方は、

フェルマーの小定理の証明と例題 | 高校数学の美しい物語

合同式の意味とよく使う６つの性質 | 高校数学の美しい物語

RSA top

この辺をどうぞ。

証明

まずは、\(M^{n(p-1)(q-1)+1} \equiv M \pmod {p}\)を証明します。

【\(M\)が\(p\)の倍数の場合】

\(M\)を自然数乗しても\(p\)の倍数なので、余りは0。

よって、左辺と右辺ともに\(p\)で割った余りは0なので、以下が成り立つ。

\(M^{n(p-1)(q-1)+1} \equiv 0 \equiv M \pmod {p}\)

【\(M\)が\(p\)の倍数でないの場合】

\(p\) が素数、\(M\)と\(p\)が互いに素な自然数であるので、「フェルマーの小定理」より、

\(M^{(p-1)} \equiv 1 \pmod {p}\) である。よって、式変形すれば以下が成り立つ。

\(M^{n(p-1)(q-1)+1} = (M^{(p-1)})^{n(q-1)} \cdot M \equiv M \pmod {p}\)
※\(M^{(p-1)}\)は\(p\)で割れば1になる。

\(M^{n(p-1)(q-1)+1} \equiv M \pmod {p}\) は証明できた。そして、\(p\)と\(q\)の対称性により、
\(M^{n(p-1)(q-1)+1} \equiv M \pmod {q}\) も同様に証明できる。よって、

\(M^{n(p-1)(q-1)+1} \equiv M \pmod {pq}\) （ここの変換は上のリンク3つ目を参照）

-----証明終了-----

RSA暗号の公開鍵と秘密鍵の生成方法とその意味

RSA暗号は、公開鍵\(k1,N\)、秘密鍵\(k2\)を作成する必要があります。

ここでは、\(k1\)と\(k2\)と\(N\)の生成方法を解説し、それらがなぜそのように作られているのかの意味について深堀りしていこうと思います。

RSA暗号の公開鍵と秘密鍵の生成方法

RSA暗号の鍵の生成方法は、

二つの異なる大きな素数\(p,q\)を生成する
公開鍵\(N=pq\)を生成する
\(k1k2=n(p-1)(q-1)\)となるように2以上の自然数\(k1\)と\(k2\)を生成する

です。

まず、RSA暗号には二つの素数\(p,q\)が必要です。
（説明では小さい素数を使いますが、実際に用いるのは1000万桁といった大きな値です。）

具体例として、今回は\(p=17,q=23\)としましょう。
（素数の作成方法については今後解説）

そして、公開鍵である\(N\)の生成方法は簡単で、\(p,q\)の積になります。

\(N = pq = 17x23 = 391\)

そうしたら次は、公開鍵\(k1\)と秘密鍵\(k2\)の生成です。これは、

\(k1k2 = n(p-1)(q-1) + 1\)

となる\(k1,k2\)を探します。

このときの\(n\)は任意の自然数で、\(k1,k2\)ともに2以上の自然数ですので\(n\)を変更しながら探していくこととなるでしょう。

今回は\(p=17,q=23\)なので、\((p-1)(q-1) = 16x22 = 352\) ですね。

つまり、\(k1k2 = n \times 352 + 1\)となる\(k1,k2\)を探していきます。

まずは\(n=1\)から検索してみましょう。

\(n=1\)の場合：\(1 \times 352 + 1 = 353\)
\(353\)は素数なので条件に合う(k1k2)が生成できないですね。

\(n=2\)の場合：\(2 \times 352 + 1 = 705\)
\(705=3 \times 5 \times 47\)なので、\(k1=15, k2=47\)としましょう。

これで、公開鍵である\(k1\)と\(N\)、秘密鍵である\(k2\)が完成し、すべての鍵が揃いました。

\(k1 = 15\)
\(k2 = 47\)
\(N = 391\)

先ほどのプログラムの中で使った値はこのようにして作られていました。

	int k1 = 15; // 公開鍵
	int k2 = 47; // 秘密鍵
	int N = 391; // 公開鍵

なぜこのように鍵を生成すればRSA暗号の鍵となるのかは、さきほどの原理通りなのですが、「意味」という観点から解説します。

RSA暗号の公開鍵と秘密鍵の意味

RSA暗号の原理は、以下の数式で示されることがわかりました。

\(M^{n(p-1)(q-1)+1} \equiv M \pmod {pq}\)

これは、「整数 \(M\) を \({n(p-1)(q-1)+1}\) 乗して素数 \(p\),\(q\) の積で割った余りと、
\(M\) を素数 \(p\),\(q\) の積で割った余りは等しい。」ということでした。

でも、これだけではただ、\(M\)を何乗かして余りを出すと元の\(M\)の余りと同じという「整数の性質」というだけなのです。

重要なのは、何がしたいか？やりたいことは何か？です。

それは、

「送りたいメッセージ \(M\) を私が\(k1\)乗して渡すから、あなたは\(k2\)乗して」
「そうすれば\(k1k2=n(p-1)(q-1)+1\) なんだからあなたが\(k2\)乗して余りを出したころには、元のメッセージ\(M\)に戻ってるよね」

ということなんですよ。

合同式の性質をうまく使って、

\(M^{n(p-1)(q-1)+1} \equiv M \pmod {pq}\) を、
\(M^{k1 \times k2} \equiv M \pmod {pq}\) とすれば、

\(M^{k1} \equiv C \pmod {pq}\) ：暗号化
\(C^{k2} \equiv M \pmod {pq}\) ：復号

こう分けられます。

つまり「暗号化と復号」という二つのプロセスに分割するには、

\({n(p-1)(q-1)+1}\)を\(k1 \times k2\)という形に直せればいいということです。

ここまでくれば、もうわかるでしょう。

\(k1\)と\(k2\)の生成方法は上で書いた通り、

\(k1k2=n(p-1)(q-1)+1\)
となるような自然数で生成します。

これが\(k1\)と\(k2\)を\(n(p-1)(q-1)+1\)から生成する理由です。

つまり、本当に使いたい原理は素数から作られる\(n(p-1)(q-1)+1\)を使った整数の性質。

それを「暗号化と復号」という二つのプロセスに分けるために、\(k1k2=n(p-1)(q-1)+1\)となる自然数\(k1,k2\)を公開鍵と秘密鍵として生成したのです。

また、公開鍵である\(N\)を生成する理由は、暗号化と復号に「\(N\)で割って余りを出す」という処理があるので必要なのですが、その\(N\)が元の\(pq\)であるといけません。

この\(p\)と\(q\)を公開鍵として渡してしまうと、上で書いた生成方法より、公開鍵はおろか、秘密鍵である\(k2\)さえも\(p\)と\(q\)から作成できてしまうからです。

これはRSA暗号の安全性にもかかわってくる話なので下で書きます。

RSA暗号の素数と安全性の関係

RSA暗号は大きな素数をつかう暗号

RSA暗号の一番大きな要素は「巨大な素数」です。

上では、素数として、17と23という非常に小さな値を使いましたが、実際に使われる素数は、1000万桁といったのとてつもなく大きな素数です。

それらから生成される公開鍵\(N=pq\)をもとの\(p\)と\(q\)に素因数分解することは非常に困難です。

たとえば、そこまで大きくなくても、 \(3559 \times 3571 = 12,709,189\) において、

\(3559 \times 3571\) を計算すること
\(12,709,189\) を素因数分解すること

どちらが難しいでしょうか？

上は電卓ですぐできますが、下は明らかに難しいのがわかります。

その「困難さ」「難しさ」こそがRSA暗号の安全性そのものであり、もしこの「素因数分解を効率的にできるアルゴリズム」であったり、「効率的にできる機械」が発明されれば現代のRSA暗号は解かれてしまうでしょう。

実際、前者の「素因数分解を効率的にできるアルゴリズム」は「リーマン予想」、
後者の「素因数分解を効率的にできる機械」は「量子コンピュータ」と言われています。

まとめ

暗号通信に使われるRSA暗号という技術を解説しまいたがどうでしたでしょうか。

私は、大学で学んだとき難しくていまいち理解できませんでした。

「なぜそのようにして鍵を生成するのか？」
「なんでそうすると元のメッセージに戻るのか？」

以前わからなかった自分に対して説明したつもりです。

最後に、この記事を読んでいただいた方に向けて暗号を残そうと思います。

RSA暗号かはわかりませんが、以下の暗号文を復号鍵「じゃぱざむ」を使って復号してみてください。（バイナリ→16進数(gzip圧縮)で復号）

53616c7465645f5fe8b8abccb534792664c4b4e0792f9b8af82938a0e63fe51a665054f7dd81b0e2832bfd0928f4d1c7cda3203aeec0f643f23b52fd1a367369ccac5c6c6991c04b9cee0d70842f26a3c83fb7a684ed22608fb61dc2892961fe996412e583910b9cfa80e11c8c593caa6e98fbd5a51060f4455fce513214380b6e6af65c509b979e

以下のサイトで復号できます。

暗号生成ツール - 暗号くん

以上「RSA暗号とは？仕組みをわかりやすく解説！【プログラム付】」でした！

最後までご覧いただきありがとうございます。

よかったらシェアしてね！