Kurs maturalny z języka angielskiego!
kurs-maturalny-jezyk-angielski

PROGRAMOWANIE I ALGORYTMY

Zajęcia maturalne z informatyki
Olimpiada Informatyczna Juniorów
    Prowadzący: Marcin Kasprowicz
  • właściciel serwisu algorytm.edu.pl
  • wrzesień 2024 — start zajęć
  • czytaj więcej

Szyfr Cezara


powrót

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:

$$... x\ \overbrace{y}^{"a"\ po\ zaszyfrowaniu}\ z\ \overbrace{a}^{\overleftarrow{2}}\ b\ c\ ...$$

Słowo "Marcin" po zaszyfrowaniu wygląda następująco: "Kypagl".

Aby zdeszyfrować dane słowo należy przesunąć każdy znak o $$-\ klucz$$, czyli w tym przypadku o $$-(-2)=2$$.

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 $$[-26..26]$$.

Załóżmy, że klucz ma wartość $$- 2$$. Każdą literę musimy przesunąć o $$2$$ w lewo. Dla liter powyżej litery $$B$$ problem jest trywialny. Dla liter $$A$$ i $$B$$ należy odliczyć odpowiednią liczbę znaków począwszy od $$Z$$ w dół.

Natomiast dla klucza równego $$2$$ aby zaszyfrować literę $$Z$$ musimy przejść do początku alfabetu i tu odliczyć dwa znaki.

Rozwiązanie w C++ (dla dużych liter języka łacińskiego):

//algorytm.edu.pl
#include<iostream>

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;

	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:

//algorytm.edu.pl
#include<iostream>
#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;

	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:

$$A,\ B,\ C,\ ...,\ W,\ X,\ Y,\ Z$$

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 (tak zwane "wyifowanie" przypadków). 

Deszyfrowanie opiera się na tej samej idei.

Rozwiązanie alternatywne:

//algorytm.edu.pl
#include<iostream>
#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;
	 
	  return 0;
}