Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Szyfr Cezara

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy opracować algorytm szyfrujący i deszyfrujący dla szyfru Cezara

Rozwiązanie


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:
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
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
?
?
?

Jak widzisz, szyfrowanie liter AW 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:
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
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

Zatem X szyfrujemy jako A, Y jako BZ jako C.

Zaszyfrujmy szyfrem Cezara tekst KROKODYL AREK:

Tekst:
K
R
O
K
O
D
Y
L
 
A
R
E
K
Szyfr
N
U
R
N
R
G
B
O
 
D
U
H
N
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, YZ:

Szyfr
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:
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

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 am liczbami nieujemnymi, a m jest większe od 0. Na przykład:

16 mod 3 = 1

3 mieści się całkowitą liczbę razy 516:

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, ab 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 AZ.

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, ab 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

Szyfrowanie Szyfrem Cezara
(C)2020 mgr Jerzy Wałaszek

.

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

Szyfrowanie Szyfrem Cezara
(C)2020 mgr Jerzy Wałaszek

.


Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.