Długość klucza szyfrowania. Klucz publiczny i prywatny: do czego służą? Generowanie ciągów losowych i pseudolosowych

Wiele nowoczesnych algorytmów szyfrowania z kluczem publicznym opiera się na jednokierunkowej funkcji faktoryzacji liczby, która jest iloczynem dwóch dużych liczb pierwszych. Algorytmy te mogą również zostać poddane atakowi podobnemu do ataku siłowego stosowanego przeciwko szyfrom z tajnym kluczem, z jedną różnicą: nie musisz wypróbowywać każdego klucza, wystarczy, że będziesz w stanie rozłożyć dużą liczbę na czynniki.

Oczywiście rozłożenie dużej liczby na czynniki jest trudnym zadaniem. Jednak natychmiast pojawia się rozsądne pytanie, jak trudne. Niestety dla kryptografów, trudność jego rozwiązania maleje. Co gorsza, ta trudność spada w znacznie szybszym tempie niż wcześniej oczekiwano. Na przykład w połowie lat siedemdziesiątych uważano, że rozłożenie liczby 125 cyfr na czynniki zajmie dziesiątki biliardów lat. A już dwie dekady później, korzystając z komputerów podłączonych do Internetu, udało się rozłożyć liczbę 129 cyfr. Przełom ten stał się możliwy dzięki temu, że w ciągu ostatnich 20 lat nie tylko zaproponowano nowe, szybsze metody faktoryzacji dużych liczb, ale także wzrosła wydajność wykorzystywanych komputerów.

Dlatego wykwalifikowany kryptograf musi zachować dużą ostrożność i dyskrecję, jeśli chodzi o długość klucza publicznego. Należy zastanowić się, jak cenne są informacje utajnione za jego pomocą i jak długo powinny pozostać tajemnicą dla osób postronnych.

I dlaczego, ktoś pyta, nie brać klucza 10 000-bitowego? Znikną przecież wtedy wszystkie pytania związane ze stabilnością algorytmu szyfrowania asymetrycznego z kluczem publicznym, opartego na rozkładzie dużej liczby na czynniki. Ale faktem jest, że zapewnienie wystarczającej siły szyfru nie jest jedyną troską kryptografa. Istnieją dodatkowe względy, które wpływają na wybór długości klucza, a wśród nich są kwestie związane z praktyczną wykonalnością algorytmu szyfrowania dla wybranej długości klucza.

Aby oszacować długość klucza publicznego zmierzymy moc obliczeniową dostępną dla kryptoanalityka w tzw. mops-yo, tj. liczba operacji, które komputer zdolny do wykonywania z prędkością 1 miliona operacji na sekundę wykonuje w ciągu roku. Załóżmy, że haker ma dostęp do zasobów komputera o łącznej mocy obliczeniowej 10 000 mops-lat, duża korporacja - 10 7 mops-lat, rząd - 10 7 mops-lat. Są to całkiem realistyczne liczby, biorąc pod uwagę, że wspomniany wyżej projekt dekompozycji 129 cyfr wykorzystał zaledwie 0,03% mocy obliczeniowej Internetu, a aby to osiągnąć, nie musiał podejmować żadnych nadzwyczajnych działań ani wykraczać poza prawo.

Załóżmy też, że moc obliczeniowa wzrasta 10-krotnie co 5 lat, a metoda rozkładu dużych liczb na czynniki pozwala na to ze złożonością wskazaną w tabeli 1. 6.3.

Tabela 6.3. Złożoność rozkładu na czynniki dużych liczb.

Przyjęte założenia pozwalają oszacować długość silnego klucza publicznego w zależności od okresu, przez jaki konieczne jest zachowanie w tajemnicy zaszyfrowanych nim danych (tabela 6.4). Należy pamiętać, że algorytmy kryptograficzne klucza publicznego są często wykorzystywane do ochrony bardzo cennych informacji przez bardzo długi okres czasu. Na przykład w systemach płatności elektronicznych lub przy notarialnym podpisie elektronicznym. Pomysł spędzenia kilku miesięcy na faktoringu dużej liczby może wydawać się komuś bardzo atrakcyjny, jeśli w końcu będzie mógł zapłacić za zakupy kartą kredytową. Poza tym nie sądzę, żebyś był zadowolony, gdybyś za 20 lat został wezwany do sądu spadkowego i bronił niemożności sfałszowania elektronicznego podpisu twojego dziadka, którego użył do sporządzenia testamentu na twoją korzyść.

Rok	Haker	duża korporacja	Rząd
2000	1024	1280	1536
2005	1280	1536	2048
2010	1280	1536	2048
2015	1536	2048	2048

Z podanym w tabeli. 6.4 nie wszyscy renomowani kryptografowie zgadzają się z danymi. Część z nich kategorycznie odmawia jakichkolwiek prognoz długoterminowych, uznając to za bezsensowne przedsięwzięcie. Inni, na przykład specjaliści z NSA, są zbyt optymistyczni, zalecając długość klucza publicznego tylko 512-1024 bitów dla systemów podpisu cyfrowego, co w świetle danych z Tab. 6.4 jest całkowicie niewystarczające do zapewnienia odpowiedniej długoterminowej ochrony.

klucza publicznego, zauważył, że wymóg ten zaprzecza całej istocie kryptografii, a mianowicie zdolności do zachowania powszechnej tajemnicy w komunikacji.

Drugim zadaniem jest konieczność stworzenia takich mechanizmów, za pomocą których nie byłoby możliwości zastąpienia któregokolwiek z uczestników, tj. potrzebować podpis cyfrowy. W przypadku korzystania z komunikacji w szerokim zakresie celów, takich jak cele komercyjne i prywatne, wiadomości i dokumenty elektroniczne muszą mieć odpowiednik podpisu zawartego w dokumentach papierowych. Konieczne jest stworzenie metody, dzięki której wszyscy uczestnicy będą przekonani, że e-mail został wysłany przez konkretnego uczestnika. Jest to silniejsze wymaganie niż uwierzytelnianie.

Diffie i Hellman osiągnęli znaczące wyniki, proponując sposób rozwiązania obu problemów, który radykalnie różni się od wszystkich poprzednich podejść do szyfrowania.

Przyjrzyjmy się najpierw wspólnym cechom. algorytmy szyfrowania z kluczem publicznym i wymaganiami dla tych algorytmów. Zdefiniujmy wymagania, jakie powinien spełniać algorytm, który używa jednego klucza do szyfrowania, a drugiego do deszyfrowania, a wyznaczenie klucza deszyfrującego jest obliczeniowo niemożliwe, jeśli znany jest tylko algorytm szyfrowania i klucz szyfrujący.

Ponadto niektóre algorytmy, takie jak RSA, mają następującą cechę: każdy z dwóch kluczy może być używany zarówno do szyfrowania, jak i deszyfrowania.

Najpierw rozważymy algorytmy, które mają obie właściwości, a następnie przejdziemy do algorytmów klucza publicznego, które nie mają drugiej właściwości.

Podczas opisywania szyfrowanie symetryczne i szyfrowania kluczem publicznym będziemy używać następującej terminologii. klucz używany w szyfrowanie symetryczne, zadzwonimy sekretny klucz. Zostaną wywołane dwa klucze używane w szyfrowaniu kluczem publicznym klucz publiczny I prywatny klucz. Klucz prywatny jest utrzymywany w tajemnicy, ale będziemy go nazywać kluczem prywatnym, a nie tajnym, aby uniknąć pomyłki z używanym kluczem szyfrowanie symetryczne. Klucz prywatny będzie oznaczony jako KR, klucz publiczny - KU.

Zakładamy, że wszyscy uczestnicy mają dostęp do swoich kluczy publicznych, a klucze prywatne są tworzone lokalnie przez każdego uczestnika i dlatego nie powinny być rozpowszechniane.

W każdej chwili uczestnik może zmienić swój klucz prywatny i opublikować klucz publiczny składający się na parę, zastępując nim stary klucz publiczny.

Diffie i Hellman opisują wymagania algorytm szyfrowania z kluczem publicznym.

Obliczeniowo łatwo jest utworzyć parę (klucz publiczny KU, klucz prywatny KR).
Biorąc pod uwagę klucz publiczny i niezaszyfrowaną wiadomość M, jest łatwo obliczeniowo utworzyć odpowiednią zaszyfrowaną wiadomość:
Odszyfrowanie wiadomości za pomocą klucza prywatnego jest łatwe obliczeniowo:
M = re KR [C] = re KR ]
Jest obliczeniowo niemożliwe, znając klucz publiczny KU, wyznaczenie klucza prywatnego KR.
Jest obliczeniowo niemożliwe, znając klucz publiczny KU i zaszyfrowaną wiadomość C, aby odzyskać pierwotną wiadomość M.
Można dodać szósty wymóg, chociaż nie dotyczy on wszystkich algorytmów klucza publicznego:
Funkcje szyfrowania i deszyfrowania można zastosować w dowolnej kolejności:
M = E ku]

Są to wystarczająco mocne wymagania, które wprowadzają pojęcie . Funkcja jednokierunkowa nazywa się taką funkcję, w której każdy argument ma unikalną wartość odwrotną, podczas gdy łatwo jest obliczyć samą funkcję, ale trudno obliczyć funkcję odwrotną.

Zwykle „łatwy” oznacza, że problem można rozwiązać w czasie wielomianowym długości wejścia. Zatem, jeśli długość wejścia wynosi n bitów, to czas obliczania funkcji jest proporcjonalny do n a , gdzie a jest stałą stałą. Zatem mówi się, że algorytm należy do klasy algorytmów wielomianowych P. Termin „twardy” oznacza bardziej skomplikowaną koncepcję. W ogólnym przypadku przyjmiemy, że problemu nie da się rozwiązać, jeśli wysiłek jego rozwiązania jest większy niż czas wielomianu wartości wejściowej. Na przykład, jeśli długość danych wejściowych wynosi n bitów, a czas oceny funkcji jest proporcjonalny do 2 n, to jest to zadanie obliczeniowo niemożliwe. Niestety, trudno jest określić, czy dany algorytm wykazuje taką złożoność. Co więcej, tradycyjne pojęcia złożoności obliczeniowej koncentrują się na złożoności algorytmu w najgorszym lub średnim przypadku. Jest to niedopuszczalne w przypadku kryptografii, gdzie wymagane jest, aby funkcja nie mogła być odwrócona dla wszystkich lub prawie wszystkich wartości wejść.

Powrót do definicji funkcja jednostronna z szyberdachem, który np funkcja jednokierunkowa, jest łatwe do obliczenia w jednym kierunku i trudne do obliczenia w przeciwnym kierunku, dopóki nie będą dostępne dodatkowe informacje. Dzięki tym dodatkowym informacjom inwersję można obliczyć w czasie wielomianowym. Zatem, funkcja jednokierunkowa z szyberdachem należącym do rodziny funkcje jednokierunkowe f k takie

Widzimy, że opracowanie określonego algorytmu klucza publicznego zależy od odkrycia odpowiadającego mu algorytmu funkcja jednostronna z szyberdachem.

Kryptoanaliza algorytmów klucza publicznego

Jak w przypadku szyfrowanie symetryczne, algorytm szyfrowania z kluczem publicznym jest podatny na atak frontalny. Środek zaradczy jest standardowy: użyj dużych klawiszy.

Kryptosystem klucza publicznego wykorzystuje pewne nieodwracalne funkcje matematyczne. Złożoność obliczania takich funkcji nie jest liniowa pod względem liczby bitów klucza, ale rośnie szybciej niż klucz. Zatem rozmiar klucza musi być wystarczająco duży, aby atak frontalny był niepraktyczny, i wystarczająco mały, aby umożliwić praktyczne szyfrowanie. W praktyce rozmiar klucza jest taki, że atak siłowy jest niepraktyczny, ale w rezultacie szybkość szyfrowania jest wystarczająco niska, aby algorytm mógł być używany do ogólnych celów. Dlatego szyfrowanie kluczem publicznym jest obecnie ograniczone głównie do aplikacji do zarządzania kluczami i podpisów, które wymagają zaszyfrowania małego bloku danych.

Inną formą ataku jest znalezienie sposobu na obliczenie klucza prywatnego na podstawie klucza publicznego. Nie ma sposobu, aby matematycznie udowodnić, że dana forma ataku jest wykluczona dla konkretnego algorytmu klucza publicznego. Dlatego każdy algorytm, w tym szeroko stosowany algorytm RSA, jest podejrzany.

Wreszcie, istnieje forma ataku, która jest specyficzna dla sposobu korzystania z systemów klucza publicznego. To atak na prawdopodobną wiadomość. Załóżmy na przykład, że wysyłana wiadomość składa się wyłącznie z 56-bitowego klucza sesyjnego dla algorytmu szyfrowania symetrycznego. Przeciwnik może zaszyfrować wszystkie możliwe klucze za pomocą klucza publicznego i może odszyfrować dowolną wiadomość pasującą do przesyłanego zaszyfrowanego tekstu. W ten sposób, niezależnie od rozmiaru klucza schematu klucza publicznego, atak zostaje zredukowany do ataku typu brute-force na 56-bitowy klucz symetryczny. Ochrona przed takim atakiem polega na dodaniu pewnej liczby losowych bitów do prostych wiadomości.

Podstawowe zastosowania algorytmów klucza publicznego

Główne zastosowania algorytmów klucza publicznego to szyfrowanie/odszyfrowywanie, tworzenie i weryfikacja podpisów oraz wymiana kluczy.

Szyfrowanie z kluczem publicznym składa się z następujących kroków:

Ryż. 7.1.

Użytkownik B tworzy parę kluczy KU b i KR b używanych do szyfrowania i deszyfrowania przesyłanych wiadomości.
Użytkownik B udostępnia swój klucz szyfrujący w jakiś bezpieczny sposób, tj. klucz publiczny KU b . Sparowany klucz prywatny KR b jest utrzymywany w tajemnicy.
Jeśli A chce wysłać wiadomość do B, szyfruje wiadomość za pomocą klucza publicznego B KU b .
Kiedy B odbiera wiadomość, odszyfrowuje ją za pomocą swojego klucza prywatnego KR b . Nikt inny nie może odszyfrować wiadomości, ponieważ tylko B zna ten klucz prywatny.

Jeśli użytkownik (system końcowy) bezpiecznie przechowuje swój klucz prywatny, nikt nie będzie mógł szpiegować przesyłanych wiadomości.

Tworzenie i weryfikacja podpisu składa się z następujących kroków:

Ryż. 7.2.

Użytkownik A generuje parę kluczy KR A i KU A , służących do tworzenia i weryfikacji podpisu przesyłanych komunikatów.
Użytkownik A udostępnia swój klucz weryfikacyjny w jakiś bezpieczny sposób, tj.

Klucze kryptograficzne mogą różnić się od siebie długością, która w konsekwencji siłą danego klucza. Im dłuższy klawisz, tym więcej możliwych kombinacji wyboru. Na przykład, jeśli użyjesz klucza o długości 128 bitów, klucz będzie jedną z 2128 możliwych opcji. Porywacz jest bardziej skłonny wygrać na loterii niż podnieść ewentualny klucz. Na standardowym komputerze domowym, aby uzyskać klucz 40-bitowy, musisz spędzić 6 godzin, aby posortować wszystkie możliwe. Jednak nawet klucze o długości 128 bitów mogą być podatne na ataki, a profesjonaliści mogą je złamać.

Niezawodność symetrycznego zależy bezpośrednio od siły długości klucza i algorytmu szyfrowania. Jeśli na przykład algorytm jest idealny, to można go odszyfrować tylko przez wyliczenie wszystkich kluczy. Aby zaimplementować tę metodę, potrzebujesz tekstu zaszyfrowanego i tekstu jawnego. Na przykład, jeśli długość klucza wynosi 128 bitów, superkomputer będzie potrzebował 1025 lat, aby wyliczyć wszystkie klucze. Natychmiast powstaje pytanie, dlaczego nie użyć klucza o długości ponad 9999, czyli 4000 bajtów.
Jednocześnie kryptografia jest bardzo subtelną nauką, w której chcemy zwiększyć niezawodność, a wręcz przeciwnie, możemy ją obniżyć przy minimalnych zmianach w algorytmie. Sprawdzając siłę algorytmu szyfrowania, sprawdzają warunki, w których atakujący może otrzymać wystarczającą ilość tekstu jawnego lub zaszyfrowanego. Na szczęście w rzeczywistości jest bardzo niewiele osób, które są naprawdę wysoko wykwalifikowane do przeprowadzania udanych ataków w celu odszyfrowania danych.

Wiele algorytmów szyfrowania z kluczem publicznym implementuje funkcje faktoryzacji dla liczby będącej iloczynem dwóch dużych liczb pierwszych. w latach 70. rozłożenie liczby 125 cyfr zajęło dziesiątki biliardów lat. Dziś nie składa się z dużo czasu. Powyżej zadano pytanie, dlaczego nie zastosować długich klawiszy overr9999, bo wtedy nie pojawi się kwestia trwałości i niezawodności. Konieczne jest uwzględnienie nie tylko wiarygodności i poufności, ale także czasu wartości informacji i czasu poświęconego na wdrożenie takiego szyfrowania. Na przykład informacja straci na wartości za 10 lat, a wydaliśmy środki finansowe, które zwrócą się dopiero po 20 latach, gdzie tu logika?

Aby ocenić klucz publiczny, należy zmierzyć kryptoanalityczną moc obliczeniową w latach pug. Jest to liczba operacji wykonywanych na sekundę w ciągu roku. Na przykład korporacje mają 107 lat mopsa, a rządy 109 lat mopsa. Na ryc.1. możesz zobaczyć, ile czasu zajmuje rozłożenie liczb o różnych długościach. Często te same cenne informacje są szyfrowane przez długi czas. Pomysł spędzenia kilku miesięcy na faktoringu dużej liczby, aby móc robić zakupy za pomocą czyjejś karty kredytowej, jest atrakcyjny. Zalecaną długość kluczy publicznych przedstawiono na rysunku 2.

Obrazek 1

Rysunek - 2

Kryptoanalityczny atak na algorytmy szyfrujące jest tradycyjnie skierowany na najcieńszy lub najsłabszy punkt algorytmu. Zazwyczaj przedsiębiorstwa stosują systemy hybrydowe, są to systemy wykorzystujące klucz publiczny i prywatny. Siła każdego algorytmu musi odpowiadać wystarczającej niezawodności. Na ryc.3. pokazane są pary długości klucza dla algorytmów niesymetrycznych i symetrycznych.

Aby oszacować długość klucza publicznego, zmierzymy moc obliczeniową dostępną dla kryptoanalityka w tzw. za rok. Załóżmy, że haker ma dostęp do zasobów komputera o łącznej mocy obliczeniowej 10 000 mops-lat, duża korporacja - 107 mops-lat, rząd - 109 mops-lat. Są to całkiem realistyczne liczby, jeśli wziąć pod uwagę, że wspomniany wyżej projekt dekompozycji 129 cyfr wykorzystał zaledwie 0,03% mocy obliczeniowej Internetu, a aby to osiągnąć, nie musiał podejmować żadnych nadzwyczajnych działań ani wykraczać poza prawo.

Załóżmy też, że moc obliczeniowa wzrasta 10-krotnie co 5 lat, a metoda rozkładu dużych liczb na czynniki pozwala na to ze złożonością wskazaną w tabeli 1. 6.3.

Tabela 6.3. Złożoność rozkładu na czynniki dużych liczb

Głównym celem stosowania certyfikatów SSL jest szyfrowanie danych przesyłanych do serwera od klienta oraz do klienta z serwera. Aby zapewnić bezpieczeństwo takiego połączenia, nowoczesne przeglądarki wykorzystują algorytm TLS oparty na certyfikatach X.509. Ten algorytm używa szyfrowania asymetrycznego do generowania klucza sesji dla szyfrowania symetrycznego. Ten ostatni służy bezpośrednio do przesyłania danych po nawiązaniu bezpiecznego połączenia.

Co to jest klucz w kryptografii?

Klucz w kryptografii to tajne informacje używane w kryptografii do szyfrowania i dekodowania wiadomości, ich cyfrowego podpisywania i weryfikacji, obliczania kodów uwierzytelniających wiadomości i tak dalej. O tym, jak niezawodny jest klucz, decyduje tak zwana długość klucza, mierzona w bitach. Standardowa długość klucza dla certyfikatów SSL to 128 lub 256 bitów. Długość klucza głównego urzędu certyfikacji (certyfikatu głównego) nie może być mniejsza niż 4096 bitów. Wszystkie urzędy certyfikacji, z którymi współpracujemy, udostępniają certyfikaty SSL z kluczem w pełni zgodnym ze współczesnymi standardami:

Klucz publiczny i prywatny w szyfrowaniu asymetrycznym

Zastosowania szyfrowania asymetrycznego para kluczy: otwarty (klucz publiczny) I Zamknięte, nazywane również sekret (prywatny klucz). Klucze publiczny i prywatny w tym przypadku umożliwiają algorytmowi kryptograficznemu szyfrowanie i deszyfrowanie wiadomości. Wiadomości zaszyfrowane kluczem publicznym można odszyfrować tylko kluczem prywatnym. Klucz publiczny jest publikowany w certyfikacie właściciela i jest dostępny dla łączącego się klienta, natomiast klucz prywatny jest przechowywany przez właściciela certyfikatu. Klucze publiczny i prywatny są ze sobą powiązane zależnościami matematycznymi, więc nie jest możliwe pobranie klucza publicznego lub prywatnego w krótkim czasie (okres ważności certyfikatu). Dlatego maksymalny okres ważności certyfikatów SSL o wyższym poziomie ochrony jest zawsze krótszy. Możesz więc zamówić maksymalnie 2 lata. Jednocześnie przy zamawianiu nowego certyfikatu SSL lub odnawianiu starego ważne jest wygenerowanie nowego żądania CSR, ponieważ jest z nim powiązany Twój klucz prywatny i lepiej jest go aktualizować, gdy wydawany jest nowy certyfikat SSL . Klient komunikuje się z serwerem w następujący sposób:

przeglądarka szyfruje żądanie na podstawie klucza publicznego i przesyła je do serwera;
serwer za pomocą klucza prywatnego odszyfrowuje otrzymaną wiadomość;
serwer szyfruje swój identyfikator cyfrowy kluczem prywatnym i przesyła go do klienta;
klient sprawdza identyfikator serwera i wysyła własny;
po wzajemnym uwierzytelnieniu klient szyfruje klucz przyszłej sesji kluczem publicznym i przesyła go do serwera;
wszystkie kolejne wiadomości przesyłane między klientem a serwerem są podpisywane kluczem sesyjnym i szyfrowane kluczem publicznym i prywatnym.

Zapewnia to kilka punktów bezpieczeństwa:

wykluczona jest możliwość wycieku informacji - po przechwyceniu nie można ich odszyfrować;
serwer potwierdza swój adres i identyfikator, odcinana jest możliwość przekierowania na inną stronę (phishing);
klientowi przydzielana jest indywidualna sesja, co pozwala na bardziej wiarygodne odróżnienie go od innych klientów;
po ustanowieniu bezpiecznej sesji wszystkie wiadomości są szyfrowane przy użyciu tożsamości klienta i nie można ich przechwycić ani zmienić niezauważenie.

W ogólnym przypadku szyfrowanie kluczem publicznym i prywatnym można uznać za przypadek, w którym stosuje się dwa klucze: jeden można tylko zamknąć, drugi otworzyć. Jeśli obudowa była zamykana pierwszym kluczem, tylko drugim można ją otworzyć, jeśli była zamykana drugim kluczem, pierwszy będzie potrzebny do jej otwarcia. Widać to wyraźnie na powyższym diagramie.