mina86.com

Szyfr Cezara

Uważa się, że szyfr ten był używany przez Juliusza Cezara. W dzisiejszych czasach złamanie tego szyfru zajęłoby dosłownie sekundę, jednak wówczas szyfr ten był zupełnie wystarczający. Polega on na przesunięciu liter o trzy pozycje. W ten sposób napis "Projekt CODE" po zaszyfrowaniu wygląda tak: "Surmhnw FRGH". Szyfr Cezara można bardzo łatwo uogólnić do takiej postaci, że przesuwa się nie o 3, lecz o n znaków.

void encode(char *M, char n) {
	n %= 26;
	for (char c; *M, M++) {
		c = *M;
		if (c>='a' && c<='z') {
			*M = 'a' + (c - 'a' + n) % 26;
		} else if (c>='A' && c<='Z') {
			*M = 'A' + (c - 'A' + n) % 26;
		}
	}
}

void decode(char *M, char n) {
	encode(M, -n);
}

I jeszcze kod w "ciężkim" C++ (ktoś prosił więc dodaje). Dzięki dla Michała Jazłowieckiego za napisanie :)

#include <string>

using std::string;

void encode(string & s, char n) {
	n %= 26;
	for (string::iterator it = s. begin(); it != s. end(); ++it) {
		if (*it>='a' && *it<='z') {
			*it = 'a' + (*it - 'a' + n) % 26;
		} else if (*it>='A' && *it<='Z') {
			*it = 'A' + (*it - 'A' + n) % 26;
		}
	}
}

void decode(string & s, char n) {
	encode(s, -n));
}

Podstawianie znaków

Kolejnym, dość naturalnym, uogólnieniem Szyfru Cezara sposobem na szyfrowanie tekstu jest podstawianie znaków. Np. literze 'a' przypisujemy 'd', literze 'b' - 'j' i tak dalej. W ten sposób powstaje nam klucz, w którym jest zapisane jakie litery należy przyporządkować kolejnym literom. Przy tworzeniu takiego klucza należy pamiętać, że nie może być dwóch takich znaków, którym by sie przypisywało tą samą literę (coś takiego uniemożliwiłoby prawidłową deszyfracje). Implementacja funkcji szyfrującej (E()) tego algorytmu jest dość prosta:

void encode(char *M, char *key) {
	for (char c; c = *M; ++M) {
		if (c>='a' && c<='z') {
			*M = key + (c - 'a') | 32;
		} else if (c>='A' && c<='Z') {
			*M = (key + (c - 'A')) & ~32;
		}
	}
}

Deszyfracja (D()) jest troche trudniejsza z tego względu, że będzie trzeba szukać litery w kluczu a nie w alfabecie, a litery w kluczu nie są ułożone według jakiejś kolejności. Można zatem zastosować przeszukwianie liniowe:

void decode(char *M, char* key) {
	for (char c, i; c = *M; ++M) {
		if (c|32>='a' && c|32<='z') {
			c |= 32;
			for (i = 0; *(key+i)!=c && i<26; ++i);
			*M = i==26 ? '?' : ((*M & 32 ? 'a' : 'A') + i);
		}
	}
}

Lub na początku stworzyć klucz dekodujący:

void decode(char *M, char* key) {
	char dkey[26];
	for (char i = 0; i<26; ++i) {
		dkey[(key[i] & 31)-1] = 'a' + i;
	}
	encode(*M, dkey);
}

Powyższe funkcje są przystosowane do klucza 26 znakowego, czyli dla samych liter i to na dodatek ich wielkość nie odgrywa roli. Dość naturalnym rozszerzeniem będzie przyjęcie klucza również na duże znaki, znaki narodowe ('ą', 'ę', itp) cyfry... W najbardziej skrajnym przypadku można zrobić klucz dla wszystkich znaków ASCII albo nawet można nie podmieniać znaków tylko np. wordy, albo nawet dwordy. W tym przypadku należy jednakowoż pamiętać, że nie będzie można stosować konwencji C do zapisu łańcuchów znaków.

Podstawianie z kilkoma kluczami

	a	b	c	d
1.	b	c	d	a
2.	c	d	a	b
3.	d	a	b	c

Dalszym uogólnieniem i jednocześnie dużym utrudnieniem w złamaniu kodu jest użycie wielu kluczy przy szyfrowaniu. Przykładowo mamy 3 klucze oraz ciąg znaków 'abcdabcd'. Algorytm polega na tym, że pierwszy znak szyfruje się przy pomocy klucza pierwszego, drugi - drugiego, trzeci - trzeciego, czwarty - pierwszego i tak w kółko. . W efekcie (przy użyciu klucza z przedstawionej obok tabelki) E('abcdabcd') = 'bdbacadb'.

Warto zauważyć, że algorytm podstawiania znaków opisany powyżej można przedstawić jako podstawianie z kilkoma kluczami, gdzie liczba kluczy to jeden.

Implementacja algorytmu może wyglądać tak (ponownie w kluczy wzięto pod uwagę jedynie małe litery):

void encode(char *M, char **keys, int keys_count) {
	int k_num = 0;
	char *key;

	for (char c; c = *M; ++M) {
		key = *(keys+k_num);

		if (c>='a' && c<='z') {
			c = key + (c - 'a') | 32;
		} else if (c>='A' && c<='Z') {
			c = (key + (c - 'A')) & ~32;
		}

		*M = c;
		k_num = (k_num+1) % keys_count;
	}
}

void decode(char *M, char** keys, int keys_count) {
	int k_num = 0;
	char *key;

	for (char c, i; c = *M; ++M) {
		key = *(keys + k_num);
		if (c|32>='a' && c|32<='z') {
			c |= 32;
			for (i = 0; *(key+i)!=c && i<26; ++i);
			*M = i==26 ? '?' : ((*M & 32 ? 'a' : 'A') + i);
		}
		k_num = (k_num+1) % keys_count;
	}
}

Klucze powinno się tak tworzyć, aby żaden znak nie powtórzył się dwa razy na tej samej pozycji w dwóch różnych kluczach, a co więcej (z kompletnie nie znanych mi przyczyn) liczba kluczy powinna być nieparzysta.

Płotek

Płotek jest algorytmem opierającym swoje działanie na innych zasadach niż algorytmy przedstawione powyżej. Kluczem jest w nim pojedyncza liczba naturalna, która jest właściwie nieograniczona co to wartości, tyle że zbyt duża lub zbyt mała wartość powoduje, że szyfr jest dość słaby. Dla krótkich wiadomości liczba ta nie powinna być zbyt duża, choć jeżeli szyfrujemy Pana Tadeusza to można za klucz przyjąć liczby rzędu sto.

Algorytm polega na tym, że ity znak z wiadomości (licząc od jedynki) przesuwa się w dół o (i-1) % k, gdzie k to klucz. Po tym odczytujemy wiadomość od lewej do prawej, od góry do dołu, czyli normalnie. Aby dokonać to zrozumieć to zademonstruję ten algorytm praktycznie. Za klucz przejmijmy 5, a naszą wiadomością niech będzie 'Ala ma kota i dobrze jej tak':

Wiadomość: Ala ma kota i dobrze jej tak
   Płotek: A    a    a    o         t
            l              b    j    a
             a    k    i    r    e    k
                   o         z    j
               m    t    d    e
    Szyfr: Aaao tl  bjaakirek o zj mtde