Szyfrowanie asymetryczne

Kryptografia klucza publicznego (nazywana również kryptografią asymetryczną) to rodzaj kryptografii, w którym używa się zestawów dwu lub więcej powiązanych ze sobą kluczy, umożliwiających wykonywanie różnych czynności kryptograficznych. Jeden z kluczy może być udostępniony publicznie bez utraty bezpieczeństwa danych zabezpieczanych tym kryptosystemem.

Najważniejsze zastosowania kryptografii asymetrycznej – szyfrowanie i podpisy cyfrowe – zakładają istnienie 2 kluczy – prywatnego i publicznego, przy czym klucza prywatnego nie da się łatwo odtworzyć na podstawie publicznego. W niektórych innych zastosowaniach kluczy może być więcej.

Algorytmy mające zastosowanie w kryptografii asymetrycznej wykorzystują operacje jednokierunkowe - takie, które da się łatwo przeprowadzić w jedną stronę a bardzo trudno w drugą. Np. mnożenie jest łatwe, a faktoryzacja trudna (na czym opiera się RSA). Potęgowanie modulo jest łatwe, a logarytmowanie dyskretne jest trudne (na czym opierają się ElGamal, DSA i ECC).

Podpisy cyfrowe

Strona uwierzytelniająca wylicza skrót (ang. hash) podpisywanej wiadomości. Następnie szyfruje ten skrót swoim kluczem prywatnym i jako podpis cyfrowy dołącza do oryginalnej wiadomości. Dowolna osoba posiadająca klucz publiczny może sprawdzić autentyczność podpisu, poprzez odszyfrowanie skrótu za pomocą klucza publicznego nadawcy i porównanie go z własnoręcznie wyliczonym na podstawie wiadomości.

2.Schemat szyfrowania

Krok 1: Alice przesyła do Boba swój klucz publiczny

  Krok 2 & 3: Bob szyfruje wiadomość kluczem publicznym Alice, która to następnie  otrzymuje zaszyfrowaną wiadomość i rozszyfrowuje ją kluczem prywatnym.

Szyfrowanie - wstęp.

Metody szyfrowania tekstów oparte były głownie na zamianie i przestawianiu znaków lub symboli, a skuteczność utajniania zależała przede wszystkim od utrzymania w tajemnicy sposobu szyfrowania.Samą kryptologię można także postrzegać jako gałąź matematyki stosowanej i informatyki. Faktycznie w zastosowaniach informatycznych kryptologia nabiera praktycznego znaczenia w połączeniu z zagadnieniami dostępu do systemów operacyjnych, baz danych oraz sieci komputerowych i przesyłania danych.

 
 METODY.

1. Szyfry przestawieniowe

Szyfry te zmieniają uporządkowanie znaków w danych według pewnego schematu. Zazwyczaj dokonuje się przestawienia za pomocą pewnej figury geometrycznej. Szyfrowanie przebiega więc w dwóch krokach: tekst jawny wpisuje się do figury w sposób określony pewną tzw. ścieżką zapisu, a następnie odczytuje się go według określonego porządku (ścieżki odczytu) otrzymując tekst zaszyfrowany. Klucz obejmuje więc figurę geometryczną oraz ścieżki zapisu i odczytu.

Jako pierwszy przykład weźmy prosty szyfr płotowy. Litery tekstu jawnego zapisuje się tu tak, aby tworzyły kształt przypominający wierzchołek płotu zbudowanego ze sztachet. Tekst zaszyfrowany otrzymujemy odczytując kolejne wiersze tak utworzonej konstrukcji. Proces szyfrowania możemy przedstawić na prostym przykładzie.

Przykład. "JUTRO JEST SOBOTA" (pomińmy przy zapisie spacje):
J            O               T               O
 U      R       J       S      S       B     T
    T                E                O             A



1.3 Szyfry podstawieniowe wieloalfabetyczne

Stosuje się w nich wiele odwzorowań znaków tekstu jawnego na znaki kryptogramu, przy czym każde odwzorowanie jest z reguły typu jeden do jednego. Jak więc widzimy szyfry wieloalfabetyczne ukrywają rozkład częstości przez użycie wielu podstawień.

Szyfrowanie wiadomości przebiega tu na podstawie dowolnie wybranego słowa kluczowego (hasła). W przypadku znaków ASCI może to być dowolny ich ciąg. Do numeru każdego kolejnego znaku tekstu jawnego dodajemy numer odpowiadającego mu znaku słowa kluczowego i uzyskujemy znak kryptogramu. Gdy słowo kluczowe się skończy, bierzemy je kolejny raz od początku.

1.4 Szyfry podstawieniowe poligramowe

Szyfry tego typu, w odróżnieniu od wyżej przedstawionych innych rodzajów szyfrów podstawieniowych, "obrabiają" jednocześnie większe grupy liter. Złamanie takiego szyfru jest zatem dużo trudniejsze dzięki odebraniu znaczenia częstości występowania liter lub znaków.

Dobrym, choć dosyć prostym, przykładem szyfru poligramowego jest szyfr Playfaira, wykorzystywany przez Anglików w czasie I wojny światowej. Kluczem jest tu macierz o wymiarach 5x5, w której skład wchodzą wszystkie litery alfabetu łacińskiego z wyjątkiem J. Użyjmy jako słowa-klucza słowa SZYFR. Zatem pierwszą czynnością będzie zapisanie liter alfabetu w kwadracie 5 x 5, zaczynając od słowa kluczowego i łącząc litery I oraz J.

Odwrotna Notacja Polska

Odwrotną notację polską ONP (ang. RPN – Reverse Polish Notation), zwana często również notacją Postfix, wymyślono w celu zapisywania dowolnych wyrażeń arytmetycznych bez nawiasów. W normalnym zapisie arytmetycznym operatory znajdują się pomiędzy argumentami:

2 + 2     6 - 4     3 * 5     12 / 3

Operatory posiadają priorytety, czyli "ważność". Jeśli w wyrażeniu wystąpią operatory o różnych priorytetach, to najpierw zostaną wykonane te ważniejsze:

3 + 5 * 2 = 3 + 10 = 13

Jeśli chcemy zmienić kolejność wykonywania działań, musimy używać nawiasów:

(3 + 5) * 2 = 8 * 2 = 16

W ONP problem ten nie występuje. Operator zawsze występuje po swoich argumentach:

2 2 +     6 4 -     3 5 *     12 3 /

Dzięki tej prostej zasadzie nawiasy stają się zbędne:

3 + 5 * 2 → 3 5 2 * + = 3 10 + = 13

(3 + 5) * 2 → 3 5 + 2 * = 8 2 * = 16

Do obliczenia wartości wyrażenia zapisanego w ONP potrzebujemy stosu. Zasada jest następująca:

Wyrażenie ONP przeglądamy od strony lewej do prawej. Jeśli napotkamy liczbę, to umieszczamy ją na stosie. Jeśli napotkamy operator, to ze stosu pobieramy dwie ostatnie liczby, wykonujemy na nich działanie zgodne z napotkanym operatorem i wynik umieszczamy z powrotem na stosie. Gdy wyrażenie zostanie przeglądnięte do końca, na szczycie stosu będzie znajdował się jego wynik.

Notacja ONP jest szeroko wykorzystywana w kompilatorach języków wysokiego poziomu. Istnieją również języki, które do obliczeń stosują jedynie ONP – np. Forth.

Przed przystąpieniem do zaprojektowania algorytmu ONP musimy poczynić pewne ustalenia. Dla prostoty umawiamy się, że używać będziemy tylko czterech operatorów arytmetycznych:

 

• + – dodawanie
• - – odejmowanie
• * – mnożenie
• / – dzielenie

Wyrażenie musi być poprawne – algorytm nie sprawdza jego poprawności.

Każdy element będzie wprowadzany w osobnym wierszu – w ten sposób pozbędziemy się problemu analizowania tekstu pod kątem zawartości w nim liczb i operatorów. W rzeczywistości wyrażenie zawarte w wierszu zostałoby najpierw rozbite na elementy składowe – liczby i operatory – a następnie elementy te zostałyby użyte do obliczenia wartości wyrażenia wg naszego algorytmu.

Liczby muszą mieć postać akceptowaną przez dany język programowania.

Ostatnim elementem wyrażenia jest znak "=". Powoduje on zakończenie obliczeń i wyprowadzenie wyniku ze stosu.

W algorytmie będziemy musieli rozpoznawać, czy wprowadzony element jest liczbą, czy też operatorem lub znakiem "=". W trzech wybranych przez nas językach można to zrobić następująco:

Wyszukiwanie wzorca w tekscie.

Problem

W łańcuchu znakowym s znaleźć wszystkie wystąpienia wzorca p.

Rozwiązanie

Problem Wyszukiwania Wzorca – WW (ang. pattern matching) to jeden z podstawowych problemów tekstowych, który intensywnie badali wybitni informatycy. Rozwiązaniem jest wskazanie w ciągu s wszystkich pozycji i takich, że zachodzi równość:

s[i : i + |p|] = p

Oznacza to, iż wzorzec p jest fragmentem łańcucha s występującym na pozycji i-tej.

Algorytm N – naiwny – ustawia okno o długości wzorca p na pierwszej pozycji w łańcuchu s. Następnie sprawdza, czy zawartość tego okna jest równa wzorcowi p. Jeśli tak, pozycja okna jest zwracana jako wynik, po czym okno przesuwa się o jedną pozycję w prawo i cała procedura powtarza się. Algorytm kończymy, gdy okno wyjdzie poza koniec łańcucha. Klasa pesymistycznej złożoności obliczeniowej algorytmu N jest równa O(n × m), gdzie n oznacza liczbę znaków tekstu, a m liczbę znaków wzorca. Jednakże w typowych warunkach algorytm pracuje w czasie O(n), ponieważ zwykle wystarczy porównanie kilku początkowych znaków okna z wzorcem, aby stwierdzić, iż są one niezgodne.