RSAの基本 ― 公開鍵、秘密鍵、素因数分解の関係を理解する

RSAは公開鍵暗号の代表例

RSAでは、公開鍵と秘密鍵という2つの鍵を使います。公開鍵は相手に渡してよい鍵で、秘密鍵は本人だけが守る鍵です。

公開鍵で暗号化したデータは、対応する秘密鍵で復号できます。反対に、秘密鍵で署名したデータは、対応する公開鍵で検証できます。このためRSAは、暗号化だけでなく、証明書やJWTのRS256のような署名にも登場します。

flowchart LR
  A[平文 HELLO] -- 公開鍵で暗号化 --> B[暗号文]
  B -- 秘密鍵で復号 --> C[平文 HELLO]
  D[データ] -- 秘密鍵で署名 --> E[署名つきデータ]
  E -- 公開鍵で検証 --> F[署名が正しいか確認]

鍵は大きな数字の組

RSAの公開鍵と秘密鍵は、概念的には次のような数字の組です。

公開鍵 = (n, e)
秘密鍵 = (n, d)

暗号化では、平文を数字 M として次の計算をします。

C = M^e mod n

復号では、暗号文 C に対して次の計算をします。

M = C^d mod n

e は公開鍵側の指数、d は秘密鍵側の指数です。公開鍵の e で変換したものを、秘密鍵の d で元に戻せるように、2つの値が数学的に対応しています。

文章は数字にしてから計算する

RSAは文章をそのまま計算しているわけではありません。コンピュータ上の文字列はバイト列なので、そのバイト列を1つの大きな整数として扱います。

たとえば HELLO はUTF-8では次のバイト列です。

H    E    L    L    O
48   45   4C   4C   4F

これを1つの16進数として読むと 0x48454C4C4F です。10進数では 310400273487 になります。

HELLO
  ↓ UTF-8のバイト列
48 45 4C 4C 4F
  ↓ 1つの整数として解釈
310400273487
  ↓ RSAの計算
暗号化された整数

RSAから見ると、「HELLO」という文章ではなく、整数 M に対して M^e mod n を計算しているだけです。復号後は、戻ってきた整数をバイト列へ戻し、最後に文字列へ戻します。

modは割った余り

mod は、割った余りを求める計算です。

17 mod 5 = 2

17を5で割ると、商は3で余りは2です。RSAでも同じように、M^e を n で割った余りを求めます。

実際には M^e が非常に巨大になるため、コンピュータは最後まで巨大な数を展開してから割るのではなく、累乗剰余計算という効率的な方法で M^e mod n を直接計算します。

秘密鍵を守る中心は素因数分解

RSAの n は、2つの巨大な素数 p と q を掛けて作ります。

n = p × q

小さい例なら、p = 5、q = 11 のとき n = 55 です。掛け算は簡単です。

しかし、55 だけを見せられて「元の2つの素数は何か」と聞かれると、割り切れる素数を探す必要があります。55ならすぐに 5 × 11 だと分かりますが、RSA-2048では n はおおよそ617桁になります。

鍵を作った本人は最初から p と q を知っています。だから秘密鍵 d を作れます。一方、攻撃者は公開鍵に含まれる n と e しか知りません。秘密鍵を作るには、まず巨大な n を素因数分解して p と q を見つける必要があります。

flowchart TD
  P[p と q を知っている鍵の所有者] --> N[n = p × q を作る]
  N --> Pub[公開鍵 n, e]
  N --> Priv[秘密鍵 d を作る]
  Pub --> Attacker[攻撃者が見る情報]
  Attacker --> Factor[n から p と q を探す]
  Factor --> Hard[巨大な n では現実的に難しい]

掛け算と逆算の難しさが違う

RSAの直感で大切なのは、計算の向きによって難しさが大きく違うことです。

立場	知っているもの	必要な計算
鍵を作る本人	p と q	n = p × q を作る。これは簡単
攻撃者	n と e	n から p と q を探す。巨大な数では難しい

53 × 71 = 3763 を計算するのは簡単です。しかし 3763 だけを渡されて、元の2つの素数を探すのは少し面倒です。この差が数百桁の世界では爆発的に広がります。

小さな数字でRSAを見る

本物のRSAより極端に小さい数字で、仕組みだけを見てみます。

p = 5
q = 11
n = 55

公開鍵の e = 3
秘密鍵の d = 27

公開鍵 = (n = 55, e = 3)
秘密鍵 = (n = 55, d = 27)

平文を数字 7 として暗号化します。

C = 7^3 mod 55
  = 343 mod 55
  = 13

暗号文は 13 になります。次に、秘密鍵 d = 27 で復号します。

M = 13^27 mod 55
  = 7

つまり、公開鍵側の計算で 7 は 13 に変わり、秘密鍵側の計算で 13 は 7 に戻ります。この対応関係を作るために、鍵生成時に p と q が使われます。

暗号化と署名では向きが違う

RSAは暗号化と署名の両方に使われますが、目的が違います。

用途	使う鍵	確認できること
暗号化	公開鍵で暗号化し、秘密鍵で復号する	秘密鍵を持つ相手だけが読める
署名	秘密鍵で署名し、公開鍵で検証する	秘密鍵の持ち主が署名したことと、改ざんされていないこと

JWTのRS256は署名の用途です。発行者が秘密鍵でJWTに署名し、受け取った側が公開鍵で署名を検証します。

ただし、公開鍵で署名検証が成功しても、その公開鍵が本当に信頼すべき発行者のものかは別問題です。OIDCでは、信頼するissuerをアプリ側に固定し、そのissuerがHTTPSで公開しているJWKSから公開鍵を取得します。

信頼済みissuer
  ↓
HTTPS/TLS
  ↓
JWKS
  ↓
kidに対応する公開鍵
  ↓
RS256署名検証

実際のRSAではそのまま暗号化しない

ここまでの説明では、理解しやすくするために M^e mod n という形だけを見てきました。しかし、実際の暗号システムでは、平文をそのままRSA計算に入れることはしません。

RSA暗号化では、RSA-OAEPのような安全なパディング方式を使います。また、長い文章やファイル全体をRSAで直接暗号化することも一般的ではありません。RSAは計算が重く、扱えるデータサイズにも制限があるためです。

実務では、次のようなハイブリッド暗号がよく使われます。

文章やファイル
  ↓
AESなどの共通鍵暗号で暗号化

AESの鍵
  ↓
RSA公開鍵で暗号化

つまりRSAは、大きなデータ本体を暗号化するというより、共通鍵を安全に渡すための仕組みとして使われることが多いです。

まとめ

RSAは、巨大な素数の掛け算は簡単だが、その結果から元の素数を探すのは難しい、という非対称性を利用した公開鍵暗号です。

鍵を作る本人は p と q を知っているため秘密鍵を作れます。攻撃者は公開鍵の n と e しか知らないため、秘密鍵を作るには巨大な n を素因数分解しなければなりません。

この性質によって、公開鍵は配ってよく、秘密鍵だけを本人が守るという仕組みが成り立ちます。RSAを理解するときは、まず「公開鍵は入口、秘密鍵は本人だけが使える出口」というイメージを持つと、暗号化や署名の話がつながりやすくなります。