Wyniki konkursu 1 – Problem króla Bajtazara

Zakończył się nasz pierwszy konkurs programistyczny. Dziękujemy siedmiu dzielnym Irysom, którzy niczym błędni rycerze wyruszyli na pomoc królowi, wojna przeciw strasznym Bitolom zakończyła się zwycięstwem króla Baltazara.

Co trzeba było zrobić

Zanim pokażemy wam honorową tabelę zwycięzców konkursu, bardzo chcemy wam trochę opowiedzieć o tym czego dotyczył konkurs. Należało rozwiązać jeden z dwóch problemów: Confidential oraz Top Secret

Confidential

Znalezione obrazy dla zapytania szyfr cezara\Był to tak na prawdę klasyczny Szyfr cezara z tą różnicą, że szyfr cezara najczęściej kojarzony jest z przesunięciem o 3 w prawo, a w przypadku naszego problemu przesunięcie wynosiło 5 pozycji w lewo.

Jest to bardzo prosty szyfr podstawieniowy, który w miejsce każdej litery hasła, podstawia literę oddaloną o pięć w lewo. Legendy głoszą, że rzymski imperator Juliusz Cezar zanim przekazał swoje tajne wiadomości posłańcom, szyfrował je właśnie tym sposobem. Gdybyśmy mogli przenieść się z naszymi programami do tamtych czasów, z pewnością znaleźlibyśmy dobrze płatną posadę w pałacu cesarza 😉

Top Secret

Również ten problem nawiązuje do istniejącego szyfru historycznego. Mowa tutaj o Szyfrze Vigenère’a. Jest to dużo bardziej zaawansowany szyfr, bo do rozszyfrowania szyfrogramu (czyli ciągu znaków powstałym po procesie szyfrowania) nie wystarczy znajomość sposobu działania szyfru. Trzeba również znać tajny klucz. Szyfr został po raz pierwszy opisany w 1553 r.

Znalezione obrazy dla zapytania knight clipartZłamanie szyfru wydawało się wtedy nie możliwe bez znajomości klucza! Nie zapominajmy, że mówimy o XVI wieku, kiedy to mężni rycerze nadal potykali sie na miecze, a o załatwianiu się w toaletach nikt nawet nie marzył.

W miarę upływu czasu, okazało się jednak, że mając wystarczającą liczbę zaszyfrowanych wiadomości tym samym kluczem, możemy złamać szyfr korzystając z metod statystycznych. Szyfr Vigenère’a jest na tyle skomplikowanym szyfrem, że nie jesteśmy w stanie wyjaśnić sposobu jego deszyfracji na tym blogu, ale jeżeli kogoś to interesuje i zna dobrze język angielski, zachęcamy do obejrzenia tego filmu.

Jeżeli mówimy już o kryptoanalizie (sztuce łamania i odkrywania szyfrów), warto wspomnieć, że duży wpływ na poziom bezpieczeństwa szyfrogramu ma język wiadomości. Nie mówimy tutaj tylko o szyfrze Vigenère’a, ale dotyczy to również innych klasycznych algorytmów szyfrujących. Pewnie zastanawiacie się, jaki?

Zadajmy sobie pytanie: czy w każdym języku średnia liczba liczba wystąpień poszczególnych znaku alfabetu jest taka sama? Co gdyby okazało się, że analizując bardzo duże ilości tekstów w różnych językach można było określić procent wystąpień poszczególnych znaków, który wskazywałby w jakim języku napisany jest tekst?

Okazuje się, że właśnie tak jest! Zobaczcie jak prezentują się histogramy (wykresy mówiące o tym jak często występuje dana litera) dla języka polskiego, angielskiego i norweskiego:

Zauważmy, że w języku norweskim litera e ma procent występowalności na poziomie ponad 16%! Domyślamy się, że najtrudniejszym do kryptoanalizy językiem będzie taki, w którym każda litera alfabetu występuje tak samo często.

Dla danych języków tworzy się również digramy, które mówią o tym, jak często występują pary liter. Wiedząc na przykład, że para IE występuje w języku polskim najczęściej, możemy w naszym procesie kryptoanalizy wykorzystać tę wiedzę i zakładać, że po literze I najprawdopodobniej wystąpi litera E.

Teraz wiemy już mniej więcej, na czym może polegać ten magiczny proces kryptoanalizy. Najwyższy czas poznać naszych młodych Irysów-krypotoanalityków! 🙂

Uczestnicy konkursu

Imię Rozwiązane problemy Technologia wykonania
Jan Samiec Confidential C++
Kuba Czyż Confidential, Top Secret C++
Łukasz Polok Confidential, Top Secret JavaScript
Marek Polok Confidential JavaScript
Mateusz Wrzecionko Confidential, Top Secret C++
Przemek Dziadek Confidential C++
Sławek Kędzior Confidential, Top Secret JavaScript

Serdecznie dziękujemy każdemu Irysowi za nadesłane rozwiązania. Każdy uczestnik konkursu zostanie nagrodzony kubkiem z logo naszego koła informatycznego. Dobry kubek na kawę, przyda się każdemu programiście!

Mamy nadzieję, że zadanie choć trochę was wciągnęło, a pozostałych Irysów zachęcamy do udziału w kolejnych konkursach. Niech moc programowania będzie z wami! 🙂

 

Główne źródło wiedzy i informacji: wikipedia.pl

Rocksoft

Redakcja

Pod tym kontem, publikowane są wpisy informacyjne i organizacyjne.

Like
Like Love Haha Wow Sad Angry

4 Replies to “Wyniki konkursu 1 – Problem króla Bajtazara”

  1. Gratulacje ludziska 😀

  2. Wow! Dobry kubek nie jest zły 🙂

  3. Kolejny kubek zawsze się przyda

  4. Gratulacje dla wszystkich zwycięzców! Kubek z Irys idealnie się nadaje do picia kawy/herbaty. Nie skłamię jeśli powiem, że te napoje smakują w nim bardziej informatycznie :p

Dodaj komentarz