Nauka

Komputer kwantowy może złamać 2048-bitowe szyfrowanie w 8 godzin

opublikowano przez Wojciech Kulik w dniu 2019-06-22

Dzisiejsze standardy szyfrowania są skuteczne, o ile próby złamania klucza powierza się aktualnym maszynom. W momencie, gdy na dobre nadejdą komputery kwantowe, te zabezpieczenia będą jednak do niczego.

Systemy szyfrujące nigdy nie były niezniszczalne, ale ich mocną stroną jest to, że złamanie klucza zajmuje mnóstwo czasu. Jest tak przynajmniej tak długo, jak mówimy o klasycznych komputerach. Najnowsze badania pokazują bowiem, że komputer kwantowy będzie w stanie poradzić sobie z 2048-bitowym szyfrowaniem RSA w zaledwie 8 godzin. Mówimy zatem o olbrzymim zagrożeniu.

Naukowcy postanowili sprawdzić, kiedy komputery kwantowe staną się wystarczająco potężne, by aktualne standardy szyfrowania okazały się bezużyteczne i czy rzeczywiście można mówić o zagrożeniu. Okazuje się… że rządy, organizacje wojskowe czy banki, które przechowują zabezpieczone dane przez 25 lat mogą mieć niemały problem.

Niebezpieczny algorytm kwantowy

Zacznijmy jednak od początku. W 1994 roku amerykański matematyk Peter Shor odkrył kwantowy algorytm rozkładu liczb naturalnych na czynniki pierwsze, znacząco przewyższający swój klasyczny odpowiednik. 

Trzeba też wiedzieć, że klucz publiczny kryptosystemu RSA to iloczyn dwóch dużych liczb pierwszych, a ich odtworzenie pozwala na poznanie klucza prywatnego i w konsekwencji: złamanie szyfru. 

Na czym polega trudność. Podajmy przykład: znając dwie liczby (np. 723 i 889) łatwo wyliczymy, że iloczyn wynosi 642 747. Znając jednak liczbę 642 747 nie dojdziemy tak łatwo do tego, jakie dwie liczby trzeba pomnożyć, by uzyskać taki wynik. Wspomniany algorytm faktoryzacji Shora to ułatwia, a komputery kwantowe pozwalają to wykorzystać.

Oczywiście im większa liczba, tym trudniej jest „rozwiązać zagadkę”, a w przypadku klasycznych komputerów praktycznie niemożliwe jest uwzględnianie liczb dłuższych niż 2048-bitowe i taka jest też baza najpopularniejszego formatu szyfrowania RSA. Komputery kwantowe rozwijają się jednak bardzo szybko.

Szybki rozwój komputerów kwantowych, ale… 

W 2001 roku informatycy z firmy IBM i Uniwersytetu Stanforda wykorzystali algorytm Shora do rozkładu liczby 15, a dziesięć lat później udało się im zrobić to samo z liczbą 21. W 2012 – było to już 143, a pięć lat temu udało się sfaktoryzować liczbę 56 153. To tempo wzrostu jest imponujące i przerażające zarazem.

Komputer kwantowy
Komputer kwantowy IBM Q System One (IBM).

Jednak choć robi to wrażenie, dużym problemem są zakłócenia. Dlatego naukowcy od dłuższego czasu szacują, że do rozkładu 2048-bitowej liczby potrzebny będzie komputer kwantowy dysponujący miliardem kubitów (czyli bitów kwantowych), Tymczasem najpotężniejsze komputery kwantowe dziś mają ich zaledwie po kilkadziesiąt. 

Teraz naukowcy Craig Gidney z firmy Google i Martin Ekera z KTH Royal Institute of Technology pokazują dowody na to, że wystarczy komputer z 20 milionami kubitów, by z 2048-bitowym RSA poradzić sobie w zaledwie osiem godzin. Jest tak dzięki wykorzystaniu bardziej efektywnej metody wykonywania obliczenia, zwanego potęgowaniem modularnym, a będącego najbardziej skomplikowaną operacją w algorytmie faktoryzacji Shora. Udało się ją jednak zoptymalizować.

Komputer kwantowy mający 20 milionów kubitów to dziś oczywiście wciąż odległe marzenie. Znacznie bliższe jednak niż taki, który dysponuje miliardem bitów kwantowych. Zdecydowanie poważnie należy więc postarać się o odpowiedź na pytanie, czy nie uda się go stworzyć w ciągu najbliższego ćwierćwiecza, czyli: czy zabezpieczane dziś 2048-bitowym szyfrowaniem RSA dane rzeczywiście są całkowicie bezpieczne.

Źródło: TechnologyReview, ExtremeTech, ScienceAlert

marketplace
avatar
Dodaj
  • avatar
    Pójdzie na tym Crysis?
    Zaloguj się
  • avatar
    Jak da się odszyfrować kubitami, to da się stworzyć nim szyfr też odpowiednio potężny. I trzeba będzie komputer mocniejszy od kubitowego aby to nowe złamać. ;)
  • avatar
    Problemem nie jest moc obliczeniowa nawet.
    Komputery kwantowe są na tyle nowy tworem ze duzo bardziej skomplikowane jest wymyslenie tego jak ich uzyc niz sama ich moc obliczeniowa.
    Duzo trudniej po prostu zbudowac dla nich algorytm na którym mają działac bo ich zasada działania jest zupełnie inna niz tego co dotychczas znamy i tego jak sami myslimy i pracujemy codziennie.
  • avatar
    Niech spróbuje bitcoina złamać :P
    Zaloguj się
    -1
  • avatar
    To dawać ten komputer do pracy z Denuvo:) 2minuty i po sprawie:)
  • avatar
    Nie rozumiem tej całej pogoni za coraz trudniejszymi hasłami i mega komputerami łamiącymi je siłowo. Przecież wystarczy ograniczenie po stronie "przyjmującej" hasło, żeby np. dało się wprowadzić tylko jedno hasło na sekundę. W zwykłym użytkowaniu nie przeszkadza to w niczym. I wtedy życia nie wystarczy na złamanie zwykłego hasła sześcioznakowego. Dlaczego nie wprowadza się tego typu zabezpieczeń?
    Zaloguj się
    -2
  • avatar
    Coś się stało, że znowu o tym wspominamy? Czy dalej nie ma żadnych konkretów, ale będziemy napędzać u ludzi strach przed nieznanym?

    Fakt, szyfry których typowy komputer ani nawet superkomputer nie złamałby w miliard lat, będą dzięki komputerom kwantowym możliwe do złamania w kilka godzin. Ale za ich pomocą będziemy mogli używać jeszcze potężniejszych szyfrów, których żaden komputer kwantowy nie będzie w stanie złamać.


    Jedyny moment w trakcie którego trzeba się będzie bać to ten przejściowy, kiedy ludzie będą już dysponować narzędziami do łamania szyfrów, a korporacje jeszcze nie będą korzystać z nowoczesnych zabezpieczeń.

    No i trzeba zrobić wszystko, żeby owe komputery jak najszybciej stały się dostępne dla typowego Kowalskiego. Bo jeżeli tylko światowe potęgi będą mogły łamać szyfry i tylko one będą mogły się przed tym bronić, to typowy użytkownik posiadający np konto w banku będzie miał przejebane.