Szyfrowanie tekstów - szyfr Cezara

Dane znakowe

We współczesnych językach programowania znaki są podstawowym typem danych. W pamięci komputera znak jest przechowywany w postaci liczby, którą nazywamy kodem znaku (ang. character code). Każdy znak posiada swój własny kod. Aby różne urządzenia systemu komputerowego mogły w ten sam sposób interpretować kody znaków, opracowano kilka standardów kodowania liter. Powszechnie używanym jest:

 

ASCII - American Standard Code for Information Interchange - Amerykański Standardowy Kod do Wymiany Informacji.

 

Znaki są zapamiętywane w postaci 8 bitowych kodów (pierwotnie było to 7 bitów, lecz później standard ASCII został poszerzony na 8 bitów, w których znalazły się różne znaki narodowe). Taki sposób reprezentacji znaków jest dzisiaj bardzo wygodny, ponieważ podstawowa komórka pamięci komputera IBM przechowuje właśnie 8 bitów. Dzięki temu znaki dobrze mieszczą się w pamięci.

8-bitowy kod pozwala przedstawić 256 różnych wartości i tylko tyle może być zdefiniowane znaków w kodzie ASCII. Pierwsza połówka zbioru kodów - od 0 do 127 - jest zdefiniowana na stałe i raczej nigdy nie jest modyfikowana. Jest to tzw. podstawowy zestaw znaków ASCII. Druga połówka - od 128 do 255 - zawiera znaki narodowe, które w różny sposób mogą być przydzielane rozszerzonym kodom ASCII. Z tego właśnie powodu powstały różne strony kodowe. Na przykład konsola znakowa stosuje kodowanie LATIN II. Natomiast system Windows stosuje Windows 1250. Niestety, w obu systemach polskie literki posiadają różne kody. Dlatego wyświetlenie przygotowanego w Windows polskiego tekstu w konsoli znakowej powoduje, iż polskie znaki Windows 1250 zostają źle zinterpretowane w konsoli LATIN II.

 

// Niezgodność kodów polskich liter
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
  cout << "ĄąĆćĘꣳŃńÓ󌜏źŻż\n";
  return 0;
}
ą╣ĂŠ╩ŕú│нˡîťĆč»┐

 

Typem znakowym w języku C++ jest char lub unsigned char. Zmienna tego typu może przechowywać jeden znak w kodzie ASCII.

Jeśli chcemy przetwarzać więcej znaków, to tworzymy tablicę znakową. Dostęp do poszczególnych literek odbywa się za pomocą indeksów.

Łańcuchy znakowe są przechowywane w pamięci w pewien ustalony sposób. Otóż za ostatnim znakiem tekstu umieszczany jest znak o kodzie zero. Jest to tzw. znacznik końca tekstu (ang. text end marker). Sam tekst może być dowolnie długi. Np. napis "I LO w Tarnowie" zostanie umieszczony w kolejnych komórkach pamięci w sposób następujący:

 

I   L O   w   T a r n o w i e \0

Wiersz znaków odczytujemy do tablicy za pomocą funkcji strumienia cin:

 

cin.getline(tablica_znakowa, ile_znaków);

 

Funkcja ta odczytuje do wskazanej tablicy co najwyżej tyle znaków, ile podano w drugim parametrze wywołania minus jeden. Za wczytanymi znakami automatycznie jest umieszczany znak o kodzie zero. Znaki są odczytywane aż do napotkania znaku /n, który nie jest kopiowany do tablicy.

 

// Odczyt danych do tablicy znakowej
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
  char t[256]; // tutaj przechowujemy znaki

  cout << "Wpisz swoje imie : ";

  cin.getline(t,255);

  cout << "Witaj, " << t << endl;

  return 0;
}

Wpisz swoje imie : Mateusz
Witaj, Mateusz

 

Problemy pojawiają się, gdy w programie mieszamy odczyt ze strumienia cin z odczytem wierszy.

 

// Odczyt danych do tablicy znakowej
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
  char nazwisko[20];
  int wiek;

  cout << "Wiek     : "; cin >> wiek;

  cout << "Nazwisko : "; cin.getline(nazwisko,20);

  cout << nazwisko << ", lat " << wiek << endl;

  return 0;
}

Wiek     : 15
Nazwisko :
, lat 15

 

Otóż cin >> wiek odczytuje dane aż do napotkania w strumieniu spacji lub znaku \n, którego jednakże ze strumienia nie usuwa. Znak ten pozostaje w strumieniu. Na przykład, wpisujemy do strumienia liczbę 41. Przed odczytem strumień wygląda tak:

 

cin : 4 1 \n

 

Po odczycie ze strumienia liczby 41 przez cin >> wiek, cyfry zostają usunięte, natomiast pozostaje wciąż znak \n.

 

cin : \n

 

Gdy teraz wywołujemy funkcję cin.getline(nazwisko,20), to napotyka ona pozostawiony znak \n i kończy wpisując do tablicy nazwisko pusty tekst - składający się tylko ze znaku o kodzie zero. Dlatego w powyższym programie nie możemy wprowadzić żadnego tekstu jako nazwisko. Rozwiązaniem jest użycie funkcji:

 

cin.ignore(ile_znaków, do_jakiego_znaku);

 

Funkcja ta odczytuje ze strumienia cin co najwyżej podaną liczbę znaków aż do napotkania wskazanego znaku, który zostaje usunięty ze strumienia. Znakiem tym powinien oczywiście być znak końca wiersza \n. Odczytywane znaki są ignorowane - stąd pochodzi nazwa funkcji. Poprawny program wygląda następująco:

 

// Odczyt danych do tablicy znakowej
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
  char nazwisko[20];
  int wiek;

  cout << "Wiek     : "; cin >> wiek;

  cin.ignore(256,'\n');

  cout << "Nazwisko : "; cin.getline(nazwisko,20);

  cout << nazwisko << ", lat " << wiek << endl;

  return 0;
}

Wiek     : 15
Nazwisko : Kowalski
Kowalski, lat 15

 

W wyrażeniach znaki są traktowane w C++ jako liczby całkowite. Poniższy program wczytuje wiersz znaków, następnie wyświetla poszczególne znaki i ich kody:

 

// Kody znaków
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
  char t[256];
  int i,c;

  cout << "Wpisz tekst : "; cin.getline(t,256);

  i = 0;

  while(t[i])
  {
     c = t[i];
     cout << "'" << t[i++] << "' - kod : " << c << endl;
  }

  return 0;
}

Wpisz tekst : Yogi Bear
'Y' - kod : 89
'o' - kod : 111
'g' - kod : 103
'i' - kod : 105
' ' - kod : 32
'B' - kod : 66
'e' - kod : 101
'a' - kod : 97
'r' - kod : 114

 

Szyfr Cezara

Szyfrowanie tekstów (ang. text encryption) ma na celu ukrycie ważnych informacji przed dostępem do nich osób niepowołanych. Historia kodów szyfrujących sięga czasów starożytnych. Już tysiące lat temu egipscy kapłani stosowali specjalny system hieroglifów do szyfrowania różnych tajnych wiadomości. Szyfr Cezara (ang. Ceasar's Code lub Ceasar's Cipher) jest bardzo prostym szyfrem podstawieniowym (ang. substitution cipher). Szyfry podstawieniowe polegają na zastępowaniu znaków tekstu jawnego (ang. plaintext) innymi znakami przez co zawarta w tekście informacja staje się nieczytelna dla osób niewtajemniczonych. Współcześnie szyfrowanie stanowi jedną z najważniejszych dziedzin informatyki - to dzięki niej stał się możliwy handel w Internecie, funkcjonują banki ze zdalnym dostępem do kont, powstał podpis elektroniczny oraz bezpieczne łącza transmisji danych.

 

Szyfr Cezara został nazwany na cześć rzymskiego imperatora Juliusza Cezara, który stosował ten sposób szyfrowania do przekazywania informacji o znaczeniu wojskowym. Szyfr polega na zastępowaniu liter alfabetu A...Z literami leżącymi o trzy pozycje dalej w alfabecie:

 

Tekst jawny A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Szyfr Cezara D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

 

Ostatnie trzy znaki X, Y i Z nie posiadają następników w alfabecie przesuniętych o trzy pozycje. Dlatego umawiamy się, iż alfabet "zawija się" i za literką Z następuje znów litera A. Teraz bez problemu znajdziemy następniki X → A, Y → B i Z → C.

 

Przykład:

Zaszyfrować zdanie: NIEPRZYJACIEL JEST BARDZO BLISKO.

Poszczególne literki tekstu jawnego zastępujemy literkami szyfru Cezara zgodnie z powyższą tabelką kodu. Spacje oraz inne znaki nie będące literami pozostawiamy bez zmian:

 

NIEPRZYJACIEL JEST BARDZO BLISKO
QLHSUCBMDFLHO MHVW EDUGCR EOLVNR

 

Deszyfrowanie tekstu zaszyfrowanego kodem Cezara polega na wykonywaniu operacji odwrotnych. Każdą literę kodu zamieniamy na literę leżącą o trzy pozycje wcześniej w alfabecie.

 

Szyfr Cezara A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Tekst jawny X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

 

Podobnie jak poprzednio trzy pierwsze znaki szyfru Cezara nie posiadają bezpośrednich odpowiedników liter leżących o trzy pozycje wcześniej, ponieważ alfabet rozpoczyna się dopiera od pozycji literki D. Rozwiązaniem jest ponowne "zawinięcie" alfabetu tak, aby przed literą A znalazły się trzy ostatnie literki X, Y i Z.

 

Do wyznaczania kodu literek przy szyfrowaniu i deszyfrowaniu posłużymy się operacjami modulo. Operacja modulo jest resztą z dzielenia danej liczby przez moduł. Wynik jest zawsze mniejszy od modułu. U nas moduł będzie równy 26, ponieważ tyle mamy liter alfabetu.

 

Szyfr Cezara uzyskujemy następująco:

 

Niech c jest kodem szyfrowanej litery od A do Z. Litera A ma kod ASCII równy 65, litera Z ma kod 90.

1. Sprowadzamy kod c do zakresu od 0 do 25:

        cc - 65

2. Dodajemy przesunięcie Cezara:

        cc - 65 + 3

3. Wykonujemy operację modulo, aby kody liter X, Y, Z sprowadzić do kodów A, B lub C:

        c ← (c - 65 + 3) mod 26

4. Wracamy z powrotem do kodów ASCII

        c ← 65 + (c - 62) mod 26

 

Rozszyfrowanie polega na przesunięciu kodu wstecz o trzy pozycje. W operacjach modulo odejmowanie możemy wykonać za pomocą dodawania. W tym celu dodajemy moduł minus liczba, którą chcemy odjąć:

 

(5 - 3) mod 6 = (5 + 6 - 3) mod 6 = 8 mod 6 = 2

 

Niech c jest kodem rozszyfrowywanej litery od A do Z.

1. Sprowadzamy kod do zakresu od 0 do 25:

        cc - 65

2. Odejmujemy 3, dodając moduł 26 i 3:

        cc - 65 + 26 + 3

3. Wykonujemy operację modulo:

        c ← (c - 65 + 26 - 3) mod 26

4. Wracamy z powrotem do kodów ASCII

        c ← 65 + (c - 42) mod 26

 

Algorytm szyfrowania tekstu kodem Cezara

Wejście:
Tablica znakowa T[ ] zawierająca tekst do zaszyfrowania.
Wyjście:

Tablica znakowa T[ ] z zaszyfrowanym tekstem za pomocą szyfru Cezara

Zmienne pomocnicze:
i  -  indeks
Lista kroków:
Krok 1: i ← 0 ; rozpoczynamy szyfrowanie od pierwszego znaku w tablicy
Krok 2: Jeśli T[i] = 0, zakończ ; sprawdzamy koniec tekstu
Krok 3: Jeśli T[i] < "A' lub T[i] > 'Z', to idź do kroku 5 ; sprawdzamy, czy szyfrowany znak jest dużą literą
Krok 4: T[i] ← 65 + (T[i] - 63) mod 26 ; szyfrujemy znak
Krok 5: ii + 1 ; przechodzimy do następnego znaku w tablicy
Krok 6: Idź do kroku 2  

 

Algorytm deszyfrowania tekstu zaszyfrowanego kodem Cezara

Wejście:

Tablica znakowa T[ ] z zaszyfrowanym tekstem za pomocą szyfru Cezara

Wyjście:

Tablica znakowa T[ ] z rozszyfrowanym tekstem

Zmienne pomocnicze:
i  -  indeks
Lista kroków:
Krok 1: i ← 0 ; rozpoczynamy rozszyfrowanie od pierwszego znaku w tablicy
Krok 2: Jeśli T[i] = 0, zakończ ; sprawdzamy koniec tekstu
Krok 3: Jeśli T[i] < "A' lub T[i] > 'Z', to idź do kroku 5 ; sprawdzamy, czy szyfrowany znak jest dużą literą
Krok 4: T[i] ← 65 + (T[i] - 42) mod 26 ; rozszyfrujemy znak
Krok 5: ii + 1 ; przechodzimy do następnego znaku w tablicy
Krok 6: Idź do kroku 2  

 

Program:

Do programu wpisujemy najpierw liczbę, a następnie tekst. Jeśli liczba ma wartość 0, to tekst zostanie zakodowany szyfrem Cezara. Jeśli liczba jest różna od zera, to tekst powinien być szyfrem Cezara, który program rozszyfruje.

 

// Szyfr Cezara
// (C)2011 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
  char t[256];
  int i,w;

  cin >> w;              // odczytujemy rodzaj pracy programu

  cin.ignore(255,'\n');  // usuwamy pozostawiony w strumieniu znak \n

  cin.getline(t,256);    // odczytujemy tekst

  for(i = 0; t[i]; i++)  // przeglądamy kolejne znaki
    if(t[i] >= 'A' && t[i] <= 'Z')
    {
       if(w) t[i] = 65 + (t[i] - 42) % 26;
       else  t[i] = 65 + (t[i] - 62) % 26;
    } 

  cout << t << endl;     // wyświetlamy przetworzony tekst

  return 0;
}

0
ATAK W NOCY OD STRONY RZEKI
DWDN Z QRFB RG VWURQB UCHNL

1
DWDN Z QRFB RG VWURQB UCHNL
ATAK W NOCY OD STRONY RZEKI

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.