Obliczanie sum kontrolnych SHA-1

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:


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

Kategoria: Algorytmy

2 komentarze

Avatar: Coldpeer
Napisany 2009-08-30 16:04 przez Coldpeer

Ładny artykuł :)

Brak avatara
Napisany 2010-01-20 00:55 przez morfeus

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

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??
<quote>#  Dopisać na końcu wiadomości 64-bitową liczbę oznaczającą długość pierwotnej wiadomości.</quote>

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

Facebook
4programmers.net