Rewelacyjne artykuły, takie jak to o komputerach kwantowych nawet w 2016 r., stwarzają niepewność dla bezpieczeństwa danych w przypadku skonstruowania komputerów kwantowych o wystarczającej mocy. W tym artykule postaram się rzucić nieco światła na sytuację.
Co to są obliczenia kwantowe?
Obliczenia kwantowe to zastosowanie zasad mechaniki kwantowej do wykonywania obliczeń. W szczególności informatyka kwantowa wykorzystuje stany kwantowe cząstek subatomowych, takie jak superpozycja i splątanie, do tworzenia komputerów kwantowych. Po zastosowaniu do komputerów kwantowych o wystarczającej mocy określone algorytmy mogą wykonywać obliczenia znacznie szybciej niż klasyczne komputery, a nawet rozwiązywać problemy poza zasięgiem obecnej technologii obliczeniowej. W rezultacie wzrasta zainteresowanie ze strony rządy i przemysłu na całym świecie w celu opracowania komputerów kwantowych. Dziedzina ta jest wciąż w powijakach, ale rozwój nabiera rozpędu i już działają komputery kwantowe, choć w tym momencie bardzo słabe.
SSL.com zapewnia szeroką gamę domen SSL /TLS certyfikaty serwera dla witryn HTTPS.
Obliczenia klasyczne i kwantowe
Jak obliczenia kwantowe mogą wpływać na kryptografię?
„W 1994 roku Peter Shor z Bell Laboratories wykazał, że komputery kwantowe, nowa technologia wykorzystująca fizyczne właściwości materii i energii do wykonywania obliczeń, mogą skutecznie rozwiązać każdy z tych problemów, tym samym czyniąc wszystkie kryptosystemy klucza publicznego oparte na takich założeniach bezsilnymi. W ten sposób wystarczająco potężny komputer kwantowy narazi na niebezpieczeństwo wiele form nowoczesnej komunikacji – od wymiany kluczy, przez szyfrowanie, po uwierzytelnianie cyfrowe”.
Czy wkrótce pojawią się obliczenia kwantowe?
Co możemy zrobić?
Kiedy pojawi się powszechna technologia obliczeń kwantowych, będziemy musieli przygotować się na odporne na kwanty PKI. Istnieje wiele projektów w trakcie realizacji tego celu i wiele proponowanych technologii, które mogą zapewnić rozwiązanie. Poniżej postaramy się podsumować najbardziej obiecujące technologie i przedstawić krótki przegląd realizowanych wspólnych projektów mających na celu ustanowienie kryptografii post-kwantowej, wraz z wyzwaniami, które nas czekają.
Rodziny algorytmów post-kwantowych
Badania z ostatnich 15-20 lat dowiodły istnienia algorytmów odpornych na ataki kwantowe. Poniżej przedstawiamy krótki opis najbardziej obiecujących rodzin algorytmów, które mogą zapewnić rozwiązanie zapewniające bezpieczeństwo w post-kwantowym świecie.
Kryptografia oparta na kodzie
Kryptografia oparta na kodzie wykorzystuje kody korekcji błędów do tworzenia kryptografii z kluczem publicznym. Został po raz pierwszy zaproponowany przez Roberta McEliece w 1978 roku i jest jednym z najstarszych i najlepiej zbadanych algorytmów szyfrowania asymetrycznego. Schemat podpisu można skonstruować na podstawie schematu Niederreitera, podwójnego wariantu schematu McEliece. Kryptosystem McEliece jak dotąd opierał się kryptoanalizie. Głównym problemem oryginalnego systemu jest duży rozmiar klucza prywatnego i publicznego.
Kryptografia oparta na hashu
Kryptografia oparta na hashu reprezentuje obiecujące podejście do kryptografii post-kwantowej dla podpisów cyfrowych. Funkcje haszujące to funkcje, które odwzorowują ciągi o dowolnej długości na ciągi o stałej długości. Są jednym ze starszych schematów kryptografii klucza publicznego, a ich oceny bezpieczeństwa przeciwko atakom klasycznym i kwantowym są dobrze poznane. Funkcje skrótu są już jednym z najczęściej używanych narzędzi kryptograficznych. Wiadomo było, że przez długi czas mogą służyć jako jedyne narzędzie do budowania kryptografii klucza publicznego. Ponadto kryptografia oparta na hashowaniu jest elastyczna i może spełniać różne oczekiwania dotyczące wydajności. Z drugiej strony, schematy podpisów oparte na hashowaniu są głównie stanowe, co oznacza, że klucz prywatny musi być aktualizowany po każdym użyciu; w przeciwnym razie bezpieczeństwo nie jest gwarantowane. Istnieją schematy oparte na skrótach, które są bezstanowe, ale kosztem dłuższych podpisów, dłuższych czasów przetwarzania i konieczności śledzenia przez sygnatariusza pewnych informacji, na przykład tego, ile razy klucz został użyty do utworzenia podpisu.
Kryptografia sieciowa
Kryptografia oparta na sieciach jest szczególnym przypadkiem kryptografii opartej na podzbiorze sum i została po raz pierwszy wprowadzona w 1996 roku przez Ajtai. Jest to ogólne określenie dla prymitywów kryptograficznych skonstruowanych przy użyciu krat. Niektóre z tych konstrukcji wydają się być odporne zarówno na ataki komputerów kwantowych, jak i klasycznych. Dodatkowo mają inne atrakcyjne cechy, takie jak najgorsza twardość. Ponadto prezentują prostotę i równoległość oraz są wystarczająco wszechstronne, aby tworzyć solidne schematy kryptograficzne. Wreszcie, są to jedyna rodzina algorytmów zawierająca wszystkie trzy rodzaje prymitywów wymaganych do zbudowania postkwantowej infrastruktury klucza publicznego: szyfrowanie kluczem publicznym, wymiana kluczy i podpis cyfrowy.
Kryptografia wielowymiarowa
Kryptografia wielowymiarowa odnosi się do kryptografii z kluczem publicznym, której klucze publiczne reprezentują wielomianową i nieliniową (zwykle kwadratową) mapę wielomianową. Udowodniono, że rozwiązanie tych systemów jest NP-kompletne, co czyni tę rodzinę algorytmów dobrymi kandydatami do kryptografii post-kwantowej. Obecnie wielowymiarowe schematy szyfrowania okazały się mniej wydajne niż inne schematy, ponieważ wymagają znacznych kluczy publicznych i długich czasów odszyfrowywania. Z drugiej strony okazały się bardziej odpowiednie do budowania schematów sygnatur, ponieważ zapewniają najkrótsze rozmiary sygnatur wśród algorytmów post-kwantowych, chociaż wiążą się z dość dużymi kluczami publicznymi.
Kryptografia oparta na izogenii
Kryptografia oparta na izogenii wykorzystuje mapy między krzywymi eliptycznymi do tworzenia kryptografii z kluczem publicznym. Algorytm, który jest kandydatem do kryptografii post-kwantowej, to supersingularna izogeniczna wymiana kluczy Diffiego-Hellmana (SIDH) wprowadzona w 2011 r., co czyni ten schemat najnowszym spośród kandydatów. SIDH wymaga jednego z najmniejszych kluczy spośród proponowanych schematów wymiany kluczy i obsługuje doskonałe utajnienie przekazywania. Jednak jego stosunkowo młody wiek sprawia, że nie ma wielu schematów opartych na tej koncepcji i nie było zbyt wiele do sprawdzenia ich możliwych podatności.
Projekty dla kryptografii post-kwantowej
Istnieją różne grupy robocze zajmujące się schematami kryptografii post-kwantowej, takie jak Projekt Open Quantum Safe (OQS) i ENISA. Jednak najbardziej spójną inicjatywą jest Projekt standaryzacji post-kwantowej kryptografii NIST trwający od 2017 roku. Jak sama nazwa wskazuje, projekt ma na celu wybór odpowiedniego schematu kryptograficznego, który będzie standardem branżowym w erze post-kwantowej. Proces rozpoczął się od 69 algorytmów kandydatów, z których 26 przeszło do drugiej rundy oceny. W lipcu 2020 r. ogłoszono kandydatów do trzeciej rundy, jak pokazano w poniższej tabeli. W sumie jest siedmiu finalistów i ośmiu alternatywnych kandydatów. W tabeli zaznaczono, czy są one brane pod uwagę pod kątem schematów szyfrowania lub podpisów, rodziny algorytmów i trudnego problemu, na którym są oparte.
Schemat | Enc/Sig | Rodzina | Trudny problem |
Finaliści rundy 3 | |||
Klasyczny McEliece | Inc | Oparte na kodzie | Dekodowanie losowych kodów binarnych Goppa |
Kryształy-Kyber | Inc | Oparte na siatce | Moduł cyklotomiczny-LWE |
NTRU | Inc | Oparte na siatce | Cyklotomiczny problem NTRU |
szabla | Inc | Oparte na siatce | Moduł cyklotomiczny-LWR |
Kryształy-Dilithium | Sig | Oparte na siatce | Moduł cyklotomiczny-LWE i Moduł-SIS |
sokół | Sig | Oparte na siatce | Pierścień cyklotomiczny-SIS |
Tęcza | Sig | Oparte na wielu odmianach | Pułapka na olej i ocet |
Alternatywni kandydaci rundy 3 | |||
ROWER | Inc | Oparte na kodzie | Dekodowanie kodów quasi-cyklicznych |
HQC | Inc | Oparte na kodzie | Wariant kodowania Ring-LWE |
Frodo-KEM | Inc | Oparte na siatce | LWE |
NTRU-Prime | Inc | Oparte na siatce | Niecyklotomiczny problem NTRU lub Ring-LWE |
TAK | Inc | Oparte na izogenii | Problem izogenii z dodatkowymi punktami |
GeMSS | Sig | Oparte na wielu odmianach | Zapadnia „Wielkiego Pola” |
piknik | Sig | Symetryczny krypto | Rezystancja przedobrazowa szyfru blokowego |
SPHINCS + | Sig | Oparte na hashu | Rezystancja przedobrazu funkcji haszującej |
Ocena algorytmu została oparta na trzech kryteriach przedstawionych poniżej.
- Bezpieczeństwo: to najważniejsze kryterium. NIST ustalił kilka czynników, które należy wziąć pod uwagę przy ocenie bezpieczeństwa zapewnianego przez każdy kandydujący algorytm. Oprócz kwantowej odporności algorytmów, NIST zdefiniował również dodatkowe parametry bezpieczeństwa, które nie są częścią obecnego ekosystemu cyberbezpieczeństwa. Są to doskonałe utajnienie do przodu, odporność na ataki boczne i odporność na ataki wieloklawiszowe.
- Koszt i wydajność: Algorytmy są oceniane na podstawie ich metryk wydajności, takich jak rozmiary kluczy, wydajność obliczeniowa operacji i generowania kluczy publicznych i prywatnych oraz błędy deszyfrowania.
- Charakterystyka algorytmu i implementacji: Zakładając, że algorytmy zapewniają dobre ogólne bezpieczeństwo i wydajność, są one oceniane na podstawie ich elastyczności, prostoty i łatwości przyjęcia (np. istnienie lub brak własności intelektualnej obejmującej algorytm).
Sprawność kryptograficzna
Podsumowanie