↓メインコンテンツへスキップ
  1. Blog/

RSA暗号の仕組み

目次

RSA暗号の仕組みについて書きました。

はじめに #

こんにちは、IKです。

自分が学んだことを文書として記録しておこうと考え、記述します。

今回はRSA暗号の仕組みについてまとめました。

RSA暗号とは #

まず、簡単にRSA暗号とは何なのかについて書きたいと思います

RSA暗号は、公開鍵暗号方式の一種です。

現在、公開鍵暗号方式のデファクトスタンダードとして利用されています。

公開鍵暗号方式は、公開鍵と秘密鍵のペアを使用してデータを暗号化および復号化します。

このRSA暗号は「非常に大きな数の素因数分解が困難であること」を利用して暗号化されています。

では、実際の暗号化の仕組みを見ていきましょう。

RSA暗号の仕組み #

とりあえず、RSA暗号の仕組みを式で表します。

  • ① 暗号化（公開鍵で暗号） $$x^e \bmod N \equiv C $$

  • ② 復号化（秘密鍵で復号） $$ C^d \bmod N \equiv x $$

1つずつ説明していきます。

記号説明
\(x\)送信したい平文
\(^d\)秘密鍵
\(^e\)公開鍵
\(\bmod\)剰余演算（プログラミングの%）
\(N\)公開されている法数
\(\equiv\)合同
\(C\)暗号文

RSA暗号はこのように暗号化と復号化が行われています。

では、式をわかりやすく１文に変換したいと思います。

下記が暗号化の式です。 $$ x^e \bmod N \equiv C $$

この式はこのようにも表せます。 $$ x^e \equiv C\bmod N $$

つまり、\(x^e\) は \(C\) と法数 \(N\) 上において合同だと示せます。

そして、復号化の式で \(x^e \equiv C\) を考慮すると $$ x^{e \cdot d}\bmod N\equiv x $$

この式はこのようにも表せます。 $$ x^{e \cdot d}\equiv x \bmod N$$

\(x^{e \cdot d}\) は法数 \(N\) 上において、\(x\) （平文）と合同だと示すことができます。

つまり、平文に秘密鍵と公開鍵を掛けたものを累乗することで、法数 \(N\) 上においては平文に戻るということがわかります。

公開鍵からの暗号化、秘密鍵からの暗号化（デジタル署名）、どちらにも対応しているという事がわかりますね。

素因数分解との関係性も含めて、次の章で解説します。

RSA暗号と素因数分解の関係 #

  • ③ \(e\) , \(d\) , \(p\) , \(q\) の関係は下記の式で表せます。 $$e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)$$

1つずつ説明していきます。

記号説明
\(d\)秘密鍵
\(e\)公開鍵
\(\equiv\)合同
\(\bmod\)剰余演算（プログラミングの%）
\(\mathrm{lcm}\)最小公倍数
\(p\)法数 \(N\) を素因数分解したもの
\(q\)法数 \(N\) を素因数分解したもの

上記の式を満たす \(e\) , \(d\) , \(p\) , \(q\) であれば、\(x^{e \cdot d}\equiv x \bmod N\) が一般に成り立ちます。

なぜ、上記の式を満たす時、\(x^{e \cdot d}\equiv x \bmod N\) が成り立つのかというのは今回は省略します。

省略した部分は下記の記事で説明しています。

RSA暗号の仕組み 補足

鍵の生成方法 #

秘密鍵 \(d\) は \((p - 1) \cdot (q -1)\) と互いに素となる関係で生まれます。

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

次に公開鍵は \(e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)\) を満たすように算出されます。

公開鍵は秘密鍵のモジュラー逆数と言えます。

つまり、鍵の生成は2つの非常に大きな素数 \(p\) , \(q\) の生成から始まるということがわかります。

法数 \(N\) が素因数分解されると #

この式において、公開鍵 \(e\) は知られています、

それに加えて、法数 \(N\) の素因数である \(p\) と \(q\) を知られてしまう、つまり、\(N\) を素因数分解されてしまうと、

拡張ユークリッドの互除法を用いて、秘密鍵である \(d\) を簡単に算出することができます。

実際に暗復号化してみた #

では、実際にRSA暗号の暗号化、復号化のプロセスを辿ろうと思います。

まず、鍵の生成を行います。

鍵の生成は2つの素数の生成から始まります。

  • \(p = 11\)
  • \(q = 13\)

今回はこの2つの素数で進めていきたいと思います。

秘密鍵の生成 #

秘密鍵 \(d\) は \((p - 1) \cdot (q -1)\) と互いに素となる関係なので、

\((11 -1) \cdot (13 - 1) = 120\)

120を素因数分解します。

\(120 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5\)

互いに素となる関係の \(d\) (秘密鍵) を策定します。

  • 秘密鍵： \(d = 7\)

公開鍵の生成 #

次に公開鍵を算出します。

\(e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)\)

この式を満たす \(e\) (公開鍵) であるため、

\(7 \cdot e \equiv 1 \bmod \mathrm{lcm}(11-1,13-1)\)

もう少しわかりやすくします。

\(\mathrm{lcm}(11-1,13-1)\) は 10と12の最小公倍数なので60ですね。

\(7 \cdot e \bmod 60 \equiv 1\)

この計算に拡張ユークリッドの互除法を使うのですが、今回はPythonにやらせます。

# 拡張ユークリッドの互除法
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return (gcd, y - (b // a) * x, x)

print(extended_gcd(7,60)[1])

結果、-17と出ました。負の数なので、正の範囲に直します。

-17の法数60上の逆数は \(60-17\) で \(43\) になります。

\(-17 = 60 \cdot (-1) + 43\) （余りは正の形で）

ということで、\(e = 43\) ということがわかりました。

\(7 \cdot 43 \bmod 60 \equiv 1\)

公開鍵を算出することができました。

  • 公開鍵： \(e = 43\)

暗号化 #

鍵の作成ができたので早速暗号化をしてみましょう。

まず、平文の策定を行います。

  • 平文： 5

今回、平文は10進数で5とします。5月だから。

下記の式に当てはめて暗号化します。

  1. \(x^e \bmod N \equiv C\)

  2. \(5^{43} \bmod 11 \cdot 13 \equiv C\)

  3. \(11136868377216160297393798828125 \bmod 143 \equiv 125\)

暗号文を得ることができました。

  • 暗号文： 125

復号化 #

では、作成した暗号文を復号していきましょう。

下記の式に当てはめて復号化します。

  1. \(C^d \bmod N \equiv x\)

  2. \(125^7 \bmod 11 \cdot 13 \equiv x\)

  3. \(476837158203125 \bmod 143 \equiv 5\)

無事、平文を復号することができました。

素因数分解されたらどうなるのか #

では、実際に法数\(N\)が素因数分解されたら、どのようにして秘密鍵が算出されてしまうのかを検証していきたいと思います。

上記の暗復号化で使用した数値を流用します。

下記に数値をまとめます。

項目数値
法数 \(N\)143
秘密鍵 ：\(d\)7
公開鍵 ：\(e\)43
法数の素因数：\(p\)11
法数の素因数：\(q\)13

今回、秘密鍵の数値は知らないという前提で進めます。

公開鍵 \(43\) は当然知られていて、法数 \(143\) も素因数分解されてしまい、\(p\) と \(q\) の数値 \(11\) と \(13\) が知られしまったという状況を想定します。

  • \(e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)\)

前述のこの式を用いて、秘密鍵を算出します。

数値を当てはめていきましょう。

  1. \(e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)\)

  2. \(43 \cdot d \equiv 1\bmod \mathrm{lcm}(10,12)\)

  3. \(43 \cdot d \equiv 1\bmod 60\)

  4. \(43 \cdot d \bmod 60 \equiv 1 \)

この式まで変換できれば、あとは前述の通り、公開鍵を算出した手順で秘密鍵も算出することができますね。

また、Pythonにやってもらいましょう。

# 拡張ユークリッドの互除法
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return (gcd, y - (b // a) * x, x)

print(extended_gcd(43,60)[1])

無事、秘密鍵 \(7\) を算出することが来ました。

今回は最初から正の範囲でしたので変換する必要はありませんでした。

まとめ #

重要な部分をまとめておきたいと思います。

重要なのはこの3つの式です。

  • ① 暗号化（公開鍵で暗号） $$x^e \bmod N \equiv C $$

  • ② 復号化（秘密鍵で復号） $$ C^d \bmod N \equiv x $$

  • ③ \(e\) , \(d\) , \(p\) , \(q\) の関係 $$e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)$$

③の式が成り立つ \(e\) , \(d\) , \(p\) , \(q\) の場合、①②も一般に成り立ちます。

終わりに #

RSA暗号と素因数分解の関係について書きました。

ちなみにRSA暗号のRSAは考案者3人の名前の頭文字です。

独学であるため、間違って理解している部分がある可能性が大いにあります。

その場合、Xやメールなどで連絡していただけると幸いです。

備忘録としてこの文書を残しますが、誰かの学びの糧となれば幸いです。

最後までお読みいただきありがとうございました。

↑