The Mathematics of Cryptography
なぜパスワードは
破られるのか
——暗号の数学
量子コンピュータの脅威
私たちのパスワード、銀行の取引、メッセージ——現代のあらゆる「秘密」は、暗号という数学に守られています。では、なぜパスワードは破られてしまうのか? 暗号はどんな「数学的な難しさ」で情報を守っているのか? そして、その守りを根底から覆すかもしれない「量子コンピュータ」とは何なのか。情報を守る者と暴く者の、数千年にわたる知の攻防を解き明かします。
一瞬
短く単純なパスワードは、現代のコンピュータなら一瞬で総当たりされてしまう
素因数分解
現代暗号(RSA)の安全性の核心——「大きな数を素数に分解するのは難しい」という数学
Shor
量子コンピュータ用のショアのアルゴリズム——現代暗号を理論上「破れる」とされる脅威
そもそもパスワードは、どう保管されているのか
「パスワードが破られる」と聞くと、誰かがあなたのパスワードの文字列を盗み見るイメージかもしれません。でも実際には、まともなサービスはパスワードそのものを保存していません。もし保存していたら、その会社のデータが漏れた瞬間、全員のパスワードがバレてしまうからです。
代わりに使われるのが「ハッシュ関数」という数学の仕組みです。ハッシュ関数は、入力(パスワード)を、まったく異なる固定長の文字列(ハッシュ値)に変換します。重要なのは、これが「一方通行」であること——パスワードからハッシュ値は簡単に計算できるのに、ハッシュ値から元のパスワードを逆算するのは事実上不可能なのです。サービスはハッシュ値だけを保存し、ログイン時に入力されたパスワードを同じ方法でハッシュ化して、保存された値と一致するか確認します。
// ハッシュ関数——一方通行の変換
入力(パスワード)
password
→
ハッシュ関数
SHA-256
→
出力(ハッシュ値)
5e884898da...
→ の向きは簡単に計算できるが、← の逆算は事実上不可能(一方向性)。
たった1文字変えるだけで、ハッシュ値は全く別物になる(雪崩効果)。
たった1文字変えるだけで、ハッシュ値は全く別物になる(雪崩効果)。
# 一方向関数——暗号の心臓部
ハッシュ関数のような「一方向関数(one-way function)」は、暗号全体の基礎です。「計算するのは簡単、逆算するのは超困難」という非対称性こそが、情報を守る鍵。たとえるなら、ガラスのコップを床に落として割るのは一瞬でできるが、割れた破片を完璧に元のコップに戻すのは事実上不可能——そんな「やりやすい方向」と「やりにくい方向」の差を、数学的に作り出しているのです。この非対称性が崩れたとき、暗号は破られます。なぜパスワードは破られるのか——攻撃の数学
ハッシュ値からは逆算できないはずなのに、なぜパスワードは破られるのでしょうか。攻撃者は「逆算」ではなく、「正解を片っ端から試して、ハッシュ値が一致するものを探す」という力技を使います。以下は、攻撃の代表的な考え方です(あくまで仕組みの理解のために、概念として説明します)。
Brute Force / 総当たり攻撃
あらゆる組み合わせを片っ端から試す
考えられる全てのパスワードを順番に試す力技。短く単純なパスワードは、現代のコンピュータが毎秒膨大な回数を試せるため、あっという間に破られる。逆に、長く複雑なパスワードは「試すべき組み合わせ」が天文学的に増え、現実的な時間では破れなくなる。パスワードの「長さ」が安全性に直結する理由がこれ——文字数が増えるほど、組み合わせは指数関数的に爆発する。
Dictionary / 辞書攻撃
「よく使われるパスワード」から試す
人間が選ぶパスワードには強い偏りがある。「password」「123456」「qwerty」、人名、誕生日、辞書の単語——こうした「ありがちなパスワード」のリストを優先的に試す。総当たりより圧倒的に効率的。私たちが「覚えやすい」と思うパスワードほど、攻撃者にとっても「予測しやすい」。人間の心理の隙を突く攻撃。
Precomputation / 事前計算
あらかじめ計算結果を貯めておく
膨大なパスワードのハッシュ値をあらかじめ計算して表にしておき、漏れたハッシュ値と照合する手法(レインボーテーブル等)。これに対抗するため、現代では「ソルト(salt)」——各パスワードにランダムな文字列を加えてからハッシュ化する技術が使われる。ソルトがあると事前計算表が役に立たなくなり、攻撃コストが跳ね上がる。守る側の重要な工夫。
Leak & Reuse / 漏洩と使い回し
そもそも「暗号を破らない」最大の弱点
実は、最も多くの被害は暗号を「数学的に破る」ことでは起きない。あるサービスから漏れたパスワードを、別のサービスで試す——多くの人が同じパスワードを使い回しているため、これが恐ろしく有効。フィッシング(偽サイトで入力させる)や、安易なパスワード設定も同じ。最強の暗号も、人間の油断という「裏口」からは守れない。技術より運用が破られる。
# 「長さ」がすべてを決める——指数の力
パスワードの強さは、主に「長さ」で決まります。使える文字が仮に95種類だとすると、4文字なら約8100万通りですが、これはコンピュータには一瞬。ところが、これが12文字になると、組み合わせは約54垓(がい＝10の20乗)通りを超え、現実的な時間では総当たりできなくなります。1文字増えるごとに組み合わせは約95倍に膨れ上がる——この指数関数的な爆発が、長いパスフレーズを安全にする数学的な理由です。「複雑な記号」より「とにかく長いこと」が効くのは、このためです。情報を守る数学——2種類の暗号
パスワードのハッシュ化だけでなく、通信や保存データを守る「暗号化」にも数学が使われます。暗号には大きく2つの方式があります。
共通鍵暗号
Symmetric — 同じ鍵で施錠・解錠
暗号化と復号に「同じ鍵」を使う方式。速くて効率的だが、問題は「鍵をどう相手に安全に渡すか」。鍵を送る途中で盗まれたら終わり。古代から使われてきた基本形(シーザー暗号もこれの原始版)。現代ではAESという強力な方式が主流で、データの保存や高速な通信に広く使われている。
公開鍵暗号
Public-key — 鍵を2つに分ける革命
「公開鍵(誰でも見られる)」と「秘密鍵(自分だけ)」のペアを使う。公開鍵で施錠したものは、対応する秘密鍵でしか開けられない。これにより「鍵を安全に渡す」問題が解決した。インターネットの暗号通信(HTTPS)の根幹。RSAという方式が有名で、その安全性は「素因数分解の難しさ」に支えられている。
# RSAの秘密——「掛け算は簡単、割り算は地獄」
現代暗号の代表RSAの安全性は、驚くほどシンプルな数学的事実に基づいています——「2つの大きな素数を掛け算するのは簡単だが、その積を素因数分解する(元の2つの素数を求める)のは、とてつもなく難しい」。たとえば「61 × 53 = 3233」は簡単に計算できますが、逆に「3233を素因数分解せよ」と言われると、試行錯誤が必要です。これが何百桁もの巨大な数になると、現在のコンピュータをすべて使っても、宇宙の年齢より長い時間がかかる。この「掛け算と素因数分解の非対称性」が、あなたの通信を守っているのです。暗号とは、こうした「簡単な方向」と「困難な方向」の差を利用した数学の芸術なのです。量子コンピュータという脅威——守りが崩れる日
現代暗号の安全性は「素因数分解は時間がかかりすぎて無理」という前提に立っています。ところが、その前提を根底から覆しかねない技術が現れました——量子コンピュータです。
Quantum Bit / 量子ビット(キュービット)
「0でも1でもある」重ね合わせの計算
普通のコンピュータのビットは「0か1」のどちらか。だが量子ビット(キュービット)は、量子力学の「重ね合わせ」により「0と1の両方の状態を同時に持つ」ことができる。複数のキュービットを組み合わせると、膨大な可能性を「並行して」計算できる。これにより、特定の種類の問題——とりわけ素因数分解のような問題——を、桁違いに速く解ける可能性がある。普通のコンピュータが一つずつ試すところを、量子コンピュータはある意味「全部まとめて」扱える。
Shor's Algorithm / ショアのアルゴリズム(1994)
RSAを「破る」ための量子アルゴリズム
1994年、数学者ピーター・ショアが、十分に強力な量子コンピュータがあれば、巨大な数の素因数分解を現実的な時間で解けるアルゴリズムを考案した。これは、RSA暗号の安全性の前提(素因数分解は無理)を直接崩すことを意味する。つまり、大規模な量子コンピュータが完成すれば、現在インターネットを守っている公開鍵暗号の多くが、理論上は破られてしまう。幸い、ショアのアルゴリズムを実用的な規模で動かせる量子コンピュータはまだ存在しない。だが、その実現は「いつか」の問題だと多くの専門家が考えている。
Grover's Algorithm / グローバーのアルゴリズム
総当たりを「速く」する——でも、致命的ではない
もう一つの量子アルゴリズム、グローバーのアルゴリズムは、総当たり探索を高速化する。ただしショアほど劇的ではなく、探索の手間を「ルートを取る」程度に減らす(たとえば、効果としてはおおよそ鍵の長さが半分になるイメージ)。これに対しては、鍵の長さを倍にすれば対抗できるため、共通鍵暗号(AES等)への影響は限定的とされる。量子の脅威が特に深刻なのは、公開鍵暗号(RSA等)の方なのだ。
Post-Quantum Cryptography / 耐量子暗号
量子コンピュータでも破れない、新しい数学
守る側も手をこまねいてはいない。「量子コンピュータでも効率的には解けない」と考えられる数学的問題(格子問題など)に基づく、新しい暗号方式の研究が世界中で進んでいる。これを「耐量子暗号(ポスト量子暗号)」と呼ぶ。米国のNISTなどが標準化を進め、すでにいくつかの方式が選定されている。「量子コンピュータが完成する前に、新しい暗号への移行を終える」——これが現在進行中の、人類規模のセキュリティ競争だ。攻撃と防御の数学は、今もこうして進化を続けている。
# 「今盗んで、後で解読する」という脅威
量子コンピュータがまだ完成していなくても、危険は「すでに」始まっているという見方があります——「Harvest Now, Decrypt Later(今収穫し、後で解読する)」と呼ばれる脅威です。攻撃者が、今は解読できない暗号化された通信を「とりあえず大量に保存しておき」、将来量子コンピュータが完成したときに一気に解読する、という戦略。長期間秘密にすべき情報(国家機密、医療データなど)は、この観点から「今すぐ耐量子暗号への移行が必要」と議論されています。守る数学と破る数学の攻防は、未来を先取りして始まっているのです。自分の情報を守るために——実践的な防御
難しい数学の話をしてきましたが、私たち一人ひとりができる防御は、実はとてもシンプルです。そして、それが最も効果的です。
1
長いパスフレーズを使う
複雑な記号を少し混ぜるより、「とにかく長い」方が圧倒的に強い(指数の力)。覚えやすい複数の単語をつなげた「パスフレーズ」(例：意味のない単語を4つ並べる)は、長くて覚えやすく、総当たりに強い。短い複雑なパスワードより、長い覚えやすいフレーズを。
2
パスワードを使い回さない
最も多い被害は「漏洩したパスワードの使い回し」から起きる。サービスごとに違うパスワードを使えば、一つ漏れても被害が広がらない。すべてを覚えるのは無理なので——次の項目へ。
3
パスワードマネージャーを使う
サービスごとに長くてランダムなパスワードを自動生成・保存してくれるツール。あなたは「マスターパスワード」一つだけ覚えればいい。人間の弱点(覚えやすさを優先してしまう)を、技術で補う最も現実的な方法。
4
二段階認証(2FA)を有効にする
パスワードに加えて、スマホアプリのコードや生体認証など「2つ目の鍵」を要求する仕組み。たとえパスワードが漏れても、2つ目の認証がなければ突破されない。これを有効にするだけで、安全性が劇的に上がる。最も費用対効果の高い防御。
5
「裏口」に注意する——フィッシング対策
どんなに強い暗号も、あなた自身が偽サイトにパスワードを入力してしまえば無意味。メールのリンクを安易にクリックしない、URLを確認する、急かす連絡を疑う。暗号を破るより「人を騙す」方が簡単だと攻撃者は知っている。最後の砦は、あなたの注意深さ。
// Summary
- まともなサービスはパスワードそのものでなく「ハッシュ値」を保存する。ハッシュ関数は一方向(計算は簡単、逆算は不可能)——この非対称性が暗号の心臓部。1文字違うだけで結果が激変する(雪崩効果)
- パスワードが破られるのは「逆算」でなく「正解を片っ端から試す」力技から。総当たり・辞書攻撃(ありがちな語)・事前計算(ソルトで対抗)・漏洩したパスワードの使い回し。被害の多くは数学を破るより「人間の油断」を突く
- パスワードの強さは主に「長さ」で決まる——1文字増えるごとに組み合わせが指数関数的に爆発する。複雑な記号より「とにかく長いパスフレーズ」が数学的に強い
- 暗号には共通鍵(同じ鍵で施錠・解錠、速いが鍵の受け渡しが課題)と公開鍵(公開鍵で施錠・秘密鍵で解錠、HTTPSの根幹)がある。RSAの安全性は「掛け算は簡単、素因数分解は地獄」という非対称性に依存
- 量子コンピュータの脅威:量子ビットの重ね合わせで並行計算が可能。ショアのアルゴリズム(1994)は素因数分解を高速化しRSAを理論上破る。グローバーは総当たりを高速化(鍵を倍にすれば対抗可)。「今盗んで後で解読」の脅威も
- 守る側は「耐量子暗号(格子問題など量子でも解けない数学)」への移行を進行中。個人の防御は——長いパスフレーズ・使い回さない・パスワードマネージャー・二段階認証・フィッシング警戒。シンプルだが最も効果的
# この記事について
この記事は、暗号やセキュリティの「仕組み」を理解し、自分の情報を守るための教育的な解説です。攻撃手法は、なぜパスワードが破られるのか・どう守ればよいのかを理解するために、概念のレベルで紹介しています。他人のアカウントやシステムへの不正アクセスは、いかなる目的であれ法律で固く禁じられた犯罪です。ここで得た知識は、ぜひご自身と周囲の人々の情報を守るために役立ててください。
情報を守る数学と、それを破る数学。
この攻防は、古代の暗号から量子コンピュータまで、
何千年も続いてきた、人類の知の競争です。
その最前線で、あなたの秘密を守っているのは——
巨大な素数や、一方通行の関数たち。
そして最後の砦は、いつだって、
私たち自身の、ほんの少しの注意深さなのです。
この攻防は、古代の暗号から量子コンピュータまで、
何千年も続いてきた、人類の知の競争です。
その最前線で、あなたの秘密を守っているのは——
巨大な素数や、一方通行の関数たち。
そして最後の砦は、いつだって、
私たち自身の、ほんの少しの注意深さなのです。
