Algorytm szyfrowania RSA. Algorytm szyfrowania RSA Przykład szyfrowania RSA

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 wielomianowego algorytmu czasu. Oznacza to, że Alicja może zaszyfrować wiadomość kluczem publicznym (e) w czasie wielomianowym. Bob może go również odszyfrować w czasie wielomianowym (ponieważ zna d). Jednak Ewa nie może rozszyfrować tej wiadomości, ponieważ musiałaby obliczyć pierwiastek e z C za pomocą arytmetyki modułowej. 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 (inwersję multiplikatywną), 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.

Dzień dobry, drodzy czytelnicy.
Najprawdopodobniej większość z Was wie, czym jest algorytm asymetrycznego szyfrowania 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 tak. Rzecz w tym, że tak naprawdę jest to 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 (ale 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 wspaniałego 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 silny, 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 odszyfrowującą „czarną skrzynkę” 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 dodatków 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:

1. 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.
2. 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).
3. 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).
4. Zdefiniuj następujący zestaw bitów: (m||0 (n-k) ⊕G(l))||(l⊕H(m||0 (n-k) ⊕G(l)))
5. Wynikowe bity są reprezentowane jako liczba całkowita M1
6. Kryptotekst uzyskuje się za pomocą wzoru: C=M 1 E (mod N)

Proces deszyfrowania przebiega następująco:

1. Znajdź M 1, korzystając ze wzoru M 1 = C D (mod N)
2. 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.
3. Znajdujemy H(T)=H(m||0 (n-k) ⊕G(l))
4. Znając H(T) otrzymujemy l, ponieważ wiemy, że l⊕H(T) jest prawą stroną bloku.
5. Po obliczeniu l znajdujemy m z T⊕G(l), ponieważ T=(m||0 (n-k) ⊕G(l))
6. 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”

Wprowadzenie 3

Część główna 5

1Historia stworzenia 5

2Opis algorytmu 5

2.1Tworzenie kluczy 6

2.2 Szyfrowanie i deszyfrowanie 6

2.3 Skorzystaj z przykładu 7

Wniosek 9

Lista wykorzystanych źródeł 10

Wstęp

Kryptografia to specjalny system zmiany zwykłego pisma, służący do uczynienia tekstu zrozumiałym tylko dla ograniczonej liczby osób znających ten system.

Kryptografia to nauka o ochronie informacji za pomocą metod matematycznych.

Współczesna kryptografia obejmuje:

kryptosystemy symetryczne;

kryptosystemy asymetryczne;

systemy elektronicznego podpisu cyfrowego (EDS);

funkcje skrótu;

zarządzanie kluczami;

zdobywanie ukrytych informacji;

kryptografia kwantowa.

Szyfrowanie symetryczne – algorytmy symetryczne to takie, w których do szyfrowania i deszyfrowania używany jest ten sam tajny klucz (znany tylko nadawcy i odbiorcy).

Typowe algorytmy szyfrowania symetrycznego:

AES (Advanced Encryption Standard) – amerykański standard szyfrowania;

GOST 28147-89 - krajowy standard szyfrowania danych;

DES (Data Encryption Standard) – standard szyfrowania danych w USA do AES;

3DES (potrójny DES, potrójny DES);

IDEA (międzynarodowy algorytm szyfrowania danych);

SEED – koreański standard szyfrowania danych;

Camellia to szyfr dopuszczony do użytku w Japonii;

XTEA to algorytm najłatwiejszy do wdrożenia.

Kryptoalgorytmy asymetryczne mają na celu przede wszystkim wyeliminowanie głównej wady kryptosystemów symetrycznych – złożoności zarządzania i dystrybucji kluczy.

Podstawą wszystkich asymetrycznych algorytmów kryptograficznych jest duża złożoność obliczeniowa odzyskiwania tekstu jawnego bez znajomości klucza prywatnego.

Przykłady asymetrycznych algorytmów kryptograficznych:

Diffiego-Hellmanna;

RSA – Rivest, Shamir, Adelman – opiera się na złożoności problemu rozkładu na czynniki dużych liczb w krótkim czasie;

DSA – algorytm podpisu cyfrowego, standard amerykański;

GOST R 34.10 – 94, 2001, normy Federacji Rosyjskiej.

W tym streszczeniu szczegółowo rozważymy algorytm asymetrycznego szyfrowania kryptograficznego - algorytm RSA.

Głównym elementem

Algorytm RSA (skrót od Rivest, Shamir i Adleman) to algorytm kryptograficzny z kluczem publicznym, który wykorzystuje złożoność obliczeniową problemu rozkładu na czynniki dużych liczb całkowitych. Kryptosystem RSA był pierwszym systemem nadającym się zarówno do szyfrowania, jak i podpisywania cyfrowego.

Historia stworzenia

Opublikowany w listopadzie 1976 roku artykuł Whitfielda Diffiego i Martina Hellmana „New Directions in Cryptography” zrewolucjonizował rozumienie systemów kryptograficznych, kładąc podwaliny pod kryptografię klucza publicznego. Opracowany później algorytm Diffiego-Hellmana umożliwił dwóm stronom uzyskanie wspólnego tajnego klucza przy użyciu niezabezpieczonego kanału komunikacji. Algorytm ten nie rozwiązał jednak problemu uwierzytelniania. Bez dodatkowych narzędzi użytkownicy nie mogliby być pewni, z kim wygenerowali wspólny tajny klucz.

Po przestudiowaniu tego artykułu trzej naukowcy Ronald Linn Rivest, Adi Shamir i Leonard Adleman z Massachusetts Institute of Technology (MIT) rozpoczęli poszukiwania funkcji matematycznej, która umożliwiłaby implementację modelu systemu kryptograficznego klucza publicznego sformułowanego przez Whitfielda Diffiego i Martina Hellmana . Po przeanalizowaniu ponad 40 możliwości opracowali algorytm oparty na różnicy w łatwości znalezienia dużych liczb pierwszych i trudności w rozłożeniu na czynniki iloczynu dwóch dużych liczb pierwszych, co później nazwali RSA. System otrzymał nazwę od pierwszych liter nazwisk jego twórców.

Opis algorytmu

Pierwszym krokiem w każdym algorytmie asymetrycznym jest utworzenie pary kluczy – publicznego i prywatnego – i rozpowszechnienie klucza publicznego „na całym świecie”.

Tworzenie kluczy

W przypadku algorytmu RSA etap tworzenia klucza składa się z następujących operacji:

Liczba nazywana jest wykładnikiem otwartym

Szyfrowanie i deszyfrowanie

Załóżmy, że nadawca chce wysłać wiadomość do odbiorcy.

Komunikaty są liczbami całkowitymi z zakresu od 0 do , tj. . Rysunek 1 przedstawia schemat algorytmu RSA.

Rysunek 1 – Schemat algorytmu RSA

Algorytm nadawcy:

Algorytm odbiorcy:

Równania (1) i (2), na których opiera się schemat RSA, wyznaczają wzajemnie odwrotne przekształcenia zbioru.

Przykład użycia

W tabeli 1 przedstawiono przykład wykorzystania algorytmu RSA. Nadawca wysłał zaszyfrowaną wiadomość „111111”, a odbiorca za pomocą swojego klucza prywatnego odszyfrował ją.

Tabela 1 – Wykonanie algorytmu RSA krok po kroku

	Opis operacji	Wynik operacji
Generacja klucza	Wybierz dwie liczby pierwsze
	Oblicz moduł
	Oblicz funkcję Eulera
	Wybierz otwarty wykładnik
	Oblicz tajny wykładnik
Szyfrowanie	Wybierz tekst do zaszyfrowania
	Oblicz szyfrogram
Rozszyfrowanie	Oblicz oryginalną wiadomość

Wniosek

W tym streszczeniu szczegółowo omówiono algorytm szyfrowania asymetrycznego RSA. Opisano historię jego powstania, opisano algorytmy tworzenia kluczy, szyfrowania i deszyfrowania. Zaprezentowano także przykład praktycznego zastosowania algorytmu RSA.

Lista wykorzystanych źródeł

Semenow Yu.A. Protokoły internetowe // M.: Prospekt, 2011. – 114 s.

Belyaev A.V. Metody i środki bezpieczeństwa informacji // Czarny Oddział Państwowego Uniwersytetu Technicznego w Petersburgu, 2010. – 142 s.

Venbo M. Współczesna kryptografia. Teoria i praktyka // M.: Williams, 2005. - 768 s.

Schneier B. Kryptografia stosowana. Protokoły, algorytmy, teksty źródłowe // M.: Triumph, 2002. - 816 s.

Algorytm RSA // Zasób internetowy: http://ru.wikipedia.org/wiki/Rsa

Poniżej wycięcia znajdują się przykłady wyboru „złych” parametrów szyfru RSA.

„Należy podkreślić, że przy wyborze modułu RSA (nr N) dla każdego z korespondentów sieci. W związku z tym można powiedzieć, co następuje. Czytelnik może to samodzielnie sprawdzić, znając jedną z trzech wielkości P, Q Lub φ(n), możesz łatwo znaleźć klucz prywatny RSA…”.

Dodajmy do tego tekstu. Jeżeli wybór modułu szyfrującego RSA nie powiedzie się, jak to miało miejsce na przykładzie z instrukcji podanej poniżej, można odszyfrować tekst bez konieczności posiadania tajnego klucza, tj. nie znając żadnej z trzech wymienionych wielkości.

Aby to zrobić, wystarczy mieć zaszyfrowany tekst określony przez moduł szyfrujący N, klucz publiczny mi szyfr i wykonaj tylko trzy kroki ataku bezkluczowego odczytu. Po czwartym etapie ataku stwierdza się, że tekst źródłowy został uzyskany w poprzednim kroku i można go odczytać. Pokażmy, jakie to proste.

Najpierw podamy sam przykład ze s. 313-315 wspomnianej instrukcji.

Przykład

Szyfrowanie krótka wstępna wiadomość tekstowa: RSA.
Odbiorca ustala szyfr z charakterystyką n=pq=527, Gdzie p=17, q=31 I φ(n)=(р –1)(q – 1)=480. Jako klucz publiczny mi wybierana jest liczba względnie pierwsza φ(n), e=7. Liczby całkowite dla tej liczby znajdują się przy użyciu rozszerzonego algorytmu Euklidesa ty I w, spełniając relację e∙u+φ(n)∙v=1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

Ponieważ –137≡343(mod480), To d=343.

Badanie: 7∙343=2401≡1(mod480).

Wiadomość tekstowa prezentowana jest jako ciąg liczb zawartych w przedziale . Listy do tego R, S I A są kodowane jako pięciobitowe liczby binarne. Numery seryjne tych liter alfabetu angielskiego są używane w ich reprezentacji binarnej:

R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.

Następnie RSA=(100101001100001) 2. Podział tekstu na bloki o ograniczonej długości daje prezentację dwublokową: RSA=(100101001), (100001)=(M 1 =297, M 2 =33).

Bloki tekstu źródłowego są szyfrowane sekwencyjnie M1 =297, M2 =33:
y 1 =E k (M 1)=M 1 mi ≡297 7 (mod527)=474.

Tutaj skorzystaliśmy z faktu, że:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 =E k (M 2)=M 2 mi ≡33 7 (mod527)=407.

Zaszyfrowany tekst, podobnie jak oryginał, uzyskiwany jest w postaci dwóch bloków: y1 =474; y2 =407.

Rozszyfrowanie wydaje się być sekwencją działań re k (y i) = (y i) d = (y i) 343 (mod 527), i=1,2.

Obliczenia potęgowania D wygodniej jest to zrobić, przedstawiając najpierw wykładnik jako sumę potęg liczby 2 , a mianowicie: 343=256+64+16+4+2+1 .

Korzystanie z tej reprezentacji wykładniczej d=343, otrzymujemy:

474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
i w końcu 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Wartość jest obliczana w podobny sposób 407 343 (mod527)=33.

Przejście na dosłowną reprezentację odszyfrowanej wiadomości daje: RSA.

Po zapoznaniu się z przykładem, w podręczniku omówiono niezawodność systemu RSA. Podkreślono potrzebę ostrożności przy wyborze modułu szyfrującego RSA (cyfry). N) dla każdego z korespondentów sieci. Wskazuje się, że niedopuszczalne jest ignorowanie wymagań dotyczących wybranych cech systemu szyfrującego. Wśród tych wymagań niestety nie wskazano naruszenia, którego naruszenie ilustruje podany przykład.

Atak na szyfr RSA

Spójrzmy na przykład ataku na szyfr RSA. Wykorzystajmy dane z przykładu podanego na stronach 313-315 w podręczniku „Podstawy kryptografii” A.P. Alferov, A.Yu. Zubov, A.S. Kuźmin, A.V. Czeremuszkin, Moskwa. „Helios ARV”, 2001.

Niedopuszczalność (niedopuszczalność) wybranych parametrów systemu w tym przykładzie łatwo pokazać obliczenia realizujące atak na bezkluczowy odczyt tekstu źródłowego. Istota takiego ataku jest następująca. Określono klucz publiczny szyfru RSA ( e=7, n=527) i tekst zaszyfrowany. W tym przykładzie szyfrogram jest reprezentowany w dwóch blokach
y=(y 1 =474, y 2 =407).

Każdy zaszyfrowany blok jest atakowany indywidualnie, najpierw atakujemy y1 =474, po odszyfrowaniu atakujemy kolejny blok y2 =407.

Następnie tworzony jest ciąg wartości liczbowych poprzez wielokrotne szyfrowanie, przechowywanie wyników dwóch kolejnych etapów algorytmu ataku oraz wykorzystanie klucza publicznego. tak, ja, y 1 = y dostępny szyfrogram.

W algorytmie ataku szyfrogramem wyznaczany jest następujący numer kroku: J, dla którego y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, ja>1. Z ostatniej relacji widzimy to po podniesieniu do potęgi mi wartości (y i e j–1 (mod n)) uzyskuje się początkowy tekst zaszyfrowany y ja = y 1.

Oznacza to jednak, że na tym etapie tekst jawny został zaszyfrowany. Dzięki bezpośrednim obliczeniom (jest ich bardzo niewiele) za pomocą kalkulatora ekranowego znajdujemy tę wartość J, przy którym cykl szyfrowania kończy się wartością y 1, od którego rozpoczął się cykl.

Atak na pierwszy blok y1 =474 szyfrogram.
Krok 1:  474 7 (mod527)=382;
Krok 2:  382 7 (mod527)=423;
Krok 3:  423 7 (mod527)=297;
Krok 4:   na tym etapie już znaleziony tekst źródłowy jest szyfrowany, ale należy to zrobić, ponieważ osoba atakująca nie zna tekstu źródłowego. Oznaką zakończenia ataku jest zbieżność początkowej wartości szyfrogramu ( 474 ) i wynik 4. etapu szyfrowania. To jest dokładnie zbieg okoliczności, który ma miejsce.

297 7 (mod527)=474 otrzymał początkowy (pierwszy) blok tekstu zaszyfrowanego. Atak na pierwszy blok zakończył się sukcesem y1 =474. Poprzedni wynik kroku 3 jest równy zwykłemu tekstowi M1 =297.

n=527 r=297 modulo n=527. Jest napisane tak y i =у 1 =297. Tworzenie pozostałości mocy
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Atak na drugi blok y2 =407 szyfrogram.
Krok 1:  407 7 (mod527)=16;
Krok 2:  16 7 (mod527)=101;
Krok 3:  101 7 (mod527)=33;
Krok 4:  33 7 (mod527)=407.

Ponownie w trzecim kroku uzyskano blok tekstu źródłowego ( M2 =33), ale atakujący o tym nie wie i wykonuje kolejny (czwarty krok), którego efektem jest ( 407 ) pasuje do początkowego tekstu zaszyfrowanego y2 =407.

Zasadniczo w pierścieniu reszt modulo n=527 wdrożono krótki cykl przetwarzania odliczeń r=33 modulo n=527. Jest napisane tak y i = y 2 =33.
Tworzenie pozostałości mocy ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Wynik ataku (tekst źródłowy M1 =297, M2 =33) uzyskuje się poprzez trzykrotne zaszyfrowanie danego szyfrogramu. Trudno sobie wyobrazić większy sukces atakującego szyfrogramem.

Kontynuując dyskusję na temat wyboru modułu i innych parametrów szyfru, możemy dodać, że moduł szyfru ( n=527) niektórych tekstów źródłowych w ogóle nie da się zaszyfrować. W tym przypadku wybór wartości klucza publicznego nie odgrywa dużej roli. Istnieją wartości tekstu źródłowego, których na ogół nie da się zaszyfrować wybranym szyfrem o module n=527.

Żaden z podanych nie może szyfrować tekstów źródłowych reprezentowanych przez liczby
187 , 341 , 154 I 373 .

Przykład (brak możliwości zaszyfrowania wartości niektórych tekstów źródłowych)

Niech teksty źródłowe będą reprezentowane przez cztery bloki y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373). Wystawca mi kluczem publicznym szyfru może być dowolna liczba względnie pierwsza z funkcją Eulera φ(n)=φ(527)=480. Jednak w rozpatrywanym przypadku klucz publiczny mi można ustawić dowolnie. Rzeczywiście, niech e=2, 4, 7, 9, 17, 111 Następnie:

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

Z rozważanego przykładu wynika prosty wniosek. Rzeczywiście, do wyboru parametrów procesu szyfrowania należy podchodzić bardzo ostrożnie i przeprowadzić dokładną wstępną analizę takich parametrów. Jak to zrobić, to osobna kwestia i nie jest rozważana w ramach tej pracy.

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.

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 działanie tego typu aktorów). 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 i prawie niemożliwe jest otwarcie drzwi innymi metodami.

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