Kodowanie teksu [cz. 1]...

|PtaH|

Za zaliczenie musiałem napisać program, który by ilustrował kilka prosrych algorytmów kodowania tekstu oraz ich słabych stron:

  1. Szyfry podstawieniowe monoalfabetyczne.

Polagają one na zamianę znaku teksu jawnego na odpowiedni znak kryptogramu, przyczym dla całej wiadomość stosuje się odwzorowanie [i]jeden do jednego[/i].

Przykładem tego szyfru może być tzw. szyfr Cezara. Polega on na przyporządkowaniu każdej literze alfabetu łacińskiego liczby(A=0, B=1...) i przesunięciu każdej liczby o k np. równe 3 (ma tu miejsce tzw. przewijanie - gdy konczy sie alfabet przesuwamy sie do jego poczatku). Zakres można oczywiście rozszerzyć o zbiór znaków ASCI lub jakiś inny skończony zbiór znaków n. Funkcja szyfrująca więc będzie wyrażana wzorem:
[b]F(a)=(a+k) mod n[/b]
Co w w cpp wyglada następująco:

   for (int i = 0; i <= strlen(napis) - 1; i++)
   napis[i]=(napis[i]+k) % 255;

Aby odkodować ten tekst należy odjąć wartość k.

Można tez stosować przekształcenia wyższego rzędu.
Hmm. W sumie przyznam się, że nie wiem gdzie mam umieścić algoytm sortowania ROT-13, wiele osób się sprzecza czy to algorytm podstawieniowy monoalfabetyczny czy nie. Moim zdaniem jest. Dlatego tutaj wklejam kod:

char* rot13(char* napis)
{
   for (unsigned int i = 0; i <= strlen(napis) - 1; i++)
   {
      if (napis[i] >= 'A' && napis[i] <= 'M')
         napis[i] = char (napis[i] + 13);
      else if (napis[i] >= 'N' && napis[i] <= 'Z')
         napis[i] = char (napis[i] - 13);
      if (napis[i] >= 'a' && napis[i] <= 'm')
         napis[i] = char (napis[i] + 13);
      else if (napis[i] >= 'n' && napis[i] <= 'z')
         napis[i] = char (napis[i] - 13);
   }
   return napis;
}

Algorytm kodowania, jest również algorytmem dekodowania.

Następnym szyfrem tego typu może być np. NOT'owanie (negowanie*). W tym sposobie mamy doczynienia z czystą matematyką. Negacja polega na tym, że jeżeli np. mamy liczbę zapisaną w systemie binarnym 1110001 to operacja negacji spowoduje odwrucenie bitów, czyli uzyskamy 0001110. Algorytm kodowania, jest również algorytmem dekodowania.

char* not(char* napis)
{
   for (unsigned int i = 0; i <= strlen(napis) - 1; i++)
      napis[i] = ~(napis[i]);
   return napis;
}

W niektórych szyfrach podstawieniowych monoalfabetycznych używano również niestandardowych alfabetów szyfrowych. Np. szyfr cmentarny, gdzie klucz utworzono za pomocą rusunków stosowanych w grze kółko i krzyrzyk.

Na koniec omawiania szyfrów monoalfabetycznych należy wspomnieć, że wiekszość z nich jest w prosty sposób łamana na podstawie analizy częstości występowania liter lub znaków (nawet przy ataku bez tekstu jawnego). Z tego powodu ich praktyczne znaczenie jest znikome.

  1. Szyfry podstawieniowe wieloalfabetyczne.

Stosuje się w nich wieleodwzorowań jednego znaku tekstu jawnego na znaki kryptogramu, przyczym każde odwzorowanie jest jeden do jednego, podobnie jak w szyfrach monoalfabetycznych. Jak więc widzimy szyfry wieloalfabetyczne ukrywają częstotliwość występowania znaków przez użycie wielu podstawień. Większość szyfrów tej grupy to szyfry okresowe o okresie d znaków. Klasycznym przykładem jest szyfr powstały w XVI wieku [b]szyfr Vigenere'a[/b].

Szyfrowanie polega tu na podstawie dowolnie wybranego słowa kluczowego (hasla). Do numeru (np. ASCI) 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 od początku. Przykład funkcji dla znaków ASCI:
[b]Fx=(a+k[x]) mod 255[/b]
Przykład:

char* koduj(char* tekst, char* haslo)
{
   unsigned int j = 0;
   for(unsigned int i = 0; i <= strlen(tekst); i++)
   {
      tekst[i] = char(tekst[i] + haslo[j]);
      if (j < strlen(haslo) - 1) j++; else j = 0;
   }
   return tekst;
}

Dekodowanie:
[b]Fx=(a-k[x]) mod 255[/b]
Przykład:

char* koduj(char* tekst, char* haslo)
{
   unsigned int j = 0;
   for(unsigned int i = 0; i <= strlen(tekst); i++)
   {
      tekst[i] = char(tekst[i] - haslo[j]);
      if (j < strlen(haslo) - 1) j++; else j = 0;
   }
   return tekst;
}

Szczególną odmianą może tu być popularnie zwane XOR'owanie.
Na początek może wyjaśnie co to jest sama operacja xorowania. Jest tzw. dodawanie bez przeniesienia* tzn.:
np. jeżeli dodajemy liczbę 12(dec) czyli 1100(bin) i 15(dec) czyli 1111(bin) otrzymamy 0011(bin) czyli 3(dec). Jak to wygląda:
[quote]
1- powinna wyjść z przeniesienia, ale pomijamy ją
1100
xor 1111

  0011

[/quote]
Najpierw dodajemy pisemnie obydwie liczby (system dwójkowy). Czyli 0+1=1, 0+1=0, 1+1=0(jedynka na przenisienie), 1+1=0, co po przeliczeniu daje 3(dec).
Wzór jest podobny jak powyżej:

char* xoruj(char* tekst, char* haslo)
{
   unsigned int j = 0;
   for(unsigned int i = 0; i <= dlugosc; i++)
   {
      tekst[i] = char(tekst[i] ^ haslo[j]);
      if (j < strlen(haslo) - 1) j++; else j = 0;
   }
   return tekst;
}

Okresowe szyfry wieloalfabetyczne również nie należą do najbezpieczniejszych. Po wyznaczeniu okresu takiego szyfru jest on bezproblemowo łamany. Do wyznaczaniu okresu szyfru służa dwie metody: wskaźnika zgoność i Kasiskiego.

I to już będzie koniec, niestety.
Wkrótce zapraszam na dalszą część.

  • Dla przyszłych studentów informatyki (Politechniki Koszalińskiej). Ostrzegam, że na pierwszym roku będzie trzeba znać nie tylko xorowanie, negacje itd. będzie trzeba jeszcze skutecznie umieć posługiwać się różnym kodowaniem liczb, niestety nie tylko będzie bin, hex, dec, oct, tylko takie brzydactwa jak kody ud, kd, kod Grey'a. I w nich jeszcze będzie trzeba wykonywać wszystkie działania.

8 komentarzy

Ja mam zajęcia z mgr. Maslennikowa i jeszcze nie jest tak strasznie :)

Hę? Studiujesz na PK? Który rok? :)
A kody pewnie u Zgreda :] To jest pikuś - później u niego będzie ciekawiej - stoisz przy tablicy na wykładzie i wypełniasz tabelkę zerami i jedynkami - jest ich tak na oko 200 :)

Jestem co prawda na pierwszym roku i nie wiem jeszcze o kim mówi się Zgreda! ale się z chętnie dowiem=]

tragiczne literówki i błędy ortograficzne, popraw to!!!
a co do wymagań wobec studentów 1 roku PK - ode mnie na pierwszym semestrze (!) PW wymagano chyba trochę więcej (operacje na liczbach zepolonych, macierzach, całkowanie, na drugim dorzucili funkcje uwikłane, residua, liczenie fft "na piechotę"). niech się Gray schowa, ULOGi były jednym z łatwiejszych przedmiotów.

btw: algorytm rot13 można zapisać krócej (inaczej warunki).

1) Popraw błędy, bo takich to jeszcze nie widziałem :)
2) Dariusz Gretkowski - będziesz u niego pisemnie realizował m.in. instrukcje MMX [rotfl]
3) No, ale to powinny być komentarze do artykułu - prawdopodobna kontynuacja rozmowy na IRCu.

nie poruszałem tematu matematyki bo owszem też mam liczby zespolone, całki, macierze itd... btw na PW zabrakło mi <ort>dwuch</ort> punktów

Łukasz - wszystko co wymieniłeś również mieliśmy - nie oceniaj uczelnii po jakimś artykule. Nie twierdzę, że to dobra uczelnia, ale są zdecydowanie gorsze. I też liczyłem FFT na piechotę, residua, czy funkcje uwikłane - więc spokojniej ;) A zespolone to miałem już w 2 klasie szkoły sredniej :] Ale jak pisałem w ostatnim komentarzu - takie rozmowy można przenieść na prv - ewentualnie na forum, ale nie widzę ku temu powodów. Pzdr.

Ja wybieram sie na PK w pszyszylm roku i z tego co slysze ne jest tam tak zle... no jezeli ktos lubi takie zeczy. a propo artu. mozna bylo to troche lepiej napisac ;)