Szyfrowanie asymetryczne

Szyfrowanie asymetryczne 

-(szyfrowanie z kluczem publicznym) jest nieco bardziej skomplikowane od szyfrowania symetrycznego. Podstawowa różnica polega na tym, że tutaj wyróżniamy dwa klucze - prywatny i publiczny. Oba klucze generowane są przez odbiorcę.

1. Odbiorca za pomocą specjalnego algorytmu (szyfru) asymetrycznego (np. RSA, ElGamal, DSA, ECC, Diffy-Hellman, Cramer-Shoup) generuje oba klucze. Klucz publiczny odbiorca przekazuję nadawcy. Ponieważ jest on publiczny odbiorca nie musi martwić się o jego przekazanie nadawcy - może to zrobić np. za pomocą Internetu, umieścić na stronie czy forum (istnieją nawet specjalne serwery kluczy publicznych). To że wszyscy mogą zdobyć ten klucz nie stanowi żadnego problemu.
2. Nadawca korzystając z przekazanego mu klucza publicznego szyfruje wiadomość. 
3. Odbiorca odszyfrowuje wiadomość za pomocą prywatnego klucza. 

Jeżeli ktoś postronny zdobył ten klucz publiczny również może zaszyfrować wiadomość. Pamiętajmy jednak że tylko odbiorca dysponuje kluczem prywatnym, a w szyfrowaniu asymetrycznym wiadomość zaszyfrowana za pomocą klucza publicznego może być odszyfrowana tylko za pomocą klucza prywatnego! Może na początku wydawać się to trochę dziwne, jednak gdy odbiorca (w kroku nr. 1) generuje oba klucz, to stają się one w pewien sposób "powiązane matematycznie". Dlatego odbiorca nie powinien nikomu innemu udostępniać klucza prywatnego! Jeżeli nie udostępni, tonikt kto zna klucz publiczny nie będzie wstanie odszyfrować wiadomości.

Przedstawione powyżej szyfrowanie asymetryczne - podobnie jak szyfrowanie symetryczne - służy zapewnieniu poufności. Jednak jeżeli zmienimy kolejność użycia kluczy szyfrowanie asymetryczne może być również wykorzystane do zapewnienia autentyczności, a także poufności i autentyczności jednocześnie.

Szyfrowanie symetryczne

Szyfrowanie symetryczne (szyfr z jednym/pojedynczym kluczem) 

– nadawca i odbiorca wiadomości używają tego samego prywatnego klucza. Inaczej mówiąc, każdy kto jest w posiadaniu tego klucza symetrycznego, może zarówno zaszyfrować jak i odszyfrować wiadomość. Wobec tego oczywiste jest, że szyfrowanie symetryczne będzie skuteczne tylko wówczas jeżeli ten klucz nie wpadnie w niepowołane ręce – kluczem tym powinny dysponować tylko nadawca i odbiorca.

Nadawca i odbiorca wiadomości muszą jednak najpierw przesłać sobie ten klucz tak, żeby nie zdobyły go osoby postronne, np. muszą spotkać się osobiście. Zauważamy że w niektórych przypadkach szyfrowanie symetryczne jest bezużyteczne, bo skoro nadawca i odbiorca spotkali się by przekazać sobie klucz, to czemu od razu nie mogli by sobie przekazać wiadomości którą mieli zaszyfrować? Oczywiście czasami jest np. tak, że w momencie przekazania klucza wiadomość która ma być zaszyfrowana nie jest jeszcze znana i w takiej sytuacji szyfrowanie symetryczne może się oczywiście przydać. Nie ma znaczenia czy to nadawca wygeneruje i przekaże klucz odbiorcy, czy odwrotnie. Kiedy już obie strony będą dysponowały tym kluczem prywatnym wiadomość może być zaszyfrowana. Spójrzmy więc jak przebiega szyfrowanie symetryczne:

1. Nadawca przekazuje odbiorcy (lub odwrotnie) klucz prywatny przez bezpieczny kanał.
2. Nadawca szyfruje wiadomość za pomocą klucza prywatnego. Szyfrowania odbywa się za pomocą specjalnego algorytmy (szyfru) symetrycznego który używa klucza prywatnego. Do szyfrów symetrycznych zaliczamy takie algorytmy jak DES, AES, Blowfish, Triple DES, Twofish, Serpent, RC4, RC5. Zaszyfrowana wiadomość zostaje wysłana to odbiorcy.
3. Odbiorca przy pomocy klucza prywatnego odszyfrowuje wiadomość.

Jak więc widzimy schemat szyfrowania symetrycznego jest bardzo prosty. Szyfrowanie symetryczny umożliwia poufność (ang. confidentiality) danych, czyli udostępnienie ich tylko osobom które posiadają odpowiedni klucz (właściwemu odbiorcy). Informacje których nie chcemy udostępniać osobom postronnym mogą mieć różnoraki charakter, stąd często spotykamy się z takim pojęciami jak:

- poufność danych/informacji
- poufność transakcji
- poufność płac/wynagrodzenia

Z uwagi na opisane powyżej niedogodności związane z przekazywaniem klucza prywatnego, często zamiast szyfrowania symetrycznego wykorzystane jest szyfrowanie asymetryczne.

Szyfrowanie przez przestawianie – metoda płotu

Szyfr przestawieniowy 

- metoda szyfrowania należąca do grupy klasycznych metod szyfrowania Szyfry te charakteryzują się tym, że w zaszyfrowanym tekście występują wszystkie znaki z tekstu jawnego, ale w innej kolejności, a tak powstałe słowo nazywamy anagramem.

Najprostszym przykładem szyfru przestawieniowego jest pisanie wspak.

S P O D E K -> K E D O P S

My natomiast zajmiemy się inną metodą szyfrowania – metodą płotu. Polega ona na tym, aby kolejne litery tekstu jawnego były zapisywane co najmniej w dwóch rzędach, a następnie za kryptogram przyjmujemy ciąg kolejnych liter z kolejnych rzędów począwszy od pierwszego.

SZYFROWANIE

Na początek zaszyfrujmy słowo:   Steganografia stosując dwa rzędy.

I    S E A O R F A

II   T G N G A I

Kryptogram: Seaorfatgngai

Szyfr polialfabetyczny 

– uogólnienie szyfru monoalfabetycznego na większą liczbę przekształceń.

Szyfr taki składa się z n przekształceń, takich że pierwszą literę szyfrujemy pierwszym przekształceniem, drugą drugim itd., po czym powtarzamy przekształcenia od początku począwszy od litery n+1. Szyfry polialfabetyczne mają współcześnie wyłącznie znaczenie historyczne.

Przykładami szyfrów polialfabetycznych są szyfr Vigenere'a i szyfr Beauforta.

Aby utrudnić zadanie kryptologom należy wyrównać częstość występowania znaków i ich sekwencji. Cel ten można osiągną między innymi stosując cyklicznie wiele alfabetów szyfrujących. Powstaje w ten sposób tzw. Szyfr polialfabetyczny (lub wieloalfabetyczny). Jako przykład rozważmy tu algorytm szyfru Vigenera (nie dokładnie, ale na nim oparty). Tablica (pole?) robocze tego szyfru ma 'kształt' kwadratu (w długości zależnej od języka) np. 26x26 (jeżeli chcielibyśmy go ujednolicić dla wszystkich języków będzie to 256x256 - tablica ASCII) i zawiera pewną liczbę (dla angielskiego 26) szyfrów monoalfabetycznych (np. ROT-1). I weźmy na przykład tablicę dla znaków języka angielskiego. Pierwszy wiersz, tzw. wiersz A zawiera litery zapisane w kolejności ABCD...WXYZ. Wiersz następny B zawiera np. BCDE...XYZA. Ostatni wiersz takiej tablicy - wiersz Z zawiera ZABC...VWXY. (Ilustracja tekiej tablicy na końcu artykułu).
       Podobnie jak szyfr monoalfabetyczny, również szyfr Vigenera ma klucz. Nie jest to jednak ciąg 26 różnych znaków, lecz zazwyczaj krótkie, łatwe do zapamiętania słowo, bądź fraza, np: PREHISTORIA. Aby zaszyfrować daną wiadomość, wpisujemy cyklicznie litery klucza ponad kolejnymi znakami tekstu źródłowego (jest to tylko ilustracja, mająca ułatwić zrozumienie tematu), w taki sposób:

P R E H I S T O R I A P R E H I S T O R

m a m u t y w y g i n e l y b a r d z o

I A P R E H I S T  ...

d a w n o t e m u  ...

(pominąłem tu znak ' ' w celu ułatwienia sobie zadania :) )

    
Litera klucza zapisana nad literą tekstu jawnego (źródłowego) określa, według którego wiersza (lub kolumny - bez różnicy) tablicy należy ją zaszyfrować. I tek: literę m szyfrujemy według wiersza P, literę a według wiersza R, kolejną literę m według wiersza E i tak dalej... Zatem te same litery tekstu źródłowego będą zależne od ich położenia w tym tekście (czyli: litera a może raz zostać zaszyfrowana jak np. c, a raz jako np. f). Podobnie di- i tri- gramy będą rozbite, przez zastępowanie ich różnymi sekwencjami znaków.


       Jeszcze trudniejszy do złamania szyfr uzyskujemy używając dla wierszy tablicy dowolnie wybranych szyfrów monoalfabetycznych, nie ograniczając się do jednego (np. szyfru Cezara). Jedynym problemem jest wtedy to, że wspomniana wyżej tablica 26 znaków jest częścią składową klucza szyfru i musiałaby być przechowywana i trzeba ją przechowywać na użytek każdego szyfranta osobno.

Wyszukiwanie wzorca w tekście

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 swszystkich 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.

Algorytmy w tekstach

Palindrom (gr. palindromeo – biec z powrotem) 

– wyrażenie brzmiące tak samo czytane od lewej do prawej i od prawej do lewej. Przykładem palindromu jest: Kobyła ma mały bok. Współcześnie palindromy pełnią funkcję gry słownej. Prawdopodobnie tak było również i w przeszłości, choć pewne znaleziska sugerują, że palindromy mogły też mieć znaczenie magiczne.

Sortowanie łańcucha znaków(tekstu)

- polega na alfabetycznym uporządkowaniu znaków zawartych w tekście.

Anagram 

– nazwa wywodząca się od słów greckich: ana- (nad) oraz grámma (litera), oznacza wyraz, wyrażenie lub całe zdanie powstałe przez przestawienie liter bądź sylab innego wyrazu lub zdania, wykorzystujące wszystkie litery (głoski bądź sylaby) materiału wyjściowego. W czasopismach szaradziarskich pojawiają się zadania polegające na odgadnięciu wykreskowanego anagramu na podstawie wierszowanego komentarza, a także anagramy rysunkowe polegające na ułożeniu hasła z wszystkich liter właściwego określenia rysunku. Formami spokrewnionymi z anagramem są stenoanagram, egzoanagram i endoanagram.

Najprostszy anagram to poukładanie liter w odwrotnej kolejności, np. kebab – babek. Przykładem jednego z prostych przestawień jest zamiana sylab w wyrazie ranty, dająca anagram: tyran. Przestawiając pojedyncze litery możemy otrzymać np. anagram narty.

W 1998 Barbara i Adam Podgórscy w swoim Vademecum szaradzisty (Wydawnictwo Kurpisz) jako rekordowy podało anagram złożony z 16 elementów: krasa, Arska, raska, sarka, askar, kasar, Raksa, sakra, Arkas, Araks, Karsa, rakas, Karas, Sakar, Skara, Askra. Nie należy go jednak traktować jako niezmiennik, ponieważ przybywa zarówno słów, jak i metod wyszukiwania. Już choćby w podanym „rekordzie” dociekliwy czytelnik zauważy brak jednego potocznego wulgaryzmu oraz słowa Ksara.

Zastosowanie programowania zachłannego

Dyskretny problem plecakowy (ang. discrete knapsack problem) 

- jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.

Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart  oraz waży . Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).

Decyzyjna wersja przedstawionego zagadnienia to pytanie "czy wartość co najmniej C może być osiągnięta bez przekraczania wagi W?"

Zachłanny algorytm, którego użycie w tym problemie wydaje się interesującą strategią, działa w kilku krokach:

• Najpierw szereguje przedmioty w kolejności nierosnącej, gdzie elementem porównawczym jest stosunek wartości przedmiotu do jego masy (sortowanie nierosnące względem wartości  - cena za jednostkę masy)
• Następnie metoda zachłanna próbuje umieścić w plecaku wpierw przedmiot o największej wartości k, potem kolejne rzeczy stojące za nim na posortowanej liście przedmiotów
• Gdy okaże się, że pewien przedmiot nie może zostać zapakowany do plecaka ze względu na przekroczenie pojemności, to jest on pomijany i następuje próba umieszczenia kolejnych przedmiotów aż do całkowitego wyczerpania miejsca w plecaku lub do momentu, kiedy nie będzie możliwe jakiekolwiek dodanie do plecaka przedmiotu jeszcze niezapakowanego – ze względu na przekroczenie ograniczenia.

Na poniższym schemacie przedstawimy rozwiązanie naszego przykładu metodą zachłanną:

Programowanie dynamiczne

Jak zapewne dobrze pamiętacie, sposób formułowania metod opartych na programowaniu dynamicznym został omówiony we poprzedniej lekcji. W skrócie polegał on na znalezieniu rekurencyjnych zależności między rozwiązaniami podproblemów różnego poziomu, a następnie na rozwiązywaniu coraz większych zadań i wykorzystania ich wyników do otrzymania głównego rozwiązania. Ten rodzaj algorytmów bardzo dobrze się zachowuje przy rozwiązywaniu wielu problemów optymalizacyjnych. Nie inaczej jest w przypadku problemu plecakowego.

W przypadku rozwiązywaniu zagadnienia upakowania przedmiotów potrzebna nam będzie dodatkowa tablica na przechowywanie cząstkowych wyników podproblemów – określmy ją jako P(i,j). W tablicy tej zapisywane będą mianowicie wartości optymalnych rozwiązań problemu upakowania, który będzie ograniczony do wyboru jedynie spośród pierwszych i przedmiotów, a pojemność plecaka będzie wynosić j. W trakcie rozwijania algorytmów zajmujących się upakowaniem plecaka opracowano wzór rekurencyjny na wartość P(i,j), który we sztandarowy sposób prezentuje możliwości programowania dynamicznego.

Otóż wartości tablicy P są obliczane zgodnie z poniższą zasadą:

Wytłumaczenie tego wzoru rekurencyjnego jest stosunkowo przejrzyste. Jeśli chcemy dodać do rozwiązania i-ty element, który jest cięższy od dopuszczalnej pojemności plecaka, to ten ruch jest automatycznie kwalifikowany jako nieopłacalny i nadal rozwiązanie optymalne składa się z przedmiotów o numerach 1..i-1. Natomiast jeżeli przedmiot i-ty, który zaczyna być w tej chwili brany pod uwagę, ma masę nie większą niż dopuszczalna „ładowność” plecaka, to porównujemy dwa przypadki:

1. optymalny podzbiór elementów zawiera element i-ty
2. optymalny podzbiór elementów nie zawiera elementu i-tego

Pierwszy przypadek jest opisany przez drugi parametr funkcji max w powyższym wzorze – do rozwiązania podproblemu z poprzedniego kroku dodajemy wartość ceny przedmiotu i-tego, a dostępną pojemność plecaka dla (i-1) przedmiotów zmniejszamy o tyle, ile miejsca w plecaku zajmuje przedmiot i-ty (czyli w_i).

Z wiadomych względów P(i,0) oraz P(0,j) są równe 0. Aby znaleźć całościowe rozwiązanie musimy wyznaczyć wartość P(n,W) – korzystając z rozwiązań najmniejszych podproblemów (właśnie tych o postaci P(0,x) lub P(y,0)), przechodząc do coraz większych i ostatecznie do P(n,W).

Skoro już omówiliśmy aspekt teoretyczny rozwiązywania problemu 0-1 knapsack przy zastosowaniu programowania dynamicznego, to możemy spróbować rozwiązać problem z rysunku znajdującego się na początku podrozdziału. Jak wiemy, należy odpowiednio przeliczyć wartości funkcji P – poniższe „drzewo rekurencji” pokazuje zależności między problemami i ich podproblemami – najpierw obliczamy wartości znajdujące się na samym dole drzewa, a następnie kroczymy z obliczeniami w górę, ostatnim kroku obliczając P(5,25).

Problem wydawania reszty 

– zagadnienie z dziedziny algorytmiki, problem polegający na wybraniu z danego zbioru monet o określonych nominałach takiej konfiguracji, by wydać żądaną kwotę przy użyciu minimalnej liczby monet. Jego rozwiązania są wykorzystywane w automatach z napojami, bankomatach itd.

Dane są trzy nominały – 1 zł, 2 zł i 5 zł. Ile minimalnie monet potrzeba, by wydać 13 zł?

Rozwiązanie

Poniżej pokazano dwa popularne rozwiązania tego problemu dla wariantu problemu, w którym zakłada się dostępność dowolnej liczby monet każdego nominału: jedno przy pomocy algorytmu zachłannego, drugie z wykorzystaniem programowania dynamicznego.

Niech:

k – żądana kwota; wg przykładu 13

n – największy element zbioru nominałów

x – liczba potrzebnych monet; początkowo 0

Algorytm zachłanny

Algorytm zachłanny jest poprawny dla tego problemu w większości stosowanych obecnie systemów monetarnych, jednak nie działa np. dla systemu (1, 4, 5) (kontrprzykładem jest kwota 8).

W tym przypadku, algorytm będzie wartość:

k – w każdym kroku pomniejszał o n

n – porównywał z wartością k, by stwierdzić, czy jest ona mniejsza lub równa

x – w każdym kroku zwiększał o 1

Algorytm odejmuje od zadanej kwoty największy spośród nominałów mniejszych i równych kwocie. Następnie, o ile kwota jest większa od zera, powtarza czynność. Liczba powtórzeń jest liczbą potrzebnych monet.

Dla powyższego przykładu algorytm zadziała następująco:

k	13	8	3	1
n	5	5	2	1
x	1	2	3	4