RSA 暗号の鍵生成・暗号化・復号

素数 $p, q$ から $n = pq$ と $(p - 1) (q - 1)$ を作り、 $e d \equiv 1 (mod (p - 1) (q - 1))$ を満たす復号指数 $d$ を求めて、 $c \equiv m^{e}$ , $m \equiv c^{d} (mod n)$ で暗号化・復号できる

前提

この技能までの道筋（28 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
約数の見つけ方（算数整数の性質）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
n 進法（数学A 整数の性質）
繰り返し二乗法によるべき剰余（大学数学暗号理論）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
ユークリッドの互除法（数学A 整数の性質）
1 次不定方程式の整数解（数学A 整数の性質）
法 $m$ での逆元（拡張ユークリッドの互除法）（大学数学暗号理論）
群の位数と元の位数（大学数学代数学）
有限アーベル群の構造と部分群の個数（大学数学代数学）
剰余類環の単元群とオイラー関数（大学数学代数学）

説明

RSA 暗号は、だれでも使える「公開鍵」で暗号化し、持ち主だけが知る「秘密鍵」でしか復号できないしくみの代表例です。異なる 2 つの素数 $p, q$ から $n = pq$ と $(p - 1) (q - 1)$ を作り、暗号化の指数 $e$ に対して $e d \equiv 1 (mod (p - 1) (q - 1))$ となる復号指数 $d$ を求めます。暗号化は $c \equiv m^{e} (mod n)$ 、復号は $m \equiv c^{d} (mod n)$ というべき剰余の計算だけで行えます。鍵の作成には拡張ユークリッドの互除法を、暗号化と復号には繰り返し二乗法を使います。

なぜそうしてよいのか

$p \neq = q$ を素数とし、 $n = pq$ とおきます。オイラー関数は互いに素な数の積に対して積になり、素数 $p$ では $φ (p) = p - 1$ です。したがって $φ (n) = (p - 1) (q - 1)$ で、これは単元群 $(Z / n Z)^{\times}$ の位数です。元の位数は群の位数を割り切るので、 $g cd (m, n) = 1$ なら $m^{φ (n)} \equiv 1 (mod n)$ が成り立ちます。 $e$ を $g cd (e, φ (n)) = 1$ となるように選べば、 $e$ は法 $φ (n)$ で逆元 $d$ をもちます。このとき $e d = 1 + k φ (n)$ （ $k$ は 0 以上の整数）と書けるので、 $m^{e d} = m \cdot (m^{φ (n)})^{k} \equiv m (mod n)$ となります。つまり、 $e$ 乗して暗号化したものを $d$ 乗すると元に戻ります。

$m$ が $n$ と互いに素でない場合（ $0 \leq m < n$ で $p$ または $q$ の倍数の場合）も、復号は正しく働きます。法 $p$ で考えると、 $p ∣ m$ なら両辺とも $0$ なので $m^{e d} \equiv m$ です。 $p ∤ m$ なら $(Z / p Z)^{\times}$ の位数は $p - 1$ なので $m^{p - 1} \equiv 1$ です。 $e d - 1$ は $p - 1$ の倍数ですから、やはり $m^{e d} \equiv m (mod p)$ になります。法 $q$ でも同じことが言えます。 $p, q$ は互いに素なので、中国剰余定理により $m^{e d} \equiv m (mod n)$ が従います。 $0 \leq m < n$ なので、 $c^{d}$ を $n$ で割った余りは $m$ そのものです。

$(n, e)$ は公開してかまいません。 $d$ を求めるには $(p - 1) (q - 1)$ が必要で、それには $n$ を素因数分解しなければなりません。 $n$ が巨大だとこの分解が現実的に困難であることが、安全性の根拠になっています。

手順

鍵の準備: 異なる素数 $p, q$ を選び、 $n = pq$ と $φ (n) = (p - 1) (q - 1)$ を計算する。
暗号化指数を選ぶ: $1 < e < φ (n)$ かつ $g cd (e, φ (n)) = 1$ となる $e$ を選ぶ。公開鍵は $(n, e)$ である。
復号指数を求める: 拡張ユークリッドの互除法で $e x + φ (n) y = 1$ を解き、 $d \equiv x (mod φ (n))$ を $0 < d < φ (n)$ の範囲に直す。 $d$ が秘密鍵である。
暗号化: 平文 $0 \leq m < n$ に対して $c = m^{e} mod n$ を繰り返し二乗法で計算する。
復号: $m = c^{d} mod n$ を繰り返し二乗法で計算する（法は $φ (n)$ ではなく $n$ ）。

例題

$p = 5, q = 11, e = 3$ として RSA 暗号の鍵を作る。暗号文 $c = 13$ を復号して得られる平文 $m$ （ $0 \leq m < 55$ ）を求めよ。

例題の解答

【手順 1】 $n = 5 \cdot 11 = 55$ 、 $φ (n) = 4 \cdot 10 = 40$ である。
【手順 2】 $g cd (3, 40) = 1$ なので、 $e = 3$ は条件を満たす。
【手順 3】互除法を行うと $40 = 3 \cdot 13 + 1$ となる。よって $1 = 40 - 3 \cdot 13$ であり、 $3 \cdot (- 13) \equiv 1 (mod 40)$ が成り立つ。 $d \equiv - 13 \equiv 27 (mod 40)$ なので $d = 27$ である。確認すると $3 \cdot 27 = 81 = 2 \cdot 40 + 1$ となる。
【手順 5】 $1 3^{27} mod 55$ を求める。 $27 = 16 + 8 + 2 + 1$ （2 進法で $1101 1_{(2)}$ ）なので、 $13$ の 2 の累乗乗を順に 2 乗して求める。
$1 3^{1} \equiv 13$
$1 3^{2} = 169 \equiv 4$
$1 3^{4} \equiv 16$
$1 3^{8} \equiv 256 \equiv 36$
$1 3^{16} \equiv 3 6^{2} = 1296 \equiv 31$
これらを掛け合わせると $1 3^{27} \equiv 31 \cdot 36 \cdot 4 \cdot 13 (mod 55)$ である。順に計算すると $31 \cdot 36 = 1116 \equiv 16$ 、 $16 \cdot 4 = 64 \equiv 9$ 、 $9 \cdot 13 = 117 \equiv 7$ となる。よって $m = 7$ である。
（検算: $7^{3} = 343 = 6 \cdot 55 + 13$ なので、 $7$ を暗号化すると確かに $13$ になる。）

答え: $7$

よくある誤り

$d$ を法 $n$ の逆元として求めてしまう誤り。例では $3^{- 1} mod 55 = 37$ としても復号できない。正しくは法 $φ (n) = (p - 1) (q - 1) = 40$ での逆元で、 $d = 27$ である。
$φ (n)$ を $n - 1 = pq - 1$ としてしまう誤り。例では $54$ としてしまう。正しくは $φ (n) = (p - 1) (q - 1) = 40$ である（ $n$ は素数ではない）。
$g cd (e, φ (n)) \neq = 1$ の $e$ を選んでしまう誤り。たとえば $φ (n) = 40$ で $e = 5$ とすると、逆元 $d$ が存在しない。正しくは、 $g cd (e, φ (n)) = 1$ を必ず確かめてから $e$ を決める。
拡張互除法で得た負の $x$ をそのまま $d$ にしたり、べき剰余を法 $φ (n)$ で計算したりする誤り。例では $d = - 13$ としてしまったり、 $1 3^{27} mod 40$ を計算してしまったりする。正しくは $d = - 13 + 40 = 27$ に直し、復号は $1 3^{27} mod 55$ で計算する。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

RSA 暗号の鍵生成・暗号化・復号

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題