szyfrowanie RSA to system, który rozwiązuje jeden z największych problemów w kryptografii: jak można wysłać komuś zakodowaną wiadomość bez możliwości wcześniejszego udostępnienia mu kodu?
Ten artykuł nauczy Cię wszystkiego, co musisz wiedzieć o tym, jak opracowano szyfrowanie RSA, jak to działa, matematyka za nim, do czego jest używane, a także niektóre z największych problemów związanych z bezpieczeństwem, z którymi się boryka., Poznanie RSA da Ci podstawową wiedzę, która pomoże Ci zrozumieć, jak wiele części naszego życia online jest bezpiecznych.
co to jest szyfrowanie RSA?
powiedzmy, że chcesz zdradzić przyjacielowi sekret. Jeśli jesteś obok nich, możesz po prostu szepnąć. Jeśli jesteś po przeciwnych stronach kraju, to oczywiście nie zadziała. Możesz je zapisać i wysłać do nich pocztą lub skorzystać z telefonu, ale każdy z tych kanałów komunikacji jest niepewny i każdy z wystarczająco silną motywacją może łatwo przechwycić wiadomość.,
gdyby sekret był wystarczająco ważny, nie zaryzykowałbyś spisania go normalnie–szpiedzy lub nieuczciwy pracownik poczty mogą przeglądać Twoją pocztę. Podobnie, ktoś może podsłuchiwać Twój telefon bez Twojej wiedzy i rejestrować każde nawiązane połączenie.
jednym z rozwiązań uniemożliwiających podsłuchiwaczom dostęp do treści wiadomości jest szyfrowanie jej. Zasadniczo oznacza to dodanie kodu do wiadomości, który zmienia ją w pomieszany bałagan. Jeśli twój kod jest wystarczająco złożony, to jedynymi osobami, które będą mogły uzyskać dostęp do oryginalnej wiadomości, są ci, którzy mają dostęp do kodu.,
Jeśli miałeś okazję wcześniej udostępnić kod znajomemu, to każdy z Was może wysłać zaszyfrowaną wiadomość w dowolnym momencie, wiedząc, że tylko wy potraficie odczytać treść wiadomości. Ale co, jeśli nie miałeś okazji wcześniej udostępnić kodu?
jest to jeden z podstawowych problemów kryptografii, który został rozwiązany przez Schematy szyfrowania klucza publicznego (znane również jako szyfrowanie asymetryczne), takie jak RSA.
w przypadku szyfrowania RSA wiadomości są szyfrowane kodem zwanym kluczem publicznym, który może być udostępniany otwarcie., Z powodu pewnych odrębnych właściwości matematycznych algorytmu RSA, gdy wiadomość zostanie zaszyfrowana kluczem publicznym, może być odszyfrowana tylko innym kluczem, znanym jako klucz prywatny. Każdy użytkownik RSA ma parę kluczy składającą się z kluczy publicznych i prywatnych. Jak sama nazwa wskazuje, klucz prywatny musi być utrzymywany w tajemnicy.
Schematy szyfrowania klucza publicznego różnią się od szyfrowania klucza symetrycznego, gdzie zarówno proces szyfrowania, jak i deszyfrowania używają tego samego klucza prywatnego., Różnice te sprawiają, że szyfrowanie kluczy publicznych, takie jak RSA, jest przydatne do komunikacji w sytuacjach, w których nie było możliwości bezpiecznej dystrybucji kluczy wcześniej.
algorytmy klucza symetrycznego mają swoje własne aplikacje, takie jak szyfrowanie danych do użytku osobistego lub w przypadku, gdy istnieją bezpieczne kanały, nad którymi można udostępniać klucze prywatne.
Zobacz też: Kryptografia klucza publicznego
gdzie stosuje się szyfrowanie RSA?
szyfrowanie RSA jest często używane w połączeniu z innymi schematami szyfrowania lub w przypadku podpisów cyfrowych, które mogą udowodnić autentyczność i integralność wiadomości., Nie jest zwykle używany do szyfrowania całych wiadomości lub plików, ponieważ jest mniej wydajny i bardziej obciążony zasobami niż szyfrowanie kluczem symetrycznym.
aby zwiększyć wydajność, plik będzie na ogół szyfrowany algorytmem klucza symetrycznego, a następnie klucz symetryczny będzie szyfrowany za pomocą szyfrowania RSA. W ramach tego procesu tylko podmiot, który ma dostęp do klucza prywatnego RSA, będzie mógł odszyfrować klucz symetryczny.
bez dostępu do klucza symetrycznego, oryginalny plik nie może zostać odszyfrowany., Ta metoda może być używana do zabezpieczania wiadomości i plików, bez zajmowania zbyt długo lub zużywania zbyt wielu zasobów obliczeniowych.
szyfrowanie RSA może być używane w wielu różnych systemach. Może być zaimplementowany w OpenSSL, wolfCrypt, cryptlib i wielu innych bibliotekach kryptograficznych.
jako jeden z pierwszych powszechnie stosowanych schematów szyfrowania klucza publicznego, RSA położył podwaliny pod znaczną część naszej bezpiecznej komunikacji. Był on tradycyjnie używany w TLS i był również oryginalnym algorytmem używanym w szyfrowaniu PGP., RSA jest nadal widoczny w wielu przeglądarkach internetowych, e-mail, VPN, czacie i innych kanałach komunikacji.
RSA jest również często używany do tworzenia bezpiecznych połączeń między klientami VPN a serwerami VPN. W ramach protokołów takich jak OpenVPN, TLS handshakes może używać algorytmu RSA do wymiany kluczy i ustanowienia bezpiecznego kanału.
tło szyfrowania RSA
jak wspomnieliśmy na początku tego artykułu, przed szyfrowaniem klucza publicznego wyzwaniem było bezpieczne komunikowanie się, gdyby nie była szansa bezpiecznej wymiany kluczy wcześniej., Jeśli nie było możliwości udostępnienia kodu z wyprzedzeniem lub bezpiecznego kanału, przez który klucze mogły być rozprowadzane, nie było sposobu na komunikowanie się bez zagrożenia, że wrogowie będą w stanie przechwycić i uzyskać dostęp do treści wiadomości.
dopiero w latach 70.wszystko zaczęło się zmieniać. Pierwszy duży rozwój w kierunku tego, co teraz nazywamy kryptografią klucza publicznego, został opublikowany na początku dekady przez Jamesa H. Ellisa., Ellis nie mógł znaleźć sposobu na wdrożenie swojej pracy, ale został on rozszerzony przez swojego kolegę Clifforda Cocksa, aby stać się tym, co obecnie znamy jako szyfrowanie RSA.
ostatnim elementem układanki jest to, co teraz nazywamy wymianą kluczy Diffie-Hellman. Malcolm J. Williamson, inny współpracownik, odkrył schemat, który pozwalał dwóm stronom na dzielenie się kluczem szyfrującym, nawet jeśli kanał był monitorowany przez przeciwników.
wszystkie te prace zostały podjęte w brytyjskiej agencji wywiadowczej, rządowej centrali łączności (GCHQ), która utrzymywała odkrycie w tajemnicy., Po części ze względu na ograniczenia technologiczne, GCHQ nie widział zastosowania kryptografii klucza publicznego w tym czasie, więc rozwój siedział bezczynnie na półce zbierając kurz. Dopiero w 1997 roku dzieło zostało odtajnione i potwierdzono oryginalnych wynalazców RSA.
kilka lat później podobne koncepcje zaczęły się rozwijać w sferze publicznej. Ralph Merkle stworzył wczesną formę kryptografii klucza publicznego, która wpłynęła na Whitfielda Diffiego i Martina Hellmana w projektowaniu wymiany kluczy Diffiego-Hellmana.,
pomysłom Diffiego i Hellmana brakowało jednego ważnego aspektu, który uczyniłby ich pracę fundamentem kryptografii klucza publicznego. Była to funkcja jednokierunkowa, którą trudno byłoby odwrócić. W 1977 roku Ron Rivest, Adi Shamir i Leonard Adleman, których nazwiska tworzą akronim RSA, wymyślili rozwiązanie po roku pracy nad problemem.
naukowcy z MIT dokonali przełomu po przyjęciu Paschy w 1977 roku., Po nocy picia Rivest poszedł do domu, ale zamiast spać, spędził wieczór gorączkowo pisząc pracę, która sformalizowała jego pomysł na niezbędną funkcję jednokierunkową.
pomysł został opatentowany w 1983 roku przez MIT, ale dopiero w pierwszych dniach Internetu algorytm RSA zaczął postrzegać powszechną adopcję jako ważne narzędzie bezpieczeństwa.
jak działa szyfrowanie RSA?
poniższy tekst będzie nieco uproszczeniem, bo zbyt wielu czytelników zapewne zostało okaleczonych przez nauczyciela matematyki z liceum., Aby matematyka nie wymykała się zbytnio spod kontroli, będziemy upraszczać niektóre pojęcia i używać znacznie mniejszych liczb. W rzeczywistości szyfrowanie RSA wykorzystuje liczby pierwsze, które są znacznie większe i istnieje kilka innych złożoności.
istnieje kilka różnych pojęć, które będziesz musiał ogarnąć, zanim będziemy mogli wyjaśnić, jak to wszystko pasuje do siebie. Należą do nich funkcje zapadkowe, generowanie liczb pierwszych, funkcja totient oraz osobne procesy związane z przetwarzaniem kluczy publicznych i prywatnych wykorzystywanych w procesach szyfrowania i deszyfrowania.,
funkcje drzwi pułapek
szyfrowanie RSA działa zgodnie z założeniem, że algorytm jest łatwy do obliczenia w jednym kierunku, ale prawie niemożliwy w odwrotnym kierunku. Na przykład, jeśli powiedziano ci, że 701,111 jest iloczynem dwóch liczb pierwszych, czy będziesz w stanie dowiedzieć się, czym są te dwie liczby?
nawet z kalkulatorem lub komputerem, większość z nas nie miałaby pojęcia od czego zacząć, nie mówiąc już o możliwości znalezienia odpowiedzi. Ale jeśli przewrócimy sprawy, stanie się to o wiele łatwiejsze., Jaki jest wynik:
907 x 773
gdybyś był wystarczająco znudzony, byłbyś w stanie wyciągnąć telefon lub może obliczyć go w głowie, aby odkryć, że odpowiedzią jest wspomniany wcześniej 701,111. Te 907 i 773 są liczbami pierwszymi, które odpowiadają na nasze pierwsze pytanie, które pokazuje nam, że pewne równania mogą być łatwe do zrozumienia w jeden sposób, ale pozornie niemożliwe w odwrotnej kolejności.
Innym ciekawym aspektem tego równania jest to, że łatwo jest obliczyć jedną z liczb pierwszych, jeśli masz już drugą, a także produkt., Jeśli powiedziano ci, że 701,111 jest wynikiem 907 pomnożonym przez inną liczbę pierwszą, możesz obliczyć drugą liczbę pierwszą za pomocą następującego równania:
701,111 ÷ 907 = 773
ponieważ zależność między tymi liczbami jest prosta do obliczenia w jednym kierunku, ale niewiarygodnie trudna w odwrotnej kolejności, równanie jest znane jako funkcja drzwi pułapki. Należy pamiętać, że podczas gdy powyższy przykład jest trudny do zrozumienia dla ludzi, komputery mogą wykonać operację w trywialnym czasie.
z tego powodu RSA używa znacznie większych liczb., Rozmiar liczb pierwszych w rzeczywistej implementacji RSA jest różny, ale w 2048-bitowym RSA, połączyłyby się, tworząc klucze o długości 617 cyfr. Aby pomóc ci go zwizualizować, kluczem będzie Liczba o tej wielkości:
Generowanie liczb pierwszych
wymienione powyżej funkcje drzwi pułapek stanowią podstawę działania schematów szyfrowania klucza publicznego i prywatnego. Ich właściwości pozwalają na współdzielenie kluczy publicznych bez narażania wiadomości lub ujawniania klucza prywatnego. Umożliwiają one również szyfrowanie danych jednym kluczem w sposób, który może być odszyfrowany tylko przez drugi klucz z pary.,
pierwszym krokiem szyfrowania wiadomości za pomocą RSA jest wygenerowanie kluczy. Aby to zrobić, potrzebujemy dwóch liczb pierwszych (p i q), które są wybierane za pomocą testu primality. Test pierwszości jest algorytmem, który skutecznie wyszukuje liczby pierwsze, np. Test Rabina-Millera.
liczby pierwsze w RSA muszą być bardzo duże, a także stosunkowo odległe od siebie. Liczby, które są małe lub bliżej siebie, są znacznie łatwiejsze do złamania. Mimo to nasz przykład użyje mniejszych liczb, aby ułatwić śledzenie i obliczanie.,
Załóżmy, że test pierwszości daje nam liczby pierwsze, których użyliśmy powyżej, 907 i 773. Następnym krokiem jest odkrycie modułu (n), używając następującego wzoru:
N = P x q
gdzie P = 907 i q = 773
dlatego:
N = 907 x 773
n = 701,111
funkcja totient Carmichaela
gdy mamy n, używamy funkcji totient Carmichaela.funkcja totient:
λ(n) = LCM (p − 1, q − 1)
jeśli minęło trochę czasu, odkąd trafiłeś na podręczniki do matematyki, powyższe może wyglądać nieco przerażająco., Możesz pominąć tę część i po prostu zaufać, że matematyka działa, w przeciwnym razie zostań z nami na kilka dodatkowych obliczeń. Wszystko zostanie wyjaśnione tak szczegółowo, jak to możliwe, aby pomóc ci zrozumieć podstawy.
dla tych, którzy nie są świadomi λ(n) oznacza iloczyn Carmichaela dla n, podczas gdy lcm oznacza najniższą wspólną wielokrotność, która jest najniższą liczbą, na którą można podzielić zarówno p jak i Q. Istnieje kilka różnych sposobów, aby to zrozumieć, ale najłatwiej jest zaufać kalkulatorowi online, który wykona równanie za Ciebie., Więc weźmy nasze liczby do równania:
λ (701,111) = lcm (907 − 1, 773 − 1)
λ(701,111) = lcm (906,772)
korzystając z kalkulatora podlinkowanego powyżej, daje nam to:
λ(701,111) = 349,716
Generowanie klucza publicznego
teraz, gdy mamy jeśli chodzi o nasze liczby pierwsze, czas odkryć nasz klucz publiczny. W RSA klucze publiczne składają się z liczby pierwszej e, a także N. liczba e może być dowolna pomiędzy 1 a wartością λ(n), która w naszym przykładzie wynosi 349,716. ,
ponieważ klucz publiczny jest udostępniany otwarcie, nie jest tak ważne, aby e była liczbą losową. W praktyce e jest na ogół ustawiony na 65 537, ponieważ gdy dużo większe liczby są wybierane losowo, sprawia to, że szyfrowanie jest znacznie mniej wydajne. W dzisiejszym przykładzie będziemy utrzymywać małe liczby, aby obliczenia były wydajne. Powiedzmy:
e = 11
nasze ostateczne zaszyfrowane dane nazywane są szyfrem (c). Wywodzimy go z wiadomości tekstowej (m), stosując klucz publiczny o następującej formule:
c = me mod n
już wymyśliliśmy e i znamy również N., Jedyne co musimy wyjaśnić to mod. Jest to trochę poza głębią tego artykułu, ale odnosi się do operacji modulo, co zasadniczo oznacza pozostałą pozostałość po podzieleniu jednej strony przez drugą. Na przykład:
10 mod 3 = 1
dzieje się tak dlatego, że 3 przechodzi w 10 trzy razy, z pozostałą częścią 1.
powrót do naszego równania. Aby wszystko było proste, powiedzmy ,że wiadomość (m), którą chcemy zaszyfrować i zachować w tajemnicy, to tylko jedna liczba, 4., Podłączmy wszystko:
c = me mod n
c = 411 mod 701,111
c = 4,194,304 mod 701,111
jeszcze raz, aby ułatwić obsługę modulo, będziemy używać kalkulatora online, ale zapraszamy do samodzielnego rozwiązania. Wpisując 4,194,304 do kalkulatora online, daje nam:
c = 688,749
dlatego, gdy używamy RSA do szyfrowania naszej wiadomości, 4, za pomocą naszego klucza publicznego, daje nam zaszyfrowany tekst 688,749., Poprzednie kroki mogły wydawać się trochę zbyt trudne z matematyki, ale ważne jest, aby powtórzyć, co się naprawdę stało.
mieliśmy wiadomość 4, którą chcieliśmy zachować w tajemnicy. Zastosowaliśmy do niego klucz publiczny, co dało nam zaszyfrowany wynik 688 749. Teraz, gdy jest zaszyfrowany, możemy bezpiecznie wysłać numer 688,749 do właściciela pary kluczy. Są jedyną osobą, która będzie w stanie odszyfrować go swoim kluczem prywatnym. Kiedy go odszyfrowają, zobaczą wiadomość, którą naprawdę wysyłaliśmy, 4.,
Generowanie klucza prywatnego
w szyfrowaniu RSA, gdy dane lub wiadomość zostaną zamienione w szyfrogram z kluczem publicznym, może on zostać odszyfrowany tylko przez klucz prywatny z tej samej pary kluczy. Klucze prywatne składają się z d i N. znamy już n, A do znalezienia d używa się następującego równania:
d =1/e Mod λ(n)
w sekcji Generowanie klucza publicznego powyżej zdecydowaliśmy już, że w naszym przykładzie E będzie równe 11. Podobnie wiemy, że λ (n) równa się 349,716 z naszej wcześniejszej pracy pod funkcją totient Carmichaela., Sprawy stają się nieco bardziej skomplikowane, gdy natkniemy się na ten fragment wzoru:
1/e mod
to równanie może wyglądać tak, jakby wymagało podzielenia 1 przez 11, ale tak nie jest. Zamiast tego, to po prostu symbolizuje, że musimy obliczyć modularną odwrotność e (która w tym przypadku jest 11) i λ(n) (która w tym przypadku jest 349,716).
zasadniczo oznacza to, że zamiast wykonywania standardowej operacji modulo, będziemy używać odwrotności., Zwykle znajduje się to w rozszerzonym algorytmie Euklidesowym, ale jest to trochę poza zakresem tego artykułu, więc będziemy po prostu oszukiwać i używać kalkulatora online., Teraz, gdy rozumiemy wszystko, co się dzieje, podłączmy nasze informacje do Formuły:
d = 1/11 mod 349,716
aby wykonać tę operację, po prostu wprowadź 11 (lub dowolną wartość, którą możesz mieć dla e, jeśli próbujesz tego z własnym przykładem), gdzie mówi liczba całkowita i 349,716 (lub dowolną wartość, którą możesz mieć dla λ(n), Jeśli próbujesz tego z własnym przykładem) gdzie mówi Modulo w kalkulatorze online, który został połączony powyżej., Jeśli zrobiłeś to poprawnie, powinieneś uzyskać wynik, w którym:
d = 254, 339
teraz, gdy mamy wartość d, możemy odszyfrować wiadomości, które zostały zaszyfrowane naszym kluczem publicznym, używając następującej formuły:
m = cd mod n
możemy teraz wrócić do zaszyfrowanego tekstu w sekcji Generowanie klucza prywatnego. Kiedy zaszyfrowaliśmy wiadomość kluczem publicznym, dało nam to wartość c wynoszącą 688 749. Z góry wiemy, że d równa się 254,339. Wiemy również, że n równa się 701,111. To daje nam:
m = 688,749254,339 mod 701,111.,
jak zapewne zauważyłeś, próba wzięcia numeru do mocy 254,339 może być trochę zbyt duża dla większości normalnych kalkulatorów. Zamiast tego będziemy używać internetowego kalkulatora odszyfrowującego RSA. Jeśli chcesz użyć innej metody, zastosuj uprawnienia tak, jak zwykle i wykonaj operację modułu w taki sam sposób, jak zrobiliśmy to w sekcji Generowanie klucza publicznego.,
w kalkulatorze linkowanym powyżej wprowadź 701,111, gdzie mówi Moduł Zasilania: N, 254,399, gdzie mówi klucz deszyfrujący: D, i 688,749, gdzie mówi wiadomość zaszyfrowaną w postaci liczbowej, jak pokazano poniżej:
Po wprowadzeniu danych naciśnij Deszyfruj, co spowoduje umieszczenie liczb przez kod źródłowy.wzór deszyfrowania, który został wymieniony powyżej. To da Ci oryginalną wiadomość w polu poniżej. Jeśli zrobiłeś wszystko poprawnie, powinieneś otrzymać odpowiedź 4, która była oryginalną wiadomością zaszyfrowaną naszym kluczem publicznym.,
Jak działa szyfrowanie RSA w praktyce
powyższe sekcje powinny dać ci rozsądne zrozumienie, jak działa matematyka stojąca za szyfrowaniem kluczy publicznych. Może to być trochę mylące, ale nawet ci, którzy nie rozumieją zawiłości równań, mogą mam nadzieję zabrać kilka ważnych informacji na temat procesu.
w powyższych krokach pokazaliśmy, w jaki sposób dwa podmioty mogą bezpiecznie komunikować się bez uprzedniego udostępnienia kodu. Po pierwsze, każdy z nich musi skonfigurować własne pary kluczy i udostępnić sobie klucz publiczny., Oba podmioty muszą zachować swoje klucze prywatne w tajemnicy, aby ich komunikacja pozostała bezpieczna.
gdy nadawca ma klucz publiczny odbiorcy, może go użyć do szyfrowania danych, które chce zabezpieczyć. Po zaszyfrowaniu kluczem publicznym można go odszyfrować tylko kluczem prywatnym z tej samej pary kluczy. Nawet ten sam klucz publiczny nie może być użyty do odszyfrowania danych. Wynika to z właściwości funkcji drzwi zapadkowych, o których wspomnialiśmy powyżej.
gdy odbiorca otrzyma zaszyfrowaną wiadomość, używa swojego klucza prywatnego, aby uzyskać dostęp do danych., Jeśli odbiorca chce zwrócić komunikację w bezpieczny sposób, może zaszyfrować swoją wiadomość kluczem publicznym strony, z którą się komunikuje. Ponownie, po zaszyfrowaniu za pomocą klucza publicznego, dostęp do informacji można uzyskać tylko za pomocą dopasowanego klucza prywatnego.
w ten sposób szyfrowanie RSA może być używane przez nieznane wcześniej strony do bezpiecznego przesyłania danych między sobą. Znaczna część kanałów komunikacji, z których korzystamy w naszym życiu online, została zbudowana z tej podstawy.,
w jaki sposób bardziej skomplikowane wiadomości są szyfrowane za pomocą RSA?
w naszym przykładzie wiele uprościliśmy, aby ułatwić zrozumienie, dlatego zaszyfrowaliśmy tylko wiadomość „4”. Możliwość szyfrowania liczby 4 nie wydaje się szczególnie przydatna, więc możesz się zastanawiać, jak zaszyfrować bardziej skomplikowany zestaw danych, taki jak klucz symetryczny (który jest najczęściej używany przez RSA), a nawet wiadomość.,
niektórzy ludzie mogą być zakłopotani tym, jak klucz taki jak „n38cb29fkbjh138g7fqijnf3kaj84f8b9f…” lub wiadomość taka jak „buy me a sandwich” może być szyfrowany za pomocą algorytmu takiego jak RSA, który zajmuje się cyframi, a nie literami. Rzeczywistość jest taka, że wszystkie informacje przetwarzane przez nasze komputery są przechowywane w binarnych (1s i 0s) i używamy standardów kodowania, takich jak ASCII lub Unicode, aby reprezentować je w sposób, który ludzie mogą zrozumieć (litery).,
oznacza to, że klucze takie jak „n38cb29fkbjh138g7fqijnf3kaj84f8b9f…” i komunikaty takie jak „buy me a sandwich” istnieją już jako liczby, które można łatwo obliczyć w algorytmie RSA. Liczby, przez które są reprezentowane, są znacznie większe i trudniejsze do zarządzania, dlatego wolimy zajmować się alfanumerycznymi znakami, a nie zbieraniem binarnych.
Jeśli chcesz zaszyfrować dłuższy klucz sesji lub bardziej złożoną wiadomość za pomocą RSA, wymagałoby to po prostu znacznie większej liczby.,
Padding
Kiedy RSA jest zaimplementowany, używa czegoś o nazwie padding, aby zapobiec wielu atakom. Aby wyjaśnić, jak to działa, zaczniemy od przykładu. Załóżmy, że wysłałeś zakodowaną wiadomość do znajomego:
Droga Karen,
Mam nadzieję, że masz się dobrze. Nadal jemy jutro kolację?
Z poważaniem,
James
Załóżmy, że zakodowałeś wiadomość w prosty sposób, zmieniając każdą literę na tę, która podąża za nią w alfabecie. Spowoduje to zmianę komunikatu na:
Efbs Lbsfo,
j ipqf zpv bsf xfmm., Bsf xf tujmm ibwjoh ejoofs upnpsspx?
Zpvst Tjodfsfmz,
Kbnft
Jeśli Twoi wrogowie przechwycili ten list, istnieje sztuczka, której mogliby użyć, aby spróbować złamać kod. Mogą spojrzeć na format listu i spróbować odgadnąć, co wiadomość może być mówi. Wiedzą, że ludzie zwykle zaczynają swoje listy od „Cześć”, „Cześć”,” droga ” lub wielu innych konwencji.
gdyby spróbowali zastosować „cześć” lub „cześć” jako pierwsze słowo, zobaczyliby, że nie pasuje do liczby znaków. Mogą wtedy spróbować „kochanie”., Pasuje, ale to nie musi nic znaczyć. Napastnicy po prostu spróbowali i zobaczyli, dokąd ich to doprowadziło. Więc zmienili litery „e”, „f”, ” b „I ” s” odpowiednio na „d”, „e”, „a” i „R”. Dałoby im to:
drogi Laseo,
J ipqe zpv są xemm. Czy xe tujmm iawjoh djooes upnpsspx?
Zpvrt tjoderemz,
Kanet
nadal wygląda to dość myląco, więc napastnicy mogą spróbować przyjrzeć się innym konwencjom, np. jak kończymy nasze listy. Ludzie często dodają „od „Lub” Z poważaniem ” na końcu, ale żaden z nich nie pasuje do formatu., Zamiast tego atakujący mogą spróbować „Z poważaniem” i zastąpić inne litery, aby zobaczyć, gdzie je dostanie. Zmieniając odpowiednio „z”, „p”, „v”,” t”,” j „” o”,” d „I” m „Z” y”,” o”,” u”,” s”,” i”,” n”,” c „i” l ” otrzymają:
Dear Lasen,
I ioqe you are xell. Czy xe tuill iawinh dinnes uonossox?
Z poważaniem,
Kanet
Po tej modyfikacji wygląda na to, że napastnicy zaczynają coś robić. Znaleźli słowa „Ja”, ” Ty ” i „jesteś”, oprócz słów, które składały się na ich początkowe przypuszczenia.,
widząc, że słowa są w prawidłowej kolejności gramatycznej, napastnicy mogą być pewni, że zmierzają we właściwym kierunku. Do tej pory prawdopodobnie zdali sobie sprawę, że kod obejmuje każdą literę zmienianą na tę, która podąża za nią w alfabecie. Gdy zdają sobie z tego sprawę, ułatwia to przetłumaczenie reszty i przeczytanie oryginalnej wiadomości.
powyższy przykład był tylko prostym kodem, ale jak widać, struktura wiadomości może dać atakującym wskazówki dotyczące jej treści., Jasne, trudno było zrozumieć przesłanie tylko na podstawie jego struktury i wymagało to pewnych wyedukowanych domysłów, ale trzeba pamiętać, że komputery są w tym znacznie lepsze niż my. Oznacza to, że mogą one być wykorzystane do opracowania znacznie bardziej złożonych kodów w znacznie krótszym czasie, w oparciu o wskazówki Pochodzące ze struktury i innych elementów.
Jeśli struktura może doprowadzić do pęknięcia kodu i ujawnienia zawartości wiadomości, potrzebujemy sposobu na ukrycie struktury, aby wiadomość była bezpieczna. To prowadzi nas do padding.,
gdy wiadomość jest wypełniona, randomizowane dane są dodawane, aby ukryć oryginalne wskazówki formatowania, które mogą prowadzić do uszkodzenia zaszyfrowanej wiadomości. W przypadku RSA sprawy są nieco bardziej skomplikowane, ponieważ zaszyfrowany klucz nie ma oczywistego formatowania litery, które pomogło nam dać wskazówki w powyższym przykładzie.
mimo to przeciwnicy mogą użyć wielu ataków, aby wykorzystać matematyczne właściwości kodu i złamać zaszyfrowane dane. Z powodu tego zagrożenia, implementacje RSA używają schematów wypełniania, takich jak OAEP, aby osadzać dodatkowe dane w wiadomości., Dodanie tego wypełnienia przed zaszyfrowaniem wiadomości sprawia, że RSA jest znacznie bezpieczniejsze.
podpisywanie wiadomości
RSA może być używane nie tylko do szyfrowania danych. Jego właściwości sprawiają, że jest to przydatny system do potwierdzania, że wiadomość została wysłana przez podmiot, który twierdzi, że ją wysłał, a także udowodnienia, że wiadomość nie została zmieniona lub zmieniona.,
Gdy ktoś chce udowodnić autentyczność swojej wiadomości, może obliczyć hash (funkcję, która pobiera dane o dowolnym rozmiarze i zamienia je w wartość o stałej długości) tekstu jawnego, a następnie podpisać go swoim kluczem prywatnym. Podpisują hash, stosując ten sam wzór, który jest używany w deszyfrowaniu (m = cd mod n). Po podpisaniu wiadomości wysyłają ten podpis cyfrowy do odbiorcy wraz z wiadomością.,
jeśli odbiorca otrzyma wiadomość z podpisem cyfrowym, może użyć podpisu, aby sprawdzić, czy wiadomość została autentycznie podpisana kluczem prywatnym osoby, która twierdzi, że ją wysłała. Mogą również sprawdzić, czy wiadomość została zmieniona przez atakujących po jej wysłaniu.
aby sprawdzić podpis cyfrowy, odbiorca najpierw używa tej samej funkcji skrótu, aby znaleźć wartość skrótu otrzymanej wiadomości., Odbiorca następnie stosuje klucz publiczny nadawcy do podpisu cyfrowego, używając formuły szyfrowania (C = me mod n), aby nadać mu hash podpisu cyfrowego.
porównując hash wiadomości, która została odebrana wraz z Hashem z zaszyfrowanego podpisu cyfrowego, odbiorca może stwierdzić, czy wiadomość jest autentyczna. Jeśli obie wartości są takie same, wiadomość nie została zmieniona, ponieważ została podpisana przez pierwotnego nadawcę. Gdyby wiadomość została zmieniona choćby o jeden znak, wartość skrótu byłaby zupełnie inna.,
bezpieczeństwo RSA ataki
podobnie jak większość kryptosystemów, bezpieczeństwo RSA zależy od tego, jak jest zaimplementowane i używane. Ważnym czynnikiem jest wielkość klucza. Im większa liczba bitów w kluczu (zasadniczo długość klucza), tym trudniej jest przebić się przez ataki takie jak brute-forcing i faktoring.
ponieważ algorytmy klucza asymetrycznego, takie jak RSA, mogą być łamane przez faktoryzację całkowitą, podczas gdy algorytmy klucza symetrycznego, takie jak AES, nie mogą, klucze RSA muszą być znacznie dłuższe, aby osiągnąć ten sam poziom bezpieczeństwa.,
obecnie największy rozmiar klucza, który został uwzględniony, wynosi 768 bitów. Zostało to zrobione przez zespół naukowców w ciągu dwóch lat, przy użyciu setek maszyn.
ponieważ faktoring został zakończony pod koniec 2009 roku, a moc obliczeniowa znacznie wzrosła od tego czasu, można założyć, że próba o podobnej intensywności może teraz mieć znacznie większy klucz RSA.
mimo to, czas i zasoby potrzebne do tego rodzaju ataku, sprawiają, że jest on poza zasięgiem większości hakerów i trafia do sfery państw narodowych., Najlepsza długość klucza zależy od indywidualnego modelu zagrożenia. Narodowy Instytut Standardów i technologii zaleca minimalny rozmiar klucza 2048-bitowego, ale klucze 4096-bitowe są również używane w niektórych sytuacjach, gdy poziom zagrożenia jest wyższy.
Faktoring jest tylko jednym ze sposobów na złamanie RSA. Wiele innych ataków może złamać szyfrowanie przy mniejszej ilości zasobów, ale zależy to od implementacji i innych czynników, niekoniecznie samego RSA. Niektóre z nich to:
czy liczby pierwsze są naprawdę losowe?,
niektóre implementacje RSA wykorzystują słabe generatory liczb losowych do wymyślania liczb pierwszych. Jeśli te liczby nie są wystarczająco losowe, znacznie ułatwia to atakującym ich uwzględnienie i złamanie szyfrowania. Tego problemu można uniknąć za pomocą zabezpieczonego kryptograficznie generatora liczb pseudolosowych.
słabe generowanie kluczy
klucze RSA muszą mieścić się w określonych parametrach, aby były bezpieczne. Jeśli liczby pierwsze p i q są zbyt blisko siebie, klucz można łatwo odkryć. Podobnie liczba d, która stanowi część klucza prywatnego, nie może być zbyt mała., Niska wartość ułatwia rozwiązanie. Ważne jest, aby te liczby były odpowiedniej długości, aby twój klucz był bezpieczny.
ataki bocznokanałowe
są to ataki, które nie łamią RSA bezpośrednio, ale zamiast tego wykorzystują informacje z jego implementacji, aby dać atakującym wskazówki dotyczące procesu szyfrowania. Ataki te mogą obejmować takie rzeczy, jak analiza ilości energii, która jest używana, lub analiza przewidywania gałęzi, która wykorzystuje pomiary czasu wykonania do odkrycia klucza prywatnego.
inny rodzaj ataku na boczny kanał jest znany jako atak czasowy., Jeśli atakujący ma możliwość zmierzenia czasu deszyfrowania na komputerze celu dla wielu różnych zaszyfrowanych wiadomości, informacje te mogą umożliwić atakującemu ustalenie klucza prywatnego celu.
Większość implementacji RSA unika tego ataku, dodając jednorazową wartość podczas procesu szyfrowania, co usuwa tę korelację. Proces ten nazywany jest oślepianiem kryptograficznym.
czy szyfrowanie RSA jest bezpieczne na przyszłość?
dobrą wiadomością jest to, że RSA jest uważany za bezpieczny w użyciu, pomimo tych możliwych ataków., Zastrzeżenie polega na tym, że musi być poprawnie zaimplementowany i użyć klucza, który mieści się w odpowiednich parametrach. Jak już omówiliśmy, implementacje, które nie używają wypełnienia, używają nieodpowiednich rozmiarów liczb pierwszych lub mają inne luki, nie mogą być uważane za bezpieczne.
Jeśli chcesz używać szyfrowania RSA, upewnij się, że używasz klucza o wartości co najmniej 1024 bitów. Osoby z modelami o wyższym zagrożeniu powinny trzymać się kluczy 2048 lub 4096 bitów, jeśli chcą korzystać z RSA z pewnością., Dopóki jesteś świadomy słabości RSA i używasz go poprawnie, powinieneś czuć się bezpiecznie używać RSA do udostępniania kluczy i innych podobnych zadań, które wymagają szyfrowania klucza publicznego.
Zobacz też: wyjaśniono typowe typy szyfrowania