Algorytmy kryptograficzne | I2S BASiSK | semestr zimowy 2025/2026

Aktualności

13.01.2026 — Projekty na egzamin

Przepraszam za zwłokę, ale dopiero teraz udało mi się przygotować projekty na egzamin. Wszystkie informacje znajdą Państwo poniżej.

Jeśli chodzi o termin egzaminu, to zgodnie z Państwa sugestią spotkamy się 2.02.2026. Prezentacja każdego zespołu odbędzie się niezależnie od pozostałych i potrwa (łącznie z pytaniami/dyskusją) od 20 do 30 minut. Dostępne godziny:

• 9.00–14.00,
• 15.00–17.30.

Wszystko odbędzie się w sali PE1.

Proszę się jakoś sensownie umówić między sobą, który zespół przychodzi o której godzinie. Oczywiście w razie jakiejś kolizji, część osób może przyjść innego dnia, ale lepiej byłoby się uporać za jednym razem.

Wykład

• Środa, 12.15–14.00, wykład zdalny.

Prowadzący

Wykład

Adam Gregosiewicz

Ćwiczenia

• Adam Gregosiewicz (gr. 2.1)
• Maciej Ziemba (gr. 2.2)

Zasady egzaminu

Egzamin polegać będzie na wyborze jednego projektu dotyczącego szeroko pojętej kryptografii od strony algorytmicznej. Zadaniem będzie zrozumienie jakiegoś zagadnienia, jego omówienie, implementacja oraz zaprezentowanie wyników.

Wymagania

• Każdy projekt powinien być realizowany przez 2 (w uzasadnionych przypadkach 3) osoby. Wkład wszystkich osób powinien być podobny.
• Implementację należy przygotować w formie repozytorium git w GitHub Classroom. Link do zadania, przez który można utworzyć szablon repozytorium, znajduje się w naszej grupie teamsowej.
• W repozytorium należy umieścić plik README.md z krótką instrukcją uruchomienia (komendy, środowisko, wymagania). Szczegóły znajdują się w szablonie repozytorium.
• W pliku DESC.md (ewentualnie desc.pdf) należy umieścić opis przygotowanego projektu (postawienie problemu, opisanie rozwiązania i sposobu implementacji). Opis powinien być zrozumiały dla osoby, która nie jest specjalistą od rozważanego zagadnienia. Jednocześnie należy omówić szczegóły teoretyczno/matematyczne. Proszę jednak nie kopiować fragmentów książek czy artykułów, ma to być opis Państwa własnymi słowami.
• W pliku EXAMPLE.md lub example.pdf można umieścić opis przykładowego uruchomienia na konkretnych danych wraz z komentarzem.
• Implementacja powinna znaleźć się w katalogu src.

Instrukcja GitHub Classroom

1. Trzeba wejść na stronę z linku do zadania (znajduje się w naszym zespole teamsowym) i ewentualnie zalogować się na swoje konto GitHub. Następnie należy wybrać Create team (jeśli jest się pierwszą osobą w zespole) albo Join an existing team (jeśli zespół już istnieje i chcemy do niego dołączyć).
2. Po utworzeniu zespołu GitHub automatycznie stworzy prywatne repozytorium (tego zespołu), w którym należy przygotować projekt.

Ważne zasady

• Korzystajcie z narzędzi AI (jak ChatGPT, Gemini, Claude, …) z dużą ostrożnością. Mogą one być pomocne, ale kod musi być Państwa autorstwa. To Państwo mają rozumieć i umieć wyjaśnić każdy element projektu.
• Każdy członek zespołu musi być w stanie wytłumaczyć, jak działa cały projekt – zarówno od strony matematycznej, jak i implementacyjnej. Podział pracy jest naturalny, ale odpowiedzialność za całość jest wspólna.
• Upewnijcie się, że rozumiecie każdą linijkę kodu w projekcie. Podczas prezentacji możecie być poproszeni o wytłumaczenie konkretnego fragmentu programu.
• Starajcie się implementować algorytmy samodzielnie, ,,od zera’’. Unikajcie gotowych bibliotek realizujących algorytm (lub jego istotny fragment) jako ,,czarną skrzynkę’'.
• Projekt ma być nie tylko działającym programem, ale także dowodem zrozumienia idei, algorytmu i jego ograniczeń.

Terminy

• Tematy nie powinny się powtarzać – każdy zespół tworzy inny projekt. O wyborze decyduje kolejność zgłoszeń. W celu wybrania projektu proszę zaakceptować zadanie (przez odpowiedni link) i dodać do pliku README.md dane zespołu oraz tytuł projektu. Będę się starał na bieżąco aktualizować listę dostępnych projektów na stronie.
• Repozytorium powinno być gotowe do 1.02.2026 do północy. Oczywiście zachęcam do prawidłowego korzystania z systemu kontroli wersji. Nie dodawajcie wszystkiego w jednym commicie. Niech historia repozytorium pokazuje zmiany w projekcie.
• Podczas egzaminu (2.02.2026) każdy zespół zaprezentuje swój projekt. Ma to być krótkie i przystępne omówienie problemu oraz jego rozwiązania. Następnie należy wskazać istotne elementy implementacji oraz działanie programu w praktyce. Całość nie powinna zająć więcej niż ok. 20 minut.
• Rada: proszę nie przygotowywać jakiejś dużej prezentacji z wieloma slajdami i morzem tekstu. Wystarczy prosty ,,obrazek’’, na którym wskażecie główne idee. Najważniejsze jest to, co powiecie, a nie to, co będzie wyświetlone.

Ocena

Przy wystawianiu ocen będę brał pod uwagę jakość:

• implementacji – 40%.
• prezentacji – 60%.

Podkreślam, że w prezentacji nie chodzi o przygotowanie pliku ze slajdami. Tego może w ogóle nie być. W razie czego jest tablica. Chodzi o Państwa zaprezentowanie tematu i omówienie rozwiązania.

Proponowane projekty

We wszystkich projektach w części Literatura pozycja [1] to książka D. Stinson, M. Paterson, Kryptografia w teorii i praktyce, Wydawnictwo Naukowe PWN, 2021.

1. Kryptoanaliza różnicowa

Zaprezentuj ideę ataku różnicowego i przeprowadź taki atak na prosty szyfr blokowy. Możesz użyć DES-a z niepełną liczbą rund albo stworzyć własny SPN, na tyle mały, aby atak się powiódł.

Literatura:

• [1] rozdz. 4.4.
• H. M. Heys, A Tutorial on Linear and Differential Cryptanalysis.
• E. Biham, A. Shamir, Differential Cryptanalysis of DES-like Cryptosystems.

2. Kryptoanaliza liniowa

Projekt analogiczny do 1, ale dotyczący ataku liniowego.

Literatura:

• [1] rozdz. 4.3.
• H. M. Heys, A Tutorial on Linear and Differential Cryptanalysis.
• M. Matsui, Linear Cryptanalysis Method for DES Cipher.

3. Algorytmy faktoryzacyjne Pollarda: $p-1$ i $\rho$

Przedstaw algorytmy faktoryzacyjne Pollarda ($p-1$ i $\rho$) od strony teoretycznej i praktycznej. Zaimplementuj oba rozwiązania i porównaj ich skuteczność dla różnych danych wejściowych. Wykorzystaj stworzone metody do ataku na kryptosystem RSA.

Literatura:

• [1] rozdz. 6.6.1–6.6.2.
• J. M. Pollard, A Monte Carlo Method for Factorization.
• The Pollard p-1 factoring algorithm.

4. Losowe kwadraty Dixona

Przedstaw i zaimplementuj metodę faktoryzacji opartą na losowych kwadratach Dixona. Omów złożoność obliczeniową algorytmu. Wykorzystaj tę metodę do ataku na kryptosystem RSA.

Literatura:

• [1] rozdz. 6.6.3.
• J. D. Dixon, Asymptotically Fast Factorization of Integers.

5. Sito kwadratowe

Omów i zaimplementuj metodę sita kwadratowego w problemie faktoryzacji. Omów złożoność obliczeniową algorytmu. Wykorzystaj tę metodę do ataku na kryptosystem RSA.

Literatura:

• [1] rozdz. 6.6.4 (wstępne informacje).
• C. Pomerance, The Quadratic Sieve Factoring Algorithm.
• E. Landquist, The Quadratic Sieve Factoring Algorithm.
• Quadratic Sieve Factoring.

6. Algorytm $\rho$ Pollarda dla problemu logarytmu dyskretnego

Zaimplementuj i omów atak $\rho$ Pollarda na problem logarytmu dyskretnego w $\mathbb{Z}_p$. Przeanalizuj liczbę potrzebnych iteracji, odsetek błędnych kolizji i wpływ doboru funkcji podziału zbioru na skuteczność ataku. Wykorzystaj tę metodę do ataku na kryptosystem Elgamal.

Literatura:

• [1] rozdz. 7.2.2.
• J. M. Pollard, Monte Carlo Methods for Index Computation (mod p).

7. Atak Pohliga–Hellmana

Przeprowadź atak Pohliga–Hellmana na problem logarytmu dyskretnego w $\mathbb{Z}_p$. Omów szczegóły teoretyczne algorytmu oraz zweryfikuj, kiedy taki atak ma szanse powodzenia. Wykorzystaj tę metodę do ataku na kryptosystem Elgamal.

Literatura:

• [1] rozdz. 7.2.3.
• C. Vinzan, Algorithms for Computing Discrete Logarithms.
• D. Goldfeld, Notes on the Pohlig–Hellman Attack.
• S. C. Pohlig, M. E. Hellman, An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance.

8. Metoda rachunku indeksowego

Zaprogramuj atak oparty o metodę rachunku indeksowego dla problemu logarytmu dyskretnego w $\mathbb{Z}_p$. Omów szczegóły teoretyczne algorytmu oraz zweryfikuj, kiedy taki atak ma szanse powodzenia. Wykorzystaj tę metodę do ataku na kryptosystem Elgamal.

Literatura:

• [1] rozdz. 7.2.4.
• C. Vinzan, Algorithms for Computing Discrete Logarithms.
• M. Bläser, Ch. Saha, The Index Calculus method.
• A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance.

---

9. Kryptosystem Rabina

Zaprogramuj kryptosystem Rabina, który pozwala szyfrować wiadomości w języku naturalnym. Zadbaj o odpowiedni padding i bezpieczeństwo semantyczne.

Literatura:

• [1] rozdz. 6.8 i 6.9.
• M. O. Rabin, Digitalized Signatures and Public-Key Functions as Intractable as Factorization.
• S. Galbraith, The RSA and Rabin Cryptosystems.
• J. Rothe, Rabin’s Public-Key Cryptosystem.

10. Atak Håstada dla małego wykładnika publicznego RSA

Zademonstruj atak Håstada na kryptosystem RSA, w którym użyto małego wykładnika publicznego. Omów szczegóły teoretyczne ataku. Zbadaj granice skuteczności tego podejścia.

Literatura:

• J. Håstad, On Using RSA with Low Exponent in a Public Key Network.
• D. Boneh, Twenty Years of Attacks on the RSA Cryptosystem.

11. Atak Wienera dla małego wykładnika prywatnego RSA

Zademonstruj atak Wienera na kryptosystem RSA, w którym użyto małego wykładnika prywatnego. Omów szczegóły teoretyczne ataku. Zbadaj granice skuteczności tego podejścia.

Literatura:

• [1] rozdz. 6.7.3.
• M. J. Wiener, Cryptanalysis of Short RSA Secret Exponents.
• D. Boneh, Twenty Years of Attacks on the RSA Cryptosystem.

13. Kryptosystem plecakowy Merkle’a–Hellmana

Omów i zaimplementuj kryptosystem plecakowy Merkle’a–Hellmana, który umożliwia szyfrowanie i deszyfrowanie wiadomości w języku naturalnym. Następnie przeprowadź atak Shamira na ten system w oparciu o twierdzenie LLL.

Literatura:

• S. Galbraith, Cryptosystems Based on Lattices (19.13).
• A. Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem.
• A. M. Odlyzko, The Rise and Fall of Knapsack Cryptosystems.
• A. K. Lenstra, H. W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients.

14. Protokół Diffiego–Hellmana na krzywych eliptycznych

Omów i zaprezentuj atak na protokół Diffiego–Hellmana dla krzywych eliptycznych, w którym strona ofiary nie waliduje punktów (należenie do krzywej, duży rząd). Pokaż, jak w praktyce można takiego ataku uniknąć.

• T. Jager, J. Schwenk, J. Somorovsky, Practical Invalid Curve Attacks on TLS-ECDH (slides, PDF).
• S. Kunzweiler, Lecture 4: Elliptic Curve Cryptography (handout, PDF).
• M. Kleppmann, Implementing Curve25519/X25519: A Tutorial on Elliptic Curve Cryptography.

15. Metody Pollarda dla problemu logarytmu dyskretnego na krzywych eliptycznych

Zaimplementuj ataki $\rho$ i kangaroo Pollarda dla problemu logarytmu dyskretnego na krzywych eliptycznych. Uzasadnij ich teoretyczną skuteczność i porównaj w praktyce oba algorytmy.

Literatura:

• S. Galbraith, Factoring and Discrete Logarithms using Pseudorandom Walks.
• Generic Algorithms for the Discrete Logarithm Problem.
• E. Teske, The Pollard kangaroo method computes discrete logarithms in any group.

Konsultacje

Adam Gregosiewicz

• Środa, 10.15–11.00, Pentagon, pok. 3 (PE 3).
• Czwartek, 14.15-15.00, Pentagon, pok. 3 (PE 3).

Terminy konsultacji pozostałych prowadzących można znaleźć tutaj.

Materiały

Książki

1. Douglas R. Stinson, Kryptografia w teorii i praktyce, Wydawnictwo Naukowe PWN, 2021.
2. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography.
3. Bruce Schneier, Kryptografia dla praktyków, WNT, 2002.
4. Dan Boneh, Victor Shoup, A Graduate Course in Applied Cryptography.
5. Steven Galbraith, Mathematics of Public Key Cryptography.
6. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, An Introduction to Mathematical Cryptography.

Polecam również książki o historii kryptologii.

1. David Kahn, Łamacze kodów. Historia kryptologii, Zysk i S-ka, 2019.
2. Simon Singh, Księga szyfrów, Albatros, 2001.
3. Steven Levy, Rewolucja w kryptografii, WNT 2002.

Strony internetowe

1. Dan Boneh.
2. Dobre notatki dotyczące kryptografii, teorii liczb i krzywych eliptycznych.

Kursy wideo

1. Christof Paar, Introduction to Cryptography.
2. Dan Boneh, Cryptography I.

Wykłady

Tydzień 1 — 1.10.2025

Wykład odwołany z powodu godzin rektorskich.

Tydzień 2 — 8.10.2025

Informacje organizacyjne. Wprowadzenie do kryptografii i kryptoanalizy. Definicja kryptosystemu. Omówienie podstawowych rodzajów szyfrów o charakterze historycznym: szyfr Cezara, podstawieniowy, afiniczny, Hille’a, Vigenère’a.

Materiały:

• Notatki z wykładu.

Literatura:

• [1] rozdz. 2.1.

Tydzień 3 — 15.10.2025

Modele ataków na kryptosystemy. Kryptoanaliza szyfrów z poprzedniego wykładu. Podstawowe narzędzie kryptoanalityczne: wyczerpujące wyszukiwanie klucza, analiza częstości, test Kasiskiego, indeks koincydencji.

Materiały:

• Notatki z wykładu.

Literatura:

• [1] rozdz. 2.2.

Tydzień 4 — 22.10.2025

Doskonała tajność kryptosystemu. Teoria Shannona. Szyfr jednorazowy (one-time pad) i jego własności.

Materiały:

• Notatki z wykładu.
• Communication Theory of Secrecy Systems – praca Claude’a Shannona, od której zaczęła się współczesna kryptografia. Pierwotnie ukazała się ona jako tajny raport A Mathematical Theory of Cryptography dla Bell Labs.

Literatura:

• [1] rozdz. 3.

Tydzień 5 — 29.10.2025

Szyfry blokowe. Sieci podstawieniowo-permutacyjne (SPN). Data Encryption Standard (DES).

Materiały:

• Notatki z wykładu.
• FIPS 46-3, Data Encryption Standard (DES) (pdf) – oficjalna specyfikacja DES.

Literatura:

• [1] rozdz. 4 (w szczególności 4.2 i 4.5).

Tydzień 6 — 5.11.2025

Szczegóły Data Encryption Standard (DES). Kryptoanaliza DES, 2DES i 3DES. Atak Meet in the middle na 2DES.

Materiały:

• Notatki z wykładu.
• FIPS 46-3, Data Encryption Standard (DES) (pdf) – oficjalna specyfikacja DES.

Literatura:

• [1] rozdz. 4 (w szczególności 4.2 i 4.5).

Tydzień 7 — 12.11.2025

Ataki side-channel na DES. Advanced Encryption Standard (AES). Historia ustanowienia standardu. Ogólny opis kryptosystemu AES.

Materiały:

• Notatki z wykładu.
• FIPS 197, Advanced Encryption Standard (AES) (pdf) – oficjalna specyfikacja AES.

Literatura:

• [1] rozdz. 4 (w szczególności 4.6).

Tydzień 8 — 19.11.2025

Targi ENERGETICS.

Tydzień 9 — 26.11.2025

Szczegóły AES. Grupy, ciała skończone. Definicja S-boxa w AES.

Materiały:

• Notatki z wykładu.
• FIPS 197, Advanced Encryption Standard (AES) (pdf) – oficjalna specyfikacja AES.

Literatura:

• [1] rozdz. 4 (w szczególności 4.6).

Tydzień 10 — 3.12.2025

Uzupełnienie szczegółów systemu AES. Omówienie funkcji MixColumn i KeyExpansion. Tryby pracy szyfrów blokowych.

Materiały:

• Notatki z wykładu.
• FIPS 197, Advanced Encryption Standard (AES) (pdf) – oficjalna specyfikacja AES.

Literatura:

• [1] rozdz. 4 (w szczególności 4.6).

Tydzień 11 — 10.12.2025

Tryby pracy szyfrów blokowych (ECB, CBC, OFB, CFB, CTR). Dopełnianie (padding) wiadomości (PKCS#7). Wprowadzenie do kryptografii klucza publicznego. Kryptosystem RSA.

Materiały:

• Notatki z wykładu.
• J.H. Ellis, Communications – Electronics Security Group, Government Communications Headquarters, Research Report No. 3006, The Possibility of Secure Non-Secret Digital Encryption (1970).
• C. Cocks, Note on Non-Secret Encryption (1973).

Literatura:

• [1] rozdz. 6.

Tydzień 12 — 17.12.2025

Kryptosystem RSA. Metody generowania dużych liczb pierwszych. Test Fermata. Test Millera–Rabina. Problem logarytmu dyskretnego. Protokół Diffiego–Hellmana.

Materiały:

• Notatki z wykładu.
• G. L. Miller, Riemann’s Hypothesis and Tests for Primality.
• M. O. Rabin, Probabilistic Algorithm for Testing Primality.
• C. Pomerance, Recent Developments in Primality Testing.
• R. Crandall, C. Pomerance, Prime Numbers: A Computational Perspective.
• V. Shoup, A Computational Introduction to Number Theory and Algebra.
• W. Diffie, M. Hellman, New Directions in Cryptography.

Literatura:

• [1] rozdz. 6.

Tydzień 13 — 7.01.2026

Kryptosystem Elgamala. Atak Shanksa (baby step–giant step) na problem logarytmu dyskretnego. Wprowadzenie do krzywych eliptycznych.

Materiały:

• Notatki z wykładu.
• T. Elgamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.

Literatura:

• [1] rozdz. 6.

Tydzień 14 — 14.01.2026

Arytmetyka na krzywej eliptycznej. Interpretacja geometryczna i wzory algebraiczne. Wprowadzenie do kryptografii opartej o krzywe eliptyczne. Protokół Diffiego–Hellmana. Porównanie bezpieczeństwa.

Materiały:

• Notatki z wykładu.

Literatura:

• [1] rozdz. 7.5.

Laboratoria

Tydzień 1 — 2.10.2025

Zadania

Tydzień 2 — 9.10.2025

Godziny dziekańskie.

Tydzień 3 — 16.10.2025

Zadania

Tydzień 4 — 23.10.2025

Zadania

Tydzień 5 — 30.10.2025

Zadania

Tydzień 6 — 6.11.2025

Zadania

Tydzień 7 — 13.11.2025

Zadania

Tydzień 8 — 20.11.2025

Targi ENERGETICS.

Tydzień 9 — 27.11.2025

Zadania

Tydzień 10 — 4.12.2025

Zadania

Tydzień 11 — 11.12.2025

Zadania

Tydzień 12 — 18.12.2025

Zadania

Tydzień 13 — 8.01.2026

Zadania

Tydzień 14 — 15.01.2026

Zadania

Tydzień 15 — 22.01.2026

Zadania