これはコナン・ドイルの小説『踊る人形』(1903)の中で出てくる暗号文です
換字式暗号の一種で、英語では「E」の文字が使用頻度が高いことから、最初の暗号から一番多い絵文字が「E」であることと推測、また旗が単語の区切りと推測して解読していきます
（頻度の順は概ね E, T, A, O, I, N, ……, J, X, Q, Z、3文字の場合では t-h-e, a-n-d, i-n-g, i-o-n, ……）

暗号の歴史

暗号の歴史は古く、紀元前19世紀の古代エジプトまで遡ることができます
標準のヒエログリフ以外の文字を混ぜて書いたものでその文字を知らない人には理解できないものでした

また紀元前5世紀にはスパルタでスキュタレー暗号が使われています
これは棒に革ひもを巻きつけるとある行に意味のある文字列が現れるという形の暗号でした
棒の太さが合わなければ解けないというのも面白いところです

紀元前1世紀には有名なシーザー暗号が登場しましたこれは元のアルファベットから同じ数だけずらして暗号文を作るというものでした復号化には逆方向にずらせばいいというものでした

例えば
　$${\Large \mathrm {Bj\ bnqq\ mfaj\ f\ gfwgjhzj\ ufwyd\ sjcy\ bjjpjsi.}}$$
という暗号文は、アルファベットを5つ戻せばもとの文（平文）に戻ります

ということで、もとの文は
　$${\Large \mathrm {We\ will\ have\ a\ barbecue\ party\ next\ weekend.}}$$

こうした換字式暗号は9世紀頃にはアラビア人によって、頻度分析という手法によって解析されました
ただ、ヨーロッパでは長い間安全な暗号として使われていました
ヨーロッパに頻度分析の手法が確立したのはルネサンスの影響を受けた15世紀になってからです

無線の時代になって大活躍をしたのが、ドイツの発明家シェルビウスが発明し、ドイツ軍が採用した暗号機械エニグマです
換字式暗号の一種でしたが、複雑な機械構成で解読するための鍵が膨大な数になり、なかなか解読ができませんでした
解読は不可能かと思われましたが、イギリスの数学者・暗号解読者のアラン・チューリングたちによって解読されることになります
初めは手作業でしたが、やがて機械化されて、戦争終了後にはコンピュータの発明にも影響していきます

鍵配送問題と公開鍵暗号

暗号通信をするには受け取る相手にも共通鍵も持っていなければならず、その鍵を暗号化して送らなければ第三者にも知られてしまうというジレンマが発生します
これを解決する公開鍵暗号の理論が1976年に発表され、具体的な公開鍵暗号として有名なRSA暗号はその翌年の1977年に発表されました
名前の由来は発明者である Ronald Linn Rivest（リベスト）、Adi Shamir（シャミア）、Leonard Max Adleman（エーデルマン） の3人に名前の頭文字によるものです

RSA暗号にチャレンジ

まず、メッセージ（暗号）を受けとる側として公開鍵と秘密鍵を準備します
選ばれた秘密鍵 $${p,\ q}$$ から公開鍵 $${n,\ e}$$ をつくり、それを全世界に公開します
$${p,\ q}$$ は共に素数を選び、 $${n=pq}$$ であり、$${e}$$ は $${(p-1)(q-1)}$$ と互いに素であれば何でも可です

メッセージを送信する人は公開鍵 $${n,\ e}$$を受信し、それをもとにメッセージを暗号化して、それを全世界に公開します
平文を $${x}$$、暗号文を $${y}$$ とすると $${y\equiv x^e\pmod n}$$ で暗号化できます

暗号を受け取った人は、$${n}$$ と別につくっておいた秘密鍵 $${d}$$ を使って暗号を解き、メッセージを受け取ります
$${d}$$ については $${ed\equiv 1\pmod {(p-1)(q-1)\ }}$$ となるものがあるので探して下さい
　定理　$${a}$$ と $${b}$$ が互いに素なとき $${ax\equiv 1\pmod b}$$
　　　　なる $${x}$$ が $${1 \le x \le b-1}$$ の間ではただ1つ存在する
より $${d}$$ の存在は保証されます
$${x\equiv y^d\pmod n}$$ で復号化できます

例
2つの素数として $${p=97,\ q=103}$$ (秘密鍵)を選んでおきます
$${n=pq=9991}$$ (公開鍵)です
次に $${(p-1)(q-1)=96 \times 102=9792}$$ と互いに素な数として $${e=7}$$ (公開鍵)を選んでみます
また、$${7d \equiv 1 \pmod {9792}}$$ となる $${d}$$ を探すと $${d=1399}$$ （秘密鍵）が見つかります

次はメッセージ（暗号）を送信する側の作業です
まず、受信者側から公開鍵 $${n=9991,\ e=7}$$ を受け取ります
次に送りたいメッセージを自然数 $${x}$$ に変換しておきます
『ぴよ』と送ろうと思うので $${x=6674}$$ とします
$${x^e}$$ を $${n}$$ で割った余り $${y}$$ を受信者に送ります

$${6674^{7} \equiv 3243 \pmod {9991}}$$なので、暗号文 $${y=3243}$$ を受信者に送ります

受け取った受信者の作業です
$${y^d}$$ を $${n}$$ で割った余りが平文 $${x}$$ になります

$${3243^{1399} \equiv 6674 \pmod {9991}}$$ なのでメッセージ数は $${x=6674}$$ 、メッセージは『ぴよ』でした
無事に相手に伝わりました



実際のRSA暗号では $${n=pq}$$ が素因数分解されてしまうと暗号が解かれてしまうので、$${p,\ q}$$ はとても大きな素数（300〜400桁程度）を選んでいて、容易に素因数分解されないようにしています
これは2つの数をかけるのは簡単だけど、素因数分解は手強いといった性質に基づいています
まるで入りのは簡単な部屋だけど、脱出するのが困難な罠みたいなものですね
こういう性質のものを「落とし戸付き一方向性関数」といいます
「落とし戸付き一方向性関数」とは，平たく言えば一方通行の関数のことです
関数には，変換することは容易だが，元に戻すことが極めて困難なものがあります
そうした関数の中で，あるヒント（落とし戸）を使えば容易に元に戻せるような関数を「落とし戸付き一方向性関数」と呼ぶのです
この場合では $${p}$$ または $${q}$$ が漏れてしまうと大変なことになりますね

E-mailでは基本的に平文で送受信していたので、傍受するのは容易です
これを防ぐためにRSA暗号技術を利用したPGPといった暗号化技術もあります
インターネットショッピングでのクレジットカード情報などの個人情報は当たり前のようにこの技術を使って守られています

最近では、量子力学の性質を利用した量子暗号という新しい暗号システムも考え出されています

PPAPとかは絶対にしないでくださいね