Zrób Sobie Firmę

Warto pokrótce poruszyć inny aspekt dotyczący kluczy publicznych: skąd wiemy, że klucz jest ważny? Głównym twierdzeniem dla systemów kluczy publicznych nad prywatnymi jest to, że zarządzanie kluczami staje się proste: nie musisz konfigurować bezpiecznego lub ukrytego kanału do przekazywania informacji o kluczach; po prostu je publikujesz lub dostarczasz na żądanie. Prawdziwe. Ale co się stanie, jeśli otrzymam klucz publiczny, który moim zdaniem należy do kogoś, ale w rzeczywistości należy do kogoś innego? Być może wysyłam duże kwoty płatności elektronicznych przez sieć, mając pewność, że nikt nie może ich przechwycić ani przekierować na konto strony trzeciej, ale skąd mam wiedzieć, że dokonuję płatności na właściwy osoby, a nie oszusta? Mogłem nawet zostać złapany w pułapkę użycia fałszywego klucza przestępcy do przesłania danych klucza do systemu klucza prywatnego, na przykład DES, który otwiera całe moje konto bankowe lub system komputerowy mojej firmy. To ponownie podkreśla różnicę między algorytmem bezpieczeństwa, który może być bezpieczny, nawet bezwarunkowo bezpieczny, a implementacją i aplikacją, które mogą prowadzić do poważnych naruszeń. Systemy kluczy publicznych mogły wyeliminować potrzebę bezpiecznego kanału do transportu kluczy; oznacza to, że usunęli potrzebę posiadania poufnego kanału. Ale zastąpili to potrzebą kanału, który może uwierzytelniać zestaw kluczy. Przyjęto różne podejścia, ale podstawowa zasada jest taka sama. W każdym przypadku potrzebna jest jakaś osoba lub organizacja kompetentna i chętna do zagwarantowania, że ​​klucze użyte do podpisania jakiegokolwiek dokumentu są ważne, w sensie przynależności do osoby, która ich żąda, oraz że dołożono wszelkich uzasadnionych starań, aby to zapewnić. gwarancja ma wartość. Co więcej, tej osobie lub organizacji muszą ufać wszystkie strony transakcji. To w jaki sposób rozwija się to zaufanie, powstają różnice. Odnosząc się konkretnie do kwestii, kto gwarantuje autentyczność klucza publicznego, przyjrzymy się teraz dwóm alternatywnym podejściom, które w równym stopniu opierają się na różnych postawach kulturowych, co na podejściu technicznym.

Optymiści i komercyjni oportuniści będą sugerować, że problem szyfrowania został mniej lub bardziej „rozwiązany” dzięki rozwojowi kryptografii klucza publicznego w ciągu ostatniego ćwierćwiecza. Oczywiście nigdy nie osiąga się prawie idealnego bezpieczeństwa, z wyjątkiem najbardziej trywialnych przypadków, ale istnieją pewne specyficzne problemy, które wciąż pozostają i co oznacza, że ​​nie możemy całkowicie zaufać systemom klucza publicznego. Niemniej jednak, proces jest osiągany w opracowaniu konsensusu i zestawu standardów dotyczących użycia klucza publicznego. Jedną z kwestii jest kwestia „silnych liczb pierwszych”, która nie tylko dotyczy technologii kryptograficznej, ale także przypomina o ludzkiej skłonności do zachowań przestępczych. Wcześniej wyjaśniliśmy, w jaki sposób algorytm RSA opierał się na trudnościach rozkładania na czynniki dużych liczb całkowitych, które są iloczynem dwóch liczb pierwszych. Trudność ta nie jest jednolita: niektóre produkty są łatwiejsze do faktoryzacji niż inne. Na przykład, niech p i q będą dwiema liczbami pierwszymi i załóżmy, że p-1 można rozłożyć na czynniki pierwsze, z których r jest największy. Następnie istnieje metoda (metoda Pollarda P – 1) na faktoryzację pq, która zajmie około r kroków. Oczywiście im większe r, tym dłużej to zajmie. Mówi się, że P jest silne, jeśli r jest duże. Wydawałoby się zatem, że silne liczby pierwsze to dobry pomysł; ale późniejsza dyskusja i rozwój alternatywnych metod faktoryzacji poddały w wątpliwość korzyści, jakie można osiągnąć. Jednak w ostatnich latach silne liczby pierwsze odzyskały pewną popularność z interesującego powodu: spekuluje się, że pozbawieni skrupułów użytkownicy mogli celowo używać słabych liczb pierwszych, aby stworzyć sobie lukę w postaci możliwości odrzucenia podpisu cyfrowego. W końcu użytkownik mógł twierdzić: „Nie chciałem wybrać słabej liczby pierwszej; to był po prostu mój pech (a właściwie twój, kumpel), że wybrałem taki, który ktoś inny mógłby złamać, a następnie użyć na moim miejscu ”. Należy zwrócić uwagę na brak wspólnego, długoterminowego punktu widzenia z w odniesieniu do niektórych zagadnień kryptografii klucza publicznego. Pamiętaj, że sprawdzalność jest niezwykle ważna dla akceptowalności każdego algorytmu bezpieczeństwa.

Jasne jest, że bezpieczeństwo zapewniane przez schemat klucza publicznego zależy od „odwracalności” procesu od klucza publicznego do klucza prywatnego. Widzieliśmy, że RSA polega na trudności w rozłożeniu dużych liczb na czynniki pierwsze. Inny powszechnie stosowany schemat, opublikowany przez ElGamala, wykorzystuje problem logarytmu dyskretnego, trudności w znalezieniu x, biorąc pod uwagę ostatnią resztę po wielokrotnym dzieleniu ax, gdzie a jest znaną liczbą, przez liczbę pierwszą p. Algorytm ElGamal został wykorzystany do podpisów cyfrowych. Ma niewielką wadę, ponieważ generuje tekst zaszyfrowany, który jest dwa razy dłuższy niż oryginalna wiadomość.

Okazuje się, że choć algorytmy z kluczem publicznym mają tę wielką zaletę znacznie prostszego zarządzania kluczami, w praktyce nie zastąpiły całkowicie algorytmów z kluczami prywatnymi. Systemy klucza prywatnego mają inne zalety, w szczególności szybkość obliczeń. W związku z tym jedną z możliwości jest wykorzystanie systemu klucza publicznego jako bezpiecznego kanału do przekazywania informacji o kluczu prywatnym . Jak pokazano, A może użyć klucza publicznego RSA B do zaszyfrowania klucza prywatnego DES, który będzie używany do bezpiecznej sesji między nimi a B. B może zrobić to samo. Klucze DES są używane do przygotowania kryptowalut DES do użytku przez całą sesję.

Różnice między mnożeniem liczb pierwszych a procesem odwrotnym są podstawą jednego z najbardziej udanych systemów klucza publicznego, RSA, nazwanego na cześć jego wynalazców, Rona Rivesta, Adi Shamira i Leonarda Adlemana. Pełny dowód tej techniki wymaga skomplikowanej matematyki, ale zasada jest prosta. Dwie duże liczby pierwsze o w przybliżeniu równej wielkości są wybierane i mnożone razem, aby otrzymać liczbę o długości kilkuset bitów. Nazywa się to „modułem”. Dwie kolejne liczby są obliczane z dwóch liczb pierwszych. Są to tak zwane klucze publiczne i prywatne. Właściciel musi zachować w tajemnicy wybór dwóch liczb pierwszych i klucza prywatnego, ale może udostępnić moduł i klucz publiczny. Dzięki temu nie ma potrzeby skomplikowanego konfigurowania bezpiecznego kanału do przekazywania tajnych kluczy. Każdy, kto chce wysłać wiadomość, używa algorytmu opisanego poniżej do zaszyfrowania wiadomości, operując na niej za pomocą modułu i klucza publicznego. Gdy wiadomość zostanie zaszyfrowana, zadanie jej odszyfrowania jest równoważne próbie faktoryzacji n, co jest znane jako „trudne”, chyba że ktoś ma dostęp do klucza prywatnego. Znajomość tego klucza prywatnego pozwala uprawnionemu odbiorcy odszyfrować wiadomość przy użyciu podobnego algorytmu do szyfrowania, z wyjątkiem tego, że zamiast klucza publicznego używany jest klucz prywatny.

Algorytm szyfrowania RSA

Algorytm opiera się na wyborze dwóch dużych liczb pierwszych p i q, których tożsamość musi być zachowana w tajemnicy. Niech n = p x q i wybierz liczbę e, która jest mniejsza od n. e nie musi być liczbą pierwszą, ale nie może mieć żadnych wspólnych czynników ani z (p – 1) ani (q – 1) . Musimy teraz znaleźć inną liczbę, d, taką, że (ex d – 1) i podzielna przez (p – 1) (q – 1) bez reszty. Mamy więc trzy liczby: d, e, n. Upubliczniamy e i n. (Są to „klucze publiczne”). D (klucz prywatny) trzymamy w tajemnicy. Załóżmy, że Alicja chce wysłać nam wiadomość, m. Wyszukuje naszą wartość e na liście publicznej. Następnie podnosi m do potęgi e. (Oznacza to, że mnoży m przez siebie, e razy. Gdyby m było „345”, a e było „7”, obliczyłaby 345 x 345 x 345 x 345 x 345 x 345 x 345). Następnie znajduje n z listy publicznej i wielokrotnie dzieli je na poprzednie obliczenia, aż pozostanie tylko reszta R. (np. załóżmy, że m do potęgi e = 10n + R. W notacji matematycznej jest to znane jako znalezienie R = m^e mod n). R to zaszyfrowany tekst, który Alicja wysyła do nas przez otwarty kanał. Można wykazać, że każda technika, która pozwala znaleźć m na podstawie R i znajomości n i e, jest trudna obliczeniowo, równoważna próbie rozłożenia na czynniki iloczynu dwóch liczb pierwszych. Bierzemy zaszyfrowany tekst R i podnosimy go do potęgi d (klucz tajny). Następnie znajdujemy resztę po wielokrotnym dzieleniu przez n (tj. obliczyliśmy Rd mod n). Co zaskakujące, okazuje się, że jest to m, wiadomość tekstowa. Typowa wartość klucza publicznego, zakodowana jako ciąg alfanumeryczny, wyglądałaby mniej więcej tak

Wszystkie systemy, które omówiliśmy powyżej, miały na celu osiągnięcie wysokiego stopnia bezpieczeństwa z łatwym do zarządzania układem obsługi kluczy. Ale wszyscy mają wspólny problem, że nadal musi istnieć bezpieczny kanał dostarczania tajnych kluczy. Jest to przykład stosunkowo bezpiecznego, algorytmicznie bezpiecznego systemu, który może zostać naruszony przez uciążliwy proces bezpieczeństwa. Na pierwszy rzut oka wydaje się to nieuniknionym wymogiem; jeśli odkryjesz klucz, którego używam do zaszyfrowania wiadomości, to na pewno łatwo ci go odszyfrować? To prawda, jeśli klucz do odszyfrowania wiadomości jest albo identyczny z kluczem szyfrowania, albo łatwo go z niego wyprowadzić, a metoda odszyfrowania polega na prostym odwróceniu szyfrowania. Ale załóżmy, że tak nie jest? W tym przypadku okazuje się, że istnieje szereg technik, które otwierają zaskakującą możliwość. Możliwość otwartego publikowania klucza szyfrowania dla każdego, co nie ułatwia nikomu poza wystawcą klucza odszyfrowania wiadomości zaszyfrowanych tym kluczem. Aby zrozumieć, co to oznacza, rozważ przykład pokazany na rysunku

Bob chce wysłać tajną wiadomość do Alice. Zauważa, że ​​Alicja powiedziała światu swój klucz publiczny. Używa tego do zaszyfrowania swojej wiadomości, zgodnie z jednym z algorytmów, które omówimy później. Następnie wysyła do niej swoją wiadomość przez otwarty kanał, wiedząc, że nawet jeśli Charlie zdoła ją przechwycić, nie będzie w stanie jej zrozumieć. Jednak Alicja i tylko Alicja, która posiada klucz prywatny, który działa jako odwrotność klucza publicznego i którego pilnie strzeże dla siebie, może zostać wykorzystana do odszyfrowania wiadomości. Ze względu na specjalną relację między kluczami prywatnymi i publicznymi Charlie jest niezwykle trudny do odszyfrowania wiadomości i opracowania klucza prywatnego. Być może bardziej zaskakujące jest to, że nikt, nawet Bob, nie może wrócić od znajomości wiadomości i klucza publicznego do prywatnego. Systemy szyfrowania klucza publicznego opierają się na fakcie, że niektóre operacje matematyczne są łatwe do wykonania w jednym kierunku, ale trudne w innym. Jednym z przykładów jest formowanie kwadratu liczby – prosta operacja mnożenia samej liczby – w porównaniu z otrzymaniem wyniku i poproszeniem o znalezienie pierwiastka kwadratowego. Liczba wymaganych do tego kroków jest znacznie większa niż w przypadku operacji kwadratu. Inną, bardziej odpowiednią operacją jest „faktoryzacja iloczynów liczb pierwszych”. Przypominamy sobie, że liczby pierwsze to liczby całkowite, których nie można „rozłożyć na czynniki” na iloczyn liczby mniejszych liczb całkowitych. 1, 2, 3, 5, 7 to liczby pierwsze, ale nie 4 (= 2 x 2), 6 (= 2 x 3) lub 9 (= 3 x 3). Wiadomo, że istnieje nieskończona liczba liczb pierwszych, z których około 10¹⁵⁰ ma 512 bitów lub mniej, ale nie ma znanego wzoru na udowodnienie, ogólnie, że liczba jest lub nie jest liczbą pierwszą, co jest znacznie szybsze niż próba lub błąd. Czas potrzebny na wykonanie tego rośnie bardzo szybko wraz z wielkością liczby. Podobny problem dotyczy „rozkładania na czynniki iloczynu dwóch liczb pierwszych”. (tj. znalezienie p i q, mając tylko p czas q). Łatwo jest pomnożyć dwie liczby pierwsze, ale trudno odwrócić ten proces.

Niezależnie od tego, czy DES ma słabości, czy nie, nadal lepiej polegać na nim niż na wielu innych systemach, które nie były intensywnie atakowane. W każdym razie równowaga między atakującym a obrońcą nie stoi w miejscu. Jednym z problemów radzenia sobie z postępami w technologii ataku jest zachowanie wstecznej kompatybilności ze starszymi systemami. Zamiast wyrzucać DES, wprowadzać nowy system i ponownie wpisywać wszystkie dane, istnieje tendencja do wydłużania czasu pracy DES poprzez wprowadzenie dłuższego klucza. W rzeczywistości zaproponowano trzy klucze 56-bitowe zamiast jednego, pod nazwą potrójnego DES. Szczególnie preferowaną opcją jest użycie tylko dwóch różnych kluczy, przy czym jeden z nich zostanie zastosowany dwukrotnie. Zdarza się, że dzięki temu odszyfrowanie może być zasadniczo odwróceniem szyfrowania. Niezależnie od rzeczywistych lub wyobrażonych słabości DES, w świecie, w którym nic nie jest pewne, prawdopodobnie prawdą jest, że potrójny DES jest bezpieczniejszy niż praktyczne zarządzanie jego kluczami. Przyjrzyjmy się teraz, jak można złagodzić niektóre problemy z zarządzaniem kluczami .

Jednym z opublikowanych i szeroko stosowanym przykładem systemu szyfrowania Feistal jest Data Encryption Standard (DES). Używa to zwykle klucza o długości co najmniej 56 bitów. Daje to prawie 1017 możliwości, które atakujący musiałby spróbować w ataku brute force. Dobrze zaprogramowany komputer ogólnego przeznaczenia w dzisiejszej technologii zajęłoby około stu lat, aby przetestować każdą możliwość. Podwojenie długości klucza do 128 bitów wydłuża czas szyfrowania o tę samą kolejność, ale sprawia, że ​​atak brute force jest 1020 razy dłuższy. Wymagałoby to imponująco dużej mocy obliczeniowej, gdyby został zaatakowany przy użyciu jednego konwencjonalnego komputera, ale uważaj, istnieją inne sposoby na zrobienie tego. Jedna z propozycji przewiduje bardzo dużą populację patriotycznych chałupników i poziom niezbyt drogiej, ale szeroko rozpowszechnionej technologii. Pojawienie się nadawania satelitarnego w Chinach zasugerowało szczególną technikę i nazwę chińska loteria. Atakujący przechwycił łącze i przesłał sygnał na satelitarnym kanale nadawczym do wielu milionów domów, z których każdy wyposażony jest w telewizor i dekoder satelitarny w postaci dekodera. Ten ostatni jest zasadniczo zmodyfikowanym komputerem i można go po prostu dalej zmodyfikować, aby umożliwić włączenie algorytmu kryptograficznego. Klucze wybrane losowo przez każde gospodarstwo domowe są testowane, aby sprawdzić, czy na ekranie telewizora pojawia się znaczący komunikat. Jedna z wielu milionów prób wkrótce zakończy się sukcesem. Okazało się, że jeden z najwcześniejszych udanych ataków na zaszyfrowaną wiadomość przy użyciu tej techniki został dokonany nie dzięki wielkiemu aktowi patriotycznej solidarności, ale dzięki ochotniczej sile 14 000 internautów, z których jednemu udało się znaleźć 56-bitowy klucz. Poprzedni sukces z użyciem 3500 komputerów osobistych złamał 48-bitowy klucz w 13 dni. Poważne implikacje są takie, że ataki oparte na przetwarzaniu równoległym zawsze będą stanowić zagrożenie dla wszelkich technik szyfrowania. Oszacowano, że kosztujące mniej niż milion dolarów maszyny specjalnego przeznaczenia, które przeprowadzają dużą liczbę równoległych ataków na 56-bitowy DES, mogą osiągnąć sukces w ciągu kilku godzin. To mieści się w granicach bezpieczeństwa rządu wielu narodów (i prawdopodobnie kilku globalnych syndykatów przestępczych). Istnieje również ciągła teoria spiskowa, według której DES zawiera słabość, która została celowo wprowadzona przez Agencję Bezpieczeństwa Narodowego, ale pomimo wielu prób czołowych ekspertów sprzeciwiających się „ingerencji” rządu, nie opublikowano żadnych sukcesów, a historia musi być traktowana z pewnym sceptycyzmem. Zaproponowano inne ataki, które wykorzystują ataki z tekstem jawnym, w których atakującemu udaje się albo skłonić nadawcę do zakodowania wybranych przez niego wiadomości, albo po prostu użyć wiadomości, których tekst jawny jest znany. Jeden z przykładów tego ostatniego z powodzeniem odzyskał klucz w ciągu 50 dni przy użyciu 12 stacji roboczych, ale wymagało to 2⁴3 znanych tekstów jawnych, a zatem prawdopodobnie nie jest praktyczne.

Podany powyżej opis szyfru Feistela sugeruje, że dane muszą istnieć w blokach o określonej wielkości, współmiernej do wielkości klucza. W rzeczywistości nie jest to wymóg; możliwe jest wykorzystanie zasady Feistela do generowania szyfrowania na każdym pojedynczym bicie danych wejściowych. W przykładzie omówionego wcześniej liniowego schematu szyfrowania rejestru przesuwnego, Rysunek pokazuje rejestr przesuwny działający w trybie sprzężenia zwrotnego, w którym rejestr generuje strumień danych pseudolosowych, który jest OR’d z danymi jawnego tekstu.

Możemy zrobić dokładnie to samo z szyframi Feistela, torując pole zmiany kolejności sekwencją początkową, pozwalając mu zaszyfrować to za pomocą klucza i w ten sposób wytwarzając zestaw bitów wyjściowych, z których niektóre można ORAZ z danymi do być zaszyfrowane. Bity wyjściowe z pola zmiany kolejności można następnie przesłać z powrotem do skrzynki, aby wygenerować nową sekwencję. Istnieje również kilka sposobów na zaimplementowanie podstawowego szyfrowania blokowego szyfru Feistela. Na przykład możliwe jest LUB poprzednie wyjście zaszyfrowanego tekstu z bieżącym blokiem. Ma to tę zaletę, że atakującemu trudniej jest wykorzystać powtarzające się bloki identycznych danych. Jednak, jak wszystkie odmiany, ma również wady. Musimy pamiętać, że atakujący mogą teoretycznie wstrzykiwać własne wiadomości w celu zainicjowania znanego ataku tekstowego lub mogą wprowadzić błędy, które mogą rozprzestrzeniać się na kilka bloków danych, czyniąc system bezużytecznym, a uprawnione strony mogą chcieć cofnąć do niepewnej alternatywy.

Alternatywą dla szyfrów strumieniowych są szyfry blokowe, które operują na bloku danych o ustalonej liczbie bitów w celu uzyskania równoważnego, zaszyfrowanego wyjścia. Zamiast generować oddzielny strumień bitów pseudolosowych i łączyć je z tekstem jawnym, szyfry blokowe często wykonują operacje „szyfrowania” na samych danych w postaci zwykłego tekstu, zmieniając kolejność bitów w bloku i łącząc je z innymi bitami, na przykład za pomocą funkcji OR . Alternatywnie, możemy po prostu wziąć duży blok danych i zaszyfrować kolejność bitów, zgodnie z pewnym wzorem permutacji, znanym nadawcy i odbiorcy, ale ponownie utrzymywanym w tajemnicy przed innymi. Kilka przykładów opiera się na szyfrach Feistela, które wielokrotnie przekazują tekst przez tę samą funkcję szyfrującą. Blok danych w postaci zwykłego tekstu jest podzielony na pół. Połowa danych jest obsługiwana przez funkcję F, która dokonuje zmiany kolejności (tasowania) bitów w bloku, zgodnie z „podkluczem” (SK1). Wynik ponownego uporządkowania jest następnie „LUB” z niepoddaną obróbce połową. Połówki są następnie zamieniane i ta sama funkcja zmiany kolejności została zastosowana do drugiej połowy. Należy zauważyć, że funkcja zmiany kolejności jest nadal taka sama, ale jej wpływ na dane może być inny, ponieważ jest kontrolowany przez nowy podklucz (SK2). Proces można powtarzać w kółko. Szyfry Feistela są wygodne do odszyfrowania, ponieważ proces szyfrowania jest po prostu odwrócony, stosując podklucze w odwrotnej kolejności. Funkcje zmiany kolejności są tak dobrane, że ich szczegółowe działanie na danych jest trudne do odszyfrowania bez znajomości podkluczy. W ten sposób funkcje ponownego porządkowania mogą być upublicznione.