Funkcja skrótu, która generuje krótkie skróty?

Czy istnieje sposób szyfrowania, który może przyjąć ciąg dowolnej długości i wygenerować skrót poniżej 10 znaków? Chcę tworzyć w miarę unikalne identyfikatory, ale oparte na treści wiadomości, a nie losowo.

Mogę jednak żyć z ograniczaniem wiadomości do wartości całkowitych, jeśli ciągi o dowolnej długości są niemożliwe. Jednak w takim przypadku skrót nie może być podobny dla dwóch kolejnych liczb całkowitych.

Możesz użyć dowolnego powszechnie dostępnego algorytmu haszującego (np. SHA-1), który da ci nieco dłuższy wynik niż potrzebujesz. Po prostu przytnij wynik do żądanej długości, co może być wystarczająco dobre.

Na przykład w Pythonie:

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

Jeśli nie potrzebujesz algorytmu, który jest odporny na celowe modyfikacje, znalazłem algorytm o nazwie adler32, który daje dość krótkie (~ 8 znaków) wyniki. Wybierz go z menu rozwijanego, aby go wypróbować:

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

Musisz zaszyfrować zawartość, aby uzyskać skrót. Dostępnych jest wiele skrótów, ale 10 znaków to dość mało dla zestawu wyników. Dawno temu ludzie używali CRC-32, który generuje 33-bitowy hash (w zasadzie 4 znaki plus jeden bit). Istnieje również CRC-64, który generuje 65-bitowy hash. MD5, który generuje 128-bitowy skrót (16 bajtów / znaków), jest uważany za uszkodzony do celów kryptograficznych, ponieważ można znaleźć dwie wiadomości, które mają ten sam skrót. Powinno być oczywiste, że za każdym razem, gdy utworzysz 16-bajtowe podsumowanie z wiadomości o dowolnej długości, otrzymasz duplikaty. Im krótszy skrót, tym większe ryzyko kolizji.

Jednak obawa, że ​​hash nie będzie podobna dla dwóch kolejnych komunikatów (niezależnie od tego, czy są to liczby całkowite, czy nie), powinna być prawdziwa dla wszystkich skrótów. Nawet jedna drobna zmiana w oryginalnej wiadomości powinna skutkować bardzo odmiennym podsumowaniem.

Tak więc użycie czegoś takiego jak CRC-64 (i wynik bazowy-64) powinno znaleźć się w okolicy, której szukasz.

Podsumowując tylko odpowiedź, która była dla mnie pomocna (zwracając uwagę na komentarz @ erasmospunk o używaniu kodowania base-64). Moim celem było uzyskanie głównie krótkiego sznurka wyjątkowy ...

Nie jestem ekspertem, więc popraw to, jeśli zawiera jakieś rażące błędy (w Pythonie znowu jak zaakceptowana odpowiedź):

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='

resultTutaj używa więcej niż tylko znaki szesnastkowe (co można dostać, jeśli używanyhash.hexdigest() ), więc jest to mniej prawdopodobne, aby mieć kolizji (czyli powinno być bezpieczniej obciąć niż hex strawienia).

Uwaga: użycie UUID4 (losowe). Zobacz http://en.wikipedia.org/wiki/Universally_unique_identifier dla innych typów.

Możesz użyć istniejącego algorytmu skrótu, który tworzy coś krótkiego, na przykład MD5 (128 bitów) lub SHA1 (160). Następnie możesz to jeszcze bardziej skrócić, XORując sekcje skrótu z innymi sekcjami. Zwiększy to ryzyko kolizji, ale nie tak źle, jak zwykłe obcięcie skrótu.

Możesz również uwzględnić długość oryginalnych danych jako część wyniku, aby uczynić go bardziej unikalnym. Na przykład XORowanie pierwszej połowy skrótu MD5 z drugą połową dałoby 64 bity. Dodaj 32 bity na długość danych (lub mniej, jeśli wiesz, że długość będzie zawsze pasować do mniejszej liczby bitów). Dałoby to wynik 96-bitowy (12-bajtowy), który można następnie przekształcić w 24-znakowy ciąg szesnastkowy. Alternatywnie możesz użyć kodowania podstawowego 64, aby było jeszcze krótsze.

Jeśli potrzebujesz, "sub-10-character hash" możesz użyć algorytmu Fletcher-32 , który generuje 8 znaków hash (32 bity), CRC-32 lub Adler-32 .

CRC-32 jest wolniejszy od Adler32 o współczynnik 20% - 100%.

Fletcher-32 jest nieco bardziej niezawodny niż Adler-32. Ma niższy koszt obliczeniowy niż suma kontrolna Adlera: porównanie Fletchera i Adlera .

Przykładowy program z kilkoma implementacjami Fletchera jest podany poniżej:

    #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;
    }

Wynik:

4031760169 F04FC729                                                                                                                                                                                                                              
4031760169 F04FC729                                                                                                                                                                                                                              

1448095018 56502D2A                                                                                                                                                                                                                              
1448095018 56502D2A                                                                                                                                                                                                                              

Zgadza się z wektorami testowymi :

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

Adler-32 ma słabość do krótkich wiadomości zawierających kilkaset bajtów, ponieważ sumy kontrolne tych wiadomości mają słabe pokrycie 32 dostępnych bitów. Sprawdź to:

Algorytm Adler32 nie jest wystarczająco złożony, aby konkurować z porównywalnymi sumami kontrolnymi .

Po prostu uruchom to w terminalu (w systemie MacOS lub Linux):

crc32 <(echo "some string")

Długość 8 znaków.

Możesz użyć biblioteki hashlib dla Pythona. W shake_128 i shake_256 algorytmy zapewniają mieszań zmienne długości. Oto działający kod (Python3):

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

Zwróć uwagę, że z parametrem długości x (na przykład 5) funkcja zwraca wartość skrótu o długości 2x .

Jest teraz 2019 i są lepsze opcje. Mianowicie xxhash .

~ echo test | xxhsum                                                           
2d7f1808da1fa63c  stdin

Ostatnio potrzebowałem czegoś w rodzaju prostej funkcji redukcji strun. Zasadniczo kod wyglądał mniej więcej tak (kod C / C ++ z wyprzedzeniem):

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);
}

Prawdopodobnie ma więcej kolizji, niż mogłoby się wydawać, ale nie jest przeznaczony do użytku jako kryptograficzna funkcja skrótu. Możesz wypróbować różne mnożniki (np. Zmienić 37 na inną liczbę pierwszą), jeśli masz zbyt wiele kolizji. Jedną z interesujących cech tego fragmentu jest to, że gdy Src jest krótszy niż Dest, Dest kończy się ciągiem wejściowym takim, jakim jest (0 * 37 + wartość = wartość). Jeśli chcesz mieć coś „czytelnego” na końcu procesu, Normalize dostosuje przekształcone bajty kosztem rosnących kolizji.

Źródło:

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