Łamanie szyfrowania RSA-2048 w 8 godzin na komputerze kwantowym

3 czerwca, 2019

Eksperci udowodnili, że świat mógł być w błędzie, kiedy sądził, że klucze RSA o długości 2048 bitów posłużą ludzkości jeszcze kilkadziesiąt lat. Nowe badania pokazują, że przejście z RSA-2048 na RSA-4096 nastąpi szybciej niż się spodziewaliśmy. Coraz tańsze komputery kwantowe zyskują coraz większą moc obliczeniową. W opracowanym modelu komputera kwantowego w zaledwie 8 godzin możliwe jest złamanie szyfru 2048 bitowego. Taki komputer mógłby powstać za kilka dekad.

Do tej pory — bez używania słabości w implementacji algorytmu — naukowcom w procesie faktoryzacji udało się odnaleźć liczby pierwsze dla klucza o długości 768-bitów. Było to w roku 2009. Obecnie standardem jest klucz 2048 bitowy.

Siła algorytmu asymetrycznego RSA tkwi w matematycznym problemie znalezienia dwóch podzielników dużej liczby, które po przemnożeniu dają w wyniku tę bardzo dużą liczbę. Dla komputerów mnożenie jest procesem szybkim, ale dzielenie już nie, dlatego jeszcze w naturalnym procesie obliczeniowym nie udało się rozszyfrować klucza o długości 2048 bitów, który jest najczęściej stosowany np. w złośliwym oprogramowaniu ransomware czy przy generowaniu kluczy SSH.

Szacowano, że klucz o długości 2048-bitów jeszcze przez 10 lat pozostanie odporny na ataki, ale będzie go bardzo łatwo zastąpić dłuższą długością np. 4096 bitów. Obciążenie obliczania faktoryzacji długości klucza 4096 bitów jest zbyt duże nawet dla współczesnych komputerów kwantowych. I dobrze, ponieważ uzyskanie klucza prywatnego na podstawie publicznego musi być obliczeniowo trudne. Jeżeli udostępnimy nasz klucz publiczny to nikt nie powinien na jego podstawie obliczyć naszego klucza prywatnego, ponieważ poznałby unikalną część kryptosystemu i mógłby odszyfrować wszystkie pliki, jeśli uzyskałby do nich dostęp.

Kluczem do bezpieczeństwa RSA-2048 jest czas

Najsłabszym ogniwem algorytmu RSA jest konieczność ochrony klucza prywatnego. Nie ważne jak bardzo matematycznie będzie skomplikowany klucz prywatny, jeżeli hackerowi uda się uzyskać do niego dostęp przy pomocy socjotechnicznych ataków albo przejęcia kontroli nad serwerem.

Algorytm RSA nigdy nie był „nie-do-zhackowania”. Jego bezpieczeństwo opiera się na czasie łamania szyfru — dla bardzo wydajnego, ale zarazem klasycznego komputera. Współczesne szyfry kryptograficzne są tak zaprojektowane, aby ich dekodowanie trwało nieskończenie długo, czyli w praktyce nie będzie to możliwe za życia całej cywilizacji ludzkości. I tutaj wkraczamy w erę kwantową.

Komputery kwantowe są nieporównywalnie potężniejsze niż domowe desktopy czy serwery produkcyjne. Jak bardzo? Normalnemu komputerowi o parametrach AMD Opteron 2,2 Ghz z 2GB pamięci RAM łamanie klucza 1024-bitowego zajęłoby około 1.5 miliona lat. Ale już temu samemu komputerowi złamanie klucza o długości 2048-bitów zajęłoby 4 miliardy razy dłużej. Nie o 4 miliardy lat więcej, ale 4 miliardy razy dłużej!

2^2048 * 1.5miliarda lat = czas w latach potrzebny na złamanie klucza 2048-bitowego.

Wszechświat liczy sobie szacunkowo 13.7 miliardów lat. Czyli zaczynając łamać szyfrowanie na początku wszechświata aż do dzisiaj, trzeba byłoby powtórzyć tę operację jeszcze prawie 500 000 razy. Te liczby robią wrażenie. Są niewyobrażalnie wielkie. Prawdopodobnie łamanie klucza na takim komputerze nie doszłoby do skutku, ponieważ wcześniej wszechświat znowu skurczyłby się do rozmiarów ziarenka piasku, zgodnie z jedną z teorii ciągłego pulsowania wszechświata.   

Czy komputery kwantowe będą niedługo wystarczająco szybkie, aby zagrozić szyfrowaniu RSA-2048? Naukowcy ze Szwecji znaleźli sposób, aby to zrobić, zmniejszając zasoby potrzebne na budowanie komputera kwantowego o rzędy wielkości. Zamiast budować mega-super-szybki komputer kwantowy (i bardzo drogi) można wymyślić nowe metody faktoryzacji, które będą przystosowane do komputerów kwantowych.

Naukowcy w pracy pt. „How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits” udowodnili (w teorii), że są bliżej niż ktokolwiek inny. Ich badanie opisuje problemy z jakimi mogą się zmagać rządy państw, wojsko, banki i cała reszta świata, która „szyfruje”.

W 2015 roku eksperci oszacowali, że komputer kwantowy będzie potrzebował miliarda kubitów, aby złamać szyfrowanie oparte o RSA-2048. To znacznie więcej niż 50-80 kubitów, które w dzisiejszych czasach posiadają supernowoczesne komputery kwantowe. Na tej podstawie oszacowano, że miną całe dekady, zanim wiadomości ze szyfrowaniem RSA-2048 zostaną złamane przez komputer kwantowy. Matematyka znowu pokazała, że jest matką nauk. Szwedzcy naukowcy oszacowali model komputera kwantowego, który może wykonać takie obliczeni w czasie 8 godzin, ale nie za pomocą miliarda kubitów, lecz już „zaledwie” 20 milionów kubitów.

To interesująca praca, bardzo techniczna, trudna do przeanalizowania, ale bardzo ważna. Pokazuje, że w niedalekiej przyszłości mogą powstać kolejne modele komputerów kwantowych, które o całe rzędy wielkości zmniejszą ilość potrzebnych kubitów do obliczania faktoryzacji z milionów do dziesiątek tysięcy. Czy takie urządzenie powstanie w nadchodzących dekadach?

Za kilkadziesiąt lat ryzyko związane z łamaniem RSA-2048 nie będzie znaczące dla zwykłych użytkowników. Już teraz używa się szyfrowania 2048-bitowego w bankowości online, komunikatorach internetowych, szyfrowaniu poczty lub plików. O większą stawkę grają rządy państw. Jeżeli już teraz używają szyfrowania RSA-2048 to za dwadzieścia lat mogą mieć kłopoty z utrzymaniem tajemnic.

Adrian Ścibor

Adrian Ścibor

W ramach działań związanych z cyberbezpieczeństwem odpowiada w AVLab za przeprowadzanie testów rozwiązań ochronnych przed zagrożeniami. Opracowuje strategie oraz narzędzia, które pomagają w ochronie danych i systemów przed cyberatakami. Współuczestnik międzynarodowej grupy non-profit AMTSO, która zrzesza ekspertów IT.
Adrian Ścibor

Adrian Ścibor

W ramach działań związanych z cyberbezpieczeństwem odpowiada w AVLab za przeprowadzanie testów rozwiązań ochronnych przed zagrożeniami. Opracowuje strategie oraz narzędzia, które pomagają w ochronie danych i systemów przed cyberatakami. Współuczestnik międzynarodowej grupy non-profit AMTSO, która zrzesza ekspertów IT.

PODZIEL SIĘ:

Czy ten artykuł był pomocny?

Średnia ocena: 4.8 / 5. Liczba głosów: 5

guest
3 komentarzy
najstarszy
najnowszy oceniany
Inline Feedbacks
View all comments

Wyrażam zgodę na przesłanie oferty drogą telefoniczną przez IT Partners security sp. z o.o. z siedzibą Katowicach ul.Padereskiego 35 na podany przeze mnie adres e-mail zgodnie z ustawą z dnia 10 maja 2018 roku o ochronie danych osobowych (Dz. Ustaw z 2018, poz. 1000) oraz zgodnie z Rozporządzeniem Parlamentu Europejskiego i Rady (UE) 2016/679 z dnia 27 kwietnia 2016 r. w sprawie ochrony osób fizycznych w związku z przetwarzaniem danych osobowych i w sprawie swobodnego przepływu takich danych oraz uchylenia dyrektywy 95/46/WE (RODO).

Wyrażam zgodę na przesłanie oferty drogą mailową przez IT Partners security sp. z o.o. z siedzibą Katowicach ul.Padereskiego 35 na podany przeze mnie adres e-mail zgodnie z ustawą z dnia 10 maja 2018 roku o ochronie danych osobowych (Dz. Ustaw z 2018, poz. 1000) oraz zgodnie z Rozporządzeniem Parlamentu Europejskiego i Rady (UE) 2016/679 z dnia 27 kwietnia 2016 r. w sprawie ochrony osób fizycznych w związku z przetwarzaniem danych osobowych i w sprawie swobodnego przepływu takich danych oraz uchylenia dyrektywy 95/46/WE (RODO).

[ninja_tables id=”27481″]