Login lub e-mail Hasło   

Liczby pierwsze - szyfr Cezara

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/pr(...)ex.html
Szyfrowanie informacji ma na celu ukrycie jej przed osobami niepowołanymi. Pierwsze dowody ukrywania informacji za pomocą szyfrów datują się na rok 4000 p.n.e. i pochod...
Wyświetlenia: 14.554 Zamieszczono 03/11/2006

Szyfrowanie informacji ma na celu ukrycie jej przed osobami niepowołanymi. Pierwsze dowody ukrywania informacji za pomocą szyfrów datują się na rok 4000 p.n.e. i pochodzą ze starożytnego Egiptu. Egipscy kapłani ukrywali ważne informacje stosując specjalne szyfrowanie hieroglifów. Również inne ludy świata starożytnego korzystały z różnych szyfrów.

Szyfrowanie nie ogranicza się tylko do tajnych służb rządowych i szpiegostwa. Wykorzystywane jest dzisiaj szeroko we wszelkich transakcjach handlowych dokonywanych poprzez sieć Internet, gdzie osoby trzecie nie powinny odczytywać przesyłanych informacji - przecież nie chciałbyś, aby twój numer konta i hasło bankowe wpadły w ręce kogoś obcego, kto natychmiast dokonałby wspaniałych zakupów w twoim imieniu. To samo odnosi się do korespondencji prywatnej i zawodowej - nie chcemy, aby obcy ludzie czytali nasze sekrety. Dlatego informatycy i matematycy na całym świecie intensywnie pracują nad stworzeniem niezawodnych i bezpiecznych metod szyfrowania informacji. W tym i następnym rozdziale postaramy się przybliżyć wam to zagadnienie.

Sławny szyfr Cezara polegał na zastępowaniu każdego znaku tekstu znakiem odległym o 3 pozycje w alfabecie. Literki z końca alfabetu były zamieniane przez literki z początku alfabetu.

Poniżej podajemy tablicę kodową. U góry znajdują się kodowane literki, a u dołu te, które je zastąpią po zaszyfrowaniu informacji:

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

Szyfrowanie:

TERA EST ROTUNDA
WHUD HVW
URWXQGD

Rozszyfrowywanie polega na zastępowaniu literek szyfru literkami z górnej kolumny:

DYH FHDPDU
AVE CEASAR

Oczywiście kody tego typu nie mają większego zastosowania, ponieważ bardzo łatwo je złamać. Dla 26 liter alfabetu można utworzyć maksymalnie 25 różnych kodów Cezara (właściwie 26, lecz dla zerowego odstępu szyfr jest równoważny szyfrowanemu tekstowi). Wystarczy więc sprawdzić każdy z nich, aż dostaniemy rozszyfrowaną wiadomość, co nie jest specjalnie trudne dla współczesnych komputerów.

Znaki są przechowywane w pamięci komputera w postaci liczb zwanych kodami znaków. Każda literka ma przyporządkowany sobie numer. W poniższej tabelce zebraliśmy kody literek od A do Z w kodzie ASCII (American Standard Code for Information Interchange - Amerykański, Standardowy Kod dla Wymiany Informacji).

Litera A B C D E F G H I J L L M N O P Q R S T U V W X Y Z
Kod ASCII 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

Klucz szyfrujący jest informacją, która pozwala zaszyfrować dane lub odczytać dane zaszyfrowane. W przypadku kodu Cezara kluczem jest wartość przesunięcia w alfabecie literek kodu względem literek tekstu jawnego. Przy szyfrowaniu przesunięcie dodajemy do kodu znaku. Przy rozszyfrowywaniu przesunięcie odejmujemy od kodu znaku. Obie operacje spisują się dobrze w środku alfabetu.

Przesunięcie d wynosi 3. Szyfrujemy literkę F. Kod literki F jest równy 70. Po dodaniu przesunięcia 3 otrzymujemy kod zaszyfrowanej literki 73. Jest to literka I:

F dla klucza d=3 szyfruje się na I

Rozszyfrowujemy literkę X. Kod X wynosi 88. Po odjęciu przesunięcia 3 otrzymujemy kod 85, który odpowiada literce U:

X dla klucza d=3 rozszyfrowuje się na U

Problem pojawia się przy literkach skrajnych, gdy dodanie przesunięcia daje kod większy od 90 lub odjęcie przesunięcia daje kod mniejszy od 65. Jeśli umówimy się, iż alfabet tworzy pierścień zamknięty, to po literce Z następuje A. Literkę A poprzedza Z:

Znak ... X Y Z A B C ... X Y Z A B C ...
  ... 62 63 64 65 66 67 ... 88 89 90 91 92 93 ...
Kod ... 88 89 90 65 66 67 ... 88 89 90 65 66 67 ...

Jeśli w wyniku dodania przesunięcia otrzymamy wartość większą od 90 (np. 92), to od tego wyniku należy odjąć 26, aby otrzymać poprawny kod szyfru (92 - 26 = 66, czyli literka B). Jeśli z kolei w wyniku odjęcia przesunięcia otrzymamy wartość mniejszą od 65 (np. 63), to do tego wyniku należy dodać 26, aby otrzymać rozkodowany znak (63 + 26 = 89, czyli literka Y).

Poniżej podajemy szczegółowy algorytm dla funkcji Cezar(z,d), która dokonuje szyfrowania lub rozszyfrowania podanego znaku z przy kluczu d.

Dane wejściowe

z - znak ASCII do zaszyfrowania lub znak ASCII zaszyfrowany, z {'A','B',...,'Z'}. Znak z jest argumentem funkcji Cezar(z,d).
d - przesunięcie dodatnie dla szyfrowania i ujemne dla rozszyfrowywania, d C d <-25,25>. Przesunięcie d jest argumentem funkcji Cezar(z,d).

Dane wyjściowe

Zaszyfrowany znak z (d > 0) lub rozszyfrowany znak z (d < 0). Jeśli znak z nie jest dużą literą alfabetu, to zostaje zwrócony bez zmian. Wynik jest wartością funkcji Cezar(z,d).

Zmienne pomocnicze i funkcje

c - wyliczany kod cezara, c N
kod(znak) - funkcja zwracająca kod znaku ASCII podanego jako argument
znak(kod) - funkcja zwracająca znak ASCII o kodzie podanym jako argument

krok 1: Jeżeli z {'A','B',...,'Z'}, to idź do kroku 2. Inaczej  Cezar(z,d) z i zakończ algorytm.
krok 2: c kod(z) + d
krok 3: Jeśli c > 90, to c c - 26
krok 4: Jeśli c < 65, to c c + 26
krok 5: Cezar(z,d) znak(c)
krok 6: Zakończ algorytm

Sprawdzamy, czy znak z należy do zbioru liter od A do Z. Jeśli nie, to nie szyfrujemy go, lecz zwracamy bez zmian. Takie podejście umożliwi wstawianie do naszego kodu spacji oraz innych znaków interpunkcyjnych.

Jeśli znak należy do zbioru liter od A do Z, wyznaczamy dla niego kod Cezara. W tym celu do kodu znaku dodajemy przesunięcie d. W wyniku możemy otrzymać wartość większą od 90 (dla d dodatniego) lub mniejszą od 65 (dla d ujemnego). W takim razie odpowiednio dodajemy do kodu lub odejmujemy od niego liczbę 26, aby otrzymać poprawny kod Cezara.

Jako wynik zwracamy znak o wyliczonym kodzie i kończymy algorytm.


Program pobiera od użytkownika klucz d oraz tekst, który ma zostać zaszyfrowany lub rozszyfrowany. Tekst musi być wprowadzony dużymi literami. Przy rozszyfrowywaniu należy zawsze podać klucz o wartości przeciwnej niż przy szyfrowaniu. Pobrany tekst jest rozbijany na kolejne znaki, które przesyła się wraz z kluczem do funkcji Cezar. Wyniki z funkcji Cezar są wyświetlane kolejno w okienku konsoli.

Prezentowany program jest bardzo prymitywny i posiada jedynie wartość dydaktyczną, chociaż...

Wydruk z uruchomionego programu
  S Z Y F R  C E Z A R A
(C)2005 mgr Jerzy Wałaszek
I LO w Tarnowie

Podaj klucz d = 3

Wpisz poniżej tekst do zaszyfrowania/rozszyfrowania

TERA EST ROTUNDA

*** WYNIKI ***

WHUD HVW URWXQGD

Koniec, naciśnij klawisz ENTER...
  S Z Y F R  C E Z A R A
(C)2005 mgr Jerzy Wałaszek
I LO w Tarnowie

Podaj klucz d = -3

Wpisz poniżej tekst do zaszyfrowania/rozszyfrowania

WHUD HVW URWXQGD

*** WYNIKI ***

TERA EST ROTUNDA

Koniec, naciśnij klawisz ENTER...
Microsoft Visual Basic 2005 Express Edition

Zwróć uwagę, iż w szyfrze Cezara tym samym literom zawsze odpowiadają takie same znaki szyfru. Na przykład literce D odpowiada znak S, literce A znak P. Własność ta ułatwia złamanie kodu.

Borland
Delphi 7.0
Personal
Edition
// Szyfr Cezara
// (C)2004 mgr Jerzy Wałaszek
// I LO w Tarnowie
//---------------------------

program szyfrCezara;

{$APPTYPE CONSOLE}

// Funkcja Cezar pobiera jako argumenty
// znak z do zaszyfrowania oraz klucz d
// Wynikiem jest zaszyfrowany znak
//-------------------------------------
function Cezar(z : char; d : integer) : char;
var
c : cardinal;
begin
if
z in ['A'..'Z'] then
begin

c := ord(z) + d;
if c > 90 then c := c - 26;
if c < 65 then c := c + 26;
Cezar := char(c);
end
else
Cezar := z;
end;

//---------------
// Program główny
//---------------

var
s : string;
d,i : integer;

begin
writeln(' S Z Y F R C E Z A R A');
writeln('(C)2004 mgr Jerzy Walaszek');
writeln(' I LO w Tarnowie');
writeln;
write('Podaj klucz d = '); readln(d);
writeln;
writeln('Wpisz ponizej tekst do zaszyfrowania/rozszyfrowania');
writeln;
readln(s);
writeln;
writeln('*** WYNIKI ***');
writeln;
for i := 1 to length(s) do write(Cezar(s[i],d));
writeln; writeln;
writeln('Nacisnij ENTER...'); readln;
end.
Borland
C++ Builder
6.0
Personal
Edition
// Szyfr Cezara
// (C)2004 mgr Jerzy Wałaszek
// I LO w Tarnowie
//---------------------------

#include <iostream>
#include <string>

using namespace std;

// Funkcja Cezar pobiera jako argumenty
// znak z do zaszyfrowania oraz klucz d
// Wynikiem jest zaszyfrowany znak
//-------------------------------------
char Cezar(char z, int d)
{
int c;

if((z >= 'A') && (z <= 'Z'))
{
c = z + d;
if(c > 90) c -= 26;
if(c < 65) c += 26;
return(c);
}
else return(z);
}

//---------------
// Program główny
//---------------

main()
{
string s;
int d,dl,i;
char c[1];

cout << " S Z Y F R C E Z A R A\n"
"(C)2004 mgr Jerzy Walaszek\n"
" I LO w Tarnowie\n\n"
"Podaj klucz d = "
;
cin >> d;
cout << "\nWpisz ponizej tekst do zaszyfrowania/rozszyfrowania\n\n";
getline(cin,s); // Pusty przebieg do końca wiersza odczytu klucza !!!
getline(cin,s); // Teraz dopiero odczytujemy nowy wiersz z cin
dl = s.length(); // Do dl trafia ilość znaków w odczytanym wierszu
cout << "\n*** WYNIKI ***\n\n";
for(i = 0; i < dl; i++) cout << Cezar(s[i],d);
cout << "\n\nKlawisz Enter = KONIEC";
cin.getline(c,1);
}
Microsoft
Visual
Basic 2005
Express
Edition
' Szyfr Cezara
' (C)2005 mgr Jerzy Wałaszek
' I LO w Tarnowie
'---------------------------


Option Explicit On

Module
Module1

' Funkcja Cezar pobiera jako argumenty
' znak z do zaszyfrowania oraz klucz d
' Wynikiem jest zaszyfrowany znak
'-------------------------------------

Public Function Cezar(ByVal z As Char, ByVal d As Integer) As Char

Dim
c As Integer

If
z >= "A" And z <= "Z" Then
c = Asc(z) + d
If c > 90 Then c = c - 26
If c < 65 Then c = c + 26
Return Chr(c)
End If
Return
z
End Function

Sub
main()

Dim s As String
Dim d, i As Integer

Console.WriteLine(" S Z Y F R C E Z A R A")
Console.WriteLine("(C)2005 mgr Jerzy Wałaszek")
Console.WriteLine(" I LO w Tarnowie")
Console.WriteLine()
Console.Write("Podaj klucz d = ") : d = Val(Console.ReadLine)
Console.WriteLine()
Console.WriteLine("Wpisz poniżej tekst do zaszyfrowania/rozszyfrowania")
Console.WriteLine()
s = Console.ReadLine
Console.WriteLine()
Console.WriteLine("*** WYNIKI ***")
Console.WriteLine()
For i = 0 To Len(s) - 1
Console.Write(Cezar(s.Chars(i), d))
Next
Console.WriteLine()
Console.WriteLine()
Console.WriteLine("Koniec, naciśnij klawisz ENTER...")
Console.ReadLine()

End Sub

End Module
Python
# -*- coding: cp1250 -*-
# Szyfr Cezara
# (C)2005 mgr Jerzy Wałaszek
# I LO w Tarnowie
#---------------------------

# Funkcja Cezar pobiera jako argumenty
# znak z do zaszyfrowania oraz klucz d
# Wynikiem jest zaszyfrowany znak
#-------------------------------------
def Cezar(z, d):
if z >= "A" and z <= "Z":
c = ord(z) + d
if c > 90: c -= 26
if c < 65: c += 26
return chr(c)
return z

#---------------
# Program główny
#---------------

print " S Z Y F R C E Z A R A"
print "(C)2005 mgr Jerzy Walaszek"
print " I LO w Tarnowie"
print
d = int(raw_input("Podaj klucz d = "))
print
print
"Wpisz ponizej tekst do zaszyfrowania/rozszyfrowania"
print
s = raw_input()
print
print
"*** WYNIKI ***"
print
t = ""
for i in range(len(s)): t += Cezar(s[i], d)
print t
print
raw_input
("Nacisnij ENTER...")
JavaScript
<html>
<head>
<title>
Szyfr Cezara</title>
</head>
<body>
<div align=
"center">
<form name=
"frmCezar"
style=
"border: 1px outset #FF9933;
padding-left: 4px;
padding-right: 4px;
padding-top: 1px;
padding-bottom: 1px;
background-color: #FFCC66"
>
<h2 style=
"text-align: center">Szyfr Cezara</h2>
<p style=
"text-align: center">
(C)2004 mgr Jerzy Wałaszek<br>
I LO w Tarnowie
</p>
<hr>
<div align=
"center">
<table border=
"0"
cellpadding=
"4"
style=
"border-collapse: collapse"
bgcolor=
"#FFCC00">
<tr>
<td>
Klucz&nbsp; =&nbsp;</td>
<td>
<input type=
"text" name="klucz" size="10" value="3">
<input type=
"button" value="Szyfruj" name="B1" onclick="main();">
</td>
</tr>
<tr>
<td>
Tekst&nbsp; =</td>
<td>
<input type=
"text" name="tekst" size="80" value="ALA MA KOTA">
</td>
</tr>
<tr>
<td>
Wynik&nbsp; =</td>
<td id=
"t_out">...</td>
</tr>
</table>
</div>
</form>

<script language=javascript>

// Szyfr Cezara
// (C)2004 mgr Jerzy Wałaszek
// I LO w Tarnowie
//---------------------------

// Funkcja Cezar pobiera jako argumenty
// znak z do zaszyfrowania oraz klucz d
// Wynikiem jest zaszyfrowany znak
//-------------------------------------
function Cezar(z,d)
{
var c;

if((z >= 65) && (z <= 90))
{
c = z + d;
if(c > 90) c -= 26;
if(c < 65) c += 26;
return(c);
}
else return(z);
}

//---------------
// Program główny
//---------------

function main()
{
var s,t,d,dl,i;

d = parseInt(document.frmCezar.klucz.value);
if(isNaN(d) || (d > 25) || (d < -25))
t = "<font color=Red><b>Zły klucz</b></font>";
else
{
t = "";
s = document.frmCezar.tekst.value;
dl = s.length;
for(i = 0; i < dl; i++)
t += String.fromCharCode(Cezar(s.charCodeAt(i),d));
}
document.getElementById("t_out").innerHTML = t;
}

</script>

</div>
</body>
</html>
   
   
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       

Przeanalizuj przedstawiony w tym rozdziale algorytm i określ, dla jakich wartości przesunięcia d przestaje on poprawnie pracować? Zaproponuj usunięcie tej niedogodności. Uniezależnij kodowanie od wielkości literek.

Ambitnym proponujemy utworzenie programu rozkodowującego dowolny tekst zakodowany szyfrem Cezara.

Więcej informacji na temat metod szyfrowania znajdziesz w artykule o komputerach Colossus.

 

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

Podobne artykuły


58
komentarze: 20 | wyświetlenia: 80676
61
komentarze: 41 | wyświetlenia: 9422
31
komentarze: 8 | wyświetlenia: 56512
31
komentarze: 7 | wyświetlenia: 86593
27
komentarze: 10 | wyświetlenia: 20334
23
komentarze: 5 | wyświetlenia: 19511
22
komentarze: 8 | wyświetlenia: 2111
14
komentarze: 8 | wyświetlenia: 100806
13
komentarze: 8 | wyświetlenia: 2028
13
komentarze: 55 | wyświetlenia: 21865
11
komentarze: 2 | wyświetlenia: 5271
9
komentarze: 3 | wyświetlenia: 15202
8
komentarze: 41 | wyświetlenia: 3829
16
komentarze: 5 | wyświetlenia: 9001
49
komentarze: 18 | wyświetlenia: 64963
 
Autor
Artykuł

Powiązane tematy






Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska