インターネットの利用とともに普及した技術の1つに公開鍵暗号がある。簡単にいうと、暗号化と復号（平文化）に異なるキーを使うことで、漏洩しないように解読キーを相手に送るという問題を解決したものだ。これを可能にしたのは、逆関数を求めるのにコストがかかり、現実問題としては計算ができないものを使うというアイディアだ。
いろいろなやり方があるが、初期に作られた方式の1つにRSA暗号がある。RSAは、素数同士の積（かけ算）は簡単に計算できるが、その積から元の素数を求めるのが難しいという原理を使う。2つの素数pとqをかけ算した結果をn（=p×q）とすると、pとqからnを計算するのは簡単だが、nからpまたはqを求めるには、3から順に割り算できるかどうかを1つ1つ調べる必要がある。素数の積nが256 bitで表現される数だとしたとき、スーパーコンピュータ富岳の計算速度44.1京回/秒（=44.1×10の16乗）の1000倍の速度で割り算を行っても単純計算で
√(2^256)÷(365×24×60×60×44.1E16×1000)≒2.447E10=245億年
という時間がかかってしまう。もちろん、多数の計算機を並列に動作させるなどして計算速度を上げることはできる。どうしても1年ぐらいでやりたいのなら富岳を245億台用意すればよい。しかし、悪の組織が世界征服のためとはいえ、1システムで1,300億円するといわれている富岳を大量に購入することは困難だし、技術者を誘拐してきて秘密基地でスーパーコンピュータを大量に製造するというのも難しそうだ。そう考えると、この問題は現実的には「解けない」と考えられる。巨大な悪の組織にも解読できないのだから、ご近所の悪い人が、あなたのプライバシーをのぞき見するために多大なコストを負担することはないと言えるだろう。
なお、素数がどれぐらいあるのかに関しては、人類はいまだに正確な答えを出していないが、10の25乗（83ビット程度）以下には、1.7×10の23乗個の素数があるらしいのでランダムに選んでも衝突の危険はそれほど心配しなくてよさそうだ。
RSA暗号
RSA暗号は、十分大きな2つの素数pとqを用意して、これを元に計算を行い、「秘密鍵」と「公開鍵」を作る。RSA暗号では、送信者は、受信者の公開鍵を使って暗号文を作る。これを解読できるのは秘密鍵だけだ。公開鍵は、その名前の通り、インターネットなどで公開してもかまわない。公開鍵で作られた暗号を解読できるのは、前述の通り事実上、秘密鍵だけだ。
RSA暗号の公開鍵は、2つの数値からなる。これらは計算式では、eとnと呼ばれる。秘密鍵はdだが、平文化するときに公開鍵のnを使う。nは、pとqの積（かけ算。つまりn=p×q）である。pとqが十分大きいとき、nからpとqを求めることは事実上できない。具体的に公開鍵と秘密鍵を求めるには、ちょっと面倒な計算を行う。計算を簡単にするため小さな素数、17と13をpとqとして使うことにしよう。eとdを求めるには、pとqから計算できるφ(n)関数（オイラーのφ関数と呼ばれる。nと互いに素であるn以下の整数を求める）を使う。φ(n)は、その定義から素数の積n=p×qの場合(p-1)×(q-1)となるため、φ(n)=φ(17×13)=(17-1）×(13-1)=192となる。eは、この192と互いに素（1以外の公約数を持たない）になる192以下の整数を選ぶ。ここでは29とした。dは、以下の式が1になるようなものを選ぶ。ここで“mod”は余剰演算で x mod yはxをyで割ったときの余りである。
d×e mod φ(n)=d×29 mod 192
この条件ではdは53になる。この状態で秘密鍵dと公開鍵eには数学的に関係があるが、eからdを求めるには、φを計算する必要があり、そのためにはpとqが必要になる。しかし、前述のように大きなpとqを使えば、nからpとqを求めることは事実上できない。
こうして秘密鍵、公開鍵ができたら次は暗号化だ。暗号化は、公開鍵、eとnを使い、以下の値を計算する
暗号文字=原文文字^e mod n
※^はべき乗演算子
こうやって、原文に含まれる文字を次々と計算していけばよい。復号するには、
平文文字=暗号文字^d mod n
とするだけだ。計算式としては簡単なのだが、指数になるeが29、dが53なので、途中の値が膨大に大きくなる。これを普通に計算するとすぐに有効数字が溢れてしまう。
しかし、剰余計算には、普通の計算にはない特徴がある。べき乗を分解して剰余計算することができるため、途中の桁数を抑えることができるのだ。具体的には、
a^b mod n = ((a×a mod n) × a^(b-2)) mod n
とべき乗を分解してmod nを計算し、これを繰り返せばよい。mod nの結果は常に0～nの間に収まるので、途中で桁数が大きくなりすぎることはない。
というわけで、これをExcelで試してみる（写真01）。実際に作成したワークシートが以下のものだ。
これを開いて、p、qに適当な素数を入れる。ただし、あまり大きなものを入れてしまうと、計算ができない。このワークシートでは、dとeは200以下になることを想定している。もっとも、Excelは最大で100万行まで使えるので、表の最下行を選んでフィルハンドルでコピーしていけば、いくらでも増やせる。
-
写真01: ExcelでRSA公開鍵暗号を試してみた。左の表で白地のセルに適当なパラメーターを設定すると、グレー部分が自動で計算される。そのあと文字欄（F3セル）にASCII文字を入れると右側のセルで公開鍵による暗号化と秘密鍵による平文化の計算が行われる
暗号化や複合のべき乗計算は、繰り返しを使わず、表を作って求めている。効率のいい方法ではないが、マクロを使わずに結果を得られる（ソルバーを使う方法もあるがアドインの組み込みが必要）。前述の制限はこの表の大きさによるものだ。pとqの初期値11と13では、nが143になるので、7bitASCIIコードであれば、暗号化が可能になる。pとqに小さな値（3と11など）を入れてしまうと、nが小さくなり、暗号化できる範囲が狭くなるので注意されたい。上の「文字」欄にASCII文字を入れると暗号化と平文化を同時に行う。eには適当な数（pやqと同じ値は避ける）を入れる。eの値によっては、dが同じ値になってしまうこともある（これだと計算上は正しいが秘密鍵が秘密にならない）。また、eを小さくしすぎると、dが200を越えてしまうことがある。
今回のタイトル元ネタの1つは2001年の映画「暗号機エニグマへの挑戦」（原題Enigma）である。同名の原作本（ロバート・ハリス。新潮文庫。）は、史実を下敷きとするもフィクションとして書かれたもの。これに対して、映画「イミテーションゲーム」(2014年）は、アラン・チューリングの評伝「エニグマ アラン・チューリング伝」（勁草書房。原題Alan Turing: The Enigma）をベースにしたもの。映画を両方見たら記憶が混同してしまった。アラン・チューリングの評伝には、チューリングのお母さんが書いたAlan Turing（邦題アラン・チューリング伝。講談社。絶版）という本もある。これらに登場するイギリス、ブレッチリー・パークには、現在National MUSEUM of Computingがおかれている。エニグマ（写真02）解読のために作られたBomb、そして同じ目的で作られた電子計算機Colossusなどが展示してある。
-
写真02: エニグマ。写真奥に見える3つの金属版が「ローター」、手前のキーを押すと暗号化が行われ、文字のランプが点灯する。そのときローターが動き、1文字ごとにキーと文字の対応を変える。ローターは3枚しか装着できないが何種類もあったようだ
