パンの木を植えて

数学の話をしたり,しなかったりする日記

暗号理論 - Cryptography -

\[ %%% 黒板太字 %%% \newcommand{\A}{\mathbb{A}} %アフィン空間 \newcommand{\C}{\mathbb{C}} %複素数 \newcommand{\F}{\mathbb{F}} %有限体 \newcommand{\N}{\mathbb{N}} %自然数 \newcommand{\Q}{\mathbb{Q}} %有理数 \newcommand{\R}{\mathbb{R}} %実数 \newcommand{\Z}{\mathbb{Z}} %整数 %%% 2項演算 %%% \newcommand{\f}[2]{ \frac{#1}{#2} } \]

前提知識

graph TB S[START] --> A[線形代数] & B[微積] & E(離散最適化) A --> F[群論] B[微積] --> G E --> G F --> G[初等整数論] --> H[暗号理論]

初等整数論を知っていることが必要です.暗号のアルゴリズムは,整数論的な事実に基づいて作られています.その計算時間の解析をするにしても,安全性について考えるにしても,整数論の知識が必要になります.

暗号理論といっても様々なものがあり,RSA暗号やラビンミラー判定法は初等整数論の知識だけで理解できますが,楕円曲線暗号を理解しようとすると楕円曲線の知識を要します.したがって,ここでは楕円曲線暗号等の高度な内容は除外して考えています.


概要

盗聴の可能性があるルートを介して,秘密にしなければならない情報を送るにはどうしたらいいのか?という問題などを扱う分野です.

電子署名などにも使うので,コミュニケーションだけが問題とされているわけではありませんが.


sequenceDiagram participant A as アリス participant B as ボブ A->> B : 秘密のメッセージ B-->> A : 秘密の返答

郵便にたとえましょう.

相手に送りたいメッセージを秘密にするためには,容器に鍵をかけることを思いつきます.

そうすれば郵便を盗んだひとがいたとしても,鍵がかかっているから秘密は漏れません.

しかし,相手に合鍵を渡さなければ相手にも伝わりません.

そこで合鍵を相手に渡したいのですが,それも敵に盗まれる可能性があります!

これでは堂々巡りですね.まさか鍵に鍵をかけて送るわけにもいきませんし.

これを鍵の配送問題といいます.


どうしようもない問題のように見えますが,これを数学的なテクニックで解決することができます.

シンプルな解決策としてDiffie-Hellmanの鍵交換アルゴリズムを使うというのがあります.

これを使えば,相手とだけこっそり秘密鍵を共有することができます.

秘密鍵が共有できれば,それを鍵にしてメッセージを暗号化し,相手にだけこっそりメッセージを伝えることができます.


もう一つの方法があって,それは公開鍵暗号を使う方法です.

公開鍵暗号というのは,暗号化するための鍵と,暗号をもとに戻すための鍵が異なっているような暗号のことです.

「暗号化するための鍵」は秘密にしなくても構わないので,公開鍵暗号という名があります.


最も有名なのはRSA暗号でしょう.RSA暗号は,最初に考案された公開鍵暗号としてとても重要です.

大きな素数 $p,q$ を掛け合わせて整数 $n = pq$ を得るのは容易ですが,大きな整数 $n$ が与えられたときにその素因数分解を求めるのは難しいということに基づいています.


文献

Rosulek『The Joy of Cryptography』

無償で公開されている教科書です.数学の本というより,暗号理論の本ですね.特色として,数学系のひとが書いた本にはない「暗号の安全性を定義し,証明する」という視点があります.

ところで,この著者は語り口が独特で,結構毒舌です.ブラックジョークが好きなのだと思います.たとえば,こんな文章が書かれていました.

never ever write $(x^ a)(x^ b) = x^ {ab}$. If you write this, your cryptography instructor will realize that life is too short, immediately resign from teaching, and join a traveling curcus.

p.1

こういうブラックジョークを本に書くのはいかがなものかと思いますが….

Silverman, Hoffstein, Pipher『An Introduction to Mathematical Cryptography』

Springerから.『はじめての数論』の著者が共著者に入っていますね.Mathematical とタイトルにある通り,かなり数学っぽい本です.

self-contained であると書かれていますが,ミラーラビン法の正当性の証明は省かれています.参照目的で読む人は注意してください.

Rubinstein-Salzedo 『Cryptography』

暗号理論の本の皮をかぶった数学の本(と著者自身が言っています).『An Introduction to Mathematical Cryptography』との違いは微妙なのですが,最後に Coding Theory (符号理論) の話を入れているところは違いといえます.また,この本の方が暗号理論の歴史を丁寧に追っている感じがします.