ここから本文です

ハッシュ関数で「ハッシュ値から元の数値を割り出すのは困難」な理由を 数学のわ...

アバター

ID非公開さん

2019/4/1700:03:55

ハッシュ関数で「ハッシュ値から元の数値を割り出すのは困難」な理由を
数学のわからない人にも納得できるよう説明してください。

普通の等式なら逆算すれば元の値が出るのに
ハッシュ関数ではそれができないというのがどうしても感覚的に理解できません。

いろいろネット検索したところ、
https://glorificatio.org/archives/3417
↑このサイトに書かれている

> 例えば2019/01/30は、水曜日だ。
> 日付から曜日は求めることができる。
> 2019/01/30は何曜日ですかと問われれば、カレンダーをめくって曜日を答えることができる。
> 逆に水曜日は何日ですか?と問われれば答えることができない。
> 直近の水曜日を答えるかもしれないが、1週間前のことかもしれないし全然違う日のことかもしれない。
> とにかく選択肢が多くなってしまう。

というのに納得しかけたのですが、
でも「水曜日」になる日付はたくさんあるけど、
同じハッシュ値が出る確率は少ないから
それはちょっと意味合いが違う…?とか思ったらよくわからなくなってしまいました。

補足何度もお答えいただいてありがとうございました。

>要は大きなデータを細切れにして、一定の値で表したものがハッシュになります。
>その時点でデータそのものは欠損しています。

>あくまで確実に戻せなくとも構わないであり、戻せない事を保証するものでは無いです。

>候補を出すためにはハッシュ関数の内容も流出しないとだめだと思う

正確に理解できたわけではないと思いますが、こういった回答から自分なりに消化できました。
最初の質問にあげた「水曜日」の例が何となくしっくりこなかったのは
自分が「7日に1回の割合で水曜日は来る」ことを知っているからでした。
これが仮に「“花曜日”は何年何月何日ですか?」と問われたとしたら
どういう式で"花曜日"が出て来るのか自分には全くわからないから
答えどころか、候補の年月日さえも出すことはできない…というようなものだと理解しました。

この質問は、活躍中のチエリアン・専門家に回答をリクエストしました。

閲覧数:
85
回答数:
3
お礼:
100枚

違反報告

ベストアンサーに選ばれた回答

プロフィール画像

カテゴリマスター

bla********さん

リクエストマッチ

2019/4/1909:28:13

ハッシュ関数は,任意の長さの入力データに対して暗号変換に似た処理(攪拌処理)を繰り返し施すことにより一定長(128~512ビット程度)のデータになるように入力データを圧縮する関数です.
基本操作が圧縮操作ですので,元の情報が持っている内容は失われていきます(一方向性関数).等式ではなく一方向性関数なので逆演算はできません(同じハッシュ値になる元データが複数存在する).
具体的な圧縮操作はハッシュ関数のアルゴリズムにより異なりますが,多くは論理演算(XORなど)やシフト演算の繰り返しです.
例えば,1234 という値を 12 と 23 に分けて,ビット単位に XOR すると 46 (101110) になります.この 46 という値から 1234 は一意には求められません.実際のハッシュ関数ではこのような操作が複雑に繰り返されます.

ハッシュ関数 h の出力長が N のとき,おおよそ 2^(N/2) 個程度のメッセージ M’に対してハッシュ関数を計算することで、h(M) = h(M’) なる M’を見出すことができます (誕生日攻撃:総当たりより少ない計算量で確率的には見つかる).これに対処するために,ハッシュ関数の出力長はある程度長くないといけません (現在は,200ビット程度以上のハッシュ関数が推奨されています). M' が見つかるとメッセージの偽造ができることになります.

なお,ハッシュ関数を使う場合,そのアルゴリズムはハッシュ値を受け取った側は知っていることが前提です.多くの場合,プロトコルの中でどのアルゴリズムを使うかを明示するものです(そうでないと,受け取った側が検証処理できない).
攻撃者もハッシュ値の計算方法を知りうることを前提に安全性が考えられます.ハッシュ値の計算方法が分かったとしても,上述のように計算量的に元の値の探索は困難です.

この回答は投票によってベストアンサーに選ばれました!

ベストアンサー以外の回答

1〜2件/2件中

並び替え:回答日時の
新しい順
|古い順

プロフィール画像

カテゴリマスター

yah********さん

2019/4/1814:34:22

ハッシュの意味が理解できてないのでしょう。

A:3桁の数字を考えてください。
B:考えました(579)
A:それを7倍して、11倍して、13倍して下3桁を教えて下さい。
B:579
A:考えた数字は579ですね。

これを、下2桁でやります。
A:3桁の数字を考えてください。
B:考えました(579)
A:それを7倍して、11倍して、13倍して下2桁を教えて下さい。
B:79
A:考えた数字は179ですね。
B:はずれー

ハッシュでは、情報が欠落しているので、与えられた情報では
正解には至らないのです。この場合、総当たりを1-9の9通り
行えば当たります。これが2の1024乗通りとかになると、
10の100乗を越えますから、無量大数とかでは収りませんし、
1usで1回計算できても、10の6乗回で1秒、10の11乗回で1日
10の13乗回で3年。10の17乗回で3万年にもなって、
辺りを探している間に、時間切れになるはずだ! ってのが、
数学を利用した暗号化の考え方です。

総当たりすればいいので、279だったら、早めに見つかりますし、
979だったら、なかなか見つからないってことです。

プロフィール画像

カテゴリマスター

aki********さん

2019/4/1703:05:25

「普通の等式なら逆算すれば元の値が出るのに」

そんな事無いよ。
x * y = z
xとyからzを求めるのは簡単だけど、
zからxとyを求めるのは困難

たとえば…

「かに」
→12363,12395(Unicode)
→12363*12395(掛けてみる)
→153239385
→39385(下5桁だけ残す)

かに→39385

こんな計算がされた場合、元の文字から「39385」を計算して求めるのは簡単だけど
(もしくは他の文字を変換してみて「39385」と一致するかどうか確認する事は簡単だけど)
「39385」を元の「かに」に計算で戻す事は殆ど不可能に近い。
(二文字って判ってれば総当たりで行けば行けるけどw)

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる