RSA暗号

同義語：RSA cryptosystem

概要

前提知識: 合同式, Eulerのφ関数, Fermatの小定理, 拡張Euclidの互除法

$2$ つの素数 $p=61$、$q=53$ を選び、$n=pq=3233$ とする。$\varphi(n)=(p-1)(q-1)=3120$ と互いに素な数 $e=17$ を選び、$17d\equiv1\pmod{3120}$ となる $d=2753$ を求めておく（$17\cdot2753=46801=15\cdot3120+1$）。$n=3233$ と $e=17$ は誰にでも公開し、$d=2753$ だけを秘密にする。誰かが $0$ 以上 $3233$ 未満の数 $m=65$ を送りたければ、$65^{17}$ を $3233$ で割った余り $c=2790$ を計算して送る。受け取った人が $2790^{2753}$ を $3233$ で割った余りを計算すると、元の $65$ が戻ってくる。暗号化に使う $(n,e)$ は公開されているのに、復号に必要な $d$ を求めることは $n$ の素因数分解と同じ難しさであり、$n$ が数百桁なら分解は現実的な時間ではできないと信じられている。
これが RSA暗号 の仕組みであり、暗号化の鍵を公開しても安全であることを目指す 公開鍵暗号（公開鍵暗号）の代表例である。本記事では鍵の作り方と暗号化・復号を定義し、復号で元の数が戻ることを、平文が $n$ と互いに素でない場合も含めて証明する。あわせて、暗号化が全単射になるための条件、大きな冪を速く計算する繰り返し二乗法、$\varphi(n)$ を知ることと $n$ を分解することの同値性を示し、安全性が証明された定理ではなく計算の困難さについての仮定に基づくことを説明する。

定義

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

鍵の生成：相異なる素数 $p,q$ を選び、$n:=pq$、$\varphi(n)=(p-1)(q-1)$ とする。$1< e<\varphi(n)$ かつ $\gcd(e,\varphi(n))=1$ を満たす整数 $e$ を選び、$ed\equiv1\pmod{\varphi(n)}$、$0< d<\varphi(n)$ を満たす整数 $d$ を求める。$(n,e)$ を 公開鍵、$d$ を 秘密鍵 という（$p,q,\varphi(n)$ も秘密にする）。
暗号化：平文 $m\in\{0,1,\dots,n-1\}$ に対し、$m^e$ を $n$ で割った余りを $c$ とし、これを暗号文とする。$c\equiv m^e\pmod n$、$0\le c< n$ である。
復号：暗号文 $c$ に対し、$c^d$ を $n$ で割った余りを計算する。

$d$ の存在は、$\gcd(e,\varphi(n))=1$ と合同式の記事の命題「逆元が存在する条件」から従い、実際の $d$ は拡張Euclidの互除法で求まる（ex-rsa-3233）。$\varphi(n)=(p-1)(q-1)$ は Eulerのφ関数の乗法性による（同記事の例「RSA暗号とφ(pq)」）。$\varphi(n)$ の代わりに $\lambda:=\operatorname{lcm}(p-1,q-1)$（最小公倍数）を法として $ed\equiv1$ となる $d$ を使っても、復号は正しく働く（thm-rsa-correct は $p-1\mid ed-1$、$q-1\mid ed-1$ だけを使う）。実際の運用では、文字列を $n$ 未満の数の列に符号化してから暗号化し、さらに乱数を加える処理（パディング）を行う（rem-rsa-practice）。

直感

RSA暗号は「一方向には簡単で、逆向きは秘密の情報がなければ難しい」計算に基づく。$m$ から $m^e\bmod n$ を求めるのは、繰り返し二乗法（prop-rsa-square-multiply）により数百桁の数でも一瞬である。逆に $c$ から「$e$ 乗して $c$ になる数」を法 $n$ で求めるのは、$d$ を知っていれば $c^d$ を計算するだけで済むが、$d$ を知らずにこれを行う方法として、$n$ を分解する以外に効率のよいものは知られていない。$d$ は $\varphi(n)=(p-1)(q-1)$ から作られ、$p,q$ を知っている鍵の持ち主だけが簡単に計算できる。郵便受けにたとえれば、投函口（公開鍵）は誰でも使えるが、取り出すための鍵（秘密鍵）は持ち主しか持っていない。

例と反例

小さな鍵での計算

冒頭の $p=61$、$q=53$、$n=3233$、$\varphi(n)=3120$、$e=17$ で計算する。
$d$ の計算：拡張Euclidの互除法で $3120=183\cdot17+9$、$17=1\cdot9+8$、$9=1\cdot8+1$ と割り、逆にたどると
$$ 1=9-8=9-(17-9)=2\cdot9-17=2(3120-183\cdot17)-17=2\cdot3120-367\cdot17 $$
である。よって $17\cdot(-367)\equiv1\pmod{3120}$ で、$d=-367+3120=2753$ である。
暗号化：$17=16+1$ なので、$65$ を $4$ 回続けて $2$ 乗して $n$ で割った余りをとると $65^2\equiv992$、$65^4\equiv1232$、$65^8\equiv1547$、$65^{16}\equiv789$ であり、$65^{17}\equiv789\cdot65\equiv2790\pmod{3233}$ である。掛け算は $5$ 回で済む。
復号：$2753$ は $2$ 進法で $101011000001$（$12$ 桁で $1$ が $5$ 個）なので、繰り返し二乗法で $11$ 回の $2$ 乗と $4$ 回の掛け算により $2790^{2753}\equiv65\pmod{3233}$ が確かめられる。$0\le m<3233$ のすべての $m$ について $(m^{17})^{2753}\equiv m\pmod{3233}$ が成り立つことは thm-rsa-correct による。

反例：$e$ と $\varphi(n)$ が互いに素でないと暗号文から平文が決まらない

$n=3233$ のまま $e=3$ とすると、$3120=3\cdot1040$ なので $\gcd(3,\varphi(n))=3$ である。このとき
$$ 1^3\equiv1,\qquad1538^3\equiv1,\qquad2121^3\equiv1\pmod{3233} $$
であり、異なる $3$ つの平文 $1,1538,2121$ が同じ暗号文 $1$ になる。受け取った人は $c=1$ からどれが送られたかを決められず、どんな $d$ を使っても復号は正しく働かない（$3d\equiv1\pmod{3120}$ となる $d$ も存在しない）。$e=3$ は「$1< e<\varphi(n)$」を満たすが「$\gcd(e,\varphi(n))=1$」を満たさず、「$m\mapsto m^e\bmod n$ は $\{0,\dots,n-1\}$ の上で単射である」という含意が破れる（prop-rsa-bijection）。

反例：$p=q$ にすると互いに素でない平文が復号されない

$p=q=3$、$n=9$ とし、$\varphi(9)=6$ と互いに素な $e=5$、$5d\equiv1\pmod6$ となる $d=5$ をとる。平文 $m=3$ は $3^5=243\equiv0\pmod9$ と暗号化され、$0^5=0\ne3$ なので元に戻らない。$n=9$ は「$ed\equiv1\pmod{\varphi(n)}$」を満たすが、「$n$ は相異なる素数の積」という仮定を満たさず、「すべての $m$ について $m^{ed}\equiv m\pmod n$」という含意が破れる。$m$ が $n$ と互いに素なら Eulerの定理(整数論)により $m^{ed}\equiv m$ は成り立つので、破れるのは $3\mid m$ の平文だけである。thm-rsa-correct の証明で $n$ が平方因子をもたないことを使う箇所がここにあたる。

性質

復号の正しさ

$n$ を相異なる素数の積とし、$e,d$ を正の整数で、$n$ のすべての素因数 $p$ について $p-1\mid ed-1$ を満たすものとする。このとき、すべての整数 $m$ について
$$ m^{ed}\equiv m\pmod n $$
が成り立つ。特に def-rsa の鍵について、平文 $m\in\{0,\dots,n-1\}$ を暗号化して復号すると $m$ に戻る。

素因数ごとに Fermat の小定理を使う

$n$ の素因数 $p$ を 1 つとり、$m^{ed}\equiv m\pmod p$ を示す。$ed\ge1$ なので $ed-1=(p-1)t$ となる整数 $t\ge0$ がある。$p\mid m$ なら両辺とも $p$ の倍数である。$p\nmid m$ なら、Fermatの小定理により $m^{p-1}\equiv1\pmod p$ なので
$$ m^{ed}=m\cdot\bigl(m^{p-1}\bigr)^t\equiv m\pmod p $$
である。
$n=p_1\cdots p_r$（$p_i$ は相異なる素数）とすると、$x=m^{ed}$ と $x=m$ はどちらも連立合同式 $x\equiv m\pmod{p_i}$（$i=1,\dots,r$）の解である。$p_1,\dots,p_r$ は対ごとに互いに素なので、中国剰余定理の記事の定理「中国剰余定理」により解は $p_1\cdots p_r=n$ を法としてただ 1 つであり、$m^{ed}\equiv m\pmod n$ である。
RSA の鍵では $p-1$ と $q-1$ はどちらも $\varphi(n)=(p-1)(q-1)$ を割り切り、$\varphi(n)\mid ed-1$ なので仮定が満たされる。暗号文 $c$ は $c\equiv m^e\pmod n$ を満たすので $c^d\equiv m^{ed}\equiv m\pmod n$ であり、$0\le m< n$ なので $c^d$ を $n$ で割った余りは $m$ である。$\square$

$m$ が $n$ と互いに素な場合は、Eulerの定理(整数論) の記事の例「RSA暗号の復号」のように Euler の定理 $m^{\varphi(n)}\equiv1\pmod n$ から直ちに従う。互いに素でない $m$（$p$ か $q$ の倍数）でも復号が正しいことは、素因数ごとに分けて初めて見える。$p=q$ を許すとこの部分が破れる（ex-rsa-square）。同じ証明は Ste17 Proposition 3.3.1（p. 57）、Sho08 §4.7（p. 100）にある。

暗号化が全単射になる条件

$p,q$ を相異なる素数、$n=pq$、$e$ を正の整数とし、$E\colon\{0,\dots,n-1\}\to\{0,\dots,n-1\}$ を $m^e$ を $n$ で割った余りを返す写像とする。次は同値である。

$E$ は全単射である。
$E$ は単射である。
$\gcd(e,\varphi(n))=1$ である。

原始根で単射性の破れを作る

1 ⇒ 2 は明らかである。
3 ⇒ 1：合同式の記事の命題「逆元が存在する条件」により $ed\equiv1\pmod{\varphi(n)}$ となる正の整数 $d$ がある。$m^d$ を $n$ で割った余りを返す写像を $D$ とすると、thm-rsa-correct により $D(E(m))=m$ がすべての $m$ で成り立つ。同様に $E(D(m))=m$ も成り立つ（$de=ed$）。よって $E$ は全単射で、逆写像は $D$ である。
2 ⇒ 3：対偶を示す。$\gcd(e,(p-1)(q-1))>1$ なら、$e$ は $p-1$ か $q-1$ と共通の素因数をもつ。$g:=\gcd(e,p-1)>1$ としてよい。原始根の記事の定理「素数を法とする原始根の存在」により、法 $p$ の原始根 $r$ がある。$a:=r^{(p-1)/g}$ とおくと、$r$ の位数は $p-1$ で $(p-1)/g< p-1$ なので $a\not\equiv1\pmod p$ であり、一方 $e/g$ は整数なので $a^e=r^{(p-1)(e/g)}\equiv1\pmod p$ である。中国剰余定理の記事の定理「中国剰余定理」により、$m\equiv a\pmod p$、$m\equiv1\pmod q$、$0\le m< n$ となる $m$ がある。$m^e\equiv1\pmod p$、$m^e\equiv1\pmod q$ なので $E(m)=1=E(1)$ であり、$m\not\equiv1\pmod p$ より $m\ne1$ である。よって $E$ は単射でない。$\square$

ex-rsa-noncoprime-e はこの証明の最後の段の具体例である。$e=3$ は $p-1=60$ と共通因数 $3$ をもち、$q-1=52$ とは互いに素である。平文 $1538$ は $1538\equiv13\pmod{61}$、$1538\equiv1\pmod{53}$ を満たし、$13^3=2197\equiv1\pmod{61}$ なので、証明の $m$ の役を果たしている。

繰り返し二乗法

暗号化と復号には、数百桁の $e,d$ に対する冪 $m^e\bmod n$ が必要になる。$m$ を $e-1$ 回掛けるのでは到底終わらないが、$e$ を $2$ 進法で書けば掛け算の回数は $e$ の桁数程度で済む。

繰り返し二乗法

正の整数 $e$ を $2$ 進法で $e=\sum_{i=0}^kb_i2^i$（$b_i\in\{0,1\}$、$b_k=1$、$k=\lfloor\log_2e\rfloor$）と書く。整数 $m$ と $n\ge2$ について、$m_0:=m\bmod n$、$m_{i+1}:=m_i^2\bmod n$ とおき、$b_i=1$ となる $i$ について $m_i$ を掛けては $n$ で割った余りをとると、$m^e\bmod n$ が得られる。使う掛け算（とその後の割り算）は $2k$ 回以下である。

指数の 2 進展開

帰納法により $m_i\equiv m^{2^i}\pmod n$ である（$m_{i+1}\equiv m_i^2\equiv(m^{2^i})^2=m^{2^{i+1}}$）。したがって
$$ m^e=\prod_{b_i=1}m^{2^i}\equiv\prod_{b_i=1}m_i\pmod n $$
であり、右辺を途中で $n$ で割った余りに置き換えながら計算しても法 $n$ での値は変わらない（合同式の記事の命題「合同式の和・差・積・冪」）。$m_1,\dots,m_k$ を作る $2$ 乗が $k$ 回、$b_i=1$ となる $k+1$ 個以下の $m_i$ を掛け合わせるのが $k$ 回以下なので、合計 $2k$ 回以下である。$\square$

途中の数は $n^2$ 未満に保たれるので、$n$ が $600$ 桁程度でも計算機で瞬時に計算できる。$e=65537=2^{16}+1$ なら $16$ 回の $2$ 乗と $1$ 回の掛け算で済む。この方法は Ste17 §2.3.2（p. 34）、Sho08 §3.4（pp. 65–66）にある。

$\varphi(n)$ を知ることと $n$ の分解

$\varphi(n)$ と素因数分解の同値性

$n=pq$（$p\ne q$ は素数）とする。$p,q$ が分かれば $\varphi(n)=(p-1)(q-1)$ が分かり、逆に $n$ と $\varphi(n)$ が分かれば、$p,q$ は $2$ 次方程式
$$ x^2-(n-\varphi(n)+1)\,x+n=0 $$
の $2$ つの解として求まる。

和と積から 2 数を求める

前半は明らかである。$\varphi(n)=(p-1)(q-1)=pq-(p+q)+1=n-(p+q)+1$ なので $p+q=n-\varphi(n)+1$、$pq=n$ である。よって $(x-p)(x-q)=x^2-(p+q)x+pq$ は与えられた多項式に等しく、その解は $p,q$ である。$\square$

$n=3233$、$\varphi(n)=3120$ なら $x^2-114x+3233=0$ で、判別式は $114^2-4\cdot3233=64=8^2$、解は $(114\pm8)/2=61,53$ である。同じ事実は Eulerのφ関数の記事の例「RSA暗号とφ(pq)」にもあり、Ste17 §3.4.1（pp. 61–62）にある。したがって公開鍵 $(n,e)$ から $\varphi(n)$ を求めることは $n$ の分解と同じ難しさである。さらに、秘密鍵 $d$ を知れば $ed-1$ が $\varphi(n)$ の倍数になることを使って、高い確率で $n$ を分解する方法がある（Ste17 §3.4.3 の Algorithm 3.4.5、pp. 63–65。Sho08 §4.7、p. 101）。

補足

安全性は証明された定理ではない

RSA暗号の安全性は、大きな $n=pq$ の素因数分解が現実的な時間ではできないという、証明されていない仮定に基づく。$n$ を分解できれば $\varphi(n)$ と $d$ が求まり暗号は破られるが、逆に「$n$ を分解せずに暗号文から平文を求める方法はない」ことも証明されていない（Sho08 §4.7、p. 101）。素因数分解の既知の方法と計算量については素因数分解の記事の注意「素因数分解の計算量」を参照。十分大きな量子計算機があれば Shor の方法で素因数分解は多項式時間でできることが知られている（同注意）。したがって「RSA暗号は安全である」は数学の定理ではなく、現在の計算技術と未解決問題についての判断である。

実際の運用での注意

def-rsa のままの暗号化は、同じ平文をいつも同じ暗号文にする。攻撃者が候補の平文をいくつか知っていれば、自分で暗号化して比べるだけでどれが送られたかが分かる。これを防ぐため、実際には平文に乱数を加えてから暗号化する（Sho08 §4.7、p. 101。Ste17 §3.3.2、p. 58）。また次のような鍵や平文は避けなければならない。

$e$ が小さく平文も小さく、$m^e< n$ となる場合、$c=m^e$ は割り算の余りをとる前の整数そのものなので、$c$ の整数としての $e$ 乗根をとれば $m$ が求まる。
$p$ と $q$ が近い場合、$p,q$ が奇素数なら $n=t^2-s^2$（$t=(p+q)/2$、$s=|p-q|/2$ は整数）と書けて、 $t$ が $\sqrt n$ に近いので、$t=\lceil\sqrt n\rceil,\lceil\sqrt n\rceil+1,\dots$ と順に試して $t^2-n$ が平方数になるものを探せば分解できる（Fermat の方法）。たとえば $n=23360947609$ では $t=152845$ で $t^2-n=804^2$ となり、$n=153649\cdot152041$ と分かる（Ste17 §3.4.2、pp. 62–63）。
公開する $e$ としては $3$、$17$、$65537$ のような小さい数がよく使われる（Ste17 Remark 3.3.4、p. 61）。

電子署名

$e$ と $d$ の役割を入れ替えると 電子署名 になる。鍵の持ち主は文書を表す数 $m$ に対して $s:=m^d\bmod n$ を署名として付け、受け取った人は公開鍵で $s^e\bmod n$ を計算して $m$ と一致するかを確かめる。一致することは thm-rsa-correct（$de=ed$）による。$d$ を知らない人は、与えられた $m$ に対して正しい $s$ を作れないと考えられている。$n=3233$、$e=17$、$d=2753$ では、$m=65$ の署名は $s=65^{2753}\bmod3233=588$ で、$588^{17}\equiv65\pmod{3233}$ である。

歴史と文献

RSA の名は、1970 年代後半にこの方式を考案した Rivest、Shamir、Adleman の頭文字による（Cri24 Historical remark 11.5.2、p. 169）。論文は RSA78 として 1978 年に発表され、題名のとおり電子署名にも使えることが示された。同じ所によれば、英国の政府通信本部（GCHQ）ではそれ以前に同様の方式が機密扱いで考案されていた。鍵の生成から復号の証明までは Ste17 §3.3（pp. 56–57）と Sho08 §4.7（pp. 99–100）、攻撃の方法は Ste17 §3.4（pp. 61–66）、安全性についての注意は Cri24 §11.6（p. 174 以降）にある。