ハッシュとはぐしゃぐしゃに混ぜること
今回は、参議院予算委員会でも取り上げられたハッシュ関数(hash function)を解説します。ハッシュとは英語で「ぐしゃぐしゃに混ぜる」ことですが、なぜぐしゃぐしゃに混ぜることが現代のコンピューティングにおいて最重要な課題の1つになったのでしょうか?
まずはハッシュ関数の用途を見てみましょう。大きく2つの用途に分かれます。
無関係というより正反対に見えます。それではハッシュ関数とはどんな関数なのでしょう?
- あるデータを整数値に対応
- データが同じなら、必ず同じ数値を返す
- データが異なっている場合は、なるべく異なる数値を返す
これだけです。この定義どおりだとすると、
つまり受け取った数値をそのまま返す関数もハッシュ関数ということになります。とくに3.に関してはなるべくどころか必ず異なる数値を返すという意味で完璧です。しかし全然ハッシュしてないのにハッシュ関数とはこれいかに?
あまり混ぜない「.hashValue」
しかしこれが、言葉遊びではなく実際に使われています。もちろんSwiftでも。
SwiftにはHashable
というプロトコルが用意されています。このプロトコルに準拠した型は、
というComputed Property、つまりfunctionを必ず持っています。実際に試してみましょう。
見てのとおり、1ビットも違わず一緒です。それが何の役に立つのか。連想配列(associative array)の実装に役立つのです。これさえあれば任意のデータ構造を作れるという意味で最も便利なこのデータ構造で、JavaScriptやPHPにいたっては連想抜きの配列さえ連想配列なのですが、その連想配列を実装する最もポピュラーな方法が、添字をハッシュ関数とする連想抜きの配列、すなわちハッシュテーブル(hash table)なのです。あまりにポピュラーなのでPerlとRubyはそれを単にハッシュ(hash)と呼んでいるのですが、筆者としては列車を全部電車と呼んでいるような違和感があります。ディーゼルカーだって蒸気機関車だってあるのに……。
それはとにかく、Swiftではこのデータ構造はPython同様Dictionary
と呼ばれています。しかしその内部実装がハッシュテーブルであることは、Hashable
プロトコルが如実に示しています。
ということは、オレオレハッシュテーブルも作れるということになります。やってみましょう(リスト1)。
名前からわかるとおり、実にナイーブな実装ですが、確かにDictionary
っぽく動いています。
しかし、簡単に破綻します。
h[0]
には1を代入したはずなのに、なぜ上書きされてしまったのでしょう? index()
を見てみましょう。.hashValue
をtable
の要素数で割っていますが、0 % 3 == 1 % 3
なのでh[3] = 7
で上書きされちゃったわけです。要は衝突(collision)が起きたわけです。ハッシュテーブルの実装において、最も難しいのは衝突が起きたときにどうするかですが、最もナイーブな実装としてはハッシュテーブルを作りなおすというものがあります。たとえばこんなふうに(リスト2)。
あるいははじめから衝突があり得ないぐらい大きな配列を用意しとくか。しかしそれではメモリがいくらあっても足りなくなってしまいます。しかも今回は添字がInt
だからいいものの、String
だとしたらindex()
ではなく.hashValue
そのものが同じ値を返すことも想定しなければなりません。Int
はたかだか8バイト。それより長い文字列には必ず同じ.hashValue
を返す別の文字列が存在することは鳩ノ巣原理で明らかなのですから。
幸い再発明をしなくても、Swiftには最初からDictionary
が組み込まれていますし、Hashable
でなければならないのはキーだけで値はなんでもありなので、ハッシュ関数を自作する必要はあまりないでしょう。どうしても必要なときは.description
を実装してから.description.hashValue
を返すという逃げもあります。
きちんと混ぜなければダメなダイジェスト
ハッシュテーブルで使うハッシュ関数は「あまり被らない」程度にかき混ぜればOKで、被る心配がなければかき混ぜそのものすら不要だというのは見てのとおりですが、国会でも取り上げられたもう1つの用途、つまりデータの指紋として使う場合はそうもいきません。別のデータから同じ指紋を簡単に作れたら指紋として役に立たないのですから。.hashValue
はたかだか64ビットの数値ですが、「指紋」用のハッシュ関数がこれよりずっと大きな値を返すのは「天文学的に被らない」ようにするためにも必須と言えるでしょう。この目的ではもはや安全とは言えないMD5でも128ビットありますし、現在主流のSHA-256にいたっては256ビットもあります。32バイト、16進数表記にすれば64文字にもなる巨大数値は「数値」というよりむしろ「要約」(digest)というにふさわしく、「ハッシュ値」(hash value)より「ダイジェスト」と呼んだほうが良いでしょう。ダイジェスト用の関数を実装するのはハッシュテーブル用の関数を実装するよりも難しそうなことは暗号学者でなくとも想像できます。
幸いにして暗号学者たちの検証を経た、プロのお墨付きのダイジェスト関数の実装は主要OSには標準装備されていますが、Swift から使うにはちょっと工夫が必要です。方法は記事の終わりにまとめたのでそちらを参照していただくとして、実例を見てみましょう。
ダイジェスト、もといまとめ
記録改竄とその防止の歴史は、おそらく人類が文字を発明したのと同じ長さがあるでしょう。バビロニアの契約書は、契約を刻んだ粘土板にさらに粘土をかぶせて同じ文言を刻んだそうです。データは粘土板や紙といった媒体から解放されましたが、黒歴史を書き換えたい誘惑から我々が解放される日は来るのでしょうか?その日が来るまで、我々はデータをハッシュし続けるのでしょう……。
[付録]module.mapを使ってimport CommonCryptoする方法
XcodeのターゲットであるmacOS、iOS、tvOSにはすでにCommonCrypto
ライブラリが搭載されているので、md5やsha256などの暗号学的ハッシュ関数を実装し直す必要はありません。ただしCライブラリなのでSwiftからそのまま使えません。
こういった場合、SwiftではBridging Headerを追加して対処していたのですが、module.map
ファイルを使うとBridging HeaderなしでSwiftのFrameworkを作れます。今回はこれを利用してCommonCryptoをSwiftから使ってみることにします。
まずは新規プロジェクトを作成したあと、プロジェクトフォルダの中にCommonCrypto
という名のフォルダを作成し、その中にmodule.map
ファイルを作成します(リスト3)。
次にプロジェクト設定で[Build Setting]→[Swift Compiler - Search Paths]
にCommonCrypto
を追加します(図1)。
この時点でimport CommonCrypto
できるようになったのですが、Cライブラリのままでは使いにくいのでリスト4のように拡張してみます。
これで"Hello, World!".sha256
のようにしてハッシュ値を取れるようになりました。やってみましょう。
なお、リスト5のようなMakefile
を用意すればREPLでも使えるようになります(図2)。
- 第1特集
MySQL アプリ開発者の必修5科目
不意なトラブルに困らないためのRDB基礎知識
- 第2特集
「知りたい」「使いたい」「発信したい」をかなえる
OSSソースコードリーディングのススメ
- 特別企画
企業のシステムを支えるOSとエコシステムの全貌
[特別企画]Red Hat Enterprise Linux 9最新ガイド
- 短期連載
今さら聞けないSSH
[前編]リモートログインとコマンドの実行
- 短期連載
MySQLで学ぶ文字コード
[最終回]文字コードのハマりどころTips集
- 短期連載
新生「Ansible」徹底解説
[4]Playbookの実行環境(基礎編)