電子署名の数学（一方向性関数と検証）

Q: 電子署名の数学（一方向性関数と検証）とは何ですか？

2つの十分大きな素数 p, q を選び、n = pq、オイラーのトーシェント関数 \varphi(n) = (p-1)(q-1) を計算する。\varphi(n) と互いに素な公開指数 e を選び、ed \equiv 1 \pmod{\varphi(n)} を満たす秘密指数 d を求める（拡張ユークリッドの互除法）。公開鍵は (n, e)、秘密鍵は (n, d) である。 メッセージを数値 m (0 \le m < n) としたとき、電子署名は次のように定義される。 \text{署名: } s = m^d \bmod n \text{検証: } m' = s^e \bmod n \ \text{が} \ m' = m \ \text{と一致するか確認}

Q: 電子署名の数学（一方向性関数と検証）は社会やプログラミングでどのように使われていますか？

トイRSAパラメータによる電子署名の生成と検証（教育用実装）: 極めて小さな素数から鍵ペアを生成し、法べき乗による署名生成・検証を実装する。メッセージを改ざんした場合に検証が失敗することを確認できる。実運用のRSA署名では桁数がこの実装の数十倍〜数百倍の巨大な素数を使うため、この実装はあくまで数学的構造を理解するための教育用デモである。

秘密鍵で「署名」し公開鍵で「検証」する、法演算のべき乗が生む非対称性

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 電子署名は「秘密鍵でしか作れないが、公開鍵で誰でも検証できる」という非対称性を、法（mod）演算のべき乗の性質を利用して実現している
2: RSA型の署名では、署名 = メッセージ^d mod n（秘密鍵dを使用）、検証 = 署名^e mod n（公開鍵eを使用）を計算し、その結果が元のメッセージと一致するかで真正性を確かめる
3: メッセージを1ビットでも改ざんすると、署名との対応が数学的に崩れて検証が必ず失敗するため、電子署名は「誰が送ったか」と「改ざんされていないか」を同時に保証できる

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

電子署名は「秘密鍵でしか作れないが、公開鍵で誰でも検証できる」という非対称性を、法（mod）演算のべき乗の性質を利用して実現している

身につく武器・思考力

RSA型の署名では、署名 = メッセージ^d mod n（秘密鍵dを使用）、検証 = 署名^e mod n（公開鍵eを使用）を計算し、その結果が元のメッセージと一致するかで真正性を確かめる

実社会・ITでの活躍現場

•トイRSAパラメータによる電子署名の生成と検証（教育用実装）
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

ごく小さな数（p, qが10〜20程度）で作ったトイRSA鍵ペアを使い、メッセージに対応する数値を「秘密鍵で署名」ボタンで署名し、「公開鍵で検証」ボタンで検証してみよう。メッセージの数値をスライダーで変えて「改ざん」した場合、検証結果がどう変わるかを確認できる。

素数 p, q

61, 53

n = pq

3233

公開鍵 e

秘密鍵 d

2753

メッセージ（数値化済み） m65

💡 一方向性と検証:

$s = m^d \bmod n$ は秘密鍵 d を持つ人にしか計算できませんが、 $s^e \bmod n = m$ の検証は公開鍵 e があれば誰でもできます。メッセージを改ざんすると、この等式が崩れて検証は必ず失敗します。

↑ ここでは p, q に61, 53という非常に小さな素数を使っています。実際のRSAは数百桁の素数を使うため、この小さな数のように総当たりで素因数分解することはできません。あくまで数式の構造を理解するための教育用デモです。

直感チェック！ミニクイズ

電子署名の検証プロセスにおいて、署名者以外の誰かが署名時のメッセージを1文字でも改ざんすると何が起こるか？

Layer 2 — 定義・受験・証明

定義

2つの十分大きな素数 $p, q$ を選び、 $n = pq$ 、オイラーのトーシェント関数 $\varphi(n) = (p-1)(q-1)$ を計算する。 $\varphi(n)$ と互いに素な公開指数 $e$ を選び、 $ed \equiv 1 \pmod{\varphi(n)}$ を満たす秘密指数 $d$ を求める（拡張ユークリッドの互除法）。公開鍵は $(n, e)$ 、秘密鍵は $(n, d)$ である。

メッセージを数値 $m$ ( $0 \le m < n$ ) としたとき、電子署名は次のように定義される。

\text{署名: } s = m^d \bmod n

\text{検証: } m' = s^e \bmod n \ \text{が} \ m' = m \ \text{と一致するか確認}

公式・数理モデル

s = m^d \bmod n \ (\text{署名, 秘密鍵}d), \qquad m' = s^e \bmod n \ (\text{検証, 公開鍵}e)

証明・導出

署名が正しく検証できる（ $s^e \bmod n = m$ となる）ことの証明：

$d$ は $ed \equiv 1 \pmod{\varphi(n)}$ を満たすように選ばれているので、ある整数 $k$ を用いて $ed = 1 + k\varphi(n)$ と書ける。したがって、

s^e \bmod n = (m^d)^e \bmod n = m^{ed} \bmod n = m^{1 + k\varphi(n)} \bmod n = m \cdot \left(m^{\varphi(n)}\right)^k \bmod n

ここでオイラーの定理（ $m$ と $n$ が互いに素なとき $m^{\varphi(n)} \equiv 1 \pmod n$ ）を用いると、

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

よって $s^e \bmod n = m$ が成り立ち、公開鍵 $e$ を使った検証計算は必ず元のメッセージ $m$ を復元する。

一方向性（秘密鍵なしでは署名を偽造できない）の根拠は「離散対数・素因数分解の困難性」にある。攻撃者は公開鍵 $(n, e)$ を知っていても、 $n = pq$ の素因数分解が計算量的に極めて困難であるため $\varphi(n)$ を求められず、したがって $d$ を復元できない。 $d$ を知らずに任意の $m$ に対して $m^d \bmod n$ を計算する効率的な方法は（ $n$ が十分大きければ）知られていない。これが「秘密鍵でしか署名を作れないが、公開鍵で誰でも検証はできる」という非対称性の数学的根拠である。

また改ざん検知の仕組みは、 $s^e \bmod n$ の計算結果が法 $n$ の下でメッセージ $m$ に一対一に対応する（べき乗写像 $x \mapsto x^e \bmod n$ が $\gcd(e, \varphi(n))=1$ のとき全単射になる）ことに由来する。メッセージが $m$ から $m'$ ( $m' \neq m$ ) に改ざんされれば、対応する検証結果 $s^e \bmod n$ は元の $m$ のままであり、改ざん後の $m'$ とは一致しなくなるため、検証は確実に失敗する。

押さえておきたいポイント

実際のRSA署名では素数 $p, q$ は数百桁の非常に大きな数を用いる。ここで扱う10〜20程度の小さな数は、計算過程を手で追える教育目的のトイモデルであり、実用上のセキュリティは一切ない
実運用では、メッセージ全体ではなく、まずハッシュ関数（SHA-256等）でメッセージを固定長のダイジェストに圧縮してから署名する（メッセージが長くても計算量が一定になり、また衝突耐性を利用して改ざん検知の信頼性を高める）
「秘密鍵で暗号化のように見える操作をする」ことと「公開鍵で復号のように見える操作をする」ことが数学的に逆写像の関係になっている点が、公開鍵暗号方式と電子署名の対称性であり同時に非対称性の源泉でもある
電子署名は「本人性（誰が署名したか）」と「完全性（改ざんされていないか）」の両方を1つの数値で保証する、電子契約・ソフトウェア配布・HTTPS証明書などの基盤技術

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

トイRSAパラメータによる電子署名の生成と検証（教育用実装）

極めて小さな素数から鍵ペアを生成し、法べき乗による署名生成・検証を実装する。メッセージを改ざんした場合に検証が失敗することを確認できる。実運用のRSA署名では桁数がこの実装の数十倍〜数百倍の巨大な素数を使うため、この実装はあくまで数学的構造を理解するための教育用デモである。

1// 法べき乗の高速計算（繰り返し二乗法）
2function modPow(base: number, exp: number, mod: number): number {
3  let result = 1;
4  base = base % mod;
5  while (exp > 0) {
6    if (exp % 2 === 1) result = (result * base) % mod;
7    exp = Math.floor(exp / 2);
8    base = (base * base) % mod;
9  }
10  return result;
11}
12
13// 拡張ユークリッドの互除法で mod 逆元（秘密鍵 d）を求める
14function modInverse(e: number, phi: number): number {
15  let [old_r, r] = [e, phi];
16  let [old_s, s] = [1, 0];
17  while (r !== 0) {
18    const q = Math.floor(old_r / r);
19    [old_r, r] = [r, old_r - q * r];
20    [old_s, s] = [s, old_s - q * s];
21  }
22  return ((old_s % phi) + phi) % phi;
23}
24
25// --- トイRSA鍵ペアの生成（教育用: 実際は数百桁の素数を使う） ---
26const p = 61;
27const q = 53;
28const n = p * q; // 3233
29const phi = (p - 1) * (q - 1); // 3120
30const e = 17; // 公開鍵の指数（gcd(e, phi) = 1）
31const d = modInverse(e, phi); // 秘密鍵の指数
32
33// --- 署名: 秘密鍵 d でメッセージに署名する ---
34function sign(message: number): number {
35  return modPow(message, d, n);
36}
37
38// --- 検証: 公開鍵 e で署名を検証する ---
39function verify(message: number, signature: number): boolean {
40  return modPow(signature, e, n) === message;
41}
42
43const message = 65; // 送信するメッセージ（数値化済み、実運用ではハッシュ値）
44const signature = sign(message);
45console.log("署名:", signature);
46console.log("正しいメッセージでの検証:", verify(message, signature)); // true
47
48const tamperedMessage = 66; // 1だけ改ざん
49console.log("改ざんされたメッセージでの検証:", verify(tamperedMessage, signature)); // false