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.
Twoim zadaniem jest rozszyfrować przechwycone wiadomości.
Za to zadanie można zdobyć 180 punktów.
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.