Szyfry

Limit pamięci: 64 MB

Bajtoccy szpiedzy przechwycili pięć zaszyfrowanych wiadomości. Agencja wywiadowcza BIA dowiedziała się, jakimi algorytmami są one zaszyfrowane, oraz dostała informację, że teksty:

• są w języku angielskim,
• zawierają tylko znaki o kodach ASCII od 32 do 126 oraz znak nowego wiersza o kodzie 10,
• nie zawierają małych liter.

Wejście

W dziale Pliki znajdziesz paczkę z załącznikiem do tego zadania. Znajdują się w niej wszystkie wejścia, na których oceniane będzie Twoje rozwiązanie. Każdy plik wejściowy zawiera zaszyfrowaną wiadomość. Dokładna specyfikacja wejścia podana jest w opisach kolejnych podzadań.

Wyjście

Na wyjście należy wypisać odszyfrowaną wiadomość.

Podzadania

Wiadomość 0 (0 punktów)

To jest wiadomość z przykładu. Jest ona zaszyfrowana przez odwrócenie kolejności bajtów wiadomości.

Pierwszy wiersz wejścia zawiera słowo reverse. Drugi wiersz zawiera liczbę oznaczającą długość tekstu. Trzeci wiersz zawiera kody ASCII kolejnych znaków tekstu, w odwróconej kolejności.

Wiadomość 1 (30 punktów)

Ta wiadomość zaszyfrowana jest szyfrem Cezara. Każda wielka litera zamieniona jest na literę znajdującą się o pozycji dalej w porządku alfabetycznym (dla pewnego ustalonego ). Rozważamy alfabet angielski i zakładamy, że kolejnymi literami po literze Z są A, B, C itd.

Przykładowo, jeśli , to A zamienione jest na C, a Z na B. Wszystkie znaki niebędące wielkimi literami pozostawione są bez zmian.

Pierwszy wiersz wejścia zawiera słowo caesar. Drugi wiersz zawiera liczbę oznaczającą długość tekstu. Trzeci wiersz zawiera kody ASCII kolejnych znaków zaszyfrowanego tekstu.

Wiadomość 2 (50 punktów)

Ta wiadomość zaszyfrowana jest szyfrem XOR zdefiniowanym poniżej.

Klucz składa się z () bajtów, które oznaczamy . Jeśli kolejne bajty -bajtowego tekstu oznaczymy przez , to -ty bajt tekstu () zaszyfrowany jest przy pomocy wzoru .

Pierwszy wiersz wejścia zawiera słowo xor. Drugi wiersz zawiera liczbę określającą długość tekstu. Trzeci wiersz zawiera kody ASCII kolejnych znaków zaszyfrowanego tekstu.

Wiadomość 3 (50 punktów)

Ta wiadomość zaszyfrowana jest szyfrem podstawieniowym. Każdą wielką literę zamieniamy na literę . Żadne dwie litery nie są zamieniane na tę samą literę. Innymi słowy to permutacja wielkich liter. Inne znaki pozostawione są bez zmian.

Pierwszy wiersz wejścia zawiera słowo substitution. Drugi wiersz zawiera liczbę określającą długość tekstu. Trzeci wiersz zawiera kody ASCII kolejnych znaków zaszyfrowanego tekstu.

Wiadomość 4 (50 punktów)

Ta wiadomość zaszyfrowana jest szyfrem RSA.

Pierwszy wiersz wejścia zawiera słowo rsa. Drugi wiersz wejścia zawiera liczbę . Trzeci wiersz wejścia zawiera liczbę . Czwarty wiersz wejścia zawiera liczbę , reprezentującą zaszyfrowaną wiadomość.

Liczby i to klucz publiczny szyfru RSA. Liczba jest postaci , gdzie i to dwie liczby pierwsze. Ponadto , oraz .

Wiadomość najpierw zamieniamy na liczbę , przez potraktowanie tekstu jako ciągu cyfr w systemie o podstawie 27. Pierwszy znak tekstu odpowiada najbardziej znaczącej cyfrze. Literze A odpowiada wartość , literze B wartość itd. Wszystkie znaki wiadomości to wielkie litery.

Zaszyfrowana wiadomość to liczba , gdzie . Należy odszyfrować wiadomość, skonwertować do postaci tekstowej i wypisać na wyjście.

Wskazówka pierwsza Niech będzie liczbą pierwszą oraz będzie liczbą względnie pierwszą z . Wówczas .

Wskazówka druga. Na Twoim komputerze zainstalowany jest program bc, który potrafi obliczać wartości prostych wyrażeń arytmetycznych i obsługuje liczby o wielu dziesiątkach cyfr.

Przykład

Dla danych wejściowych:

reverse
14
69 71 65 83 83 69 77 32 84 69 82 67 69 83

poprawną odpowiedzią jest:

SECRET MESSAGE

Autor zadania: Tomasz Czajka.