Szyfr Afiniczny

Wstęp

Szyfrowanie

Szyfr Afiniczny jest to szyfr podstawieniowy co oznacza, że jednej literze tekstu jawnego odpowiada jedna litera alfabetu tajnego. Podczas szyfrowania tą metodą kluczem jest para liczb naturalnych (a, b). Wtedy szyfrowana litera l jest wyliczana z funkcji f(l) = al + b mod m. Litera m we wzorze oznacza liczbę liter w alfabecie. W przypadku alfabetu angielskiego m = 26, a w przypadku polskiego m = 32.

Należy też zauważyć, że nie każda para liczb (a, b) może zostać użyta do szyfrowania. Funkcja f(l) musi być funkcją różnowartościową - inaczej dana litera z tekstu jawnego będzie reprezentowana przez dwie różne litery, albo odwrotnie. Przez to może stać się niemożliwe odczytanie tekstu jawnego. Równanie f(l) = al + b mod m ma tylko jedno rozwiązanie wtedy i tylko wtedy, gdy największy wspólny dzielnik liczb a i m wynosi 1. Oznacza to, że jedna z wartości a lub m musi być liczbę pierwszą. W przypadku, gdy obie są pierwsze to jedna nie może być równa drugiej.

W przypadku, gdy a = 1 to b może przyjąć dowolną wartość. Jest to szczególny przypadek, który jest znany jako Szyfr Cezara.

Deszyfrowanie

W celu deszyfrowania danych należy skorzystać z wzoru g(l) = a^-1(y - b) mod m. Należy pamiętać, że a^-1 jest odwrotnością liczby w pierścieniu .

Przykłady

Załóżmy, że do zaszyfrowania jest słowo TEST. Dla ułatwienia warto przyjąć, że wyraz jest zapisany przy pomocy alfabetu łacińskiego co oznacza, że m = 26. W takiej sytuacji za a można przyjąć dowolną liczbę pierwszą z przedziału [1, 26]. Wartość b jest dowolna, dlatego można przyjąć, że wyraz będzie szyfrowany przy pomocy pary (7, 4). Wtedy dla każdej litery należy obliczyć wartość funkcji f(l):

Ostatecznie zaszyfrowany tekst TEST to HGAH. Teraz w celu rozszyfrowania danych należy wyznaczyć odwrotność wartości a. W przypadku pierścienia wartość odwrotna do 7 to 15. Sposób rozszyfrowania jest analogiczny do szyfrowania:

Implementacja

Założenia

W przykładowej implementacji zostało przyjęte, że szyfrowany tekst składa się tylko z małych liter alfabetu łacińskiego.

Szyfrowanie

Szyfrowanie danych polega na przetłumaczeniu zapisu matematycznego na informatyczny:

1. char* cipher(char* txt, int a, int b){
2.   char* wynik = new char[strlen(txt) + 1];
3.   for(int i = 0; txt[i]; i++)
4.     wynik[i] = 'a' + (((txt[i] - 'a') * a + b) % 26);
5.   wynik[strlen(txt)] = '\0';
6.   return wynik;
7. }

Deszyfrowanie

Podczas deszyfrowania danych zasadniczą trudnością jest znalezienie odwrotności a. W tym przypadku (3. - 5.) została wykorzystana metoda naiwna. Lepszym pomysłem jest wykorzystanie Rozszerzonego Algorytmu Euklidesa.

1. char* decipher(char* txt, int a, int b){
2.   char* wynik = new char[strlen(txt) + 1];
3.   int x = 1;
4.   while((a*x) % 26 != 1)
5.     x++;
6.   for(int i = 0; txt[i]; i++)
7.     wynik[i] = 'a' + ((x * (txt[i] - 'a' - b + 26)) % 26);
8.   wynik[strlen(txt)] = '\0';
9.   return wynik;
10. }

Testowanie funkcji

Powyższe funkcje można przetestować przy pomocy poniższej funkcji main(). Program na początek oczekuje dwóch liczb a i b, a w następnej linijce tekstu do zaszyfrowania:

1. int main () {
2.   int a, b;
3.   cin >> a >> b;
4.   cin.ignore();
5.   char* txt = new char[128];
6.   cin.getline(txt, 128);
7.   char* txtc = cipher(txt, a, b);
8.   cout << txtc << endl;
9.   char* txtd = decipher(txtc, a, b);
10.   cout << txtd << endl;
11.   system("pause");
12.   return 0;
13. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz program, który w trzeciej linijce będzie przyjmował alfabet z jakiego składa się podany tekst do zaszyfrowania. Dane powinny być szyfrowane zgodnie z podanym alfabetem. Można założyć, że wprowadzone dane są poprawne.

Przykładowo dla danych:

1. 7 4
2. informacja
3. acfijmnor

otrzymujemy:

1. ocarnijfmj

• Kod źródłowy Zadanie 1