Szyfrowanie klucza publicznego

Kryptografia klucza publicznego

W przeciwieństwie do kryptografii klucza symetrycznego, nie znajdujemy historycznego zastosowania kryptografii klucza publicznego. To stosunkowo nowa koncepcja.

Kryptografia symetryczna była dobrze dostosowana do organizacji takich jak rządy, wojsko i duże korporacje finansowe, które były zaangażowane w tajną komunikację.

Wraz z rozprzestrzenianiem się bardziej niezabezpieczonych sieci komputerowych w ciągu ostatnich kilku dziesięcioleci, pojawiła się prawdziwa potrzeba wykorzystania kryptografii na większą skalę. Stwierdzono, że klucz symetryczny jest niepraktyczny ze względu na wyzwania, przed którymi stanął przy zarządzaniu kluczami. Doprowadziło to do powstania kryptosystemów klucza publicznego.

Na poniższej ilustracji przedstawiono proces szyfrowania i deszyfrowania -

Najważniejsze właściwości schematu szyfrowania klucza publicznego to -

Do szyfrowania i deszyfrowania używane są różne klucze. Jest to właściwość, która ustawia ten schemat inaczej niż schemat szyfrowania symetrycznego.
Każdy odbiorca posiada unikalny klucz odszyfrowywania, ogólnie nazywany jego kluczem prywatnym.
Odbiorca musi opublikować klucz szyfrujący, nazywany jego kluczem publicznym.
W tym schemacie potrzebne jest pewne zapewnienie autentyczności klucza publicznego, aby uniknąć fałszowania przez przeciwnika jako odbiorcę. Ogólnie rzecz biorąc, ten typ kryptosystemu obejmuje zaufaną stronę trzecią, która zaświadcza, że określony klucz publiczny należy tylko do określonej osoby lub podmiotu.
Algorytm szyfrowania jest na tyle złożony, że uniemożliwi atakującemu wyprowadzenie tekstu jawnego z tekstu zaszyfrowanego i klucza szyfrowania (publicznego).
Chociaż klucze prywatny i publiczny są powiązane matematycznie, obliczenie klucza prywatnego na podstawie klucza publicznego nie jest możliwe. W rzeczywistości inteligentną częścią każdego kryptosystemu klucza publicznego jest projektowanie relacji między dwoma kluczami.

Istnieją trzy typy schematów szyfrowania kluczy publicznych. Omawiamy je w następujących sekcjach -

RSA Cryptosystem

Ten kryptosystem jest jednym z pierwszych systemów. Do dziś pozostaje najczęściej wykorzystywanym kryptosystemem. System został wymyślony przez trzech uczonychRon Rivest, Adi Shamir, i Len Adleman i dlatego jest określany jako kryptosystem RSA.

Zobaczymy dwa aspekty kryptosystemu RSA, po pierwsze generowanie pary kluczy, a po drugie algorytmy szyfrowania i deszyfrowania.

Generowanie pary kluczy RSA

Każda osoba lub strona, która chce uczestniczyć w komunikacji za pomocą szyfrowania, musi wygenerować parę kluczy, a mianowicie klucz publiczny i klucz prywatny. Proces generowania kluczy opisano poniżej -

Generate the RSA modulus (n)
- Wybierz dwie duże liczby pierwsze, p i q.
- Oblicz n = p * q. Dla silnego, niemożliwego do złamania szyfrowania, niech n będzie dużą liczbą, zwykle minimum 512 bitów.
Find Derived Number (e)
- Numer e musi być większe niż 1 i mniejsze niż (p - 1) (q - 1).
- Nie może być żadnego wspólnego dzielnika dla e i (p - 1) (q - 1) z wyjątkiem 1. Innymi słowy, dwie liczby e i (p - 1) (q - 1) są względnie pierwsze.
Form the public key
- Para liczb (n, e) tworzy klucz publiczny RSA i jest upubliczniana.
- Co ciekawe, chociaż n jest częścią klucza publicznego, trudność w rozkładaniu na czynniki dużej liczby pierwszej zapewnia, że atakujący nie może znaleźć w skończonym czasie dwóch liczb pierwszych (p & q) użytych do uzyskania n. To jest siła RSA.
Generate the private key
- Klucz prywatny d jest obliczany na podstawie p, q i e. Dla danych n i e istnieje niepowtarzalna liczba d.
- Liczba d jest odwrotnością e modulo (p - 1) (q - 1). Oznacza to, że d jest liczbą mniejszą niż (p - 1) (q - 1) taką, że po pomnożeniu przez e jest równa 1 modulo (p - 1) (q - 1).
- Ta zależność jest zapisana matematycznie w następujący sposób -

ed = 1 mod (p − 1)(q − 1)

Rozszerzony algorytm euklidesowy przyjmuje p, q i e jako dane wejściowe i daje d jako wyjście.

Przykład

Przykład generowania pary kluczy RSA podano poniżej. (Dla ułatwienia zrozumienia liczby pierwsze p i q są tu małymi wartościami. W praktyce wartości te są bardzo wysokie).

Niech dwie liczby pierwsze będą p = 7 i q = 13. Zatem moduł n = pq = 7 x 13 = 91.
Wybierz e = 5, co jest prawidłowym wyborem, ponieważ nie ma liczby, która jest wspólnym dzielnikiem 5 i (p - 1) (q - 1) = 6 × 12 = 72, z wyjątkiem 1.
Para liczb (n, e) = (91, 5) tworzy klucz publiczny i może być udostępniona każdemu, komu chcemy, aby wysyłał nam zaszyfrowane wiadomości.
Wprowadź p = 7, q = 13 ie = 5 do rozszerzonego algorytmu euklidesowego. Wynik wyniesie d = 29.
Sprawdź, czy obliczone d jest poprawne, obliczając -

de = 29 × 5 = 145 = 1 mod 72

Stąd klucz publiczny to (91, 5), a klucz prywatny to (91, 29).

Szyfrowanie i deszyfrowanie

Po wygenerowaniu pary kluczy proces szyfrowania i deszyfrowania jest stosunkowo prosty i łatwy obliczeniowo.

Co ciekawe, RSA nie działa bezpośrednio na łańcuchach bitów, jak w przypadku szyfrowania z kluczem symetrycznym. Działa na liczbach modulo n. Dlatego konieczne jest przedstawienie tekstu jawnego jako serii liczb mniejszych niż n.

Szyfrowanie RSA

Załóżmy, że nadawca chce wysłać wiadomość tekstową do osoby, której klucz publiczny to (n, e).
Nadawca następnie przedstawia tekst jawny jako ciąg liczb mniejszych niż n.
Aby zaszyfrować pierwszy tekst jawny P, który jest liczbą modulo n. Proces szyfrowania jest prostym krokiem matematycznym, ponieważ -

C = P^e mod n

Innymi słowy, zaszyfrowany tekst C jest równy tekstowi jawnemu P pomnożonemu przez siebie e razy, a następnie zredukowanemu modulo n. Oznacza to, że C jest również liczbą mniejszą niż n.
Wracając do naszego przykładu generowania klucza z tekstem jawnym P = 10, otrzymujemy tekst zaszyfrowany C -

C = 10⁵ mod 91

Deszyfrowanie RSA

Proces deszyfrowania RSA jest również bardzo prosty. Załóżmy, że odbiorca pary kluczy publicznych (n, e) otrzymał zaszyfrowany tekst C.
Odbiorca podnosi C do potęgi swojego klucza prywatnego d. Wynik modulo n będzie tekstem jawnym P.

Plaintext = C^d mod n

Wracając do naszego przykładu liczbowego, zaszyfrowany tekst C = 82 zostałby odszyfrowany do numeru 10 przy użyciu klucza prywatnego 29 -

Plaintext = 82²⁹ mod 91 = 10

Analiza RSA

Bezpieczeństwo RSA zależy od mocnych stron dwóch oddzielnych funkcji. Kryptosystem RSA jest najpopularniejszym kryptosystemem z kluczem publicznym, którego siła opiera się na praktycznej trudności z fakturowaniem bardzo dużych liczb.

Encryption Function - Jest traktowana jako jednokierunkowa funkcja konwersji tekstu jawnego na tekst zaszyfrowany i może zostać odwrócona tylko przy znajomości klucza prywatnego d.
Key Generation- Trudność w określeniu klucza prywatnego na podstawie klucza publicznego RSA jest równoważna faktoryzacji modułu n. Dlatego osoba atakująca nie może wykorzystać wiedzy o kluczu publicznym RSA do określenia klucza prywatnego RSA, chyba że może uwzględnić n. Jest to również funkcja jednokierunkowa, przechodzenie od wartości p & q do modułu n jest łatwe, ale odwrócenie nie jest możliwe.

Jeśli okaże się, że którakolwiek z tych dwóch funkcji nie jest jednokierunkowa, RSA zostanie przerwane. W rzeczywistości, jeśli technika efektywnego faktoringu zostanie opracowana, RSA nie będzie już bezpieczne.

Siła szyfrowania RSA drastycznie spada w przypadku ataków, jeśli liczby p i q nie są dużymi liczbami pierwszymi i / lub wybrany klucz publiczny e jest małą liczbą.

ElGamal Cryptosystem

Wraz z RSA proponowane są inne kryptosystemy klucza publicznego. Wiele z nich opiera się na różnych wersjach problemu logarytmu dyskretnego.

Kryptosystem ElGamal, zwany wariantem krzywej eliptycznej, jest oparty na problemie logarytmu dyskretnego. Wywodzi się z założenia, że dyskretnych logarytmów nie można znaleźć w praktycznych ramach czasowych dla danej liczby, podczas gdy odwrotne działanie mocy można obliczyć efektywnie.

Przejdźmy przez prostą wersję ElGamala, która działa z liczbami modulo p. W przypadku wariantów krzywych eliptycznych opiera się na zupełnie innych układach liczbowych.

Generacja pary kluczy ElGamal

Każdy użytkownik kryptosystemu ElGamal generuje parę kluczy w następujący sposób -

Choosing a large prime p. Generalnie wybierana jest liczba pierwsza o długości od 1024 do 2048 bitów.
Choosing a generator element g.
- Ta liczba musi mieścić się w przedziale od 1 do p - 1, ale nie może być dowolną liczbą.
- Jest to generator multiplikatywnej grupy liczb całkowitych modulo p. Oznacza to, że dla każdej liczby całkowitej m będącej liczbą pierwszą do p, istnieje liczba całkowita k taka, że g ^k = a mod n.
  
  Na przykład 3 jest generatorem grupy 5 (Z ₅ = {1, 2, 3, 4}).

N	3 ⁿ	3 ⁿ mod 5
1	3	3
2	9	4
3	27	2
4	81	1

Choosing the private key. Klucz prywatny x to dowolna liczba większa niż 1 i mniejsza niż p − 1.
Computing part of the public key. Wartość y jest obliczana na podstawie parametrów p, g i klucza prywatnego x w następujący sposób -

y = g^x mod p

Obtaining Public key. Klucz publiczny ElGamal składa się z trzech parametrów (p, g, y).

Na przykład załóżmy, że p = 17 i że g = 6 (można potwierdzić, że 6 jest generatorem grupy Z ₁₇ ). Klucz prywatny x może być dowolną liczbą większą niż 1 i mniejszą niż 71, więc wybieramy x = 5. Wartość y jest następnie obliczana w następujący sposób -

y = 6⁵ mod 17 = 7

Zatem klucz prywatny to 62, a klucz publiczny to (17, 6, 7).

Szyfrowanie i deszyfrowanie

Generowanie pary kluczy ElGamal jest stosunkowo prostsze niż równoważny proces dla RSA. Ale szyfrowanie i deszyfrowanie są nieco bardziej złożone niż RSA.

Szyfrowanie ElGamal

Załóżmy, że nadawca chce wysłać zwykły tekst do osoby, której klucz publiczny ElGamal to (p, g, y), a następnie -

Nadawca przedstawia tekst jawny jako ciąg liczb modulo p.
Aby zaszyfrować pierwszy tekst jawny P, który jest reprezentowany jako liczba modulo p. Proces szyfrowania w celu uzyskania tekstu zaszyfrowanego C jest następujący:
- Losowo wygeneruj liczbę k;
- Oblicz dwie wartości C1 i C2, gdzie -

C1 = g^k mod p
C2 = (P^*y^k) mod p

Wyślij szyfrogram C składający się z dwóch oddzielnych wartości (C1, C2), przesłanych razem.
Odnosząc się do naszego przykładu generowania klucza ElGamal podanego powyżej, tekst jawny P = 13 jest szyfrowany w następujący sposób -
- Wygeneruj losowo liczbę, powiedzmy k = 10
- Oblicz dwie wartości C1 i C2, gdzie -

C1 = 6¹⁰ mod 17
C2 = (13^*7¹⁰) mod 17 = 9

Wyślij szyfrogram C = (C1, C2) = (15, 9).

Deszyfrowanie ElGamal

Aby odszyfrować zaszyfrowany tekst (C1, C2) za pomocą klucza prywatnego x, należy wykonać następujące dwa kroki -
- Oblicz modularną odwrotność (C1) ^x modulo p, która wynosi (C1) ^-x , ogólnie określaną jako współczynnik deszyfrowania.
- Uzyskaj tekst jawny, korzystając z następującego wzoru -

C2 × (C1)^-x mod p = Plaintext

W naszym przykładzie, aby odszyfrować zaszyfrowany tekst C = (C1, C2) = (15, 9) za pomocą klucza prywatnego x = 5, współczynnik deszyfrowania wynosi

15^-5 mod 17 = 9

Wyodrębnij tekst jawny P = (9 × 9) mod 17 = 13.

Analiza ElGamala

W systemie ElGamal każdy użytkownik ma klucz prywatny x. i mathree components klucza publicznego - prime modulus p, generator g, and public Y = g^x mod p. Siła ElGamala opiera się na trudności zadania z logarytmem dyskretnym.

Rozmiar bezpiecznego klucza to zazwyczaj> 1024 bity. Obecnie używany jest nawet klucz o długości 2048 bitów. Pod względem szybkości przetwarzania Elgamal jest dość powolny, jest używany głównie w protokołach uwierzytelniania kluczy. Ze względu na wyższą wydajność przetwarzania, warianty ElGamal z krzywą eliptyczną stają się coraz bardziej popularne.

Kryptografia krzywych eliptycznych (ECC)

Kryptografia krzywych eliptycznych (ECC) to termin używany do opisania zestawu narzędzi i protokołów kryptograficznych, których bezpieczeństwo opiera się na specjalnych wersjach problemu logarytmu dyskretnego. Nie używa liczb modulo p.

ECC opiera się na zbiorach liczb, które są powiązane z obiektami matematycznymi zwanymi krzywymi eliptycznymi. Istnieją reguły dotyczące dodawania i obliczania wielokrotności tych liczb, tak jak istnieją dla liczb modulo p.

ECC zawiera warianty wielu schematów kryptograficznych, które zostały początkowo zaprojektowane dla liczb modularnych, takich jak szyfrowanie ElGamal i algorytm podpisu cyfrowego.

Uważa się, że problem logarytmu dyskretnego jest znacznie trudniejszy, gdy zostanie zastosowany do punktów na krzywej eliptycznej. To powoduje przejście z liczb modulo p do punktów na krzywej eliptycznej. Równoważny poziom bezpieczeństwa można również uzyskać przy krótszych kluczach, jeśli używamy wariantów opartych na krzywej eliptycznej.

Krótsze klucze dają dwie korzyści -

Łatwość zarządzania kluczami
Wydajne obliczenia

Korzyści te sprawiają, że warianty schematu szyfrowania oparte na krzywej eliptycznej są bardzo atrakcyjne dla aplikacji, w których zasoby obliczeniowe są ograniczone.

Schematy RSA i ElGamal - porównanie

Porównajmy pokrótce schematy RSA i ElGamala w różnych aspektach.

RSA	ElGamal
Szyfrowanie jest bardziej wydajne.	Jest to bardziej wydajne do odszyfrowania.
Jest mniej wydajna przy odszyfrowywaniu.	Jest to bardziej wydajne do odszyfrowania.
W przypadku określonego poziomu bezpieczeństwa w RSA wymagane są długie klucze.	Aby uzyskać ten sam poziom bezpieczeństwa, potrzebne są bardzo krótkie klucze.
Jest szeroko akceptowany i używany.	Jest nowy i niezbyt popularny na rynku.