RSA, czy to naprawdę takie proste? Przykład algorytmu szyfrowania rsa Algorytm szyfrowania rsa 1024.

RSA używa dwóch typów kluczy - e i d, gdzie e jest publiczne, a d jest tajne. Załóżmy, że P jest tekstem jawnym, a C jest tekstem zaszyfrowanym. Alicja używa C = P e mod n do utworzenia tekstu zaszyfrowanego C z tekstu jawnego P; Bob używa P = C d mod n do pobrania tekstu źródłowego (pliku) przesłanego przez Alicję. Bardzo duża liczba n modułów jest tworzona przy użyciu procesu generowania klucza, który omówimy później.

Do szyfrowania i deszyfrowania stosuje się potęgowanie modulo. Jak omawialiśmy w wykładach 12-13, przy użyciu szybkiego algorytmu potęgowanie modulo jest możliwe w czasie wielomianowym. Jednak znalezienie logarytmu modułowego jest tak samo trudne, jak rozłożenie liczby modulo. Nie ma dla tego algorytmu czasu wielomianowego. Oznacza to, że Alicja może zaszyfrować wiadomość kluczem publicznym (e) w czasie wielomianowym. Bob może go także odszyfrować w czasie wielomianowym (ponieważ zna d). Jednak Ewa nie może rozszyfrować tej wiadomości, ponieważ musiałaby obliczyć pierwiastek e z C, stosując arytmetykę modułową. Rysunek 14.5 przedstawia ideę RSA.

Ryż. 14,5.

Innymi słowy, Alicja używa funkcja jednokierunkowa(potęgowanie modulo) z luką znaną tylko Bobowi. Ewa nie zna luki, więc nie może rozszyfrować przesłania. Jeśli kiedykolwiek znajdą algorytm wielomianowy dla modułu obliczania e-tego pierwiastka z n, to potęgowanie modulo n nie będzie już funkcją jednokierunkową.

Procedura

Rysunek 14.6 pokazuje ogólną ideę procedury stosowanej w RSA.

RSA wykorzystuje potęgowanie modulo do szyfrowania/deszyfrowania. Aby zaatakować prywatny tekst, Ewa musi dokonać kalkulacji

Ryż. 14.6.

Dwie struktury algebraiczne

RSA wykorzystuje dwie struktury algebraiczne: pierścień i grupę.

Pierścienie szyfrujące/deszyfrujące. Szyfrowanie i deszyfrowanie odbywa się za pomocą pierścienia przemiennego z dwoma operacjami arytmetycznymi: dodawaniem i mnożeniem. W RSA ten pierścień jest publiczny, ponieważ moduł n jest publiczny. Każdy może wysłać wiadomość do Boba, korzystając z tego pierścienia szyfrującego.

Grupy generowania kluczy. RSA używa grupy multiplikatywnej do generowania kluczy. Grupa obsługuje wyłącznie mnożenie i dzielenie (inwersja multiplikatywna), które są niezbędne do tworzenia kluczy publicznych i prywatnych. Ta grupa musi być ukryta, ponieważ jej moduł jest tajny. Zobaczymy, że jeśli Eve odnajdzie ten moduł, będzie mogła z łatwością zaatakować system kryptograficzny.

RSA wykorzystuje dwie struktury algebraiczne: otwarty pierścień R =< Z N , +, x > i tajna grupa G =< Z (N)* , x >.

Generacja klucza

Bob wykonuje kroki pokazane w algorytmie 14.2, aby utworzyć swoje klucze publiczne i prywatne. Po wygenerowaniu kluczy Bob deklaruje krotkę (e, n) jako swój publiczny klucz dostępu: Bob przechowuje d jako swój klucz prywatny. Bob może zrezygnować z p, q i ; nie mogą zmienić jego tajnego klucza bez zmiany modułu. Ze względów bezpieczeństwa zalecany rozmiar każdej liczby pierwszej p lub q wynosi 512 bitów (prawie 154 cyfry dziesiętne). Określa to rozmiar modułu, n 1024 bitów (309 cyfr).

14.2. Generowanie klucza RSA

W RSA krotka (e, n) jest publicznym kluczem dostępu; liczba całkowita d - tajny klucz.

Szyfrowanie

Każdy może wysłać wiadomość do Boba, używając jego publicznego klucza dostępu. Szyfrowanie w RSA można wykonać za pomocą algorytmu o wielomianowej złożoności czasowej, jak pokazano w Algorytm 14.3. Szybki algorytm potęgowania był omawiany w wykładach 12-13. Rozmiar tekstu źródłowego musi być mniejszy niż n ; jeżeli rozmiar tekstu źródłowego jest większy, należy go podzielić na bloki.

Rozważmy działanie asymetryczności RSA . Zostało zaproponowane przez trzech matematyków Ronalda Rivesta ( R.Rivest), Adi Shamir ( A. Szamir) i Leonarda Adlemana ( L. Adlemana) w 1978 r.

Pod Liczba pierwsza Rozumiemy liczbę, która dzieli się tylko przez 1 i samą siebie. Euklides w swoich Elementach pokazał, że dla każdej liczby pierwszej istnieje większa liczba pierwsza, to znaczy liczba liczb pierwszych jest nieskończona.

Dowód. Załóżmy, że istnieje największa liczba pierwsza P, definiujemy iloczyn wszystkich liczb pierwszych P=2∙3∙5∙7∙…∙P.

Rozważ liczbę P+1. Albo sama jest dużą liczbą pierwszą P lub iloczyn liczb pierwszych, które są większe P. Doszliśmy do sprzeczności, co oznacza, że liczba liczb pierwszych jest nieskończona.

2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;

2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.

Wzajemnie liczby pierwsze będziemy nazywać liczby, które nie mają ani jednego wspólnego dzielnika, z wyjątkiem 1 .

Wreszcie pod wynikiem operacji moduję j obliczymy resztę z dzielenia liczb całkowitych I NA J. Aby skorzystać z algorytmu RSA, należy najpierw wygenerować klucz publiczny i prywatny, wykonując poniższe kroki.

1. Wybierz dwie bardzo duże liczby pierwsze R I Q.

2. Zdefiniujmy N w wyniku mnożenia R NA q (n=p·q).

3. Wybierzmy dużą liczbę losową, którą wywołamy D. Liczba ta musi być względnie pierwsza do wyniku mnożenia (p – 1) · (q – 1).

4. Zdefiniujmy taką liczbę mi, dla którego prawdziwa jest następująca zależność (e d) mod ((p – 1) (q – 1)) = 1.

5. Zadzwońmy pod numery kluczy publicznych mi I N, a tajnym kluczem są liczby D I N.

Teraz, aby zaszyfrować dane przy użyciu znanego klucza ( e, rz), musisz wykonać następujące czynności:

– podziel zaszyfrowany tekst na bloki, z których każdy można przedstawić jako liczbę Mi);

– szyfruj tekst traktowany jako ciąg liczb Mi) według formuły С(i) = (M(i) e) mod n. Aby odszyfrować te dane za pomocą tajnego klucza (d, n), musisz wykonać następujące obliczenia: M(i)=(C(i) d) mod n. Rezultatem będzie wiele liczb Mi), które reprezentują tekst źródłowy.

Algorytm RSA opiera się na jednym ze sprawdzonych twierdzeń Eulera, którego szczególny przypadek stwierdza, że jeśli liczba N można przedstawić w postaci dwóch liczb pierwszych P I Q, to dla dowolnego X jest równość

x (p-1)(q-1) mod n = 1.

Aby odszyfrować wiadomości RSA, użyjemy tej formuły. Aby to zrobić, podnosimy obie jego części do potęgi (- y):

(x (- y)(p-1)(q-1)) mod n= 1 (- y) = 1.

Teraz pomnóżmy obie strony przez x:

(x (-y)(p-1)(q-1)+1) mod n = 1· x = x.

Przypomnijmy sobie teraz, jak powstały klucze publiczny i prywatny. Wybraliśmy D takie, że

e d+(p-1)(q-1) y = 1,

e·d = (-y)(p-1)(q-1)+1.

Dlatego w ostatnim wyrażeniu poprzedniego akapitu możemy zastąpić wykładnik liczbą (red.). Dostajemy (x e d) mod n = x. Aby przeczytać wiadomość do ja = ((m i) e)mod n wystarczy podnieść to do potęgi D modulo M:

((c i) d)mod n = ((m i) mi · d) mod n = m ja .

Oto prosty przykład użycia metody RSA do zaszyfrowania wiadomości „CAB”. Dla uproszczenia będziemy używać bardzo małych liczb (w praktyce stosuje się duże liczby).

1. Wybierzmy p= 3i q= 11.

2. Zdefiniujmy n= 3· 11=33.

3. Znajdźmy (p–1) (q–1)= 20. Jako D wybierz na przykład dowolną liczbę względnie pierwszą do 20 d= 3.

4. Wybierz numer mi. Za taką liczbę można przyjąć dowolną liczbę, dla której relacja jest spełniona (mi· 3) mod 20 = 1,
na przykład 7.

5. Wyobraź sobie zaszyfrowaną wiadomość jako ciąg liczb całkowitych z zakresu 0...32. Niech list A reprezentowany przez cyfrę 1, literę W– cyfra 2 i litera Z– cyfrę 3. Wtedy wiadomość można przedstawić jako ciąg liczb 312. Zaszyfrujmy wiadomość za pomocą klucza (7, 33):

С(1)=(З 7) mod 33 = 2187 mod 33 = 9,

С(2) = (1 7) mod 33 = 1 mod 33 = 1,

C(Z) = (2 7) mod 33 = 128 mod 33 = 29.

6. Spróbujmy odszyfrować wiadomość (9, 1, 29), otrzymaną w wyniku szyfrowania znanym kluczem, w oparciu o tajny klucz (3, 33):

M(1) = (9 3) mod 33 = 729 mod 33 = 3,

M(2) = (1 3) mod 33 = 1 mod 33 = 1,

M(Z) = (29 3) mod 33 = 24389 mod 33 = 2.

Zatem w wyniku odszyfrowania wiadomości otrzymano oryginalną wiadomość „CAB”.

Siła kryptograficzna algorytmu RSA opiera się na założeniu, że niezwykle trudno jest ustalić tajny klucz ze znanego klucza publicznego, gdyż wymaga to rozwiązania problemu istnienia dzielników całkowitych. Problem ten nie pozwala obecnie na skuteczne (wielomianowe) rozwiązanie. W związku z tym w przypadku kluczy składających się z 200 cyfr binarnych (i takich liczb zaleca się używać) tradycyjne metody znajdowania dzielników wymagają wykonania ogromnej liczby operacji (około 10 23).

Kryptosystem RSA jest używany na wielu różnych platformach i branżach. Jest wbudowany w wiele produktów komercyjnych, których liczba stale rośnie. Jest używany przez systemy operacyjne Microsoft, Apple, Sun i Novell. Sprzętowo algorytm RSA jest używany w bezpiecznych telefonach, kartach sieciowych Ethernet, kartach inteligentnych i jest szeroko stosowany w sprzęcie kryptograficznym firmy Zaxus (Rasal). Ponadto algorytm jest zawarty we wszystkich głównych protokołach bezpiecznej komunikacji internetowej, w tym S/MIME, SSL i S/WAN, a także jest używany w wielu instytucjach, takich jak agencje rządowe, większość korporacji, laboratoria rządowe i uniwersytety.

Z technologii szyfrowania RSA BSAFE korzysta ponad 500 milionów użytkowników na całym świecie. Ponieważ w większości przypadków stosowany jest algorytm RSA, można go uznać za najpopularniejszy kryptosystem klucza publicznego na świecie, a liczba ta ma wyraźną tendencję do zwiększania się wraz ze wzrostem liczby użytkowników Internetu.

Dzień dobry, drodzy czytelnicy.
Najprawdopodobniej większość z Was wie, czym jest algorytm szyfrowania asymetrycznego RSA. W rzeczywistości w RuNet jest tak wiele artykułów poświęconych temu zagadnieniu, a zwłaszcza temu zasobowi, że prawie niemożliwe jest powiedzenie na ten temat niczego nowego.
No, na Boga, można wymyślić coś innego i już dawno było wszystko jasne. Przepis jest prosty:
Dwie liczby pierwsze P i Q.
Mnóż, aż otrzymasz liczbę N.
Wybierz dowolne E.
Znajdź D=E -1 (mod( P-1)(Pytanie-1)).
Aby zaszyfrować wiadomość M, podnosimy ją do potęgi E modulo N. Aby odszyfrować kryptotekst C do potęgi D, modulo N. Cały kryptoprymityw jest gotowy. Weźmy to i wykorzystajmy, prawda? Właściwie to nie w ten sposób. Rzecz w tym, że to tak naprawdę nic innego jak krypto-prymityw, a w prawdziwym świecie wszystko jest trochę bardziej skomplikowane.

Trochę teorii

Aby zrozumieć, dlaczego zdecydowanie odradza się używanie RSA w jego najprostszej formie, najpierw zwracamy uwagę na następujący wymóg dotyczący asymetrycznych kryptosystemów.
Wymóg 1:
Współczesny kryptosystem asymetryczny można (choć nie jest to jeszcze faktem) uznać za bezpieczny, jeśli atakujący, dysponując dwoma tekstami jawnymi M 1 i M 2 oraz jednym szyfrogramem C b, nie może z prawdopodobieństwem większym niż 0,5 określić, który z nich dwóm tekstom jawnym zaszyfrowany tekst C odpowiada b.
Zobaczmy, czy RSA spełnia ten wymóg. Wyobraźmy sobie więc, że atakujący Mallory podsłuchuje korespondencję pomiędzy Alicją i Bobem. Pewnego cudownego dla siebie dnia widzi, że Bob otwarcie zadał Alicji bardzo ważne pytanie, a znajomość odpowiedzi wzbogaci, a przynajmniej ogromnie rozbawi ciekawość Malory'ego. Alicja odpowiada Bobowi monosylabami na to osobiste pytanie. Szyfruje swoją odpowiedź kluczem publicznym Boba i wysyła zaszyfrowany tekst. Następnie Malory przechwytuje zaszyfrowany tekst i podejrzewa, że zawiera on „Tak” lub „Nie”. Jedyne, co musi teraz zrobić, aby poznać odpowiedź Alicji, to zaszyfrować słowo „Tak” kluczem publicznym Boba i jeśli otrzymany kryptotekst pasuje do przechwyconego, oznacza to, że Alicja odpowiedziała „Tak”, w przeciwnym razie atakujący zrozumie że odpowiedź brzmi „nie”.

Jak widać z tego, choć nieco naciąganego, ale wciąż nie tak utopijnego przykładu, RSA nie jest tak niezawodny, jak się powszechnie uważa. Tak, oczywiście, możemy powiedzieć, że sama Alicja jest głupcem i nikt nie prosił jej, aby monosylabami odpowiadała na tak poważne pytanie. Dlaczego więc teraz zakazać stosowania odpowiedzi składających się z jednego słowa w kryptografii? Oczywiście nie. Wszystko nie jest takie złe, wystarczy, że algorytm doda do tekstu losową informację, której nie da się przewidzieć, a podstępny Mallory będzie bezsilny. Przecież tak naprawdę nie będzie w stanie przewidzieć, że odpowiedź „Tak” po przetworzeniu przez algorytm zamieni się na przykład w „Tak4FE6DA54”, a zatem nie będzie mógł zaszyfrować tej wiadomości i nie będzie miał nic do porównania z przechwyconym kryptotekstem.

Tym samym możemy już powiedzieć, że RSA we wszystkich swoich przejawach, czy to PGP, czy SSL, nie szyfruje jedynie danych przesyłanych na wejście funkcji szyfrującej. Algorytm najpierw dodaje do tych danych bloki zawierające losowy zestaw bitów. I dopiero potem wynikowy wynik jest szyfrowany. Te. zamiast zwykłego
C=M E (mod N)
zbliżamy się do rzeczywistości
C=(M||Rand) E (mod N),
gdzie Rand jest liczbą losową.
Technika ta nazywana jest schematami augmentacji. Obecnie używanie RSA bez obwodów dopełniających to nie tyle złe maniery, co bezpośrednie naruszenie standardów.

Ale to nie wszystko. Uważa się, że nawet jeśli kryptosystem spełnia sformułowane powyżej wymagania, nie świadczy to jeszcze o jego przydatności do celów praktycznych. Sformułujmy jeszcze jeden wymóg bezpieczeństwa algorytmu asymetrycznego.

Wymóg 2:
Pozwól atakującemu uzyskać dostęp do „czarnej skrzynki” deszyfrującej. Te. Każdy kryptotekst może zostać odszyfrowany na żądanie atakującego. Następnie atakujący tworzy dwa teksty jawne M 1 i M 2 . Jeden z tych tekstów jest szyfrowany, a powstały kryptotekst Cb jest zwracany atakującemu. Zadaniem atakującego jest odgadnięcie z prawdopodobieństwem większym niż 0,5, która z wiadomości M 1 i M 2 odpowiada kryptotekstowi C b . Jednocześnie może poprosić o rozszyfrowanie dowolnej wiadomości z wyjątkiem Cb (w przeciwnym razie gra nie ma sensu). Mówią, że kryptosystem jest mocny, jeśli atakujący, nawet w tak doskonałych dla siebie warunkach, nie jest w stanie wskazać, któremu tekstowi źródłowemu odpowiada C b, z prawdopodobieństwem większym niż 0,5.

W świetle powyższego zobaczmy, jak sprawy mają się w RSA.
Zatem atakujący ma dwie wiadomości M 1 i M 2. A także kryptotekst
C b = M 1 E (mod N).
Musi wskazać, który z dwóch tekstów odpowiada Cb. Aby to zrobić, może wykonać następujące czynności. Znając klucz publiczny E, może stworzyć wiadomość
C"=2 E *C b (mod N).
Następnie prosi „czarną skrzynkę” deszyfrującą o odszyfrowanie wiadomości C.” A następnie prostą arytmetykę, która mu pomoże. Mamy:
M"=C" D (mod N)=2 ED *M 1 ED (mod N)=2*M 1 (mod N).
Te. Po obliczeniu M”/2 atakujący zobaczy M 1. Oznacza to, że zrozumie, że w naszym przykładzie wiadomość M 1 została zaszyfrowana, dlatego po raz kolejny utwierdzamy się w przekonaniu o niedopuszczalności stosowania RSA w jego naiwnej formie w praktyce .

Schematy dodawania pomagają wyeliminować tę uciążliwość. Dopiero teraz prosi się ich nie tylko o to, aby dodatkowe informacje były całkowicie przypadkowe i nieprzewidywalne. Ale ważne jest również, że dodatkowe bloki pomagają ustalić, czy zaszyfrowany tekst został uzyskany w wyniku zastosowania funkcji szyfrującej, czy też został zasymulowany przez osobę atakującą. Co więcej, jeśli okaże się, że zamiast odszyfrowanych danych symulowany jest szyfrogram, osoba atakująca otrzyma komunikat wskazujący, że dane nie odpowiadają prawdziwemu kryptotekstowi.

Wydawać by się mogło, że wdrożenie takiego schematu dodawania jest zadaniem trudnym, jednak kryptografia posiada już gotowe narzędzie do monitorowania integralności danych. Są to oczywiście funkcje skrótu. Wszystkie nowoczesne schematy dodawania opierają się na idei wykorzystania funkcji skrótu do sprawdzenia autentyczności odszyfrowanych danych.

RSA używa dwóch różnych schematów dopełniania do podpisywania i szyfrowania danych. Schemat wdrożony do podpisywania dokumentów nazywa się RSA-PSS (schemat podpisu probabilistycznego) lub probabilistyczny schemat podpisu. Stosowany schemat szyfrowania to RSA-OAEP (Optymalne dopełnienie szyfrowania asymetrycznego) lub zoptymalizowane asymetryczne wypełnienie szyfrowania, używając OAEP jako przykładu, i przyjrzyjmy się, jak wiadomości są faktycznie szyfrowane w RSA.

RSA-OAEP

Aby więc zaszyfrować absolutnie dowolną wiadomość w RSA-OAEP, wykonaj następujące czynności:

Dwie funkcje mieszające G(x) i H(x) dobiera się tak, aby łączna długość wyników funkcji mieszającej nie przekraczała długości klucza RSA.
Generowany jest losowy ciąg bitów l. Długość ciągu musi być równa długości wyniku funkcji skrótu H(x).
Wiadomość M jest podzielona na bloki k-bitów. Następnie do każdego otrzymanego bloku m dodawane są (n-k) zera. Gdzie n jest długością funkcji skrótu G(x).
Zdefiniuj następujący zestaw bitów: (m||0 (n-k) ⊕G(l))||(l⊕H(m||0 (n-k) ⊕G(l)))
Wynikowe bity są reprezentowane jako liczba całkowita M1
Kryptotekst uzyskuje się za pomocą wzoru: C=M 1 E (mod N)

Proces deszyfrowania przebiega następująco:

Znajdź M 1, korzystając ze wzoru M 1 = C D (mod N)
W powstałym zestawie bitów lewa strona jest odcięta. W tym sensie: lewa strona to n lewych bitów liczby M 1, gdzie n jest długością funkcji mieszającej G(x). Oznaczmy te bity umownie jako T. I zauważmy, że T=(m||0 (n-k) ⊕G(l)). Wszystkie pozostałe bity są po prawej stronie.
Znajdujemy H(T)=H(m||0 (n-k) ⊕G(l))
Znając H(T) otrzymujemy l, ponieważ wiemy, że l⊕H(T) jest prawą stroną bloku.
Po obliczeniu l znajdujemy m z T⊕G(l), ponieważ T=(m||0 (n-k) ⊕G(l))
Jeśli m kończy się na (n-k)-zera, wiadomość jest zaszyfrowana poprawnie. Jeśli nie, oznacza to, że zaszyfrowany tekst jest nieprawidłowy i dlatego najprawdopodobniej został sfałszowany przez osobę atakującą.

Wniosek

Te. RSA to nie tylko potęgowanie dużej liczby. To także dodanie zbędnych danych pozwalających na dodatkową ochronę Twoich informacji. Możesz zapytać: dlaczego to wszystko jest konieczne? Czy naprawdę możliwa jest taka sytuacja, w której osoba atakująca uzyskuje dostęp do algorytmu deszyfrującego? Przy zupełnie innej okazji powiedziano kiedyś: jeśli jakieś kłopoty mogą się zdarzyć, to na pewno się pojawią. Tylko przy zastosowaniu schematów dodawania nie będzie to już uważane za uciążliwe.

Aktualizacja: przeniesiono kryptografię na bloga.
aktualizacja2:
Literatura i linki:
1. N. Fergusson, B. Schneier „Kryptografia praktyczna”
2. N. Inteligentna „kryptografia”

W drugiej części przyjrzymy się popularnemu algorytmowi RSA, w którym do szyfrowania wykorzystywany jest klucz publiczny. Ale najpierw chcę cię jeszcze raz ostrzec. Kod przedstawiony w tym artykule służy wyłącznie celom edukacyjnym. Kryptografia to bardzo szeroka i złożona dziedzina, dlatego aby uniknąć problemów, nie polecam szyfrowania informacji za pomocą mojego hacka.

Algorytm RSA

Szyfrowanie przy użyciu klucza publicznego

Szyfrowanie kluczem publicznym jest stosowane wszędzie. Jeśli chociaż raz zapłaciłeś za coś w internecie, to zapewne korzystałeś już z tej metody (mam nadzieję!). Od razu pojawia się pytanie, jak działa ta ochrona. Jeśli wprowadzę numer mojej karty kredytowej, aby coś kupić, dlaczego nikt oprócz odbiorcy nie może zobaczyć tych informacji? Pozwólcie, że podam wam metaforę. Do otwarcia sejfu potrzebny jest klucz (lub młotek, ale na szczęście sejfy i zamki są odporne na tego typu ludzi). W przypadku szyfrowania klucza publicznego dzieje się prawie to samo. Pokazujesz zamek, aby wszyscy mogli go zobaczyć, ale tylko nieliczni mają klucz do tego zamka, a otwarcie drzwi innymi metodami jest prawie niemożliwe.

RSA jest jednym z algorytmów realizujących powyższy schemat. Dodatkowo możemy wykorzystać ten algorytm do sprawdzenia autentyczności naszej tożsamości. Jeśli wyślesz komuś zaszyfrowaną wiadomość przy użyciu klucza prywatnego, odbiorca będzie mógł odszyfrować Twoją wiadomość przy użyciu klucza publicznego. Technologia ta umożliwia podpisywanie wiadomości, potwierdzając tym samym autentyczność nadawcy.

Program demonstracyjny oparty na algorytmie RSA

Elektroniczny podpis cyfrowy (EDS) jest wymogiem dokumentu elektronicznego, którego zadaniem jest poświadczenie źródła danych i zabezpieczenie tego dokumentu elektronicznego przed fałszerstwem.

Schemat ogólny

Schemat podpisu elektronicznego zazwyczaj obejmuje:

algorytm generowania par kluczy użytkownika;
funkcja obliczania podpisu;
funkcja weryfikacji podpisu.

Funkcja obliczania podpisu na podstawie dokumentu i tajnego klucza użytkownika oblicza sam podpis. W zależności od algorytmu funkcja obliczania sygnatury może być deterministyczna lub probabilistyczna. Funkcje deterministyczne zawsze obliczają tę samą sygnaturę na podstawie tych samych danych wejściowych. Funkcje probabilistyczne wprowadzają do podpisu element losowości, co zwiększa siłę kryptograficzną algorytmów podpisu cyfrowego. Jednak obwody probabilistyczne wymagają niezawodnego źródła losowości (albo sprzętowego generatora szumu, albo kryptograficznie bezpiecznego generatora bitów pseudolosowych), co komplikuje implementację.

Obecnie schematy deterministyczne praktycznie nie są stosowane.

Funkcja weryfikacji podpisu sprawdza, czy dany podpis jest zgodny z danym dokumentem i kluczem publicznym użytkownika. Klucz publiczny użytkownika jest publicznie dostępny, więc każdy może zweryfikować podpis na danym dokumencie.

Ponieważ podpisywane dokumenty mają zmienną (i dość dużą) długość, w schematach podpisu cyfrowego podpis często jest umieszczany nie na samym dokumencie, ale na jego haszu. Do obliczenia skrótu wykorzystywane są kryptograficzne funkcje skrótu, co gwarantuje wykrycie zmian w dokumencie już po weryfikacji podpisu. Funkcje skrótu nie są częścią algorytmu podpisu cyfrowego, zatem w schemacie można zastosować dowolną niezawodną funkcję skrótu.

Bezpieczeństwo

Podpis cyfrowy zapewnia:

Identyfikacja źródła dokumentu. W zależności od szczegółów definicji dokumentu, podpisane mogą być pola typu „autor”, „wprowadzone zmiany”, „znacznik czasu” itp.
Ochrona przed zmianami dokumentów. Jakakolwiek przypadkowa lub celowa zmiana w dokumencie (lub podpisie) spowoduje zmianę skrótu, a tym samym unieważnienie podpisu.
Niemożność zrzeczenia się autorstwa. Ponieważ poprawny podpis można złożyć jedynie znając klucz prywatny, a jest on znany tylko właścicielowi, właściciel nie może odmówić złożenia podpisu na dokumencie.

Możliwe są następujące zagrożenia związane z podpisem cyfrowym:

Osoba atakująca może podjąć próbę sfałszowania podpisu pod wybranym przez siebie dokumentem.
Osoba atakująca może próbować dopasować dokument do danego podpisu, tak aby podpis do niego pasował.
Osoba atakująca może próbować sfałszować podpis dokumentu.

W przypadku korzystania z niezawodnej funkcji skrótu utworzenie fałszywego dokumentu z tym samym skrótem co oryginał jest trudne obliczeniowo. Zagrożenia te mogą jednak zostać zrealizowane w wyniku słabości określonych algorytmów mieszania lub podpisu lub błędów w ich implementacjach.

Możliwe są jednak również następujące zagrożenia dla systemów podpisu cyfrowego:

Osoba atakująca, która kradnie klucz prywatny, może podpisać dowolny dokument w imieniu właściciela klucza.
Osoba atakująca może nakłonić właściciela do podpisania dokumentu, na przykład za pomocą protokołu podpisu ślepego.
Osoba atakująca może zastąpić klucz publiczny właściciela (patrz zarządzanie kluczami) swoim własnym, podszywając się pod niego.

Algorytmy podpisu cyfrowego

Amerykańskie standardy elektronicznego podpisu cyfrowego: DSA, ECDSA

Rosyjskie standardy elektronicznego podpisu cyfrowego: GOST R 34.10-94 (obecnie nieobowiązujący), GOST R 34.10-2001
Ukraińska norma dotycząca elektronicznego podpisu cyfrowego: DSTU 4145-2002
Standard PKCS#1 opisuje w szczególności schemat elektronicznego podpisu cyfrowego oparty na algorytmie RSA

Zarządzanie kluczami

Ważnym problemem w całej kryptografii klucza publicznego, w tym w systemach podpisu cyfrowego, jest zarządzanie kluczem publicznym. Konieczne jest zapewnienie każdemu użytkownikowi dostępu do prawdziwego klucza publicznego dowolnego innego użytkownika, zabezpieczenie tych kluczy przed zastąpieniem przez osobę atakującą, a także zorganizowanie unieważnienia klucza, jeśli zostanie on naruszony.

Problem ochrony kluczy przed podmianą rozwiązuje się za pomocą certyfikatów. Certyfikat pozwala na poświadczenie zawartych w nim danych o właścicielu i jego kluczu publicznym podpisem dowolnej zaufanej osoby. Scentralizowane systemy certyfikatów (takie jak PKI) korzystają z urzędów certyfikacji prowadzonych przez zaufane organizacje. W systemach zdecentralizowanych (np. PGP), podpisując certyfikaty znanych i zaufanych osób, każdy użytkownik buduje sieć zaufania.

Zarządzaniem kluczami zajmują się centra dystrybucji certyfikatów. Kontaktując się z takim centrum, użytkownik może uzyskać dla niego certyfikat, a także sprawdzić, czy dany klucz publiczny nie został jeszcze unieważniony.

Opis algorytmu RSA

RSA- algorytm kryptograficzny klucza publicznego. RSA był pierwszym algorytmem tego typu, odpowiednim zarówno do szyfrowania, jak i podpisu cyfrowego. Algorytm jest używany w dużej liczbie zastosowań kryptograficznych.

Fabuła

Brytyjski matematyk Clifford Cocks pracujący w Centrum Komunikacji Rządu Wielkiej Brytanii (GCHQ) opisał podobny system w 1973 r. w wewnętrznych dokumentach GCHQ, ale praca ta została ujawniona dopiero w 1977 r., a Rivest, Shamir i Adleman opracowali RSA niezależnie od pracy Cox.

Patent amerykański nr 4 405 829 został wydany MIT w 1983 r. i wygasł 21 września 2000 r.

Opis algorytmu

Bezpieczeństwo algorytmu RSA opiera się na złożoności problemu faktoryzacji. Algorytm wykorzystuje dwa klucze - otwarty (publiczny) i tajny (prywatny), razem klucz publiczny i odpowiadający mu klucz tajny tworzą parę kluczy (parę kluczy). Klucz publiczny nie musi być utrzymywany w tajemnicy; służy do szyfrowania danych. Jeśli wiadomość została zaszyfrowana kluczem publicznym, można ją odszyfrować tylko za pomocą odpowiedniego klucza prywatnego.

Generacja klucza

Aby wygenerować parę kluczy, wykonaj następujące kroki:

1. Wybrano dwie duże liczby pierwsze i

2. Obliczany jest ich iloczyn

3. Obliczenie funkcji Eulera

4. Wybiera się taką liczbę całkowitą, że i porównaj z

5. Korzystając z rozszerzonego algorytmu Euklidesa, znajduje się taką liczbę, że

Liczba jest używana jako tekst zaszyfrowany. Aby odszyfrować, musisz obliczyć

Łatwo zauważyć, że podczas deszyfrowania przywrócimy oryginalną wiadomość:

Od warunku

wynika z tego

zatem dla pewnej liczby całkowitej

Zgodnie z twierdzeniem Eulera:

Niektóre cechy algorytmu

Generowanie liczb pierwszych

Aby znaleźć dwie duże liczby pierwsze i , podczas generowania klucza stosuje się zwykle probabilistyczne testy pierwszości liczb, które pozwalają szybko zidentyfikować i odrzucić liczby złożone.

· przy małej wartości wskaźnika otwarcia (np.) możliwa jest sytuacja, gdy okaże się, że . Następnie intruz może łatwo przywrócić oryginalną wiadomość, obliczając pierwiastek pliku .

· ponieważ RSA jest algorytmem deterministycznym, tj. nie wykorzystuje w trakcie działania wartości losowych, atakujący może zastosować wybrany atak tekstem jawnym.

Aby rozwiązać te problemy, wiadomości przed każdym szyfrowaniem są uzupełniane jakąś losową wartością – solą. Wypełnienie odbywa się w taki sposób, aby zapewnić , i . Dodatkowo, ponieważ wiadomość jest uzupełniana losowymi danymi, szyfrując ten sam tekst jawny za każdym razem otrzymamy inną wartość tekstu zaszyfrowanego, co uniemożliwia wykonanie wybranego ataku tekstem jawnym.

Wybór otwartej wartości wskaźnika

RSA jest znacznie wolniejszy niż algorytmy symetryczne. Aby zwiększyć szybkość szyfrowania, wybiera się mały wykładnik otwarty, zwykle 3, 17 lub 65537. Liczby te w postaci binarnej zawierają tylko dwie jedyneki, co zmniejsza liczbę niezbędnych operacji mnożenia przy podnoszeniu do potęgi. Na przykład, aby podnieść liczbę do potęgi 17, musisz wykonać tylko 5 operacji mnożenia:

powinien być wystarczająco duży. W 1990 roku Michael J. Wiener pokazał, że jeśli wybierzesz małe, okazuje się, że jest wystarczająco duże i nie ma problemu.

Długość klucza

Numer N musi mieć rozmiar co najmniej 512 bitów. Obecnie system szyfrowania oparty na RSA jest uważany za mocny, zaczynając od rozmiaru N wynoszącego 1024 bity.

Zastosowanie RSA

System RSA jest używany do zabezpieczania oprogramowania i schematów podpisu cyfrowego. Jest również stosowany w otwartym systemie szyfrowania PGP.

Ze względu na niską prędkość szyfrowania (około 30 kb/s przy 512-bitowym kluczu w procesorze 2 GHz) wiadomości są zwykle szyfrowane przy użyciu wysokowydajnych algorytmów symetrycznego klucza losowego ( klucz sesji), a za pomocą RSA szyfrują tylko ten klucz.

II. Realizacja

Jako przykład zaimplementowano program do cyfrowego podpisywania plików i weryfikacji podpisów. Zastosowano algorytm RSA oraz certyfikaty X.509. Certyfikat użytkownika jest wybierany z magazynu certyfikatów systemu Windows.

Podpisy cyfrowe zapisywane są w pliku xml z nazwą<имя исходного файла>.sig.xml

Fragmenty kodu

klasa publiczna Podpis

prywatny certyfikat X509Certificate2;

prywatna data typu DateTime;

prywatny bajt podpisanyHash;

publiczny certyfikat X509Certificate2

zdobądź (certyfikat zwrotu;)

zestaw (certyfikat = wartość; )

publiczna Data/Godzina Data

dostać (data powrotu;)

set(data = wartość; )

publiczny znak nieważności (wprowadzany ciąg znaków, certyfikat X509Certificate2)

this.certificate = nowy X509Certificate2(certyfikat);

data = DateTime.Now;

podpisanyHash = ((RSACryptoServiceProvider)cert.PrivateKey).SignData(Utils.StringToBytes(stringToEncrypt),nowy MD5CryptoServiceProvider());

public bool IsValid (wejście tekstowe)

string stringToEncrypt = dane wejściowe + data.Ticks;

return ((RSACryptoServiceProvider)certificate.PublicKey.Key).VerifyData(Utils.StringToBytes(stringToEncrypt),nowy MD5CryptoServiceProvider(), SignHash);

bajt publiczny SignedHash

get(zwróć podpisanyHash;)

set (signedHash = wartość;)

void DisplaySignatureList()

FileSignatures fileSignatures = ReadSignatures(GetSignaturesFileName(fileNameTextBox.Text));

podpisListTextBox.Text = "";

foreach (podpis podpisu w fileSignatures.Signaures)

wiersz ciągu = „”;

wiersz+= podpis.Certyfikat.Temat;

wiersz+=" "+podpis.Data.ToString();

string hash = GetFileHash(fileNameTextBox.Text);

bool ważny = podpis.IsValid(hash);

rząd = „v” + rząd;

rząd = "x" + rząd;

podpisListTextBox.Text += wiersz+"\r\n";

III. Literatura

S. Burnet, S. Payne: Kryptografia. Oficjalny przewodnik bezpieczeństwa RSA – M. „Binom”, 2002
V. Zima: Bezpieczeństwo globalnych technologii sieciowych – „BHV-Petersburg”, 2003
Wenbo Mao Nowoczesna kryptografia: teoria i praktyka = Nowoczesna kryptografia: teoria i praktyka. - M.: „Williams”, 2005. - s. 768. ISBN 0-13-066943-1
Nils Ferguson, Bruce Schneier Kryptografia praktyczna: projektowanie i wdrażanie bezpiecznych systemów kryptograficznych. - M.: „Dialektyka”, 2004. - s. 432. ISBN 0-471-22357-3
Schneier, Bruce. Kryptografia stosowana. Protokoły, algorytmy, teksty źródłowe w języku C - M.: Wydawnictwo TRIUMPH, 2002 - 816 s.: il. ISBN 5-89392-055-4