公開鍵暗号「RSA」の仕組みを理解する

都内のスタートアップに勤務しているエンジニア（Twitter）です。
普段はReact、GrahqlQL、Railsを使ってフロントエンドからサーバーサイドの開発を幅広く担当しています。

「暗号技術入門」って本を読みました。タイトルにもある通り、暗号技術(「対称暗号」「公開鍵暗号」「デジタル署名」「SSL/TLS」などなど）の基礎を解説している本で、文系出身の私にも非常にわかりやすく書いてありとても面白かったです。

今回はその中から公開鍵暗号の1つであるRSA（アール・エス・エイ）について学んだ事をまとめようと思います。

対象読者

• 公開鍵暗号を使った大まかな通信の流れがわかっている方
• 公開鍵暗号に興味がある方

RSAによる暗号化・復号化

RSAによる暗号化は次の式で表すことができます。

暗号文 = 平文ᴱ mod N

EとNのセットが公開鍵になります。

復号化は次のような式で表現できます。

平文 = 暗号文ᴰ mod N

DとNのセットがプライベート鍵になります。

めちゃめちゃシンプルですよね。

mod??なにそれ？？😵‍💫となった方にも一から説明するのでご安心ください。

modとは

mod(モッド）とは、割り算の余りを求める記号です。Rubyでいう「％」です。
×や÷といった記号と同じように扱われます。

例えば、「13 mod 6」というのは「13を６で割った余り」を意味しています。この値は1になりますので次のように書くことができます。

13 mod 6 = 1

他にもいくつか例を載せておきます。

26 mod 8 = 2  (26を8で割った余りは2に等しい）
19 mod 7 = 5  (19を7で割った余りは5に等しい)
5 mod 7 = 5   (5を7で割った余りは5に等しい）

modの理解ができたところで、RSAによる暗号化・復号化の話に戻りましょう。

暗号化と復号化は次の式でしたね。

暗号文 = 平文ᴱ mod N
平文 = 暗号文ᴰ mod N

これはすなわち、
RSAの暗号文は平文を表す数をE乗してmod Nをとったもの
RSAの平文は暗号文を表す数をD乗してmod Nをとったもの
ということになります。

先ほども書いたように、EとNのセットが公開鍵でDとNのセットがプライベート鍵です。

次はEとDとNをどうやって求めるのか見ていきます。

鍵の作成手順

RSAの公開鍵・プライベート鍵の作成手順は次のようになっています。

1. Nを求める
2. Lを求める(Lは鍵を作成する時だけ登場する数です）
3. Eを求める
4. Dを求める

1. Nを求める

まず初めに、大きな素数を2つ(p,q)用意します。
次にこの2つの数を掛け合わせます。この結果がNとなります。
式にすると次のように表現できます。

N = p × q  (pとqは素数)

2. Lを求める

Lは鍵を作るときのみ登場する数です。なのでRSAの暗号化と復号化に登場しません。
Lは、p - 1とq - 1の最小公倍数です。

3. Eを求める

Eは１より大きくLより小さい数です。また、EとLは互いに素でなければいけません。

「互いに素」というのは、 「共通の約数が1だけ」 という意味です。

4. Dを求める

Dは次の条件を満たす数です。

1 < D < L
E × D mod L = 1

手順がわかったところで実際に鍵を作ってみましょう。

公開鍵とプライベート鍵を作ってみる

本当は大きな数を使わないといけませんが、大きな数を使うと計算が大変なので今回は小さい数を使って練習してみます。

1. Nを求める

2つの素数（7、11）を用意します。Nはこの2つの素数を掛け合わせたものでしたので77になります。

p = 7
q = 11

N = p × q
  = 7 × 11
  = 77

2. Lを求める

Lは、p - 1とq - 1の最小公倍数でしたね。
pが７、qが11でしたので、Lは30となります。

L = 30

3. Eを求める

Eは１より大きくLより小さい数でしたので、1 < E < 30と表現できます。
また、EとLは互いに素でないといけません。これを満たす数はいくつかあります。

7, 11, 13, 17, 19　・・・

今回は7を選ぼうと思います。

E = 7

4. Dを求める

Dは次の式を満たさなければいけません。

1 < D < 30
7 × D mod 30 = 1

これを満たすDは13になります。

D = 13

これで鍵が完成しました🎉🎉

公開鍵： E ＝ ７
　　　　 N ＝ 77

プライベート鍵: D = 13
              N = 77

暗号化してみる

暗号化できる数は、N未満の数すなわち今回は77未満の数でなければいけません。
平文として30を暗号化してみます。
暗号化では、「公開鍵E=7、N=77」を使います。

「平文を表す数をE乗してmod Nをとったもの」が暗号文になるんでしたね。

平文ᴱ mod N = 30⁷ mod 77
            = 21870000000 mod 7
	    = 2

暗号文は、2になりました。

復号化してみる

暗号文2を復号化します。
復号化では、プライベート鍵「D=13、N=77」を使います。

「暗号文を表す数をD乗してmod Nをとったもの」が平文になるんでしたね。

暗号文ᴰ mod N = 2¹³ mod 77
             = 8192 mod 77
	     = 30

暗号化する前の平文30を導き出すことができました🎉

まとめ

「暗号技術入門」の公開鍵暗号（RSA)の章を参考に、学んだことをまとめました。本書の説明はとてもわかりやすく、少しでも暗号技術に興味があるようでしたらぜひおすすめしたいです。

Twitterもよければフォローしていただけると嬉しいです！