Zadanie 1. Szyfr przestawieniowy (7 pkt)
Szyfrowanie przestawieniowe jest klasyczną metodą szyfrowania polegającą na zmianie
kolejności liter w szyfrowanym tekście. Często używa się reguł zamiany opartych na różnych
figurach geometrycznych - w tym zadaniu użyjemy kwadratu. Szyfrowanie będzie polegało
na wprowadzeniu tekstu do kwadratowej tablicy szyfrującej o wymiarach n
n
× po kolei
wierszami, a następnie odczytaniu tekstu z tablicy kolumnami od lewej do prawej. Wymiar n
tablicy jest najmniejszą liczbą, przy której tekst zmieści się w całości w kwadracie n n
× .
W przypadku, gdy tekst jest krótszy i nie wypełnia wszystkich pól tablicy, puste pola
uzupełnia się znakami odstępu. W tym zadaniu znaki odstępu będziemy oznaczać
Przykład:
Załóżmy, że tekst ALGORYTM_PRZESTAWIENIOWY ma być zaszyfrowany w tablicy
kwadratowej. Liczba znaków w tekście do zaszyfrowania jest równa 24, czyli tablica
szyfrująca ma wymiary 5×5 . Ostatni element tablicy będzie uzupełniony znakiem odstępu.
Tekst zapisujemy do tablicy wierszami.
A
L
G
O
R
Y
T
M
P
R
Z
E
S
T
A
W
I
E
N
I
O
W
Y
Następnie odczytujemy zaszyfrowany tekst kolumnami:
AYRAILTZWOGMEIWO_SEYRPTN_
a) Podaj wzór na liczbę wierszy i kolumn tablicy kwadratowej używanej do szyfrowania
tekstu o długości d znaków lub opisz algorytm wyznaczania tej liczby (w postaci listy
kroków, schematu blokowego lub w wybranym języku programowania).
kierunek odczytywania
zaszyfrowanego tekstu
kierunek wprowadzania
szyfrowanego tekstu
Poziom rozszerzony - część I
3
b) Do zaszyfrowania pewnego cytatu z Sokratesa użyto metody opisanej w podpunkcie a).
Rozszyfruj ten cytat. Poniższy szyfr składa się z 64 znaków.
BTLLTU_ĘL_EOYPM_ĄPJZLCYNDREOKYLI_ZMFO_ĄGJY_Ó_N_DEWFWGISYSII_
ŁEI_
c) Zapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku
programowania), który szyfruje zadany tekst sposobem opisanym w tym zadaniu i jest
zgodny z poniższą specyfikacją.
Specyfikacja
Dane:
d - dodatnia liczba całkowita, długość tekstu do zaszyfrowania
tekst[1…d] - tablica zawierająca tekst do zaszyfrowania, gdzie tekst[i], to i-ty znak w tekście
do zaszyfrowania
Wynik:
s - dodatnia liczba całkowita, długość tekstu po zaszyfrowaniu
szyfr[1…s] - tablica zawierająca tekst po zaszyfrowaniu, gdzie szyfr[i], to i-ty znak w tekście
po zaszyfrowaniu
Poziom rozszerzony - część I
4
Algorytm
Nr zadania
1a)
1b)
1c)
Maks. liczba pkt
1
1
5
Wypełnia
egzaminator Uzyskana liczba pkt
Poziom rozszerzony - część I
5
Oficjalna odpowiedź CKE (Klucz punktowania odpowiedzi, poziom rozszerzony, maj 2010):
\nZadanie 1. Szyfr przestawieniowy (7 pkt) — a), b), c):
\na) (1 pkt) Wzór na wymiar tablicy kwadratowej dla tekstu o długości d znaków:
n = ⌈√d⌉ (najmniejsza liczba naturalna większa lub równa √d).
b) (1 pkt) Rozszyfrowany cytat z Sokratesa:
BŁĄD JEST PRZYWILEJEM FILOZOFÓW TYLKO GŁUPCY NIE MYLĄ SIĘ NIGDY
c) (5 pkt) Przykładowy algorytm szyfrujący (Java), zgodny ze specyfikacją (dane: d, tekst[1..d]; wynik: s, szyfr[1..s]):
\npublic char[] szyfruj(char[] tekst) {
int d = tekst.length;
int n = (int) Math.ceil(Math.sqrt(d));
char[][] tab = new char[n][n];
int znak = 0;
for (int i = 0; i < tab.length; i++) {
char[] cs = tab[i];
for (int j = 0; j < cs.length; j++) {
if (znak >= d) {
cs[j] = ' ';
} else {
cs[j] = tekst[znak];
}
znak++;
}
}
int s = n*n;
char szyfr[] = new char[s];
znak = 0;
for (int i = 0; i < tab.length; i++) {
char[] cs = tab[i];
for (int j = 0; j < cs.length; j++) {
szyfr[znak] = tab[j][i];
znak++;
}
}
return szyfr;
}
Punktacja za c): 5 pkt za w pełni poprawny algorytm (1 pkt za poprawne n, 1 pkt za poprawne s,
2 pkt za poprawne indeksowanie przy szyfrowaniu, 1 pkt za uzupełnienie tekstu znakami odstępu do długości s).