質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

Q&A

解決済

1回答

4383閲覧

ハッシュ方式について質問

musiruda

総合スコア15

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

0グッド

1クリップ

投稿2017/12/15 11:40

ハッシュ方式について、安全でないと判定されるものを以下から教えて頂けるとありがたいです

①ハッシュ値と同じ値が元のデータの中に含まれる
②同じハッシュ値を与える入力値の組み合わせが1つ偶然見つかった
③入力値の上位数ビットを変更してもハッシュ値が変化しない
④ハッシュ関数の設計から10年以上経過した
⑤同じハッシュ値を与える入力値の組み合わせを求める最適なアルゴリズムが見つかった
⑥ハッシュ値がとりえない値が1つ見つかった
⑦ハッシュ値の高速な計算方法がある

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

raccy

2017/12/15 13:09

連想配列の実装などに使う汎用ハッシュ関数ですか?それとも暗号学的ハッシュ関数のことですか?汎用ハッシュ関数に求められる物と暗号などに使用するために求められる物では要件が異なり、一概には言えません。
musiruda

2017/12/15 13:33

なるほど...、違いがあるのですね。暗号学的ハッシュ関数のほうについてご教授願いたいです
guest

回答1

0

ベストアンサー

①ハッシュ値と同じ値が元のデータの中に含まれる

全てのデータ列に対して、データ列のハッシュ値が、そのデータ列の一部になっている、つまり、data.includes(hash(data))があらゆるデータにとって成り立つと言うことと解釈しました。長さ0のデータの場合のハッシュ値が定義できない、長さ1の場合はそのデータそのものであるなど、既にハッシュ関数とは言えません。

②同じハッシュ値を与える入力値の組み合わせが1つ偶然見つかった

誕生日のパラドックスと同じです。

③入力値の上位数ビットを変更してもハッシュ値が変化しない

無視されるビット列がある時点で、それはすでにハッシュ関数とは言えません。

④ハッシュ関数の設計から10年以上経過した

いつから設計されていたのかは開発者本人しかわからず、構想だけなら公表の10年以上前から設計していた可能性があります。公表の時期では無く設計の時期を問うことは検証不可であり、無意味です。

⑤同じハッシュ値を与える入力値の組み合わせを求める最適なアルゴリズムが見つかった

「最適」の定義が曖昧です。多項式時間のことを意味するのであれば、P≠NP予想の結論次第では、全てのハッシュ関数に多項式時間でとけるアルゴリズムが存在することになります。しかし、AKS素数判定法のように多項式時間のアルゴリズムであっても、実用的であるとは限りません。

⑥ハッシュ値がとりえない値が1つ見つかった

ハッシュ値が2^256のパターンがあるハッシュ関数において、とりえない値が1つあると言うことは、とりえるハッシュ値が2^256-1であると言うことになります。もし、2^256であると発表しているのに、実際は2^256-1であったとするなら、世間では詐欺扱いになります。第一、後からとりえない値が見つかったというのであれば、そもそもから検証不足であり、開発者の能力が不足しています。

⑦ハッシュ値の高速な計算方法がある

「高速」の定義が曖昧です。どんなハッシュ関数であれ、とりえるパターンの数と同じ数だけのPCを用意し、一度にバラバラのデータをハッシュ値を求めることで特定のハッシュ値のデータを探したときの期待値は1です。

まとめ

①ハッシュ関数では無い
②誕生日のパラドックス
③ハッシュ関数では無い
④検証不可
⑤定義が曖昧
⑥検証不足
⑦定義が曖昧

安全を問う以前の問題だと思われます。

投稿2017/12/15 22:05

raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問