RSA (cryptosystem) (Polski)

Korzystanie z chińskiego algorytmu Rest

dla wydajności wiele popularnych bibliotek kryptograficznych (takich jak OpenSSL, Java i.NET) stosuje następującą optymalizację do odszyfrowywania i podpisywania w oparciu o Chińskie twierdzenie Rest. Następujące wartości są wstępnie obliczane i przechowywane jako część klucza prywatnego:

te wartości pozwalają odbiorcy na bardziej wydajne obliczanie wykładnika m = cd (Mod PQ) w następujący sposób:

jest to bardziej wydajne niż obliczanie wykładnika przez kwadrat, nawet jeśli trzeba obliczyć dwa wykładniki modularne., Powodem jest to, że te dwa wykładniki modularne używają mniejszego wykładnika i mniejszego modułu.

integer Factorisation and RSA problemedytuj

bezpieczeństwo kryptosystemu RSA opiera się na dwóch matematycznych problemach: problem faktoringu dużych liczb i problem RSA. Pełne odszyfrowanie szyfrogramu RSA jest uważane za niewykonalne przy założeniu, że oba te problemy są trudne, tzn. nie istnieje skuteczny algorytm do ich rozwiązania., Zapewnienie bezpieczeństwa przed częściowym odszyfrowaniem może wymagać dodania bezpiecznego schematu wypełniania.

problem RSA jest zdefiniowany jako zadanie pobierania pierwiastków eth modulo złożonych n: odzyskiwanie wartości m takiej, że c ≡ me (mod n), gdzie (n, e) jest kluczem publicznym RSA, a c jest szyfrem RSA. Obecnie najbardziej obiecującym podejściem do rozwiązania problemu RSA jest współczynnik modułu N. dzięki możliwości odzyskania czynników pierwszych atakujący może obliczyć tajny wykładnik d z klucza publicznego (n, e), a następnie odszyfrować c za pomocą standardowej procedury., Aby to osiągnąć, atakujący współczynniki N na p i q i oblicza lcm (p-1, q-1), który pozwala na wyznaczenie d z e. nie znaleziono jeszcze metody wielomianowej dla faktorowania dużych liczb całkowitych na klasycznym komputerze, ale nie udowodniono, że żadna nie istnieje. Zobacz Faktoryzacja liczby całkowitej w celu omówienia tego problemu.

wielokrotny wielomian kwadratowy sito (MPQS) może być używany do czynnika publicznego modułu N.,

pierwsza Faktoria RSA-512 w 1999 roku używała setek komputerów i wymagała równowartości 8400 MIPS lat, w czasie około siedmiu miesięcy. Do 2009 roku Benjamin Moody mógł wykorzystać klucz RSA-512 w ciągu 73 dni, używając tylko oprogramowania publicznego (ggnfs) i swojego komputera stacjonarnego (dwurdzeniowego Athlon64 z procesorem 1900 MHz). Tylko mniej niż pięć gigabajtów pamięci dyskowej było wymagane i około 2,5 gigabajtów pamięci RAM dla procesu przesiewania.,

Rivest, Shamir i Adleman zauważyli, że Miller wykazał, że-zakładając prawdziwość rozszerzonej hipotezy Riemanna-znalezienie d Z n I e jest tak trudne, jak faktorowanie n na p i q (do wielomianowej różnicy czasu). Jednak Rivest, Shamir i Adleman zauważyli w sekcji IX / D swojej pracy, że nie znaleźli dowodu na to, że odwrócenie RSA jest tak trudne, jak faktoring.

od 2020 roku największa publicznie znana liczba RSA wynosiła 829 bitów (250 cyfr dziesiętnych, RSA-250). Jego Faktoryzacja, dzięki najnowocześniejszej implementacji rozproszonej, zajęła około 2700 lat procesora., W praktyce klucze RSA mają zwykle długość od 1024 do 4096 bitów. W 2003 r. RSA Security oszacowała, że 1024-bitowe klucze prawdopodobnie staną się możliwe do złamania do 2010 r. Od 2020 roku nie wiadomo, czy takie klucze mogą zostać złamane, ale minimalne zalecenia zostały przeniesione do co najmniej 2048 bitów. Ogólnie przyjmuje się, że RSA jest bezpieczne, jeśli n jest wystarczająco duże, poza obliczeniami kwantowymi.

Jeśli n jest 300 bitów lub krótsze, można je obliczyć w ciągu kilku godzin na komputerze osobistym, przy użyciu oprogramowania już swobodnie dostępnego., Klucze 512 bitów okazały się praktycznie łamalne w 1999 roku, kiedy RSA-155 został uwzględniony przy użyciu kilkuset komputerów, a te są obecnie uwzględniane w ciągu kilku tygodni przy użyciu wspólnego sprzętu. Exploity wykorzystujące 512-bitowe certyfikaty podpisywania kodu, które mogły zostać uwzględnione, zostały zgłoszone w 2011 roku. Teoretyczne urządzenie sprzętowe o nazwie TWIRL, opisane przez Shamira i Tromera w 2003 roku, zakwestionowało bezpieczeństwo kluczy 1024-bitowych.,

w 1994 roku Peter Shor pokazał, że komputer kwantowy – jeśli kiedykolwiek mógłby być praktycznie stworzony do tego celu – byłby w stanie liczyć czas wielomianowy, łamiąc RSA; patrz algorytm Shor.

wadliwe generowanie kluczówedytuj

znalezienie dużych liczb pierwszych P I q odbywa się zazwyczaj poprzez testowanie losowych liczb o prawidłowej wielkości za pomocą probabilistycznych testów primality, które szybko eliminują praktycznie wszystkie nieprimes.

liczby p i q nie powinny być „zbyt blisko”, aby Faktoryzacja Fermata dla n nie powiodła się., Jeśli p-q jest mniejsze niż 2n1/4 (n = P * q, Co nawet dla małych 1024-bitowych wartości n wynosi 3×1077) rozwiązanie dla p i q jest trywialne. Ponadto, jeśli p – 1 lub q − 1 ma tylko małe współczynniki pierwsze, n może być szybko obliczone przez algorytm P − 1 Pollarda, a zatem takie wartości p lub q powinny zostać odrzucone.

ważne jest, aby prywatny wykładnik d był wystarczająco duży. Michael J. Wiener pokazał, że jeśli p jest pomiędzy q A 2Q (co jest dość typowe) i d < n1/4/3, to d można obliczyć efektywnie z n I e.,

nie jest znany atak na małe publiczne wykładniki, takie jak e = 3, pod warunkiem użycia odpowiedniego paddingu. Atak Coppersmith ' A ma wiele zastosowań w atakowaniu RSA, szczególnie jeśli publiczny wykładnik e jest mały i jeśli zaszyfrowana wiadomość jest krótka i nie jest wyściełana. 65537 jest powszechnie używaną wartością dla e; wartość tę można uznać za kompromis między unikaniem potencjalnych ataków o małym wykładniku a dalszym umożliwianiem skutecznego szyfrowania (lub weryfikacji podpisu)., Specjalna Publikacja NIST dotycząca bezpieczeństwa komputera (SP 800-78 Rev 1 z sierpnia 2007) nie dopuszcza wykładników publicznych e mniejszych niż 65537, ale nie podaje powodu tego ograniczenia.

w październiku 2017 roku zespół naukowców z Uniwersytetu Masaryka ogłosił lukę ROCA, która wpływa na klucze RSA generowane przez algorytm zawarty w bibliotece Infineon znanej jako RSALib. Wykazano, że dotyczy to dużej liczby kart inteligentnych i modułów trusted platform modules (TPMS). Wrażliwe klucze RSA są łatwo identyfikowane za pomocą programu testowego wydanego przez zespół.,

Znaczenie silnego generowania liczb losowychedytuj

silny kryptograficznie generator liczb losowych, który został odpowiednio zaszeregowany z odpowiednią entropią, musi być użyty do generowania liczb pierwszych p I q. analiza porównująca miliony kluczy publicznych zebranych z Internetu została przeprowadzona na początku 2012 roku przez Arjena K. Lenstra, Jamesa P. Hughesa, Maxime Augiera, Joppe W. Bos, Thorstena Kleinjunga i Christophe ' a Wachtera. Udało im się obliczyć 0,2% kluczy używając tylko algorytmu Euklidesa.

wykorzystali słabość unikalną dla kryptosystemów opartych na faktoryzacji całkowitej., Jeśli N = pq jest jednym kluczem publicznym, a n' = p' q 'jest innym, to jeśli przez przypadek p= p '(ale q nie jest równe q'), to proste obliczenie GCD(n, n') = p powoduje zarówno N, jak i N', całkowicie kompromitując oba klucze. Lenstra et al. należy zauważyć, że problem ten można zminimalizować poprzez użycie silnego losowego ziarna o długości bitów dwukrotnie większej od zamierzonego poziomu bezpieczeństwa lub poprzez zastosowanie deterministycznej funkcji do wyboru Q podanego p, zamiast wyboru P I q niezależnie.

Nadia Heninger była częścią grupy, która przeprowadziła podobny eksperyment. Wykorzystali pomysł Daniela J., Bernstein obliczył GCD każdego klucza RSA n względem iloczynu wszystkich pozostałych kluczy n', które znaleźli (729 milionów cyfr), zamiast obliczać każdy gcd(n,n') oddzielnie, osiągając tym samym bardzo znaczące przyspieszenie, ponieważ po jednym dużym podziale problem GCD jest normalnej wielkości.

Heninger mówi na swoim blogu, że złe klucze wystąpiły prawie całkowicie w aplikacjach wbudowanych, w tym „firewallach, routerach, urządzeniach VPN, urządzeniach do zdalnej administracji serwerami, drukarkach, projektorach i telefonach VOIP” od ponad 30 producentów., Heninger wyjaśnia, że problem jedynki dzielonej przez obie grupy wynika z sytuacji, w których generator liczb pseudorandomowych jest początkowo słabo zaszeregowany, a następnie jest ponownie zaszeregowany między generacją pierwszej i drugiej liczby pierwszej. Zastosowanie nasion o wystarczająco wysokiej entropii uzyskanej z czasów skoku klawisza lub szumu diod elektronicznych lub szumu atmosferycznego z odbiornika radiowego dostrojonego między stacjami powinno rozwiązać problem.

silne generowanie liczb losowych jest ważne w każdej fazie kryptografii klucza publicznego., Na przykład, jeśli słaby generator jest używany do kluczy symetrycznych, które są dystrybuowane przez RSA, to podsłuchiwacz może ominąć RSA i odgadnąć klucze symetryczne bezpośrednio.

ataki Czasoweedytuj

Kocher opisał nowy atak na RSA w 1995 roku: jeśli atakująca Eve zna sprzęt Alice wystarczająco szczegółowo i jest w stanie zmierzyć czas odszyfrowania dla kilku znanych szyfrów, Eve może szybko wydedukować klucz deszyfrujący D. Atak ten może być również zastosowany przeciwko schematowi sygnatury RSA., W 2003 roku Boneh i Brumley zademonstrowali bardziej praktyczny atak zdolny do odzyskiwania faktoryzacji RSA za pośrednictwem połączenia sieciowego (np. z serwera www z obsługą Secure Sockets Layer (SSL)).

jednym ze sposobów udaremnienia tych ataków jest zapewnienie, że operacja deszyfrowania zajmuje stałą ilość czasu dla każdego szyfru. Jednak takie podejście może znacznie zmniejszyć wydajność., Zamiast tego, większość implementacji RSA używa alternatywnej techniki znanej jako oślepianie kryptograficzne. Oślepianie RSA wykorzystuje multiplikatywną własność RSA. Zamiast obliczać cd (mod n), Alice najpierw wybiera tajemną losową wartość r i oblicza (rec) d (mod n). Wynikiem tego obliczenia, po zastosowaniu twierdzenia Eulera, jest rcd (mod n), a więc efekt r można usunąć mnożąc przez jego odwrotność. Dla każdego zaszyfrowanego tekstu wybierana jest nowa wartość r. Po zastosowaniu Oślepiania czas odszyfrowania nie jest już skorelowany z wartością wejściowego tekstu szyfrowego, więc atak czasowy nie powiedzie się.,

Adaptacyjne ataki zaszyfrowaneedytuj

w 1998 roku Daniel Bleichenbacher opisał pierwszy praktyczny adaptacyjny atak zaszyfrowany zaszyfrowany tekst, przeciwko wiadomościom zaszyfrowanym przez RSA przy użyciu systemu padding PKCS #1 v1 (system padding randomizuje i dodaje strukturę do wiadomości zaszyfrowanej przez RSA, dzięki czemu możliwe jest określenie, czy odszyfrowana wiadomość jest prawidłowa). Ze względu na błędy w schemacie PKCS #1, Bleichenbacher był w stanie zamontować praktyczny atak przeciwko implementacjom RSA protokołu Secure Socket Layer i odzyskać klucze sesji., W wyniku tych prac kryptografowie zalecają teraz stosowanie sprawdzalnie bezpiecznych schematów padding, takich jak optymalne asymetryczne Szyfrowanie Padding, a RSA Laboratories wydało nowe wersje PKCS #1, które nie są podatne na te ataki.

atak Bocznokanałowyedytuj

został opisany atak bocznokanałowy z wykorzystaniem analizy przewidywania gałęzi (branch prediction analysis-BPA). Wiele procesorów używa predyktora gałęzi do określenia, czy warunkowa gałąź w przepływie instrukcji programu może zostać wzięta, czy nie. Często procesory te również implementują jednoczesną wielowątkowość (SMT)., Ataki analizy przewidywania gałęzi wykorzystują proces szpiegowski, aby odkryć (statystycznie) klucz prywatny, gdy są przetwarzane z tymi procesorami.

Simple Branch Prediction Analysis (SBPA) twierdzi, że poprawia BPA w sposób nie statystyczny. W swojej pracy „On The Power of Simple Branch Prediction Analysis” autorzy SBPA (Onur Aciicmez i Cetin Kaya Koc) twierdzą, że odkryli 508 z 512 bitów klucza RSA w 10 iteracjach.

w 2010 roku opisano atak awarii zasilania na implementacje RSA., Autor odzyskał klucz, zmieniając napięcie zasilania procesora poza limity; spowodowało to wiele awarii zasilania na serwerze.