podstawy szyfrowania informacji.pdf

(194 KB) Pobierz
Dokument1
BSK
KATARZYNA TYBICKA- FRANCIK
PODSTAWY SZYFROWANIA INFORMACJI
W swiecie wymiany informacji, w którym obecnie króluje globalna siec Internet, coraz
czesciej pojawia sie zagadnienie tajnosci danych przesylanych w sieci. Prawde mówiac problem
ten nie jest nowy, nie zrodzil sie on wraz z era maszyn liczacych i sieci komputerowych. Borykali
sie z nim juz starozytni i oni tez opracowali pierwsze sposoby ochrony informacji przed oczyma
niepowolanych osób. Metoda byla bardzo prosta: szyfrowanie.
Wyróznia sie dwa sposoby szyfrowania informacji: za pomoca szyfrów przestawieniowych oraz
za pomoca szyfrów podstawieniowych. W wyniku zlozenia tych dwu metod otrzymujemy nowa
klase szyfrów, szyfry kaskadowe, które sa znacznie bezpieczniejsze od swych poprzedników.
1.1. Szyfry przestawieniowe
Szyfry przestawieniowe zmieniaja porzadek znaków wedlug pewnego schematu.
Przestawienia tego dokonuje sie za pomoca pewnej figury geometrycznej, do której wpisuje sie
tekst w sposób okreslony sciezka zapisu , a potem odczytuje sie tekst zgodnie z pewna sciezka
odczytu .
Tekst jawnyfiFigurafiTekst zaszyfrowany
zapis odczyt
Przykladem takiego szyfru jest szyfr plotkowy. Tekst zaszyfrowany otrzymuje sie przez zapis
w ksztalcie „plotka”, a nastepnie odczytuje sie wierszami informacje. Klucz K tego szyfru
okreslony jest wysokoscia tego „plotka”.
Przyklad (dla K = 3):
BEZPIECZENSTWO_SIECI_KOMPUTEROWYCH
tekst jawny
B EZP I ECZ E NST W O_S I ECI _ KOM P UTE R OWY C H
B E Z P I E C Z E N S T W O _ S I E C I _ K O M P U T E R O W Y C H
figura
BE Z PIE C ZEN S TWO _ SIE C I_K O MPU T ERO W YCH
BIEWI_PRCEPEZNTOSEIKMUEOYHZCS_COTW
wiadomosc zaszyfrowana
BSK
KATARZYNA TYBICKA- FRANCIK
Czesto figura jest macierz dwuwymiarowa. Tekst jawny zapisuje sie do macierzy wierszami.
Tekst zaszyfrowany powstaje przez odczytanie kolumn w okreslonym porzadku.
Przyklad: Uzywajac macierzy 3x4 szyfrujemy slowo „MARCYPANKOWY” .
1 2 3 4
Tekst zaszyfrowany po odczycie kolumn w kolejnosci 2-4-1-3
M. A R C
Bedzie mial postac:
Y P A N
APOCNYMYKRAW
K O W Y
Macierz moze byc n-wymiarowa.
Wiele szyfrów przestawieniowych zmienia kolejnosc znaków tekstu przy zastosowaniu
pewnego stalego okresu d . Niech Z d jest zbiorem liczb calkowitych od 1 do d , a f: Z d fi Z d
permutacja na zbiorze Z d . Kluczem takiego szyfru jest para K=(d, f) . Kolejne bloki d znaków sa
szyfrowane przez dokonanie permutacji znaków zgodnie z f .
Przyklad:
d=4
f jest permutacja i: 1 2 3 4
f(i): 2 4 1 3
UWAGA_SCISLE_TAJNA_WIADOMOSC
tekst jawny
WGUA_CASSEILTJ_AAWN_AOIDOCMS
wiadomosc zaszyfrowana
W rzeczywistosci dwa poprzednie sposoby szyfrowania sa szczególnymi przypadkami
trzeciego. Bardzo latwo jest rozpoznac, czy dany szyfr jest szyfrem przestawieniowym.
Czestotliwosc wystepowania liter w tekscie jawnym jest taka sama jak czestotliwosc
wystepowania tych samych liter w tekscie zaszyfrowanym.
1.2. Szyfry podstawieniowe
Szyfry podstawieniowe dzielimy na cztery typy: monoalfabetyczne, homofoniczne,
wieloalfabetyczne i poligramowe.
1.2.1. Szyfry monoalfabetyczne
Szyfry monoalfabetyczne zamieniaja kazdy znak uporzadkowanego alfabetu jawnego na
odpowiedni znak uporzadkowanego alfabetu szyfru. Bardzo czesto alfabet szyfru powstaje
z alfabetu jawnego przez prosta zamiane kolejnosci znaków w alfabecie jawnym (permutacja).
2
21336705.002.png 21336705.003.png
BSK
KATARZYNA TYBICKA- FRANCIK
Jesli alfabet jawny ma a 1 , a 2 , ..., a N-1 , wtedy alfabet szyfru ma postac f(a 1 ) , f(a 2 ) , ..., f(a N-1 ), przy
czym f jest odwzorowaniem wzajemnie jednoznacznym (bijekcja). Kluczem jest alfabet szyfru lub
funkcja f .
Przyklad:
alfabet jawny: A B C D E F G H I J K L M N O P R S T U W X Y Z
alfabet szyfru: D E F G H I J K L M N O P R S T U W X Y Z A B C
tekst jawny:
SYSTEM
tekst zaszyfrowany:
WBWXHP
Powyzszy przyklad jest szczególnym przypadkiem szyfru podstawieniowego, gdyz szyfr
powstal na „alfabecie przesunietym” zwanym tez szyfrem Cezara [1, 2, 3] .
Funkcja f ma wtedy postac:
f(a) = (a+k) mod N
gdzie:
N – dlugosc alfabetu,
k – przesuniecie w prawo,
a – oznacza pozycje litery w alfabecie .
Innym przypadkiem szyfru podstawieniowego jest szyfr oparty na mnozeniach zwany
„przerzedzonym”. Funkcja f ma postac:
f(a) = (s*k) mod N
przy czym k oraz N sa wzglednie pierwsze. Jesli k i N nie sa liczbami wzglednie pierwszymi, to
wielu literom tekstu jawnego bedzie odpowiadac ta sama litera tekstu zaszyfrowanego.
Dwie powyzsze metody mozna polaczyc i otrzymamy wtedy szyfr „afiniczny”.
f(a) = (a * k 1 + k 0 ) mod N
gdzie:
k 0 – przesuniecie w prawo,
k 1 – wspólczynnik przerzedzenia.
Ogólny wzór przeksztalcenia wyzszego rzedu otrzymuje sie z przeksztalcen wielomianowych
stopnia t
f(a) = (a t *k t + a (t-1) *k (t-1) + ... a*k 1 + k 0 ) mod N
3
 
BSK
KATARZYNA TYBICKA- FRANCIK
1.2.2. Szyfry homofoniczne
Szyfry homofoniczne odwzorowuja kazdy znak a i alfabetu jawnego A na zestaw elementów
tekstu zaszyfrowanego, zwanych homofonami. W ten sposób odwzorowanie tekstu jawnego na
zaszyfrowany mozna okreslic jako funkcje:
f: AfiB
gdzie B jest alfabetem szyfrujacym, skladajacym sie z podzbiorów b i , bedacych zbiorami
homofonów odpowiadajacych a i
Tekst jawny M=m 1, m 2 , ... podlega szyfrowaniu jako b=c 1 , c 2 , ... gdzie znak c i wybierany jest
losowo ze zbioru homofonów f(m i ) .
Przyklad:
Litera Homofony
A
17 19 34 41 56 60 67 83
I
08 22 53 65 88 90
L
03 44 76
N
02 09 15 27 32 40 59
O
10 11 23 28 42 54 70 80
P
33 91
T
05 10 20 29 45 58 64 78
Tekst jawny: P I L O T
Tekst zaszyfrowany: 91 53 03 80 64
lub:
33 08 76 80 05
Szyfry homofoniczne moga byc duzo trudniejsze do zlamania niz zwykle szyfry
podstawieniowe, szczególnie w przypadkach, gdy liczba homofonów przydzielonych literze jest
proporcjonalna do wzglednej czestosci jej wystepowania. Oczywiscie im wiecej homofonów
przydzielimy literom, tym silniejszy tworzymy szyfr.
W wiekszosci szyfrów jest mozliwe jego zlamanie, gdy posiadamy odpowiednio duza ilosc
tekstu zaszyfrowanego [4]. Wynika to z faktu, ze istnieje tylko jeden klucz K , którego uzycie do
deszyfrowania daje w wyniku zrozumialy tekst jawny. Istnieje jednak mozliwosc stworzenia
szyfru homofonicznego wyzszego stopnia, dla którego kryptogram mozna zdeszyfrowac na wiecej
niz jeden sensowny tekst.
Aby skonstruowac taki szyfr drugiego stopnia (kazdemu tekstowi zaszyfrowanemu
odpowiadaja dwa teksty jawne), nalezy macierz K(NxN) wypelnic losowo liczbami od 1 do N 2 .
Wiersze i kolumny odpowiadaja znakom alfabetu jawnego. Dla kazdego znaku a tekstu jawnego
4
21336705.004.png
BSK
KATARZYNA TYBICKA- FRANCIK
wiersz a macierzy tworzy jeden zbiór homofonów f 1 (a) , zas kolumna a tworzy zbiór f 2 (a) .
Wlasciwy tekst jawny M=m 1 , m 2 ,... szyfrujemy z tekstem falszywym X=x 1 , x 2 ,..., tworzac
kryptogram C=c 1 , c 2 ,..., gdzie c i = K(m. i , x i ) dla i = 1, 2, ...
Przyklad:
N=5 , {A, I, K, L}
\ A I J K L
Tekst „lalka” szyfrujemy tekstem falszywym „kajak” .
A 10 22 18 02 11
Tekst zaszyfrowany:
I 12 01 25 05 20
L A L K A
J 19 06 23 13 07
K A J A K
K 03 16 08 24 15
14 10 21 03 02
L 17 09 21 14 04
1.2.3. Szyfry wieloalfabetyczne
Szyfry monoalfabetyczne zachowuja rozklad czesciowy wystepowania znaków tekstu
jawnego. Szyfr homofoniczny ukrywa ten rozklad przez przypisanie danej literze wielu symboli
(homofonów). Szyfr wieloalfabetyczny takze ukrywa ten rozklad, ale robi to przez uzycie wielu
podstawien. Twórca szyfrów wieloalfabetycznych jest Leon Batista Alberti [5, 6, 7, 8, 9] .
Skonstruawal on dysk szyfrowy, skladajacy sie z dwóch kól. Na zewnetrznym znajdowaly sie
litery alfabetu jawnego (24 znaki), na wewnetrznym ruchomym znajdowaly sie litery alfabetu
szyfrowego. Dzieki temu dysk ten definiuje 24 mozliwe podstawienia (zamiana tekstu jawnego na
litery kryptogramu z kola wewnetrznego), które oczywiscie mozemy zmienic co pewien okres d
(znak tekstu) przez obrót kola.
Przykladem szyfru podstawieniowego wieloalfabetycznego jest szyfr Vigene’a [5]. Klucz
szyfru K tworzy sekwencja liter K=k 1 , k 2 , ... k d , gdzie k i (i=1, ... d) daje liczbe przesuniec w i -tym
alfabecie:
f i (a) = (a + k i ) mod N
Przyklad:
Szyfrujemy slowo „lekkoatletka” z uzyciem klucza czad .
Tekst jawny:
L E K K O A T L E T K A
Klucz:
C Z A D C Z A D C Z A D
Tekst zaszyfrowany:
N D K N Q Z T O G S K D
Pomocna przy szyfrowaniu i deszyfrowaniu jest tablica Vigenere’a. Czesc tej tablicy
przedstawiona jest ponizej:
5
21336705.001.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin