Strona główna

Algorytm sha-1 Cyfrowy odcisk palca


Pobieranie 32.99 Kb.
Data18.06.2016
Rozmiar32.99 Kb.

Algorytm SHA-1 Cyfrowy odcisk palca


Jedną z popularnych technik szyfrowania danych jest algorytm SHA-1. Przedstawimy jego przykładową implementację w C++. SHA-1 (Secure Hash Algorithm) pozwala na obliczenie tzw. odcisku wiadomości (message digest), będącego skondensowaną reprezentacją kodowanej informacji (np. tekstu lub pliku). Z danego ciągu bitów o wielkości mniejszej niż 264, SHA-1 oblicza 160-bitowy wynik ­ wspomniany odcisk. Pierwowzorem tego algorytmu był SHA, w którym zaraz po jego wprowadzeniu wykryto poważną lukę w bezpieczeństwie. W wyniku wprowadzonych modyfikacji, polegających na dodaniu w jednym miejscu operacji przesunięcia kołowego, powstał SHA-1.



Sposób weryfikacji autentyczności cyfrowego podpisu wiadomości

SHA-1 (RFC)

Standard opisany w dokumencie FIPS PUB 180-1 security.isu.edu/...

Oprócz SHA-1 wykorzystywane są również inne algorytmy mieszające (hashing algorithm) ­ MD2, MD4 i MD5, które obliczają 128-bitowy odcisk wiadomości. SHA-1 jest najnowszym z nich wszystkich ­ powstał w 1995 roku. W porównaniu z algorytmami MD (Message Digest) słabą stroną SHA-1 jest mniejsza szybkość kodowania ­ na komputerze z procesorem Pentium 800 MHz kodowanie MD4 i MD5 przeprowadzane jest z szybkością 10,5 MB/s, natomiast SHA-1 charakteryzuje się wydajnością 8,5 MB/s. Spowodowane jest to tym, że odcisk uzyskany za pomocą SHA-1 ma 160 bitów. Jednak dzięki tym 160 bitom SHA-1 jest w znacznie mniejszym stopniu podatny na ataki typu brute-force niż algorytmy MD. Ponadto w MD4 i MD5 znaleziono luki pozwalające na obliczenie kolizji, a więc zaistnienie sytuacji, kiedy z dwóch różnych wiadomości powstaje ten sam odcisk. Spośród algorytmów MD najbezpieczniejszym, ale też najwolniejszym jest MD2.



Schemat bezpiecznego przesyłania haseł w Sieci

Bezpieczny algorytm mieszający, a za taki jest uznawany SHA-1, powinien spełniać następujące warunki:



  • zmiana każdego z bitów kodowanej informacji wpływa na każdy bit odcisku;

  • przy zmianie pojedynczego bitu informacji każdy z bitów odcisku może się zmienić z prawdopodobieństwem 0,5;

  • mając daną wiadomość i jej odcisk, znalezienie innej wiadomości o identycznym odcisku powinno być nie do obliczenia.

SHA-1 ma wiele zastosowań, charakterystyczne dwa to:

  • algorytm DSA (Digital Signature Algorithm) ­ generuje i weryfikuje cyfrowy podpis odcisku wiadomości (odcisk jest zwykle znacznie mniejszy od wiadomości, dzięki czemu wzrasta znacznie wydajność DSA);

  • bezpieczne przesyłanie haseł w sieci ­ klient po podaniu serwerowi nazwy użytkownika otrzymuje od niego losowy łańcuch, który jest łączony razem z hasłem. Z powstałej kombinacji obliczany jest za pomocą SHA-1 odcisk wiadomości. Odcisk ten jest przesyłany do serwera, który porównuje go z odciskiem wygenerowanym przez siebie na podstawie hasła odpowiadającego danemu użytkownikowi. Przy każdym logowaniu przesyłany odcisk będzie inny, tak więc przechwycenie go będzie bezużyteczne ­ nie pozwoli na bezśladowe dokonanie zmiany w przesyłanej informacji.
Definicje

Zanim przedstawię algorytm SHA-1 i jego implementację w C++, wyjaśnię kilka pojęć i operacji:

  • /\ (AND), \/ (OR), NOR oraz "~" (NOT) ­ operatory binarne, które zostaną użyte w naszym przykładzie;

  • słowo - ciąg 32 bitów, reprezentujący liczbę całkowitą X, która spełnia warunek: 0 < X <= 232

  • blok ­ 16 słów, czyli 512 bitów;

  • operator "+" ­ w algorytmie SHA operacja X + Y, gdzie X i Y to słowa, daje rezultat Z, będący również słowem. Niech x oraz y będą liczbami całkowitymi (32-bitowymi), wtedy
    z = (x + y) mod 232, następnie zamieniamy z na słowo i otrzymujemy Z.

W systemach, gdzie typ unsigned long jest 32-bitowy działanie "+" wykonywane jest standardowym operatorem dodawania (+). Jeśli jednak typ ten prezentowany jest za pomocą większej liczby bitów, wtedy należy zastosować maskowanie wszystkich bitów z wyjątkiem 32 najmłodszych:

unsigned long x, y, z;

z = (x + y) & 0xFFFFFFFF;

Sn(X) ­ operacja przesunięcia kołowego, gdzie X jest słowem, zaś n liczbą całkowitą z zakresu 0 <= n < 32, jest definiowana następująco:

Sn(X) = (X << n) ( (X >> 32 ­ n)

W C++ służy do tego celu funkcja z biblioteki stdlib.h:

unsigned long _lrotl(unsigned long val, int count);


  • funkcja ft(B,C,D) dla słów B, C, D i 0 <= t <= 79 ­ zwraca 32-bitowe słowo:

(0 <= t <= 19) ­ ft(B,C,D) = (B /\ C) \/ (~B /\ D)

(20 <= t <= 39) ­ ft(B,C,D) = B XOR C XOR D

(40 <= t <= 59) ­ ft(B,C,D) = (B /\ C) \/ (B /\ D) \/ (C /\ D)

(60 <= t <= 79) ­ ft(B,C,D) = B XOR C XOR D


unsigned long TSHA1::BCD(unsigned long B, unsigned long C, unsigned long D, int t) {

if (t > 59) return B /\ C /\ D;

else if (t > 39) return (B & C) | (B & D) | (C & D);

else if (t > 19) return B /\ C /\ D;

else return (B & C) | (~B & D);

}
W przykładowym algorytmie użyta zostanie sekwencja stałych K będących słowami:


TSHA1::TSHA1()

{

//wypełnienie tablicy stałych K



for (int i = 0; i < 80; i++)

if (i > 59) K[i] = 0xCA62C1D6;

else if (i > 39) K[i] = 0x8F1BBCDC;

else if (i > 19) K[i] = 0x6ED9EBA1;

else K[i] = 0x5A827999;

}

Implementacja


Utworzymy klasę TSHA1 udostępniającą funkcję GetDigest, która zwróci wskaźnik do tablicy zawierającej pięć słów reprezentujących 160-bitowy odcisk przekazanej wiadomości (msg):

class TSHA1

{

...


public:

unsigned long * GetDigest(char * msg, unsigned long length);

};

Do obliczeń potrzebne będą dwa bufory liczące po pięć słów: A, B, C, D, E oraz H0, H1, H2, H3, H4, jeden liczący 80 słów: W0, W1 ... W79, a także bufor TEMP na jedno słowo.



Przed rozpoczęciem przetwarzania wiadomości bufor H należy wypełnić:

H[0] = 0x67452301;

H[1] = 0xEFCDAB89;

H[2] = 0x98BADCFE;

H[3] = 0x10325476;

H[4] = 0xC3D2E1F0;

SHA-1 przetwarza 512-bitowe bloki, więc wiadomość musi zostać uzupełniona, tak aby jej rozmiar (w bitach) był wielokrotnością 512. Reguła jest taka, że najpierw dodawana jest jedynka, następnie ciąg zer o zmiennej długości. Ostatnie 64 bity ostatniego bloku są zarezerwowane dla długości oryginalnej wiadomości (przed dopełnieniem) ­- patrz listing:

void TSHA1::ProcessMessage(char * message, unsigned long length)

{

for (int x = 0; x < length / 64; x++) ProcessBlock(message + x * 64);



byte pad[128];

byte *temp = &pad[0];

message += (length / 64) * 64;

for (int i = 0; i < length % 64; i++) *(temp++) = (byte) *(message++);

//Dodajemy jedynkę i siedem zer (128 = 10000000)

*(temp++) = 128;

//Dodajemy ciąg zer

int blocks;

if (length % 64 >= 56)

{

for (int i = 0; i < 59 ­ length % 64 + 64; i++) *(temp++) = 0;



blocks = 2;

}

else



{

for (int i = 0; i < 59 ­ length % 64; i++) *(temp++) = 0;

blocks = 1;

}

//Dodajemy 32-bitowe słowo określające długość kodowanego



//tekstu (jest to uproszczenie, ponieważ powinny być 64 bity

//określające rozmiar wiadomości, ale 32 wystarczą dla

//rozmiaru < 4294967296 bitów)

*(temp++) = ((8 * length) >> 24) & 0xFF;

*(temp++) = ((8 * length) >> 16) & 0xFF;

*(temp++) = ((8 * length) >> 8) & 0xFF;

*(temp++) = (8 * length) & 0xFF;

temp = &pad[0];

for (int x = 0; x < blocks; x++) ProcessBlock(temp);

}
void TSHA1::ProcessBlock(byte *pointer)

{

//umieszczamy blok w pierwszych szesnastu słowach bufora W



for (int i = 0; i < 16; i++)

{

W[i] = ((unsigned long) *(pointer++) ź 24);



W[i]|= ((unsigned long) *(pointer++) ź 16);

W[i]|= ((unsigned long) *(pointer++) ź 8);

W[i]|= (unsigned long) *(pointer++);

}

for (int t = 16; t < 80; t++)



W[t] = _lrotl(W[t-3] /\ W[t-8] /\ W[t-14] /\ W[t-16], 1);

A = H[0];

B = H[1];

C = H[2];

D = H[3];

E = H[4];

for (int t = 0; t < 80; t++)

{

TEMP = _lrotl(A, 5) + BCD(B, C, D, t) + E + W[t] + K[t];



E = D;

D = C;


C = _lrotl(B, 30);

B = A;


A = TEMP;

}

H[0] = H[0] + A;



H[1] = H[1] + B;

H[2] = H[2] + C;

H[3] = H[3] + D;

H[4] = H[4] + E;

}
Po przetworzeniu wszystkich bloków 160-bitowy odcisk wiadomości jest reprezentowany przez pięć słów: H0, H1, H2, H3, H4.

Aby przedstawić odcisk w postaci szesnastkowej wykorzystajmy funkcję IntToHex:


AnsiString HexDigest(unsigned long *digest)

{

AnsiString hex = IntToHex((__int64) digest [0], 8) +



IntToHex((__int64) digest [1], 8) +

IntToHex((__int64) digest [2], 8) +

IntToHex((__int64) digest [3], 8) +

IntToHex((__int64) digest [4], 8);

return hex;

}
Istnieje alternatywny sposób obliczenia odcisku wiadomości, wykorzystuje on jedynie bufor 16 słów. Oszczędza się w ten sposób pamięć, jednakże kosztem wydłużenia czasu obliczeń. Polecany jest jedynie w przypadkach, gdy liczy się każdy bajt pamięci.




str.




©snauka.pl 2016
wyślij wiadomość