Kryptologia

Prowadzący

Czas Trwania Warsztatów

25 godzin lekcyjnych (5 dni po 5 godzin lekcyjnych)

Kryptologia

Zaawansowane warsztaty informatyczno-matematyczne

Celem warsztatu będzie przedstawienie historii kryptografii (czyli gałęzi wiedzy o utajnianiu wiadomości) na przykładzie 4 historycznie ważnych algorytmów szyfrowania. Uczestnicy nie tylko stworzą w języku C++ programy szyfrujące informacje, ale także zmierzą się z wyzwaniem złamania poznanych na warsztatach szyfrów.

Do kogo kierowany jest warsztat?

Warsztat jest skierowany dla licealistów, którzy opanowali już dobrze podstawy języka C++, a chcieliby poznać jego praktyczne zastosowanie w kryptografii i kryptoanalizie. To warsztat dla osób z analitycznym umysłem, uwielbiających rozwiązywać zagadki i łamigłówki. Jest to warsztat skierowany do osób zainteresowanych studiami na kierunkach takich jak informatyka i matematyka.

Warsztat nie jest warsztatem uczącym uczestników języka C++, ale pokazującym przykładowe wykorzystanie go w konkretnych zastosowaniach. Dlatego uczestnicy warsztatu powinni mieć opanowany język do poziomu 4 (włącznie) kursu http://cpp0x.pl/kursy/Kurs-C++/1.

Przed rejestracją na warsztaty zachęcamy do rozwiązania zadania i oceny poziomu swojej wiedzy:

Zadanie

Niezbędny sprzęt i oprogramowanie

Każdy uczestnik powinien posiadać swój laptop z systemem Linux. Preferowane jest Ubuntu/Xubuntu/Kubuntu 16.04 LTS lub 18.04 LTS. System operacyjny może być zainstalowany także, jako dual-boot lub w maszynie wirtualnej. Dodatkowe pakiety potrzebne podczas warsztatów:

  • g++ lub g++-5 lub g++-6
  • libboost-all-dev
  • dowolny edytor programisty

Dlaczego warto wziąć udział w tym warsztacie?

Podczas warsztatu uczestnicy:

  • poznają fascynującą historię kryptografii i kryptoanalizy;
  • poznają praktyczne zastosowanie programowania w C++;
  • nauczą się wykorzystywania komputerów do rozwiązywania różnorodnych złożonych problemów.

Program warsztatu

Dzień pierwszy

Repetytorium z C++. Szyfr Cezara

Zaczniemy od powtórzenia niezbędnych elementów języka C++, które będziemy wykorzystywać przez cały tydzień. Jednym ze sposobów przećwiczenia i utrwalenia umiejętności programistycznych będzie napisanie programu szyfrującego depeszę prostym szyfrem przesuwającym, zwanym często szyfrem Cezara. Zwieńczeniem dnia będzie program automatycznie łamiący szyfrogram otrzymany tym algorytmem.

Dzień drugi

Monoalfabetyczny szyfr podstawieniowy

Nieco bardziej bezpiecznym szyfrem jest monoalfabetyczny szyfr podstawieniowy, czyli taki, w którym jednej literze alfabetu szyfrogramu odpowiada dokładnie jedna litera alfabetu jawnego. Zaczniemy od napisania programu szyfrującego tym algorytmem. Następnie zmierzymy się ze złamaniem krótkiego szyfrogramu bez użycia komputera. Na koniec wykorzystamy komputer do złamania dłuższego szyfrogramu metodą analizy częstotliwości występowania znaków w szyfrogramie.

Dzień trzeci

Szyfr Vigenère'a

Szyfr Vigenère’a to jeden z najsłynniejszych algorytmów szyfrujących, należy do grupy tzw. polialfabetycznych szyfrów podstawieniowych. Został opisany w połowie XVI w., jednak jego złożoność sprawiła, że nie został złamany przez kolejne trzy stulecia, dzięki czemu zyskał francuską nazwę le chiffre indéchiffrable. Tradycyjnie zaczniemy od napisania programu do szyfrowania omawianą metodą. Następnie zmierzymy się z próbą złamania szyfrogramu otrzymanego algorytmem  Vigenère’a, który – wbrew swojej francuskiej nazwie – nie jest niemożliwy do złamania.

Dzień czwarty

Szyfr RSA

RSA to niezwykle ważny i jeden z pierwszych asymetrycznych algorytmów kryptograficznych, wynaleziony przez Rona Rivesta, Adi Shamira oraz Leonarda Adlemana w 1977 r. na Massachusetts Institute of Technology, który na zawsze zmienił oblicze współczesnej kryptografii. Choć pełna implementacja przekracza ramy niniejszego warsztatu, zapoznamy się ideą szyfrowania metodą RSA oraz napiszemy program do generacji krótkich kluczy prywatnych/publicznych oraz prosty program do szyfrowania i deszyfrowania algorytmem RSA, przy okazji uzupełniając wiedzę o liczbach pierwszych i arytmetyce modulo.

Dzień piąty

Podsumowanie warsztatu. Enigma. Podstawy kryptografii kwantowej

Ostatniego dnia podsumujemy dotychczasowe osiągnięcia na warsztacie, rezerwując trochę czasu na uzupełnienie/poprawienie programów z wcześniejszych zajęć. Dodatkowo zostanie pokazana historia niemieckiej maszyny szyfrującej Enigma i polskiego nieocenionego udziału w złamaniu jej potęgi oraz idee kryptografii kwantowej – technikę szyfrowania przyszłości.

Inteligencja nie polega na tym, aby gromadzić informacje, ale na tym, aby wiedzieć, gdzie je znaleźć.

Albert Einstein