Kryptografia asymetryczna

W tej lekcji przyjrzymy się kryptografii asymetrycznej, która stanowi podstawę wielu bezpiecznych interakcji sieciowych w dzisiejszych czasach.

Do końca lekcji omówimy:

• Czym jest kryptografia asymetryczna
• Zastosowania kryptografii asymetrycznej, w tym wymianę kluczy i podpisy cyfrowe
• Bezpieczeństwo kryptografii asymetrycznej w ogólności
• Dalsze szczegóły dotyczące algorytmów RSA, DSA i krzywych eliptycznych oraz ich bezpieczeństwa
• Kilka przykładów kodu w Pythonie pokazujących, jak algorytmy działają w praktyce
• Zagrożenia dla tych algorytmów ze strony zarówno komputerów klasycznych, jak i kwantowych

Wprowadzenie do kryptografii asymetrycznej

Jak dowiedzieliśmy się w poprzedniej lekcji, kryptografia symetryczna jest bardzo szybka i efektywna w ochronie informacji, ale ma kilka ograniczeń:

1. W miarę wzrostu liczby stron pragnących wymieniać się bezpiecznymi informacjami, liczba wymaganych kluczy rośnie kombinatorycznie. Nie zapewnia ona mechanizmu bezpiecznej dystrybucji tych kluczy między nadawcami a odbiorcami.
2. Brak jest zapewnienia niezaprzeczalności. Każda strona może deszyfrować lub szyfrować wiadomości, bez możliwości zagwarantowania, że wiadomość została odebrana lub skąd pochodzi.

Rozwiązanie obu tych problemów zapewnia kryptografia asymetryczna (AKC), znana również jako kryptografia klucza publicznego (PKC), która stanowi w związku z tym fundament współczesnego bezpieczeństwa cyfrowego.

Kryptografia asymetryczna (AKC) polega na wykorzystaniu pary kluczy – jednego publicznego, jednego prywatnego. Klucze publiczny i prywatny są powiązane kryptograficznie i zazwyczaj generowane w tym samym czasie jako para kluczy przy użyciu specjalistycznego algorytmu matematycznego. Klucz publiczny, jak sugeruje jego nazwa, jest przeznaczony do swobodnej dystrybucji, natomiast klucz prywatny jest trzymany w tajemnicy przez stronę generującą parę kluczy. Bezpieczeństwo komunikacji wykorzystującej pary kluczy asymetrycznych jest zapewnione tak długo, jak długo klucz prywatny pozostaje poufny.

Rysunek 1. Szyfrowanie kluczem asymetrycznym

AKC oferuje kilka użytecznych funkcji, takich jak:

1. Szyfrowanie i deszyfrowanie w celu zapewnienia poufności komunikacji.
2. Podpisy cyfrowe w celu zapewnienia autentyczności, integralności oraz niezaprzeczalności.
3. Bezpieczna wymiana kluczy w celu umożliwienia późniejszego wykorzystania kryptosystemów symetrycznych.

We współczesnych zastosowaniach AKC jest używana przede wszystkim do podpisów cyfrowych oraz bezpiecznej wymiany kluczy. W tej lekcji przedstawimy te dwie kluczowe funkcje, a następnie omówimy kilka wariantów protokołów kryptograficznych dla tych funkcji.

Wymiana kluczy z kryptografią asymetryczną

Jednym z fundamentalnych problemów w kryptografii jest bezpieczna wymiana kluczy. Na przykład, jeśli dwie strony chcą używać szyfrowania symetrycznego, obie potrzebują tego samego klucza do szyfrowania i deszyfrowania wiadomości. Ale jak bezpiecznie wymienić ten klucz? Kryptografia asymetryczna rozwiązuje ten problem poprzez interaktywne i nieinteraktywne mechanizmy wymiany kluczy.

Interaktywna wymiana kluczy

Interaktywny protokół wymiany kluczy odnosi się do metody, w której dwie strony współpracują, aby utworzyć wspólny sekretny klucz za pośrednictwem niebezpiecznego kanału komunikacyjnego. Ten wspólny sekretny klucz może być następnie używany do zadań symetrycznego szyfrowania i deszyfrowania.

Najbardziej znanym wśród takich protokołów jest algorytm Diffiego-Hellmana (DH), który został opracowany specjalnie w celu ułatwienia wymiany kluczy. W tym protokole każda strona generuje parę kluczy (publiczny i prywatny) oraz rozsyła swój klucz publiczny. Następnie każda strona używa swojego klucza prywatnego oraz klucza publicznego drugiej strony, aby wygenerować wspólny sekretny klucz. DH wykorzystuje zasady arytmetyki modularnej, aby zapewnić, że obie strony otrzymują ten sam wspólny sekret, mimo że każda ze stron ma dostęp tylko do klucza publicznego drugiej strony.

Współczesne kryptosystemy oparte na kryptografii krzywych eliptycznych (ECC) rozszerzają tę koncepcję o wymianę kluczy Diffiego-Hellmana na krzywych eliptycznych (ECDH). ECDH działa podobnie do DH, ale wykorzystuje właściwości krzywych eliptycznych, co skutkuje bardziej bezpiecznym i wydajnym systemem.

Rysunek 2. Protokół wymiany kluczy

Nieinteraktywna wymiana kluczy

W przeciwieństwie do protokołów wymiany kluczy takich jak DH i ECDH, które są interaktywne i wymagają wymiany komunikatów w celu ustalenia klucza symetrycznego, AKC zapewnia również nieinteraktywne sposoby ustanawiania wspólnego sekretnego klucza. W takich schematach jedna strona generuje parę kluczy (publiczny i prywatny) i udostępnia klucz publiczny drugiej stronie. Ta druga strona generuje następnie losowy klucz symetryczny, szyfruje go za pomocą otrzymanego klucza publicznego i odsyła z powrotem do pierwszej strony. Pierwsza strona używa swojego klucza prywatnego do odszyfrowania otrzymanej wiadomości, uzyskując tym samym wspólny klucz symetryczny. Schemat ten jest nieinteraktywny w tym sensie, że klucz symetryczny jest ustalany przez jedną stronę i po prostu bezpiecznie przekazywany drugiej stronie w zaszyfrowanej formie.

Istotnym zagadnieniem w nieinteraktywnej wymianie kluczy jest różnica długości w bitach pomiędzy kluczem symetrycznym, który strony chcą wymienić, a zalecanymi rozmiarami wiadomości w AKC. Zazwyczaj współczesne klucze symetryczne mają długość 128-256 bitów, podczas gdy asymetryczne kryptosystemy takie jak RSA pracują z wiadomościami o długości około 1024-4096 bitów. Dlatego przy użyciu AKC do transmisji klucza symetrycznego, dla bezpieczeństwa musi on mimo to zostać zakodowany w dłuższą wiadomość 1024-4096 bitów. Można to osiągnąć za pomocą dwóch podejść:

• Wymiana kluczy oparta na dopełnianiu (padding): W tym podejściu krótszy klucz symetryczny (128-256 bitów) jest generowany jako pierwszy, a następnie stosowany jest uzgodniony odwracalny schemat dopełniania, taki jak OAEP, aby osadzić go w dłuższej wiadomości (1024-4096 bitów). Ta dłuższa wiadomość jest szyfrowana za pomocą AKC i rozsyłana jako szyfrogram. Odbiorca najpierw odszyfrowuje szyfrogram, a następnie usuwa dopełnienie, aby wyodrębnić krótszy klucz symetryczny.

• Mechanizmy enkapsulacji kluczy (KEM): W wymianie kluczy opartej na KEM najpierw generowana jest losowa, długa (1024-4096 bitów) wiadomość w postaci jawnej, z której można wyodrębnić krótszy (128-256 bitów) klucz symetryczny, używając uzgodnionej funkcji derywacji klucza (KDF). Dłuższy tekst jawny jest szyfrowany za pomocą AKC i rozsyłany do odbiorcy jako szyfrogram. Odbiorca dekoduje szyfrogram przy użyciu swojego klucza prywatnego, a następnie używa KDF do wyodrębnienia krótszego (128-256 bitów) klucza symetrycznego. Popularne kryptosystemy takie jak RSA, dzięki swojej zdolności do bezpośredniego szyfrowania danych, mogą być wykorzystywane do implementacji KEM.

Rysunek 3. Mechanizm enkapsulacji kluczy

Podpisy cyfrowe z kryptografią asymetryczną

Podpisy cyfrowe to kolejne potężne zastosowanie kryptografii asymetrycznej. Zapewniają uwierzytelnianie, integralność i niezaprzeczalność, co wynika z faktu, że w ramach AKC podmioty posiadają unikalne klucze prywatne. Podstawowa idea leżąca u podstaw protokołów podpisów polega na tym, że nadawcy bezpiecznych wiadomości dodatkowo podpisują cyfrowo wiadomości przy użyciu swojego unikalnego klucza prywatnego. Odbiorca następnie weryfikuje podpis cyfrowy przy użyciu klucza publicznego nadawcy. W ramach AKC podpisy cyfrowe mogą być implementowane przy użyciu algorytmów zaprojektowanych specjalnie w tym celu lub poprzez wykorzystanie ogólnych kryptosystemów.

Rysunek 4. Podpisy cyfrowe z kryptografią asymetryczną

Dedykowane algorytmy podpisów cyfrowych

Obecnie amerykańskim standardem Federal Information Processing Standard (FIPS) dla podpisów cyfrowych jest dedykowany schemat po prostu zatytułowany Digital Signature Algorithm (DSA). Nieco podobnie do protokołu Diffiego-Hellmana, DSA wykorzystuje algebraiczne właściwości potęgowania modularnego oraz odwrotności multiplikatywnych do generowania i weryfikacji podpisu.

Algorytm podpisu cyfrowego na krzywych eliptycznych (ECDSA) jest wariantem DSA opartym na ECC, zapewniającym tę samą funkcjonalność, ale przy znacznie krótszych kluczach. Skutkuje to poprawą wydajności, co czyni go popularnym wyborem dla systemów z ograniczeniami zasobów.

Zarówno DSA, jak i ECDSA zostaną zilustrowane bardziej szczegółowo w dalszej części.

Schematy podpisów cyfrowych wykorzystujące ogólne kryptosystemy

Oprócz dedykowanych algorytmów, podpisy cyfrowe można również generować przy użyciu ogólnych kryptosystemów asymetrycznych, takich jak RSA.

RSA, który zostanie szczegółowo omówiony w dalszej części, również wykorzystuje modularne odwrotności multiplikatywne oraz potęgowanie modularne jako podstawowe operacje, ale łączy je w innej kolejności niż DSA. W RSA podpisujący zazwyczaj tworzy skrót wiadomości, a następnie szyfruje ten skrót swoim kluczem prywatnym, tworząc podpis cyfrowy. Każda strona może następnie zweryfikować ten podpis, odszyfrowując go kluczem publicznym podpisującego i porównując go ze skrótem wiadomości.

Zastosowania kryptografii klucza asymetrycznego

Kryptografia klucza asymetrycznego jest wszechobecna w nowoczesnych zastosowaniach technologii cyfrowej. Podstawowe funkcjonalności AKC opisane powyżej stanowią elementy składowe wielu protokołów aplikacyjnych wyższego poziomu, w tym:

1. Komunikacja internetowa: Bezpieczna komunikacja przez internet, taka jak HTTPS, w dużej mierze opiera się na kryptografii klucza asymetrycznego. Transport Layer Security (TLS) oraz jego poprzednik, Secure Sockets Layer (SSL), wykorzystują kryptografię klucza asymetrycznego w początkowym procesie uzgadniania (handshake) w celu ustanowienia klucza symetrycznego, który jest następnie używany przez resztę sesji komunikacyjnej.

2. Uwierzytelnianie: Kryptografia klucza asymetrycznego jest używana do tworzenia podpisów cyfrowych, umożliwiając podmiotowi uwierzytelnienie dokumentu cyfrowego lub wiadomości jako pochodzących od konkretnego nadawcy. Jest to wykorzystywane w wielu scenariuszach, od weryfikacji aktualizacji oprogramowania po prawnie wiążące umowy cyfrowe.

3. Szyfrowanie poczty e-mail: Protokoły szyfrowania poczty e-mail, takie jak PGP (Pretty Good Privacy) oraz jego alternatywa open-source GPG (GNU Privacy Guard), wykorzystują kryptografię klucza asymetrycznego, aby zapewnić, że tylko zamierzony odbiorca może odczytać treść wiadomości.

4. Secure shell (SSH): SSH to protokół do bezpiecznego zdalnego logowania i innych bezpiecznych usług sieciowych w niezabezpieczonej sieci. Wykorzystuje on kryptografię klucza asymetrycznego do uwierzytelniania serwera wobec klienta oraz, opcjonalnie, klienta wobec serwera.

5. VPN (wirtualna sieć prywatna): Szyfrowanie kluczem asymetrycznym jest używane do ustanawiania bezpiecznych połączeń w VPN, zapewniając bezpieczną komunikację w sieciach publicznych.

6. Blockchain i kryptowaluty: Technologie blockchain, w tym Bitcoin i Ethereum, wykorzystują kryptografię klucza asymetrycznego. Na przykład własność Bitcoina jest ustalana za pomocą podpisów cyfrowych opartych na kryptografii klucza asymetrycznego.

7. Urzędy certyfikacji: Kryptografia klucza asymetrycznego jest używana przez urzędy certyfikacji (CA) do wydawania i podpisywania certyfikatów cyfrowych, które są używane w komunikacji TLS, podpisywaniu kodu, szyfrowaniu poczty e-mail i nie tylko. Certyfikat cyfrowy wiąże klucz publiczny z konkretnym podmiotem (na przykład osobą lub serwerem).

Rysunek 5. Wydawanie i podpisywanie certyfikatów cyfrowych z wykorzystaniem kryptografii klucza asymetrycznego

Bezpieczeństwo kryptografii klucza asymetrycznego

Kilka pojęć kryptograficznych współgra ze sobą, aby umożliwić bezpieczną kryptografię klucza asymetrycznego, w tym:

Tajność klucza prywatnego: Najbardziej podstawowym wymaganiem bezpieczeństwa AKC jest zachowanie tajności klucza prywatnego. Jednak ponieważ klucz prywatny musi być matematycznie powiązany z kluczem publicznym, tajność klucza prywatnego wymaga również, aby wyprowadzenie klucza prywatnego ze znajomości klucza publicznego było obliczeniowo niewykonalne. Schematy generowania kluczy w AKC opierają się na obliczeniowo trudnych problemach matematycznych, aby spełnić ten wymóg.

Funkcjonalność zapadki (trapdoor) W AKC operacje szyfrowania i deszyfrowania obejmują różne, uzupełniające się klucze z pojedynczej pary kluczy. Szyfrogram wygenerowany przez szyfrowanie z użyciem jednego z kluczy (na przykład klucza publicznego) musi być niezrozumiały dla osób trzecich, a jednocześnie łatwy do odszyfrowania przez posiadacza klucza uzupełniającego (w tym przypadku klucza prywatnego). Innymi słowy, szyfrowanie powinno przypominać jednokierunkową funkcję z zapadką, tak aby osoby trzecie nie mogły odwrócić operacji i odzyskać tekstu jawnego, ale klucz prywatny zapewnia tajną zapadkę, która umożliwia łatwe odwrócenie. Popularne algorytmy AKC wykorzystują potęgowanie modularne do ustanowienia zachowania jednokierunkowej funkcji z zapadką.

Losowość: Proces generowania kluczy powinien również wykorzystywać losowość, aby zapewnić, że klucze są nieprzewidywalne, ponieważ każdy wzorzec lub przewidywalność w generowaniu kluczy mogłyby zostać wykorzystane przez atakującego. Losowość jest również używana do dopełniania (paddingu) podczas szyfrowania w celu generowania semantycznie bezpiecznych szyfrogramów oraz w ramach schematów podpisów cyfrowych do tworzenia unikalnych podpisów, nawet gdy ta sama wiadomość jest podpisywana wielokrotnie. Z tego powodu stosowanie silnych generatorów liczb losowych stanowi istotną część AKC.

Duży rozmiar klucza: Podobnie jak w przypadku SKC, duże rozmiary kluczy zapewniają ochronę przed atakami typu brute force. Jednakże, ponieważ duże rozmiary kluczy również zwiększają koszt obliczeniowy procesu szyfrowania i deszyfrowania, optymalne rozwiązanie musi równoważyć względy bezpieczeństwa i wydajności. Poniższa tabela przedstawia typowe rozmiary kluczy dla różnych protokołów i zastosowań kryptografii klucza asymetrycznego:

Protokół	Typowe rozmiary klucza (w bitach)	Zastosowanie
RSA	1024 (wycofany), 2048, 3072, 4096	Szyfrowanie, podpisy cyfrowe
DSA	1024 (wycofany), 2048, 3072	Podpisy cyfrowe
DH	2048, 3072, 4096	Wymiana kluczy
ECDH	224, 256, 384, 521	Wymiana kluczy
ECDSA	224, 256, 384, 521	Podpisy cyfrowe

Infrastruktura klucza publicznego: W AKC klucze prywatne muszą być utrzymywane w tajemnicy przez właścicieli, podczas gdy klucze publiczne są udostępniane. Konieczny jest bezpieczny mechanizm zarządzania tymi kluczami publicznymi i ich dystrybucji pomiędzy użytkownikami. Infrastruktura klucza publicznego (PKI) zapewnia sposób na to za pomocą certyfikatów cyfrowych. Certyfikat cyfrowy stanowi dowód tożsamości właściciela klucza publicznego i jest wydawany przez zaufany urząd, taki jak urząd certyfikacji (który jest częścią PKI). Stąd PKI odgrywa nieodłączną rolę w bezpieczeństwie nowoczesnych aplikacji wykorzystujących AKC, umożliwiając zarządzanie kluczami na dużą skalę (poprzez tworzenie, zarządzanie, dystrybucję i unieważnianie certyfikatów cyfrowych).

Zagrożenia bezpieczeństwa dla kryptografii klucza asymetrycznego

Jak pokazano w powyższej tabeli, nowoczesne algorytmy klucza asymetrycznego, takie jak RSA, zazwyczaj stosują znacznie większe rozmiary kluczy niż powszechnie używane odpowiedniki klucza symetrycznego, takie jak AES-128. Nawet protokoły oparte na ECC (ECDH i ECDSA), które mają mniejsze rozmiary kluczy, stosują minimum co najmniej 224 bitów dla kluczy. To z kolei oznacza, że atak typu brute force polegający na wyczerpującym przeszukaniu przestrzeni kluczy prywatnych w celu zidentyfikowania właściwego klucza jest obliczeniowo nieosiągalny w dającej się przewidzieć przyszłości. Pozostaje to prawdą nawet gdyby do tego zadania wykorzystano komputery kwantowe. Dlatego ataki na AKC zwykle koncentrują się na wykorzystywaniu innych potencjalnych słabości konkretnych kryptosystemów. Niektóre dobrze udokumentowane tryby ataków celują w:

1. Słabości algorytmiczne poprzez wykorzystanie wyrafinowanych środków matematycznych i obliczeniowych do podważenia założeń dotyczących trudności, na których oparto algorytmy klucza asymetrycznego. Na przykład bezpieczeństwo RSA opiera się na trudności faktoryzacji dużych liczb pierwszych, a ostatnie postępy obliczeniowe umożliwiły pomyślną faktoryzację 829-bitowych kluczy RSA. Dlatego 1024-bitowe RSA jest obecnie wycofywane. Jak zostanie omówione w dalszej części, główne zagrożenie, jakie komputery kwantowe stanowią dla AKC, również mieści się w tej kategorii.

2. Niedoskonała losowość, która może prowadzić do słabości procesu generowania kluczy. Na przykład, jeśli generator liczb losowych używany do tworzenia kluczy jest wadliwy i generuje klucze, które nie są naprawdę losowe, atakujący może być w stanie przewidzieć klucze.

3. Błędy implementacji, takie jak błędy w implementacji algorytmów kryptograficznych, które nieumyślnie ujawniają informacje o kluczach. Na przykład nieprawidłowe dopełnienie (padding) może potencjalnie ujawniać szczegóły dotyczące kluczy.

4. Kanały boczne, które odnoszą się do wycieku informacji z systemu fizycznego wykonującego kryptografię. Takie wycieki mogą mieć postać informacji o czasie, zużyciu energii, a nawet dźwięku, które można wykorzystać w tak zwanym ataku kanałem bocznym. Na przykład analiza czasu potrzebnego na wykonanie operacji kryptograficznych może ujawnić liczbę jedynek w kluczu binarnym. Ten pozornie niewinny wyciek znacząco zawęża przestrzeń przeszukiwania, ujawniając potencjalne rozwiązania problemów, które początkowo wydawały się nie do pokonania.

5. Wymiana kluczy poprzez przechwytywanie kluczy podczas ich wymiany, na przykład w ramach ataku man-in-the-middle (MITM). Protokół DH jest podatny na ataki MITM, jeśli nie zostaną uwzględnione dodatkowe kroki uwierzytelniania.

6. Przechowywanie kluczy poprzez próby kradzieży kluczy ze słabo zabezpieczonego miejsca przechowywania. Obejmuje to ataki fizyczne, takie jak manipulacja lub kradzież urządzeń pamięci masowej.

Zabezpieczanie kryptosystemów klucza asymetrycznego przed różnorodnością możliwych ataków jest zatem znaczącym zadaniem obejmującym rozważania matematyczne, sprzętowe, programowe, logistyczne i prawne.

RSA

Algorytm RSA (Rivest-Shamir-Adleman) jest jednym z pierwszych kryptosystemów klucza publicznego i jest szeroko używany do bezpiecznej transmisji danych. Jest to wszechstronny kryptosystem, ponieważ zapewnia niezbędne operacje umożliwiające szyfrowanie, deszyfrowanie, podpisy cyfrowe oraz wymianę kluczy w ramach wspólnego szkieletu.

W tej sekcji zilustrujemy kryptografię klucza asymetrycznego (AKC) przy użyciu RSA na prostych przykładach.

Użyjemy standardowego scenariusza z dwiema stronami, Alicją i Bobem, którzy chcą komunikować się bezpiecznie za pomocą AKC.

Algorytm RSA

Podstawowy algorytm RSA obejmuje cztery operacje: generowanie kluczy, dystrybucję kluczy, szyfrowanie i deszyfrowanie:

1. Generowanie kluczy:

   Klucze publiczny i prywatny są generowane na podstawie zasad matematycznych dotyczących liczb pierwszych, gdzie ich obliczanie jest łatwe, ale operacja odwrotna jest trudna.

   Będziemy się do nich odnosić następująco:

   • Klucz publiczny: $(e, n)$
   • Klucz prywatny: $(d, n)$

   Zauważ, że $n$ jest wspólny zarówno dla klucza publicznego, jak i prywatnego, i jest znany jako moduł. Będziemy musieli użyć go później.

Szczegóły matematyczne

• Wybierz dwie różne liczby pierwsze, $p$ i $q$.
  • wybrane losowo (ze względów bezpieczeństwa).
  • Powinny być zbliżone wielkością, ale różnić się długością o kilka cyfr, aby utrudnić faktoryzację.
  • Liczby pierwsze można skutecznie wybierać przy użyciu testu pierwszości.
• Oblicz $n = p*q$.
  • $n$ jest modułem zarówno dla klucza publicznego, jak i prywatnego.
• Oblicz tocjent $φ$$(n) = (p-1)*(q-1)$.
  • Tocjent powinien być utrzymywany w tajemnicy i zazwyczaj jest odrzucany po wygenerowaniu kluczy.
• Wybierz liczbę całkowitą $e$ taką, że $1 < e <$$φ$$(n)$ oraz $gcd$$(e,$$φ$$(n)) = 1$.
  • to znaczy, $e$ i $φ$$(n)$ powinny być względnie pierwsze.
  • Ta liczba $e$ tworzy wykładnik klucza publicznego i zazwyczaj jest wybierana jako mała liczba dla efektywności obliczeniowej.
  • Często używana jest liczba pierwsza $65537 = 2^{16} + 1$.
  • Oblicz $d$ tak, aby spełniało relację przystawania $d*e ≡ 1 ($$mod$$φ$$(n))$.
    • To znaczy, $d$ jest odwrotnością multiplikatywną $e$ modulo $φ$$(n)$.
    • Jest to efektywniej obliczane przy użyciu rozszerzonego algorytmu Euklidesa.
    • Ta liczba $d$ jest wykładnikiem klucza prywatnego.
• Klucz publiczny składa się z $(e, n)$, a klucz prywatny to $(d, n)$.

2. Dystrybucja kluczy:

   • Klucz publiczny $(e, n)$ jest udostępniany tym, którzy mogą chcieć wysłać wiadomość
   • Klucz prywatny $(d, n)$ jest utrzymywany w tajemnicy.

3. Szyfrowanie:

   • Alicja chce wysłać wiadomość $M$ do Boba. W tym przypadku jest to prosta liczba całkowita
   • Alicja używa klucza publicznego Boba $(e, n)$ do zaszyfrowania wiadomości w szyfrogram $C$

   Szczegóły matematyczne

   • $M$ jest liczbą całkowitą $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$, gdzie $C$ jest szyfrogramem.

4. Deszyfrowanie:

   • Bob otrzymuje szyfrogram $C$
   • Bob używa swojego klucza prywatnego $(d, n)$ do odszyfrowania wiadomości z powrotem do postaci $M$

   Szczegóły matematyczne

   • $M ≡ C^d (mod n)$.

To jest podstawowy zarys RSA. W praktyce, bardziej wyrafinowane schematy dopełnienia są stosowane do tekstu jawnego $M$ przed szyfrowaniem, aby zapewnić, że identyczne teksty jawne dają różne szyfrogramy. Zapobiega to szeregowi możliwych ataków na naiwne implementacje RSA i umożliwia bezpieczeństwo semantyczne.

Ilustracja RSA w Pythonie

W kolejnych komórkach kodu zilustrujemy prosty przykład algorytmu RSA przy użyciu małych liczb całkowitych, a następnie zademonstrujemy praktyczne zastosowania dystrybucji kluczy i podpisów cyfrowych przy użyciu bibliotek Pythona implementujących RSA.

uwaga

Uwaga: W tej sekcji pokażemy szczegółowe obliczenia matematyczne jako część kodu Pythona

Generowanie kluczy RSA

Przejdźmy krok po kroku przez prosty przykład algorytmu RSA wykorzystujący małe liczby pierwsze.

Będziemy musieli umieć obliczyć największy wspólny dzielnik dwóch liczb całkowitych, ponieważ będzie to potrzebne do sprawdzenia, czy dwie liczby całkowite są względnie pierwsze.

Wyjaśnimy jeden prosty sposób jego obliczania, ale w przypadku większych liczb całkowitych znacznie wydajniej jest używać funkcji math.gcd z Pythona.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

Pierwszą fazą przepływu pracy RSA jest generowanie kluczy. Rozpoczyna się ono od wyboru dwóch liczb pierwszych, które mają być utrzymywane w tajemnicy przez podmiot generujący klucze.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Następnie obliczany jest moduł $n$, który jest po prostu iloczynem dwóch wybranych liczb pierwszych. Ten moduł zostanie opublikowany jako część klucza publicznego.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

Następnie obliczana jest funkcja tocjentu Eulera $\varphi(n)$, ponieważ jest ona potrzebna do operacji modularnej odwrotności multiplikatywnej używanej do wyznaczenia kluczy w RSA. $phi$ jest również utrzymywane w tajemnicy i zazwyczaj odrzucane po wygenerowaniu kluczy.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Jesteśmy teraz gotowi do obliczenia kluczy publicznego i prywatnego. W RSA każdy z nich jest określony przez krotkę dwóch liczb całkowitych. Pierwszym wpisem w każdej krotce jest odrębna liczba całkowita, a drugim wpisem jest moduł $n$ wspólny dla obu kluczy.

Pierwszym wpisem w kluczu publicznym może być dowolna liczba całkowita większa od 1, która jest względnie pierwsza z $phi$. Dwie liczby całkowite są względnie pierwsze, jeśli ich największy wspólny dzielnik wynosi 1. Używamy więc funkcji math.gcd, aby znaleźć liczbę całkowitą $e$ względnie pierwszą z $phi$.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

Klucz prywatny wymaga liczby całkowitej $d$, która jest odwrotnością multiplikatywną $e$ modulo $phi$; to znaczy spełnia relację przystawania $d*e\equiv 1 \pmod{\varphi(n)}$. Dla tej prostej ilustracji, w której mamy do czynienia z małymi liczbami całkowitymi, możemy po prostu iterować po dodatnich liczbach całkowitych, aby znaleźć odpowiednie $d$. W realistycznych warunkach do tego celu używany jest obliczeniowo wydajny rozszerzony algorytm Euklidesa.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Tworzymy teraz krotki $(e, n), (d, n)$, które stanowią odpowiednio klucz publiczny i prywatny. Klucz publiczny jest następnie publikowany, podczas gdy klucz prywatny jest utrzymywany w tajemnicy.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

Szyfrowanie i deszyfrowanie w RSA wykorzystują operację modularnego potęgowania. Ponadto klucze publiczny i prywatny są komplementarne w tym sensie, że każdy z nich może zostać użyty do zaszyfrowania wiadomości, którą następnie może odszyfrować drugi.

Tutaj ilustrujemy przypadek, w którym klucz publiczny $(e,n)$ jest używany do szyfrowania, a klucz prywatny $(d, n)$ jest używany do deszyfrowania, definiując funkcję Pythona dla każdej operacji.

Następnie szyfrujemy i deszyfrujemy całkowitoliczbową wiadomość $msg$.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

Chociaż małe liczby całkowite użyte powyżej są pomocne do łatwego przedstawienia kluczowych idei algorytmu RSA, w rzeczywistych zastosowaniach RSA wymaga użycia bardzo dużych liczb całkowitych. Na przykład 2048-bitowy RSA wymaga użycia modułu $n$ o długości 2048 bitów, którego dziesiętne odpowiedniki całkowite wynoszą około 10$^616$. Te naprawdę ogromne liczby są niezbędne dla praktycznego bezpieczeństwa RSA.

Wymiana kluczy symetrycznych z użyciem RSA

Jak omówiono wcześniej, AKC umożliwia dwóm stronom, które chcą się komunikować, bezpieczne ustalenie wspólnego sekretu, który może być użyty na przykład jako tajny klucz do późniejszego symetrycznego szyfrowania większych ilości tekstu jawnego.

Rozważmy następujący scenariusz. Alice i Bob chcą użyć SKC do szyfrowania i odszyfrowywania wiadomości. Jednak zanim ten proces będzie mógł się rozpocząć, muszą uzgodnić wspólny tajny klucz. Jedną z opcji jest, aby jedna strona — powiedzmy Alice — wygenerowała tajny klucz, a następnie bezpiecznie przekazała go Bobowi. Aby osiągnąć ten bezpieczny transfer, Alice decyduje się użyć RSA jako mechanizmu enkapsulacji klucza (KEM).

Obejmuje to następujące kroki:

• Najpierw Alice generuje losowy klucz symetryczny, który zamierza udostępnić Bobowi.
• Następnie Bob generuje parę kluczy asymetrycznych i udostępnia swój klucz publiczny na odpowiednim kanale.
• Potem Alice używa klucza publicznego Boba do zaszyfrowania klucza symetrycznego, enkapsulując go w ten sposób w szyfrogramie.
• Następnie Alice rozgłasza szyfrogram w niezawodnym, ale niekoniecznie bezpiecznym kanale.
• Na koniec Bob odbiera szyfrogram i odszyfrowuje go przy użyciu swojego klucza prywatnego. Teraz ma dostęp do klucza symetrycznego wygenerowanego przez Alice.

Rysunek 1. Wymiana klucza symetrycznego z użyciem RSA

Przykład wymiany kluczy w Pythonie opartej na dopełnianiu

Praktyczny przepływ pracy wykorzystujący RSA do nieinteraktywnej wymiany kluczy opartej na dopełnianiu jest teraz zilustrowany przy użyciu biblioteki Pythona cryptography.

Zaimportuj niezbędne moduły z biblioteki Pythona cryptography. W razie potrzeby tę bibliotekę można zainstalować za pomocą polecenia pip install cryptography.

Alice następnie generuje losowy tajny klucz, który zamierza przekazać Bobowi.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

Używając modułu rsa z biblioteki cryptography, Bob generuje parę kluczy, a następnie rozgłasza swój klucz publiczny. Każdy może przechwycić klucz publiczny i odczytać liczby publiczne $(e,n)$, które tworzą klucz.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

W tym momencie zakładamy, że Alice otrzymała klucz publiczny rozgłoszony przez Boba. Powyższy symmetric_key Alice może teraz zostać zaszyfrowany przy użyciu klucza publicznego Boba, aby wytworzyć szyfrogram. W realistycznym scenariuszu Alice użyje również dodatkowych metod dopełniania, takich jak OAEP, aby zapewnić semantyczne bezpieczeństwo swojej komunikacji z Bobem.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice następnie rozgłasza szyfrogram w otwartym kanale, mając pewność, że tylko Bob, z odpowiednim kluczem prywatnym, będzie w stanie go odszyfrować. Zakładamy, że Bob otrzymał szyfrogram i może go teraz odszyfrować przy użyciu swojego poufnego klucza prywatnego.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

W tym momencie Alice i Bob mają oboje dostęp do tajnego klucza symetrycznego, którego mogą użyć w zastosowaniach SKC.

Symulacja mechanizmu enkapsulacji klucza z użyciem RSA w Pythonie

W poniższym przepływie pracy ilustrujemy użycie RSA do symulacji mechanizmu enkapsulacji klucza (KEM), w którym wystarczająco długa losowa tajna wiadomość jest bezpiecznie wymieniana, a następnie konwertowana na wspólny sekret o odpowiedniej długości przy użyciu KDF.

Po raz kolejny Alice i Bob chcą ustalić wspólny sekret w sposób nieinteraktywny, a Alice jest stroną, która decyduje, którego sekretu użyć.

Zaczynamy od zaimportowania niezbędnych bibliotek Pythona.

Bob następnie generuje swoją parę kluczy RSA i rozgłasza swój klucz publiczny.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice najpierw generuje długi losowy sekret, z którego ostatecznie zostanie wyprowadzony wspólny sekret. W czystym KEM długi sekret będzie losowym elementem ze struktury algebraicznej leżącej u podstaw kryptosystemu. W przypadku 2048-bitowego RSA byłaby to losowa liczba całkowita modulo 2048-bitowy moduł RSA. Jako taki, czysty KEM nie wymaga dodatkowego dopełniania, ale w tym przykładzie tylko symulujemy KEM przy użyciu RSA, a biblioteka cryptography wymaga użycia dopełniania przy szyfrowaniu za pomocą RSA. Użyjemy więc nieco krótszego długiego sekretu, który mimo to jest znacznie dłuższy niż standardowy 256-bitowy klucz AES.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

Następnie Alice szyfruje długi sekret przy użyciu klucza publicznego Boba, a zaszyfrowany sekret zostaje przekazany Bobowi.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob odszyfrowuje zaszyfrowany sekret otrzymany od Alice przy użyciu swojego klucza prywatnego.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

Na koniec zarówno Alice, jak i Bob oddzielnie stosują uzgodnioną funkcję wyprowadzania klucza (KDF) na długim sekrecie, aby wyprowadzić klucz symetryczny.

Zauważ, że proces obejmuje protokół haszowania i użycie losowej soli, która zapewnia unikalność i nieprzewidywalność wspólnego klucza symetrycznego w przypadku ponownego użycia długiego sekretu (co nie jest zalecane). Jednak sama sól nie musi być tajna i po jej losowym wygenerowaniu, powiedzmy przez Alice w tym przykładzie, może być rozgłoszona Bobowi wraz z zaszyfrowanym długim sekretem.

Zakładamy zatem, że zarówno Alice, jak i Bob mają dostęp do tej samej losowej soli.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Podpisy cyfrowe z RSA

Teraz rozszerzymy opisany powyżej scenariusz poufnej komunikacji pomiędzy Alicją a Bobem o weryfikację z wykorzystaniem podpisu cyfrowego.

Tak jak wcześniej, Alicja poufnie wyśle Bobowi wiadomość zawierającą klucz symetryczny, ale dodatkowo podpisze ją cyfrowo, dzięki czemu Bob po odebraniu wiadomości będzie mógł zweryfikować, że to właśnie Alicja była jej nadawcą oraz że treść wiadomości nie została zmieniona podczas transmisji.

Ogólniej rzecz biorąc, pożądane jest umożliwienie weryfikacji bez naruszania poufności, tak aby każda zainteresowana strona mogła zweryfikować integralność, autentyczność oraz ustanowić niezaprzeczalność danej komunikacji, nawet jeśli ta strona nie ma dostępu do rzeczywistej wiadomości w postaci jawnego tekstu.

Rozważymy to ogólne ustawienie, które obejmuje następujące kroki:

• Najpierw zarówno Bob, jak i Alicja udostępniają swoje klucze publiczne przez otwarty kanał.
• Następnie Alicja szyfruje jawny tekst za pomocą klucza publicznego Boba, tworząc szyfrogram.
• Potem Alicja tworzy skrót szyfrogramu za pomocą funkcji skrótu i dodatkowo szyfruje uzyskany skrót szyfrogramu, używając swojego klucza prywatnego. Ten zaszyfrowany skrót to podpis.
• Następnie Alicja przesyła zarówno szyfrogram, jak i podpis przez otwarty kanał.
• Potem Bob używa klucza publicznego Alicji, aby odszyfrować podpis, ujawniając skrót szyfrogramu.
• Następnie, ponieważ Bob ma również dostęp do samego szyfrogramu, używa tej samej funkcji skrótu, której użyła Alicja, aby odtworzyć drugą wersję skrótu szyfrogramu. Jeśli ta druga wersja pasuje do tej uzyskanej przez odszyfrowanie podpisu Alicji, wówczas wiadomość jest zweryfikowana, mimo że sam szyfrogram nie został jeszcze odszyfrowany.
• Na koniec Bob, po zweryfikowaniu wiadomości, odszyfrowuje szyfrogram przy użyciu swojego klucza prywatnego.

Rysunek 2. Podpisy cyfrowe z RSA

Ten przepływ pracy dla podpisu cyfrowego zostanie zilustrowany poniżej.

Ponownie importujemy kilka użytecznych modułów z biblioteki cryptography. Tak jak wcześniej, Alicja zamierza bezpiecznie wysłać klucz symetryczny do Boba, ale chce go również podpisać cyfrowo. W tym przypadku potrzebujemy kluczy publicznych zarówno dla Alicji, jak i dla Boba. Dlatego pierwszym krokiem jest wygenerowanie przez Alicję i Boba własnej pary kluczy za pomocą RSA i rozgłoszenie swojego klucza publicznego światu.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

W następnym kroku, tak jak wcześniej, Alicja używa klucza publicznego Boba, aby zaszyfrować klucz symetryczny i przygotować szyfrogram.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

Na tym etapie, zamiast po prostu rozgłaszać szyfrogram, Alicja zamierza dołączyć do niego podpis cyfrowy, aby móc udowodnić Bobowi, że to ona była nadawcą wiadomości. Odbywa się to w dwóch krokach:

1. Utworzenie skrótu szyfrogramu za pomocą algorytmu skrótu.
2. Zaszyfrowanie skrótu przy użyciu klucza prywatnego Alicji, co stanowi podpis.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Następnie Alicja rozgłasza szyfrogram i podpis przez sieć, aby Bob mógł przechwycić oba.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Po stronie Boba pierwszym zadaniem jest weryfikacja integralności i autentyczności szyfrogramu. W tym celu Bob tworzy skrót otrzymanego szyfrogramu za pomocą tego samego algorytmu skrótu, którego użyła Alicja.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Następnie Bob odszyfrowuje otrzymany podpis za pomocą klucza publicznego Alicji. Ponieważ Alicja użyła swojego klucza prywatnego do utworzenia podpisu, Bob jest w stanie odszyfrować go przy użyciu klucza publicznego Alicji. Odszyfrowany podpis to nic innego jak skrót szyfrogramu utworzony po stronie Alicji. Jeśli skrót utworzony przez Boba pasuje do odszyfrowanego podpisu, wówczas Bob potwierdza, że otrzymany szyfrogram nie został zmieniony oraz że to Alicja podpisała szyfrogram.

W poniższym kodzie Pythona te operacje są połączone w użyteczną funkcję pomocniczą o nazwie verify, udostępnianą przez obiekt powiązany z kluczem publicznym Alicji.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

Po zweryfikowaniu integralności i autentyczności otrzymanego szyfrogramu Bob może go odszyfrować przy użyciu swojego klucza prywatnego, ponieważ Alicja utworzyła szyfrogram, używając klucza publicznego Boba.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

W powyższym scenariuszu podpisu cyfrowego każda strona — nie tylko Bob — może zweryfikować, że Alicja jest nadawcą szyfrogramu, ponieważ każdy ma dostęp do klucza publicznego Alicji, szyfrogramu oraz podpisu cyfrowego. Ponadto po wysłaniu szyfrogramu i podpisu Alicja nie może później zaprzeczyć, że to zrobiła, ponieważ podpis można odszyfrować do znaczącego skrótu, używając wyłącznie jej klucza publicznego. Ustanawia to niezaprzeczalność.

Umożliwiając bezpieczną dystrybucję kluczy i wspierając niezaprzeczalność, kryptografia klucza publicznego stanowi solidny fundament dla bezpiecznej komunikacji cyfrowej.

Łamanie RSA

Użyteczność i bezpieczeństwo algorytmu RSA opisanego powyżej opiera się na dwóch założeniach matematycznych:

1. Znalezienie odwrotności multiplikatywnej modulo $d$, mając dostęp jedynie do $(e, n)$, jest obliczeniowo niewykonalne.

2. W kontekście RSA operacja potęgowania modularnego zachowuje się jak jednokierunkowa funkcja z zapadką. Używana do szyfrowania daje szyfrogram, który jest nieczytelny, a bez dostępu do klucza prywatnego odwrócenie operacji w celu odzyskania jawnego tekstu z szyfrogramu jest niewykonalne. Jednak mając dostęp do klucza prywatnego, który działa jak zapadka, szyfrogram można łatwo odszyfrować.

Najbardziej znany atak na algorytm RSA ma na celu podważenie założenia 1 poprzez efektywne odzyskanie liczby stanowiącej klucz prywatny $d$ poprzez faktoryzację modułu $n$. Jak zostanie pokazane poniżej, łatwo jest odzyskać $d$, jeśli ma się dostęp do czynników pierwszych $p$ i $q$ liczby $n$ albo do tocjentu $φ$$(n)$. Przypomnijmy, że $p$, $q$ oraz $φ$$(n)$ są utrzymywane w tajemnicy podczas generowania kluczy i odrzucane po jego zakończeniu. Trzecia strona, która odzyskuje te informacje przy użyciu komputera klasycznego lub kwantowego, w praktyce odkrywa klucz prywatny, łamiąc RSA. Dlatego faktoryzacja liczb pierwszych jest kluczowym prymitywem obliczeniowym niezbędnym do złamania RSA.

Obliczenia klasyczne a RSA

Wiadomo, że faktoryzacja dużych liczb całkowitych na czynniki pierwsze wykazuje superwielomianowe lub subwykładnicze skalowanie na komputerach klasycznych. Najlepiej znany klasyczny algorytm do faktoryzacji liczb całkowitych większych niż $10^{100}$ to ogólne sito ciała liczbowego (GNFS)

Szczegóły matematyczne

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

jako funkcja liczby całkowitej $n$ poddawanej faktoryzacji.

To skalowanie jest superwielomianowe w liczbie bitów wymaganych do reprezentacji $n$.

Dlatego faktoryzacja liczb pierwszych jest uważana za nieefektywną na komputerach klasycznych.

Obecnie największe liczby całkowite rozłożone na czynniki na sprzęcie klasycznym mieszczą się w zakresie 829 bitów lub 250 cyfr dziesiętnych. Biorąc pod uwagę wykładniczy wzrost mocy obliczeniowej komputerów klasycznych obserwowany w ciągu ostatnich kilku dekad, 1024-bitowy RSA nie jest już uważany za bezpieczny w najbliższym czasie i jest obecnie wycofywany. Niemniej jednak w dającej się przewidzieć przyszłości faktoryzacja 2048-bitowych liczb całkowitych, których wielkość mieści się w zakresie $10^{617}$, jest obecnie uważana za niewykonalną w systemach klasycznych, co sugeruje dalszą żywotność. Pojawienie się komputerów kwantowych unieważnia jednak tę ocenę.

Kwantowy algorytm Shora i RSA

Prawdopodobnie najbardziej znanym algorytmem kwantowym jest dzisiaj algorytm Shora do znajdowania czynników pierwszych liczb całkowitych. Kiedy został przedstawiony przez Petera Shora w 1994 roku, został uznany za pierwszy algorytm kwantowy, który oferował przyspieszenie superwielomianowe w stosunku do algorytmów klasycznych w problemie o dużym znaczeniu praktycznym, a mianowicie faktoryzacji liczb pierwszych.

Algorytm Shora może faktoryzować liczby pierwsze z $O(n^2)$, gdzie $n$ to liczba bitów.

Matematyczne wyjaśnienie algorytmu Shora

W kontekście RSA, algorytm Shora działa poprzez wykorzystanie okresowości funkcji wykładniczej modularnej $f(x) = a^x (mod~n)$ i dostarcza kwantowego prymitywu do znajdowania okresu, który umożliwia efektywną faktoryzację liczby modulus $n$.

Uproszczony wysokopoziomowy zarys ogólnego schematu Shora do łamania RSA jest następujący:

1. Mając modulus $n$, który jest publikowany jako część klucza publicznego, wybierz liczbę $a$ względnie pierwszą z $n$, to znaczy $gcd(a,n) = 1$. Ponieważ wiemy, że $n = p*q$ ma dokładnie dwa czynniki pierwsze $(p, q)$, prawie każda liczba mniejsza od $n$, którą wybierzemy losowo, będzie prawdopodobnie względnie pierwsza z $n$.

2. Po wybraniu $a$, znajdź wykładnik $r$ taki, że $a^r \equiv 1 (mod~n)$. Oznacza to $a^r - 1 \equiv 0 (mod~n)$. Istnienie wykładnika $r$ takiego, że powyższa kongruencja zachodzi, jest gwarantowane przez własność okresowości potęgowania modularnego.

3. Jeśli $r$ jest parzyste, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ dla pewnej liczby całkowitej $\gamma$. Lewa strona tej ostatniej równości musi zawierać $p$ i $q$ jako dwa ze swoich czynników pierwszych, ponieważ zawiera je prawa strona. Jeśli $r$ jest nieparzyste, wróć do kroku 1 i spróbuj innego wyboru $a$.

4. Użyj rozszerzonego algorytmu Euklidesa do znalezienia $gcd((a^{r/2} - 1), n)$ lub $gcd((a^{r/2} + 1), n)$. Obliczony GCD bardzo prawdopodobnie zidentyfikuje jeden z czynników pierwszych $p$ lub $q$. Podziel $n$ przez ten czynnik pierwszy, aby odzyskać drugi.

5. Gdy znane są $p, q$, użyj kroków z oryginalnego algorytmu RSA do rekonstrukcji tocjentu $\phi(n)$ i wygenerowania liczby klucza prywatnego $d$ jako odwrotności modularnej znanej liczby klucza publicznego $e$.

W sierpniu 2023 roku Oded Regev opublikował ulepszenie oryginalnego algorytmu Shora przy użyciu podejścia wielowymiarowego, co daje $O(n^{1.5})$. W tej dziedzinie trwają dalsze badania, w tym prace Ragavana i Vaikuntanathana, które mogą poprawić czas, koszt lub liczbę wymaganych kubitów. Chociaż nie możemy powiedzieć, kiedy uruchamianie takich algorytmów przeciwko rzeczywistemu szyfrowaniu RSA stanie się naprawdę wykonalne, staje się to coraz bliższe.

Przykład w Pythonie demonstrujący łamanie szyfrowania RSA

W poniższych komórkach kodu ilustrujemy przykład znajdowania klucza prywatnego mając jedynie klucz publiczny. Wykorzysta to klasyczne obliczenia siłowe (brute-force), ale pokazuje, jak można by wykorzystać algorytm Shora - w tym dla dużych kluczy.

uwaga

W tej sekcji pokażemy obliczenia matematyczne szczegółowo jako część kodu Pythona

W tym przykładzie mamy klucz publiczny $(5, 247)$ i odzyskamy klucz prywatny.

Krok 1: Pierwszym krokiem jest wybranie liczby względnie pierwszej z 247. Prawie każda liczba, którą zgadniemy, wykona to zadanie. Wybierzmy 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Krok 2: Następnie musimy znaleźć okres $r$ taki, że $6^r \equiv 1 (mod~247)$. W tym przykładzie obliczamy $r$ klasycznie metodą siłową, ale moglibyśmy również użyć algorytmu Shora na komputerze kwantowym przy użyciu Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Krok 3: Ponieważ okres $r = 36$ jest parzysty, możemy obliczyć $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Krok 4: Znajdź GCD dowolnego z tych czynników z $n$. Po prostu podziel $n$ przez już znaleziony czynnik pierwszy, aby uzyskać drugi czynnik pierwszy.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Krok 5: Po odzyskaniu czynników pierwszych liczby $n = 247$ jako $p_{found}=13$ oraz $q_{found}=19$, obliczamy tocjent $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

Klucz prywatny to odwrotność modularna liczby klucza publicznego $e=5$.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

W powyższym schemacie krok 2 jest kluczową operacją wyznaczania okresu, do której algorytm Shora wykorzystuje dwie fundamentalne prymitywy kwantowe, a mianowicie kwantową transformatę Fouriera oraz kwantową estymację fazy. Szczegółowe wyjaśnienie kwantowych aspektów algorytmu Shora znajduje się w lekcji o estymacji fazy i faktoryzacji w kursie Fundamentals of Quantum Algorithms. Kroki 1 oraz 3 do 5 obejmują stosunkowo tanie operacje, które można łatwo wykonać na komputerach klasycznych.

Opcjonalnie, oto szczegółowy wizualny przewodnik po implementacji algorytmu Shora.

Na komputerach kwantowych algorytm Shora może wykazywać skalowanie polilogarytmiczne tak korzystne jak $O((log~n)^2 (log~log~n))$ w odniesieniu do modułu $n$, lub skalowanie wielomianowe w odniesieniu do liczby bitów potrzebnych do reprezentacji $n$. Jest to przyspieszenie superwielomianowe w porównaniu z klasycznym algorytmem GNFS.

Ostatnie szacunki zasobów wskazują, że w oparciu o pewne założenia dotyczące konfiguracji sprzętowej, potrzebne będzie od kilkudziesięciu tysięcy do kilku milionów kubitów, aby złamać 2048-bitowe RSA za pomocą algorytmu Shora. Nie jest wykluczone, że komputery kwantowe z kilkudziesięcioma tysiącami kubitów staną się dostępne w ciągu kilku najbliższych lat, co uczyni dolny koniec szacunków zasobów osiągalnym.

Wymiana kluczy Diffiego-Hellmana i algorytm podpisu cyfrowego

W poprzedniej sekcji omówiliśmy kryptosystem RSA, którego bezpieczeństwo opiera się na obliczeniowej trudności faktoryzacji liczb pierwszych. Tutaj omówimy dwa popularne protokoły kryptografii asymetrycznej, wymianę kluczy Diffiego-Hellmana (DH) oraz algorytm podpisu cyfrowego (DSA), z których oba opierają się na innym problemie matematycznym, a mianowicie problemie logarytmu dyskretnego (DLP).

Problem logarytmu dyskretnego

W poniższym równaniu musimy znaleźć $a$ mając dane tylko $e$,$M$,$c$

$a^e$ $mod$ $M = c$

Uważa się, że jest to trudne na komputerach klasycznych ze względu na użycie arytmetyki modulo, a zatem stanowi dobrą podstawę matematyczną dla algorytmu szyfrowania.

Jest to znane jako problem logarytmu dyskretnego (DLP).

Matematyczne szczegóły problemu logarytmu dyskretnego

DLP jest zwykle ujmowany w kontekście grup cyklicznych i jest sformułowany następująco.

Rozważmy grupę cykliczną $G$ generowaną przez element grupy $g \in G$, a mając dany dowolny element $h \in G$, znajdź liczbę całkowitą $k$ taką, że $h = g^{k}$.

Tutaj liczba całkowita $k \equiv log_{g}h$ jest logarytmem dyskretnym. Cykliczna własność $G$ gwarantuje, że dla każdego $h$ istnieje poprawna liczba całkowita $k$.

W kryptografii przydatny okazuje się DLP na grupie multiplikatywnej liczb całkowitych modulo liczba pierwsza $p$ oznaczonej $(\mathbb{Z}_p)^{\times}$. Elementy $(\mathbb{Z}_p)^{\times}$ są klasami kongruencji oznaczonymi liczbami całkowitymi modulo $p$, które są względnie pierwsze z $p$.

Na przykład:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{and}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

Operacja mnożenia $(\times)$ na tych grupach jest po prostu zwykłym mnożeniem liczb całkowitych, po którym następuje redukcja modulo $p$, a potęgowanie liczbą całkowitą $k$ to po prostu wielokrotne mnożenie $k$ razy i redukcja modulo $p$.

Zilustrujmy przykład DLP na $(\mathbb{Z}_7)^{\times}$.

Ta grupa multiplikatywna ma dwa generatory ${[3],[5]}$, znane również jako pierwiastki pierwotne. Użyjemy $[5]$ jako generatora; to znaczy, wygenerujemy każdy element $(\mathbb{Z}_7)^{\times}$ używając kolejnych całkowitych potęg liczby 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Widzimy, że w arytmetyce modulo 7, podnoszenie 5 do kolejnych całkowitych potęg daje każdy element $(\mathbb{Z}_7)^{\times}$ dokładnie raz, zanim cykl powtórzy się w nieskończoność z okresem $p-1 =6$.

Zatem DLP na $(\mathbb{Z}_7)^{\times}$ z generatorem [5] to:

$\mathrm{Given}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, find~} k \mathrm{~such~that~} 5^{k} \equiv h~(mod~7)$.

Z powyższego wyjścia komórki Pythona widzimy, że:

$h = 2 \implies k=4 \mathrm{~lub~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~lub~} 3 = log_5(6) (mod~7)$

W zwykłej arytmetyce liczb rzeczywistych potęgowanie jest funkcją monotoniczną, a znalezienie logarytmu dowolnej liczby przy dowolnej podstawie jest obliczeniowo łatwe. W przeciwieństwie do tego, jak widać z prostego przykładu $(\mathbb{Z}_7)^{\times}$ powyżej, potęgowanie modularne jest niemonotoniczne i choć jest okresowe z okresem $p-1$, poza tym jest wysoce nietrywialne. Dlatego obliczenie jego odwrotności, czyli logarytmu dyskretnego, okazuje się nieefektywne dla dużych $p$ na komputerach klasycznych.

Obserwacja ta stanowi podstawę zarówno wymiany kluczy Diffiego-Hellmana (DH), jak i algorytmu podpisu cyfrowego (DSA), które zostaną omówione w następnym rozdziale.

DLP można rozszerzyć na cykliczne podgrupy w następujący sposób:

• Rozważmy $(\mathbb{Z}_p)^{\times}$ zdefiniowane powyżej oraz element $g \in (\mathbb{Z}_p)^{\times}$ rzędu pierwszego $r$, to znaczy $g^r \equiv 1 (~mod~p)$.
• Zbiór potęg całkowitych $g$: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ jest cykliczną podgrupą $(\mathbb{Z}_p)^{\times}$ rzędu $r$.
• DLP można określić na $\langle g \rangle$ wybierając $h \in \\langle g \rangle$ i pytając o $1 \le a \le r$ takie, że $g^a~(mod~p) = h$

Wymiana kluczy Diffiego-Hellmana

W 1976 roku Whitfield Diffie i Martin Hellman zaproponowali protokół wymiany kluczy, który umożliwia utworzenie wspólnego klucza tajnego przez niezabezpieczone kanały komunikacyjne. Tajny klucz może być następnie używany przez strony go współdzielące do szyfrowania symetrycznego. Algorytm opiera się na DLP.

Rysunek 1. Wymiana kluczy Diffiego-Hellmana

Szczegóły matematyczne wymiany kluczy Diffiego-Hellmana

Przy założeniu, że dwiema komunikującymi się stronami są Alicja i Bob, protokół działa następująco:

• Najpierw Alicja i Bob uzgadniają dużą liczbę pierwszą $p$ oraz pierwiastek pierwotny lub generator $a$.
• Następnie Alicja losowo wybiera tajny wykładnik $k_A$ taki, że $1 \le k_A \le p-2$ i oblicza $h_A = a^{k_A}~(mod~p)$. $k_A, h_A$ są odpowiednio kluczem prywatnym i publicznym Alicji.
• Następnie Bob losowo wybiera tajny wykładnik $k_B$ taki, że $1 \le k_B \le p-2$ i oblicza $h_B = a^{k_B}~(mod~p)$. $k_B, h_B$ są odpowiednio kluczem prywatnym i publicznym Boba.
• Następnie Alicja wysyła Bobowi $h_A$, a Bob wysyła Alicji $h_B$ przez niezawodny, ale niekoniecznie bezpieczny kanał.
• Następnie Alicja używa otrzymanego $h_B$, aby obliczyć wspólny klucz tajny $\kappa = h_B^{k_A}~(mod~p)$.
• Na koniec Bob używa otrzymanego $h_A$, aby obliczyć wspólny klucz tajny $\kappa = h_A^{k_B}~(mod~p)$.

Przy tym protokole:

• Alicja i Bob mają gwarancję otrzymania tego samego tajnego klucza $\kappa$, ponieważ $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$.
• Osoba trzecia, która przechwyci $h_A$ lub $h_B$, nie może skonstruować tajnego klucza $\kappa$, ponieważ nie ma dostępu odpowiednio do $k_B$ lub $k_A$.
• Wyodrębnienie $k_A$ lub $k_B$ przy użyciu informacji publicznych $a$, $p$, $h_A$ i $h_B$ jest obliczeniowo trudne, gdyż jest równoważne rozwiązaniu DLP na $(\mathbb{Z}_p)^{\times}$.

Ilustracja protokołu Diffiego-Hellmana w Pythonie

Przyjrzyjmy się prostemu przykładowi protokołu DH w Pythonie przy użyciu małych liczb pierwszych:

uwaga

W tej sekcji pokażemy szczegółowe obliczenia matematyczne jako część kodu Pythona

Krok 1: Alicja i Bob uzgadniają liczbę pierwszą $p$ oraz pierwiastek pierwotny $a$. Wybierzmy $p=11, a=7$.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Kroki 2, 3: Alicja wybiera tajny wykładnik $k_A$ i oblicza $h_A = a^{k_A}~(mod~p)$. Podobnie Bob wybiera tajny wykładnik $k_B$ i oblicza $h_B = a^{k_B}~(mod~p)$.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Krok 4: Obie strony rozgłaszają swoje klucze publiczne $h_A$ i $h_B$.

Kroki 5, 6: Każda ze stron łączy swój klucz prywatny z kluczem publicznym drugiej strony, aby utworzyć wspólny klucz tajny.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alicja i Bob mogą teraz używać wspólnego klucza tajnego do szyfrowania symetrycznego.

Bezpieczeństwo wymiany kluczy Diffiego-Hellmana

Jak zauważono powyżej, bezpieczeństwo DH opiera się na trudności obliczeniowej rozwiązania DLP z dużymi liczbami pierwszymi $p$. W typowych zastosowaniach NIST zaleca 2048- lub 3072-bitowe liczby pierwsze dla wymiany kluczy DH, co jest uznawane za wystarczająco bezpieczne przeciwko próbom rozwiązania DLP przy użyciu komputerów klasycznych.

Ataki typu man-in-the-middle (MITM): Fakt, że DH jest interaktywnym schematem, w którym wspólny sekret zależy od połączenia klucza prywatnego jednej strony z kluczem publicznym drugiej strony, czyni go podatnym na tak zwany atak man-in-the-middle (MITM).

Szczegóły matematyczne bezpieczeństwa DH i ataków MITM

W tym scenariuszu osoba trzecia — powiedzmy Ewa — przechwytuje klucze publiczne $h_A, h_B$ podczas transmisji i zastępuje swoim kluczem publicznym $h_E$ każdy z $h_A$ i $h_B$ przed przekazaniem ich odpowiednio do Boba i Alicji.

Wtedy zamiast używać $h_B$ do utworzenia swojego wspólnego sekretu, Alicja użyje $h_E$, myśląc, że używa klucza publicznego Boba. Podobnie, zamiast używać $h_A$ do utworzenia swojego wspólnego sekretu, Bob użyje $h_E$, myśląc, że używa klucza publicznego Alicji.

Ponieważ $h_E$ został użyty do utworzenia wspólnego sekretu Alicji (Boba), tekst jawny zaszyfrowany przez Alicję (Boba) może zostać odszyfrowany przez Ewę.

Dlatego wymiana kluczy DH jest zwykle używana w połączeniu z algorytmem podpisu cyfrowego, aby zapewnić, że każda strona używa uwierzytelnionego klucza publicznego do utworzenia wspólnego sekretu.

Algorytm podpisu cyfrowego (DSA)

Chociaż ogólne kryptosystemy, takie jak RSA, zapewniają funkcjonalność podpisu cyfrowego, w 1994 roku NIST przyjął specjalistyczny schemat podpisu oparty na potęgowaniu modularnym i problemie logarytmu dyskretnego jako federalny standard podpisów cyfrowych. Schemat ten, znany po prostu jako Algorytm podpisu cyfrowego (DSA), obejmuje cztery odrębne fazy:

1. Generowanie kluczy:

   Klucze DSA generowane są z:

   • 2 liczb pierwszych spełniających określone reguły
     • $p$ - zwykle 256 bitów (długość tę nazwiemy $N$)
     • $q$ - zwykle 3072 bity (długość tę nazwiemy $L$)
   • Kryptograficznej funkcji skrótu, która będzie konwertować ciągi o długości $L$ na $N$
   • Dodatkowego parametru $g$ (szczegóły poniżej)

   Z tego wybieramy liczbę losową $x$ jako klucz prywatny i jesteśmy w stanie obliczyć klucz publiczny $y$

   Szczegóły matematyczne generowania kluczy

   • Generowanie parametrów: Matematycznie DSA obejmuje cykliczną podgrupę $(\mathbb{Z}_p)^{\times}$ generowaną przez element $g$ rzędu pierwszego q < p. Pierwszym krokiem w DSA jest zatem wybór dwóch liczb pierwszych p, q w celu ustanowienia niezbędnych struktur matematycznych.

     • Wybierz $N$-bitową liczbę pierwszą $q$.
     • Wybierz $L$-bitową liczbę pierwszą $p$ taką, że $p-1$ jest wielokrotnością $q$. Wybór $p$ określa grupę $(\mathbb{Z}_p)^{\times}$
     • Wybierz losowo liczbę całkowitą $1 < h < p-1$ i oblicz $g = h^{(p-1)/q}~mod~p$. Jeśli $g=1$, co zdarza się rzadko, spróbuj innego h.
     • Sprawdź, czy $g^q~mod~p = 1$. g jest zatem generatorem cyklicznej podgrupy $\langle g \rangle$ grupy $(\mathbb{Z}_p)^{\times}$ rzędu pierwszego q.

     Parametry $(q, p, g)$ określają instancję algorytmu i są informacją publiczną. Zwykle w realistycznych zastosowaniach $N \sim 256$ i $L \sim 3072$.

     Protokół wymaga również kryptograficznej funkcji skrótu $H : \{0,1\}^L \rightarrow \{0, 1\}^N$, która odwzorowuje binarne ciągi $L$-bitowe na ciągi $N$-bitowe, na przykład SHA-256.

   • Generowanie pary kluczy: Podpisujący musi wygenerować parę kluczy po swojej stronie.

     • Wybierz losową tajną liczbę całkowitą $x \in \{1,2...q-1\}$. $x$ jest kluczem prywatnym.
     • Wygeneruj $y = g^{x}~mod~p$. $y$ jest kluczem publicznym podpisującego.

2. Dystrybucja kluczy:

   Następujące informacje są udostępniane każdemu, kto chce zweryfikować podpis

   • Użyte parametry $(p,q,g)$, które opisują algorytm
   • Funkcja skrótu $H$
   • klucz publiczny $y$

3. Podpisywanie:

   • Podpisujący może teraz podpisać wiadomość $m$. Wynikowym podpisem jest $(r,s)$
   • Wiadomość i podpis są teraz wysyłane do odbiorcy

   Szczegóły matematyczne podpisywania wiadomości

   Podpisujący podpisuje wiadomość $m$ w następujący sposób:

   • Wybierz tajną liczbę całkowitą k losowo z $\{1,2...q-1\}$
   • Oblicz $r = (g^k~mod~p)~mod~q$. W rzadkim przypadku, gdy $r=0$, spróbuj innego losowego k.
   • Oblicz $s = (k^{-1} (H(m) + xr))~mod~q$. W rzadkich przypadkach, gdy $s=0$, spróbuj innego losowego k.
   • Podpisem jest krotka $(r, s)$.
   • Podpisujący przekazuje weryfikatorowi zarówno wiadomość $m$, jak i podpis $(r,s)$.

   Ponieważ zarówno $r$, jak i $s$ są liczbami całkowitymi modulo $q$, rozmiar podpisu jest rzędu $N$-bitów, a nie dłuższych $L$-bitów.

4. Weryfikacja:

   Odbiorca chce teraz zweryfikować autentyczność nadawcy. Ma dostęp do informacji publicznych $(q, p, g, H, y, (r,s), m)$ Może wykonać obliczenie, które dowodzi, że nadawca miał dostęp do klucza prywatnego $x$

   i dąży do ustalenia, że osoba podpisująca to ktoś, kto ma dostęp do klucza prywatnego $x$.

   Szczegóły matematyczne schematu weryfikacji DSA

   • Sprawdź, że $0 \lt r \lt q$ oraz $0 \lt s \lt q$, to znaczy, że $r, s$ są poprawnymi liczbami całkowitymi modulo~q.
   • Oblicz $w = s^{-1}~mod~q$.
   • Oblicz $u_1 = H(m)w~mod~q$.
   • Oblicz $u_2 = rw~mod~q$.
   • Oblicz $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$.
   • Podpis zostaje zweryfikowany, jeżeli $v = r$.

   Dla prawidłowych podpisów poprawność algorytmu DSA można łatwo wykazać w następujący sposób:

   • Po stronie podpisującego: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • Rozważając prawą stronę ostatniej równości, weryfikator może obliczyć $s^{-1}, H(m)$, ponieważ $s, q, m, H$ są informacjami publicznymi.
   • W ten sposób weryfikator oblicza $w = s^{-1}~mod~q$ oraz $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$.
   • Weryfikator oblicza także $u_2 = rw~mod~q = rs^{-1}~mod~q$, ponieważ $r$ również jest publiczne.
   • Zauważ, że $k = (u_1 + xu_2)~mod~q$.
   • Jednakże weryfikator nie ma dostępu do $x$, ponieważ jest to klucz prywatny podpisującego, więc samego $k$ nie można bezpośrednio obliczyć. - Schemat opiera się natomiast na fakcie, że nawet jeśli weryfikator nie może obliczyć $k$, to przy prawidłowym podpisującym weryfikator powinien być w stanie ponownie obliczyć $(g^k~mod~p)~mod~q = r$ przy pomocy klucza publicznego podpisującego $y = g^{x}~mod~p$.
   • Zatem weryfikator oblicza $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$.
   • Ostatnia równość wynika z faktu, że $g$ ma rząd $q$, i ustala $v = r$ dla prawidłowych podpisów.

Ilustracja DSA w Pythonie

W tym przykładzie użyjemy małych liczb pierwszych, aby zilustrować proces DSA w scenariuszu, w którym Alicja wysyła podpisaną wiadomość do Boba. W tym przykładzie użyjemy małych liczb całkowitych. W rzeczywistym scenariuszu stosowano by znacznie większe liczby pierwsze rzędu 2048–3072 bitów.

uwaga

Możesz spróbować ponownie uruchomić ten przykład z różnymi wartościami, aby zobaczyć, jak zachowuje się algorytm, ale upewnij się, że zaczynasz wykonywanie od pierwszej komórki w tej sekcji.

Zaczynamy od zaimportowania niezbędnych bibliotek i wyboru naszych parametrów. Parametry całkowite $p$, $q$, $g$ są informacjami publicznymi i spełniają następujące reguły:

• $p$, $q$ są liczbami pierwszymi
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Następnie podpisująca, Alicja, generuje swój klucz prywatny.

Klucz prywatny k (alice-private-key w kodzie Pythona) musi spełniać:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alicja utrzymuje swój klucz prywatny w tajemnicy.

Następnie Alicja oblicza swój klucz publiczny, używając potęgowania modularnego. Odwrócenie tego kroku w celu odzyskania klucza prywatnego jest przykładem DLP, więc jest trudne do obliczenia na komputerach klasycznych, gdy używane są duże liczby pierwsze.

Z powyższego wyjaśnienia matematycznego wiemy, że można to obliczyć za pomocą wzoru:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Jak zwykle, Alicja udostępnia swój klucz publiczny poprzez niekoniecznie bezpieczny kanał.

Teraz Alicja może podpisać wiadomość.

Dla schematu podpisu cyfrowego musimy wygenerować skrót $H(m)$ wiadomości $m$, która ma zostać podpisana.

Załóżmy, że Alicja i Bob zgadzają się używać konkretnego algorytmu haszującego o długości skrótu $N$ równej liczbie bitów w $q$. W tym prostym przykładzie ograniczymy wyjścia naszej pozornej funkcji haszującej przez $q$. Funkcja haszująca jest tu trywialna, po prostu generuje losową liczbę całkowitą.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Następnie Alicja musi wygenerować losową, unikalną dla danej wiadomości liczbę tajną $k$, a także jej odwrotność multiplikatywną modulo $q$, aby obliczyć podpis.

Do obliczenia odwrotności modularnej można użyć prostego algorytmu siłowego. Jednak lepiej jest użyć jednej z wbudowanych funkcji Pythona pow, jak pokazano poniżej

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Alicja może teraz obliczyć podpis.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

Zauważ, że istnieją pewne szczególne warunki, które będą wymagały od nas wybrania innej wartości $k$ w przypadku, gdy $r$ lub $s$ obliczy się do $0$. W takim przypadku wygenerujemy nową wartość i powtórzymy.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice rozgłasza wiadomość i swój podpis do odbiorcy lub weryfikatora, Boba.

Bob wcześniej przechwycił klucz publiczny Alice i może teraz zweryfikować podpis, aby uwierzytelnić jej wiadomość.

Aby to zrobić, wykonuje pewne sprawdzenia, a następnie ponownie generuje skrót rozgłaszanej wiadomości Alice i oblicza pomocnicze wielkości $w, u_1, u_2$ oraz $v$.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

Na koniec Bob sprawdza, czy $v$ jest równe $r$. Jeśli są równe, to podpis jest zweryfikowany.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Bezpieczeństwo DSA

W przypadku obliczeń klasycznych na bezpieczeństwo DSA może wpływać kilka czynników:

1. Rozmiar klucza: Jak zawsze, rozmiar klucza zapewnia podstawową ochronę przed atakami brute force. Nowoczesne zastosowania korzystające z DSA używają kluczy o rozmiarze co najmniej 2048 bitów.

2. Jakość $k$: W DSA każdy podpis wymaga unikatowej, losowej i tajnej wartości $k$ (patrz wyżej). Unikatowość, entropia i tajność $k$ mają kluczowe znaczenie, a słabość w którymkolwiek z tych aspektów może prowadzić do ujawnienia klucza prywatnego $x$. Generatory liczb losowych używane do generowania $k$ same muszą być bezpieczne.

3. Siła funkcji skrótu: Ponieważ DSA używa funkcji skrótu jako części procesu generowania i weryfikacji podpisu, słaba funkcja skrótu mogłaby naruszyć bezpieczeństwo podpisu cyfrowego. Na przykład użycie SHA-1 z DSA jest odradzane, a zalecane jest SHA-2 lub wyższe.

Oprócz tego, solidna implementacja DSA powinna również chronić przed innymi typami ataków wymierzonych w kryptografię klucza asymetrycznego, jak wcześniej opisano.

Uwierzytelniona wymiana kluczy z Diffie-Hellmanem i DSA

Nowoczesne protokoły bezpieczeństwa sieciowego, takie jak Transport Layer Security (TLS) i wiele innych, polegają na łączeniu funkcjonalności wymiany kluczy i uwierzytelniania. W kontekście Diffie-Hellmana uwierzytelnianie jest potrzebne do ochrony przed atakami MITM. W poniższych komórkach kodu ilustrujemy przykład, w którym Alice i Bob wykonują uwierzytelnioną wymianę kluczy, łącząc protokoły Diffie-Hellmana i DSA. W tym celu użyjemy biblioteki Pythona cryptography.

Rysunek 2. Uwierzytelniona wymiana kluczy z Diffie-Hellmanem i DSA Najpierw Alice i Bob uzgadniają zestaw parametrów DH i generują zestaw par kluczy publiczny-prywatny DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

Klucze publiczne DH są rozgłaszane. Następnie zarówno Alice, jak i Bob generują oddzielną parę kluczy do użytku z DSA. Klucze te zostaną z kolei wykorzystane do podpisania kluczy publicznych DH, które mają zostać wymienione.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice podpisuje swój klucz publiczny DH przy użyciu swojego klucza prywatnego DSA.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

Podobnie Bob podpisuje swój klucz publiczny DH przy użyciu swojego klucza prywatnego DSA.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

Klucze publiczne DH i odpowiadające im podpisy są teraz rozgłaszane zarówno przez Alice, jak i Boba. Po otrzymaniu klucza publicznego i podpisu kontrahenta, każda ze stron weryfikuje, czy podpis jest ważny. W ten sposób można zapobiec atakowi MITM, ponieważ Alice na przykład wie, że klucz publiczny DH Boba został rzeczywiście podpisany przez Boba, i vice versa.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

Po weryfikacji podpisu Alice i Bob generują wspólny sekret, co kończy wymianę kluczy.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

Opcjonalnie, dla dodatkowego bezpieczeństwa, Alice i Bob mogą użyć specjalizowanej funkcji wyprowadzania klucza, takiej jak HKDF, aby wygenerować bardziej bezpieczny klucz symetryczny z ich wspólnego sekretu przy użyciu technik rozciągania klucza.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Łamanie Diffie-Hellmana i DSA

Zarówno protokoły Diffie-Hellmana (DH), jak i DSA polegają na generowaniu kluczy publicznych postaci $y = g^{x}~mod~p$, gdzie klucz prywatny $x$ jest logarytmem dyskretnym.

Atakujący, który jest w stanie rozwiązać instancję DLP, może ujawnić klucz prywatny jednej z dwóch stron i, łącząc go z kluczem publicznym drugiej strony, uzyskać dostęp do wspólnego sekretu. W przypadku DSA atakujący, który potrafi rozwiązać DLP, może odzyskać klucz prywatny osoby podpisującej, unieważniając podstawowe założenie podpisu cyfrowego.

W klasycznych systemach obliczeniowych uważa się, że DLP nie ma rozwiązania w czasie wielomianowym. Jednak, jak pokazał Peter Shor w swoim oryginalnym artykule z 1994 r., algorytm Shora rozwiązuje również DLP w czasie wielomianowym na komputerach kwantowych.

Algorytm Shora i problem logarytmu dyskretnego

Algorytm Shora potrafi rozwiązać problem logarytmu dyskretnego w czasie wielomianowym. Swoją wydajność osiąga głównie dzięki zastosowaniu algorytmów kwantowych, które potrafią znaleźć okres funkcji zależnej od danych wejściowych problemu — co jest następnie łączone z bardziej konwencjonalnymi operacjami.

Matematyczne szczegóły algorytmu Shora

Algorytm Shora dostarcza efektywnego rozwiązania DLP, odwzorowując go na bardziej ogólny problem w teorii grup znany jako problem ukrytej podgrupy (HSP).

W HSP dane są: grupa algebraiczna $G$ oraz funkcja $f: G \rightarrow X$ z $G$ do pewnego zbioru $X$, taka że $f$ jest stała na każdej warstwie pewnej podgrupy $H$ grupy $G$ (i różna na różnych warstwach). Zadaniem jest wyznaczenie $H$. Wiadomo, że komputery kwantowe potrafią rozwiązać HSP na skończonych grupach abelowych w czasie wielomianowym względem $log~|G|$, gdzie $|G|$ to rząd grupy.

W przypadku całkowitoliczbowego DLP omawianego w tej lekcji odwzorowanie na HSP jest następujące:

• Niech $p$ będzie liczbą pierwszą i rozważmy DLP dany przez $y = g^r~mod~p$, gdzie $g$ jest generatorem $(\mathbb{Z}_p)^{\times}$. Ponieważ $g^{p-1} \equiv 1~mod~p$, $g$ ma rząd $p-1$.
• Wybierzmy $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$, gdzie $\mathbb{Z}_{p-1}$ jest grupą liczb całkowitych modulo $(p-1)$.
• Wybierzmy $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ daną jako $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$ .
• Jądrem $f$ jest wówczas podgrupa $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$.
• $f$ jest stała na warstwach $(\delta, 0) + H_0$ i „ukrywa” podgrupę $H_0$, tworząc HSP.

Mając powyższe, kwantowy algorytm Shora dla całkowitoliczbowego DLP używa kwantowej wyroczni do obliczenia funkcji $f$ na stanie reprezentującym jednorodną superpozycję nad $G$, a następnie wykorzystuje kwantową transformatę Fouriera oraz pomiary z estymacją fazy, aby wytworzyć stany kwantowe pozwalające na identyfikację generatora $(r, 1)$ podgrupy $H_0$. Z tego można wydobyć $r$ — interesujący nas logarytm dyskretny.

Oryginalna praca Shora zawiera szczegółowy opis algorytmu.

Kryptografia krzywych eliptycznych

Kryptografia krzywych eliptycznych (ECC), oparta na matematyce krzywych eliptycznych, oferuje potężne podejście do kryptografii z kluczem asymetrycznym. Wiadomo, że ECC zapewnia podobny poziom bezpieczeństwa jak metody takie jak RSA, ale z krótszymi kluczami, co czyni ją bardziej wydajną i szczególnie odpowiednią dla systemów o ograniczonych zasobach, takich jak systemy wbudowane i urządzenia mobilne, gdzie oszczędności w zakresie przechowywania i obliczeń wynikające z mniejszych rozmiarów kluczy są wysoce pożądane.

Podstawowe zasady kryptografii krzywych eliptycznych

Krzywa eliptyczna zazwyczaj ma postać $y^2 = x^3 + ax + b$ i posiada kilka interesujących właściwości.

• Jest symetryczna w poziomie. Zatem dla dowolnego punktu $(x,y)$ na krzywej jego odbicie $(x,-y)$ również znajduje się na krzywej.
• Dowolna niepionowa linia prosta przetnie krzywą w co najwyżej trzech punktach.

Rysunek 1. Operacje dodawania i podwajania punktu na krzywej eliptycznej. Aspekt 1 definiuje P + Q = -R. Aspekt 2 ilustruje podwajanie punktu 2Q = -P. Aspekt 3 definiuje odwrotność addytywną punktu jako jego odbicie względem osi x, tj. P = -Q

Kryptografia krzywych eliptycznych wykorzystuje stosowanie serii operacji arytmetycznych na punktach krzywej. Każda z nich efektywnie prowadzi do nowego punktu na krzywej. Jest to prosty proces do wykonania w jednym kierunku, a przy krótszych rozmiarach kluczy jest bardziej wydajny niż inne algorytmy takie jak RSA, ale próba odwrócenia tego procesu jest bardzo trudna, stąd jego zastosowanie w kryptografii.

Zasady matematyczne kryptografii krzywych eliptycznych

Krzywa eliptyczna nad ciałem algebraicznym $K$ jest zdefiniowana równaniem matematycznym, zazwyczaj w postaci $y^2 = x^3 + ax + b$ ze współczynnikami $a, b \in K$ i opisuje punkty $(x, y) \in K \otimes K$ z dodatkowym wymogiem, aby krzywa nie miała załamań ani samoprzecięć.

Właściwości krzywych eliptycznych pozwalają na zdefiniowanie operacji „dodawania” i „mnożenia przez skalar” dotyczących punktów na krzywej.

Dodawanie: Jeśli $P$ i $Q$ są dwoma punktami na krzywej eliptycznej, to $P + Q$ opisuje unikalny trzeci punkt zidentyfikowany w następujący sposób: Rysujemy linię przechodzącą przez $P$ i $Q$ i znajdujemy trzeci punkt $R$, w którym linia ponownie przecina krzywą. Definiujemy wówczas $P + Q = −R$, punkt przeciwny do $R$ odbity względem osi $x$ (patrz rysunek poniżej). Gdy linia przechodząca przez $P, Q$ nie przecina krzywej w żadnym skończonym $(x, y)$, mówimy, że przecina ona krzywą w punkcie w nieskończoności $\mathbf{O}$.

Dodawanie krzywej eliptycznej spełnia algebraiczne właściwości grupy, przy czym punkt w nieskończoności jest elementem neutralnym dodawania.

Podwajanie i mnożenie przez skalar: Operacja podwajania punktu, która odpowiada mnożeniu przez skalar $2$, jest uzyskiwana przez ustawienie $P = Q$ w operacji dodawania i graficznie polega na stycznej w punkcie $P$. Ogólne mnożenie przez skalar przez liczbę całkowitą $n$ zdefiniowane jako $nP = P + P + ...~n$ razy, jest uzyskiwane przez wielokrotne podwajanie i dodawanie.

Problem logarytmu dyskretnego krzywej eliptycznej

Problem logarytmu dyskretnego krzywej eliptycznej (ECDLP) ma wiele podobieństw do omawianego wcześniej problemu logarytmu dyskretnego, będąc opartym o trudności znajdowania czynników.

Operacja mnożenia przez skalar na krzywych eliptycznych pozwala na zdefiniowanie problemu logarytmu dyskretnego krzywej eliptycznej:

Mając dane punkty $P, Q$ na krzywej eliptycznej takie, że $Q = nP$, wyznacz $n$.

Wiadomo, że problem ten jest nierozwiązywalny na klasycznych komputerach dla dużych $n$ i stanowi podstawę bezpieczeństwa kryptograficznego.

Matematyczny opis ECDLP

Kryptografia krzywych eliptycznych opiera się głównie na ECDLP sformułowanym na pewnych algebraicznych ciałach skończonych. W 1999 roku NIST rekomendował dziesięć ciał skończonych do użycia w ECC. Są to:

• Pięć ciał prostych $\mathbb {F} _{p}$ dla liczb pierwszych $p$ o rozmiarze $\{192, 224, 256, 384, 521\}$ bitów.
• Pięć ciał binarnych $\mathbb {F} _{2^{n}}$ dla $n \in \{163, 233, 283, 409, 571\}$.

Przy powyższej konfiguracji, oparty na ECC system kryptograficzny z kluczem asymetrycznym w przypadku ciał prostych może być określony następująco:

• Wybierz $p$ z listy wartości rekomendowanych przez NIST, aby określić $\mathbb {F} _{p}$.

• Wybierz parametry $a, b$ krzywej eliptycznej.

• Wybierz punkt bazowy $G$, który „generuje” cykliczną podgrupę na krzywej rzędu $n$; to znaczy najmniejszą liczbę całkowitą taką, że $nG = \mathbf{O}$.

• Oblicz kofaktor $h = |E(\mathbb {F} _{p})|/n$, gdzie $|E(\mathbb {F} _{p})|$ to liczba punktów na krzywej. $h$ jest zazwyczaj małą liczbą całkowitą.

• Parametry dziedziny $(p, a, b, G, n, h)$ pozwalają na specyfikację kluczy asymetrycznych w ten sposób:

  • Klucz prywatny to losowo wybrana liczba całkowita $d$ o tylu bitach, ile ma liczba pierwsza $p$. Powinien być utrzymywany w tajemnicy.
  • Klucz publiczny jest wynikiem „pomnożenia” punktu bazowego $G$ przez klucz prywatny $d$. Jest to zazwyczaj oznaczane jako $Q = dG$.

Odzyskanie $d$ jest równoważne rozwiązaniu ECDLP, co uważa się za nierozwiązywalne dla dużych $d$. ECDLP stanowi więc podstawę schematów wymiany kluczy i podpisu cyfrowego w bezpośredniej analogii do schematów Diffiego-Hellmana i DSA zdefiniowanych nad $(\mathbb{Z}_p)^{\times}$, omówionych wcześniej.

Wymiana kluczy z użyciem ECC

Jednym z głównych zastosowań ECC jest protokół wymiany kluczy znany jako Diffie-Hellman krzywych eliptycznych (ECDH). W ECDH każda ze stron generuje parę kluczy prywatny-publiczny, a następnie wymienia klucze publiczne. Każda strona używa wówczas swojego klucza prywatnego oraz klucza publicznego drugiej strony do obliczenia wspólnego sekretu, który może być użyty jako klucz do szyfrowania symetrycznego.

Podczas gdy stosunkowo łatwo jest wykonać dodawanie punktów na krzywej eliptycznej i wyprowadzić klucz publiczny z klucza prywatnego, obliczeniowo niewykonalne jest odwrócenie procesu i wyprowadzenie klucza prywatnego z klucza publicznego. Takie „jednokierunkowe” zachowanie zapewnia bezpieczeństwo wymiany kluczy ECDH.

Poniżej zilustrujemy przykład, jak można przeprowadzić wymianę kluczy ECDH używając Pythona i biblioteki cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Podpisy cyfrowe z użyciem ECC

ECC może być również używany do generowania podpisów cyfrowych za pomocą Algorytmu podpisu cyfrowego krzywej eliptycznej (ECDSA). W ECDSA podpisujący tworzy podpis przy użyciu swojego klucza prywatnego, a inni mogą zweryfikować podpis przy użyciu klucza publicznego podpisującego. Podobnie jak w przypadku ECDH, bezpieczeństwo ECDSA opiera się na ECDLP. Obliczeniowo niewykonalne jest dla kogokolwiek sfałszowanie podpisu bez dostępu do klucza prywatnego podpisującego.

Poniżej znajduje się przykład prostej transakcji podpisania i weryfikacji przy użyciu ECDSA z Pythonem i biblioteką cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

W powyższym kodzie, jeśli zmodyfikujemy wiadomość po jej podpisaniu, weryfikacja zakończy się niepowodzeniem, dając gwarancję autentyczności i integralności wiadomości.

Łamanie ECDH i ECDSA

Analogicznie do całkowitoliczbowego problemu logarytmu dyskretnego, ECDLP okazuje się być trudnym na klasycznych komputerach, ale posiada wydajne rozwiązanie na komputerach kwantowych — ponownie za pomocą algorytmu Shora. Odsyłamy do najnowszej literatury w celu zapoznania się z dyskusją związaną z uogólnieniem algorytmu Shora na przypadek ECDLP.

Podsumowanie

W tej lekcji zaczęliśmy od przyjrzenia się głównym cechom kryptografii z kluczem asymetrycznym (AKC) i omówiliśmy podstawowe aspekty bezpieczeństwa, które stanowią podstawę asymetrycznych systemów kryptograficznych. W szczególności wprowadziliśmy dwa główne zastosowania AKC — a mianowicie wymianę kluczy i podpisy cyfrowe — z których oba są niezbędnymi komponentami nowoczesnej komunikacji opartej na internecie.

Następnie przyjrzeliśmy się systemowi kryptograficznemu RSA, który od lat 70. XX wieku okazał się mieć ogromną wartość dla zabezpieczania nowoczesnej komunikacji cyfrowej, umożliwiając wymianę kluczy i podpisy cyfrowe w prostych i wszechstronnych ramach. Bezpieczeństwo kryptograficzne RSA w odniesieniu do obliczeń klasycznych opiera się na trudności faktoryzacji dużych liczb całkowitych i wymaga rozmiarów kluczy w zakresie 2048 bitów, aby zapewnić, że liczby całkowite używane w praktycznych zastosowaniach są wystarczająco duże, aby oprzeć się faktoryzacji.

Następnie przyjrzeliśmy się wymianie kluczy Diffiego-Hellmana (DH) i Algorytmowi podpisu cyfrowego (DSA). Bezpieczeństwo tych schematów opiera się na problemie całkowitoliczbowego logarytmu dyskretnego (DLP), przy czym klucz prywatny jest trudny do wydobycia obliczeniowo mając klucz publiczny, bez rozwiązania w czasie wielomianowym na klasycznych komputerach. Użycie losowych i unikalnych kluczy zapewnia dodatkowe bezpieczeństwo przed atakami. Zarówno całkowitoliczbowe warianty ciał skończonych, jak i warianty krzywych eliptycznych protokołów DH i DSA znajdują obecnie szerokie zastosowanie w wielu nowoczesnych protokołach komunikacji cyfrowej, takich jak TLS, SSH i tak dalej.

Na koniec przyjrzeliśmy się kryptografii krzywych eliptycznych. Ze swoim efektywnym rozmiarem klucza i silnymi właściwościami bezpieczeństwa, stanowi ona obecnie doskonały wybór dla wielu zastosowań kryptograficznych, od wymiany kluczy po podpisy cyfrowe.

Wszystkie te algorytmy są narażone na atak ze strony algorytmów kwantowych, ponieważ można opracować rozwiązania, aby rozwiązać problemy matematyczne, które stanowiły założenie w ich projekcie. Jednym z takich przykładów jest algorytm Shora. Dlatego będą musiały zostać zastąpione kwantowo-bezpiecznymi asymetrycznymi systemami kryptograficznymi, które są bardziej odporne na ataki kwantowe — a jednocześnie tak samo bezpieczne w stosunku do algorytmów klasycznych. Problemy matematyczne, na których się opierają, mogą być efektywnie rozwiązywane przez komputery kwantowe, co wymusza rozwój kwantowo-bezpiecznych asymetrycznych systemów kryptograficznych, które mogą wytrzymać ataki kwantowe, zachowując jednocześnie bezpieczeństwo klasyczne.

Przyszła lekcja będzie dotyczyć kwantowo-bezpiecznych systemów kryptograficznych i omówi wymagane podejście do utrzymania bezpieczeństwa kryptograficznego.