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

98

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.

rath3r
źródło
To się nazywa haszysz. To nie będzie wyjątkowe.
Slaks
1
Jest to również problem z obcinaniem skrótu , więc zobacz także stackoverflow.com/q/4784335
Peter Krauss
2
FYI, zobacz listę funkcji skrótu w Wikipedii.
Basil Bourque

Odpowiedzi:

78

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'
Greg Hewgill
źródło
3
Każda rozsądna funkcja skrótu może zostać obcięta.
Prezydent James K. Polk
89
czy nie zwiększyłoby to w znacznie większym stopniu ryzyka kolizji?
Gabriel Sanmartin
143
@erasmospunk: kodowanie z base64 nie robi nic dla odporności na kolizje, ponieważ jeśli hash(a)zderza się z, hash(b)to base64(hash(a))również zderza się z base64(hash(b)).
Greg Hewgill
56
@GregHewgill masz rację, ale nie mówimy o zderzaniu się oryginalnego algorytmu wyznaczania wartości skrótu (tak, kolizje, sha1ale to już inna historia). Jeśli masz 10-znakowy hash, otrzymasz wyższą entropię, jeśli jest zakodowana za pomocą base64vs base16(lub hex). Jak wyżej? Z base16ciebie dostać 4 bitów informacji na znak, ze base64ta jest 6bits / char. Łącznie 10-znakowy hash „hex” będzie miał 40 bitów entropii, a base64 60 bitów. Więc jest trochę bardziej odporny, przepraszam, jeśli nie byłem super jasny.
John L. Jegutanis
20
@erasmospunk: Och, rozumiem, co masz na myśli, tak, jeśli masz ograniczony stały rozmiar wyniku, możesz spakować bardziej znaczące bity z kodowaniem base64 w porównaniu z kodowaniem szesnastkowym.
Greg Hewgill
46

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/

BT
źródło
2
jest bardzo stary, niezbyt niezawodny.
Mascarpone
1
@Mascarpone „niezbyt wiarygodne” - źródło? Ma ograniczenia, jeśli je znasz, nie ma znaczenia, ile ma lat.
BT
8
@Mascarpone "mniej słabości" - znowu, jakie słabości? Jak myślisz, dlaczego ten algorytm nie jest w 100% idealny do użycia przez OP?
BT,
3
@Mascarpone OP nie mówi, że chce hash klasy kryptograficznej. OTOH, Adler32 jest sumą kontrolną, a nie hashem, więc może nie być odpowiedni, w zależności od tego, co faktycznie z nim robi OP.
PM 2Ring
2
Adler32 ma jedno zastrzeżenie, cytując Wikipedię : Adler-32 ma słabość do krótkich wiadomości z kilkuset bajtami, ponieważ sumy kontrolne tych wiadomości mają słabe pokrycie 32 dostępnych bitów.
Basil Bourque
13

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.

Jan
źródło
1
Czy CRC'owanie skrótu SHA-1, a następnie base-64'owanie wyniku sprawia, że ​​wynikowy identyfikator jest bardziej odporny na kolizje?
5
„Jednak twoja obawa, że ​​hash nie będzie podobny dla dwóch kolejnych wiadomości [...] powinna być prawdziwa dla wszystkich hashów”. - To niekoniecznie prawda. Na przykład w przypadku funkcji skrótu, które są używane do grupowania lub wykrywania klonów, jest dokładnie odwrotnie: chcesz , aby podobne dokumenty dawały podobne (lub nawet takie same) wartości skrótu. Dobrze znanym przykładem algorytmu wyznaczania wartości skrótu, który został specjalnie zaprojektowany w celu uzyskania identycznych wartości dla podobnych danych wejściowych, jest Soundex.
Jörg W Mittag
Używam skrótów do uwierzytelniania podpisu wiadomości. Zasadniczo więc dla znanej wiadomości i określonego podpisu skrót musi być poprawny. Nie obchodzi mnie jednak, czy byłby mały procent fałszywych alarmów. To jest całkowicie do przyjęcia. Obecnie używam obciętego skrótu SHA-512 skompresowanego za pomocą base62 (coś, co szybko zebrałem) dla wygody.
@ JörgWMittag Doskonały punkt na SoundEx. Poprawiono mnie. Nie wszystkie skróty mają te same cechy.
John
12

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.

JJ Geewax
źródło
7

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.

dynamichael
źródło
2
FWIW, to jest znane jako składanie XOR.
PM 2Ring
7

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 .

sg7
źródło
6

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

crc32 <(echo "some string")

Długość 8 znaków.

sgon00
źródło
4

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 .

feran
źródło
1

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

~ echo test | xxhsum                                                           
2d7f1808da1fa63c  stdin
sorbet
źródło
Ten link jest uszkodzony. lepiej udzielić pełniejszej odpowiedzi.
eri0o
0

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

CubicleSoft
źródło
std :: hash nie rozwiązuje niektórych przypadków użycia (np. unikanie przeciągania rozdętego std :: templates, gdy wystarczy kilka dodatkowych linii kodu). Nie ma tu nic głupiego. Został dokładnie przemyślany, aby poradzić sobie z poważnymi ograniczeniami w systemie Mac OSX. Nie chciałem liczby całkowitej. W tym celu mogłem użyć djb2 i nadal unikać używania std :: templates.
CubicleSoft
To wciąż brzmi głupio. Dlaczego miałbyś kiedykolwiek używać DestSizewięcej niż 4 (32 bity), skoro sam hash jest tak kiepski? Jeśli chcesz, aby odporność na kolizje zapewniana przez wyjście większe niż int, użyłabyś SHA.
Navin
Słuchaj, to naprawdę nie jest tradycyjny haszysz. Ma przydatne właściwości, w których użytkownik może zadeklarować rozmiar ciągu w miejscach, w których jest bardzo ograniczona przestrzeń bufora w niektórych systemach operacyjnych (np. Mac OSX) ORAZ wynik musi mieścić się w ograniczonej domenie rzeczywistych nazw plików ORAZ nie chcą po prostu skracać nazwa, ponieważ to POWODUŁO kolizje (ale krótsze struny zostaną pozostawione same). Hash kryptograficzny nie zawsze jest właściwą odpowiedzią, a std :: hash również nie zawsze jest właściwą odpowiedzią.
CubicleSoft