ハッシュへの考察：前提

大本の発端は、Mixi(ええつい最近入りました。idが6707097番でございます)で、ハッシュの話をしているときに出てきた、とある方の「ハッシュは一方向とは限らない」という発言が元です。
結局のところ、現時点まででその発言をされた方から「一方向ではない(恐らくは双方向、ですよねぇ？)ハッシュ」というものについて伺うことができなかったのですが。
折角だしハッシュの考察を一度やり直そうと思いまして。

まずはHashという「英単語」の調査から。gooさんの辞書によれば

━━ n. こま切り［ハヤシ］肉料理; ごたまぜ; 焼直し; 〔俗〕 ＝hashish; 【コンピュータ】ハッシュ ( (意味のない不要データ) ).
make a hash of　〔話〕 …をめちゃめちゃにする.
settle …'s hash　〔話〕 人をやっつける, へこます.
━━ vt. 切り刻む ( (up) ); めちゃくちゃにする ( (up) ); よく話し合う ( (over) ).
hash out　〔話〕 とことん議論して解決する.
hash browns　( (複数扱い) ) ハッシュブラウン ( (刻んでパリッと揚げたジャガイモ) ).
hash house　〔米俗〕 安飲食店, 大衆食堂.
hash・ing　━━ n. 【コンピュータ】ハッシュ法 ( (データのキーに対して変換を施して行うデータ検索の技法) ).
hash totals　【コンピュータ】ハッシュ合計.
hash-up　〔英俗〕 改作, 焼き直し.

…まて。「データのキーに対して変換を施して行うデータ検索の技法」っていきなり答えかいてど〜する(苦笑

気を取り直して。もうちょっと技術背景をきちんと調べてみましょう。
あ、先に。シェル系(PerlとかPHPとか)のハッシュ配列とかその辺の話を期待されている方は…ちぃと長くなるので。ご容赦のほどを。
本気で長くなりそうなので章立てにします(笑

ハッシュへの考察：検索手法としてのハッシュ

なにもない一番初めからいきましょう。
まだすべてが混沌だったころに神様が矛を持たれてその混沌を混ぜると………ってまて。前すぎ。

コンピュータが出てきてからまぁ「人間じゃシャレにならん大量のデータを扱うのに便利」って発想は割合に早くからありまして。
大量のデータで一つ重要な要素は「検索」です。図書館ですと、司書の方とかが魔法のような手さばきでありえない速度の検索をやっている、あんな感じです。
基本は「頭からデータ嘗め回して見つけたら"君だ〜"とか叫ぶ」感じなのですが。こういうのを「線形検索」とか呼称します。

問題がありまして。単純に「力技なので時間が掛かる」です。データ量が少なけりゃよいのですが、多いと大変な目にあいます*1。
大変なときには何か考える。必要は発明の母と申します。
一つには「Bツリー(Balanced tree)」ってのがあるのですがおいといて*2。

大雑把に考えて。データを「全部嘗め回す」から時間がかかるのです。んじゃぁ「データをいくつかのグループに分ければ」問題は解決すると思いませんか？
これがハッシュ(「ハッシュ法(hashing)」って言い回しが多いですねぇ)の根幹たる発想です。
例えば。データを10のグループにわければ、理論上は「全体を嘗め回す1/10の労力」でいけます。100のグループなら1/100。すばらしい。
問題は「データとグループとを結びつける必要」があるのですが。これにテーブルを用意したんじゃ意味ありません。当たり前ですね。「グループを探すためにデータ全部に対して線形検索が必要」になっちゃいますから。

幸い。コンピュータは「計算機」です。んじゃ計算でなんか出てくりゃ按配よかんべ、ってのがここから連なる発想になります。
ここで、ちょっと格好よく専門用語を出してみると。
ハッシュ関数っていう「計算してくれるhogehoge」を用意しまして。こいつにデータを食わせると「ハッシュ値(又はハッシュキー)」と呼称される「グループ名」が出てきます、って感じの流れを作っちゃうんですね。

ハッシュ値 ＝ ハッシュ関数(でぇた);

こんなイメージ。
これが「ハッシュ」と呼ばれるものの大元になります。
この辺を踏まえて、あちこちのハッシュ関数の定義を少し見てみましょう。

あるデータが与えられた場合にそのデータを代表する数値を得る操作、又は、その様な数値を得るための関数（ハッシュ関数）のこと。またハッシュ関数から得られた数値そのもの（ハッシュ値）のことをハッシュということもある。

ドキュメントや数字などの文字列の羅列から一定長のデータに要約するための関数・手順のことをハッシュ関数という。関数を通して出力される値は、「ハッシュ値」、または単に「ハッシュ」と呼ぶ。

データベース処理などで、ハッシュ法による検索処理を実現する際に、レコードの検索を高速に行なえるようなキー（ハッシュキー）を作成するのに使用する処理。ハッシュ関数で得られたキーからハッシュテーブルを参照して、検索対象を高速に得ることができる。

与えられた原文から固定長の疑似乱数を生成する演算手法。生成した値は「ハッシュ値」と呼ばれる。

データ（キー値）をある関数で変換し、格納する場所を直接決め、そこにデータを格納する。この関数のことをハッシュ関数とよぶ。

ハッシュ関数（はっしゅかんすう、hash function）とは、もとのデータからある一定範囲の数値を生成する関数である。理想的には、異なったデータからは常に異なったハッシュ値が得られることが望ましいが（完全ハッシュ関数）、多くの場合それは困難である。

概ね腑に落ちるのではないでしょうか？
ハッシュとは「検索を高速に行うために必要な色々」である、というのがここまでの定義になります。

さてはて。鍵は出来ましたが。ではどんな風に実際のデータを格納していくのでしょう？

*1:ちなみに某サイトには「データ量が1000を越えたら，線形表よりも効率のよい方法を考えたほうがよい」とありました。検証はしていないのですが参考として記述しておきます。

*2:とあるサイトによると「各種のツリー構造とは異なり、静的な配列だけで簡単に実装でき、効率も極めて高い。このため、非常に実用的な手法として重宝である。」だそうです。

ハッシュへの考察：ハッシュ法実装の些末時(些末ぢゃないんだけどね)

実際のデータは「ハッシュ表(ハッシュテーブル)」と呼称される場所に格納されます。
さて。問題がありまして「ハッシュ関数通すと違うデータで同じハッシュ値が出てくる」事は、可能性として十分にありえます。１万のデータに対して100のグループで分けようとすれば、１グループあたり100のデータがあるはずですし。理想的なハッシュ関数であったとしても。
こーゆー「異なるデータでハッシュ値が一緒になる」事を、衝突(コリジョン:collision)って呼称しますが。
コレに対して「どんな風にデータを格納するか」ってのを考えなければいけません。
アバウトに２種類の方向性が存在しますので、簡単に。

連鎖法(チェイン法)
直接連鎖法とも呼称されるようです。
同じハッシュ値が生成された場合に連結リストを使って、ハッシュ表的に同じキー位置にデータを連結していきます。
あんまり一つのキーに対するチェインが長すぎるとハッシュにする意義が低くなります。まぁハッシュ法である以上共通に持ちうる問題点なのですが。

開番地法(オープンアドレス法)
同じハッシュ値が生成された場合に「次どこか探してみる〜」っていう手法です。
ここには更に二つの代表的(…だと思う)がありますので、順次ご紹介を。

線型操作法
キーに相当する格納場所が埋まってたら、キーの値をインクリメントして(デクリメントも…論理的にはありえるはず)、空き場所を探します。相手たらデータ突っ込みます。

２重ハッシュ法
キーに相当する格納場所が埋まってたら、別のハッシュ関数を用いて別のハッシュ値を算出、そのキーで格納をします。
…「二つのハッシュ関数で双方ともに衝突したら」…ど〜するんでしょ？

も一個些末な話を。
これも受け売りってか引用で検証はしていないのですが。

ハッシュ空間のサイズに対する言及：

ハッシュ表は，表に十分な空白があるときには，効率がよい．
おおよそ表の半分程度が空白であればいい．
シミュレイションによれば，そのくらい以上の空白があるとき，表の大きさによらず平均2回程度の比較で足りる．
ただし，ハッシュ関数がデータを均一にばらまくような性格をもっていないとうまくいかない．

ハッシュ空間の使用率に対する言及：

表の埋まりかたが70%以下なら，ハッシュ表は効率がよい．
しかしそれを越えるととたんに効率低下が生じる．

ハッシュ法における「簡単なハッシュ関数」への言及：

一般的なハッシュ関数としては，
名前の文字列を0と1のビット列として，32ビットごと(あるいは64ビットごと)に折り畳んで排他的論理和をとり，それを(先頭のビットを符号とみなさずに)正整数とみなして，表の大きさで割った余り+1を返すと，比較的よいものになる．
(1を加えた理由は表の添字が1から始まるとしたからで，C言語の配列のように添字が0から始まるなら+1は不要)．

ハッシュへの考察：完全性を確保する手段としてのハッシュ

さてはて。ハッシュ法からどういう経緯でココにたどり着いたかがもう一つ不明なのですが。
恐らくは

• 良質で比較的ハッシュ空間の広いハッシュ関数だと、なかなか衝突がおきない(アルゴリズムの慎重な選定)
• 本質的に一方向な性質を持つために逆算が出来ない(データを間引いているため)

あたりから、なにか降りてきたのでしょう。
セキュリティの一環である「正真性あるいは完全性(integrity)の確保」としてのハッシュ関数の利用、という発想が沸いてきました。

データから一定長のハッシュ値が出てくる、って話はすでに腑に落ちたかと思いますが。
ここから「衝突がほとんど起きない」事を前提に、それを指紋に例えた人がいます。この場合、ハッシュ値と同意の単語として、メッセージダイジェスト(message digest)、フィンガープリント(fingerprint)、なんて単語も用いられます。
ちなみにリアルな指紋にも衝突はあるようです。ポイントは「めったにない」事。DNAは…確か衝突あったはず。微妙に自信なし。
おいといて。

ファイルの「指紋」をとって、ファイル本体と指紋情報を別ルートで郵送。こいつを受け取り側が受け取ってもう一度ファイルから指紋を取って「指紋照合」すれば、ファイルが「同一」であることがおおよそ確定できます。
こーゆーのをセキュリティの世界では「完全性の確保」というのですが。

こういった流れから、セキュリティの世界でもハッシュ関数がよく用いられるようになりました。
ちなみに、こういった「セキュリティの世界で用いられるポピュラーな(あるいは、ポピュラーだった)」ハッシュ関数には

• SHA-0/1/224/256/384/512
• MD 2/4/5
• RIPEMD-80/128/160/256/320
• Snefru
• Haval-128/160/192/224/256
• Whirlpool
• Tiger/Tiger2

などがあります。

ハッシュへの考察：とりあえずのまとめ

さてはて。こーゆー流れでハッシュってのは現在に至っているようです。
で…使われ方でハッシュ関数への配慮が変わるのは当然なのですが、ちぃとまとめて見ましょう。

ハッシュ法(ハッシュ検索)として用いる場合。
衝突することは概ね前提なので、如何に「均一に衝突するようにするか」がポイントになります。予めデータの質がわかってると色々と小細工も可能ですね。
とはいえ「とりあえずざっくり作ってみて後で修正」ってケースが多いような気もしますが*1。
よくJavaやらPHPやらPerlやらで出てくる「ハッシュ配列」は本質的にハッシュ検索のロジックがベースになってます。

ちなみに余談ですが。完全ハッシュ関数ってものがありまして、これは「衝突しない」ハッシュ関数です。
概ね「ある固定された母数における」という限定環境下において言及されるものです。
ちなみにコンパイラ作るときにも出てきます。予約語テーブルに対する完全ハッシュ関数があるとコンパイル楽なんですよ。…ええかなり停滞しているOOBHPの話に絡んできます(笑

閑話休題

セキュリティとしてのハッシュ関数の場合。
なによりも「衝突しないこと」が重要なのですが。まぁハッシュである以上不可避なので。
次に出てくるのは「衝突耐性 (collision resistance) 」になります。対衝突性とは「衝突を簡単に見つけられるか否か」って観点で。簡単なら弱いし難しけりゃ強いって観点ですね。
厳密には。さらにこの衝突耐性は二つの方向から見まして。

弱衝突耐性
「あるメッセージのハッシュ値が与えられたときに、そのハッシュ値をもつ別のメッセージを見つけ出すことが容易か困難かを指し示す」
代表的アタック手法：ブルートフォース
力押しで「適当に作った元メッセージを微妙に変化させていってハッシュ値がぶつかるまでリトライし続ける」。
この場合の「適当に作った元メッセージ」ってのは大抵「悪意あるアタッカーにとって有利な、すりかえたいモノ」。

強衝突耐性
「同一のハッシュ値をもつ二つのメッセージを見つけ出すことが容易か困難かを指し示す」
代表的アタック手法：誕生日攻撃(birthday attack)
まず二つのメッセージを作成。一つは「本来使われたい、攻撃される側が読んで疑惑を抱かないようなメッセージ」。もう一つは当然のごとく「悪意あるアタッカーにとって有利な、すりかえたいモノ」。ポイントは、この二つのメッセージが「同一のハッシュ値を持つ」こと。
んで。
本来使われたいメッセージを使わせてハッシュ値を計算させた後、元ファイルを「攻撃者にとって都合の良いファイル」に摩り替える。これによって正真実を打ち破ることができる。

以上がハッシュに関する考察になります。
少しはハッシュってモノが見えてきましたでしょうか？

で。元に戻しますが。
結局のところ、ここまで調べてなお「一方向ではない(恐らくは双方向、ですよねぇ？)ハッシュ」という存在については確認ができませんでした。
…というか正直なところ。「データをある程度間引く」ハッシュにおいて「一方向ではない」っていうのは…ちょっと想像しにくいんですよね。
ただ、無論「私の知らない何か」がある可能性を否定は出来ないので。また何かありましたら追記などしてみたいと思います。

捕捉１：チェックサムはハッシュか？
すごく悩ましいのですが。「完全性の確保としてのハッシュ」という基準から考えると、チェックサムもまたハッシュの一環なのかなぁ、と思います。
ただ…衝突がほとんど問題にならないとか(いやまぁだから縦横でやるんでしょうが)なんとか…どうももう一つ腑に落ちていません(苦笑

捕捉２：圧縮ロジックはハッシュか？
一瞬。ハッシュの「縮める」って部分を基準にこんなことを考えたのですが。
「出力が固定長である」という定義の部分をもって明示的に否定できることがわかりました。
同じミスしないようにここに書いておきます。

*1:昔「カオス関数でハッシュ関数をごにょごにょ」とかいう狂気の沙汰もありましたがそれは多分例外(笑

ハッシュへの考察：追記あるいは「一方向性」という言葉への考察

えっと。始めに話を受けた方から

「ハッシュ関数」とは何か。
「一方向ハッシュ関数」とは何か。
「一方向性」とは何か。
について個別に触れようとしてないのが全然ダメ。

というお話を頂いて。…なんとなく「どの辺に引っかかっていたのか」を色々と考察してみます。

ここで。とりあえずポイントとしては

• 不可逆
• 一方向性

の二つの言葉の定義でしょうか？
不可逆はまぁそのまんまなので省略します。
で…ちと一方向性について調べてみたりするのですが。

一方向性関数とは、関数の中でも、間単に計算できるが逆関数の逆関数の計算が非常に困難である（もしくは不可能である）ような関数のことである。

一方向性関数（いちほうこうせいかんすう, oneway function）とは、簡単に計算できるが逆関数の計算は非常に困難である関数の事。

このあたりから公約数的な発想をすると…

hoge ＝ 関数(でぇた)
があるときにおいて。

• でぇたを関数に通すとhogeが算出できる
• hogeから、逆関数を定義してでぇたを取り出すのが不可能、若しくは困難である

っていうのが恐らくは定義としてあるのではないか、と思われるです。
で…「不可逆」である以上、逆算は(データがつぶれてるから)不可能なはずなので。真っ当な手段「ではなく」アタック的手法で逆算したとして、その値が「衝突するほかのデータではない」保障もないですし。
この観点からすると、ハッシュ関数はすべからく一方向性関数になると思われます。そこから「一方向性ハッシュ関数」という呼称が出てきたのだろうとは十分に予測が出来るのですが(そういった用語使用例も、ネットを見ている限りでは多いですし)。

ただ、ここで微妙に気になるのが。
「一方向性関数」ではなくて「一方向性ハッシュ関数」とした場合の定義が、場所によっては

一方向性ハッシュ関数は、衝突を起こしにくい圧縮関数hのことをいいます。ここでいう衝突とは、異なるx1、x2に対してh(x1)=h(x1)となることです。

という風に「値の逆算の不可能性/困難性」ではなく「衝突を起こしにくい、或いは衝突を見つけにくい」という部分に言及してある場合があることです(ケース的には少ないように感じられましたが。とりあえず１件しか見つけられてないので)。
で。もし前述のMixiの方の発言が、この定義を元に「衝突耐性の強度如何によっては"一方向性ハッシュ関数ではない"」と定義されるなら………わからなくも、ないです。
ただ…「一方向性関数」からの派生語としての「一方向性ハッシュ関数」を考えた場合に、衝突の強度の有無(しかも基準がもう一つ微妙)を前提にするのは…ちょっと難しいように思うのですが。どうなんでしょうかねぇ？

とりあえず「一方向性関数」関連で調べると案外に面白かったので追記してみます。