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 % 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 % 3 = 1

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

3 × 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 % 3 = 1, bo 10 - 3 × 3 = 10 -  9 = 1
10 % 4 = 2, bo 10 - 2 × 4 = 10 -  8 = 2
10 % 5 = 0, bo 10 - 2 × 5 = 10 - 10 = 0
10 % 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 % 6 = 1 (13 - 2 × 6 = 13 - 12 = 1)
20 % 6 = 2 (20 - 3 × 6 = 20 - 18 = 2)
27 % 6 = 3 (27 - 4 × 6 = 27 - 24 = 3)
34 % 6 = 4 (34 - 5 × 6 = 34 - 30 = 4)
41 % 6 = 5 (41 - 6 × 6 = 41 - 36 = 5)
48 % 6 = 0 (48 - 6 × 8 = 48 - 48 = 0)

Reszta z  dzielenia może przyjąć wartości: a % 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 % jest wyrażenie a + b, ab nieujemne, to wynikiem będzie liczba mniejsza od modułu:

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

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

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

Szyfrowanie Cezara

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

Mamy kod znaku tekstu t. 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 0…2:

t'''t" % 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) % 26 + 65
c ← (t - 62) % 26 + 65

Sprawdźmy:

t = kod(G) = 71
c = (71 - 62) % 26 + 65
c = 9 % 26 + 65
c = 9 + 65
c = 74 : kod litery J
t = kod(Y) = 89
c = (89 - 62) % 26 + 65
c = 27 % 26 + 65
c = 1 + 65
c = 66 : kod litery B

Odejmowanie modulo m

Jeśli pierwszym argumentem operatora % będzie wyrażenie ab, ab nieujemne, to wynikiem jest:

(ab) % m = -m + 1 … m - 1

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

(ab + m) % m = 0 … m - 1

Jest to prawdziwe, gdy |ab| < m.

Sprawdźmy, m = 10:

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

Rozszyfrowywanie szyfru Cezara

Tutaj postępujemy podobnie, mamy kod znaku szyfru c, 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'' % 26

Wracamy do kodu ASCII:

c''''c''' + 65

Składamy wzór:

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

Sprawdźmy:

c = Kod(G) = 71
t = (71 - 42) % 26 + 65
t = 29 % 26  + 65
t = 3 + 65
t = 68 : kod litery D
c = Kod(B) = 66
t = (66 - 42) % 26 + 65
t = 24 % 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) % 26 + 65
Rozszyfrowywanie:
t = (c - 42) % 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

Zmienne pomocnicze:

i : indeks; i ∈ B.
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: ; 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.

Zmienne 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.