『現代暗号入門』神永正博

もともと暗号は、軍事的な通信を秘匿するために作られました。長い間、私たちの生活とは無縁なものでしたが、今や暗号なしに生活するのは困難です。インターネットショッピングや携帯電話、Wi-Fi、ICカードはもちろん、ビットコインを始めとする暗号通貨も暗号技術でできています。現代的な暗号の基本要素は、共通鍵暗号、ハッシュ関数、公開鍵暗号の3つです。これらを組み合わせて、様々なシステムを構築する仕組みになっています。本記事では、これらの役割と利用法について解説していきます。

目次

暗号の起源

1. シーザー暗号

いきなりですが、あなたは今戦場にいるとしましょう。敵に知られずに、指令室から前線の部隊に指令を送る場合、どんな手段を使えばよいでしょうか。基本的に、指令には無線通信が使われます。しかし、電波が届く範囲が広いため、敵も無線通信を傍受、つまり盗聴することができます。したがって、無線の場合は、盗聴されることを前提に通信を行う必要があります。そのためには、通信内容を暗号化するしかありません。歴史上最もシンプルな暗号化は、古代ローマの軍事指導者ジュリアス・シーザーが用いたと言われるシーザー暗号です。

シーザー暗号では、アルファベットを決まった数だけ巡回的にずらすことによって暗号化します。例えば3文字右にずらすのであれば、AはDに、FはIに、ZはCに対応します。言うまでもなく、この暗号は現代では使い物になりません。なぜなら、アルファベットのずらし方が、わずか25通しかないからです。これでは、計算機を使えば一瞬で終わってしまいます。

2. 単換(たんかえ)字(じ)暗号

そこで、アルファベットをランダムに対応付けた暗号が、単換字暗号です。アルファベット26文字の並べ方は、全部で26の階乗、すなわち、4 × 1026通りにも及びます。これにより、シーザー暗号と比較すれば、鍵の総数は劇的に増加しました。この暗号は、シーザーの時代から約1000年にわたり、最強の暗号として君臨しました。しかし、この鉄壁の暗号技術もあえなく崩れ去ります。

アルファベットは、全て均等に現れるわけではありません。例えば、最も出現頻度が高いアルファベットは「e」です。そのため、暗号文で最も出現頻度の高いアルファベットが「y」であれば、それに対応する文字は「e」と考えられます。次に高い頻度で出てくるのは、「t」と「a」のどちらかである確率が高く、逆にめったに出てこないアルファベットはj、q、x、zのどれかになります。この要領で、じわじわと候補を絞っていきます。当初はでたらめなアルファベットの羅列にしか見えない暗号文に、頻度の高いものと低いものから順次当てはめて文章を虫食い状態にしていきます。さらに、実際の単語や熟語との対比を取りながら解読を進めていくのです。頻度を調べることで対応表のパターンは劇的に減り、ついに元の文章が現れます。この攻撃法を頻度分析といいます。つまり、偏りが見つけられれば、それを手がかりに暗号を解読できるということです。

3. 3種の神器

暗号システムを構成する最も基本的な道具は、「共通鍵暗号」「公開鍵暗号」「ハッシュ関数」の3つです。現在使われているほとんどの暗号システムは、この3つの部品だけでできており、3種の神器と呼ばれています。

共通鍵暗号は、閉める鍵と開ける鍵が同じ暗号です。身近なものに例えるのであれば、家の鍵を想像すればわかりやすいです。家の鍵は1つであり、閉める鍵と開ける鍵は同じものです。2つ目の公開鍵暗号は非対称鍵暗号とも呼ばれ、閉める鍵と開ける鍵が異なる暗号のことをいいます。3つ目のハッシュ関数は、任意の長さのデータを一定の長さのデータに変換する関数です。ハッシュ関数は、元のデータが改ざんされていないかどうかを検証するために利用されます。次項からは、これらについて解説していきます。

共通鍵暗号

1. バーナム暗号

バーナム暗号は、第一次世界大戦中にギルバート・バーナムによって考案されました。バーナム暗号は、少なくとも理論上は安全であることが証明されています。最もシンプルかつ重要な暗号で、現代の暗号に通用するエッセンスが多数含まれています。現代の暗号は、平文も暗号文も0と1で表現することを前提に作られています。コンピュータは0と1しか扱うことができないためです。コンピュータで文字を表現する方式はたくさんありますが、例えばアルファベットのZを1111010と表したとします。0と1でできたデータを処理する際には、0と1の間の演算（足し算や掛け算など）が必要になります。バーナム暗号では特に、排他的(はいたてき)論理和(ろんりわ)が使われます。排他的論理和とは次のようなものです。

1 +1 = 0
1 +0 = 1
0 +0 = 0

2つの値が同じ時、排他的論理和は0になり、異なる値の時は1になります。例えば、ノック式のボールペンを想像するとわかりやすいです。ノック式ボールペンは、スイッチを押すと引っ込み、もう一度押すと元に戻る仕組みになっています。スイッチを押す操作を+1と考えれば、1 +1 = 0になります。これが排他的論理和のイメージです。これを用いると、平文（元の文）と秘密鍵を演算することで、暗号文を作ることができます。また、暗号文をもとの平文に戻す際は、暗号文と秘密鍵をもう一度排他的論理和すればいいのです。ノック式ボールペンのように、同じ秘密鍵で2回演算すれば、最も通りの平文になるからです。バーナム番号は、鍵に規則性がないという条件のもとであれば、絶対に破ることはできません。

ただし、弱点もあります。バーナム暗号では、暗号化送信するたびに同じ長さの鍵が必要になります。つまり、鍵が使えるのは1回きりであり、次の送信では別の鍵に変えなければなりません。一度送信した内容から、平文と暗号文の両方がわかれば、秘密鍵を割り出すことができてしまうからです。

2. IC乗車券、携帯電話SIMについて

日本では2001年11月から、Suicaが首都圏で使われるようになりました。その後急速に普及し、キヨスクやコンビニ、コインロッカーなどでIC乗車券による支払いができるようになりました。ICカードとSIMチップは、見た目は異なりますが、本体はどちらも金属部分の下にある5ミリ角のICチップです。Suicaを始めとするIC乗車券は、ソニーが開発したFeliCaと言う非接触式ICカードの通信方式を採用しています。ICカード乗車券自体は、内部に電源を持ちません。代わりに、ICカードにはコイルが内蔵されており、改札機から発信される電波によって電力が生じます。つまり、改札機がICカードに電力を供給しているのです。FeliCaは電磁誘導によって発電を行い、その電力で通信と暗号処理を行います。改札機は所定の長さの乱数を発生させ、電波でICカードにその乱数を送信します。それに対し、ICカードが保持している秘密鍵を使って、改札機から受け取った乱数を暗号化し、改札機に送信します。改札機は、改札機が保持する秘密鍵を用いて、先程の乱数を暗号化します。その乱数とIC乗車券より送信された暗号化された乱数が同一であれば、ICカードに格納されている秘密鍵と改札機で持っている秘密鍵が同一であると認識されます。これをチャレンジレスポンス認証といいます。これらの処理を、改札を通る間ほぼ0.5秒の間に行います。

ハッシュ関数

ハッシュ関数とは、データを混ぜあわせて一定の長さのデータを作り出す関数です。出力されるデータをハッシュ値と言います。ハッシュとは、もともと「切り刻んで混ぜる」という意味です。ハッシュドポテトやハッシュドビーフのハッシュも同じ意味です。実際、ハッシュ関数は、データを切り刻んで混ぜる処理から構成されています。

ハッシュ関数の特徴は、データの改ざんが検出できることです。データをほんの少しか改ざんしても、ハッシュ値が大きく変化するため、改ざんされていることがすぐにわかります。また、ハッシュ関数は逆にたどれないように作られています。ハッシュ値を見て、もとのデータがわかると、暗号として成り立たないからです。この性質を、一方向性といいます。ハッシュ値を計算するのは簡単なのに対して、元に戻すのは難しいということです。ハッシュ関数は、シュレッダーのようなものだとイメージしてください。シュレッダーに文書を放り込んで細くするのは簡単ですが、出てきた紙片を元の文書に戻すのは困難です。さらに、ハッシュ関数の目的は改ざんの検出にあるため、異なるデータに対して同じハッシュ値が出力（衝突）されてしまうと困ります。簡単に衝突が起きるということは、データを改ざんするのも簡単と言うことです。そこで、衝突困難性が重要になります。

公開鍵暗号

1. 公開鍵暗号とは

公開鍵暗号とは、閉める鍵と開ける鍵が異なる暗号のことをいいます。公開鍵と秘密鍵の間には数学的な関係式があり、原理的には公開鍵から秘密鍵を計算することができます。しかし、公開鍵から秘密鍵を知るのに膨大な時間（例えば数万年）かかるとすればどうでしょう。実質的に不可能だといえます。これが、計算量的安全性と呼ばれる性質です。一般に、計算量が多いというのは困った問題です。しかしこれを逆手にとり、安全性につなげて考えたことは公開鍵暗号の斬新なところです。

公開鍵暗号を構成するためには、一方向性関数が必要となります。一方向性関数は、順方向の計算が容易になるのに対して、逆方向が計算量的に困難な関数です。最もわかりやすい例が、掛け算関数です。掛け算は簡単ですが、逆の因数分解が難しいと言うものです。 6 = 2 × 3くらいなら問題ありませんが、例えば、4056203を因数分解せよ、と言われたらどうでしょう。答えは1061× 3823ですが、暗算でできる人はほとんどいないでしょう。さらに大きな数となると、掛け算は簡単でも、因数分解は劇的に難しくなります。これを用いたのが、公開鍵暗号です。

2. マイナンバーカードについて

2015年10月から、行政機関が国民一人一人に固有の12 桁の番号を割り振り、社会保障や税に関する共通番号として個人を識別する仕組みが日本で実施されました。これがマイナンバー制度です。年金記録を調べる場合、雇用保険、医療保険やその他の福祉、確定申告などの税金の手続きでは、行政へ提出する書類にマイナンバー記載の義務が生じます。また、民間企業の源泉徴収や社会保険を扱う部署でも、マイナンバーを扱うことになりました。そうした業務を行う者には重い責任が伴います。預かったマイナンバーを漏らすと、「4年以下の懲役若しくは200万円以下の罰金」が科せられるのです。

2016年から、国民なら希望すれば誰にでもマイナンバーカードが交付されています。その中身は、あなたの秘密鍵が格納された暗号装置です。マイナンバーカードは IC カードです。IC カードは小型のコンピュータとも言え、その中核となる役割は暗号処理です。簡単に言えば、マイナンバーカードは電子署名装置です。そのため、カードさえあれば電子署名ができるのでなりすましができ、あなたの個人情報を自由に取り出せる可能性があります。券面には、12桁のマイナンバーと氏名、住所、生年月日、性別が書かれています。そして、IC カード内部には、個人に対応した 秘密鍵が格納されています。

利用者が、IC カードリーダにマイナンバーカードをセットすると、地方公共団体情報システム機構の利用者証明用電子証明書サーバに、認証のリクエストがなされます。サーバは乱数をネットワーク経由でマイナンバーカードに送信し、マイナンバーカードは内部の秘密鍵を使って電子署名を作成し、サーバに送り返します。サーバはこの電子署名に対応する公開鍵を公開鍵簿から探してこれを復号し、もとの乱数に戻っているかどうかを確認します。元に戻っていれば秘密鍵は登録された正当性を持つ公開鍵と対応していることになり、その正当性が認証されます。

この方式は、サーバ側には秘密鍵がないため、IC 乗車券などで用いられている共通鍵暗号によるチャレンジレスポンス認証よりも安全性が高いと言われています。サーバが攻撃され、公開鍵の情報が流出したとしても、利用者の秘密鍵を知ることはできません。しかし、マイナンバーカード自体を盗み出し、パスワードを推定できれば、なりすましはできてしまいます。カードの所持には十分注意が必要です。

ビットコインとブロックチェーン

1. ビットコインのメリット

暗号通貨ビットコインは画期的な発明と言われています。ビットコインとは、私たちが普段使っている100円玉や1000円札のような「お金」ではなく、価値の所有権を移動させる仕組み全体を指します。その本体は、ウェブ上の巨大な取引台帳です。この取引台帳はブロックチェーンと呼ばれ、世界中のビットコイン取引が全て記録されています。参加者は平等に通信しあうことができ、このようなネットワークは、ピア・ツー・ピア（P2P）ネットワークと呼ばれます。また、ネットワークにつながっているコンピュータはノードと呼ばれます。たとえば、「AさんからBさんに1ビットコイン（BTC）渡すという取引を考えます。このとき、A さんがBさんに支払ったということを証明するには、電子署名を使います。署名は A さんの公開鍵を使うことで容易に検証でき、さらになりすましや改竄、否認を防ぐことができます。

• (1) A さんの秘密鍵を持っていなければ、Aさんになりすましてビットコインの取引をすることはできない（なりすまし防止）。
• (2) 第三者が金額などの取引内容を書き換えることもできない（改竄防止）。
• (3) Aさんが署名している以上、A さんは支払っていないということはできない（否認防止）。

2. ビットコインの仕組み

一方、電子署名だけでは重要な問題が解決できません。それは、二重支払い（一度送ったコインを別の誰かに送ること）の問題です。ビットコインには物理的な実体はありません。そのため、電子メールを複数の人にコピーして送るのと同じようにビットコインを複数の人に送ることができてしまいます。ビットコインでは、この問題を巧妙な方法で解決します。AさんがBさんに送金する場合、A さんは取引内容（トランザクション）に自分自身の電子署名をつけてビットコイン・ネットワークに流します。Bさんに直接送らない点が重要です。

ビットコイン（Bitcoin／BTC）というシステムは、このような署名付きの全世界のビットコイン取引データを（約）10分間ごとに1つのブロックにまとめます。この時点では、このブロックはまだ正式な取引として承認されていません。正式な取引と認めるため難しいパズルを解く仕事を課すことを「プルーフ・オブ・ワーク」（Proof of Work =仕事の証明）といいます。ブロックを承認するには、ハッシュ値の先頭に決まった数以上の0が並ぶようなナンスと呼ばれる数字を探す必要があります。これが「難しいパズル」です。ナンスを探すのはビットコイン・ネットワークの参加者です。ナンスを探すことをマイニング（採掘）、マイニングする人やコンピュータをマイナー（採掘者）といいます。マイナーは、前のブロックのハッシュ値と 10分間の取引データに「ナンス」という数字をつけてハッシュ関数に通します。ハッシュ関数では、入力を少しでも変えるとハッシュ値はがらりと変わります。ナンスが変わればハッシュ値も大きく変わります。そのようなナンスの中でハッシュ値の先頭に決まった数以上の0が並ぶものを探すには、手あたり次第にナンスを変えてハッシュ値を計算しなければならなりません。マイナーはナンスを変えてハッシュ値を計算するという操作を膨大な回数繰り返し、0の並ぶナンスを見つけ出すのです。これは途方もない仕事となります。たとえば、先頭に 0 が 18個並んでいる場合、16進数表示なので、1つのゼロは二進数の 0000に相当します。つまり、二進数で書いたとき、先頭に並んでいる 0の個数は 18×4=72個です。このようなハッシュ値を得るには平均して2の72乗回（4722366482869645213696回）ものハッシュ計算が必要になります。

ビットコインのシステムは世界中のマイナーたちが片っ端からナンスを変えてハッシュ値を計算すると平均10分程度で条件を満たすハッシュが見つかるようにゼロの個数を調整しています。計算能力が上がったら、その分ゼロの個数を増やして問題を難しくするのです。条件を満たすナンスを見つけたノードは、このナンスを含むトランザクションをビットコイン・ネットワークに流します。これを受け取った各ノードは、ハッシュ値が条件を満たすことを確認します。確認はハッシュを1回計算するだけだからすぐにできます。ネットワークの全てのノードが、これが正しいトランザクションと認めたらそのブロックは正当なものとなり、タイムスタンプが押されて直前のブロックの後ろに接続されます。このように台帳はブロックが鎖のようにつながった構造を持つので、ブロックチェーンと呼ばれます。

3. ビットコインの運用

ナンスを見つけるのは大変な作業なので報酬が支払われます。正しいナンスを見つけたノードには報酬としてビットコインが支払われます（2017年時点では 12.5BTC）。この報酬は、ビットコインのシステムが何もないところから作るものなので、ビットコインは平均して 10 分で 12.5 ビットコインのインフレ状態にあります。マイナーはこの報酬を求めてマイニングを行います。実際には個人のPCでマイニングを行っても成功する可能性はほとんどなく、専用のマイニングマシンが使われています。プルーフ・オブ・ワークの仕組みの何が巧妙かを理解するには、アタッカーがブロックチェーンの取引記録を改ざんしようとしたときを考えればわかります。アタッカーは、取引記録を自分に都合のいいように書き換えたいが、取引記録を書き換えるとハッシュ値も変わってしまいます。ハッシュ関数の説明で見たように、取引記録をちょっとでも書き換えるとハッシュ値はめちゃめちゃに変わってしまうので、改竄した取引記録を正当なものに見せかけるには、再びマイニングを行わなければなりません。前述の通り、これは世界中のマイナーの途方もないハッシュ計算力で10分もかかる大仕事です。不正をはたらくには、この作業を自力でやらなければなりません。成功するには平均して世界中のビットコイン・ネットワークのマイニングパワーを上回る必要があります。つまりマイニングパワーにおいて過半数を制する必要があります。これを51%アタックといいます。これほどの計算力を持っているなら、正当なマイナーとなった方が得であり、不正をするインセンティブはなくなります。

ビットコインの画期的なところは、管理者なしに経済取引できることです。通常の貨幣は、信頼できる第三者（=国家）がいて初めて機能します。だから国が信用されていなければその国の貨幣も信用を失います。しかし、ビットコインには、そうした主体がありません。ビットコインのネットワークは世界中に網の目のように広がり、国家を超越したものになっています。もちろん、日銀のような中央銀行は必要ありません。中央銀行の大きな役割として、通貨の発行があるが、ビットコインではマイニングの成功報酬という形で「ビットコインという仕組み」そのものがコインを発行します。逆に言えば、ビットコインではマイニング以外にコインを生み出す方法はありません。

さいごに

暗号は数学技術の塊です。しかし、純粋な数学者が好むような格調高い領域ではなく、なんでもありの雑多な世界とされています。出自もさまざまで、数学出身者やハッカー、政府諜報機関の役人、そして犯罪者も含まれます。

また、暗号業界はとにかく進歩が速く、暗号戦争ともいうべき世界的競争は加速を続けています。暗号の開発者(ディフェンダー)と攻撃者(アタッカー)の応酬が続く中で、暗号技術は日々進歩しており、今後間違いなくテクノロジーの中核を担う業界と言えるでしょう。