Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

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:

{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 (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;
}