Apa itu Fungsi Hash yang baik?

Apa fungsi Hash yang baik? Saya melihat banyak fungsi hash dan aplikasi dalam mata kuliah struktur data saya di perguruan tinggi, tetapi kebanyakan saya cukup sulit membuat fungsi hash yang baik. Sebagai aturan praktis untuk menghindari tabrakan, profesor saya mengatakan bahwa:

function Hash(key)
  return key mod PrimeNumber
end

(mod adalah% operator dalam bahasa C dan sejenisnya)

dengan bilangan prima menjadi ukuran tabel hash. Saya mendapatkan bahwa itu adalah fungsi yang agak baik untuk menghindari tabrakan dan yang cepat, tetapi bagaimana saya bisa membuat yang lebih baik? Apakah ada fungsi hash yang lebih baik untuk kunci string terhadap kunci numerik?

Untuk melakukan pencarian tabel hash "normal" pada dasarnya semua jenis data - yang ini oleh Paul Hsieh adalah yang terbaik yang pernah saya gunakan.

http://www.azillionmonkeys.com/qed/hash.html

Jika Anda peduli tentang keamanan kriptografis atau hal lain yang lebih canggih, maka YMMV. Jika Anda hanya ingin fungsi hash tujuan umum pantat pantat untuk pencarian tabel hash, maka ini adalah apa yang Anda cari.

Tidak ada yang namanya "fungsi hash baik" untuk hash universal (ed. Ya, saya tahu ada yang namanya "universal hashing" tapi bukan itu yang saya maksudkan). Tergantung pada konteksnya kriteria yang berbeda menentukan kualitas hash. Dua orang sudah menyebutkan SHA. Ini adalah hash kriptografi dan sama sekali tidak baik untuk tabel hash yang mungkin Anda maksud.

Tabel hash memiliki persyaratan yang sangat berbeda. Tetapi tetap saja, menemukan fungsi hash yang baik secara universal sulit karena tipe data yang berbeda mengekspos informasi yang berbeda yang dapat di hash. Sebagai patokan, baik untuk mempertimbangkan semua informasi yang dimiliki oleh suatu jenis. Ini tidak selalu mudah atau bahkan mungkin. Untuk alasan statistik (dan karenanya tabrakan), juga penting untuk menghasilkan penyebaran yang baik ke ruang masalah, yaitu semua objek yang mungkin. Ini berarti bahwa ketika hashing angka antara 100 dan 1050 itu tidak baik untuk membiarkan digit paling signifikan memainkan peran besar dalam hash karena untuk ~ 90% dari objek, digit ini akan menjadi 0. Jauh lebih penting untuk membiarkan tiga terakhir digit menentukan hash.

Demikian pula, ketika hashing string, penting untuk mempertimbangkan semua karakter - kecuali ketika diketahui sebelumnya bahwa tiga karakter pertama dari semua string akan sama; mengingat ini adalah pemborosan.

Ini sebenarnya adalah salah satu kasus di mana saya menyarankan untuk membaca apa yang dikatakan Knuth dalam The Art of Computer Programming , vol. 3. Bacaan lain yang bagus adalah The Art of Hashing karya Julienne Walker .

Ada dua tujuan utama fungsi hashing:

• untuk membubarkan titik data secara seragam menjadi n bit.
• untuk mengidentifikasi data input dengan aman.

Tidak mungkin untuk merekomendasikan hash tanpa mengetahui untuk apa Anda menggunakannya.

Jika Anda hanya membuat tabel hash dalam sebuah program, maka Anda tidak perlu khawatir tentang bagaimana algoritme yang dapat dibalik atau diretas ... SHA-1 atau AES sama sekali tidak diperlukan untuk ini, Anda akan lebih baik menggunakan sebuah variasi FNV . FNV mencapai dispersi yang lebih baik (dan dengan demikian lebih sedikit tabrakan) daripada mod prime sederhana seperti yang Anda sebutkan, dan itu lebih mudah beradaptasi dengan berbagai ukuran input.

Jika Anda menggunakan hash untuk menyembunyikan dan mengotentikasi informasi publik (seperti hashing password, atau dokumen), maka Anda harus menggunakan salah satu algoritma hashing utama yang diperiksa oleh pengawasan publik. Hash Function Lounge adalah tempat yang baik untuk memulai.

Ini adalah contoh yang bagus dan juga contoh mengapa Anda tidak ingin menulisnya. Ini adalah Fowler / Noll / Vo (FNV) Hash yang merupakan bagian jenius ilmu komputer yang sama dan voodoo murni:

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

Edit:

• Landon Curt Noll merekomendasikan di situsnya algoritma FVN-1A di atas algoritma FVN-1 yang asli: Algoritma yang ditingkatkan lebih baik menyebarkan byte terakhir dalam hash. Saya menyesuaikan algoritme sesuai.

Saya akan mengatakan bahwa aturan utama adalah tidak menggulung Anda sendiri. Cobalah untuk menggunakan sesuatu yang telah diuji secara menyeluruh, misalnya, SHA-1 atau sesuatu di sepanjang garis itu.

Fungsi hash yang baik memiliki properti berikut:

1. Mengingat hash pesan, secara komputasi tidak mungkin bagi penyerang untuk menemukan pesan lain sehingga hash mereka identik.

2. Diberikan sepasang pesan, m 'dan m, secara komputasi tidak layak untuk menemukan dua sehingga h (m) = h (m')

Kedua kasus itu tidak sama. Dalam kasus pertama, ada hash yang sudah ada yang Anda coba cari tabrakan. Dalam kasus kedua, Anda mencoba untuk menemukan setiap dua pesan yang bertabrakan. Tugas kedua secara signifikan lebih mudah karena ulang tahun "paradoks."

Di mana kinerja bukanlah masalah besar, Anda harus selalu menggunakan fungsi hash yang aman. Ada serangan yang sangat cerdas yang dapat dilakukan dengan memaksa tabrakan dalam hash. Jika Anda menggunakan sesuatu yang kuat sejak awal, Anda akan mengamankan diri Anda dari ini.

Jangan gunakan MD5 atau SHA-1 dalam desain baru. Kebanyakan cryptographers, termasuk saya, akan menganggapnya rusak. Sumber utama kelemahan dalam kedua desain ini adalah bahwa properti kedua, yang saya uraikan di atas, tidak berlaku untuk konstruksi ini. Jika seorang penyerang dapat menghasilkan dua pesan, m dan m ', yang keduanya hash dengan nilai yang sama mereka dapat menggunakan pesan-pesan ini terhadap Anda. SHA-1 dan MD5 juga menderita serangan ekstensi pesan, yang dapat melemahkan aplikasi Anda secara fatal jika Anda tidak berhati-hati.

Hash yang lebih modern seperti Whirpool adalah pilihan yang lebih baik. Itu tidak menderita dari serangan ekstensi pesan ini dan menggunakan matematika yang sama seperti AES digunakan untuk membuktikan keamanan terhadap berbagai serangan.

Semoga itu bisa membantu!

Apa yang Anda katakan di sini adalah Anda ingin memiliki yang menggunakan memiliki resistensi tabrakan. Coba gunakan SHA-2. Atau coba gunakan cipher blok (baik) dalam fungsi kompresi satu arah (tidak pernah mencobanya sebelumnya), seperti AES dalam mode Miyaguchi-Preenel. Masalahnya adalah Anda perlu:

1) memiliki infus. Coba gunakan 256 bit pertama dari bagian pecahan konstanta Khinchin atau sesuatu seperti itu. 2) memiliki skema bantalan. Mudah. Barrow dari hash seperti MD5 atau SHA-3 (Keccak [diucapkan 'ket-chak']). Jika Anda tidak peduli dengan keamanan (beberapa orang lain mengatakan ini), lihat FNV atau lookup2 oleh Bob Jenkins (sebenarnya saya orang pertama yang merekomendasikan lookup2). Juga coba MurmurHash, cepat (periksa ini: .16 cpb ).