Kryptografia postkwantowa

Daniel Olczyk

Plan

  • Krótkie przypomnienie o komputerach kwantowych
  • Różnica między kryptografią postkwantową a kwantową
  • Rodzaje algorytmów
  • Podstawowa implementacja w Rust
  • Przykłady użycia w różnych produktach

O mnie

  • SWE 3,5+ lat doświadczenia
  • Student 3. roku w PJATK
  • Przewodniczący w KN Rust Lab PJATK
  • Zacząłem uczyć się Rust 2 lata temu do projektów embedded
  • Obecnie poznaję inne obszary wykorzystania Rust

Krótkie przypomnienie o komputerach kwantowych

Komputery klasyczne przechowują bity (0 lub 1).

ale...

Komputery kwantowe przechowują jednostki zwane kubitami.

Reprezentacja kubitu

Źródło: kwantologia.pl

Dlaczego komputery kwantowe są szybkie?

Liczba bitów/qubitów Liczba stanów klasycznych (jednocześnie) Liczba stanów kwantowych (jednocześnie)
2 1 z 4 4
10 1 z 1024 1024
50 1 z 1.12×10^15 Ponad biliard
300 1 Więcej niż atomów w widzialnym wszechświecie

Czym są algorytmy postkwantowe?

Algorytmy postkwantowe to algorytmy kryptograficzne, które mają być odporne na ataki komputerów kwantowych.

Postkwantowe != kwantowe

Kryptografia postkwantowa działa na klasycznych komputerach i ma być odporna na ataki komputerów kwantowych.

Dlaczego potrzebujemy kryptografii postkwantowej?

Komputery kwantowe mogą złamać wiele obecnie używanych algorytmów kryptograficznych, takich jak RSA i ECC. Istnieje algorytm Shora, który może efektywnie złamać klucz RSA w ciągu nawet kilkunastu sekund!

Algorytm Shora


Kwantowy algorytm umożliwiający rozkład dużej liczby naturalnej na czynniki pierwsze w czasie wielomianowym względem liczby jej bitów, czyli istotnie szybciej niż wszystkie znane algorytmy klasyczne.

Ciekawostka: Złamanie klucza RSA-2048 za pomocą tej metody zajmuje 8h przy użyciu 20 milionów kubitów

Kto zajmuje się standardyzacją algorytmów?

nist

timeline title Historia algorytmów postkwantowych 1994 : Algorytm Shora : Zagrożenie dla RSA/ECC 1996 : Pierwsze schematy : Post-kwantowe propozycje 2006 : NIST rozpoczyna : Prace nad standardami 2016 : NIST konkurencja : Nominacja kandydatów 2022 : NIST wybiera : Finaliści standaryzacji 2024 : Standard FIPS : FIPS 203, 204, 205

Porównanie algorytmów postkwantowych

Rodzina Na czym polega (intuicja) Przykład postkwantowy Przykład tradycyjny
Lattice-based Znalezienie najkrótszego wektora w wielowymiarowej siatce punktów. ML-KEM (Kyber) RSA (wymiana klucza)
Multivariate Rozwiązywanie układów wielu równań kwadratowych. Rainbow ECDSA (podpisy cyfrowe)
Hash-based Budowanie drzew haszujących SPHINCS+ SHA

Obecne algorytmy postkwantowe

  1. ML-KEM (Kyber)
  2. ML-DSA - standard podpisywania kluczy
  3. SLH-DSA - funkcje skrótu (hash-based)
  4. HSS/LMS - podpisy stanowe (przy podpisywaniu np. firmware)

Złamane algorytmy postkwantowe

  1. SIKE (Supersingular Isogeny Key Encapsulation) - atak w 2022 roku (złamany w ciągu 1h na single core)
  2. Rainbow - problem z architekturą algorytmu
  3. SIDH (Supersingular Isogeny Diffie-Hellman) - atak w 2022 roku (złamany w ciągu 1h na single core)
    i wiele innych...

Wielkości danych kluczy

Dla RSA-2048: rozmiar wynosi 256 bajtów

...lecz dla algorytmu Kyber-512 800 bajtów!

Nie wspominając o tym, że dla code-based klucze mogą mieć nawet kilka MB!

Biblioteki do implementacji algorytmów postkwantowych

  • Rust: pgcrypto (wrapper Open Quantum Safe), kyber, ml-kem
  • .NET/Java: Bouncy Castle
  • C/C++: Open Quantum Safe (OQS)
  • Python: pycryptodome

Pora zajrzeć do kodu!

Obecne użycie w produktach

  • Chrome: od wersji 116 (a domyślnie od 124) obsługuje algorytm X25519Kyber768, który służy do bezpiecznej wymiany kluczy w protokole TLS
  • Firefox: tak samo jak Google Chrome, tylko od wersji 132
  • Cloudflare: od 2022 roku oferuje wsparcie dla połączeń TLS z algorytmem Kyber
  • iMessage: Protokół PQ3 wspiera domyślnie algorytmy postkwantowe

Co robić, Jak żyć?

Dziękuję za uwagę!

Z każdym kolejnym qubitem moc obliczeniowa rośnie wykładniczo, a nie liniowo.

Qubity mogą zostać ze sobą połączone tak, że stan jednego zależy od stanu drugiego, bez względu na to, jak daleko od siebie się znajdują.

Algorytm Shora służy do rozkładu dużych liczb na czynniki pierwsze.

Standaryzację, cyberbezpieczeństwo i badania nad kryptografią postkwantową prowadzi amerykański NIST (National Institute of Standards and Technology).

SIDH do wyminay kluczy powstał w 2011