Prezentacja multimedialna

Zadanie 2

Zadanie zostało opracowane na podstawie zadania maturalnego przygotowanego przez Centralną Komisję Egzaminacyjną. Oryginalne zadanie oznaczone numerem 77 znajduje się w zbiorze zadań maturalnych z informatyki, dostępnym na stronie internetowej CKE.

W zadaniu rozważamy teksty zbudowane tylko z wielkich liter alfabetu angielskiego, znaków odstępu i znaków przestankowych (przecinek, kropka). Oto litery alfabetu i numery ich pozycji w alfabecie:

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
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Szyfrowanie Vigenère’a polega na zastąpieniu każdej litery tekstu źródłowego literą odległą od niej cyklicznie w alfabecie o k pozycji.

Wartość k nie jest z góry ustalona dla całego tekstu źródłowego, lecz dla każdej litery w tekście jest określana osobno, zależnie od słowa przyjętego jako klucz szyfrowania.

Przystępując do szyfrowania, należy przyporządkować kolejnym literom tekstu źródłowego kolejne litery klucza, chodząc po nim cyklicznie, jeśli jest krótszy od szyfrowanego tekstu. Znaki inne niż litery nie są szyfrowane, pomijamy je podczas przypisywania liter klucza. Pozycja litery klucza w alfabecie jest tą wartością k, o jaką należy wykonać przesunięcie względem litery tekstu źródłowego w celu znalezienia odpowiadającej jej litery szyfru.

Przykład

Tekst źródłowy: JEST OK, klucz: EWA

tekst źródłowy	J	E	S	T	spacja	O	K
Klucz	E	W	A	E		W	A
pozycja litery klucza	4	22	0	4		22	0
Szyfr	J → 4 = N	E → 22 = A	S → 0 = S	T → 4 = X	spacja	O → 22 = K	K → 0 = K

Wynik szyfrowania: NASX KK.

Napisz w wybranym języku programowania program, który wyznaczy rozwiązania zadań podanych niżej.

Ważne!

Do wykonania zadań przydatne będzie zaokrąglanie wartości oraz operowanie na kodach ASCII, pozwalających reprezentować wybrane znaki, np. litery, cyfry czy znaki interpunkcyjne w postaci liczb całkowitych z zakresu od 0 do 127.

Zdefiniujmy trzy dodatkowe funkcje, które wykorzystamy w pseudokodzie:

znakDoKodu(znak)– funkcja, która jako parametr przyjmuje pojedynczy znak, a następnie konwertuje go na odpowiadający mu kod ASCII i zwraca otrzymaną wartość liczbową,
kodDoZnaku(kod) – funkcja, która jako parametr przyjmuje kod ASCII w postaci liczby całkowitej z zakresu od 0 do 127, a następnie konwertuje ją na odpowiadający jej znak oraz go zwraca.

Zadanie 2.1

W pliku szyfr.txt zapisano dwa wiersze tekstu. W pierwszym wierszu pliku zawarta została wiadomość zaszyfrowana algorytmem Vigenère’a. W drugim wierszu znajduje się klucz użyty do tego szyfrowania. Szyfr zawiera wiele słów. Jego łączna długość nie przekracza 1024 znaków. Szyfrowaniu podlegały tylko wielkie litery tekstu, zaś odstępy i znaki przestankowe pozostały bez zmiany.

Odszyfruj tekst i umieść jego postać źródłową w pliku z odpowiedziami.

Plik szyfr.txt składa się z dwóch wierszy. Oba zawierają łańcuchy znaków. Pierwszy jest zbudowany wielkich liter alfabetu łacińskiego, znaków przestankowych (kropek i przecinków) oraz odstępów (znaków spacji) i reprezentuje zaszyfrowaną wiadomość. Drugi zbudowany jest z wielkich liter alfabetu łacińskiego i reprezentuje klucz szyfrujący.

RRhc6u0hudHFQ

Przycisk do pobrania pliku TXT z treścią zadania.

Plik TXT o rozmiarze 406.00 B w języku polskim

Napisz program, który odszyfruje zapisany w załączonym pliku szyfrogram, wykorzystując podany w tym samym pliku klucz. Odszyfrowany tekst zapisz do pliku wyniki2_1.txt.

Do oceny oddajesz:

plik wyniki2_1.txt zawierający odpowiedź (odszyfrowany tekst),
plik(i) z komputerową realizacją zadania (kodem programu).

Polecenie 1

Rozwiąż zadanie dla danych z pliku szyfr.txt. Wykorzystaj w tym celu jeden z języków programowania: C++, Java lub Python. Zadbaj o prawidłowe wczytanie danych z pliku tekstowego do programu. Odpowiedź do zadania znajdziesz w osobnym pliku, umieszczonym po omówieniu przykładowego rozwiązania w formie pseudokodu.

Przykładowe rozwiązanie

RaUZ1uyiLna5O1

Odpowiedź

Odpowiedź do zadania znajduje się w pliku wyniki2_1.txt.

R1dMqC4Qg19U7

Plik TXT o rozmiarze 393.00 B w języku polskim

Zadanie 2.2

Podaj liczby wystąpień poszczególnych liter A, B, ..., Z w treści szyfru zawartego w pierwszym wierszu pliku szyfr.txt.

Napisz program, który obliczy liczbę wystąpień poszczególnych liter w zaszyfrowanej wiadomości zapisanej w pierwszym wierszu pliku szyfr.txt i zapisze wyznaczone wartości w pliku wyniki2_2.txt. Liczby wystąpień poszczególnych liter powinny zostać zapisane w osobnych wierszach w formacie litera - liczba wystąpień litery w kolejności alfabetycznej.

Przykładowa forma zapisu rozwiązania:

A - liczba wystąpień litery A
B - liczba wystąpień litery B
C - liczba wystąpień litery B
...
Z - liczba wystąpień litery Z

Do oceny oddajesz:

plik tekstowy wyniki2_2.txt (zawierający informacje na temat liczby wystąpień poszczególnych liter w zaszyfrowanej wiadomości),
plik(i) z komputerową realizacją zadania (kodem programu).

Polecenie 2

Rozwiąż zadanie dla danych z pliku szyfr.txt. Wykorzystaj w tym celu jeden z języków programowania: C++, Java lub Python. Zadbaj o prawidłowe wczytanie danych z pliku tekstowego do programu. Odpowiedź do zadania znajdziesz w osobnym pliku umieszczonym po omówieniu przykładowego rozwiązania w formie pseudokodu.

Zapisz wyznaczone wartości w pliku wyniki2_2.txt. Liczby wystąpień poszczególnych liter powinny zostać zapisane w osobnych wierszach w formacie litera - liczba wystąpień litery w kolejności alfabetycznej.

Przykładowe rozwiązanie

RNepXgp6CB4lJ

Odpowiedź

Odpowiedź do zadania znajduje się w pliku wyniki2_2.txt.

Ry6I1BjdyVSmG

Plik TXT o rozmiarze 200.00 B w języku polskim

Zadanie 2.3

Chcąc złamać szyfr Vigenère’a bez znajomości klucza, w pierwszym kroku należy oszacować długość klucza (rozumianą jako liczba znaków). Istnieje przybliżony wzór na szacunkową długość klucza $d$ danego szyfru Vigenère’a dla tekstu nad alfabetem 26‑literowym (oszacowanie jest tym lepsze, im dłuższy jest szyfr):

d = \frac{0, 0285}{K_{0} - 0, 0385}

gdzie:

$K_{0}$ – indeks koincydencji znaków obliczany następująco:

K_{0} = \frac{l_{A} \cdot (l_{A} - 1) + l_{B} \cdot (l_{B} - 1) + . . . + l_{Z} \cdot (l_{Z} - 1)}{n \cdot (n - 1)}

$n$ – łączna liczba wystąpień wszystkich liter w tekście szyfrogramu (nie liczymy odstępów i znaków przestankowych),
$l_{A}, l_{B}, . . ., l_{Z}$ – liczby wystąpień poszczególnych liter A, B, …, Z w tekście szyfru.

Wykorzystując powyższe wzory, wyznacz szacunkową długość klucza dla szyfru danego w pierwszym wierszu pliku szyfr.txt i porównaj z dokładną długością klucza umieszczonego w drugim wierszu tego pliku. Wypisz obie wartości, wartość szacunkową zaokrąglij do 2 cyfr po przecinku.

Do oceny oddajesz:

plik wyniki2_3.txt zawierający odpowiedź (szacowaną i rzeczywistą długość klucza zapisane w osobnych wierszach),
plik(i) z komputerową realizacją zadania (kodem programu).

Polecenie 3

Wyniki zapisz do pliku wyniki2_3.txt w osobnych wierszach (wartość szacowana w pierwszym wierszu). Wartość szacunkową zaokrąglij do dwóch cyfr po przecinku.

Przykładowe rozwiązanie

R5ioCMCmafGsT1

Odpowiedź

Odpowiedź do zadania zapisana jest w pliku wyniki2_3.txt.

Ra4jgTIXcvbIO

Plik TXT o rozmiarze 9.00 B w języku polskim

Przeczytaj

Sprawdź się

Zadanie 2

Zadanie 2.1

Przykładowe rozwiązanie

Odpowiedź

Zadanie 2.2

Przykładowe rozwiązanie

Odpowiedź

Zadanie 2.3

Przykładowe rozwiązanie

Odpowiedź

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
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

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
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

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
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25