Obliczanie sum kontrolnych SHA-1

mnbvcX

SHA-1 jest algorytmem stworzonym w 1995 roku ze względu na wykryte luki swojego poprzednika, SHA-0.

1. Algorytm

1.1. Używane funkcje

Algorytm SHA-1 używa jedynie:

  • dodawanie,
  • iloczyn bitowy (and, &)
  • sumę bitową (or, |)
  • działanie xor (^)
  • rotację bitową.
    Pierwsze cztery działania można zostawić bez komentarza. Warto jednak omówić rotację bitową.
  • W rotacji bitowej w prawo (w Assemblerze instrukcja ROR) ostatni bit po prawej przechodzi na lewą stronę, a wszystkie pozostałe bity przesuwają się o pozycję w prawo.
  • W rotacji bitowej w lewo (ROL) jest na odwrót: ostatni bit po lewej przechodzi na prawą stronę, a wszystkie pozostałe bity przesuwają się o pozycję w lewo.
    Czynność tę należy wykonać odpowiednią ilość razy.

Rotację w prawo przedstawia rysunek:
sha1_csr.gif

Nasza definicja rotacji w lewo przedstawia się następująco:

#define rol(x,n) ((x << n) | (x >> (32-n)))

1.2. Podział na bloki

Pierwszym etapem hashowania jest podział na bloki. Aby go wykonać, powinniśmy:

  1. Zamienić wiadomość na postać binarną.
  2. Na końcu wiadomości dodać bit o wartości 1.
  3. Dopisać na końcu tyle zer, aby długość wiadomości modulo 512 wynosił 448. Przykładowo, jeżeli wiadomość (z bitem 1) ma długość 5001 bitów (wraz z bitem o wartości 1), powinniśmy wydłużyć ją do długości 5056 bitów (bo 5056 % 512 = 448).
  4. Dopisać na końcu wiadomości 64-bitową liczbę oznaczającą długość pierwotnej wiadomości.
  5. Podzielić ciąg na 512-bitowe bloki.

Przykład działania:
1010100000000001101111111111110101001010100101010100101001010101111111101010101
0011111111010100101001010100010101010101001010101111101001101010101110101001100
1010101000000000001111111111101010100101001010100000010000000001111101010101111
1111111111111111010010101001010100111010010101010111110101011001000100000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000
00000000000000000000000000
00000000000000000000000000000100110000

Gdzie kolory to:

  • Pierwotny ciąg
  • Bit o wartości 1
  • Wypełniacz
  • Długość wiadomości

1.3. Główne działania

Potrzebne będą liczby 32-bitowe bez znaku: h0, h1, h2, h3, h4, a, b, c, d, e, tmp, f, k oraz tablica 80-elementowa w.

Na początku inicjujemy 5 zmiennych - każda to część wyjścia. Inicjujemy je łączną wartością 0x0123456789ABCDEFFEDCBA9876543210F0E1D2C3:

h0 = 0x67452310;
h1 = 0xEFCDAB89;
h2 = 0x98BADCFE;
h3 = 0x10325476;
h4 = 0xC3D2E1F0;

Teraz wykonujemy działania dla każdego 512-bitowego bloku.

  • Dzielimy blok na szesnaście 32-bitowych słów i zapisujemy je do w[0], w[1], ..., w[15].
  • Rozszerzamy ilość słów z 16 do 80, wykonując działanie dla każdego 15 < i < 80:
    w[i] = rol((w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]), 1);
  • Tworzymy zmienne a, b, c, d, e o wartościach h0, h1, h2, h3, h4.
  • Główna pętla (dla każdego 0 ≤ i ≤ 79):
    • Jeżeli 0 ≤ i ≤ 19:
      f = (b & c) | ((~b) & d);
      k = 0x5A827999;
    • Jeżeli 20 ≤ i ≤ 39:
      f = b ^ c ^ d;
      k = 0x6ED9EBA1;
    • Jeżeli 40 ≤ i ≤ 59:
      f = (b & c) | (b & d) | (c & d);
      k = 0x8F1BBCDC;
    • Jeżeli 60 ≤ i ≤ 79:
      f = b ^ c ^ d;
      k = 0xCA62C1D6;
    • Następnie:
      tmp = rol(a, 5) + e + f + k + w[i];
      e = d;
      d = c;
      c = rol(b, 30);
      b = a;
      a = tmp;
  • Zwiększamy wartość zmiennych h0..h4:
    h0 += a;
    h1 += b;
    h2 += c;
    h3 += d;
    h4 += e;

    Wynik to połączone ze sobą szesnastkowe przedstawienia zmiennych h0..h4.

Wartości 5A827999, 6ED9EBA1, 8F1BBCDC, CA62C1D6 to części całkowite z 2^{30}\sqrt{x} dla x = {2, 3, 5, 10}.

2. Implementacja w C/C++

Poniższa implementacja oblicza sumę kontrolną SHA-1 pliku. W pewnym stopniu oparty jest na stronie: http://www.hoozi.com/Articles/SHA1_Source.htm .

/* natchnione stroną:
www.hoozi.com/Articles/SHA1_Source.htm */
 
#include <iostream> 
 
#define rol(x,n) ((x << n) | (x >> (32-n)))  
 
char SHA1_result[50];
 
void block(unsigned char* str, unsigned long &h0, unsigned long &h1, //obliczenia na każdym bloku
            unsigned long &h2, unsigned long &h3, unsigned long &h4){
    unsigned long w[80], a, b, c, d, e, k, f, tmp; //zmienne
    for(int j = 0; j < 16; j++){  
        w[j] = str[j*4 + 0] * 0x1000000 //ustawianie szesnastu 32-bitowych słów
         + str[j*4 + 1] * 0x10000
         + str[j*4 + 2] * 0x100
         + str[j*4 + 3];
    }  
    for(int j = 16; j < 80; j++){ //rozszerzanie szesnastu słów do osiemdziesięciu
        w[j] = rol((w[j-3] ^ w[j-8] ^ w[j-14] ^ w[j-16]),1);  
    }  
 
        a = h0;  //inicjalizacja a,b,c,d,e
        b = h1;  
        c = h2;  
        d = h3;  
        e = h4;  
 
        for(int m=0;m<80;m++){  //działania...
            if(m <= 19){  
                f = (b & c) | ((~b) & d);  
                k = 0x5A827999;  
            } else if(m <= 39){  
                f = b ^ c ^ d;  
                k = 0x6ED9EBA1;  
            } else if(m <= 59){  
                f = (b & c) | (b & d) | (c & d);  
                k = 0x8F1BBCDC;  
            } else {  
                f = b ^ c ^ d;  
                k = 0xCA62C1D6;   
            }  
 
            tmp = (rol(a,5) + f + e + k + w[m]) & 0xFFFFFFFF;  
            e = d;  
            d = c;  
            c = rol(b,30);  
            b = a;  
            a = tmp;  
        }  
 
        h0 = h0 + a;  //przypis wartości h0..h4
        h1 = h1 + b;  
        h2 = h2 + c;  
        h3 = h3 + d;  
        h4 = h4 + e;    
}
 
void sha1file(char* filename){
    //otwieramy plik
    FILE *f;
    f = fopen(filename, "rb");
    if(f != NULL){
        //tworzymy zmienne
        char buffer[65];
        unsigned long h0, h1, h2, h3, h4;
            h0 = 0x67452301;  
            h1 = 0xEFCDAB89;  
            h2 = 0x98BADCFE;  
            h3 = 0x10325476;  
            h4 = 0xC3D2E1F0; 
 
        //uzyskujemy rozmiar pliku
        fseek(f, 0, SEEK_END);
        unsigned long filesize = ftell(f);
        //wracamy na początek pliku
        rewind(f);
 
        //uzyskujemy liczbę 64-bajtowych (512-bitowych) bloków
        long blocks = filesize / 64;
        //uzyskujemy rozmiar ostatniego bloku
        long lastblock = filesize % 64;
        if(lastblock == 0){blocks--; lastblock = 64;}
 
        //przetwarzamy wszystkie bloki oprócz ostatniego
        for(int i = 0; i < blocks; i++){
            fread(buffer, 1, 64, f); //czytamy 64 bajty
            buffer[64] = '\0'; //dodajemy ostatni
            block((unsigned char*)buffer, h0, h1, h2, h3, h4); //uaktualniamy zmienne
        }
 
                /* Teraz musimy dodać do ostatniego bufora bit o wartości 1, wypełniacz i
                rozmiar badanego pliku.
                Jeżeli ów bufor ma mniej niż 56 znaków, możemy spokojnie do niego dodać
                bit o wartości 1, który z 7 bitami wypełniacza stworzy bajt o wartości 0x80.
                Niestety, jeżeli bufor ma więcej lub równo 56 bajtów (ale mniej niż 64), bit "1"
                zmieści się do bloku, ale długość pliku - już nie - będzie w kolejnym bloku.
                Przy 64 bajtach nawet ów bit się nie zmieści i musimy go przenieść
                do następnego bloku.*/
 
        if(lastblock < 56){ //jeżeli ostatni blok ma mniej niż 64 elementy
            for(int i = 0; i < 64; i++) buffer[i] = 0;
            fread(buffer, 1, lastblock, f); //to go czytamy do końca
            buffer[lastblock] = 0x80; //dodajemy bit o wartości 1 i siedem zer
        } else {  //inaczej
            for(int i = 0; i < 64; i++) buffer[i] = 0;
            fread(buffer, 1, lastblock, f); //czytamy go do końca
            if(lastblock < 64) buffer[lastblock] = 0x80;
            buffer[64] = '\0';
            block((unsigned char*)buffer, h0, h1, h2, h3, h4); //uaktualniamy hx
            for(int i = 0; i < 64; i++) buffer[i] = 0; //zerujemy blok
        }
        //dodajemy długość
        if(lastblock == 64) buffer[0] = 0x80;  //jeżeli ostatni blok był pełny, musimy bajt 1 zapisać do następnego
        filesize *= 8; //potrzebna nam długość pliku w bitach, nie bajtach
 
                /* Zapisujemy tylko 4 ostatnie znaki określające rozmiar; zakładamy, że
                plik nie ma więcej niż 2^32-1 bitów (ok. 0,5GB). Jeśli mamy zamiar sprawdzić
                większy plik (co jednak może trwać wieki :D), zmieniamy rozmiar zmiennej
                filesize na unsigned long long i zmieniamy odpowiednio wiersze. */
        buffer[60] = filesize / 0x1000000;
        buffer[61] = filesize % 0x1000000 / 0x10000;
        buffer[62] = filesize % 0x10000 / 0x100;
        buffer[63] = filesize % 0x100;
        buffer[64] = '\0';
        block((unsigned char*)buffer, h0, h1, h2, h3, h4); //uaktualniamy hx
        sprintf(SHA1_result, "%08x%08x%08x%08x%08x", h0, h1, h2, h3, h4); //tworzymy wynik
 
        //zamykamy zmienne
        fclose(f);
    } else {
        SHA1_result[0] = '-'; //jeśli wystąpił błąd, pierwszy znakiem jest kreska
    }
    //wynik jest w zmiennej globalnej SHA1_result
}
 
int main(){
    char filename[256];
    printf("Podaj nazwe pliku: ");
    scanf("%s", filename);       //wczytujemy nazwę pliku
    printf("\n\nsha1(%s) = ", filename);
    sha1file((char*)filename);     //obliczamy sumę kontrolną SHA-1
    if(SHA1_result[0] != '-'){      //jeżeli funkcja została ukończona poprawnie
        printf("%s\n\n", SHA1_result);   //wypisz wynik
    } else {
        printf("{Error: %s}\n\n", strerror(errno)); //inaczej wypisz błąd
    }
    return 0;
}

2 komentarzy

Ładny artykuł :)

if(lastblock < 56){ //jeżeli ostatni blok ma mniej niż 64 elementy

Mógłbyś wytłumaczyć ten fragment?? Linie 88-99. :)

I dlaczego długość pliku zapisujesz na 4 bajtach(buffer[60..63]) zamiast na 8 bajtach jak w opisie słownym algorytmu??

# Dopisać na końcu wiadomości 64-bitową liczbę oznaczającą długość pierwotnej wiadomości.

Wynik na Wyjściu jest dobry, ale nie czaje tych momentów. ;)