sharin

Appearance

暗号 ​

実装: crypto/rsa/ / 実行: go test ./crypto/rsa/

「暗号化」「ハッシュ」「署名」。全部まとめて暗号と呼ばれがちだが、目的がまるで違う3つの道具。この章はまずその違いを整理し、公開鍵暗号(RSA)を小さな素数で自作する。公開鍵で暗号化して秘密鍵で戻す、その鍵を逆向きに使うと署名になる。同じ数式の裏表であることが、手を動かすと腑に落ちる。auth と blockchain の土台になる回。

この章で作るもの ​

まず「暗号化・ハッシュ・署名は別物」を整理し、その中核である**公開鍵暗号(RSA)**を 小さな素数で実装する。auth 編(JWT の署名)も blockchain 編(取引の署名)も、 この章の署名がそのまま土台になる。

先に押さえることが3つある。

  • 暗号化・ハッシュ・署名は目的が違う別の道具。混同しやすいが役割は真逆のこともある
  • 公開鍵暗号は「暗号化の鍵と復号の鍵が別」。これで鍵配布問題が解ける
  • 暗号化と署名は鍵の向きが逆の同じ数式。RSA だとそれが数式レベルで見える

まず整理: 暗号化・ハッシュ・署名は別物 ​

道具何をする元に戻せる?目的
暗号化中身を読めなくする戻せる(鍵があれば)秘密を守る
ハッシュ任意長を固定長の指紋にする戻せない(一方向)同一性の確認・改竄検出
署名本人が作った証拠を付ける—本人性と改竄検出

よくある誤解が「ハッシュは暗号化の一種」。違う。暗号化は戻すためにやるが、 ハッシュは戻せないのが本質(パスワードをハッシュで保存するのは、盗まれても 元が分からないため)。署名はまた別で、「この人が確かに作った」を証明する。

暗号化:  平文 ──暗号化──▶ 暗号文 ──復号──▶ 平文     (往復する)
ハッシュ: データ ──hash──▶ 指紋                      (片道。戻せない)
署名:    データ ─hash→ 指紋 ─秘密鍵で暗号化→ 署名     (ハッシュ + 公開鍵暗号)
3つの道具の関係。暗号化は往復する。ハッシュは片道。署名はハッシュ + 公開鍵暗号の組み合わせでできている

この章は暗号化と署名の中核、公開鍵暗号を作る。ハッシュは別の仕組みで、 ハッシュと HMAC の章で自作した。

鍵配布問題と、公開鍵暗号 ​

暗号化には2種類ある。

  • 共通鍵暗号(AES など): 暗号化と復号で同じ鍵を使う。速いが、 「その鍵をどうやって相手に安全に渡すか」問題が残る(鍵を送る通信が盗聴されたら終わり)。 中身は対称暗号とモードの章で作った
  • 公開鍵暗号(RSA など): 暗号化の鍵(公開鍵)と復号の鍵(秘密鍵)が別。 公開鍵は誰に見られてもいい。だから鍵配布問題が消える

公開鍵暗号の要はこの一点にある。公開鍵で暗号化したものは、対応する秘密鍵でしか戻せない。 南京錠を配って回るようなもの。誰でも鍵をかけられる(公開鍵)が、開けられるのは 鍵を持つ本人(秘密鍵)だけ。

RSA: 素因数分解の難しさに賭ける ​

RSA は「大きな数の素因数分解は難しい」という事実を安全性の根拠にする。 2つの素数 p, q から鍵を作る:

go
// PublicKey は公開鍵 (e, n)。暗号化と署名検証に使う。誰に配ってもよい。
type PublicKey struct {
	E, N int64
}

// PrivateKey は秘密鍵 (d, n)。復号と署名に使う。絶対に他人に渡さない。
type PrivateKey struct {
	D, N int64
}

// GenKeyPair は2つの素数 p, q から鍵ペアを作る。
//
//	n   = p·q                     ← 公開する法(modulus)
//	φ   = (p-1)(q-1)              ← n のオイラー関数(秘密)
//	e   = φ と互いに素な公開指数   ← 慣例の 65537。φ が小さければ互いに素な小さい奇数
//	d   = e の逆元 (e·d ≡ 1 mod φ) ← 秘密指数。φ を知らないと求まらない
//
// 「n だけ知っていても d は求まらない(φ を知るには n の素因数分解が要る)」が安全性の核。
func GenKeyPair(p, q int64) (PublicKey, PrivateKey) {
	if !isPrime(p) || !isPrime(q) || p == q || p < 5 || q < 5 {
		panic("rsa: p, q must be distinct primes >= 5")
	}
	n := p * q
	phi := (p - 1) * (q - 1)

	// e は φ と互いに素な公開指数。慣例の 65537 が使えなければ小さい候補を探す。
	e := int64(65537)
	if e >= phi || gcd(e, phi) != 1 {
		e = 3
		for gcd(e, phi) != 1 {
			e += 2
		}
	}
	d := modInverse(e, phi) // e の逆元
	return PublicKey{E: e, N: n}, PrivateKey{D: d, N: n}
}

n = p·q は公開する。でも n から p, q を復元する(素因数分解)のは、n が十分大きければ 現実的な時間で解けない。そして秘密鍵 d を求めるには φ=(p-1)(q-1) が要り、 φ を知るには p, q が要る。だから n を公開しても d は守られる。これが安全性の核心。

暗号化と復号 ​

go
// Encrypt は公開鍵で暗号化する: c = m^e mod n。
// m は 0 <= m < n の整数(実物はメッセージをこの範囲のブロックに切る)。
func Encrypt(pub PublicKey, m int64) int64 {
	return modExp(m, pub.E, pub.N)
}

// Decrypt は秘密鍵で復号する: m = c^d mod n。
// e で上げたものを d で戻せるのは、e·d ≡ 1 mod φ という関係(オイラーの定理)による。
func Decrypt(priv PrivateKey, c int64) int64 {
	return modExp(c, priv.D, priv.N)
}

暗号化は c = m^e mod n、復号は m = c^d mod n。e で上げたものが d で元に戻るのは、 e·d ≡ 1 mod φ という鍵の作り方(オイラーの定理)による。

コードの読みどころ: modExp(べき乗剰余) ​

m^e を素直に計算すると、小さな数でも桁が天文学的になる。だから 掛けるたびに mod を取る(modExp)。二乗を繰り返す高速べき乗法で、 m^e mod n を大きな中間値を作らずに求める。RSA が実用になるのはこの計算法のおかげ。

署名: 鍵を逆向きに使う ​

ここが美しいところ。秘密鍵で上げて、公開鍵で戻すと、暗号化とは逆の意味になる。

go
// Sign は秘密鍵で署名する: s = m^d mod n。
// 暗号化(公開鍵で上げる)と鍵の向きが逆。「秘密鍵を持つ本人しか作れない値」を作る。
// 実物はメッセージそのものでなくハッシュに署名する(長さ固定 + 改竄検出のため)。
func Sign(priv PrivateKey, m int64) int64 {
	return modExp(m, priv.D, priv.N)
}

// Verify は公開鍵で署名を検証する: s^e mod n == m なら本物。
// 誰でも(公開鍵だけで)検証できるが、作れるのは秘密鍵の持ち主だけ。これが「署名」。
func Verify(pub PublicKey, m, sig int64) bool {
	return modExp(sig, pub.E, pub.N) == m
}
  • 暗号化: 公開鍵で上げる(誰でも) → 秘密鍵で戻す(本人だけ) = 秘密を守る
  • 署名: 秘密鍵で上げる(本人だけ) → 公開鍵で戻す(誰でも) = 本人性を証明する

秘密鍵を持つ本人しか作れない値(署名)を、誰でも公開鍵で検証できる。 「確かにこの人が作った、かつ改竄されていない」。auth 編の JWT も、 blockchain 編の取引も、この署名で信頼を作る。

試す: 暗号化と署名を切り替えて、鍵の向きが逆になること、 そして復号/検証で元のメッセージに戻ることを確かめてほしい。

デモRSA(小さな素数)n=3233
暗号化署名
公開鍵 (e=7, n=3233)秘密鍵 (d=1783, n=3233)
公開鍵で暗号化c = 427 mod 3233 = 240
秘密鍵で復号m = 2401783 mod 3233 = 42✓ 元に戻った

誰でも公開鍵で暗号化できるが、復号できるのは秘密鍵 d を持つ人だけ。

メリット / デメリット / 実物との距離 ​

メリット

  • 鍵配布問題を解く(公開鍵は公開してよい)
  • 1つの鍵ペアで暗号化と署名の両方ができる
  • 署名で本人性と改竄検出を同時に得る

デメリット / 実物との距離

  • 遅い: 公開鍵暗号は共通鍵暗号より桁違いに遅い。実際は「RSA で共通鍵を交換し、 本体は AES で暗号化」するハイブリッド(TLS がこれ)
  • パディング必須: 素の RSA(この章)は、同じ平文が同じ暗号文になる等の弱点がある。 実物は OAEP(暗号化)/PSS(署名)でランダム性を混ぜる
  • 鍵が大きい: 安全には2048bit 以上。この章の n=3233 は一瞬で素因数分解できる
  • 署名するのはハッシュ: 実物はメッセージそのものでなく、その SHA-256 に署名する (長さ固定 + 改竄検出)

実例

  • TLS(HTTPS)の鍵交換・証明書。HTTP サーバの "S"
  • SSH の公開鍵認証、Git のコミット署名
  • 暗号通貨の取引署名(UTXO の所有権の証明)

設計の観点 ​

  • 難しさを1つ選んで、そこに全部を賭ける: RSA の安全性は素因数分解が難しいという1点だけに乗っている。破られるとしたらどこかを1か所に絞れることが、この設計の強さでもあり弱さでもある
  • 同じ道具を逆向きに使う: 公開鍵で閉じて秘密鍵で開けば秘密が守れ、秘密鍵で閉じて公開鍵で開けば本人だと分かる。向きを変えるだけで、目的がまったく別のものになる
  • 配れるものと配れないものを分ける: 公開鍵は全世界に配ってよく、秘密鍵は絶対に配らない。この非対称さこそが、事前に会わずに秘密を共有できる理由になる
  • 遅いものは、要所だけに使う: 公開鍵暗号は桁違いに遅いので、本文には使わない。鍵の受け渡しだけを担わせ、本文は共通鍵で暗号化する。適材適所が性能の設計そのものになる
  • 決定的であることが弱点になる: 同じ平文が必ず同じ暗号文になると、送ったものを当てられてしまう。だから実物はランダム性を混ぜる詰め物(パディング)を必須にする
  • 署名する相手を固定長にする: メッセージそのものではなくハッシュに署名すると、長さによらず一定の手間で済み、改竄検出も同時に手に入る

裏どり:

  • 教科書 RSA は使ってはいけない: 詰め物なしの素の RSA は、同じ平文が同じ暗号文になるほか、複数の受信者へ同じ短い平文を送ると復元できてしまう攻撃が知られている。暗号化は OAEP、署名は PSS を付けるのが規格(PKCS#1 v2)の要求になる
  • 鍵の長さの相場: 2048 ビットが現在の下限で、より長い鍵は指数的に重くなる。同じ強度を短い鍵で得られる楕円曲線(ECDSA、Ed25519)が置き換えを進めていて、TLS の鍵交換も楕円曲線が主流になった
  • 署名と暗号化で鍵を使い回さない: 理屈上は同じ鍵ペアでどちらもできるが、実務では別の鍵を使う。片方の用途で漏れた情報がもう片方を弱めうるためになる
  • 速度差の実際: 公開鍵の演算は共通鍵の数百倍から数千倍重い。TLS が接続の最初だけ公開鍵を使い、以降は共通鍵に切り替えるのは、この差を接続あたり1回に閉じ込めるためになる
  • 量子計算機への備え: 素因数分解も離散対数も、量子計算機の Shor のアルゴリズムで解ける見込みがある。だから格子など別の難しさに基づく方式(耐量子暗号)の標準化が進んでいる。難しさを1つに賭ける設計は、その難しさが崩れたときに一斉に崩れる

簡略化したこと ​

  • 極小の素数: 安全ではない、教材専用。実物は数百桁
  • パディングなし: OAEP/PSS は未実装
  • 整数1つの暗号化: ブロック分割やハッシュへの署名はしていない
  • 素数判定が素朴: 実物は Miller-Rabin の確率的判定

参考資料 ​