1313878026

Złożoność metody łamania szyfru jest szacowana jako minimum z tych trzech miar. Niektóre metody łamania wymagają kompromisu pomiędzy tymi trzema miarami, np. łamanie jest szybsze, ale wymaga dużo więcej pamięci itp.

Złożoność jest określana jako rząd wielkości. Jeśli z jakimś algorytmem jest związana złożoność przetwarzania rzędu 2¹²⁸, to oznacza, że do złamania tego algorytmu trzeba wykonać 2 ²⁸ operacji, które mogą być złożone i czasochłonne. Dysponując procesorem, wykonującym milion operacji na sekundę, i stosując milion takich procesorów, nasze zadanie pochłonie 10¹⁹ lat, czyli miliard razy więcej niż wynosi wiek Wszechświata. Złożoność metody łamania, niezbędna do złamania danego algorytmu jest stała (oczywiście do czasu znalezienia lepszej metody łamania), ale moc obliczeniowa komputerów nie jest stała. Dlatego też twierdzenie, że algorytm jest bezpieczny, gdyż przy obecnych możliwościach przetwarzania danych nie można go złamać, jest ryzykowne - postęp w konstrukcji procesorów jest nadal bardzo szybki i trend ten najprawdopodobniej zostanie utrzymany. Dobre algorytmy są projektowane tak, aby nie można ich było złamać nawet dysponując przewidywanymi za wiele lat mocami obliczeniowymi.

8 Łamanie brutalne

Aby rozpocząć atak, kryptoanalityk potrzebuje tylko kryptogramu (nawet fragmentu kryptogramu). W przypadku szyfrów blokowych będzie niezbędny przynajmniej jeden blok kryptogramu. Zdobycie kryptogramu powinno być stosunkowo proste.

Dodatkowo warto uzyskać pewne informacje na temat struktury czy układu tekstu jawnego, co bardzo ułatwia łamanie (np. w przypadku łamania algorytmu XOR) - np. czy tekst jawny to plik Worda, plik graficzny JPG, standardowa wiadomość poczty elektronicznej, rekord bazy danych, plik spakowany algorytmem ZIP itp. Każdy z tych formatów danych ma pewne, charakterystyczne i ściśle określone bajty w określonych miejscach pliku, co znacznie ułatwia operację łamania szyfru, tak, że kryptoanalityk może wykorzystać te informacje w celu ograniczenia złożoności obliczeniowej łamania brutalnego. Jednak często kryptoanalityk dysponuje wyłącznie fragmentem (lub całością) kryptogramu i może wtedy zastosować wyłącznie łamanie brutalne.

Oszacowanie złożoności obliczeniowej łamania brutalnego jest łatwe. Jeśli klucz ma długość 8 bitów (1 bajt), to należy zbadać 2⁸ = 256 możliwych kluczy. Zatem przy 256 próbach jest pewność znalezienia klucza, przy szansie 50% na powodzenie przy połowie tej ilości prób. Jeśli klucz ma długość 56 bitów, to kombinacji jest 2, co przy sprawdzaniu miliona kluczy na sekundę daje 2 285 lat badania. Dla 64-bitowego klucza jest to już 585 000 lat, zaś dla klucza 128-bitowego 10²⁵ lat. Wiek Wszechświata szacowany jest tylko na 10¹⁰ lat, więc okres 10²⁵ lat prawdopodobnie zapewnia bezpieczeństwo. Przy kluczu 2048-bitowym milion komputerów, pracujących równolegle i badających po milionie kluczy na sekundę każdy, łamanie brutalne szyfru zajmie 10⁵⁹⁷ lat.

Należy jednak pamiętać, że algorytm musi być tak bezpieczny, by nie było innej metody jego złamania niż atak brutalny. Nie jest to tak łatwe, jak mogłoby się wydawać. Nawet algorytmy, które wydają się być doskonałe, często po pewnym czasie badań okazują się być skrajnie słabe. Dlatego też najlepiej jest ufać algorytmom, które są od wielu lat przedmiotem bezskutecznych badań kryptografów, natomiast z dystansem podchodzić do nowych algorytmów, reklamowanych jako najlepsze i nie do złamania.