Kryptoanaliza Brute Force.

Następną rzeczą, na którą warto zwrócić uwagę na szyfr Cezara, jest to, że używając alfabetu angielskiego istnieje 26 możliwych kluczy. Oznacza to, że ktoś przechwytujący zaszyfrowaną wiadomość mógł zamontować standardową formę ataku znaną jako kryptoanaliza brutalna. Ta metoda uruchamia możliwe klucze za pomocą algorytmu deszyfrowania do czasu znalezienia rozwiązania. Statystycznie rzecz biorąc, właściwy klucz zostaje osiągnięty po przetestowaniu tylko połowy wszystkich możliwych kluczy. W

tabela arkusza kalkulacyjnego wyszczególnia atak brute force na szyfrogram Caesara. W tym przykładzie tekst jawny pojawia się w wierszu 6, klucz nr 3. Pamiętaj, że do ataku są wymagane trzy informacje, a wszystkie trzy są odpowiednie do szyfrowania na komputerach osobistych:

1. Znajomość zastosowanego algorytmu szyfrowania

2. Liczba możliwych kluczy

3. Język tekstu jawnego

Korzystanie z komputera w biurze nieco odbiega od wysyłania wiadomości na polu bitwy (przynajmniej w dobrym dniu). W przeciwieństwie do szpiega wroga, ktoś, kto próbuje uzyskać nieautoryzowany dostęp do danych, ma już dość dobre pojęcie o tym, który algorytm jest używany. (Jest ich stosunkowo niewiele i często są bezpośrednio związane z konkretnymi aplikacjami). Zajmuje się pierwszym elementem. Podstawową przeszkodą w ataku z użyciem siły jest drugi element, liczba kluczy. W przypadku szyfru Caesara liczba możliwych kluczy jest stosunkowo niewielka, a więc praca związana z przenoszeniem że atak może zostać zakończony bardzo szybko, co jest bardzo znaczące. Czas jest często najważniejszym czynnikiem w praktycznym kryptoanalizie. Możliwość odszyfrowania wiadomości w ciągu 24 godzin jest mało przydatna, jeśli informacje dotyczą zdarzeń mierzonych w minutach, takich jak zamówienia na zakup i sprzedaż akcji lub uruchomienie nalotów. Jeśli szyfr składa się w całości z przypadkowych substytucji listowych, takich jak to:

Plaintext: abcdefghijklmnopqrstuvwxyz

Tekst zaszyfrowany: UTWFRAQOYSEDCKJVBXGZIPHLNM

Liczba możliwych kluczy (przestrzeń kluczy) wynosi teraz 26 !, czyli ~ 4,03 × 1026, co wygląda na jeszcze bardziej zniechęcające, gdy jest napisane:

403 291 461 126 606 000 000 000 000

Wyobraźmy sobie brutalny atak siłowy przy użyciu komputera, który może wykonać 1 milion odszyfrowania na mikrosekundę (znacznie więcej chrupania numerów niż przeciętny komputer osobisty może wykonać). Korzystanie z pojedynczego procesora może zająć ponad 10 milionów lat, aby wykonać brutalny atak na ten kod. Na szczęście dla łamacza kodu istnieją inne sposoby łamania szyfrów zastępczych, jak to omówiono za chwilę. Chodzi o to, że podczas gdy ataki brutalną siłą są możliwe, nie zawsze są one praktyczne. Chociaż prawdą jest, że przez centralne twierdzenie graniczne statystyki, najbardziej prawdopodobna liczba prób wymaganych do trafienia na prawidłowy klucz stanowi połowę całkowitej przestrzeni kluczy, średnia redukcja o współczynnik 2 jest znikoma w obliczu okresów obliczeniowych mierzony w latach i trudność w rozpoznawaniu jasnego tekstu w bagnie niewłaściwych odszyfrowań. Funkcjonalnie ataki typu brute force zależą od tego, który algorytm szyfrowania znajduje się za zaszyfrowanym tekstem. W praktyce zależą one od wykonalności sukcesów w odpowiednim czasie. Zależą one również od trzeciej informacji z powyższej listy: znajomość języka tekstu zwykłego. Rozwiązanie szyfru Caesar w Exhibit 7.5 ma tendencję do wyskakiwania, ponieważ jest bliższe zwykłemu angielskiemu niż jakiekolwiek inne rozwiązanie. Jednak bez znajomości tego, co stanowi tekst jawny, a brutalny atak siłowy będzie w najlepszym razie nieefektywny, aw najgorszym razie nieskuteczny. Ta część kryptoanalizy, rozpoznająca wynik pozytywny, jest mniej podatna na automatyzację niż jakakolwiek inna. Trudność jest potęgowana przez szyfrowanie czysto liczbowych wyników, gdzie poprawny tekst jawny może być niemożliwy do ustalenia bez rozległej dodatkowej wiedzy.

Monoalfabetyczny szyfr zastąpieniowy.

Zarówno szyfr cezara, jak i losowy szyfr zastępczy są przykładami szyfrów monoalfabetycznych. Oznacza to, że jedna litera zaszyfrowanego tekstu oznacza jedną literę tekstu zwykłego. Powoduje to, że takie kody podatne na atak różnią się od brutalnej siły. Przypuśćmy, że funkcjonariusz celny spróbuje odkryć, kiedy i jak nielegalna dostawa broni wejdzie do kraju. Następująca wiadomość jest przechwytywana:

YZYGJ KZORZ OYXZR RKZRK XUXRJ XRZXU YKQQQ

Osoba, która zakodowała ten tekst, wyraźnie zastąpiła nowe litery oryginalnych liter wiadomości. Dla doświadczonego łamacza kodów lub kryptoanalityka zadanie odszyfrowania tej wiadomości jest dość proste. Najpierw policz ile razy pojawia się każda litera w tekście. W ten sposób powstaje lista taka jak ta:

Tekst zaszyfrowany: R Z X Y K J U O G

Częstotliwość: 6 6 5 4 4 2 2 2 1

Zwróć uwagę, że ostatnie trzy litery są dyskontowane, ponieważ są po prostu wypełnianiem grupowania pięciu liter. Następnie odwołaj się do tabeli częstotliwości, która pokazuje względną częstotliwość, z jaką litery alfabetu występują w określonym języku lub dialekcie tego języka. Jedna taka lista jest pokazana w

 

Ta lista została stworzona dla tego przykładu i proponuje, że najczęściej używanymi literami w języku angielskim w malejącej kolejności częstotliwości są e, t, r i tak dalej. Rzeczywista kolejność to prawdopodobnie e, t, a, i, o, n, s, h, r, d, l, u, kolejność kluczy na angielskiej maszynie Linotyp z XIX wieku, chociaż dokładna kolejność częstotliwości mogą się różnić w zależności od regionu pochodzenia lub przedmiotu tekstu.

Zakładając, że oryginalna wiadomość jest w języku angielskim, łatwo można uzyskać listę, która dopasowuje litery kodów do liter w postaci zwykłego tekstu.

Tekst zaszyfrowany: R Z X Y K J U O G

Częstotliwość: 6 6 5 4 4 2 2 2 1

Prosty tekst: e t r i n o h s

Wynik to:

Tekst zaszyfrowany: YZYGJ KZORZ OYXZR RKZRK XUXRJ XRZXU YKQQQ

Plaintext: itiso nthet hirte enten rareo retra inqqq Można to odczytać jako “znajduje się na trzynastce dziesięciu rzadkich pociągów rudy”. Chociaż ten przykład był oczywiście wymyślony, by to podkreślić, wyraźnie ilustruje ważne narzędzie kryptograficzne, które może szybko odszyfrować coś, co na pierwszy rzut oka wydaje się bardzo nieprzyjemne. Szyfrowanie w poprzednim przykładzie mogło być oparte na prostym szyfrze zastępowania. Na przykład po użyciu hasła “TRYB”, po którym następuje zwykły

alfabet, bez liter w haśle dla zwykłego tekstu, zaszyfrowany tekst jest alfabetem zapisanym wstecz:

Plaintext: TRICKABDEFGHJLMNOPQSUVWXYZ

Tekst zaszyfrowany: ZYXWVUTSRQPONMLKJIHGFEDCBA

Analiza częstotliwości działa również, jeśli podstawienie jest całkowicie losowe, tak jak w przykładzie pokazanym wcześniej, którego klucz jest całkowicie losowy. Specjalistyczne narzędzia, takie jak tablice częstotliwości, które są wymagane do łamania kodów, wskazują na podstawowy kompromis: jeśli wymagany jest podstawowy poziom ochrony, łatwo jest go uzyskać, ale także łatwo go złamać, przynajmniej dla eksperta. Kwalifikacja “dla eksperta” jest ważna, ponieważ użytkownicy szyfrowania muszą zachować swoją rolę w perspektywie. Najważniejsze pytania to: Kto może zyskać dzięki odszyfrowaniu danych i jakie środki mają do dyspozycji? Nie ma sensu inwestowanie w potężny sprzęt lub oprogramowanie szyfrujące, jeśli ci próbują czytać

Twoje pliki nie są szczególnie wyrafinowane, dedykowane lub dobrze wyposażone. Na przykład osoba, która wysyła pocztówkę, wie, że może ją przeczytać każdy, kto ją zobaczy. Do tego celu można wykorzystać koperty, które nie są ostateczną poufnością, ale są szeroko stosowane i stosunkowo udane.

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *