e zeszyt: kwietnia 2014

wtorek, 15 kwietnia 2014

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

Szyfrowanie asymetryczne

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.

Szyfrowanie

Kryptoanaliza zajmuje się zarówno odtworzeniem tekstu jawnego (danych przed zaszyfrowaniem) gdy nie jest znany klucz kryptograficzny jak i odtworzeniem samego klucza.

1. Przestawianie kolumnowe:

5kolumn:
K R Y P T
O A N A L
I Z A

szyfr odczytujemy rzędami: KOI RAA YN PA TL

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

3 Szyfry wieloalfabetyczne:

Słowo klucz(litery nie mogą się powtarzać):
BASI:
Mamy 4 alfabety:
B C D E F.... A
A B C... Z
S T U... R
I J K... H
I z każdego alfabtu wybieramy odpowiadające znaki, np. DRUK = ERUL
TELFON - ZNAK = SOLP

Wyszukiwanie wzorca w tekście

Algorytm Knutha-Morrisa-Pratta - algorytm wyszukiwania wzorca w tekście. Wykorzystuje fakt, że w przypadku wystąpienia niezgodności ze wzorcem, sam wzorzec zawiera w sobie informację pozwalającą określić gdzie powinna się zacząć kolejna próba dopasowania, pomijając ponowne porównywanie już dopasowanych znaków. Dzięki temu właściwy algorytm działa w czasie liniowym od długości przeszukiwanego tekstu i wzorca (co dla dużych wzorców ma znaczenie).
Algorytm został wynaleziony przez Donalda Knutha i Vaughana Pratta i niezależnie przez J. H. Morrisa w 1977, ale wszyscy trzej opublikowali go wspólnie.

wtorek, 1 kwietnia 2014

Algorytm wydawania reszty, palindromy, sortowanie tekstu oraz anagramy

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.

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.

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.

Problem plecakowy

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.

Definicja formalna: mamy do dyspozycji plecak o maksymalnej pojemności $B$ oraz zbiór $N$ elementów $\{x_1, x_j, ..., x_N\}$ , przy czym każdy element ma określoną wartość $c_{j}$ oraz wielkość $w_{j}$ .
Dyskretny problem plecakowy (ang. 0-1 knapsack problem)

formalnie problem może być zdefiniowany:

zmaksymalizuj $\sum_{j=1}^N c_j x_j.$

przy założeniach: $\sum_{j=1}^N w_j x_j \le B, \quad \quad x_j = 0\;\mbox{lub}\;1, \quad j=1,\dots,n.$

Problem plecakowy, w którym liczba elementów danego typu jest ograniczona przez podaną wartość (ang. bounded knapsack problem).

Formalnie:

zmaksymalizuj $\sum_{j=1}^N c_j x_j.$

przy założeniach: $\sum_{j=1}^N w_j x_j \le B, \quad \quad 0 \le x_j \le b_j, \quad j=1,\dots,n.$

Można rozważać także przypadek w którym nie ma wartości ograniczającej liczbę elementów danego typu (ang. unbounded knapsack problem).
W ciągłym problemie plecakowym można brać ułamkowe części przedmiotów.
W przypadku, gdy problem jest rozważany przy założeniach, że

jest problemem decyzyjnym
jest dyskretny
dla każdego elementu waga równa się wartości $w_j=c_j$

utożsamiany jest z problemem: czy dla danego zbioru liczb całkowitych istnieje taki jego podzbiór, że suma jego liczb wynosi dokładnie W? Zagadnienie to nazywane jest problemem sumy podzbioru.