2026-08-26·無料·16分で読めます

暗号を1から — 共通鍵・公開鍵・ハッシュ

暗号は「読めない文字を作る技術」ではなく「元に戻す手間に極端な差を作る技術」です。共通鍵・公開鍵・ハッシュという3つの道具を前提知識ゼロから積み上げ、なぜ素因数分解が使われるのか、署名は何を保証するのか、そして過去の暗号がどう壊れてきたかまでを一続きで追います。

#cryptography #security #aes #rsa #hash #digital-signature

対象textタスクsystems

暗号がやっているのは「隠す」ことではない

暗号というと、読めない文字列を作る魔法のように聞こえます。でも設計者が実際に作っているのは、もっと素っ気ない性質です。ある秘密を知っている人には元に戻すのが簡単で、知らない人には現実的な時間で戻せない。その手間の差を作ること。それだけです。

比喩を使います。あなたの家の玄関は、鍵を持っていれば1秒で開きます。持っていない人でも、ピッキングなり破壊なりで開けること自体は可能です。玄関が「安全」なのは、開けられないからではなく、開けるのに割に合わない手間がかかるからです。暗号も同じで、「絶対に解けない」ではなく「解くのに宇宙の年齢より長くかかる」を目指します。

この視点に立つと、暗号技術の全体像が3つの道具に整理できます。

共通鍵暗号 — 同じ鍵で閉めて、同じ鍵で開ける。速い。
公開鍵暗号 — 閉める鍵と開ける鍵が別。会ったことのない相手と鍵を共有できる。
ハッシュ関数 — 戻すことをそもそも想定していない。データの指紋を作る。

現実のシステム（HTTPS、SSH、暗号資産、パスワード保存）は、この3つを役割分担させた組み合わせでできています。順番に、なぜそれが必要になったのかを含めて積み上げます。

1. 共通鍵暗号 — 同じ鍵で閉めて開ける

いちばん単純な暗号から始めます。平文（元のメッセージ）のビット列と、同じ長さの鍵のビット列を用意し、1ビットずつ XOR（排他的論理和: 違えば1、同じなら0）を取ります。

$c = m \oplus k \qquad m = c \oplus k$

$m$ は平文、 $k$ は鍵、 $c$ は暗号文です。要するに「鍵で1回かき混ぜ、もう1回同じ鍵でかき混ぜると元に戻る」という関係です。同じものを2回XORすると打ち消し合うので、閉める操作と開ける操作がまったく同じ式になります。

鍵が完全にランダムで、平文と同じ長さで、二度と使い回さなければ、この方式（ワンタイムパッド）は理論的に解読不可能であることが証明できます。暗号文からはどんな平文もあり得るように見えるからです。ところが実用にはなりません。1GBのファイルを送るのに1GBの鍵を安全に届けられるなら、最初からファイルを安全に届けられるはずです。

そこで実務では、短い鍵（128ビットや256ビット）から「ランダムに見えるビット列」を作り出す関数を使います。これが AES に代表されるブロック暗号で、128ビットの塊を鍵に応じて混ぜ替える巨大な置換表のようなものだと思ってください。鍵を知らない者には、出力が乱数と見分けがつかないように設計されています。

鍵長が1ビット伸びると、総当たりは2倍になる

鍵を知らない攻撃者に残された最後の手段は、鍵を片っ端から試すこと（総当たり）です。鍵が $n$ ビットなら候補は $2^n$ 通り。ここで効いてくるのが指数の暴力です。

FIG 1鍵が1ビット伸びるだけで総当たりの手数は倍になる。nを動かすと、O(n²)までの線が地を這ったままなのに O(2ⁿ) だけが桁を突き抜けていく——暗号が守っているのはこの差です

図で確かめたとおり、 $n$ を少し増やすだけで手数の桁が変わります。攻撃者の計算機が1000倍速くなっても、鍵を10ビット伸ばせば追いつかれます。防御側のコストは足し算、攻撃側のコストは掛け算という、この非対称性が暗号の土台です。オーダー記法そのものについては計算量を1から理解するで扱っています。

2. 鍵配送問題 — 会ったことのない相手とどうやって鍵を共有するのか

共通鍵暗号は速くて強いのですが、致命的な前提があります。送る側と受け取る側が、あらかじめ同じ鍵を持っていること。

初めて訪れた通販サイトと、あなたのブラウザは事前に何も共有していません。鍵を平文で送れば、それを盗聴した者も復号できます。鍵を暗号化して送ろうにも、そのための鍵をどう共有するのか——堂々巡りです。これが鍵配送問題で、1970年代半ばまで暗号の根本的な限界でした。

この壁を壊したのが1976年のディフィーとヘルマンの論文 "New Directions in Cryptography" です。彼らが示したのは、盗聴されている通信路の上で、盗聴者には分からない共通の値を作れるという、直感に反する事実でした。

仕組みはこうです。公開の数 $g$ と大きな素数 $p$ を全員が知っているとします。アリスは自分だけが知る数 $a$ を選び、 $g^a \bmod p$ を送ります。ボブも $b$ を選び、 $g^b \bmod p$ を送ります。すると互いに、

$(g^b)^a \equiv (g^a)^b \equiv g^{ab} \pmod{p}$

を計算できます。ここで $\bmod p$ は「 $p$ で割った余り」の意味です。つまり両者は同じ $g^{ab} \bmod p$ という値にたどり着けるのに、通信路を流れたのは $g^a$ と $g^b$ だけ。盗聴者がここから $a$ を求めるには「 $g$ を何乗したらこの値になるか」を解く必要があり、これ（離散対数問題）が現実的な時間では解けない、というのが安全性の根拠です。

3. 公開鍵暗号 — なぜ素因数分解なのか

ディフィー＝ヘルマンは鍵を作る手順でした。もう一歩進めて、閉める鍵と開ける鍵を別々にするのが公開鍵暗号です。南京錠を街中にばらまいておくところを想像してください。誰でも錠を掛けられる（＝暗号化できる）が、開ける鍵はあなたしか持っていない。

これを数の世界で実現するには、片方向にはすぐ計算できるのに、逆向きは絶望的に手間がかかる演算が要ります。ここで素因数分解が登場します。

2つの素数を掛ける: 桁が何百桁あっても一瞬
掛けた結果から元の2つの素数を復元する: 現状、桁数に対して爆発的に手間が増える

この非対称性を使ったのが1977年に考案された RSA です。素数 $p, q$ を選び $n = pq$ とし、 $\phi(n) = (p-1)(q-1)$ に対して互いに素な $e$ を選び、 $ed \equiv 1 \pmod{\phi(n)}$ となる $d$ を求めます。公開するのは $(n, e)$ 、秘密にするのは $d$ です。

c = m^e \bmod n \qquad m = c^d \bmod n

(1)

「メッセージを $e$ 乗して $n$ で割った余りが暗号文、それをさらに $d$ 乗して余りを取ると元に戻る」と読みます。 $e$ 乗と $d$ 乗が打ち消し合うように $d$ を選んである、という関係です。そして $d$ を求めるには $\phi(n)$ が要り、 $\phi(n)$ を求めるには $n$ を素因数分解しなければならない。鍵の強さが「分解の難しさ」に紐付いているわけです。

ここは正直に書いておきます。素因数分解が本当に難しいことは証明されていません。「何十年も世界中が挑んで速い方法が見つかっていない」という経験的な事実に乗っているだけです。実際、記録は着実に更新されていて、768ビットの合成数が2009年に、829ビットのものが2020年に分解されています。だから推奨鍵長は時代とともに引き上げられ、いまRSAで一般に使われるのは2048ビット以上です。

なお、新しい設計では楕円曲線暗号（ECC）が主流です。同じ強度をずっと短い鍵で得られるためで、256ビット程度の楕円曲線鍵が3072ビットのRSA鍵と同程度の強度とされています。根拠となる「難しい問題」が離散対数に変わるだけで、話の骨格は同じです。

そしてどちらも、巨大な数のべき乗を計算するので共通鍵暗号より桁違いに遅い。だから実際のHTTPS通信は、公開鍵暗号で共通鍵を共有し、本文の暗号化は共通鍵暗号で行うというハイブリッド構成になっています。公開鍵は「最初の一瞬だけ使う高価な道具」です。

4. ハッシュ関数 — 戻せないことが取り柄

3つ目の道具は、暗号化とは目的が違います。ハッシュ関数は任意長のデータを固定長（例: 256ビット）の値に潰します。潰すので情報は失われ、元に戻せません。それが欠陥ではなく仕様です。

暗号学的ハッシュに求められるのは3つの性質です。

原像計算困難性: ハッシュ値から元のデータを求められない
第二原像計算困難性: あるデータと同じハッシュ値になる別のデータを作れない
衝突困難性: 同じハッシュ値になる2つのデータの組を、何でもいいから見つけることができない

3つ目がいちばん破られやすい点は覚えておく価値があります。誕生日のパラドックスと同じ理屈で、 $n$ ビットのハッシュに対して衝突は $2^{n/2}$ 程度の試行で見つかります。256ビットのハッシュの衝突耐性は「128ビット相当」であって「256ビット相当」ではありません。

ここで、プログラミングで日常的に使う「ハッシュテーブルのハッシュ」と混同しないでください。あちらは速く均等にばらけることが目的で、意図を持った攻撃者に耐えることは想定していません。両者の設計目標の違いはハッシュと近傍探索と読み比べると輪郭がはっきりします。

5. 署名 — 公開鍵を逆向きに使う

暗号化は「あなただけが読める」を作ります。署名はその逆で、「あなたが書いたことを誰でも確認できる」を作ります。鍵の使い方を裏返すだけです。

暗号化: 公開鍵で閉める → 秘密鍵で開ける
署名: 秘密鍵で作る → 公開鍵で検証する

秘密鍵を持つ人しか作れない値を、公開鍵を持つ全員が「確かにあの鍵の持ち主が作った」と確認できる。RSAの教科書的な署名は、メッセージそのものではなくハッシュ値に対して行います。

$s = H(m)^d \bmod n \qquad \text{検証}: \; s^e \bmod n \overset{?}{=} H(m)$

$H(m)$ はメッセージのハッシュ値、 $s$ が署名です。「秘密の指数 $d$ で作った値を、公開の指数 $e$ で戻したらハッシュと一致するか」を確かめている、と読めます。ハッシュに署名するのは、長いメッセージでも署名が固定長で済むからであり、同時にハッシュが壊れると署名も壊れることを意味します。中身の違う2つの文書が同じハッシュ値を持てるなら、片方への署名がもう片方にもそのまま通ってしまうからです。

そして署名が保証しないことも押さえておきます。署名は「この公開鍵の持ち主が作った」ことしか言いません。その公開鍵が誰のものかは何も保証していないのです。この最後の穴を埋めるのが証明書と認証局（PKI）で、「この公開鍵は確かにexample.comのものだ」という主張に、信頼された第三者が署名を重ねる仕組みです。ブラウザの鍵アイコンはこの連鎖の検証結果を表示しています。

コードで触る（教育用・本番で使ってはいけません）

RSAの往復を、小さな数で実際に動かしてみます。

p, q = 61, 53                      # 本番では数百ビットの素数
n = p * q                          # 3233
phi = (p - 1) * (q - 1)            # 3120
e = 17                             # phi と互いに素
d = pow(e, -1, phi)                # 2753 = e の mod phi 逆元

m = 65
c = pow(m, e, n)                   # 2790  暗号化
print(pow(c, d, n))                # 65    復号

s = pow(m, d, n)                   # 署名（本来はハッシュ値に対して行う）
print(pow(s, e, n) == m)           # True  検証

pow(x, y, n) が「 $x^y \bmod n$ 」を効率的に計算する組み込み関数です。10行で往復しますが、これをそのまま本番に持ち込むと必ず破られます。実際のRSAはOAEPやPSSといったパディングを併用し、乱数を混ぜて同じ平文が毎回違う暗号文になるようにしています。上のコードは決定的なので、暗号文を見比べるだけで同じメッセージだと分かってしまいます。暗号は「式が合っていること」と「安全であること」の距離がとても遠い分野です。

危殆化の歴史 — 暗号は必ず古びる

暗号の実務でいちばん誤解されているのは、「安全な暗号を選べば終わり」という感覚です。実際には、広く使われた暗号は例外なく寿命を迎えてきました。

DES（1977年に米国標準）: 鍵が56ビットしかなく、1998年にEFFが作った専用ハードウェアが3日足らずで鍵を全数探索して見せました。設計が悪かったのではなく、鍵長が計算機の進歩に追い越されたのです。
MD5: 2004年に衝突を作る方法が公表され、2008年には偽の認証局証明書を作る実証に使われました。2012年のFlameというマルウェアは、MD5の衝突を利用してソフトウェア署名を偽造しています。
SHA-1: 2005年に理論的な弱点が示され、2017年には中身の違う2つのPDFが同じSHA-1値を持つ実例が公開されました（SHAttered）。2020年にはさらに強い形の衝突も実現しています。
RSAの鍵長: 分解記録が更新されるたびに推奨値が引き上げられてきました。

パターンは共通しています。「理論的な弱点の指摘」→「計算資源の低下で実用的な攻撃に」→「標準からの排除」。この移行に何年もかかるので、弱点が指摘された時点で移行を始めるのが正しい構えです。壊れてから動くのでは間に合いません。

そしていま進行中なのが量子計算機への備えです。1994年のショアのアルゴリズムは、十分な規模の量子計算機があれば素因数分解と離散対数を効率的に解けることを示しました。つまりRSAと楕円曲線暗号は原理的に破れる側です。一方、共通鍵暗号やハッシュへの影響は限定的で、理論上は強度が半分（ $2^n$ が $2^{n/2}$ ）になる程度とされます。AES-256が推奨されるのはこのためです。

置き換え先の標準化も進んでおり、米国NISTは2024年に格子暗号ベースの鍵交換・署名方式を連邦標準（ML-KEM、ML-DSA、SLH-DSA）として公表しました。実務で警戒すべきは「今のうちに暗号文を保存しておいて、量子計算機ができてから復号する」という攻撃で、長期間秘密であるべきデータほど移行を急ぐ理由になります。

なお、雑音から守る誤り訂正と暗号は、どちらも「壊れる前提で設計する」点は似ていますが、想定する相手が違います。誤り訂正の敵は確率的な雑音、暗号の敵はあなたの設計を読んだ上で最悪の入力を選んでくる知性です。平均的にうまくいく設計では足りません。

現場ではこう使う

誰が、いつ触るか。 Webアプリのバックエンド開発者はパスワード保存とセッション、トークン検証で。SREとインフラ担当は証明書の更新、鍵管理サービスの権限設計、TLS設定で。組込・IoTの開発者はファームウェア署名と、乱数源が貧弱な環境での鍵生成で。決済や医療のシステムを触る人は、保存データの暗号化と鍵ローテーションの監査で必ず出会います。

実際に触る名前。 共通鍵は AES-256-GCM か ChaCha20-Poly1305（暗号化と改ざん検知を同時に行うAEADと呼ばれる形式）。ライブラリは自前実装ではなく libsodium や各言語の標準暗号ライブラリ。パスワードは argon2id か bcrypt、コストパラメータ（メモリ量・反復回数）はハードウェアに合わせて調整します。証明書とTLSの設定確認は openssl s_client -connect host:443 と openssl x509 -text。鍵の保管は環境変数ではなく AWS KMS / Google Cloud KMS / HSM のようなキー管理サービスへ。メッセージ認証は自作せず HMAC-SHA256 を使います。

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

自作暗号: 暗号アルゴリズムを自分で設計・実装するのは、ほぼ確実に負けます。「動く」と「安全」は別物です。
ECBモード: ブロックごとに独立して暗号化するモードは、同じ平文ブロックが同じ暗号文になるため模様が透けます。既定値として選ばれていたら疑ってください。
nonce（初期化ベクトル）の再利用: 特にAES-GCMで同じ鍵と同じnonceを2回使うと、平文が漏れるだけでなく改ざん検知の鍵まで復元されます。カウンタか十分長い乱数で必ず一意にすること。
乱数源: random モジュールのような一般用途の乱数を鍵生成に使ってはいけません。secrets（Python）や crypto.randomBytes（Node.js）など暗号用のAPIを使います。過去には、乱数の質が落ちた実装から鍵が推測できた事故も、署名の乱数を使い回して秘密鍵が丸ごと復元された事故も起きています。
文字列比較のタイミング: トークンやMACの照合を == で行うと、一致した文字数によって処理時間が変わり、そこから正解を1文字ずつ絞り込まれます。hmac.compare_digest のような定数時間比較を使います。
ハッシュ(鍵 + メッセージ) を自作MACにする: SHA-2までのハッシュには長さ拡張攻撃という弱点があり、この形は破られます。HMACはまさにこれを防ぐ構成です。
鍵のハードコードとローテーション不在: リポジトリに入った鍵は履歴から消えません。鍵は交換できる設計にしておくこと。

面接や設計レビューで問われること。 「パスワードをSHA-256で保存してはいけない理由は？」——速すぎるからです。GPUで秒間に膨大な回数試せるため、遅くメモリを食うよう設計されたArgon2やbcryptを、利用者ごとに違うソルトと共に使います。「HTTPSはなぜ公開鍵と共通鍵を両方使うのか？」——公開鍵は遅いので鍵の共有だけに使い、本文は速い共通鍵で流すからです。「証明書の有効期限が切れると何が起きるのか？」——署名自体は数学的にはまだ正しいのに、検証側が信頼の連鎖を打ち切ります。暗号の失敗の多くは、数学ではなく運用で起きます。

まとめ

暗号は「解けない」を作るのではなく、鍵を知る側と知らない側の手間に指数的な差を作る技術
共通鍵は速いが事前共有が要る、公開鍵は事前共有が不要だが遅い。だから現実は両方を組み合わせる
公開鍵の安全性は「素因数分解や離散対数が難しい」という証明されていない仮定に乗っている
ハッシュは戻せないことが取り柄で、署名は「誰が作ったか」だけを保証する。「誰の鍵か」は証明書の仕事
使われた暗号はいずれ壊れる。移行できる設計にしておくことが、強い暗号を選ぶことと同じくらい重要

次はこの3つの道具が実際にどう組み合わさっているかを、HTTPSのハンドシェイクを1往復ずつ追いながら見ていきます。