一方向ハッシュ関数についてまとめ

ハッシュ関数とは

ハッシュ関数とは、ある入力に対してそのデータを代表するデータを出力する関数のことである。

ハッシュ関数の安全性

ハッシュ関数には、以下の3つの安全性要件がある。

  • 原像計算困難性
  • 衝突計算困難性
  • 第二原像計算困難性

原像計算困難性

原像計算困難性とは、与えられたハッシュ値からそのハッシュ値を出力する入力を求めることが困難である性質を言う。

衝突計算困難性

消灯計算困難性とは、同じハッシュ値を出力する入力を求めることが困難であることを言う。

第二原像計算困難性

第二原像計算困難性とは、与えられた入力と同じハッシュ値を出力する別の入力を求めることが困難であることを言う。

一方向ハッシュ関数

ハッシュ関数のうち、原像計算困難性を満たすものを一方向ハッシュ関数という。

具体的には、一方向性関数をfとするとき xからf(x) を多項式時間で求められ f(x)からx を多項式時間で求められないことである。

一方向ハッシュ関数に用いられるアルゴリズムの種類

MD5

Message Digest Algorythm 5のことで、出力128bitのハッシュアルゴリズムとなっている。 現在は、安全でないアルゴリズムで使用は推奨されていない。

SHA-1

Secure Hash Algorithmの一種で、SHA-1には脆弱性が存在しているため使用にすることは推奨されていない。

SHA-2

Secure Hash Algorithmの一種で、SHA-1脆弱性が発見されたため現在はこちらを使用することが推奨されている。SHA-2は鍵長により以下のような種類がある。

  • SHA-224
  • SHA-256
  • SHA-384
  • SHA-512

ソルト

一方向性ハッシュ関数では、同じ文字列の入力に対して同じハッシュ値を出力する。しかし、ユーザ名などが同じ複数のユーザのパスワードを保存したい場合がある。 この時使用するのが「ソルト」で、ハッシュ化を行う前に対象文字列にランダムな文字列を追加する。こうすることによって、同一文字列のハッシュ化時の衝突を防ぐことができる。

ElasticsearchでMySQLのLIKE検索ぽいものを実現

はじめに

Elasticsearchを使って全文検索システムを作る機会がありました。 そのとき、MySQL%HOGE% と同様の検索をすることが必要な場面がありハマってました。 色々試行錯誤して実現した結果を、自分と同じようなことを行いたい人がいるかもしれないのでメモとして残しておきます。 Elasticsearch & 検索システム初心者なので間違ったことなどあったら、教えてほしいです。

環境

  • Amazon Elasticsearch Service (ver 2.3)

注意

  • Amazon Elasticsearch ServiceElastic社のElasticsearch別物です。
  • あくまでLIKE検索もどきである完全に同じ検索が行えるわけではありません。
  • 困ったときはElastic社のリファレンスを見てください。リファレンス

検索の仕方

N-gram analyzermatch_phrase を用いて検索します。

{
    " query" : {
        "match_phrase" : {"field_name" : "keyword" }
    }
}

N-gramのfiledを作る方法は、他の記事などで詳しく解説されているので省きます。 このように、 N-grammatch_phrase を組み合わせるとLIKE検索もどきが実現できます。