Zadanie 1

Szkolny klub naukowy NEUTRON swoje pozalekcyjne spotkania prowadzi online za pośrednictwem specjalnego komunikatora internetowego. Każda konwersacja wideo ma swój indywidualny identyfikator składający się z 16 wielkich liter alfabetu łacińskiego, przy czym żadna litera nie może w nim wystąpić więcej niż dwa razy. Dołączenie do spotkania wymaga znajomości identyfikatora.

Za każdym razem, gdy zaplanowane jest spotkanie klubu, jego przewodnicząca rozsyła uczestnikom e‑mail z wiadomością częściowo zaszyfrowaną algorytmem Vigenère’a.

Wiadomości zawierają pozornie losowe ciągi znaków składające się wyłącznie z:

• wielkich liter alfabetu łacińskiego,

• znaków przestankowych (kropek i przecinków),

• spacji.

Każdy członek po dołączeniu do klubu otrzymał instrukcję opisującą proces odczytywania identyfikatorów spotkań z przesyłanych wiadomości. Prezentuje się ona następująco:

GPWDRL. HZOMWDGEK, OJVU PWEBD. YHOWPQMAGRNPX DHSGAUAKO.
BE O NSZNTDRRF NPXG, ELZLHWO.

GPWDRL

BKSJFSAPO, LSKO AABKS. SSSTYFGLKOWER OLPPPOLOL.
KT I YWWWIXCVC WERR, IIIABHS.

TYFG

OLOL

IXCV

ABHS

TYFGOLOLIXCVABHS

Zadanie 1.1

Na twoją skrzynkę e‑mailową regularnie przesyłane są zaszyfrowane wiadomości dotyczące spotkania klubu naukowego NEUTRON, których długość nie przekracza 100 znaków.

W pliku dane.txt znajduje się zaszyfrowana wiadomość.

Napisz program, który wyszuka identyfikator konwersacji ukryty w zaszyfrowanej wiadomości zapisanej w pliku dane.txt (po uprzednim odszyfrowaniu wiadomości). Wynik zapisz w pliku wyniki1_1.txt.

Do oceny oddajesz:

• plik wyniki1_1.txt zawierający odpowiedź (identyfikator konwersacji),

• plik(i) z komputerową realizacją zadania (kodem programu).

Przykładowe rozwiązanie

Na początku korzystamy z dwóch tablic pomocniczych: kluczPomoc[0..p‑1] oraz szyfrPomoc[0..p‑1] (gdzie p oznacza długość wiadomości), do których zapisujemy odpowiednio odnaleziony klucz oraz zaszyfrowaną wiadomość. Nie są to jednak docelowe tablice, na których będziemy operować w dalszej części algorytmu. Obliczamy również liczbę znaków klucza a oraz liczbę znaków wiadomości b, które definiują rozmiar tablicy klucz[0..a‑1] i szyfr[0..b‑1].

Definiujemy dwie dodatkowe zmienne (x oraz j):

a ← 0
b ← 0
j ← 0
x ← 0

Do tablicy kluczPomoc[0..p‑1] zapisujemy kolejne litery wiadomości zawartej w tablicy mail[0..p‑1]. Jeżeli natrafimy na kropkę, przerywamy działanie pętli (zakładamy, że klucz został odnaleziony) i obliczamy indeks pierwszego elementu tablicy mail[0..p‑1] po odnalezionej kropce (przechowujemy go w zmiennej x). Jeżeli analizowany znak nie jest ani literą, ani kropką, przypisujemy zmiennym a oraz j ich początkowe wartości (odpowiednio 0 i 0), aby od nowa zacząć wypełniać tablicę kluczPomoc (pierwszym znakiem po poszukiwanym kluczu zawsze będzie kropka). Pamiętamy też o aktualizowaniu wartości przechowywanej w zmiennej a.

dla i = 0, 1, ..., p - 1 wykonuj:
	jeżeli znakDoKodu(mail[i]) = znakDoKodu('.'):
    	x ← i + 1 
        przerwij pętlę
    jeżeli znakDoKodu(mail[i]) ≥ znakDoKodu('A') i znakDoKodu(mail[i]) ≤ znakDoKodu('Z'):
    	kluczPomoc[j] ← mail[i]
        a ← a + 1
        j ← j + 1
	w przeciwnym razie:
        a ← 0
        j ← 0

Resztę wiadomości (rozpoczynając od elementu tablicy mail[0..p‑1] o indeksie x) zapisujemy do tablicy szyfrPomoc[0..p‑1].

j ← 0
dla i = x, x + 1, ..., p - 1 wykonuj:
	szyfrPomoc[j] ← mail[i]
    b ← b + 1
    j ← j + 1

Gdy już znamy liczbę znaków składających się na klucz oraz wiadomość, tworzymy dwie tablice: klucz[0..a - 1] oraz szyfr[0..b - 1], do których zapisujemy wyróżnione dwa ciągi znaków.

dla i = 0, 1, 2, ..., a - 1 wykonuj:
	klucz[i] ← kluczPomoc[i]
    
dla i = 0, 1, 2, ..., b - 1 wykonuj:
	szyfr[i] ← szyfrPomoc[i]

Następnie definiujemy zmienną j, która będzie przechowywać indeks aktualnie wykorzystywanej litery klucza. Inicjalizujemy zmienną wartością 0.

j ← 0

Wykorzystamy również tablicę wynik, której zadaniem jest przechowywanie identyfikatora spotkania. Jej długość jest równa 16, ponieważ jest to domyślna liczba znaków w identyfikatorze.

Teraz przejdziemy do rozszyfrowywania wiadomości. Wykorzystywanym kluczem będzie słowo FORMAT, natomiast pozostała treść przykładowego e‑maila prezentuje się następująco:

. NZBE PEXR, LGUPWYE XLI. NZCXAUHQ JMRM TZ, ZW DH. UCEE IPP ORMYQEJ CAL, NZFIMPIUPOVI. BBHP XOD UCB.

Deszyfracji podlegają jedynie litery wiadomości. Sprawdzamy, czy aktualnie deszyfrowany znak ma kod ASCII z zakresu od 65 (wielka litera A) do 90 (wielka litera Z).

dla i = 0, 1, 2, ..., b - 1 wykonuj:
	jeżeli znakDoKodu(szyfr[i]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[i]) ≤ znakDoKodu('Z'):

Jeżeli rozpatrywany znak jest literą, wówczas na podstawie klucza ustalamy odpowiadający mu znak tekstu jawnegotekst jawnytekstu jawnego. Od kodu ASCII elementu tablicy szyfr o indeksie i odejmujemy kod odpowiedniego znaku klucza, pomniejszony o 65 (kod litery A). Otrzymaną liczbę konwertujemy do znaku, po czym zapisujemy do i-tego elementu tablicy.

dla i = 0, 1, 2, ..., b - 1 wykonuj:
	jeżeli znakDoKodu(szyfr[i]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[i]) ≤ znakDoKodu('Z'):
		szyfr[i] ← kodDoZnaku(znakDoKodu(szyfr[i]) - (znakDoKodu(klucz[j]) - znakDoKodu('A')))

Należy uwzględnić sytuację, w której otrzymany znak nie jest wielką literą alfabetu łacińskiego. Dzieje się tak, gdy w wyniku opisanej operacji otrzymujemy kod ASCII mniejszy od liczby 65. Wówczas do kodu dodajemy 26 (rozmiar alfabetu), konwertujemy go do znaku, a następnie zapisujemy do tablicy szyfr.

dla i = 0, 1, 2, ..., b - 1 wykonuj:
	jeżeli znakDoKodu(szyfr[i]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[i]) ≤ znakDoKodu('Z'):
		szyfr[i] ← kodDoZnaku(znakDoKodu(szyfr[i]) - (znakDoKodu(klucz[j]) - znakDoKodu('A')))
		jeżeli znakDoKodu(szyfr[i]) < znakDoKodu('A'):
			szyfr[i] ← kodDoZnaku(znakDoKodu(szyfr[i]) + 26)

Po każdorazowym rozpatrzeniu znaku będącego literą, dokonujemy inkrementacji zmiennej j wskazującej aktualną literę klucza wykorzystywaną do procesu deszyfrowania. Jeżeli wykorzystamy już wszystkie litery klucza (wartość zmiennej j wyniesie a), wówczas kolejnej literze wiadomości odpowiadać będzie ponownie pierwszy znak klucza.

dla i = 0, 1, 2, ..., b - 1 wykonuj:
	jeżeli znakDoKodu(szyfr[i]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[i]) ≤ znakDoKodu('Z'):
		szyfr[i] ← kodDoZnaku(znakDoKodu(szyfr[i]) - (znakDoKodu(klucz[j]) - znakDoKodu('A')))
		jeżeli znakDoKodu(szyfr[i]) < znakDoKodu('A'):
			szyfr[i] ← kodDoZnaku(znakDoKodu(szyfr[i]) + 26)
		jeżeli j = a - 1:
			j ← 0
		w przeciwnym razie
			j ← j + 1

Przygotowana część programu pozwoli rozszyfrować otrzymaną wiadomość. Przejdźmy do odszukania w tekście jawnym identyfikatora.

Rozpoczynamy od definicji dwóch zmiennych: l i k, które przechowywać będą odpowiednio indeks aktualnie rozpatrywanego elementu tablicy szyfr (zawierającej już rozszyfrowaną wiadomość) oraz indeks tablicy wynik, do którego z kolei będziemy zapisywać następny odnaleziony znak identyfikatora.

l ← 0
k ← 0

W celu odnalezienia czteroznakowych fragmentów identyfikatora należy znaleźć w odszyfrowanej wiadomość trzy sąsiednie, powtarzające się litery. Warto zwrócić uwagę, że wcale nie musimy iterować po każdym elemencie tablicy szyfr. Możemy założyć, że jeżeli wśród siedmiu ostatnich znaków wiadomości pierwsze trzy litery nie są identyczne, to z pewnością cztery kolejne nie stanowią poszukiwanego identyfikatora. Tę zależność wyrazimy poprzez warunek pętli dopóki.

dopóki k < (b - 6) wykonuj:

Podobnie jak w przypadku procesu deszyfrowania również podczas poszukiwania identyfikatora rozpatrujemy jedynie litery alfabetu.

dopóki k < (b - 6) wykonuj:
	jeżeli znakDoKodu(szyfr[k]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[k]) ≤ znakDoKodu('Z'):

Jeżeli analizowany znak okaże się literą, sprawdzamy, czy dwa kolejne elementy tablicy (o indeksach odpowiednio k + 1 oraz k + 2) zawierają tę samą literę.

dopóki k < (b - 6) wykonuj:
	jeżeli znakDoKodu(szyfr[k]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[k]) ≤ znakDoKodu('Z'):
		jeżeli szyfr[k] = szyfr[k + 1] i szyfr[k] = szyfr[k + 2]:

Jeśli warunek ten zostanie spełniony, do czterech kolejnych elementów tablicy wynik zapisujemy odnalezione litery identyfikatora. Podczas tego procesu pamiętajmy o każdorazowym inkrementowaniu zmiennej l.

dopóki k < (b - 6) wykonuj:
	jeżeli znakDoKodu(szyfr[k]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[k]) ≤ znakDoKodu('Z'):
		jeżeli szyfr[k] = szyfr[k + 1] i szyfr[k] = szyfr[k + 2]:
			dla i = 0, 1, 2, 3 wykonuj:
				wynik[l] ← szyfr[k + 3 + i]
				l ← l + 1

Ostatnim krokiem jest zwiększanie wartości zmiennej k. Jeżeli aktualnie sprawdzany znak nie jest literą bądź nie rozpoczyna trzyznakowego ciągu wskazującego na obecność identyfikatora, wówczas wykonujemy inkrementację zmiennej. W przypadku gdy odnaleźliśmy fragment identyfikatora, do wartości zmiennej k dodajemy 6, ponieważ w ramach procesu zapisu identyfikatora do tablicy wynik w sumie rozpatrujemy siedem kolejnych znaków (aktualnie rozpatrywany znak, dwa kolejne identyczne znaki oraz czteroliterowy kod).

dopóki k < (b - 6) wykonuj:
	jeżeli znakDoKodu(szyfr[k]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[k]) ≤ znakDoKodu('Z'):
		jeżeli szyfr[k] = szyfr[k + 1] i szyfr[k] = szyfr[k + 2]:
			dla i = 0, 1, 2, 3 wykonuj:
				wynik[l] ← szyfr[k + 3 + i]
				l ← l + 1
			k ← k + 6
		w przeciwnym razie:
			k ← k + 1
	w przeciwnym razie:        
		k ← k + 1

Zwracamy tablicę z identyfikatorem spotkania.

zwróć wynik

Gotowy algorytm zapisany za pomocą pseudokodu wygląda następująco:

a ← 0
b ← 0
j ← 0
x ← 0

dla i = 0, 1, ..., p - 1 wykonuj:
	jeżeli znakDoKodu(mail[i]) = znakDoKodu('.'):
    	x ← i + 1 
        przerwij pętlę
    jeżeli znakDoKodu(mail[i]) ≥ znakDoKodu('A') i znakDoKodu(mail[i]) ≤ znakDoKodu('Z'):
    	kluczPomoc[j] ← mail[i]
        a ← a + 1
        j ← j + 1
	w przeciwnym razie:
        a ← 0
        j ← 0

j ← 0

dla i = x, x + 1, ..., p - 1 wykonuj:
	szyfrPomoc[j] ← mail[i]
    b ← b + 1
    j ← j + 1

dla i = 0, 1, 2, ..., a - 1 wykonuj:
	klucz[i] ← kluczPomoc[i]
    
dla i = 0, 1, 2, ..., b - 1 wykonuj:
	szyfr[i] ← szyfrPomoc[i]

j ← 0

dla i = 0, 1, 2, ..., b - 1 wykonuj:
	jeżeli znakDoKodu(szyfr[i]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[i]) ≤ znakDoKodu('Z'):
		szyfr[i] ← kodDoZnaku(znakDoKodu(szyfr[i]) - (znakDoKodu(klucz[j]) - znakDoKodu('A')))
		jeżeli znakDoKodu(szyfr[i]) < znakDoKodu('A'):
			szyfr[i] ← kodDoZnaku(znakDoKodu(szyfr[i]) + 26)
		jeżeli j = a - 1:
			j ← 0
		w przeciwnym razie
			j ← j + 1

l ← 0
k ← 0

dopóki k < (b - 6) wykonuj:
	jeżeli znakDoKodu(szyfr[k]) ≥ znakDoKodu('A') i znakDoKodu(szyfr[k]) ≤ znakDoKodu('Z'):
		jeżeli szyfr[k] = szyfr[k + 1] i szyfr[k] = szyfr[k + 2]:
			dla i = 0, 1, 2, 3 wykonuj:
				wynik[l] ← szyfr[k + 3 + i]
				l ← l + 1
			k ← k + 6
		w przeciwnym razie:
			k ← k + 1
	w przeciwnym razie:        
		k ← k + 1

zapisz wynik do pliku "wyniki1_1.txt"

Odpowiedź

Odpowiedź do zadania znajduje się w pliku wyniki1_1.txt:

Zadanie 1.2.

Poproszono cię o przygotowanie wiadomości z zaszyfrowanym identyfikatorem spotkania klubu NEUTRON. Przewodnicząca przekazała ci wzór niezaszyfrowanej wiadomości. Symbolem „*” oznaczone są w nim pozycje, na których powinny znaleźć się znaki docelowego identyfikatora. Sam identyfikator wysłany został w osobnej wiadomości. Wzór wiadomości znajduje się w pierwszej linijce w pliku tekstowym dane2.txt, natomiast identyfikator w drugiej.

Napisz program, który w odpowiednie miejsca wzoru wiadomości wprowadzi litery kodu spotkania, a następnie zaszyfruje wiadomość (z wyłączeniem klucza na początku tekstu, który należy wykorzystać do szyfrowania). Wynik zapisz w pliku wyniki1_2.txt.

Do oceny oddajesz:

• plik wyniki1_2.txt zawierający odpowiedź (uzupełnioną i zaszyfrowaną wiadomość);

• plik(i) z komputerową realizacją zadania (kodem programu).

Wzór wiadomości i identyfikator znajdują się w pliku dane2.txt:

Przykładowe rozwiązanie

Na początek z tablicy wzor[0..p - 1], do której została wczytana pierwsza linijka pliku z danymi, odczytujemy ciąg znaków stanowiący klucz szyfrujący. Identyfikator, czyli drugą linijkę pliku z danymi, zapisujemy w tablicy identyfikator[0..15].

a ← 0
j ← 0

dla i = 0, 1, 2, ..., p - 1 wykonuj:
	jeżeli znakDoKodu(wzor[i]) = znakDoKodu('.'):
        przerwij pętlę
    jeżeli znakDoKodu(wzor[i])  ≥ znakDoKodu('A') i znakDoKodu(wzor[i]) ≤ znakDoKodu('Z'):
    	kluczPomoc[j] ← wzor[i]
        a ← a + 1
        j ← j + 1
	w przeciwnym razie:
        a ← 0
        j ← 0

dla i = 0, 1, 2, ..., a - 1 wykonuj:
	klucz[i] ← kluczPomoc[i]

Następnie definiujemy zmienną k, która przechowywać będzie indeks litery aktualnie zapisywanej w wyznaczonym miejscu w wiadomości. Inicjalizujemy zmienną wartością 0. Wykorzystamy również tablicę wynik2[0..p‑1], do której zapiszemy zaszyfrowaną wiadomość.

k ← 0

Przechodzimy po wszystkich znakach wiadomości, poszukując znaków „*” – gdy na taki natrafimy, w jego miejsce wpisujemy k-ty znak identyfikatora oraz inkrementujemy zmienną k.

dla i = 0, 1, 2, ..., p - 1 wykonuj:
	jeżeli znakDoKodu(wzor[i]) = znakDoKodu('*'):
		wzor[i] ← identyfikator[k]
		k ← k + 1

Następnym krokiem jest zdefiniowanie zmiennej l oraz zainicjalizowanie jej wartością 0. Zmienną tę wykorzystamy do przechowywania indeksu elementu tablicy wzor, będącego pierwszym znakiem po kluczu szyfrującym. Z treści zadania wiemy, że będzie to pierwsza kropka w wiadomości.

l ← 0

W kolejnym kroku wyszukujemy w wiadomości pierwszą kropkę, a następnie zapisujemy do zmiennej l indeks elementu tablicy wzor, w którym jest przechowywana.

dla i = 0, 1, 2, ..., p - 1 wykonuj:
	jeżeli znakDoKodu(wzor[i]) = znakDoKodu('.'):
		l ← i
        przerwij pętlę

Wiemy teraz, że proces szyfrowania wiadomości rozpoczniemy od l-tego elementu tablicy wzor. Dodatkowo definiujemy zmienną j, która przechowywać będzie indeks litery klucza aktualnie wykorzystywanej w procesie szyfrowania. Inicjalizujemy ją wartością 0.

j ← 0

Proces szyfrowania przebiegać będzie podobnie do omówionej wcześniej operacji deszyfrowania. Dodatkowo znaki nieprzeznaczone do szyfrowania będziemy bezpośrednio przepisywać do tablicy wynik2.

dla i = 0, 1, 2, ..., p - 1 wykonuj:
	jeżeli i ≤ l:
		wynik2[i] = wzor[i]
	w przeciwnym razie
		jeżeli znakDoKodu(wzor[i]) ≥ znakDoKodu('A') i znakDoKodu(wzor[i]) ≤ znakDoKodu('Z'):
			wynik2[i] ← kodDoZnaku(znakDoKodu(wzor[i]) + (znakDoKodu(klucz[j]) - znakDoKodu('A')))
			jeżeli znakDoKodu(wynik2[i]) > znakDoKodu('Z'):
				wynik2[i] ← kodDoZnaku(znakDoKodu(wynik2[i]) - 26)
			jeżeli j = a - 1:
				j ← 0
			w przeciwnym razie
				j ← j + 1
		w przeciwnym razie
			wynik2[i] ← wzor[i]

Gotowy program zapisany za pomocą pseudokodu wygląda następująco:

a ← 0
j ← 0

dla i = 0, 1, 2, ..., p - 1 wykonuj:
	jeżeli znakDoKodu(wzor[i]) = znakDoKodu('.'):
        przerwij pętlę
    jeżeli znakDoKodu(wzor[i])  ≥ znakDoKodu('A') i znakDoKodu(wzor[i]) ≤ znakDoKodu('Z'):
    	kluczPomoc[j] ← wzor[i]
        a ← a + 1
        j ← j + 1
	w przeciwnym razie:
        a ← 0
        j ← 0

dla i = 0, 1, 2, ..., a - 1 wykonuj:
	klucz[i] ← kluczPomoc[i]

k ← 0

dla i = 0, 1, 2, ..., p - 1 wykonuj:
	jeżeli znakDoKodu(wzor[i]) = znakDoKodu('*'):
		wzor[i] ← identyfikator[k]
		k ← k + 1

l ← 0

dla i = 0, 1, 2, ..., p - 1 wykonuj:
	jeżeli znakDoKodu(wzor[i]) = znakDoKodu('.'):
		l ← i
        przerwij pętlę

j ← 0

dla i = 0, 1, 2, ..., p - 1 wykonuj:
	jeżeli i ≤ l:
		wynik2[i] = wzor[i]
	w przeciwnym razie
		jeżeli znakDoKodu(wzor[i]) ≥ znakDoKodu('A') i znakDoKodu(wzor[i]) ≤ znakDoKodu('Z'):
			wynik2[i] ← kodDoZnaku(znakDoKodu(wzor[i]) + (znakDoKodu(klucz[j]) - znakDoKodu('A')))
			jeżeli znakDoKodu(wynik2[i]) > znakDoKodu('Z'):
				wynik2[i] ← kodDoZnaku(znakDoKodu(wynik2[i]) - 26)
			jeżeli j = a - 1:
				j ← 0
			w przeciwnym razie
				j ← j + 1
		w przeciwnym razie
			wynik2[i] ← wzor[i]	

zapisz wynik2 do pliku "wyniki1_2.txt"

Odpowiedź

Odpowiedź do zadania znajduje się w pliku wyniki1_2.txt:

Słownik