RSA暗号（高校数学）

同義語：RSA cryptosystem (high school mathematics)

概要

前提知識: Fermatの小定理と冪の余り, 合同式の割り算と逆元, 中国剰余定理（高校数学）, Eulerのφ関数（高校数学）

高校での出発点：累乗して、累乗で戻す

数 $m$ を $e$ 乗して別の数に変え、それをさらに $d$ 乗すると $m$ に戻る。そんな $e$ と $d$ の組があれば、$e$ 乗を「暗号にする」操作、$d$ 乗を「元に戻す」操作として使える。Fermatの小定理と冪の余りで学んだ $a^{p-1}\equiv1\pmod p$ は、そのような組を作る道具になる。この記事では、2 つの素数の積を法とするこの仕組み（RSA 暗号）がいつも正しく元に戻ることを、Fermat の小定理と中国剰余定理（高校数学）の考え方で証明し、小さな数で計算してみる。大学向けの用語解説は RSA暗号で、ここでは $n=pq$ の場合の正しさの証明と小さな数の例に絞る。

法 $11$ で $3$ 乗して $7$ 乗で戻す

$m=5$ を $3$ 乗すると $5^3=125=11\cdot11+4$ で、法 $11$ で $4$ になる。この $4$ を $7$ 乗する。$2$ 乗を繰り返すと
$$ 4^2=16\equiv5,\qquad 4^4=(4^2)^2\equiv5^2=25\equiv3\pmod{11} $$
で、$7=4+2+1$ なので
$$ 4^7=4^4\cdot4^2\cdot4\equiv3\cdot5\cdot4=60=5\cdot11+5\equiv5\pmod{11} $$
である。$5$ に戻った。
戻る理由は、$3\cdot7=21=2\cdot10+1$ にある。Fermat の小定理 $m^{10}\equiv1\pmod{11}$（$11$ で割り切れない $m$）を使うと、$(m^3)^7=m^{21}=m\cdot(m^{10})^2\equiv m$ となる。

ex-rsahs-start-11 の方法には弱点がある。法 $11$ と $e=3$ を知っている人は、$3d\equiv1\pmod{10}$ を解いて $d=7$ をすぐに求められる。法から $10=11-1$ が分かってしまうからである。RSA 暗号では、法を 2 つの素数の積 $n=pq$ にする。$n$ を公開しても、$p$ と $q$ を知らない人は「$10$ に当たる数」$(p-1)(q-1)$ をすぐには求められない（求めるには $n$ を素因数分解することになる。prop-rsahs-factor）。

法 $55$ で $3$ 乗して $27$ 乗で戻す

$p=5$、$q=11$、$n=55$ とし、$e=3$、$d=27$ とする。$m=7$ を $3$ 乗すると $7^3=343=6\cdot55+13$ で、法 $55$ で $c=13$ になる。
$c=13$ を $27$ 乗する。$2$ 乗を繰り返して法 $55$ の余りをとると
$$ 13^2=169\equiv4,\quad13^4\equiv4^2=16,\quad13^8\equiv16^2=256\equiv36,\quad13^{16}\equiv36^2=1296\equiv31\pmod{55} $$
である（$169=3\cdot55+4$、$256=4\cdot55+36$、$1296=23\cdot55+31$）。$27=16+8+2+1$ なので
$$ 13^{27}=13^{16}\cdot13^8\cdot13^2\cdot13\equiv31\cdot36\cdot4\cdot13\pmod{55} $$
で、$31\cdot36=1116=20\cdot55+16$、$16\cdot4=64\equiv9$、$9\cdot13=117=2\cdot55+7$ より $13^{27}\equiv7\pmod{55}$ である。$m=7$ に戻った。

ex-rsahs-start-55 の $e=3$、$d=27$ は、$3\cdot27=81=2\cdot40+1$、$40=(5-1)(11-1)$ という関係で選んだ。この記事で答える問いは次の 3 つである。

$d$ はどう選べばよいか。いつ選べるか。→ def-rsahs-keys、prop-rsahs-d
どんな $m$ でも、$e$ 乗してから $d$ 乗すると元に戻るか。$m$ が $5$ や $11$ で割り切れるときはどうか。→ thm-rsahs-main

$n$ と $e$ を公開しても、$d$ が知られにくいのはなぜか。→ prop-rsahs-factor

高校の計算	この記事の言葉	大学の言葉
$ed\equiv1\pmod{(p-1)(q-1)}$ となる $d$ を互除法で求める	秘密の鍵（def-rsahs-keys）	$\mathbb{Z}/\varphi(n)\mathbb{Z}$ での逆元
$p$ と $q$ で別々に Fermat の小定理を使う	復号の正しさ（thm-rsahs-main）	中国剰余定理による $\mathbb{Z}/n\mathbb{Z}$ の分解
$2$ 乗を繰り返して累乗の余りを求める	繰り返し 2 乗法（rem-rsahs-square）	指数の 2 進展開
$p+q$ と $pq$ から 2 次方程式で $p,q$ を求める	$L$ が分かれば $n$ が分解できる（prop-rsahs-factor）	$\varphi(n)$ を知ることと素因数分解の同値性

仕組み：鍵を作る、暗号にする、元に戻す

鍵の定義

RSA 暗号の鍵、暗号化、復号

相異なる素数 $p$、$q$ をとり、$n=pq$、$L=(p-1)(q-1)$ とおく。$L$ と互いに素な正の整数 $e$ を選び、$ed\equiv1\pmod L$ を満たす正の整数 $d$ をとる。$(n,e)$ を 公開鍵、$d$ を 秘密鍵 という。
$0\le m< n$ の整数 $m$（平文）に対し、$m^e$ を $n$ で割った余り $c$ を 暗号文 とする（暗号化）。$c^d$ を $n$ で割った余りを求めることを復号という。

$L=(p-1)(q-1)$ は、$1$ から $n$ までのうち $n$ と互いに素な数の個数 $\varphi(n)$ に等しい（Eulerのφ関数（高校数学））。鍵の作り方は Ste17 §3.3、暗号化と復号の手順は Cri24 の Algorithm 11.5.5 と同じである。文字の列を送るときは、文字を数に直し（n進法と記数法のように、何文字かをまとめて 1 つの数にしてもよい）、$n$ より小さい数の列にしてから暗号化する。

小さな鍵の例

$p=5$、$q=11$ なら $n=55$、$L=4\cdot10=40$ である。$e=3$ は $40$ と互いに素で、$d=27$ は $3\cdot27=81=2\cdot40+1$ を満たす。公開鍵は $(55,3)$、秘密鍵は $27$ である。
$p=11$、$q=13$ なら $n=143$、$L=10\cdot12=120$ である。$e=7$ は $120$ と互いに素で、$d=103$ は $7\cdot103=721=6\cdot120+1$ を満たす。

秘密鍵 $d$ の求め方

秘密鍵 $d$ の存在

$\gcd(e,L)=1$ なら、$ed\equiv1\pmod L$ を満たす正の整数 $d$ が、$1\le d< L$ の範囲にただ 1 つある。$\gcd(e,L)\ne1$ なら、そのような整数 $d$ はない。

方針：$d$ は法 $L$ での $e$ の逆元なので、合同式の割り算と逆元の定理「逆元をもつ条件」と命題「逆元はあれば 1 つ」を使う。
段 1（存在）。合同式の割り算と逆元の定理「逆元をもつ条件」により、$\gcd(e,L)=1$ なら $ed_0\equiv1\pmod L$ となる整数 $d_0$ がある。$d_0$ を $L$ で割った余りを $d$ とすると $d\equiv d_0$ なので $ed\equiv1$ で、$0\le d< L$ である。$d=0$ なら $0\equiv1\pmod L$ となり $L\ge2$ に反するので（$p,q$ の一方は $3$ 以上で $L\ge2$）、$1\le d< L$ である。
段 2（ただ 1 つ）。同じ記事の命題「逆元はあれば 1 つ」により、$ed\equiv1$ と $ed'\equiv1$ なら $d\equiv d'\pmod L$ である。$1\le d,d'< L$ なら $d=d'$ である。
段 3（$\gcd(e,L)\ne1$ の場合）。同じ定理の「必要」の向きにより、$e$ は法 $L$ で逆元をもたない。$\square$

$d$ を実際に求めるには、互除法を逆にたどる（整数の割り算と互除法）。

互除法で $d$ を求める

$e=3$、$L=40$。$40$ を $3$ で割ると $40=3\cdot13+1$ なので、$1=40-3\cdot13$ である。両辺を法 $40$ で見ると $3\cdot(-13)\equiv1$ で、$-13+40=27$ より $d=27$ である。
$e=7$、$L=120$。$120=7\cdot17+1$ なので $1=120-7\cdot17$、$7\cdot(-17)\equiv1\pmod{120}$ で、$d=-17+120=103$ である。

主定理：暗号文は必ず元に戻る

定理と証明

RSA 暗号の復号の正しさ

相異なる素数 $p$、$q$ について $n=pq$、$L=(p-1)(q-1)$ とし、正の整数 $e$、$d$ が $ed\equiv1\pmod L$ を満たすとする。このとき、すべての整数 $m$ について
$$ (m^e)^d\equiv m\pmod n $$
である。特に、$0\le m< n$ の平文 $m$ を暗号化した $c$ を復号すると $m$ に戻る。

方針：法 $n$ で直接考える代わりに、法 $p$ と法 $q$ で別々に $m^{ed}\equiv m$ を示す。法 $p$ では、$m$ が $p$ で割り切れるかどうかで分け、割り切れないときは Fermat の小定理を使う。最後に、$p$ と $q$ がともに $m^{ed}-m$ を割ることから $n=pq$ も割ることを導く。
段 1（指数を書き直す）。$ed\equiv1\pmod L$ で $ed\ge1$ なので、$ed-1$ は $0$ 以上の $L$ の倍数である。$ed=1+kL=1+k(p-1)(q-1)$（$k$ は $0$ 以上の整数）と書く。
段 2（法 $p$、$p$ が $m$ を割らない場合）。Fermat の小定理により $m^{p-1}\equiv1\pmod p$ である。段 1 から
$$ m^{ed}=m^{1+k(p-1)(q-1)}=m\cdot\bigl(m^{p-1}\bigr)^{k(q-1)}\equiv m\cdot1^{k(q-1)}=m\pmod p $$
である。
段 3（法 $p$、$p$ が $m$ を割る場合）。$m\equiv0\pmod p$ なので、$m^{ed}\equiv0\equiv m\pmod p$ である（$ed\ge1$）。
段 4（法 $q$）。段 2・段 3 の $p$ と $q$ を入れかえると、同じ計算で $m^{ed}\equiv m\pmod q$ が得られる（段 2 では $m^{ed}=m\cdot(m^{q-1})^{k(p-1)}$ と書く）。
段 5（法 $n$ にまとめる）。段 2〜4 により、$p$ も $q$ も $m^{ed}-m$ を割る。$m^{ed}-m=ps$（$s$ は整数）と書くと、$q$ は $ps$ を割り、$p$ と $q$ は相異なる素数なので互いに素である。整数の割り算と互除法の系「互いに素な数による割り算」により $q$ は $s$ を割り、$s=qt$ と書けて $m^{ed}-m=pqt=nt$ となる。よって $(m^e)^d=m^{ed}\equiv m\pmod n$ である。
段 6（復号）。$c\equiv m^e\pmod n$ なので $c^d\equiv(m^e)^d\equiv m\pmod n$ である。$0\le m< n$ なので、$c^d$ を $n$ で割った余りは $m$ そのものである。$\square$

素因数ごとに Fermat の小定理を使うこの証明は、Ste17 の Proposition 3.3.1 と同じ考え方である。証明の段 2〜4 は、法 $n$ の計算を法 $p$ と法 $q$ の計算に分けて行っている。これは中国剰余定理（高校数学）の命題「余りの組への対応は和と積を保つ」の使い方と同じで、次の図式で表せる。縦の矢印は、法 $n$ の余りを「法 $p$ の余りと法 $q$ の余りの組」に移す対応である。
$$ \xymatrix{ m \ar[r]^{e\text{ 乗}} \ar[d] & c \ar[r]^{d\text{ 乗}} \ar[d] & m \ar[d] \\ (m\bmod p,\ m\bmod q) \ar[r]_{e\text{ 乗}} & (c\bmod p,\ c\bmod q) \ar[r]_{d\text{ 乗}} & (m\bmod p,\ m\bmod q) } $$
図式が可換であるとは、上の行で $e$ 乗・$d$ 乗してから組に移しても、先に組に移してから成分ごとに $e$ 乗・$d$ 乗しても、同じ組になることである。等式で書くと、$c\equiv m^e\pmod n$ なら $c\equiv m^e\pmod p$ かつ $c\equiv m^e\pmod q$ であり、$c^d\equiv m\pmod p$、$c^d\equiv m\pmod q$ が段 2〜4 の内容である。下の行で組が元に戻ることから、上の行でも元に戻ることを言うのが段 5 である。

$m=7$ を法 $5$ と法 $11$ で追う

ex-rsahs-start-55 の $m=7$、$c=13$ を、法 $5$ と法 $11$ の組で見る。
(1) 法 $5$。$m\equiv2$ で、$2^3=8\equiv3$、$c=13\equiv3$ と一致する。復号は $3^{27}$ で、Fermat の小定理 $3^4\equiv1\pmod5$ から $3^{27}=3^{24}\cdot3^3\equiv27\equiv2\pmod5$ である。$m\equiv2$ に戻った。
(2) 法 $11$。$m\equiv7$ で、$7^3=343=31\cdot11+2\equiv2$、$c=13\equiv2$ と一致する。復号は $2^{27}$ で、$2^{10}\equiv1\pmod{11}$ から $2^{27}=2^{20}\cdot2^7\equiv128=11\cdot11+7\equiv7\pmod{11}$ である。$m\equiv7$ に戻った。
法 $5$ で $2$、法 $11$ で $7$ となる $0$ 以上 $55$ 未満の数は $7$ だけなので、法 $55$ でも $7$ に戻っている。

0 から 54 を、5 で割った余りを行、11 で割った余りを列として並べた 5 行 11 列の表。m = 7 のます（行 2、列 7）から 3 乗した c = 13 のます（行 3、列 2）への赤い矢印と、27 乗で戻る青い矢印
図 1 は、$0$ から $54$ までの数を、法 $5$ の余り（行）と法 $11$ の余り（列）の組の位置に置いた表である。どの組にもちょうど 1 つの数が入る（中国剰余定理）。$3$ 乗は行と列を別々に動かし、$m=7$ の位置 $(2,7)$ を $c=13$ の位置 $(3,2)$ に移す。$27$ 乗はそれを $(2,7)$ に戻す。

$p$ や $q$ で割り切れる平文

thm-rsahs-main の証明の段 3 は、$m$ が $p$ で割り切れる場合である。$n=55$、$e=3$ で確かめる。
(1) $m=10$ は $5$ で割り切れる。$10^3=1000=18\cdot55+10$ で、暗号文は $c=10$ である。$10^{27}$ も法 $55$ で $10$ と合同で（$10^3\equiv10$ を繰り返し使うと $10^{27}=(10^3)^9\equiv10^9=(10^3)^3\equiv10^3\equiv10$）、元に戻る。
(2) $m=22$ は $11$ で割り切れる。$22^3=10648=193\cdot55+33$ で $c=33$ である。法 $11$ では $m\equiv c\equiv0$、法 $5$ では $m\equiv2$、$c\equiv3$ で、ex-rsahs-crt-7 (1) と同じ計算で $3^{27}\equiv2\pmod5$ に戻る。法 $5$ で $2$、法 $11$ で $0$ の数は $22$ なので、$33^{27}\equiv22\pmod{55}$ である。

暗号化は並べ替え

thm-rsahs-main の条件のもとで、$0$ 以上 $n$ 未満の整数 $m$ に、$m^e$ を $n$ で割った余りを対応させると、$0,1,\dots,n-1$ の並べ替えになる。つまり、異なる平文は異なる暗号文になる。

方針：復号で元に戻ることから、2 つの平文が同じ暗号文になることはないと示す。
$0\le m,m'< n$ で、$m^e$ と $m'^e$ を $n$ で割った余りが同じ $c$ だったとする。thm-rsahs-main により、$c^d$ を $n$ で割った余りは $m$ でもあり $m'$ でもあるので、$m=m'$ である。よって対応は $n$ 個の数を $n$ 個の相異なる数に移し、$0,1,\dots,n-1$ の並べ替えになる。$\square$

$n=55$、$e=3$ の暗号化の表

$m$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$
$m^3\bmod55$	$0$	$1$	$8$	$27$	$9$	$15$	$51$	$13$	$17$	$14$	$10$	$11$	$23$	$52$	$49$
$27$ 乗して戻した値	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$	$13$	$14$

$m=0,1,10,11$ のように、暗号化しても変わらない平文もある。$0$ から $54$ までの $55$ 個のうち、$m^3\equiv m\pmod{55}$ となるのは $0,1,10,11,21,34,44,45,54$ の $9$ 個である（計算機で全部調べた結果）。

横軸を平文 m、縦軸を暗号文 m³ mod 55 として 55 個の点を描いた図。どの縦の列にも横の行にも点がちょうど 1 つずつあり、暗号化が並べ替えであることを示す。赤い丸は暗号化しても変わらない 9 点
図 2 は、$0\le m<55$ のすべての $m$ について、点 $(m,\ m^3\bmod55)$ を描いたものである。縦の列にも横の行にも点がちょうど 1 つずつあり、cor-rsahs-perm のとおり暗号化は並べ替えになっている。点は不規則に散らばっていて、暗号文が大きいからといって平文が大きいとは限らない（暗号文の大小と平文の大小は対応していない）。

累乗の余りを速く求める

繰り返し 2 乗法

ex-rsahs-start-55 では $13^{27}$ を $27=16+8+2+1$ と分け、$13^2,13^4,13^8,13^{16}$ を順に 2 乗して求めた。一般に、指数 $d$ を 2 進法で書き（n進法と記数法）、$c,c^2,c^4,\dots$ を法 $n$ で 2 乗しながら求めて、2 進法の桁が $1$ の所の値を掛ければよい。$d$ が $2^k$ 未満なら、2 乗は $k-1$ 回、掛け算は多くて $k-1$ 回で済み、$d-1$ 回掛けるよりずっと速い。$d=27<2^5$ では、2 乗 $4$ 回と掛け算 $3$ 回である。

秘密鍵が守られる理由

公開鍵 $(n,e)$ は誰でも見られる。秘密鍵 $d$ は $ed\equiv1\pmod L$ から決まるので、$L=(p-1)(q-1)$ さえ分かれば、ex-rsahs-euclid と同じ計算で誰でも $d$ を求められる。そこで、$n$ から $L$ を求めることがどれくらい難しいかが問題になる。次の命題は、$L$ を知ることと $n$ を素因数分解することが同じくらい難しいことを示している。

$L$ が分かれば $n$ が分解できる

$p$、$q$ を相異なる素数、$n=pq$、$L=(p-1)(q-1)$ とする。$p$ と $q$ は、2 次方程式
$$ t^2-(n-L+1)\,t+n=0 $$
の 2 つの解である。

方針：$L$ を展開して $p+q$ を $n$ と $L$ で表し、解と係数の関係を使う。
段 1（$p+q$ を求める）。$L=(p-1)(q-1)=pq-p-q+1=n-(p+q)+1$ なので、$p+q=n-L+1$ である。
段 2（2 次方程式を作る）。$(t-p)(t-q)=t^2-(p+q)t+pq=t^2-(n-L+1)t+n$ なので、この 2 次方程式の解は $t=p$、$t=q$ である。$\square$

$n=55$、$L=40$ から $p,q$ を求める

$n-L+1=55-40+1=16$ なので、2 次方程式は $t^2-16t+55=0$ である。$(t-5)(t-11)=0$ より $t=5,11$ で、$55=5\cdot11$ と分解できた。

逆に、$p$ と $q$ が分かれば $L=(p-1)(q-1)$ はすぐに計算できる。つまり、$n$ の素因数分解を知ることと $L$ を知ることは、同じ情報である。実際に使われる RSA 暗号では $p$、$q$ を非常に大きな素数にして、$n$ の素因数分解を現実的な時間で求められないようにする。ただし、「大きな $n$ の素因数分解は難しい」ことや「$L$ を経ずに $d$ や平文を求める速い方法はない」ことは、証明された定理ではない（RSA暗号の注意「安全性は証明された定理ではない」）。この記事では安全性は証明しない。

例と反例

外す条件	反例	成り立たなくなること
$p\ne q$	$n=9=3^2$、$e=d=5$、$m=3$	$m^{ed}\equiv m\pmod n$（$3^{25}\equiv0$）
$\gcd(e,L)=1$	$n=55$、$e=2$	$d$ があること、暗号化が並べ替えであること
$0\le m< n$	$n=55$、$m=62$	復号で元の $m$ に戻ること（$7$ になる）
平文が小さすぎない（安全性）	$n=55$、$e=3$、$m=2$	暗号文から平文が分からないこと

反例：$p=q$ の場合

$p=q=3$、$n=9$ とする。$1$ から $9$ までで $9$ と互いに素な数は $1,2,4,5,7,8$ の $6$ 個なので、$L$ の代わりに $\varphi(9)=6$ を使い、$e=d=5$（$25=4\cdot6+1$）とする。$m=2$ は $2^6=64\equiv1\pmod9$ なので $2^{25}=(2^6)^4\cdot2\equiv2$ と戻る。ところが $m=3$ では $3^{25}$ は $9$ で割り切れ（$3^2$ を因数にもつ）、$3^{25}\equiv0\not\equiv3\pmod9$ である。$m=6$ でも $6^{25}\equiv0$ である。
thm-rsahs-main の証明の段 5 では、$p$ と $q$ が互いに素であることから「$p$ と $q$ がともに割るなら $pq$ も割る」を導いた。$p=q=3$ では「$3$ が割る」から「$9$ が割る」は出ない。$m=3$ では $3^{25}-3=3(3^{24}-1)$ で、$3^{24}-1$ は $3$ で割り切れないので、$9$ で割り切れない。

反例：$e$ と $L$ が互いに素でない場合

$n=55$、$L=40$ で $e=2$ とすると、$\gcd(2,40)=2\ne1$ で、prop-rsahs-d により $2d\equiv1\pmod{40}$ となる $d$ はない（$2d$ は偶数で、$40$ の倍数に $1$ を足した数は奇数である）。実際、$1^2=1$ と $54^2=2916=53\cdot55+1$ はどちらも法 $55$ で $1$ になり、暗号文 $1$ から平文が $1$ か $54$ かを決められない。$0$ から $54$ を $2$ 乗した余りは $18$ 種類しかなく、cor-rsahs-perm の並べ替えにならない。

反例：平文が $n$ 以上の場合と、小さすぎる場合

$n=55$、$e=3$ で $m=62$ とする。$62\equiv7\pmod{55}$ なので暗号文は $7$ と同じ $13$ で、復号すると $7$ になり、$62$ には戻らない。thm-rsahs-main が保証するのは「法 $n$ で合同な数に戻る」ことで、平文を $0\le m< n$ に限ったので「$m$ そのものに戻る」と言えた。
$m=2$ では $2^3=8<55$ なので、暗号文は $c=8$ で、法 $55$ の余りをとる効果がない。暗号文 $8$ を見た人は、$8$ の 3 乗根として $m=2$ を求められる。これは thm-rsahs-main の反例ではない（復号は正しく $2$ に戻る）が、暗号として役に立たない例である。実際の運用では、平文に手を加えてから暗号化する工夫がある（RSA暗号の注意「実際の運用での注意」）。

大学数学で見る：$\operatorname{lcm}(p-1,q-1)$ と電子署名

thm-rsahs-main の証明で $L=(p-1)(q-1)$ を使ったのは、段 2 で $ed-1$ が $p-1$ の倍数であること、段 4 で $q-1$ の倍数であることが必要だったからである。そのためには、$ed-1$ が $p-1$ と $q-1$ の最小公倍数 $\lambda=\operatorname{lcm}(p-1,q-1)$ の倍数であれば足りる。つまり $ed\equiv1\pmod\lambda$ となる $d$ でも、証明はそのまま通る（Ste17 の Proposition 3.3.1 は、この形で述べられている）。$n=55$ では $\lambda=\operatorname{lcm}(4,10)=20$ で、$e=3$ に対して $d=7$（$21=20+1$）でも、$0\le m<55$ のすべての $m$ が戻る（計算機で確かめた）。累乗の余りが $1$ に戻る周期の考え方は冪の余りの周期と元の位数で扱っている。

電子署名と、法 $n$ の乗法群の見方を開く

(1) 電子署名。暗号化と復号の順を入れかえても、$(m^d)^e=m^{ed}\equiv m\pmod n$ が thm-rsahs-main と同じ理由で成り立つ。秘密鍵をもつ人が $s=m^d\bmod n$ を作って $m$ と一緒に送ると、受け取った人は公開鍵で $s^e\equiv m$ を確かめられる。$d$ を知らない人には $s$ を作りにくいので、$s$ は「秘密鍵をもつ人が $m$ を送った」ことの証拠になる（RSA暗号の注意「電子署名」）。$n=55$、$d=27$、$m=8$ では $s=8^{27}\bmod55=2$ で、$2^3=8$ と確かめられる。

(2) 群の言葉。$n$ と互いに素な法 $n$ の余りは、掛け算について群 $(\mathbb{Z}/n\mathbb{Z})^\times$ をなし、元の個数は $\varphi(n)=L$ である。Lagrange の定理から、この群の元 $m$ は $m^{L}\equiv1$ を満たし（Euler の定理）、$m^{ed}=m\cdot(m^L)^k\equiv m$ となる。ただしこの見方では $n$ と互いに素な $m$ しか扱えず、ex-rsahs-divisible のような $m$ には、この記事の証明のように $p$ と $q$ に分ける考え方が要る。

演習

$n=33$ の鍵で暗号にして戻す

$p=3$、$q=11$、$e=7$ とする。秘密鍵 $d$（$1\le d< L$）を求め、平文 $m=4$ を暗号化してから復号せよ。

解答を開く

$n=33$、$L=2\cdot10=20$ である。$7\cdot3=21=20+1$ なので $d=3$ である。暗号化：$4^2=16$、$4^4=256=7\cdot33+25\equiv25$、$4^7=4^4\cdot4^2\cdot4\equiv25\cdot16\cdot4=1600=48\cdot33+16\equiv16$ で、$c=16$ である。復号：$16^3=4096=124\cdot33+4$ で、$4$ に戻る。

互除法で秘密鍵を求める

$p=7$、$q=11$、$e=7$ とする。互除法を使って秘密鍵 $d$（$1\le d< L$）を求めよ。

解答を開く

$L=6\cdot10=60$ で、$\gcd(7,60)=1$ である。互除法：$60=7\cdot8+4$、$7=4\cdot1+3$、$4=3\cdot1+1$。逆にたどると $1=4-3=4-(7-4)=2\cdot4-7=2\cdot(60-7\cdot8)-7=2\cdot60-17\cdot7$ なので、$7\cdot(-17)\equiv1\pmod{60}$ で、$d=-17+60=43$ である。確かめ：$7\cdot43=301=5\cdot60+1$。

$L$ から $n$ を分解する

$n=91$ が相異なる 2 つの素数の積で、$L=(p-1)(q-1)=72$ であることが分かっている。$p$、$q$ を求めよ。

解答を開く

prop-rsahs-factor により、$p$、$q$ は $t^2-(91-72+1)t+91=t^2-20t+91=0$ の解である。$(t-7)(t-13)=0$ より $p,q$ は $7$ と $13$ で、$91=7\cdot13$、$L=6\cdot12=72$ と合う。

さらに先へ

RSA 暗号の名前は、仕組みを考えた 3 人（Rivest、Shamir、Adleman）の頭文字である（Sho08 §4.7）。暗号にする鍵を公開し、元に戻す鍵だけを秘密にする方式を 公開鍵暗号 という。
素数 $p$、$q$ を作るには、大きな数が素数かどうかを速く判定する必要がある。Fermat の小定理を使った判定の考え方は Fermatの小定理と冪の余りの「さらに先へ」にある。Wilsonの定理（高校数学）は素数の必要十分条件を与えるが、計算が大きすぎて実用的でない。
ex-rsahs-crt-7 のように法 $p$ と法 $q$ に分けて計算すると、法 $n$ で直接計算するより速く復号できる（中国剰余定理（高校数学））。
大学向けの RSA暗号では、暗号化が並べ替えになる条件、繰り返し 2 乗法、$\varphi(n)$ を知ることと素因数分解の関係を、より一般の形で扱う。