なんとなく理解する、RSA暗号を用いたJWT認証

Last updated at 2024-11-06Posted at 2024-11-06

はじめに

認証機能などを作るとき、何も考えずにJWT認証を使っていませんか。~~はい、私です~~

どういう仕組みなのか気になったので調べてみました。

RSA暗号(RS256)の仕組みも軽く書いてみたので、JWTとか何もわからないよーて人も是非読んでみてください。

全体の概要

まず、共通鍵での認証を行いたい場合は、サーバー内にのみ秘密鍵が置かれており、それを元にリクエストの一部を署名して、あとは認証期限などを残して返すだけなので、仕組みは簡単そうです。(JWTなどの用語はとりあえず飛ばして読んでください。)

自分たちの作ったの認証機能のみで動かす場合はこれでいいと思います。

（↓APIにDjango、表にNext.jsでの例）

ただ、⇩のようなGoogleでログインなどを秘密鍵だけで認証しようと思った時、どのようなリスクが表れてしまうでしょうか。

秘密鍵を複数のサービスやクライアントに配布する必要があると、秘密鍵が漏洩するリスクが非常に高まります。

秘密鍵が漏洩した場合、悪意のある第三者がなりすましや偽の署名生成を行う可能性があるため、セキュリティが大幅に低下してしまいます。

ここで登場するのがIDプロバイダで、IDプロバイダが署名の生成に秘密鍵を使い、クライアントやサービスは公開鍵で署名を検証することができます。公開鍵は自由に配布できるため、誰でも署名を検証でき、IDプロバイダからのトークンが改ざんされていないことを簡単に確認できます。

しかし、この図から見てみると、公開鍵で署名を検証して、それが正規の秘密鍵によって出来たものなのか検証はできるけれど、秘密鍵自体は特定できないできる魔法のような鍵が必要なことがわかります。

(ネタバレ...魔法なんてないです。サマーウォーズの健二が鼻血出しながら暗算で潰しました。)

お先に結論

暗号化のアルゴリズムにはいろいろありますが、RS256においては、巨大な互い素な自然数$(p,q)$の積$pq$を元に秘密鍵を作り、公開鍵を$N=$$pq$(計算途中で他の鍵も出てきますが)とすることで、巨大な自然数の因数分解ができないと秘密鍵が推測できないようになっています。

この巨大というのがまた巨大で、現在の暗号化技術において安全性が担保されるためには、数百桁の素数$(p,q)$が必要とされます。

例えば、RSA暗号の推奨鍵長である2048ビットの場合、これに相当するのは約617桁の数です。このように桁数が非常に大きくなると、一般的な因数分解アルゴリズムでは計算に膨大な時間がかかり、現行のコンピュータでは実質的に解読が不可能とされています。いました。なんか変わってきているみたいです。

やっと序章、JWTの内容から書いていきたいと思います。

JWT認証とは

JWT (JSON Web Token)

認証や情報のやり取りのために用いられるデータフォーマットで、JSON形式で表現されます。JWTは「情報のパッケージ」を意味し、必ずしも署名や暗号化を含むわけではありません。JWTは3つの部分 (ヘッダー、ペイロード、署名) で構成され、ドット (.) で区切られます。

JWS (JSON Web Signature)

JWTを含むデータの署名を行うための仕様です。JWSはデータの完全性を保証するためにデジタル署名を付加し、不正な改ざんを検知できるようにします。JWTが署名付きの場合、そのJWTはJWSとしての性質を持つといえます。

上の写真は下のような指定でした。(公開鍵、秘密鍵は適当に巨大な数にしました)

JWT認証

JWT認証は、ユーザーが一度ログインすると、サーバーからJWTが発行され、クライアントがこのトークンを持って通信を行う仕組みです。サーバーはトークンを検証するだけでユーザーの認証ができるため、セッション管理が不要です。認証用のJWTはサーバーレスポンスでクライアントに渡され、後続リクエストのヘッダーにトークンを含めることで認証を行います。

JWTはデータ交換フォーマットで、署名（JWS）や暗号化（JWE）を含む場合もあり、JWT自体が認証でセキュリティのあるものを示しているわけではない。

BASE64URLとは

先ほど、ヘッダーではHS256、JWTなどと指定したのに、いざ作成されたJWTを見てみると署名の場所だけではなく、ヘッダーとペイロードも文字だらけでしたよね。

これには、BASE64URLと呼ばれる処理がされています。

まずは手順から見ていきましょう。

BASE64URLエンコーディング手順

バイナリ変換
- エンコードしたいデータを、まずASCIIまたはUTF-8などのバイトデータ（バイナリ）に変換します。
6ビットごとに分割
- バイナリデータを6ビットごとに区切ります。この6ビットの各グループは、BASE64URLの64種類の文字に対応します。
BASE64URLの文字に変換
- 各6ビットの値を以下のBASE64URL用文字セット(A~z,0~9と-)にマッピングします。
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_

ここでは、$+$を$-$に、$/$を_に置き換えることでURLに適した形式にします。
パディング文字の削除
- BASE64では、データが24ビット（3バイト）の倍数でない場合、末尾にパディング文字 $=$ を追加しますが、BASE64URLではパディングを削除します。したがって、$=$は使用されません。

例: {"n":4} をエンコードする場合

例: `{"n":4}` をエンコードする場合

この解説では、{"n":4} の文字列を BASE64URL にエンコードする手順を示します。

ASCII 変換
各文字を ASCII コードに変換します。

{    "    n    "    :    4    }
123  34   110  34   58   52   125

2進数変換
各 ASCII コードを 8 ビットの 2 進数に変換します。

{    : 01111011
"    : 00100010
n    : 01101110
"    : 00100010
:    : 00111010
4    : 00110100
}    : 01111101

6 ビットグループへの分割
8 ビットの 2 進数列を 6 ビットずつのグループに分割します。最後に 6 ビット未満の残りが出る場合はパディングします。
```
011110  110010  001001  101110  001000  100011  101000  110100  011111  01(パディング)
```

BASE64URL 変換
各 6 ビットのグループを BASE64URL で使用する文字に変換します。

011110 (30) → e
110010 (50) → y
001001 (9)  → J
101110 (46) → u
001000 (8)  → I
100011 (35) → j
101000 (40) → o
110100 (52) → 4
011111 (31) → f
01     → Q (パディング後)

結果

エンコード後の文字列は次のようになります。

eyJuIjo0fQ

これを先ほどの画像と見比べてみましょう。

紫部分のペイロードと一致していますね！ヘッダーも同様にこの処理でBASE64URL表記になっています。

BASE64URLの形式において、異様にeyJで始まることが多い理由は{と"で始まることがほとんどだからでしょう。

こちらのサイトで試してみてください。

しかし、どうしてこのような処理を行なったのでしょうか？

7ビットの制約

通信プロトコルや古いシステムでは、ASCIIの7ビット（つまり、0～127の範囲の文字）だけが扱える場合がありました。この制約下では、8ビットのバイナリデータ（画像や動画、バイナリファイルなどのファイルデータ）を直接送ることができません。ASCIIの7ビット文字の範囲に収まるようにデータを変換する必要が生まれ、BASE64がその解決策のひとつとなります。

BASE64では、バイナリデータを6ビットごとに分割し、64種類の文字（アルファベットの大小文字、数字、+ と /）で表現します。この64種類の文字は、ASCIIの7ビットの範囲に含まれるため、古いプロトコルやテキストのみが扱える環境でも、問題なく送受信が可能です。

BASE64をURLに使うときの問題点

BASE64エンコーディングは、データをASCIIテキストに変換して通信やデータ保存を容易にしますが、通常のBASE64ではURLに問題を引き起こす文字（例えば、+ や /）が使われます。これに対してBASE64URLは、次のように記号の置き換えとパディングの削除を行い、URLやファイル名に直接使えるようにしています。

BASE64URLの特徴: +を-に置き換え; /を_に置き換え; 通常のBASE64で末尾に追加されるパディング文字 = を削除

この変更により、URL中でBASE64URLエンコードされたデータを使う際にエンコードやデコードの追加処理が不要になります。

署名にどのアルゴリズムを使うべきか

さぁ、あとは署名に使うアルゴリズの仕組みを把握すれば大丈夫そうですね。

以下の表が署名によく使われる有名なアルゴリズムの例です。(飛ばしてーー)

アルゴリズム	特徴	推奨鍵長	用途	適用例
RSA	公開鍵と秘密鍵を使用。鍵長が長くなるほど安全性は高いが処理速度が低下する	2048ビット以上	電子署名、デジタル証明書	互換性が求められるシステム全般
ECDSA	楕円曲線暗号を用いるため、RSAと同等のセキュリティを維持しながら短い鍵長で高速化	256ビット以上 (例: P-256)	SSL/TLS証明書、ブロックチェーン	リソース制約があるモバイルやIoT機器

この中で、今回はRS256を用いてみました。

RS256を用いた署名の仕組み

ここからほとんど数学になるので、飛ばして具体例から行った方がいいかもです。

秘密鍵を作成

とりあえず、こちらの大きな二つの互いに素な自然数から秘密鍵を求める訳のわからない文章を読んでみましょう。

秘密鍵の作成手順

まず、2つの異なる素数 $p$ と $q$ を選びます。
公開鍵$N$は、$pq$であり、巨大な素数の積で表されます。
次に、オイラーのトーシェント関数を使って、$\phi(pq)$ を計算します。これは次のように求められます：

$$
\phi(pq) = pq - p - q + 1 = (p-1)(q-1)
$$
公開鍵 $e$ を選びます。条件は $1 < e < \phi(N)$ と$ e ,\phi(N)$が互いに素であることです。
秘密鍵は指数 $d$ で構成されます。もし $p$ と $q$ が互いに素であれば、次の条件を満たす $d$ が一意に存在します：

$$
d \times e \equiv 1 \pmod{\phi(N)}
$$

簡単に説明すると、互い素な自然数p,qを2個選んで、それぞれ1引いた数がその素数と互いに素な個数である。(7だったら互いに素なのは1,2,3,4,5,6の6個)
p×qの互いに素な数はpq個からp個とq個引いた後に1個余分なもの(pq)を足した(p-1)(q-1)個であある。
互いに素なe,bからなる一次不定方程式ed + bn = 1は必ず解を持ち、
mod(n)とするとed≡1(mod n)となるdは必ず1~nの中に存在する。
n=(p-1)(q-1)とすると、dが必ず一つのみ存在するので、それを秘密鍵にしようではないか。　

φ(pq)=(p-1)(q-1) の理由

オイラーのトーシェント関数 $\phi(n)$ は、1から $n$ までの整数のうち、$n$ と互いに素である数の個数を表します。つまり、$\phi(n)$ は $n$ 以下の整数の中で、$n$ と最大公約数が1である数の個数です。

基本的な考え方:
- 素数 $p$ の場合、$p$ と互いに素な数は $1, 2, \ldots, p-1$ です。したがって、$\phi(p) = p - 1$ です。
- 同様に、素数 $q$ に対しても $\phi(q) = q - 1$ です。
合成数 $pq$ の場合:
- $p$ と $q$ が互いに素であるとき、$\phi(pq)$ は $\phi(p) \times \phi(q)$ に等しくなります。これは、$p$ と $q$ のそれぞれの倍数を除外することで求められます。
具体的な計算:
- $pq$ の中で $p$ の倍数は $q$ 個、$q$ の倍数は $p$ 個あります。ただし、$pq$ 自体は $p$ と $q$ の両方の倍数なので、重複して数えられています。
- したがって、$\phi(pq) = pq - (p + q) + 1$ となります。
- $(p-1)(q-1) = pq - p - q + 1$ だからです。

このようにして、オイラーのトーシェント関数を使って $\phi(pq)$ を計算することができます。

秘密解が一つしかできない理由

続いてこちらの説明です。

3.　公開鍵 $e$ を選びます。条件は $1 < e < \phi(N)$ と$ e ,\phi(N)$が互いに素であることです。

4.　秘密鍵は指数 $d$ で構成されます。もし $p$ と $q$ が互いに素であれば、次の条件を満たす $d$ が一意に存在します：

$$
d \times e \equiv 1 \pmod{\phi(N)}
$$

これを証明するために、以下の定理を用いていきます。

（定理）

自然数 ( a, b ) に対して、整数 ( m, n ) が存在して ( am + bn = 1 ) を満たす。

$$
\Longleftrightarrow
$$

( a, b ) は互いに素である。

簡単な説明です。数式で読みたい人は下見てください。
⇒の証明は最大公約数gを出して括ってみるけど結局1だよねーみたいな感じです。
⇦の証明は鳩の巣論法を使ってa×1からa×(b-1)までの数をaで割ったあまりは全て異なっていて、1からb-1まで出してみるけどどれか一つは1に必ずなるから整数解存在するよねー的な感じです。

証明

⇒の証明
自然数 ( a, b ) に対して、整数 ( m, n ) が存在して ( am + bn = 1 ) を満たすなら、

( a, b ) は互いに素である。

( a ) と ( b ) の最大の共通の数を ( g ) とします。

( a = gd ) と ( b = gb' ) と表せます。

式に代入すると、( g(dm + b'n) = 1 ) になります。

( g ) は 1 の約数なので、( g = 1 ) です。

だから、( a ) と ( b ) は互いに素です。

⇦の証明には部屋割り論法を用います

(部屋割り論法)
𝑛個の部屋に𝑛人が入るとき、相部屋が無ければ、どの部屋にも1人ずつ人が入っている。

まず、以下の定理から証明します

定理
( a, b ) を互いに素である自然数とします。( k ) を整数とするとき、( ak ) を ( b ) で割った余りを ( r(k) ) と表します。( k ) と ( l ) を ( b-1 ) 以下の異なる自然数とするとき、$$( r(k) \neq r(l) )$$ です。

定理（1）を簡単に言うと、$$( a \times 1, a \times 2, a \times 3, \ldots, a \times (b-1) ) $$をそれぞれ ( b ) で割ったときの余りは全部違うということです。

これを証明するために、$$( r(k) = r(l) )$$と仮定して矛盾を示します。

仮定から、

$$
ak - al = bM \quad (M \text{は整数})
$$

となります。

これを変形すると、

$$
a(k - l) = bM
$$

となります。

ここで、( a ) と ( b ) は互いに素なので、( k - l ) は ( b ) の倍数でなければなりません。

しかし、( 0 < k < b ) と ( 0 < l < b ) なので、

$$
-b < k - l < b
$$

となります。

この範囲では、( k - l = 0 ) しかありえません。つまり、( k = l ) です。

これは ( k ) と ( l ) が異なる自然数であるという仮定に矛盾します。

したがって、$( r(k) \neq r(l) ) $であることが示されました。

これを用いて、欲しかった定理を導いていきましょう。

( a , b ) が互いに素であるとき、$$( am + bn = 1 ) $$を満たす整数解(m , n)が存在する。

まず、先ほどの定理から、$$( r(1), r(2), \ldots, r(b-1) )$$ という数は全部違うことがわかります。

また、( a ) と ( b ) が互いに素なので、$$( a \times 1, a \times 2, \ldots, a \times (b-1) ) $$は ( b ) の倍数にはなりません。だから、これらの数を ( b ) で割った余りは 1 から ( b-1 ) の間にあります。ここで、部屋割り論法を用いることで、余りはどこかと必ず結びつきます。

このことから、$$( r(1), r(2), \ldots, r(b-1) ) $$の中には必ず 1 になるものがあります。それを ( r(s) ) とします。

( r(s) ) は、( as ) を ( b ) で割った余りなので、ある整数 ( q ) を使って

$$
as = bq + 1
$$

と書けます。

これを変形すると、

$$
as + b(-q) = 1
$$

これで、-qは整数なので、-qを新しい整数mに置き換えると、欲しかった式になり、証明完了です。

これを用いると、
互いに素な $m$ と $n$に対して、次のような式

$$
am + bn = 1
$$

を満たす整数 ( a ) と ( b ) が必ず存在し、

これをmod$n$で見ると、次のようになります：

$$
ap \equiv 1 \pmod{n}
$$

ただ、このままだと上記を満たす解$m$に$n$×定数倍をしたものを足した解が無数に存在してしまいます。

ここで、範囲を$nま$でとすることで、これを満たす解は一意に存在することがわかりました。

秘密鍵を用いて署名を作成

ここで、公開鍵$(N,e)$と秘密鍵$(d)$を二つの素数から作成できることがわかりました。
ただ、今回の目的としては、正常な秘密鍵を用いて作られた署名かどうかを、公開鍵で検証できるかを知りたいです。

そこで、以下の式を用います。

署名と検証の方法

署名の作成:

メッセージ $M$ を署名者の秘密鍵 $(d, N) $ を用いて署名 $S$ を作成します。

$$
S ≡ M^d \mod N
$$
署名の検証:

受信者は、公開鍵 $ (e, N) $ を使って署名 $ S $ から元のメッセージを再計算します。

$$
M' ≡ S^e \mod N
$$

このとき、もし$M'$=$M$であれば検証成功である。

正式な秘密鍵で作られたなら、次の関係が成り立っています。

$$
(M^d)^e \equiv M \mod N
$$

これは、公開鍵 $ e $と秘密鍵 $ d $ が次の条件を満たすように作られているからです。

$$
e \times d \equiv 1 \mod \varphi(N)
$$

この条件により、署名 $ S $を公開鍵$ e $ を使って復号すると、元のメッセージ $ M $ が得られるように設計されています。

わかりにくいと思うので具体例でやってみましょう。

小さい数で具体例

まず、素数 $p=3$ と $q=11$ を選びます。

$$
N = p \times q = 3 \times 11 = 33
$$

次に、オイラーのトーシェント関数 $\phi(N)$ を計算します。

$$
\phi(N) = (p - 1)(q - 1) = 2 \times 10 = 20
$$

公開鍵 $e=3$ を選びます（この値は $1 < e < 20$ かつ $e$ と $\phi(N) = 20$ が互いに素である必要があります）。

秘密鍵 $d$ を求めます。$d$ は次の条件を満たす必要があります：

$$
e \times d \equiv 1 \ (\text{mod} \ 20)
$$

つまり、

$$
3 \times d \equiv 1 \ (\text{mod} \ 20)
$$

となる $d = 7$ が見つかります。

したがって、公開鍵は $(N, e) = (33, 3)$、秘密鍵は $d = 7$ です。

暗号化(署名)

平文を $M = 4$ として暗号化します。

$$
C = M^e \ \text{mod} \ N = 4^3 \ \text{mod} \ 33 = 64 \ \text{mod} \ 33 = 31
$$

したがって、暗号文は $C = 31$ です。

検証

暗号文 $C = 31$ が元の平文 $M = 4$ に対応することを検証します。

公開鍵を使って、$C$ から平文 $M$ を復元できるか確認します。

$$
M' = C^d \ \text{mod} \ N = 31^7 \ \text{mod} \ 33 = 4
$$

計算結果として、$M' = 4$ が得られました。したがって、暗号文 $C = 31$ は元の平文 $M = 4$ に対応していることが確認されました。

公開鍵から逆算も可能じゃない？

小さい数なら可能なのでやってみましょう。

N を素因数分解する

公開鍵 $N$ を素因数分解し、$p$ と $q$ を求めます。RSAでは、$N$ が大きい場合、この分解が困難であるため、安全性が保たれます。しかし、小さい数であれば、試し割り法や他の因数分解アルゴリズムを使って簡単に分解できます。

例として、$N = 33$ の場合、$p = 3$ と $q = 11$ です。

オイラーのトーシェント関数φ(N)を計算する

次に、$\phi(N)$ を計算します。

$$
\phi(N) = (p - 1)(q - 1)
$$

例では、

$$
\phi(33) = (3 - 1)(11 - 1) = 2 \times 10 = 20
$$

dを求める

秘密鍵 $d$ は、以下の合同式を満たす整数です。

$$
e \times d \equiv 1 \ (\text{mod} \ \phi(N))
$$

この式は「$e$ の $\phi(N)$ における逆元を求める」ことを意味します。例えば、$e = 3$ の場合、次のようにして $d$ を探します。

$$
3 \times d \equiv 1 \ (\text{mod} \ 20)
$$

$d$ は $1, 2, 3, \ldots$ と順番に代入していき、この式が成り立つ $d$ を探します。この場合、$d = 7$ で式が成り立つため、秘密鍵は $d = 7$ となります。

あれ...これさっきやったくない？？

そうです。因数分解すら解けてしまえば、あとは$mod (φ(N))$の範囲で入れていくだけなので現実的な計算時間でとけてしまいます。

つまり、RSAにおける一番の頑丈なところは超巨大な因数分解が困難なところにあります。

もちろん、因数分解を効率的に探索するアルゴリズムも私は何もわかりませんが色々あるみたいです。

とりあえず、今日分かったことは、健二、お前なんで数学オリンピック落ちたんや。

参考サイト

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up