- PR -

元の値と元の値のハッシュ値を関係付ける方法

1|2 次のページへ»
投稿者投稿内容
banboo
大ベテラン
会議室デビュー日: 2003/12/05
投稿数: 210
投稿日時: 2005-09-02 18:30
ハッシュ値について質問が御座います．

元の値と元の値のハッシュ値を関係付ける方法がありましたら
ご教授下さい．

例えば，
元の値に優先順位がついていたとします．
例えば，M1の優先順位が1，M2の優先順位が2，M3の優先順位が3とします．
ここで，元の値のハッシュ値をとると，元の値と全く関係ない値になります．

M1：1 ⇒　Hash(M1)= cnaour;eb;o21

M2：2 ⇒　Hash(M2)= euay329nfoenf

M3：3 ⇒　Hash(M3)= 1gieyubicpo

やりたいことは，ハッシュ値をとった状態で，Hash(M1)，Hash(M2)，Hash(M3)の関係を明らかに
したいのです．
つまり，Hash(M1)の優先順位が1，Hash(M2)の優先順位が2，Hash(M3)の優先順位が3
という事を明らかにしたいのです．
ハッシュは一方向関数なので，Hash(M1)　⇒　M1　という事はできません．
しかし，元の値の関係を保ったまま，ハッシュ値を関係付けるいい方法がありましたら
ご教授下さい．
angel
ぬし
会議室デビュー日: 2005/03/17
投稿数: 711
投稿日時: 2005-09-02 19:08
こんばんは。
引用:
やりたいことは，ハッシュ値をとった状態で，Hash(M1)，Hash(M2)，Hash(M3)の関係を明らかにしたいのです．

単純に、ハッシュ値 + 優先順位の値を連結するのは…やっぱりN.G.なんでしょうかね。
優先順位が漏洩した時に、ハッシュの元の値 ( M1〜M3 ) も漏洩するかどうか…がミソですよね。

さてさて、ハッシュとは一方向の変換になるのですが、変換前後で値同士の大小関係を保存するようなアルゴリズムがあれば、面白いことになりそうですね。
尤も、ハッシュの変換では情報の欠落が起こりますから、大小関係を厳密に保存することは理論上無理そうに思いますけれど。
※それ以前に、そんなアルゴリズム、衝突に弱くて使い物にならなさそうですね。

以上、とりとめも無く。
冬寂
ぬし
会議室デビュー日: 2002/09/17
投稿数: 449
投稿日時: 2005-09-02 19:09
引用:

ここで，元の値のハッシュ値をとると，元の値と全く関係ない値になります．

分かっているじゃないですか。
全く関係無い値になる（もしくは、全く関係無い値にするようにしてある。）のだから
ハッシュ値から元の値同士の関係なんて導き出せません。
（例え、アルゴリズムの穴かなんかで値が偏る為に元の関係が導き出せたとしても、その穴を塞ぐパッチが出たら使えなくなるでしょ？）

でもまぁ、例えばハッシュ値を保持するクラスなんてのを作って、元の値から比較の為に使えるなんらかの値をとってきて保持して・・・
なんてのやれば、比較は出来ると思うけど、そんな事じゃなくて？

（ってか、自分のやりたい事は自分しか解らんのよ。他人に聞く前に、もちっと整理した方がいいんでないかい？）
がるがる
ぬし
会議室デビュー日: 2002/04/12
投稿数: 873
投稿日時: 2005-09-02 19:33
どもです。がるです。
んっと…前回とほぼ同様の答えで恐縮なのですが。
引用:

banbooさんの書き込み (2005-09-02 18:30) より:
やりたいことは，ハッシュ値をとった状態で，Hash(M1)，Hash(M2)，Hash(M3)の関係を明らかに
したいのです．
つまり，Hash(M1)の優先順位が1，Hash(M2)の優先順位が2，Hash(M3)の優先順位が3
という事を明らかにしたいのです．

というのは確定で「無理」です。
以下、証明を。

ハッシュ値はハッシュアルゴリズム(ハッシュ関数)によって計算されます。
アルゴリズムは色々ありまずが、基本的にはどんなに優れたハッシュ関数
でも「違う入力に対して同一のハッシュ値を算出する」状況が出てきます。
これを「衝突」とか「チェイン」とか呼びます。

ハッシュのアルゴリズム次第では、ハッシュ値が異なるAとBにおいては
「ある値Aとある値Bのソート条件の保持」が可能なものも考えられ
うるかとはおもうのですが。少なくともハッシュ値が衝突した場合に
おいて、その関係性を明らかにするのは無理になります(同一の値の
比較は常に「同一」でしかないため)。

したがって、banbooさんの要求は「無理である」こととなります。
ネガティブな投稿で大変恐縮ではあるのですが。
一郎
ぬし
会議室デビュー日: 2002/10/11
投稿数: 1081
投稿日時: 2005-09-02 19:53
背理法で考えてみましょうか。

もし
「ハッシュ値から元の値の順位の比較ができる」
これが真であるとすると、hash(対象の値)をhash(ある値A)と比較して
それより小さければ、hash(Aより小さい値)と比較して
それより大きければ、hash(Aより大きい値)と比較して
と、二分探索みたいな感じでやっていけば、元の値をある一つの値に収束させていけるということですよね。
これは
「元の値が違くても、同じハッシュ値になることがある」
と矛盾します。

例えば2つの値が同じハッシュ値になるとして、元の値が存在する可能性のある範囲を収束させていけば必ずどちらかが範囲から外れるということです。

・・・つまりは、ハッシュ値から元の値の順位の比較は無理ってことです。


-------
あららん。
ゆっくり書いてたらがるがるさんに・・・。
ほとんど内容"かぶり"ですかね。

[ メッセージ編集済み 編集者: 一郎 編集日時 2005-09-02 19:57 ]
一郎
ぬし
会議室デビュー日: 2002/10/11
投稿数: 1081
投稿日時: 2005-09-02 20:14
ん？値じゃなくて、値から計算される順位か・・・。
hash関数の処理として、ハッシュ値の最後に順位を付けるとか。

M1：1 ⇒　Hash(M1)= cnaour;eb;o211
M2：2 ⇒　Hash(M2)= euay329nfoenf2
M3：3 ⇒　Hash(M3)= 1gieyubicpo3

これどーよ。
MMX
ぬし
会議室デビュー日: 2001/10/26
投稿数: 861
投稿日時: 2005-09-02 22:48
＞元の値と元の値のハッシュ値を関係付ける方法
元の値を 暗号化、ハッシュ値として使用、復号化で元の関係を再現。
あるいは、データ圧縮。元の関係を知りたい人のみ鍵を持つ（両方向性関数？）
算術符号圧縮風なら、SORT順を保持するように構成できる。
ソートキーの圧縮もWeb検索に出そうもないが、ありました。

元の関係を再現するには、元の全情報が必要、短縮したハッシュ値ではダメ。
元が100bitあっても情報点が疎で有効50bitて こともありますが

秘匿した状態でデータ処理はなかなかメンドウ。
固定長COBOLデータでは、軽いバイト転置をしてパッと目にはわからないように、があったが、手間の割には秘匿性は低かった。しかもデバッグが大変やりにくい
強い型付けの現状では、項目の区切りと無関係にバイト転置もできません。

耐タンパー性とかサイドチャネル解析の論文を狙っていなければ
seLinux とかの方向が実用的と思います。

[ メッセージ編集済み 編集者: MMX 編集日時 2005-09-02 23:54 ]
unibon
ぬし
会議室デビュー日: 2002/08/22
投稿数: 1532
お住まい・勤務地: 美人谷　　　　　　　　良回答(20pt)
投稿日時: 2005-09-02 23:41
unibon です。こんにちわ。

もしも3つ程度で良いならば、
コード:
for (s = 0; ; s++) {
    h1 = Hash(s + M1);
    h2 = Hash(s + M2);
    h3 = Hash(s + M3);
    if (h1 < h2 && h2 < h3) {
        // 偶然に順序が揃ったので抜ける。
        // (s + "_" + h1) と (s + "_" + h2) と (s + "_" + h3) を結果とする。
        break;
    } else {
        // ループ変数 s を別の値に変えてリトライする。
    }
}

のような感じでできるかなと思います。3つなら有限の時間内に有限の情報量で出力できるでしょう。しかし10個位になると s の情報量が非常に多くなり、もう破綻してしまいます。
1|2 次のページへ»

スキルアップ／キャリアアップ（JOB@IT）