Algorytmy i Struktury Danych

Gajusz Juliusz Cezar

Szyfrowanie polega na takiej zmianie tekstu, aby stał się on nieczytelny dla osoby niewtajemniczonej. Szyfr Cezara jest takim prostym szyfrem. Obecnie posiada on jedynie wartość dydaktyczną. Zasada szyfrowania jest bardzo prosta. Załóżmy, iż tekst składa się tylko z dużych liter od A do Z. Każdą literę tekstu zastępujemy literą, która leży o trzy pozycje dalej w alfabecie. Np. literę A zastępujemy literą D (A B C D E…), literę B zastępujemy literą E (…B C D E F…), itd. Zróbmy tabelę szyfrowania:

Tekst:

Szyfr

Jak widzisz, szyfrowanie liter A…W nie sprawia problemu. Co jednak z literami X, Y i Z. Otóż umówmy się, iż alfabet szyfru zawija się i po literze Z znów mamy: A, B, C:

Tekst:

Szyfr

Zatem X szyfrujemy jako A, Y jako B i Z jako C.

Zaszyfrujmy szyfrem Cezara tekst KROKODYL AREK:

Tekst:

Szyfr

KROKODYL AREK → NURNRGBO DUHN

Tekst stał się nieczytelny. Przy rozszyfrowywaniu postępujemy odwrotnie: literę szyfru zastępujemy literą leżącą w alfabecie o trzy pozycje wcześniej. Tutaj podobnie musimy zawinąć alfabet, aby przed literą A znalazły się litery X, Y i Z:

Szyfr

Tekst:

Otrzymaliśmy szyfr: DWDNXMHPB:

Szyfr	D	W	D	N	X	M	H	P	B
Tekst:	A	T	A	K	U	J	E	M	Y

DWDNXMHPB → ATAKUJEMY

Przejdźmy do szczegółów technicznych. Szyfrowanie będzie polegało na zamianie kodu ASCII znaku tekstu na kod ASCII znaku szyfru. Wykorzystamy operację modulo, ponieważ pozwoli ona nam zawijać kody liter.

Najpierw omówimy operacje dodawania i odejmowania modulo (reszta z dzielenia całkowitoliczbowego-operator %).

Dodawanie modulo m

Operacja a mod m (a modulo m) daje w wyniku resztę z dzielenia całkowitoliczbowego a przez m. Zakładamy, że a i m są liczbami nieujemnymi, a m jest większe od 0. Na przykład:

16 mod 3 = 1

3 mieści się całkowitą liczbę razy 5 w 16:

3 mod 5 = 15 i do 16 brakuje 1

1 jest tym, co pozostaje po odjęciu 3×5 = 15 od 16. Dlatego nazywamy to resztą z dzielenia. Zobaczmy kilka przykładów:

10 mod 3 = 1, bo 10-3×3 = 10- 9 = 1
10 mod 4 = 2, bo 10-2×4 = 10- 8 = 2
10 mod 5 = 0, bo 10-2×5 = 10-10 = 0
10 mod 6 = 4,  bo 10-1×6 = 10- 6 = 4

Drugi argument operatora % nazywamy modułem. Reszta z dzielenia jest zawsze mniejsza od modułu. Dlaczego? Bo gdyby była równa lub większa, to by oznaczało, iż moduł mieści się więcej razy w dzielonej liczbie. Zobaczmy wszystkie reszty z dzielenia różnych liczb przez moduł m = 6:

13 mod 6 = 1 (13-2×6 = 13-12 = 1)
20 mod 6 = 2 (20-3×6 = 20-18 = 2)
27 mod 6 = 3 (27-4×6 = 27-24 = 3)
34 mod 6 = 4 (34-5×6 = 34-30 = 4)
41 mod 6 = 5 (41-6×6 = 41-36 = 5)
48 mod 6 = 0 (48-6×8 = 48-48 = 0)

Reszta z dzielenia może przyjąć wartości: a mod m = 0 … m-1.

Reszta z dzielenia jest równa 0, gdy moduł m dzieli a całkowitą liczbę razy.

Jeśli pierwszym argumentem operatora mod jest wyrażenie a+b, a i b nieujemne, to wynikiem będzie liczba mniejsza od modułu:

(a+b) mod m = 0…m-1

Dodawanie poddane działaniu reszty z dzielenia nazywamy dodawaniem modulo. Zobaczmy kilka przykładów:

…
(5+3) mod 10 = 8
(6+3) mod 10 = 9
(7+3) mod 10 = 0
(8+3) mod 10 = 1
(9+3) mod 10 = 2
…

Szyfrowanie Cezara

Jak to zastosować do szyfrowania szyfrem Cezara? Prześledź poniższe wyprowadzenie:

Mamy kod znaku t z tekstu Ma on zakres od 65 (A) do 90 (Z). Najpierw kod ten zmieniamy tak, aby otrzymać wartości 0…25:

t' ← t-65

Za moduł przyjmujemy liczbę 26 – to liczba liter A … Z.

Teraz dodajemy 3, czyli przesuwamy się o 3 pozycje do przodu. W wyniku dostaniemy wartości 3…28:

t" ← t'+3

Jest to nasza suma, poddajemy ją operacji modulo 26. W ten sposób wartości równe lub większe od modułu (czyli 26…28) wrócą na początek zakresu do 0…2:

t''' ← t" mod 26

I wracamy z powrotem do kodu ASCII:

t'''' ← t'''+65

Złóżmy to w jedno wyrażenie i otrzymamy wzór na kod znaku szyfru Cezara c:

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

Sprawdźmy:

t = kod(G) = 71
c = (71-62) mod 26+65
c = 9 mod 26+65
c = 9+65
c = 74:kod litery J

t = kod(Y) = 89
c = (89-62) mod 26+65
c = 27 mod 26+65
c = 1+65
c = 66:kod litery B

Odejmowanie modulo m

Jeśli pierwszym argumentem operatora mod będzie wyrażenie a-b, a i b nieujemne, to wynikiem jest:

(a-b) mod m = -m+1…m-1

Aby pozbyć się wartości ujemnych, do różnicy dodajemy m:

(a-b+m) mod m = 0…m-1

Jest to prawdziwe, gdy |a-b| < m.

Sprawdźmy, m = 10:

…
(0-3+10) mod 10 = 7
(1-3+10) mod 10 = 8
(2-3+10) mod 10 = 9
(3-3+10) mod 10 = 0
(4-3+10) mod 10 = 1
…

Rozszyfrowywanie szyfru Cezara

Tutaj postępujemy podobnie jak przy szyfrowaniu, mamy kod c znaku szyfru, który jest literą ASCII o kodzie 65…90. Kod sprowadzamy do przedziału 0…25:

c' ← c-65

Odejmujemy 3, aby przesunąć kod o 3 pozycje w tył. Otrzymujemy wynik w przedziale -3…22. Do wyniku odejmowania dodajemy moduł 26, aby zniwelować ewentualną wartość ujemną. Otrzymamy wynik w przedziale 23…48:

c" ← c'-3+26
c" ← c'+23

Teraz operacja reszty z dzielenia przez 26 da nam wynik w przedziale 0…25:

c''' ← c'' mod 26

Wracamy z powrotem do kodu ASCII:

c'''' ← c'''+65

Składamy wzór:

t = (c-65-3+26) mod 26+65
t = (c-42) mod 26+65

Sprawdźmy:

c = Kod(G) = 71
t = (71-42) mod 26+65
t = 29 mod 26+65
t = 3+65
t = 68:kod litery D

c = Kod(B) = 66
t = (66-42) mod 26+65
t = 24 mod 26+65
t = 24+65
t = 89:kod litery Y

Podsumujmy:

t - kod ASCII znaku tekstu
c - kod ASCII znaku szyfru Cezara

Szyfrowanie:
c ← (t-62) mod 26+65

Rozszyfrowywanie:
t = (c-42) mod 26+65

Teraz jesteśmy gotowi do konstrukcji algorytmu.

Algorytm szyfrowania tekstu kodem Cezara

Wejście:

Łańcuch tekstowy s.

Wyjście:

Łańcuch tekstowy s zaszyfrowany kodem Cezara

Elementy pomocnicze:

i : indeks; i ∈ B.
kod(x) : zwraca kod ASCII litery x.
znak(x) : zamienia kod x na odpowiadający mu znak ASCII.

Lista kroków:

K01: Dla i = 0, 1, …, |s|-1: ; przeglądamy kolejne znaki tekstu
     wykonuj kroki K02…K03
K02:   Jeśli (s[i] < "A") ∨ (s[i] > "Z"), ; pomijamy znaki nie będące literami A…Z
       to następny obieg pętli K01
K03:   s[i] ← znak(65+(kod(s[i])-62) mod 26) ; szyfrujemy szyfrem Cezara
K04: Pisz s ; wypisujemy szyfr
K05: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje wiersz znaków. Zamienia litery małe na duże i szyfruje kodem Cezara wyświetlając wynik.

Pascal

// Szyfrowanie Kodem Cezara
// Data: 18.08.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

var
  s : string;
  i : integer;

begin

  // odczytujemy wiersz znaków
  readln(s);

  // zamieniamy małe litery na duże
  s := upcase(s);

  // tekst kodujemy szyfrem Cezara
  for i := 1 to length(s) do
    if s[i] in ['A'..'Z'] then
      s[i] := chr(65+(ord(s[i])-62) mod 26);

  // wypisujemy zaszyfrowany tekst
  writeln(s);
  writeln;
end.

C++

// Szyfrowanie Kodem Cezara
// Data: 18.08.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;
  int i;

  // odczytujemy wiersz znaków
  getline(cin, s);

  // zamieniamy małe litery na duże
  // i kodujemy szyfrem cezara
  for(i = 0; i < s.length(); i++)
  {
    s[i] = toupper(s[i]);
    if((s[i] >= 'A') && (s[i] <= 'Z'))
      s[i] = char(65+(s[i]-62)%26);
  }

  // wypisujemy zaszyfrowany tekst
  cout << s << endl << endl;
  return 0;
}

Basic

' Szyfrowanie Kodem Cezara
' Data: 18.08.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Dim As String s
Dim As Integer i

' odczytujemy wiersz znaków
Line Input s

' zamieniamy małe litery na duże
s = Ucase(s)

' tekst kodujemy szyfrem Cezara
For i = 1 To Len(s)
  If Mid(s, i, 1) >= "A" And _
     Mid(s, i, 1) <= "Z" Then _
    Mid(s, i, 1) = Chr(65+(Asc(Mid(s, i, 1))- 62) Mod 26)
Next

' wypisujemy zaszyfrowany tekst
Print s
Print
End

Python (dodatek)

# Szyfrowanie Kodem Cezara
# Data: 24.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# odczytujemy wiersz znaków
s = input()
# zamieniamy małe litery na duże
s = s.upper()
# kodujemy szyfrem cezara
for i in range(len(s)):
    if (s[i] >= "A") and (s[i] <= "Z"):
        s = s[:i]+chr(65+(ord(s[i])-62)%26)+s[i+1:]
# wypisujemy zaszyfrowany tekst
print(s)
print()

Wynik:

nieprzyjaciel jest bardzo blisko
QLHSUCBMDFLHO MHVW EDUGCR EOLVNR

JavaScript

<html>
  <head>
    <title>
      Szyfrowanie
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm1"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>Szyfrowanie
          Szyfrem Cezara</b><br/>
          (C)2026 mgr
          Jerzy Wałaszek
          <hr>
          &nbsp;
          <input
          type="text"
          name="inp_s1"
          size="50"
          value=
"Nieprzyjaciel jest bardzo blisko"
          >
          &nbsp;<hr>
          <input
          type="button"
          value="Szyfruj"
          name="B1"
          onclick="main1();">
          <hr>
          <b>Wynik:</b>
          <div id="out1">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script language=javascript
        type=text/javascript>

// Szyfrowanie Kodem Cezara
// Data: 18.08.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------

function main1()
{
  let s,t,i,c;

  // odczytujemy
  // wiersz znaków
  s = document.frm1
      .inp_s1.value;

  // zamieniamy małe
  // litery na duże
  s = s.toUpperCase();
 
   // i kodujemy
   // szyfrem cezara
  t = "";
  for(i = 0; i < s.length; i++)
  {
    c = s.charCodeAt(i);
    if((c >= 65) &&
       (c <= 90))
      c = 65 + (c - 62) % 26;
    t += String.fromCharCode(c);
  }

  // wypisujemy
  // zaszyfrowany tekst
  document.getElementById("out1")
  .innerHTML = t;
}

</script>

  </body>
</html>

Algorytm deszyfrowania tekstu zaszyfrowanego kodem Cezara

Wejście:

Łańcuch tekstowy s zaszyfrowany kodem Cezara.

Wyjście:

Tekst jawny.

Elementy pomocnicze:

i	:	indeks; i ∈ N.
kod(x)	:	zwraca kod litery x.
znak(x)	:	zamienia kod x na odpowiadający mu znak ASCII.

Lista kroków:

K01: Dla i = 0, 1, …, |s|-1: ; przetwarzamy kolejne znaki tekstu
     wykonuj kroki K02…K03
K02:  Jeśli(s[i] < "A") ∨ (s[i] > "Z"), ; pomijamy znaki nie
       to następny obieg pętli K01       ; będące literami A…Z
K03:   s[i] ← znak(65+(kod(s[i]-42) mod 26) ; deszyfrujemy
K04: Pisz s
K05: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje wiersz znaków zaszyfrowanych szyfrem Cezara, deszyfruje je i wypisuje tekst jawny.

Pascal

// Deszyfrowanie Kodu Cezara
// Data: 18.08.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

var
  s : string;
  i : integer;

begin

  // odczytujemy wiersz znaków
  readln(s);

  // zamieniamy małe litery na duże
  s := upcase(s);

  // rozszyfrowujemy
  for i := 1 to length(s) do
    if s[i] in ['A'..'Z'] then
      s[i] := chr(65+(ord(s[i])-42) mod 26);

  // wypisujemy rozszyfrowany tekst
  writeln(s);
  writeln;
end.

C++

// Deszyfrowanie Kodu Cezara
// Data: 18.08.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <string>

using namespace std;

int main()
{
  string s;
  int i;

  // odczytujemy wiersz znaków
  getline(cin, s);

  // zamieniamy małe litery na duże
  // i rozszyfrowujemy
  for(i = 0; i < s.length(); i++)
  {
    s[i] = toupper(s[i]);
    if((s[i] >= 'A') && (s[i] <= 'Z'))
      s[i] = char(65+(s[i]-42)%26);
  }

  // wypisujemy rozszyfrowany tekst
  cout << s << endl << endl;
  return 0;
}

Basic

' Deszyfrowanie Kodu Cezara
' Data: 18.08.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Dim As String s
Dim As Integer i

' odczytujemy wiersz znaków
Line Input s

' zamieniamy małe litery na duże
s = Ucase(s)

' rozszyfrowujemy
For i = 1 To Len(s)
  If Mid(s, i, 1) >= "A" And Mid(s, i, 1) <= "Z" Then _
    Mid(s, i, 1) = Chr(65+(Asc(Mid(s, i, 1))-42) Mod 26)
Next

' wypisujemy rozszyfrowany tekst
Print s
Print
End

Python (dodatek)

# Deszyfrowanie Kodu Cezara
# Data: 25.03.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

# odczytujemy wiersz znaków
s = input()
# zamieniamy małe litery na duże
s = s.upper()
# i rozszyfrowujemy
for i in range(len(s)):
    if(s[i] >= "A") and (s[i] <= "Z"):
        s = s[:i]+chr(65+(ord(s[i])-42)%26)+s[i+1:]
# wypisujemy rozszyfrowany tekst
print(s)
print()

Wynik:

QLHSUCBMDFLHO MHVW EDUGCR EOLVNR
NIEPRZYJACIEL JEST BARDZO BLISKO

JavaScript

<html>
  <head>
    <title>
      Deszyfrowanie
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm2"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>
          Deszyfrowanie Szyfru Cezara
          <br/></b>
          (C)2026 mgr Jerzy Wałaszek
          <hr>
          &nbsp;
          <input
          type="text"
          name="inp_s2"
          size="50"
          value=
"QLHSUCBMDFLHO MHVW EDUGCR EOLVNR"
          >&nbsp;&nbsp;<hr>
          <input
          type="button"
          value="Deszyfruj"
          name="B2"
          onclick="main2();">
          <hr>
          <b>Wynik:</b>
          <div id="out2">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script language=javascript
        type=text/javascript>

// Rozszyfrowywanie Kodu Cezara
// Data: 18.08.2008
// (C)2008 mgr Jerzy Wałaszek
//-----------------------------

function main2()
{
  var s,t,i,c;

  // odczytujemy
  // wiersz znaków
  s = document.frm2.
      inp_s2.value;

  // zamieniamy małe
  // litery na duże
  s = s.toUpperCase();
 
  // i rozszyfrowujemy
  t = "";
  for(i = 0; i < s.length; i++)
  {
    c = s.charCodeAt(i);
    if((c >= 65) &&
       (c <= 90))
      c = 65 + (c - 42) % 26;
    t += String.fromCharCode(c);
  }

  // wypisujemy
  // zaszyfrowany tekst
  document.getElementById("out2")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Szyfr Cezara

Problem

Rozwiązanie

Dodawanie modulo m

Szyfrowanie Cezara

Odejmowanie modulo m

Rozszyfrowywanie szyfru Cezara

Podsumujmy:

Algorytm szyfrowania tekstu kodem Cezara

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm deszyfrowania tekstu zaszyfrowanego kodem Cezara

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy