Kurs C++
Matura z informatyki
KONKURS FRAKTAL
Ćwiczenia
Warsztaty
Logowanie
Szyfr Cezara
Zacznijmy od wyjaśnienia idei szyfru Cezara. Jest to jeden z najprostszych szyfrów przesuwających. Polega ona na przesunięciu każdej litery o pewną stałą wartość zwaną kluczem. Prześledźmy przykład:
Zaszyfrujmy słowo Marcin kluczem o wartości równej -2. A więc każdą literę przesuwamy w lewą stronę o dwie wartości:
| Przed szyfrowaniem | Po szyfrowaniu |
| M | K |
| a | y |
| r | p |
| c | a |
| i | g |
| n | l |
Oczywiście szyfrowanie odbywa się w zakresie liter alfabetu łacińskiego. Aby zaszyfrować literę a należy się cofnąć do końca alfabetu i będzie to litera y:
{tex}... x\ \overbrace{y}^{"a"\ po\ zaszyfrowaniu}\ z\ \overbrace{a}^{\overleftarrow{2}}\ b\ c\ ...{/tex}
Słowo "Marcin" po zaszyfrowaniu wygląda następująco: "Kypagl".
Aby zdeszyfrować dane słowo należy przesunąć każdy znak o {tex}-\ klucz{/tex}, czyli w tym przypadku o {tex}-(-2)=2{/tex}.
Szyfr Cezara jest szyfrem symetrycznym, ponieważ do szyfrowania i deszyfrowania wykorzystujemy ten sam klucz, dodatkowo jest to szyfr podstawieniowy (litery nie zmieniają swojego położenia, tylko zostają podmienione na inne).
Przeanalizujemy przypadek szyfrowania dużych liter o kluczu z przedziału {tex}[-26..26]{/tex}.
Załóżmy, że klucz ma wartość {tex}- 2{/tex}. Każdą literę musimy przesunąć o {tex}2{/tex} w lewo. Dla liter powyżej litery {tex}B{/tex} problem jest trywialny. Dla liter {tex}A{/tex} i {tex}B{/tex} należy odliczyć odpowiednią liczbę znaków począwszy od {tex}Z{/tex} w dół.
Natomiast dla klucza równego {tex}2{/tex} aby zaszyfrować literę {tex}Z{/tex} musimy przejść do początku alfabetu i tu odliczyć dwa znaki.
Rozwiązanie w C++ (dla dużych liter języka łacińskiego):
#include<iostream> #include<cstdlib> using namespace std; void szyfruj(int klucz, char tab[]) { int dl = strlen(tab); //określenie ilości znaków wyrazu //sprawdzenie, czy klucz miesci sie w zakresie if(!(klucz >= -26 && klucz <= 26)) return; if(klucz >= 0) for(int i=0;i<dl;i++) if(tab[i] + klucz <= 'Z') tab[i] += klucz; else tab[i] = tab[i] + klucz - 26; else for(int i=0;i<dl;i++) if(tab[i] + klucz >= 'A') tab[i] += klucz; else tab[i] = tab[i] + klucz + 26; } int main() { char tab[1001]; //tablica znaków - max 1000 znaków. int klucz; cout<<"Podaj wyraz składający się z dużych liter: "; cin>>tab; cout<<"Podaj klucz z przedziału [-26..26]: "; cin>>klucz; szyfruj(klucz,tab); //szyfrowanie cout<<"Po zaszyfrowaniu: "<<tab<<endl; szyfruj(-klucz,tab); //deszyfrowanie cout<<"Po rozszyfrowaniu: "<<tab<<endl; system("pause"); return 0; } |
Szyfrowanie małych liter
Do poprawnego szyfrowania małych liter należy zmodyfikować funkcję zamieniając znak A na a oraz Z na z:
void szyfruj(int klucz, char tab[]) { int dl = strlen(tab); //określenie ilości znaków wyrazu //sprawdzenie, czy klucz miesci sie w zakresie if(!(klucz >= -26 && klucz <= 26)) return; if(klucz >= 0) for(int i=0;i<dl;i++) if(tab[i] + klucz <= 'z') tab[i] += klucz; else tab[i] = tab[i] + klucz - 26; else for(int i=0;i<dl;i++) if(tab[i] + klucz >= 'a') tab[i] += klucz; else tab[i] = tab[i] + klucz + 26; } |
Szyfrowanie uniwersalne
W tym miejscu przedstawię program, który szyfruje całe zdania bez względu na wielkość liter. Dla odmiany rozwiązanie korzysta z klasy string:
#include<iostream> #include<cstdlib> #include<string> using namespace std; inline int sprawdz(char znak) { //jesli jest mala litera if(znak >= 'a' && znak <= 'z') return 0; //jesli jest duza litera if(znak >= 'A' && znak <= 'Z') return 1; //inna niż litera return 2; } void szyfruj(int klucz, string &tab) { //sprawdzenie, czy klucz miesci sie w zakresie if(!(klucz >= -26 && klucz <= 26)) return; int pom; char a, z; for(int i = 0; i < tab.size(); i++) { pom = sprawdz(tab[i]); //ustalienie wielkosci litery if(pom < 2) { if(pom == 0) a = 'a', z = 'z'; else a = 'A', z = 'Z'; if(klucz >= 0) if(tab[i] + klucz <= z) tab[i] += klucz; else tab[i] = tab[i] + klucz - 26; else if(tab[i] + klucz >= a) tab[i] += klucz; else tab[i] = tab[i] + klucz + 26; } } } int main() { string tab; int klucz; cout<<"Podaj zdanie do zaszyfrowania: "; getline(cin, tab); cout<<"Podaj klucz z przedziału [-26..26]: "; cin>>klucz; szyfruj(klucz,tab); //szyfrowanie cout<<"Po zaszyfrowaniu: "<<tab<<endl; szyfruj(-klucz,tab); //deszyfrowanie cout<<"Po rozszyfrowaniu: "<<tab<<endl; system("pause"); return 0; } |
Alternatywne rozwiązanie (być może bardziej zrozumiałe)
Założenia:
- klucz jest znany, na przykład równy 3
- szyfrujemy duże litery
Popatrzmy teraz na kilka początkowych i ostatnich znaków w alfabecie:
{tex}A,\ B,\ C,\ ...,\ W,\ X,\ Y,\ Z{/tex}
Zauważmy, że począwszy od znaku X, gdy przesuniemy tą literę o 3 miejsca to wyskoczymy poza alfabet. W takiej sytuacji możemy rozpatrzeć oddzielnie przypadki dla liter X, Y oraz Z (tak zwane "wyifowanie" przypadków).
Deszyfrowanie opiera się na tej samej idei.
Rozwiązanie alternatywne:
#include<iostream> #include<cstdlib> #include<cstring> using namespace std; void szyfruj(char tab[]) { //zakładamy, że klucz ma wartosć 3 int i=0; while(tab[i]) { if(tab[i] == 'X') tab[i] = 'A'; else if(tab[i] == 'Y') tab[i] = 'B'; else if(tab[i] == 'Z') tab[i] = 'C'; else if(tab[i]<'X') tab[i]+=3; ++i; } } void deszyfruj(char tab[]) { //zakładamy, że klucz ma wartosć 3 int i=0; while(tab[i]) { if(tab[i] == 'A') tab[i] = 'X'; else if(tab[i] == 'B') tab[i] = 'Y'; else if(tab[i] == 'C') tab[i] = 'Z'; else if(tab[i] > 'C') tab[i]-=3; ++i; } } int main() { char tab[1001]; //tablica znaków - max 1000 znaków cout<<"Podaj wyraz składający się z dużych liter: "; cin>>tab; szyfruj(tab); //szyfrowanie cout<<"Po zaszyfrowaniu: "<<tab<<endl; deszyfruj(tab); //deszyfrowanie cout<<"Po rozszyfrowaniu: "<<tab<<endl; system("pause"); return 0; } |