Przypomnienie najważniejszych informacji

Szyfrowanie to proces mający na celu zamianę jawnej wiadomości w szyfrogram – przekształconą wiadomość, której odczytanie przez osobę postronną nie sprawi, że pozna ona oryginalną informację. Do szyfrowania wykorzystujemy zwykle pewien klucz, którego forma i wartość dostosowana jest do wybranego przez nas algorytmu kryptograficznegokryptografiakryptograficznego. W zależności od typu szyfrowania przechwycenie klucza przez osobę nieupoważnioną może, ale nie musi pozwolić jej na odszyfrowanie wiadomości. Można spotkać różne podziały szyfrów, m.in.:

• szyfry symetryczne – do procesu szyfrowania i deszyfrowania wykorzystujemy ten sam klucz,

• szyfry asymetryczne – stosuje się osobne klucze do szyfrowania i deszyfrowania wiadomości,

• szyfry podstawieniowe – podczas procesu szyfrowania każdy znak jawnej wiadomości zamieniany jest na inny znak lub ciąg znaków,

• szyfry przestawieniowe – w trakcie szyfrowania zamieniana jest kolejność znaków w wiadomości.

Obecnie stosowane szyfry to skomplikowane algorytmy, często uniemożliwiające szybkie ich złamanie. W zadaniach maturalnych skupimy się jednak na o wiele prostszych, historycznych przykładach metod szyfrowania.

Zadanie 1 – Szyfr kolumnowy

Zadanie pochodzi z pierwszej części egzaminu maturalnego z informatyki na poziomie rozszerzonym, który odbył się w czerwcu 2019 r.

Treść zadania

Szyfrowanie kolumnowe jest jedną z metod szyfrowania przestawieniowego, polegającego na zmianie kolejności znaków w szyfrowanym tekście. W tej metodzie jest wykorzystywana tabela o dodatniej liczbie wierszy równej k. Liczba k jest nazywana kluczem. Wiersze i kolumny tabeli są numerowane liczbami naturalnymi, począwszy od 1. Znaki tekstu, który ma być zaszyfrowany, wpisujemy do kolejnych kolumn tabeli, zaczynając od jej lewego górnego rogu. W kolumnach nieparzystych znaki wpisujemy od góry do dołu, a w parzystych od dołu do góry. Puste miejsca w ostatniej rozpoczętej kolumnie wypełniamy znakiem „_” oznaczającym spację. Następnie odczytujemy kolejne wiersze od góry do dołu (każdy z nich od lewej do prawej), w wyniku czego uzyskujemy szyfrogram.

Przykład: dla klucza k=3 i tekstu MATURA_Z_INFORMATYKI budujemy tabelę:

i otrzymujemy szyfrogram MA_FOYKARZNRTITU_IMA_.

Podpunkt 1

Do zaszyfrowania pewnego 40‑znakowego cytatu z wypowiedzi Juliusza Cezara użyto metody szyfru kolumnowego o kluczu 10. Otrzymano szyfrogram:

NKI_ATE_USGACYOKZZ_YYSJTCWEKI_SAEMTRLE_P

Rozszyfruj ten cytat.

Rozwiązanie

Do rozszyfrowania tego cytatu potrzebować będziemy podobnej tabeli, do tej przedstawionej w treści zadania. Podany cytat jest w postaci szyfrogramu, dlatego jego znakami wypełniamy po kolei następujące po sobie wiersze (będzie ich dziesięć, ponieważ taka jest też wartość klucza).

Odczytajmy teraz tekst jawnytekst jawnytekst jawny, stosując opisane w treści zadania wytyczne. W rezultacie otrzymujemy:

NAUCZYCIELEM_WSZYSTKIEGO_JEST_PRAKTYKA

Jest to rozwiązanie naszego zadania.

Podpunkt 2

W wybranym przez siebie języku programowania, za pomocą pseudokodu lub w postaci listy kroków, napisz algorytm deszyfrujący tekst, który został zakodowany szyfrem kolumnowym.

Specyfikacja:

Dane:

• k – klucz, liczba całkowita większa od 0

• n – liczba znaków w tekście zaszyfrowanym, n jest wielokrotnością k

• S[1..n] – ciąg znaków (tekst do odszyfrowania)

Wynik:

• T[1..n] – ciąg znaków (tekst odszyfrowany)

Rozwiązanie

Pierwszym krokiem naszego algorytmu będzie zdefiniowanie odpowiednich zmiennych. Należeć do nich będą (przyjęte oznaczenia mogą być inne):

• P – liczba kolumn w tabeli,

• W – pozycja w szyfrogramie litery aktualnie dopisywanej do tekstu jawnego,

• z – różnica pomiędzy pozycjami kolejnych liter, odczytywanych z szyfrogramu.

Początkowe wartości zdefiniowanych zmiennych:

P = n/k

W = 0

z = P

Mimo że operować będziemy na ciągu znaków, musimy zachować wyobrażenie utworzonej do szyfrowania tabeli. W naszym algorytmie wykorzystamy dwie pętle:

• pierwszą zawierającą operacje odczytywania liter z rozpatrywanej kolumny (liczba powtórzeń tej pętli równa jest kluczowi k),

• drugą odpowiedzialną za operacje przejścia pomiędzy parzystymi i nieparzystymi iteracjami pierwszej pętli (P powtórzeń).

Zależność operacji od parzystości powtórzenia pętli wynika z konstrukcji tabeli – parzyste kolumny zapisywane są od dołu do góry, natomiast nieparzyste od góry do dołu.

Wewnątrz pętli odpowiedzialnej za odczytanie liter wykonywać będziemy dwie operacje – najpierw dopisanie litery szyfrogramu z pozycji W do ciągu znaków tekstu jawnego, a następnie dodanie wartości zmiennej z do aktualnej wartości zmiennej W.

Przed każdym wykonaniem tej pętli musimy dodać do W liczbę jeden – przed pierwszą iteracją w celu ustalenia odczytu litery z pierwszej pozycji w szyfrogramie, natomiast w przypadku kolejnych iteracji ze względu na fakt, że dwie sąsiednie litery tekstu jawnego, znajdujące się w dwóch różnych kolumnach tabeli, w szyfrogramie również ze sobą sąsiadują. Operację tę zamieścimy oczywiście w pętli odpowiedzialnej za przejścia pomiędzy kolejnymi kolumnami (parzystymi i nieparzystymi).

Pozostaje nam dodać jeszcze dwie operacje w tej samej pętli, tym razem po wykonaniu odczytu z kolumn. Pierwsza z nich to odjęcie od zmiennej W wartości zmiennej z – w ostatniej iteracji pętli odczytującej litery z kolumn osiągamy wartość przekraczającą liczbę liter w wiadomości. Drugą operacją natomiast jest zmiana znaku zmiennej z wynikająca z różnego sposobu zapisu kolumn zależnego od parzystości. W ten sposób otrzymujemy gotowy algorytm odszyfrowujący.

Przykładowy algorytm będący poprawnym rozwiązaniem zadania:

P ← n / k
W ← 0
z ← P
	dla i = 1, 2, ..., P wykonuj
	W ← W + 1
	dla j = 1, 2, ..., k wykonuj
 		T ← T + S[W] 
        W ← W + z
	W ← W - z
	z ← z * (-1)

Schemat oceniania

Słownik