ゼロから学ぶRSA暗号 — 公開鍵を支える数論

RSAは「掛けられるが外せない鍵」を公開できるようにする。この記事は合同算術から積み上げる——鍵生成、2回のべき乗剰余、そしてオイラーの定理から「なぜ元のメッセージが戻るのか」を1行ずつ証明する。そのうえで手計算で追える実例、安全性が素因数分解の難しさに乗っている理由、そして教科書RSAをパディング無しで出荷してはならない理由まで。

"Rivest

問題: 共有していない秘密で合意する

歴史のほとんどの期間、暗号とは双方が同じ秘密を知っていることを意味していました。あなたと私が事前に鍵を取り決め、私がそれでメッセージを撹拌し、あなたが同じ鍵で戻す。これが共通鍵暗号で、高速でよく理解されています——ただし解けそうにない「最初の一歩」問題を抱えています。安全に話すためには、まず安全に会って鍵を交換しなければならない。一度も連絡したことのない店で買い物をしたいインターネットには、その事前の面会がありません。

公開鍵暗号は、初めて聞くと不可能に響くアイデアでこの循環を断ち切ります——掛けられるが外せない鍵。誰もが、世界に公開する公開鍵と、決して明かさない秘密鍵を持ちます。誰でもあなたの公開鍵であなた宛のメッセージを暗号化でき、復号できるのはあなたの秘密鍵だけ。事前の面会も、共有された秘密も不要です。

Rivest・Shamir・Adlemanが1978年にこれの最初の実用的な構成を発表し、いまもその名前が RSA として残っています。使われるのはふつうの整数の算術だけ——特殊な数学は出てきません。この記事はそれを土台から組み立てます。必要な算術、鍵生成、2つの操作、それらが互いを打ち消す証明、小さな実例、そして教科書版が実トラフィックに触れる前にパディングを要する理由。（他の道具との位置関係はゼロから学ぶ暗号技術にあります。）

前提: 時計の上の算術

RSAで起きることはすべて、ある整数 $n$ を法とする（modulo）世界の話です。意味は「ふつうに計算し、$n$ で割って、余りだけを残す」。おなじみの例は $n = 12$ の時計算術です。10時の4時間後は2時——$14$ を $12$ で割った余りが $2$ だからです。

「$a$ と $b$ は $n$ で割った余りが等しい」を表す記法は

$$a \equiv b \pmod{n}$$

で、「$a$ は $n$ を法として $b$ と合同」と読みます。要するに、$n$ で割った余りだけを見る目で眺めると $a$ と $b$ は区別がつかない、ということです。だから $14 \equiv 2 \pmod{12}$。必要なのは合同式についての3つの事実だけで、3つとも納得しやすいものです。

1. 足し算と掛け算は生き残る。 $a \equiv a'$ かつ $b \equiv b'$ なら $a + b \equiv a' + b'$ および $ab \equiv a'b'$。計算のどの時点で $n$ で割って余りにしても答えは変わりません——これが巨大な数の扱いを可能にしている当のものです。
2. したがってべき乗は安い。 $a^{2k} = (a^k)^2$ なので、2乗を繰り返し、そのたびに $n$ で余りを取ればよい。$a^{2048} \bmod n$ は2048回の掛け算ではなく約11回の2乗で済みます。これが2乗によるべき乗剰余で、2048bitの数でRSAが使える理由です。
3. 割り算だけが特別。 一般の「$b$ で割る」はありません。ときどき存在するのがモジュラ逆元——$b \cdot b^{-1} \equiv 1 \pmod{n}$ となる数 $b^{-1}$ です。これは $b$ と $n$ が1以外の共通因数を持たないときちょうど存在し、拡張ユークリッドの互除法が高速に見つけてくれます。

もう1つ道具を。オイラーのトーシェント関数 $\varphi(n)$ は、$1, 2, \dots, n$ のうち $n$ と共通因数を持たないものの個数を数えます。素数 $p$ なら $1, \dots, p-1$ のすべてが該当するので $\varphi(p) = p - 1$。異なる2つの素数の積——RSAが必要とする唯一の場合——では

$$\varphi(pq) = (p-1)(q-1)$$

$1, \dots, pq$ から除かれるものを数えれば見えます。$p$ の倍数が $q$ 個、$q$ の倍数が $p$ 個、そして $pq$ 自身を二重に数えているので、$pq - q - p + 1 = (p-1)(q-1)$ です。要するに、$p$ の倍数と $q$ の倍数を取り除くと、残りはちょうど $(p-1)(q-1)$ 個になる、という式です。

RSAが乗っている非対称性

公開鍵方式には、やるのは簡単で、戻すのが難しい操作が必要です。RSAのそれは素数の掛け算です。

1024bitの素数2つを掛け合わせるのは、計算機には測定できないほどの時間です。逆向き——2048bitの積だけから2つの素数を復元する——は素因数分解であり、効率的なアルゴリズムは知られていません。公表されている最良の古典的手法である一般数体篩法は、このサイズでは準指数的、しかし依然として絶望的な時間がかかります。公開の場で分解された最大のRSA法数である829bitの RSA-250 は、2020年に約2700コア年を要しました。2048bitはそのはるか先です。

つまり——積は公開、因数は秘密。RSAの残りは、この差を暗号方式に変換する機構です。

鍵生成

5つの手順で、どれも必要な道具はもう揃っています。

1. 大きな異なる素数 $p$, $q$ を2つ選ぶ。 実務では適切な大きさのランダムな奇数を生成し、素数判定（Miller–Rabin）に2つ通るまで試します。2048bit鍵ならそれぞれ約1024bitです。

2. 法 $n = pq$ を計算する。 この数は公開されます。「2048bitのRSA鍵」というときの大きさはこれです。

3. $\varphi(n) = (p-1)(q-1)$ を計算する。 この数は秘密にしなければなりません——そして $n$ を分解できる者は誰でもこれを計算できる、というのが安全性の核心そのものです。

4. 公開指数 $e$ を選ぶ。 $1 < e < \varphi(n)$ かつ $\gcd(e, \varphi(n)) = 1$。この互いに素という条件は美学ではなく、手順5に解が存在するための条件そのものです。実在の鍵はほぼすべて $e = 65537 = 2^{16} + 1$ を使います。これは素数で、2進表記 10000000000000001 に1が2つしかないので、暗号化は17回の2乗と1回の掛け算で済みます。

5. 秘密指数 $d$ を、$e$ のモジュラ逆元として計算する。

$$d \equiv e^{-1} \pmod{\varphi(n)}, \quad\text{すなわち}\quad ed \equiv 1 \pmod{\varphi(n)}$$

「すなわち」を開くと、$d$ は「$e$ に掛けると $\varphi(n)$ の倍数のちょうど1つ先に着地する数」です。合同式を使わずに書くと、ある整数 $k$ について $ed = 1 + k\varphi(n)$——そしてこの形こそ、あとの証明で必要になるものです。拡張ユークリッドの互除法が $e$ と $\varphi(n)$ からマイクロ秒で $d$ を出します。要するに $d$ は「$e$ 乗した効果をちょうど打ち消す指数」です。

結果として2つの鍵が得られます。

• 公開鍵 $(n, e)$ — どこに公開してもよい。
• 秘密鍵 $(n, d)$ — 決して送信しない。そして $p$, $q$, $\varphi(n)$ は破棄するか守る。どれ1つでも $d$ を渡してしまいます。

暗号化と復号

メッセージを $0 \le m < n$ の整数 $m$ として表します。（バイト列から整数へどう持っていくかがパディングの居場所で、それは後の節です。）すると両方向がただ1回のべき乗剰余です。

$$\textbf{暗号化:}\quad c \equiv m^{e} \pmod{n}$$

$$\textbf{復号:}\quad m \equiv c^{d} \pmod{n}$$

これがアルゴリズムの全部です。要するに、暗号化も復号も「べき乗して $n$ で割った余りを取る」という同じ操作で、違うのは使う指数だけです。公開指数でべき乗すれば鍵がかかり、秘密指数でべき乗すれば開き、全体を通して $n$ で余りを取る。2つの操作の非対称性は、$d$ を知っているか知らないかという非対称性そのものにすぎません。

当然の疑問は、なぜ2つめが1つめを打ち消すのかです。

なぜメッセージが戻ってくるのか

エンジンはオイラーの定理です。ここで述べて、一度だけ使います。

オイラーの定理。 $\gcd(a, n) = 1$ ならば $a^{\varphi(n)} \equiv 1 \pmod{n}$。

言葉にすると、$n$ と互いに素な数を $\varphi(n)$ 乗すると、$n$ を法としてちょうど1に着地する。（素数 $p$ について $a^{p-1} \equiv 1 \pmod p$ というフェルマーの小定理は $n = p$ の特別な場合です。）これが与えてくれるのは、指数を周回させる手段です。$a^{\varphi(n)}$ を掛けても $n$ を法として何も変わらないので、指数は実質的に $\varphi(n)$ を法として生きている。だからこそ $d$ は $n$ ではなく $\varphi(n)$ を法として定義されたのです。

では復号を、1行ずつ。暗号文から始めて代入します。

$$c^{d} \equiv (m^{e})^{d} \pmod{n}$$

暗号化の定義により $c \equiv m^e$ だから。

$$(m^{e})^{d} = m^{ed}$$

べきのべきは指数の積になるから——ここまで剰余の話は出てこない。

$$m^{ed} = m^{1 + k\varphi(n)}$$

鍵生成の手順5が、ある整数 $k$ についてちょうど $ed = 1 + k\varphi(n)$ を用意してくれたから。この一歩を使えるようにするために構成全体が設計されている。

$$m^{1 + k\varphi(n)} = m^{1} \cdot \left(m^{\varphi(n)}\right)^{k}$$

$x^{a+b} = x^a x^b$ で分け、$x^{k\varphi(n)} = (x^{\varphi(n)})^k$ とまとめただけ——まだ指数法則の話。

$$m \cdot \left(m^{\varphi(n)}\right)^{k} \equiv m \cdot 1^{k} \pmod{n}$$

オイラーの定理が $m^{\varphi(n)}$ を1に置き換えるから（$\gcd(m, n) = 1$ のとき）。

$$m \cdot 1^{k} = m$$

1は何乗しても1だから。 よって $c^d \equiv m \pmod n$。そして $0 \le m < n$ を要求していたので、戻ってくる余りは「$m$ と合同な何か」ではなく $m$ そのものです。メッセージが返ってきました。この6行が言っているのは要するに、$e$ 乗してから $d$ 乗すると指数が $\varphi(n)$ ずつ $k$ 周して元の位置（1乗）に戻る、ということです。

何が働いたかに注目してください。この方式の全体は、「$ed$ が $\varphi(n)$ の倍数より1だけ大きくなるように $d$ を選ぶ」という作業です。なぜならそれがオイラーの定理が潰してくれる指数だからです。そして $\varphi(n)$ は $p$ と $q$ から計算できる——だから因数を秘密にしなければならないのです。

正直な補足を1つ。上の証明には穴があります。オイラーの定理は $\gcd(m, n) = 1$ を必要としましたが、メッセージが原理的には $p$ または $q$ の倍数になりうる。その場合もRSAは正しく復号します。ただし議論は、$n$ に対してオイラーの定理を直接使うのではなく、中国剰余定理で素因数ごとに分けて扱います。ランダムなメッセージがそういう $m$ に当たる確率はおよそ $1/p + 1/q$——実際の鍵サイズでは天文学的に小さく、そもそもパディングが $m$をランダム化するので実務上は無関係です。厳密な扱いがここに1ページ費やすのを見て驚かないために、穴の存在は知っておく価値があります。

手計算で追える実例

実際の鍵は617桁の数を使います。代わりに極小の素数を取って、どの手順も鉛筆で検証できるようにします。

鍵生成。 $p = 3$, $q = 11$ とします。

• $n = pq = 33$
• $\varphi(n) = (3-1)(11-1) = 2 \times 10 = 20$
• $e = 3$ を選ぶ。$\gcd(3, 20) = 1$ を確認。✓
• $3d \equiv 1 \pmod{20}$ となる $d$ を探す。$d = 7$ を試すと $3 \times 7 = 21 = 1 + 1 \times 20$。✓

よって公開鍵は $(33, 3)$、秘密鍵は $(33, 7)$。$ed = 21 = 1 + k\varphi(n)$（$k = 1$）——証明が必要としたちょうどその形です。

$m = 5$ を暗号化。

$$c \equiv 5^{3} = 125 \pmod{33}$$

$125 = 3 \times 33 + 26$ なので $c = 26$。つまり暗号文は「5を3回掛けて33で割った余り」にすぎません。

復号。 $26^{7} \bmod 33$ を、毎回余りを取りながら2乗の繰り返しで計算します。

• $26^{2} = 676 = 20 \times 33 + 16 \implies 26^2 \equiv 16$
• $26^{4} \equiv 16^{2} = 256 = 7 \times 33 + 25 \implies 26^4 \equiv 25$
• $26^{6} = 26^{4} \cdot 26^{2} \equiv 25 \times 16 = 400 = 12 \times 33 + 4 \implies 26^6 \equiv 4$
• $26^{7} = 26^{6} \cdot 26 \equiv 4 \times 26 = 104 = 3 \times 33 + 5 \implies 26^7 \equiv 5$

5が戻ってきました。ここに出た数はすべて確認できる大きさで、同じ6行を2048bitの整数でやっているのがあなたのブラウザです。

この玩具のような例が見せてくれることが2つあります。1つめ、$m$ は $n$ より小さくなければなりません。$n = 33$ ならメッセージは33通りしかなく、$m = 40$ は $40 - 33 = 7$ として戻ってきます。2つめ、暗号化は決定的です——5はいつも26に写る——そして33通りしかないなら、攻撃者は全部を暗号化して答えを引くだけで済みます。これがサイズの小ささによる作り物ではないことを、次の次の節で説明します。

なぜ破るのが難しいのか

攻撃者は $(n, e)$ と $c$ を見て $m$ を欲しがっています。経路を並べます。

$n$ を素因数分解する。 $p$ と $q$ を手に入れれば $\varphi(n) = (p-1)(q-1)$ を計算し、拡張ユークリッドの互除法で $d$ を得て復号できます。これが第一の攻撃で、RSAの安全性が素因数分解の難しさに乗っている理由です。2048bitでは既知の古典的手法すべての手が届きません。一般数体篩法のコストは桁数について準指数的に増え、829bitの公開記録ですでに数千コア年を要しています。

別の方法で $\varphi(n)$ を求める。 助けになりません。$n = pq$ と $\varphi(n) = (p-1)(q-1) = n - p - q + 1$ の両方を知れば $p + q$ が分かり、和と積から2次方程式の解の公式で $p$ と $q$ が復元できます。$\varphi(n)$ を求めることは素因数分解と等価です。

$c$ の $e$ 乗根を直接取る。 整数の上では $e$ 乗根は簡単です。しかし分解を知らない合成数 $n$ を法として $c^{1/e} \bmod n$ を計算する「RSA問題」には、効率的な解法が知られていません。ただし正確に述べておくべきことが1つ。RSAを破ることが素因数分解と同じ難しさである、という証明はありません。 素因数分解ができればRSAは破れます。RSAへのあらゆる攻撃が素因数分解アルゴリズムを含意するかどうかは未解決問題です。

$m$ を総当たりする。 候補のメッセージを暗号化して突き合わせる——メッセージ空間が小さいときは常に致命的で、パディングが存在する理由です。

実務上の帰結。1024bit鍵は非推奨、2048bitが現在の下限、3072bitがNISTのガイダンスでおおよそ128bit安全性水準に対応します。そしてこの構築物全体に期限があります。Shorのアルゴリズムは十分に大きな量子計算機の上で整数を多項式時間で分解するので、標準化団体は耐量子方式への移行を進めています。上の古典的な分析は、いま記録して後で復号できる敵からデータを守ってはくれません。

教科書RSAは出荷してよいRSAではない

ここまでの内容は暗号学者が教科書RSAと呼ぶもので、書いたまま配備すれば重大な脆弱性になります。数学は正しい。その上に直接建てた方式が壊れているのです。理由は3つ、どれも単独で致命的です。

決定的である。 同じ鍵の下では同じ平文がいつも同じ暗号文になります。だからメッセージ空間を推測できる攻撃者は数論を一切使わずに勝てます——公開鍵（公開されています）で候補を全部暗号化し、突き合わせるだけ。はい／いいえのフィールド、クレジットカード番号、部屋番号、貧弱な乱数生成器から出たAES鍵。すべて表引きで復元されます。形式的には、教科書RSAは IND-CPA 安全性を満たさず、修正には乱数性が必要です。

可鍛性（malleability）がある。 べき乗が掛け算に分配されるので、

$$c_1 c_2 \equiv m_1^{e} m_2^{e} = (m_1 m_2)^{e} \pmod{n}$$

要するに、暗号文どうしを掛けると、中身の平文どうしを掛けたものの暗号文になる。だから暗号文を読めない攻撃者でも、それに $2^e$ を掛けて「復号すると $2m$ になるもの」をあなたに渡せます。「復号できた」を「正当である」と扱うプロトコルはすべて悪用可能です。

小さな指数は小さなメッセージを漏らす。 $m^e < n$ なら——$e = 3$ と短いメッセージなら簡単に起きます——$c = m^e$ が整数の上でそのまま成り立ち、周回が一度も起きません。$c$ のふつうの整数の3乗根を取ればメッセージが読めます。素因数分解は不要です。

治療法はパディングです。メッセージを $n$ のほぼ全幅まで埋め、新鮮な乱数バイトを混ぜ、復号側が検証できる構造を付ける標準化された変換のことです。

• 暗号化には RSAES-OAEP（Optimal Asymmetric Encryption Padding）。乱数化されているので同じ平文が毎回違う暗号文になり、掛け算の構造も壊します。
• 署名には RSASSA-PSS。
• 古い PKCS#1 v1.5 の暗号化パディングは、Bleichenbacherの1998年のパディングオラクル攻撃の住処です。エラー応答で「パディングが不正」と「メッセージが不正」を区別してしまうサーバは、平文を持っていなかった暗号文の復号をさせられてしまいます。この種のバグはTLS実装で何度も再発見されています（ROBOT, 2017）。v1.5は旧互換専用と扱ってください。

RSAが実データそのものを暗号化しない理由はもう1つあります。$m < n$ という制約が2048bit鍵の上限を「256バイトからパディングの分を引いた量」に縛り、さらにべき乗剰余は共通鍵暗号より桁違いに遅い。実システムはハイブリッドです——RSA（使う場合）が短い共通鍵を暗号化し、AESが本体を暗号化する。現代のTLS 1.3ではその役割さえ無くなりました。鍵確立は前方秘匿性のために一時的なDiffie–Hellmanへ移り、RSAが主に生き残っているのは証明書の署名アルゴリズムとしてです。（部品の組み合わせ方はゼロから学ぶTLSを参照。）

署名: 同じ2つの指数を逆順に

$e$ と $d$ は互いに逆元なので、逆の順で適用しても往復します——$(m^d)^e \equiv m$。これがデジタル署名を与えます。$d$ を独占する署名者が

$$s \equiv H(m)^{d} \pmod{n}$$

を作り、誰でも公開鍵を使って

$$s^{e} \stackrel{?}{\equiv} H(m) \pmod{n}$$

を確認して検証します。検証を通る $s$ を作れるのは $d$ の保持者だけなので、署名はメッセージをその鍵に結びつけます。2本の式を並べると要するに、秘密指数で「鍵をかけた」ハッシュを公開指数で開き、手元で計算したハッシュと一致するかを見ている、ということです。

ハッシュ $H$ に注目してください。署名するのはメッセージそのものではなくダイジェストで、理由は2つ。メッセージはほぼ常に $n$ の許容量より長いから。そして生の値に署名すると上の可鍛性を受け継ぐから——攻撃者が2つの署名を掛け合わせて、その積に対する署名を偽造できてしまいます。衝突耐性のあるハッシュとPSSパディングが両方を塞ぎます。現代のウェブで実際に効いているのはこの操作です。ブラウザが検証する証明書チェーンはすべて、この検証の積み重ねです。

落とし穴

自分で実装しないこと。 これは定番の助言で、正しい助言です。以下はすべて、配備されたRSAで実際に起きた破りの類型であり、ライブラリ作者が何十年も費やしてきた領域です。

標準が使うのは $\varphi(n)$ ではなく $\lambda(n)$。 FIPSやPKCS#1は $d$ を $\lambda(n) = \operatorname{lcm}(p-1, q-1)$ を法として定義します。これは $\varphi(n)$ を割り切ります。証明は同じように通り、得られる $d$ は小さいので速い。ライブラリの $d$ と自分が $\varphi(n)$ から導いた $d$ を比べて違っていても、どちらも有効なことがあります——2つの指数は $\lambda(n)$ を法として合同です。

乱数の弱さは致命的で、しかも鍵をまたいで効く。 エントロピー源が悪くて独立に生成した2つの鍵が素数を共有すると、$\gcd(n_1, n_2)$ がそれを暴き、両方の鍵が——ほぼ無コストの計算で——落ちます。2012年の調査（"Mining your Ps and Qs"）は、まさにこの形で壊れた稼働中のTLSホストを数万台発見しました。大半は、エントロピーが存在する前の初回起動時に鍵を生成した組み込み機器でした。

時間はサイドチャネル。 素朴なべき乗剰余は $d$ のビットによって所要時間が変わり、それを使ってネットワーク越しに秘密鍵が抽出されています。実装はブラインディング——べき乗の前に乱数因子を掛け、後で割り戻す——と定数時間のコード経路で防ぎます。

CRT高速化への故障注入攻撃。 復号はふつう中国剰余定理で、$p$ を法とする計算と $q$ を法とする計算に分けて約4倍速くします。片方の半分だけが1回の計算誤りで壊れると、壊れた署名と正しい署名を比べてGCDを取るだけで $p$ が露出します。ライブラリは結果を出す前に検証して防ぎます。

小さな秘密指数は破れる。 復号を速くするために小さな $d$ を選ぶとWienerの攻撃を招きます。$d$ がおおよそ $n^{1/4}$ 以下のとき $d$ を効率的に復元します。小さな公開指数は問題ありません（$e = 65537$ が標準）が、$d$ は大きくなければなりません。

パディングの検査は定数時間で行い、エラーは区別できてはならない。 これがBleichenbacherの教訓です。脆弱性は算術の側には一度も無く、エラーメッセージの側にありました。

現場ではこう使う

RSAの算術を自分で書く場面は、現場にはまずありません。触るのは鍵の生成・形式・パディングの選択で、事故もほぼそこで起きます。

いつ触るか。 バックエンド／インフラのエンジニアがTLS証明書のCSRを作るとき、SSH鍵を発行するとき、JWTの署名アルゴリズムを決めるとき。セキュリティ担当なら、既存システムの鍵長とパディングを棚卸しするとき。

実際に打つコマンドと、そこに出てくる名前。

• 鍵生成: openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out key.pem。公開指数は既定で65537です。
• 中身の確認: openssl pkey -in key.pem -text -noout を打つと modulus（$n$）、publicExponent（$e$）、privateExponent（$d$）、prime1/prime2（$p, q$）に加え、exponent1/exponent2/coefficient が並びます。最後の3つは落とし穴の節で触れたCRT高速化用の前計算値です。秘密鍵ファイルは $d$ だけでなく $p$ と $q$ を丸ごと抱えている——だから漏えいしたら一巻の終わりです。
• JWT: alg の RS256 は PKCS#1 v1.5 署名、PS256 は PSS 署名です。どちらも公開鍵で検証する方式で、共有秘密の HS256 とは別物です。
• アプリのコード: Pythonの cryptography なら padding.OAEP(mgf=padding.MGF1(hashes.SHA256()), algorithm=hashes.SHA256(), label=None) のようにパディングを明示して呼びます。

知らないと事故になる落とし穴。

• Javaの Cipher.getInstance("RSA") はパディング指定を省くと PKCS#1 v1.5 になります（標準プロバイダの既定）。新規コードでは "RSA/ECB/OAEPWithSHA-256AndMGF1Padding" のように明示します。「ECB」と書いてありますが、RSAではブロックモードの意味は持ちません。
• JWTのアルゴリズム取り違え。 検証側がトークン自身の alg を信じると、RS256 の公開鍵を HS256 のHMAC鍵として使わせる偽造が成立します。検証時は許可するアルゴリズムを固定します。
• SSHの ssh-rsa は鍵の種類とは別に、SHA-1署名の名前でもあります。 OpenSSH 8.8 以降はこのSHA-1署名が既定で無効なので、RSA鍵でも rsa-sha2-256/rsa-sha2-512 に対応していない古い相手とは繋がらなくなります。「鍵が壊れた」のではありません。
• RSAでデータ本体を暗号化しようとして長さ制限にぶつかる。 2048bit鍵ではパディング込みで256バイトが上限です。ファイルを分割してRSAで暗号化する設計は誤りで、前節のとおり共通鍵をRSAで包むハイブリッドにします。

面接・設計レビューで問われる問いと答えの筋道。

• 「TLS 1.3でRSAは何をしているか」→ 鍵交換はもう担っていない。証明書の署名と、ハンドシェイク中にサーバが秘密鍵を持っていることを示す署名（CertificateVerify）に使われる。
• 「なぜRSAで直接データを暗号化しないのか」→ $m < n$ の長さ制限と速度。だから共通鍵を包むだけにする。
• 「教科書RSAの何がまずいか」→ 決定的・可鍛性・小さな指数の3点と、その答えがOAEP/PSSであること。
• 「新規に鍵を選ぶなら」→ RSAを使うなら2048bit以上、パディングはOAEP/PSS。そもそも署名だけならECDSAやEd25519も候補に挙げ、耐量子方式への移行を視野に入れる、まで言えると十分です。

まとめ

• 共通鍵暗号は敵対的なネットワーク越しには確立できない共有秘密を必要とする。公開鍵暗号は「掛けられるが外せない鍵」でその最初の一歩を解決する
• RSAが乗る非対称性は1つだけ——大きな素数2つの掛け算は自明、積の素因数分解は自明でない
• 鍵生成: $n = pq$、$\varphi(n) = (p-1)(q-1)$、$\varphi(n)$ と互いに素な $e$ を選び、$d \equiv e^{-1} \pmod{\varphi(n)}$。公開 $(n,e)$、秘密 $(n,d)$
• 暗号化は $c \equiv m^e \bmod n$、復号は $m \equiv c^d \bmod n$——それぞれべき乗剰余1回
• 往復するのは $ed = 1 + k\varphi(n)$ だから。$m^{ed} = m \cdot (m^{\varphi(n)})^k \equiv m$ がオイラーの定理から従う
• 安全性は $n$ の素因数分解が非現実的であること。$\varphi(n)$ の復元は素因数分解と等価で、2048bitが今日の下限——ただしShorのアルゴリズムは大規模な量子計算機の上でこれを終わらせる
• 教科書RSAは絶対に出荷してはならない。決定的で、可鍛性があり、小さな指数で破れる。暗号化にはOAEP、署名にはPSSを使う
• 実務でRSAが暗号化するのはデータではなく共通鍵で、TLS 1.3で生き残っている役割は証明書への署名

周辺の全体像はゼロから学ぶ暗号技術から。RSA署名が実際のハンドシェイクの中で働くところはゼロから学ぶTLSへ。

確認問題

1. 鍵生成は $\gcd(e, \varphi(n)) = 1$ を要求します。これを満たさない $e$ を選ぶと、具体的に何が壊れますか。
2. $d$ はなぜ $n$ ではなく $\varphi(n)$ を法として計算されるのでしょうか。
3. 実例の公開鍵 $(33, 3)$ を使って $m = 2$ を暗号化してください。その後 $d = 7$ で復号し、2が戻ることを確認してください。
4. 攻撃者がある2048bit RSA鍵について $\varphi(n)$ を知りましたが、$p$ も $q$ も知りません。この鍵は危険な状態でしょうか。理由を述べてください。
5. あるサービスが1桁のPINを2048bit公開鍵で教科書RSAのまま暗号化し、暗号文を保存しています。鍵は強く、素因数分解は非現実的です。それでも攻撃者がPINを読める方法と、それを防ぐ対策を説明してください。