Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

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:

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

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

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:

Po odczycie ze strumienia liczby 41 przez cin >> wiek, cyfry zostają usunięte, natomiast pozostaje wciąż znak \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;
}

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

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:

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.

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:

        c  ← c  - 65

2. Dodajemy przesunięcie Cezara:

        c  ← c  - 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:

        c  ← c  - 65

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

        c  ← c  - 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:

Lista kroków:

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:

Lista kroków:

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

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

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

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe