Gynvael rozpoczął nową świecką tradycję podrzucania prostych zadanek programistycznych na końcu swoich streamów. W tym poście opiszę jak doszedłem do rozwiązania i dlaczego zajęło mi to więcej czasu niż powinno.
Zadanie pierwsze polega na złamaniu części klucza na podstawie kilku wiadomości “zaszyfrowanych” xorem przy użyciu jednakowego klucza. Wiadomości to pojedyncze słowa w języku angielskim, a dane wejściowe wyglądają tak:
1f9111 1799 0790001226d8 0a9e1e5c3ada 1f 099e195e 0a97075a21dac1 0a9710 199e075131d3 1199 12961350 |
Uwaga, niżej są spoilery.
Przygotowanie danych
Uznałem, że do rozwiązania użyję C++. Aby to zrobić musiałem doprowadzić dane wejściowe do akceptowalnej postaci. Użyłem do tego prostego (i zapewne brzydkiego) skryptu w ruby:
data = <<X 1f9111 1799 0790001226d8 0a9e1e5c3ada 1f 099e195e 0a97075a21dac1 0a9710 199e075131d3 1199 12961350 X puts data.lines.map(&:strip).map{|l| '"%s"' % l.chars.each_slice(2).map(&:join).map{|x| "\\x#{x}" }.join }.join(", \n") |
Na jego wyjściu otrzymałem tablicę gotową do wklejenia do programu w C++:
"\x1f\x91\x11", "\x17\x99", "\x07\x90\x00\x12\x26\xd8", "\x0a\x9e\x1e\x5c\x3a\xda", "\x1f", "\x09\x9e\x19\x5e", "\x0a\x97\x07\x5a\x21\xda\xc1", "\x0a\x97\x10", "\x19\x9e\x07\x51\x31\xd3", "\x11\x99", "\x12\x96\x13\x50" |
Algorytm
Uznałem, że najszybszą metodą będzie iteracyjne ręczne sprawdzanie kolejnych znaków klucza. Znając pierwszą literę, liczba dwuliterowych poprawnych słów jest ograniczona. Ponadto, pierwsze dwie litery muszą być poprawnymi pierwszymi dwoma literami angielskich słów dla wszystkich pozostałych wyrazów (czyli np. xx odpada).
Jeśli zaś chodzi o pierwszy znak klucza, to sprawa wydawała się oczywista – w końcu jest tylko jedno jednoliterowe słowo: I, więc pierwszym znakiem klucza powinno być 1f16 ⊕ 4916, gdzie 1f16 to jedyny jednoznakowy string w danych, a 4916 to kod ASCII litery I.
Implementacja
Utworzyłem tablicę stringów wejściowych poprawiając jednocześnie trzeci string (ponieważ zawiera on zero tradycyjnie kończące C-stringa):
static const string foo[] = { "\x1f\x91\x11", "\x17\x99", string("\x07\x90\x00\x12\x26\xd8", 6), "\x0a\x9e\x1e\x5c\x3a\xda", "\x1f", "\x09\x9e\x19\x5e", "\x0a\x97\x07\x5a\x21\xda\xc1", "\x0a\x97\x10", "\x19\x9e\x07\x51\x31\xd3", "\x11\x99", "\x12\x96\x13\x50" }; |
Napisałem prostą funkcję xorującą:
string decrypt(string const& s, string const& k) { string ret(s.size(), '?'); for(size_t i{}; i < s.size(); ++i) { auto c = s[i] ^ k[i % k.size()]; if(isprint(c)) ret[i] = c; } return ret; } |
Pożyczyłem ze Stacka funkcję do ładnego printowania hexów:
std::string string_to_hex(const std::string& input) { static const char* const lut = "0123456789ABCDEF"; size_t len = input.length(); std::string output; output.reserve(2 * len); for (size_t i = 0; i < len; ++i) { const unsigned char c = input[i]; output.push_back(lut[c >> 4]); output.push_back(lut[c & 15]); } return output; } |
Obliczyłem pierwszy znak klucza: 1f16 ⊕ 4916 = 5616. Ustawiłem go w kodzie:
const string key = "\x56" "*******************"; |
I przystąpiłem do rozwiązywania:
int main() { for(auto const& s : foo) { cout << setw(20) << left << string_to_hex(s) << decrypt(s, key) << endl; } } |
Odpaliłem program i… Pojawił się drobny problem: część wyrazów zaczynała się od znaków \ i _. Wyjście przedstawiało się następująco:
1F9111 I?;
1799 A?
0790001226D8 Q?*8??
0A9E1E5C3ADA \?4v??
1F I
099E195E _?3t
0A97075A21DAC1 \?-p???
0A9710 \?:
199E075131D3 O?-{??
1199 G?
12961350 D?9z |
Co poszło nie tak?
Po długich minutach szukania błędu w trywialnej implementacji poszedłem po rozum do głowy i zastanowiłem się, czy na pewno I jest jedynym angielskim jednoliterowym słowem. Spoiler: nie jest, przedimek a również jest kwalifikowany jako słowo.
Rozwiązanie
Po zmianie pierwszego znaku klucza na 1f16 ⊕ 6116 = 7e16, otrzymane wyniki były znacznie bardziej zachęcające:
1F9111 a?;
1799 i?
0790001226D8 y?*8??
0A9E1E5C3ADA t?4v??
1F a
099E195E w?3t
0A97075A21DAC1 t?-p???
0A9710 t?:
199E075131D3 g?-{??
1199 o?
12961350 l?9z |
Uzyskanie kolejnego znaku było już bardzo proste. Oba dwuliterowe wyrazy miały tę samą drugą literę (9916 po xorowaniu z kluczem), więc mogły to być tylko pary in/on oraz if/of (ale już np. or odpada, bo ir nie jest słowem).
Podstawienie pod drugi znak 9916 ⊕ 6616 = ff16 (6616 to kod ASCII litery f) dało niepożądane rezultaty:
1F9111 af;
1799 in
0790001226D8 yg*8??
0A9E1E5C3ADA ti4v??
1F a
099E195E wi3t
0A97075A21DAC1 t`-p???
0A9710 t`:
199E075131D3 gi-{??
1199 on
12961350 la9z |
Tak więc drogą dedukcji doszedłem do wartości drugiego znaku klucza. 9916 ⊕ 6e16 = f716 (6e16 to kod ASCII litery n):
1F9111 an;
1799 if
0790001226D8 yo*8??
0A9E1E5C3ADA ta4v??
1F a
099E195E wa3t
0A97075A21DAC1 th-p???
0A9710 th:
199E075131D3 ga-{??
1199 of
12961350 li9z |
Wynik
Powtarzając powyższe kroki aż do wyczerpania znaków w wyrazach uzyskałem początek klucza o wartości: 7E FF 75 35 54 BD A9, a odczytane słowa układają się w cytat z piosenki Iron Maiden:
1F9111 and 1799 if 0790001226D8 you're 0A9E1E5C3ADA taking 1F a 099E195E walk 0A97075A21DAC1 through 0A9710 the 199E075131D3 garden 1199 of 12961350 life |
Cały kod można znaleźć tutaj.