1 KRYPTOGRAFIA KWANTOWATomasz Stachlewski
2 AGENDA: Krótkie wprowadzenie: Komputery a kryptografia. Algorytm RSA.Algorytm Shora – kwantowy sposób łamania algorytmu RSA. Algorytm BB84 – bezpieczne przesyłanie danych przy użyciu inżynierii kwantowej. Podsumowanie
3 Kryptografia Kwantowa : WprowadzeniePierwszy komputer:
4 Kryptografia Kwantowa : WprowadzeniePierwszy komputer: Colossus, rok 1942
5 Kryptografia Kwantowa : WprowadzeniePierwszy komputer: Colossus, rok 1942 Służył do łamania kodu Lorenza.
6 Kryptografia Kwantowa : WprowadzeniePierwszy komputer: Colossus, rok 1942 Służył do łamania kodu Lorenza. Złamał ponad 63 miliony zakodowanych znaków
7 Kryptografia Kwantowa : WprowadzeniePierwszy komputer: Colossus, rok 1942 Służył do łamania kodu Lorenza. Złamał ponad 63 miliony zakodowanych znaków Większa moc obliczeniowa niż stworzonego później amerykańskiego ENIAC’u
8 Kryptografia Kwantowa : WprowadzenieAlgorytm RSA
9 Kryptografia Kwantowa : WprowadzenieAlgorytm RSA Wykorzystujący trudność w faktoryzacji (rozkładzie na czynniki pierwsze) dużych liczb.
10 Kryptografia Kwantowa : WprowadzenieAlgorytm RSA Wykorzystujący trudność w faktoryzacji (rozkładzie na czynniki pierwsze) dużych liczb. Wykorzystywany m.in. w podpisach cyfrowych
11 Kryptografia Kwantowa : WprowadzenieAlgorytm RSA Wykorzystujący trudność w faktoryzacji (rozkładzie na czynniki pierwsze) dużych liczb. Wykorzystywany m.in. w podpisach cyfrowych Maj 2007: Politechnice z Lozanny, Uniwersytetowi w Bonn oraz japońskiej firmie NTT udaje się rozłożyć na czynniki pierwsze liczbę 2^ Zajeło to 11 miesięcy.
12 Kryptografia Kwantowa : Wprowadzenie Nagroda za sfaktoryzowanie tej liczby to 20 tysięcy dolarów. Składa się ona z 193 cyfr.
13 Kryptografia Kwantowa : Algorytm Shora
14 Kryptografia Kwantowa : Algorytm ShoraUmożliwia szybką faktoryzację liczb.
15 Kryptografia Kwantowa : Algorytm ShoraUmożliwia szybką faktoryzację liczb. Mogący posłużyć do łamania algorytmu RSA
16 Kryptografia Kwantowa : Algorytm ShoraUmożliwia szybką faktoryzację liczb. Mogący posłużyć do łamania algorytmu RSA Wymaga komputera kwantowego
17 Kryptografia Kwantowa : Algorytm ShoraUmożliwia szybką faktoryzację liczb. Mogący posłużyć do łamania algorytmu RSA Wymaga komputera kwantowego Obecnie największa sfaktoryzowana liczba przy użyciu tego algorytmu na komputerze kwantowym to 15.
18 Kryptografia Kwantowa : Algorytm ShoraNiech dana będzie pewna liczba N. Na podstawie algorytmów klasycznych sprawdźmy czy jest ona parzysta lub czy jest kwadratem liczby pierwszej. Jeśli nie, to możemy kontynuować.
19 Kryptografia Kwantowa : Algorytm ShoraNiech dana będzie pewna liczba N. Na podstawie algorytmów klasycznych sprawdźmy czy jest ona parzysta lub czy jest kwadratem liczby pierwszej. Jeśli nie, to możemy kontynuować. Niech N=21.
20 Kryptografia Kwantowa : Algorytm ShoraNiech dana będzie pewna liczba N. Na podstawie algorytmów klasycznych sprawdźmy czy jest ona parzysta lub czy jest kwadratem liczby pierwszej. Jeśli nie, to możemy kontynuować. Niech N=21. Przygotujmy rejestr A, składający się z liczb od 0 do N
21 Kryptografia Kwantowa : Algorytm ShoraNiech dana będzie pewna liczba N. Na podstawie algorytmów klasycznych sprawdźmy czy jest ona parzysta lub czy jest kwadratem liczby pierwszej. Jeśli nie, to możemy kontynuować. Niech N=21. Przygotujmy rejestr A, składający się z liczb od 0 do N A: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
22 Kryptografia Kwantowa : Algorytm ShoraWybieramy w sposób losowy pewną liczbę a następnie na podstawie algorytmu klasycznego (np. Euklidesa) znajdujemy Jeśli to przechodzimy do następnego punktu, jeśli nie to powtarzamy punkt jeszcze raz.
23 Kryptografia Kwantowa : Algorytm ShoraWybieramy w sposób losowy pewną liczbę a następnie na podstawie algorytmu klasycznego (np. Euklidesa) znajdujemy Jeśli to przechodzimy do następnego punktu, jeśli nie to powtarzamy punkt jeszcze raz. Niech x=2
24 Kryptografia Kwantowa : Algorytm ShoraWybieramy w sposób losowy pewną liczbę a następnie na podstawie algorytmu klasycznego (np. Euklidesa) znajdujemy Jeśli to przechodzimy do następnego punktu, jeśli nie to powtarzamy punkt jeszcze raz. Niech x=2 Przygotowujemy rejestr B na podstawie
25 Kryptografia Kwantowa : Algorytm ShoraWybieramy w sposób losowy pewną liczbę a następnie na podstawie algorytmu klasycznego (np. Euklidesa) znajdujemy Jeśli to przechodzimy do następnego punktu, jeśli nie to powtarzamy punkt jeszcze raz. Niech x=2 Przygotowujemy rejestr B na podstawie A: B: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 2 4 8 16 11
26 Kryptografia Kwantowa : Algorytm ShoraObliczamy okres wartości w rejestrze B (tu wynosi on ). Jeśli jest liczbą nieparzystą to poszukujemy kolejnego i powtarzamy czynności. W przeciwnym wypadku obliczamy wartości wyrażeń:
27 Kryptografia Kwantowa : Algorytm ShoraObliczamy okres wartości w rejestrze B (tu wynosi on ). Jeśli jest liczbą nieparzystą to poszukujemy kolejnego i powtarzamy czynności. W przeciwnym wypadku obliczamy wartości wyrażeń: W naszym przypadku
28 Kryptografia Kwantowa : Algorytm ShoraObliczamy okres wartości w rejestrze B (tu wynosi on ). Jeśli jest liczbą nieparzystą to poszukujemy kolejnego i powtarzamy czynności. W przeciwnym wypadku obliczamy wartości wyrażeń: W naszym przypadku Sprawdzamy, czy liczb N dzieli się przez którąś z liczb P i Q, jeśli nie, to powtarzamy wszystkie czynności. Jeśli tak, to znaleźliśmy dzielnik liczby N.
29 Kryptografia Kwantowa : Algorytm ShoraObliczamy okres wartości w rejestrze B (tu wynosi on ). Jeśli jest liczbą nieparzystą to poszukujemy kolejnego i powtarzamy czynności. W przeciwnym wypadku obliczamy wartości wyrażeń: W naszym przypadku Sprawdzamy, czy liczb N dzieli się przez którąś z liczb P i Q, jeśli nie, to powtarzamy wszystkie czynności. Jeśli tak, to znaleźliśmy dzielnik liczby N.
30 Kryptografia Kwantowa : Algorytm Bennetta - Brassarda
31 Kryptografia Kwantowa : Algorytm Bennetta - BrassardaZapewnia w pełni bezpieczne ustalanie klucza prywatnego, służącego do szyfrowania przesyłanych danych.
32 Kryptografia Kwantowa : Algorytm Bennetta - BrassardaZapewnia w pełni bezpieczne ustalanie klucza prywatnego, służącego do szyfrowania przesyłanych danych. Niemożność niezauważalnego przechwycenia klucza prywatnego
33 Kryptografia Kwantowa : Algorytm Bennetta - BrassardaZapewnia w pełni bezpieczne ustalanie klucza prywatnego, służącego do szyfrowania przesyłanych danych. Niemożność niezauważalnego przechwycenia klucza prywatnego W zależności od kierunku padania fotonów na polaryzator i od jego ustawienia, mamy do czynienia z innym kierunkiem odbicia fotonów na wyjściu.
34 Kryptografia Kwantowa : PodsumowanieAlgorytm Bennetta-Brassarda Rekord przesłania zaszyfrowanej wiadomości 67km, Genewa - Lozanna
35 Kryptografia Kwantowa : PodsumowanieAlgorytm Bennetta-Brassarda Rekord przesłania zaszyfrowanej wiadomości 67km, Genewa – Lozanna Sieć kryptograficzna łącząca Pentagon z Białym Domem.
36 Kryptografia Kwantowa : PodsumowanieUrządzenie firmy id Quantique umożliwiające budowę własnej domowej sieci kryptograficznej.
37 Dziękuje za uwagę