RSA暗号ってなに？

歴史

1977年に発明され、発明者であるロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンの原語表記の頭文字をつなげてこのように呼ばれる。

RSAというのは３人の頭文字を繋げて付けられた名前なんですね。

もともと公開鍵暗号方式という考え方は提案されていたのですが、それを実現する良い方法は見つかっていませんでした。難しいですよね、秘密鍵を持っている人だけが復号できる暗号方式なんて。

そんな中、この天才３人が考案したRSA暗号はとても素晴らしい方法ですぐに広まりました。

さらにすごいところはこのRSA暗号は４０年経った今でも用いられていることです。ちなみに私達がよく使っているLINEの文章もこの方法を用いて暗号化してから送られています。

暗号は主に２種類、共通鍵暗号方式と公開鍵暗号方式があります。その違いは以下で説明しているのでぜひ先にそっちを読んでください！

公開鍵暗号方式はみんなが知っている鍵で暗号化し、自分だけが知っている鍵で復号しますよね。

RSA暗号は数学を用いてそれを可能にしています。その方法はすごく簡単なのに斬新です！！！私は考えた人をマジな天才だと思っています。

んじゃまずは具体例から見ていきましょう。

今回はAliceがBobに”Hello”という文章を送るという設定にしましょう。ちなみに暗号の例ではAさんとBさんではなく、AliceさんとBobさんがよく使われるんで覚えておいてください（笑）

まずは平文（暗号化されていない文章）を数字に置換します。置換の方法は簡単に以下の方法にします。

英字	a	b	c	d	e	f	g	h	i	j	k	l
数字	01	02	03	04	05	06	07	08	09	10	11	12

m	n	o	p	q	r	s	t	u	v	w	x	y	z
13	14	15	16	17	18	19	20	21	22	23	24	25	26

するとHelloは”0805121215″と変換されます。ちなみに置換だけでも暗号の一種ですよ。これだけだとすぐにバレちゃいますが。

次は公開鍵と秘密鍵の設定ですね。RSA暗号では公開鍵は2つあります。1つ目は2つの素数の積$n$です。今回は２つの素数5と11の積である55にしましょう。そして2つ目は$(5-1) \times (11-1) = 40$と互いに素で40以下であるような整数な数を選びます。今回は7にします。

そして次は大事な秘密鍵です。今回の場合、秘密鍵$t$が満たすべき条件は40未満で$$7 \times t \equiv 1 \bmod 40$$です。つまり$t=23$となります。

これで準備は整いました！それでは暗号化してみましょう。

今回は公開鍵が55と小さいので、平文（”0805121215″）も小さく区切って暗号化しましょう。ということで数字2桁ずつ暗号化します。

まずは08からですが、暗号化は簡単です。08を公開鍵7乗し、もう一つの公開鍵55で割った余りを求めるだけです。つまり、\[8^7 \equiv 2 \bmod 55\]となるので、02に暗号化されます。

同様にして05,12,12,15はそれぞれ25,23,23,05と変換されるので、全部をつなげ合わせると\[“0225232305″\]となります。これで暗号化は完了です！

では受け取った側は”0225232305″をどうやって復号すればよいのでしょうか。

それも簡単です。2つずつ区切って秘密鍵を用いて同様の作業を行えばよいのです！具体的には秘密鍵は23なので、最初の02を取り出して23乗して55で割った余りを求めます。つまり、\[2^{23}\equiv 8 \bmod 55 \]となります。

同様に25,23,23,05に対しても同じ作業を行うと、05,12,12,15となります。これらを繋げると\[0805121215\]となり見事復号に成功しました！

どうですか、凄くないですか？？

私は初めてこの方法を知ったときはかなり感動しましたね～。まさに天才です。

ざっとどんな流れなのかは掴めたと思いますが、考えることはまだまだあります。例えば

などですね。ここからは理論的なところを解説していきたいと思います。が、長くなりそうなので別の記事にしますね。高校生以上なら誰でも分かるように解説したいと思っているので興味がある人はぜひ見てください！！