Nauka dla Społeczeństwa

27.01.2023
PL EN
03.12.2022 aktualizacja 03.12.2022

Kryptolodzy rozpracowują możliwe ataki na szyfry

Źródło: WAT Źródło: WAT

Czy do ataków na szyfry lekkie wykorzystywane w Internecie Rzeczy można wykorzystać wyżarzanie kwantowe? Obecnie nie istnieją jeszcze odpowiednio duże komputery kwantowe, żeby złamać wszystkie aktualnie wykorzystywane klasyczne algorytmy klucza publicznego - tłumaczą kryptolodzy Wojskowej Akademii Technicznej.

Jak informuje na swoich stronach uczelnia, każdy z nas na co dzień korzysta z Internetu Rzeczy. System ten sprawia, że za pomocą specjalnych sensorów, urządzenia samodzielnie łączą się z siecią komputerową i przetwarzają dane. Przesyłane za pomocą tych urządzeń dane muszą być zabezpieczone. W tym celu opracowano algorytmy kryptograficzne zwane szyframi lekkimi.

Na całym świecie coraz intensywniej bada się wykorzystanie komputerów kwantowych do ataków na szyfry. Naukowcy z z Instytutu Matematyki i Kryptologii Wydziału Cybernetyki WAT skupili się nad lekkimi algorytmami blokowymi.

W artykule Elżbieta Burek i dr inż. Michał Wroński przeanalizowali strukturę lekkiego szyfru Speck. Sprawdzili możliwości opisania go za pomocą układu równań wielomianowych wielu zmiennych w taki sposób, aby problem rozwiązywany za pomocą wyżarzania kwantowego był jak najmniejszy.

ZANIM POWSTANIE KOMPUTER KWANTOWY SPECJALNEGO PRZEZNACZENIA

"Powszechnie znanym algorytmem kwantowym, który może zostać wykorzystany do kryptoanalizy szyfrów symetrycznych, jest algorytm Grovera. Atak za pomocą algorytmu Grovera polega na pełnym przeszukiwaniu. Wykorzystuje się przy tym kwantową implementację danego szyfru. Istnienie tego ataku zmniejsza bezpieczeństwo szyfrów symetrycznych" - tłumaczą naukowcy WAT.

Wyjaśniają, że atak ten jest przeznaczony dla komputerów kwantowych ogólnego przeznaczenia. Obecnie komputery takie dysponują zbyt małą liczbą zasobów do przeprowadzenia tego ataku. Dlatego, coraz większe zainteresowanie zyskuje komputer kwantowy specjalnego przeznaczenia, wykorzystujący wyżarzanie kwantowe. Jego zasoby są znacznie większe.

Naukowcy zaproponowali zmianę zakresu rundy, w stosunku do rundy opisanej w oficjalnej dokumentacji. Dzięki takiemu podejściu, uzyskane problemy dla szyfru Speck są nawet o połowę mniejsze, niż problemy dla szyfru AES, o takiej samej długości klucza. Oznacza to, że ataki algebraiczne z wykorzystaniem wyżarzania kwantowego na szyfr Speck powinny być znacznie wydajniejsze niż w przypadku szyfru AES.

Jak podkreślają autorzy, złożoność obliczeniowa rozwiązywania problemów za pomocą wyżarzania kwantowego nie została jeszcze w pełni zbadana. Mimo to istnieją pewne oszacowania, oparte na metodach heurystycznych, według których rozwiązanie problemu wymaga wykorzystania wyżarzania kwantowego. Przyjmując wysoką złożoność, atak algebraiczny z wykorzystaniem wyżarzania kwantowego może być skutecznym atakiem na 31 z 34 rund szyfru Speck128/256. Wynik ten jest lepszy niż najlepszy znany atak klasyczny na ten wariant szyfru Speck.

PRAKTYCZNY POMYSŁ NA LOGARYTM DYSKRETNY

Gdy powstanie odpowiednio duży komputer kwantowy, wówczas złamane zostaną wszystkie aktualnie wykorzystywane klasyczne algorytmy klucza publicznego. Naukowcy wiedzą to od niemal 30 lat, kiedy opublikowano algorytm Shora.

W przypadku algorytmu Shora najlepszym do tej pory wynikiem było rozłożenie na czynniki liczby 21.Jeżeli chodzi o kwantowe wyznaczenie logarytmu dyskretnego w ciele skończonym, to do tej pory na tym polu nie osiągnięto żadnych sukcesów – ani przy to wykorzystaniu algorytmu Shora, ani jakiejkolwiek innej metody.

Pierwszą praktyczną realizację obliczania logarytmu dyskretnego w ciele skończonym z wykorzystaniem metod kwantowych przedstawił w artykule dr inż. Michał Wroński. Jak wyjaśnia naukowiec WAT, problem logarytmu dyskretnego w ciele skończonym polega na znalezieniu takiego najmniejszego całkowitego dodatniego y, dla którego i dla elementów g oraz h z tego ciała zachodzi równość g do potęgi y jest równe h. Aby to lepiej wyjaśnić, badacz posługuje się przykładem.

„Załóżmy, że operujemy w ciele 11-elementowym. Ważne, aby liczba elementów była liczbą pierwszą, a 11 taką liczbą właśnie jest. Operowanie w ciele 11-elementowym oznacza, że działania wykonujemy na resztach z dzielenia przez 11. Teraz chcemy wyznaczyć najmniejsze całkowite dodatnie y, dla którego w naszym ciele 4 do potęgi y jest równe 9” – tłumaczy autor artykułu. Chodzi więc o znalezienie takiego y, dla którego liczba 4 podniesiona do potęgi y przy dzieleniu przez 11 da resztę 9. Rozwiązaniem jest w tym przypadku y równe 8. „Każdy może sprawdzić, że 4 do potęgi 8 równa się 65 536, a liczba ta przy dzieleniu przez 11 daje właśnie resztę równą 9” – dodaje dr Wroński, ale zastrzega, że dla dostatecznie dużych ciał problem staje się bardzo trudny.

Komputery realizujące wyżarzanie kwantowe posiadają obecnie znacznie więcej zasobów aniżeli komputery kwantowe ogólnego przeznaczenia. Dlatego naturalnym pomysłem była próba wykorzystania wyżarzania kwantowego do rozwiązania problemu logarytmu dyskretnego w ciałach skończonych.

„Najpierw trzeba było pokonać pewne trudności. Wiedzieliśmy, w jaki sposób, wykorzystując wyżarzanie kwantowe, rozwiązywać układy równań wielomianowych w ciałach skończonych. W przypadku logarytmu dyskretnego w ciele skończonym cała trudność polegała na przekształceniu funkcji wykładniczej do pewnej funkcji wielomianowej, a następnie do pewnego kwadratowego problemu optymalizacyjnego, który posiada stosunkowo mało zmiennych. Trzeba pamiętać, że poszukiwany y znajduje się właśnie w wykładniku. Wykorzystując wyżarzanie kwantowe, udało się w ten sposób rozwiązać problem logarytmu dyskretnego w 6-bitowym ciele skończonym” – tłumaczy naukowiec.

Jak podkreśla dr Wroński, pomimo że rozmiar rozwiązanego problemu nie wydaje się zbyt duży, osiągnięty wynik jest istotny z teoretycznego punktu widzenia i może prowadzić do bardziej efektywnych metod kwantowego rozwiązywania problemu logarytmu dyskretnego, zanim to będzie możliwe z wykorzystaniem algorytmu Shora.

Pomysły polskich kryptologów zostały przedstawione podczas International Conference on Computational Science. Głównym organizatorem konferencji był Uniwersytet w Amsterdamie. O zaprezentowanych artykułach poinformowano w ramach cyklu Najlepsze publikacje WAT.

PAP – Nauka w Polsce, Karolina Duszczyk

kol/

Przed dodaniem komentarza prosimy o zapoznanie z Regulaminem forum serwisu Nauka w Polsce.

Copyright © Fundacja PAP 2023