Fungsi hash yang menghasilkan hash pendek?

Apakah ada cara enkripsi yang dapat mengambil string dengan panjang berapa pun dan menghasilkan hash sub-10 karakter? Saya ingin menghasilkan ID yang cukup unik tetapi berdasarkan isi pesan, bukan secara acak.

Saya bisa hidup dengan membatasi pesan ke nilai integer, jika string dengan panjang arbitrer tidak mungkin. Namun, hash tidak boleh sama untuk dua bilangan bulat yang berurutan, dalam hal ini.

Anda dapat menggunakan algoritma hash yang tersedia secara umum (mis. SHA-1), yang akan memberi Anda hasil yang sedikit lebih panjang dari yang Anda butuhkan. Cukup potong hasilnya ke panjang yang diinginkan, yang mungkin cukup bagus.

Misalnya, dengan Python:

>>> import hashlib
>>> hash = hashlib.sha1("my message".encode("UTF-8")).hexdigest()
>>> hash
'104ab42f1193c336aa2cf08a2c946d5c6fd0fcdb'
>>> hash[:10]
'104ab42f11'

Jika Anda tidak memerlukan algoritme yang kuat terhadap modifikasi yang disengaja, saya telah menemukan algoritme yang disebut adler32 yang menghasilkan hasil yang cukup pendek (~ 8 karakter). Pilih dari tarik-turun di sini untuk mencobanya:

http://www.sha1-online.com/

Anda perlu mencirikan konten untuk menghasilkan intisari. Ada banyak hash yang tersedia tetapi 10 karakter cukup kecil untuk kumpulan hasil. Sebelumnya, orang menggunakan CRC-32, yang menghasilkan hash 33-bit (pada dasarnya 4 karakter ditambah satu bit). Ada juga CRC-64 yang menghasilkan hash 65-bit. MD5, yang menghasilkan hash 128-bit (16 byte / karakter) dianggap rusak untuk tujuan kriptografi karena dua pesan dapat ditemukan yang memiliki hash yang sama. Tidak perlu dikatakan lagi bahwa setiap kali Anda membuat intisari 16-byte dari pesan dengan panjang acak, Anda akan mendapatkan duplikat. Semakin pendek cerna, semakin besar risiko tabrakan.

Namun, kekhawatiran Anda bahwa hash tidak sama untuk dua pesan yang berurutan (baik bilangan bulat maupun tidak) harus benar dengan semua hash. Bahkan sedikit perubahan dalam pesan asli akan menghasilkan hasil intisari yang sangat berbeda.

Jadi, menggunakan sesuatu seperti CRC-64 (dan mendasarkan hasilnya) akan membawa Anda ke lingkungan yang Anda cari.

Hanya meringkas jawaban yang bermanfaat bagi saya (mencatat komentar @erasmospunk tentang penggunaan encoding base-64). Tujuan saya adalah memiliki tali pendek yang sebagian besar unik ...

Saya bukan ahli, jadi perbaiki ini jika ada kesalahan yang mencolok (dengan Python lagi seperti jawaban yang diterima):

import base64
import hashlib
import uuid

unique_id = uuid.uuid4()
# unique_id = UUID('8da617a7-0bd6-4cce-ae49-5d31f2a5a35f')

hash = hashlib.sha1(str(unique_id).encode("UTF-8"))
# hash.hexdigest() = '882efb0f24a03938e5898aa6b69df2038a2c3f0e'

result = base64.b64encode(hash.digest())
# result = b'iC77DySgOTjliYqmtp3yA4osPw4='

Di resultsini menggunakan lebih dari sekedar karakter hex (apa yang akan Anda dapatkan jika Anda gunakan hash.hexdigest()) sehingga kecil kemungkinannya untuk bertabrakan (yaitu, harus lebih aman untuk dipotong daripada hex digest).

Catatan: Menggunakan UUID4 (acak). Lihat http://en.wikipedia.org/wiki/Universally_unique_identifier untuk jenis lainnya.

Anda dapat menggunakan algoritme hash yang ada yang menghasilkan sesuatu yang pendek, seperti MD5 (128 bit) atau SHA1 (160). Kemudian Anda dapat mempersingkatnya lebih lanjut dengan XORing bagian intisari dengan bagian lain. Ini akan meningkatkan kemungkinan tabrakan, tetapi tidak seburuk hanya memotong digest.

Juga, Anda bisa memasukkan panjang data asli sebagai bagian dari hasil untuk membuatnya lebih unik. Misalnya, XORing paruh pertama intisari MD5 dengan paruh kedua akan menghasilkan 64 bit. Tambahkan 32 bit untuk panjang data (atau lebih rendah jika Anda tahu bahwa panjang akan selalu sesuai dengan bit yang lebih sedikit). Itu akan menghasilkan hasil 96-bit (12-byte) yang kemudian bisa Anda ubah menjadi string hex 24 karakter. Bergantian, Anda dapat menggunakan pengkodean basis 64 untuk membuatnya lebih pendek.

Jika perlu, "sub-10-character hash" Anda dapat menggunakan algoritma Fletcher-32 yang menghasilkan hash 8 karakter (32 bit), CRC-32 atau Adler-32 .

CRC-32 lebih lambat dari Adler32 dengan faktor 20% - 100%.

Fletcher-32 sedikit lebih andal dibandingkan Adler-32. Ini memiliki biaya komputasi yang lebih rendah daripada checksum Adler: perbandingan Fletcher vs Adler .

Program contoh dengan beberapa implementasi Fletcher diberikan di bawah ini:

    #include <stdio.h>
    #include <string.h>
    #include <stdint.h> // for uint32_t

    uint32_t fletcher32_1(const uint16_t *data, size_t len)
    {
            uint32_t c0, c1;
            unsigned int i;

            for (c0 = c1 = 0; len >= 360; len -= 360) {
                    for (i = 0; i < 360; ++i) {
                            c0 = c0 + *data++;
                            c1 = c1 + c0;
                    }
                    c0 = c0 % 65535;
                    c1 = c1 % 65535;
            }
            for (i = 0; i < len; ++i) {
                    c0 = c0 + *data++;
                    c1 = c1 + c0;
            }
            c0 = c0 % 65535;
            c1 = c1 % 65535;
            return (c1 << 16 | c0);
    }

    uint32_t fletcher32_2(const uint16_t *data, size_t l)
    {
        uint32_t sum1 = 0xffff, sum2 = 0xffff;

        while (l) {
            unsigned tlen = l > 359 ? 359 : l;
            l -= tlen;
            do {
                sum2 += sum1 += *data++;
            } while (--tlen);
            sum1 = (sum1 & 0xffff) + (sum1 >> 16);
            sum2 = (sum2 & 0xffff) + (sum2 >> 16);
        }
        /* Second reduction step to reduce sums to 16 bits */
        sum1 = (sum1 & 0xffff) + (sum1 >> 16);
        sum2 = (sum2 & 0xffff) + (sum2 >> 16);
        return (sum2 << 16) | sum1;
    }

    int main()
    {
        char *str1 = "abcde";  
        char *str2 = "abcdef";

        size_t len1 = (strlen(str1)+1) / 2; //  '\0' will be used for padding 
        size_t len2 = (strlen(str2)+1) / 2; // 

        uint32_t f1 = fletcher32_1(str1,  len1);
        uint32_t f2 = fletcher32_2(str1,  len1);

        printf("%u %X \n",    f1,f1);
        printf("%u %X \n\n",  f2,f2);

        f1 = fletcher32_1(str2,  len2);
        f2 = fletcher32_2(str2,  len2);

        printf("%u %X \n",f1,f1);
        printf("%u %X \n",f2,f2);

        return 0;
    }

Keluaran:

4031760169 F04FC729                                                                                                                                                                                                                              
4031760169 F04FC729                                                                                                                                                                                                                              

1448095018 56502D2A                                                                                                                                                                                                                              
1448095018 56502D2A                                                                                                                                                                                                                              

Setuju dengan vektor Uji :

"abcde"  -> 4031760169 (0xF04FC729)
"abcdef" -> 1448095018 (0x56502D2A)

Adler-32 memiliki kelemahan untuk pesan singkat dengan beberapa ratus byte, karena checksum untuk pesan ini memiliki cakupan yang buruk dari 32 bit yang tersedia. Periksa ini:

Algoritme Adler32 tidak cukup rumit untuk bersaing dengan checksum yang sebanding .

Cukup jalankan ini di terminal (di MacOS atau Linux):

crc32 <(echo "some string")

8 karakter.

Anda dapat menggunakan pustaka hashlib untuk Python. The shake_128 dan shake_256 algoritma memberikan hash panjang variabel. Berikut beberapa kode yang berfungsi (Python3):

import hashlib
>>> my_string = 'hello shake'
>>> hashlib.shake_256(my_string.encode()).hexdigest(5)
'34177f6a0a'

Perhatikan bahwa dengan parameter panjang x (misalnya 5) fungsi mengembalikan nilai hash dengan panjang 2x .

Sekarang tahun 2019 dan ada opsi yang lebih baik. Yakni, xxhash .

~ echo test | xxhsum                                                           
2d7f1808da1fa63c  stdin

Saya membutuhkan sesuatu di sepanjang garis fungsi pengurangan string sederhana baru-baru ini. Pada dasarnya, kodenya terlihat seperti ini (kode C / C ++ di depan):

size_t ReduceString(char *Dest, size_t DestSize, const char *Src, size_t SrcSize, bool Normalize)
{
    size_t x, x2 = 0, z = 0;

    memset(Dest, 0, DestSize);

    for (x = 0; x < SrcSize; x++)
    {
        Dest[x2] = (char)(((unsigned int)(unsigned char)Dest[x2]) * 37 + ((unsigned int)(unsigned char)Src[x]));
        x2++;

        if (x2 == DestSize - 1)
        {
            x2 = 0;
            z++;
        }
    }

    // Normalize the alphabet if it looped.
    if (z && Normalize)
    {
        unsigned char TempChr;
        y = (z > 1 ? DestSize - 1 : x2);
        for (x = 1; x < y; x++)
        {
            TempChr = ((unsigned char)Dest[x]) & 0x3F;

            if (TempChr < 10)  TempChr += '0';
            else if (TempChr < 36)  TempChr = TempChr - 10 + 'A';
            else if (TempChr < 62)  TempChr = TempChr - 36 + 'a';
            else if (TempChr == 62)  TempChr = '_';
            else  TempChr = '-';

            Dest[x] = (char)TempChr;
        }
    }

    return (SrcSize < DestSize ? SrcSize : DestSize);
}

Ini mungkin memiliki lebih banyak tabrakan daripada yang diinginkan tetapi tidak dimaksudkan untuk digunakan sebagai fungsi hash kriptografi. Anda dapat mencoba berbagai pengali (yaitu mengubah 37 ke bilangan prima lain) jika Anda mendapatkan terlalu banyak tabrakan. Salah satu fitur menarik dari potongan ini adalah ketika Src lebih pendek dari Dest, Dest berakhir dengan string input apa adanya (0 * 37 + nilai = nilai). Jika Anda menginginkan sesuatu yang "dapat dibaca" di akhir proses, Normalisasi akan menyesuaikan byte yang diubah dengan biaya meningkatkan tabrakan.

Sumber:

https://github.com/cubiclesoft/cross-platform-cpp/blob/master/sync/sync_util.cpp