Kryptografia II stopień

Jak pracować z listami

Zaczynamy od nazwania informacji dostępnej przeciwnikowi. Dopiero potem zapisujemy jego algorytm i sprawdzamy, czy osiąga cel. Zadania oznaczone Pogłębienie rozwijają rachunek w kierunku pełniejszych argumentów bezpieczeństwa.

Bank zadań do wyboru. Prowadzący ćwiczenia ustala, które zadania wykonuje grupa, w jakiej liczbie, zakresie i terminie. Podaje zasady zaliczenia zgodne z kartą przedmiotu. Cały bank nie jest listą obowiązków do wykonania w jednym semestrze. Zadania z C0a przygotowują do pierwszego bloku algebraicznego laboratoriów. Pozostałe propozycje można dobierać do aktualnego tematu wykładu.

W rozwiązaniu podaj najpierw cel, interfejsy algorytmów i model, potem rachunek, a na końcu wniosek z jego ograniczeniami. Wypisz argumenty i wyniki każdej procedury. Osobno sprawdź poprawność uczciwych wywołań i własność bezpieczeństwa. Atak powinien być algorytmem wykorzystującym wyłącznie dostępne dane. Dowód powinien wskazywać, jak redukcja odpowiada na każde dozwolone zapytanie. Przykład liczbowy sprawdza obliczenie, lecz nie zastępuje argumentu ogólnego.

Na początek przeczytaj podstawy zapisu, schemat jako krotkę algorytmów, a następnie model przeciwnika i wyrocznie. Notacja grupowa jest potrzebna w C0a oraz od C5. C2.5 i C4.6 korzystają z rachunku w ciałach z C0a. Przy każdej liście wskazujemy osobne przygotowanie.

Losowanie a przypisanie. Zapis $x\overset{\$}{\leftarrow}S$ oznacza jednostajne losowanie ze skończonego zbioru $S$. Dolar przy strzałce odróżnia je od przypisania $y\leftarrow f(x)$. Ograniczenia zbioru, zależności i losowanie bez zwracania podajemy osobno.

C0a. Algebra do implementacji

Przygotowanie: rachunek modularny i odwrotność, rozszerzenia ciał, prawo grupowe krzywej. Dla wariantu binarnego potrzebne jest osobne prawo dodawania. Najpierw wykonaj mały rachunek ręcznie. Dopiero potem porównaj go z własnym kodem w L0a.

1. Ciało nie jest pierścieniem modulo potęgi. Pokaż, że w $\mathbb Z_{25}$ istnieją niezerowe elementy, których iloczyn jest zerem. Następnie zbuduj $\mathbb F_{25}=\mathbb F_5[t]/(t^2+2)$. Uzasadnij nierozkładalność $t^2+2$ przez sprawdzenie, że nie ma pierwiastka w $\mathbb F_5$. Niech $\alpha$ oznacza klasę $t$. Oblicz $\alpha^2$, $\alpha^{-1}$ oraz $(\alpha+1)\cdot(\alpha-1)$. Wyjaśnij, dlaczego każdy niezerowy element tego ilorazu ma odwrotność. Wskaż, co przestaje działać, gdy zamiast nierozkładalnego wielomianu użyjesz $t^2-1$.
2. Bity jako współczynniki. W $\mathbb F_{16}=\mathbb F_2[t]/(t^4+t+1)$ przedstaw wszystkie elementy jako czterobitowe wektory. Wyjaśnij, dlaczego dodawanie jest XOR-em, i ręcznie zredukuj $t^4$. W $\mathbb F_{256}$ z wielomianem $t^8+t^4+t^3+t+1$ oblicz iloczyn bajtów 57 i 83. Zapis jest szesnastkowy, a bit o numerze $i$ jest współczynnikiem przy $t^i$. Wskaż różnicę między tą operacją a zwykłym mnożeniem modulo 256. To przygotowanie do AES, nie ogólna reguła kodowania wszystkich ciał binarnych.

   XOR

   exclusive OR. Alternatywa wykluczająca. Wynik to 1 dokładnie wtedy, gdy dwa bity są różne.

   AES

   Advanced Encryption Standard. Standard szyfrowania blokowego. Liczby 128, 192 i 256 oznaczają długości klucza w bitach.

3. Punkt, skalar i przypadki wyjątkowe. Dla $E:y^2=x^3+2\cdot x+2$ nad $\mathbb F_{17}$ sprawdź nieosobliwość. Zweryfikuj $P=(5,1)$ i oblicz $2\cdot P$ ze wzoru na styczną. Wylicz punkty krzywej wraz z $\mathcal O$, a z ich liczby uzasadnij rząd $P$. Wskaż, dlaczego współrzędne liczymy modulo 17, a skalary tej podgrupy modulo 19. Osobno opisz $P+(-P)$ oraz podwajanie punktu o $y=0$, jeżeli taki punkt wystąpi na innej krzywej. Nie dziel przez zerowy mianownik.
4. Krzywa w charakterystyce 2. Dla $y^2+x\cdot y=x^3+a\cdot x^2+b$ nad $\mathbb F_{2^k}$ wykaż, że wraz z $(x,y)$ na krzywej leży $(x,x+y)$. Jest to punkt przeciwny. Przy $a=b=1$ sprawdź $(0,1)$ i jego podwojenie. Wyjaśnij, dlaczego nie można po prostu użyć wzoru z mianownikiem $2\cdot y$ z krzywej o charakterystyce większej niż 3. Wskazówka: odrębne prawo grupowe opisuje SEC 1, §2.2.2.
5. Jednoznaczne kodowanie. Podaj bajty dla krotek (01, 0203) i (0102, 03), gdy kodowanie tylko skleja pola. Zaproponuj format, który je rozróżnia i określa długości, kolejność bajtów oraz dziedzinę. Wyjaśnij, dlaczego ten sam wektor współczynników przy różnych wielomianach redukcyjnych może podlegać innym regułom mnożenia. Rozdziel trzy kontrole punktu publicznego: poprawne kodowanie, przynależność do krzywej i przynależność do wymaganej podgrupy. Które z nich sprawdza samo równanie krzywej?

Kontrola rachunku: w zadaniu 1 otrzymujesz $\alpha^2=3$, $\alpha^{-1}=2\cdot\alpha$ i wynik ostatniego iloczynu równy 2. W zadaniu 2 iloczyn bajtów wynosi c1. W zadaniu 3 punkt $2\cdot P=(6,3)$, a krzywa ma 19 punktów wraz z $\mathcal O$. Kontrole pomagają wykryć pomyłkę, ale nie zastępują uzasadnienia.

Pochodzenie zadań: blok algebraiczny i powiązane zadania C2.5, C4.6, C6.6, C7.6 oraz C15.6 rozwijają tematykę listy 2 i listy 3 Marcina Słowika. Te ćwiczenia rachunkowe to przygotowanie do implementacji, nie obowiązek realizacji wszystkich wariantów.

C0. Model, eksperyment i zapytania

Przygotowanie: interfejsy, poprawność i bezpieczeństwo, następnie przeciwnik i wyrocznie.

1. Usługa podpisująca. Przeciwnik może zlecać podpisy pod dowolnymi dokumentami, lecz nie zna klucza. Opisz jego wejście, dozwolone pytania i cel. Dlaczego oddanie już otrzymanego podpisu nie jest fałszerstwem w rozpatrywanym eksperymencie?
2. Adaptacyjny wybór. Zapisz dwa pytania, z których drugie zależy od pierwszej odpowiedzi. Porównaj taki dostęp z otrzymaniem dwóch podpisów pod dokumentami wybranymi wcześniej przez kogoś innego.
3. Pamięć wyroczni. Dla kolejnych wejść kot, pies, kot, kot uzupełnij tabelę wyroczni losowej do $\mathbb Z_{101}$. Które odpowiedzi muszą być równe? Które mogą być równe? Policz wszystkie pytania i różne wejścia. Ostatni tekst zawiera spację.
4. Nowe uprawnienie. Rozszerz usługę o odczyt losowości pojedynczego podpisu. Wskaż, który element poprzedniego modelu się zmienił. Czy dowód w poprzednim modelu automatycznie obejmuje rozszerzenie?
5. Zdarzenie sukcesu. Porównaj odzyskanie całego sekretu, utworzenie jednego nowego podpisu i rozróżnienie dwóch szyfrowanych wiadomości. Dla każdego zapisz, jakie wyjście przeciwnika eksperyment sprawdza.
6. Złożenie algorytmów. Zapisz krotkę Setup, KeyGen, Sign, Verify oraz pełne wywołania dla jednej wiadomości. Wskaż, które argumenty Verify pochodzą z KeyGen, które z Sign, a które trzeba dostarczyć osobno. Czy uruchomienie Verify wymaga znajomości klucza tajnego? Czy ten brak klucza jest dowodem niepodrabialności? Zapisz osobno warunek poprawności i warunek nowego fałszerstwa.
7. Poprawny, lecz niebezpieczny wariant. Pozostaw Setup i KeyGen, ale zastąp Sign algorytmem zwracającym zawsze bit 0. Niech Verify akceptuje dokładnie ten bit dla każdej dozwolonej wiadomości. Sprawdź poprawność. Następnie podaj przeciwnika, który bez klucza i bez zapytań wygrywa z prawdopodobieństwem 1. Osobno oceń szyfrowanie, w którym Enc zwraca niezmienioną wiadomość, a Dec przepisuje ją z wejścia. Dlaczego w obu przypadkach zgodne wejścia i wyjścia nie wystarczają do bezpieczeństwa?

Kontrola: w zadaniu 3 są cztery pytania i trzy różne wejścia. Wyniki pierwszego i trzeciego pytania muszą być identyczne. Spacja zmienia wejście. Nie wymuszamy różnych odpowiedzi na różne wejścia.

Do zadań 6–7: prawdziwy podpis otrzymany od usługi oraz podpis pod własnym, samodzielnie wygenerowanym kluczem nie są fałszerstwami pod atakowanym kluczem dla nowej wiadomości. Przeciwnik może jednak użyć dowolnego sposobu tworzenia wyniku. Nie musi wywoływać Sign ani odzyskać sekretu.

C1. Tajność doskonała i sam szyfrogram

Przygotowanie: W1: eksperyment poufności, następnie W3: tajność doskonała i OTP.

OTP

one-time pad. Szyfr z jednorazowym, losowym kluczem długości wiadomości.

1. Definicja w małym przykładzie. Niech $M\in\{0,1\}$, $\Pr[M=1]=3/4$ i $K$ będzie niezależnym, jednostajnym bitem. Dla $C=M\oplus K$ oblicz tabelę $\Pr[M=m,C=c]$ oraz $\Pr[M=1\mid C=c]$. Wyjaśnij, dlaczego szyfr nie musi wyrównywać prawdopodobieństw wiadomości.
2. Niejednostajny klucz. Powtórz obliczenie dla $\Pr[K=0]=3/4$. Wskaż szyfrogram zmieniający przekonanie odbiorcy o wiadomości. Czy poprawność deszyfrowania uległa zmianie?
3. Dwa użycia OTP. Dla dowolnych ciągów tej samej długości wyprowadź $C_1\oplus C_2=M_1\oplus M_2$. Zbuduj rozróżniacz między parami $(0^\ell,0^\ell)$ i $(0^\ell,1^\ell)$. Osobno podaj przypadek odzyskania drugiej wiadomości przy znanej pierwszej.
4. Pogłębienie: koszt tajności doskonałej. Załóż tajność doskonałą, poprawne deterministyczne deszyfrowanie, skończone przestrzenie kluczy i wiadomości oraz dodatnie prawdopodobieństwo każdej wiadomości. Klucz losujemy niezależnie od wiadomości. Uzasadnij $|\mathcal K|\ge|\mathcal M|$. Zacznij od jednego szyfrogramu o dodatnim prawdopodobieństwie. Wykorzystaj tajność doskonałą, aby wykazać, że każda wiadomość pozostaje dla niego możliwa. Dlaczego deterministyczne deszyfrowanie wymaga wtedy innego klucza dla każdego możliwego tekstu? Pokaż też, że bez założenia tajności sama poprawność nie daje tej nierówności.

C2. Szyfry blokowe i tryby pracy

Przygotowanie: W1: eksperyment poufności, W2: definicja PRF i W4: AES oraz tryby pracy.

PRF

pseudorandom function. Funkcja pseudolosowa.

Najpierw jedna runda AES. Ułóż bajty 00 01 … 0f w macierzy stanu, kolumnami. Wykonaj ShiftRows i zapisz wynik w tej samej kolejności bajtów. Uzasadnij, dlaczego samo przestawienie nie zmienia liczby różnych bitów między dwoma stanami. Następnie dla dowolnych $S,S',K$ sprawdź $(S\oplus K)\oplus(S'\oplus K)=S\oplus S'$. Który krok AES jest nieliniowy? Dlaczego pomiar dyfuzji nie jest jeszcze eksperymentem odzyskania klucza?

1. ECB. Mając wyrocznię szyfrującą pod stałym kluczem, skonstruuj jednozapytaniowy atak IND-CPA. Wybierz dwie wiadomości z dwóch bloków, z których tylko jedna ma powtórzony blok. Wyjaśnij, dlaczego nie musisz odwracać AES.

   ECB

   Electronic Codebook. Tryb niezależnego szyfrowania bloków, tradycyjnie nazywany elektroniczną książką kodową.

   IND-CPA

   indistinguishability under chosen-plaintext attack. Nierozróżnialność przy ataku z wybranym tekstem jawnym.

2. Modyfikacja CBC. Dla $m_i=D_k(c_i)\oplus c_{i-1}$ wskaż, jak zmiana $c_{i-1}$ o maskę $\Delta$ wpływa na $m_i$. Co dzieje się z sąsiednim blokiem? Rozpatrz osobno zmianę IV i zmianę wewnątrz szyfrogramu. Nie zakładaj, że odbiorca akceptuje niepoprawny znacznik integralności.

   CBC

   Cipher Block Chaining. Tryb wiązania bloków szyfrogramu.

   IV

   Initialization Vector. Wektor inicjalizujący. Wymagania wobec niego zależą od trybu szyfrowania.

3. CTR. Dwa strumienie zaczęły się od tego samego licznika pod tym samym kluczem. Wykaż związek z C1. Zaproponuj format nonce i licznika z kontrolą przepełnienia oraz zasady restartu urządzenia.

   CTR

   Counter mode. Tryb licznikowy.

4. Pogłębienie: zamiana PRP na PRF. Wyjaśnij, jak rozróżnić losową funkcję od losowej permutacji przez kolizję odpowiedzi. Dla $t$ różnych wejść i bloków $n$-bitowych wyprowadź górną granicę $t(t-1)/2^{n+1}$. Nie przedstawiaj jej jako ataku odzyskującego klucz.

   PRP

   pseudorandom permutation. Permutacja pseudolosowa.

Wynik pracy: po jednym transkrypcie ataku i jednej wskazanej własności, której brakuje. Nie używaj ogólnego zdania „szyfr jest zły”, gdy problem dotyczy sposobu użycia prymitywu.

5. Algebra MixColumns. Po C0a.2 zapisz macierz MixColumns z FIPS 197, §5.1.3. Oblicz obraz kolumny d4 bf 5d 30 i porównaj z 04 66 81 e5. Wszystkie liczby w tym zapisie są szesnastkowe. Wyjaśnij mnożenie przez 02 i 03 jako działania na wielomianach nad $\mathbb F_2$. Uzasadnij, dlaczego operacja jest liniowa nad $\mathbb F_{256}$ oraz odwracalna. Czy sama liniowość i odwracalność oznaczają, że otrzymaliśmy bezpieczny szyfr? Powiąż rachunek z L1.7.

   FIPS

   Federal Information Processing Standards. Amerykańskie federalne standardy przetwarzania informacji.

C3. Strumień, generator i redukcja

Przygotowanie: W2: definicje PRG i PRF, następnie W3: OTP i pierwszy dowód z PRG. Do zadań 3 i 4 przeczytaj W3a: metodę gier, sprzężenie i sumę strat. Jest tam pełny dowód po polsku, animacja obu przebiegów i dokładny rachunek kolizji.

PRG

pseudorandom generator. Generator pseudolosowy.

1. Generator liniowy. Dla $x_{i+1}=\alpha x_i+\beta\bmod p$ załóż, że parametry są publiczne, a pełny stan $x_i$ jest wyjściem. Pokaż przewidywanie kolejnych wyjść. Wyjaśnij, dlaczego długi okres i dobry histogram nie stanowią bezpieczeństwa kryptograficznego.
2. Redukcja PRG. Zapisz kompletny algorytm $\mathcal B$ dowodzący bezpieczeństwa jednorazowego $m\oplus\mathsf{PRG}(k)$. Wskaż, skąd bierze wiadomości, co otrzymuje jako wyzwanie, co zwraca i ile razy wywołuje $\mathcal A$.
3. Powtórzony argument PRF. W szyfrowaniu $(r,m\oplus F_k(r))$ odróżnij dwa eksperymenty: niezależne losowanie $r$ oraz licznik bez powtórzeń. Dla każdego podaj zdarzenie złe i element stanu, który trzeba utrzymać.
4. Pogłębienie: hybrydy. Masz $t$ przejść o różnicach $\delta_i$. Wyprowadź sumę ograniczającą różnicę końców. Wyjaśnij, kiedy pojawia się strata $t$, a kiedy jedno zastąpienie całej wyroczni PRF pozwala jej uniknąć.

C4. Hasze, MAC i integralność

MAC

Message Authentication Code. Kod uwierzytelnienia wiadomości, sprawdzany przy użyciu klucza.

Przygotowanie: W2: definicja PRF, W4: AEAD i dane dodatkowe, W5: hasze i MAC i dodatek A.

AEAD

Authenticated Encryption with Associated Data. Uwierzytelnione szyfrowanie z danymi dodatkowymi.

Do zadania 2: stan hasza i dopełnienie. Konstrukcja Merkle’a–Damgårda przetwarza wiadomość blokami. Funkcja kompresująca łączy poprzedni stan z kolejnym blokiem. Dopełnienie kończy wiadomość i koduje jej długość. W rozpatrywanym wariancie skrót ujawnia cały stan końcowy. Znając ten stan oraz długość dotychczasowego wejścia, można kontynuować obliczenia dla dopisanych bloków. Przy $\mathcal D(k\|m)$ przeciwnik musi znać lub zgadnąć długość klucza, aby ustalić dopełnienie po $k\|m$. Przedłużana wiadomość zawiera to dopełnienie przed nowymi danymi. Nie zakładamy, że każdy hasz ma tę własność. Przykład przetwarzania bloków i dopełnienia SHA-256 opisuje RFC 6234, rozdziały 4 i 6.2.

SHA-256

Secure Hash Algorithm. Algorytm bezpiecznego haszowania. W nazwie SHA-256 liczba oznacza 256-bitowy wynik.

RFC

Request for Comments. Dokument z serii opisującej m.in. protokoły internetowe. Nie każdy RFC jest standardem.

Do zadania 4: silniejsza gra poufności. W IND-CPA przeciwnik może uzyskiwać szyfrowania wybranych wiadomości. Wybiera dwie wiadomości tej samej długości i zgaduje, którą zaszyfrowano w wyzwaniu. W IND-CCA2 dodatkowo pyta o deszyfrowanie przed wyzwaniem i po nim. Nie wolno mu zlecić deszyfrowania dokładnego wyzwania. Odpowiedź wyroczni to wiadomość albo odrzucenie. W zadaniu 4 symulujemy właśnie ten dodatkowy interfejs. Przykład ataku pokazuje W10a: CPA i CCA.

IND-CCA2

indistinguishability under adaptive chosen-ciphertext attack. Nierozróżnialność przy adaptacyjnym ataku z wybranym szyfrogramem.

CPA

chosen-plaintext attack. Atak z wybranym tekstem jawnym.

CCA

chosen-ciphertext attack. Atak z wybranym szyfrogramem.

1. Trzy własności hasza. Dla odporności na odwrócenie, drugi przeciwobraz i kolizje zapisz wejście przeciwnika i warunek wygranej. Wyjaśnij, dlaczego przeciwnik wybierający obie wiadomości ma inne zadanie niż przeciwnik z otrzymaną wiadomością.
2. Jawny znacznik. Oceń $\tau=\mathcal D(m)$ jako MAC. Zbuduj fałszerza po zmianie wiadomości. Następnie wyjaśnij, dlaczego samo $\mathcal D(k\|m)$ nie jest uniwersalnym zamiennikiem HMAC. Przy haszu Merkle’a–Damgårda z ujawnionym stanem końcowym wskaż rolę dopełnienia w przedłużaniu wiadomości.

   HMAC

   Hash-based Message Authentication Code. Kod uwierzytelnienia wiadomości oparty na funkcji haszującej. Przyrostek SHA-256 wskazuje użyty hasz.

3. MAC z PRF. Dla $\tau=F_k(m)\in\{0,1\}^n$ wykaż granicę dla jednej próby na nowej wiadomości. W losowej grze warunkuj względem całej dotychczasowej tabeli. Rozszerz ostrożnie na $v$ prób weryfikacji.
4. Encrypt-then-MAC. Dla niezależnych kluczy rozpisz tabelę symulatora deszyfrującego. Co zwraca dla znanej pary? Co dla nowej niepoprawnej pary? Jakie zdarzenie pozwala mu przerwać? Uwzględnij AAD i zakaz deszyfrowania wyzwania.

   AAD

   Additional Authenticated Data. Dodatkowe dane uwierzytelniane, ale nieszyfrowane.

5. Pogłębienie: znaczniki niejednoznaczne. Wyjaśnij, dlaczego nowy poprawny znacznik dla już podpisanego szyfrogramu wymaga silnej niepodrabialności albo szczególnej własności MAC. Podaj różnicę między nową wiadomością a nową parą wiadomość–znacznik.

Wynik pracy: definicja gry, redukcja i jej granica. Test odrzucenia jednego zmienionego bitu nie dowodzi odporności na wszystkie fałszerstwa.

6. GHASH jako rachunek w ciele. Po C0a.2 przyjmij działania w $\mathbb F_{2^{128}}$ i ustalony element $H$. Dla $Y_0=0$, $Y_i=(Y_{i-1}\oplus S_i)\cdot H$ wyprowadź $Y_2=S_1\cdot H^2\oplus S_2\cdot H$. Oddziel kluczowy element $H=\operatorname{AES}_K(0^{128})$ od funkcji skrótu $\mathcal H$. Na podstawie NIST SP 800-38D, §6–7 rozpisz bloki wejściowe GCM dla 1 bajtu AAD i 17 bajtów szyfrogramu. Długości 8 i 136 kodujemy w bitach, każdą na 64 bitach. Dlaczego samo dopełnienie zerami nie wystarcza do odróżnienia danych kończących się zerami? Wyjaśnij rolę bloku długości i końcowej maski AES. GHASH nie jest samodzielnym publicznym haszem odpornym na kolizje ani kompletnym MAC. Implementacja: L1.6.

   NIST

   National Institute of Standards and Technology. Amerykański Narodowy Instytut Standaryzacji i Technologii.

   SP

   Special Publication. Seria publikacji specjalnych NIST.

   GCM

   Galois/Counter Mode. Tryb Galois/licznikowy, łączący szyfrowanie ze sprawdzaniem integralności.

C5. Identyfikacja i ujawniona losowość

Przygotowanie: W6: grupy, skalary i pairing, następnie W7: Schnorr, symulacja i ekstrakcja oraz W8: identyfikacja i ujawnienia.

Rama rozwiązania: zacznij od interfejsu identyfikacji. Oddziel Setup i KeyGen od lokalnych kroków Commit, Challenge, Respond i Check. Przy każdym zapisz stronę wykonującą, wejście, wynik i stan zachowany do następnego kroku. Wyprowadzone równanie umieść dopiero pod odpowiadającym mu wywołaniem.

Stosujemy oznaczenia z wykładu. Grupa $G=\langle g\rangle$ ma pierwszy rząd $q$. Sekret to $a$, klucz publiczny $A=g^a$, losowość sesji $u$, zobowiązanie $X=g^u$, wyzwanie $c$, odpowiedź $s=u+a\cdot c$. Działania na skalarach wykonujemy w $\mathbb Z_q$. $\mathcal H$ zwraca skalar, a $\mathcal H_{G_1}$ poprawny punkt grupy $G_1$.

Punktem wyjścia jest zapis potęgowy, również wtedy, gdy wybraną grupę realizujemy na krzywej. Równanie $g^s=X\cdot A^c$ opisuje Schnorra bez wchodzenia w działania na współrzędnych. W notacji addytywnej staje się $s\cdot P=X+c\cdot A$, gdzie $P$ jest generatorem. Nie zmienia się odpowiedź $s=u+a\cdot c$. Zadania zapisane punktowo pozostają w tej notacji, aby można było powiązać rachunek z biblioteką.

Zanim obliczysz ekstrakcję: odtwórz trzy ataki z W8. W każdym wypisz dane wejściowe oszusta, zobowiązanie wysłane przed wyzwaniem i odpowiedź obliczoną po wyzwaniu. Nie wolno używać sekretu z konfiguracji testowej. Dla wariantu afinicznego pokaż nowe zobowiązanie, inne niż obserwowane. Dlaczego przechowywanie poprzednich zobowiązań nie naprawia tego wariantu?

1. Poprawność Schnorra. Wyprowadź $g^s=X\cdot A^c$ ze wzoru odpowiedzi. Zapisz identyczny rachunek addytywnie. Wskaż, które wielkości są skalarami, a które punktami.
2. Znany nonce. Mając poprawny transkrypt i $u$, wyprowadź $a=(s-u)/c$ dla $c\ne0$. Co otrzymujesz przy $c=0$? Nie wykonuj dzielenia przez zero.
3. Reset bez znajomości nonce. Mając dwa poprawne transkrypty z tym samym $X$ i różnymi wyzwaniami, odzyskaj $a$. Odróżnij reset do tej samej nieznanej wartości od ustawienia wartości znanej.
4. Symulator. Wylosuj niezależne $c,s$ z całego $\mathbb Z_q$ i oblicz $X=g^s\cdot A^{-c}$. Udowodnij równość rozkładów z uczciwą rozmową dla $u,c\overset{\$}{\leftarrow}\mathbb Z_q$, nie tylko akceptację. Następnie zmień profil na $u\ne0$. Zastosuj odrzucanie neutralnego $X$ w symulatorze, jak w W7, i policz prawdopodobieństwo przyjęcia próby. Dlaczego te rachunki uzasadniają HVZK, ale same nie wystarczają dla dowolnego złośliwego weryfikatora?

   HVZK

   honest-verifier zero knowledge. Zerowa wiedza wobec uczciwego weryfikatora.

5. Pogłębienie: odpowiedź w grupie. Dla $B=\mathcal H_{G_1}(\operatorname{enc}(X,c))$ i $S=(u+a\cdot c)\cdot B$ sprawdź równanie pairingowe z wykładu. Po poznaniu $u$ i dla $c\ne0$ wykaż, że algebraicznie można otrzymać $a\cdot B$. Dlaczego to nie jest jeszcze odzyskanie skalara $a$? Co zmienia znajomość logarytmu $B$ względem stałego generatora?

MCL

mcl. Nazwa biblioteki kryptograficznej Herumi do szybkich obliczeń grupowych i pairingów.

WebAssembly

WebAssembly. Format kodu wykonywanego m.in. w przeglądarce. Wasm i WASM to jego skrócone nazwy.

BLS12-381

Barreto–Lynn–Scott. Rodzina krzywych eliptycznych. W BLS12-381 stopień zanurzenia wynosi 12, a moduł ciała bazowego ma 381 bitów. To inny zestaw nazwisk niż w podpisie BLS.

C6. Podpisy i obowiązki redukcji

Przygotowanie: W7: transkrypt Schnorra i ekstrakcja, następnie W9: konstrukcja podpisu i niepodrabialność. Do zadań 3 i 5 przeczytaj dodatek B: symulacja podpisów i forking.

Rama rozwiązania: użyj Setup, KeyGen, Sign i Verify. Wskaż dokładną wiadomość wejściową Sign oraz dane potrzebne później w Verify. Podpisujący nie jest dodatkową stroną uczestniczącą w publicznej weryfikacji.

1. Fiat–Shamir. Zapisz generowanie, podpis i weryfikację dla $c=\mathcal H(\operatorname{enc}(A,X,m))$. Wskaż kodowanie bez niejednoznaczności. Wyjaśnij, dlaczego identyczny tekst bajtowy nie może oznaczać dwóch różnych krotek.
2. Dwa fałszerstwa. Wyprowadź ekstrakcję przy tym samym kluczu i zobowiązaniu. Następnie podaj przykład dwóch poprawnych podpisów z różnymi zobowiązaniami, dla których ten wzór nie odzyskuje klucza.
3. Wyrocznia podpisu. Redukcja zna tylko $A$. Pokaż programowanie hasza dla symulowanego podpisu. Wskaż kolizję z zajętym wpisem jako zdarzenie przerwania i wyprowadź granicę z liczby zajętych wpisów.
4. BLS i celowo błędny hasz. Przyjmij $\mathcal H_{\mathrm{bad}}(m)=\mu(m)\cdot P_1$ dla jawnego skalara $\mu(m)$. Z jednego podpisu pod wiadomością o $\mu(m)\ne0$ odzyskaj punkt pozwalający tworzyć podpisy pod innymi wiadomościami. Nie nazywaj tej funkcji $\mathcal H_{G_1}$.

   BLS

   Boneh–Lynn–Shacham. Nazwiska autorów schematu krótkich podpisów z pairingiem.

5. Pogłębienie: strata forkingu. Wyjaśnij każdą zmienną we wzorze $\epsilon_0^2/Q-\epsilon_0/h$. Podaj przykład parametrów, przy których dolna granica jest niedodatnia. Czy wynika stąd, że ekstrakcja jest niemożliwa?

Wynik pracy: poprawność, atak na zły wariant i szkic redukcji dla właściwego wariantu stanowią trzy osobne części.

6. Podpis z odzyskiwanym zobowiązaniem. Dla $A=g^a$, $X=g^u$, $c=\mathcal H(\operatorname{enc}(\mathrm{suite},A,X,m))$ i $s=(u+a\cdot c)\bmod q$ zastąp podpis $(X,s)$ parą $(s,c)$. Wyprowadź $X'=g^s\cdot A^{-c}$ i zapisz pełny Verify, który ponownie oblicza hasz. Wskaż argumenty publiczne oraz sprawdzane zakresy. Czy można pominąć porównanie wyzwania z haszem tylko dlatego, że równanie grupowe dało jakiś punkt? Następnie zapisz odzyskanie zobowiązania addytywnie. To ta sama konstrukcja w innym formacie, nie osobna obietnica bezpieczeństwa. Porównanie implementacyjne: L4.7.

C7. Ustalanie klucza i modele AKE

AKE

Authenticated Key Exchange. Uwierzytelniona wymiana klucza.

Przygotowanie: W10 i dodatek C.

Rama rozwiązania: rozdziel długoterminowe klucze, Start i Next. Dla każdego przejścia określ komunikat wejściowy, lokalne wywołania, komunikat wyjściowy i status sesji. Osobno zaznacz moment obliczenia sekretu DH i moment udostępnienia zaakceptowanego klucza aplikacji.

DH

Diffie–Hellman. Nazwiska autorów metody uzgadniania wspólnego sekretu.

1. DH bez uwierzytelniania. Narysuj dwie równoległe rozmowy z przeciwnikiem pośrodku. Podaj oba klucze przeciwnika. Wyjaśnij, dlaczego poprawne równanie DH nie identyfikuje partnera.
2. SIGMA. Dla każdego komunikatu wskaż, co wiąże podpis i co wiąże MAC. Rozróżnij autentyczność wkładu DH, powiązanie tożsamości i potwierdzenie znajomości klucza. Omów, kiedy obie strony mogą uznać sesję za zakończoną.

   SIGMA

   SIGn-and-MAc. Podejście łączące podpis cyfrowy i kod uwierzytelnienia wiadomości.

3. NAXOS. Zapisz po obu stronach trzy składniki wejścia do $\mathcal K$. Sprawdź osobno ich zgodność i kolejność. Wyjaśnij, dlaczego hasz krotki powinien obejmować tożsamości w ustalonej kolejności ról.

   NAXOS

   NAXOS. Nazwa własna protokołu uwierzytelnionej wymiany klucza, nie skrót rozwijany do angielskich słów.

4. Świeżość. Dla uczciwie partnerowanych sesji sklasyfikuj ujawnienia: $a$, $(a,b)$, $(a,r_B)$, $(a,r_A)$, klucz partnera. Powtórz analizę dla braku sesji partnera. Oddziel „atak trywialny” od „przypadek wykluczony definicją”.
5. Pogłębienie: redukcja przez zapytanie. Dla wyroczni $\mathcal K$ zapisz zdarzenie, że przeciwnik pyta o dokładną krotkę sesji testowej. Wyjaśnij sprzężenie eksperymentu z kluczem rzeczywistym i losowym do tego zdarzenia. Które dodatkowe błędy może wprowadzić symulacja innych sesji?

Dalszy krok: wybierz jeden przypadek ekspozycji z oryginalnej pracy NAXOS. Wypisz instancję problemu, wiedzę symulatora, odpowiedzi na wszystkie wyrocznie i zdarzenie ekstrakcji. Nie przenoś automatycznie dowodu do innego modelu.

6. Parametry i niepoprawny wkład DH. Dla podgrupy $G=\langle g\rangle$ o pierwszym rzędzie $q$ uzasadnij $Y^x=X^y$ przy $X=g^x$, $Y=g^y$. Co otrzyma odbiorca, jeśli przyjmie neutralne $Y=1_G$? Dla podgrupy $\mathbb F_p^*$ wskaż kontrolę $Y^q=1$ oraz osobne odrzucenie $Y=1$. Dla krzywej zapisz ich addytywne odpowiedniki i wcześniejsze sprawdzenie współrzędnych. Dlaczego pierwszy rząd podgrupy nie jest jeszcze dowodem założenia DDH? Jako kontrprzykład rozważ grupę z efektywnie obliczalnym, niedegenerowanym symetrycznym pairingiem: porównaj $e(g^x,g^y)$ z $e(g,T)$. Nie przenoś tego testu automatycznie do pojedynczej grupy źródłowej pairingu typu 3. Zastosowanie: L5.6.

   DDH

   Decisional Diffie–Hellman. Decyzyjny problem Diffiego–Hellmana.

C8. Szyfrowanie z kluczem publicznym

Przygotowanie: W6: grupy i problemy trudne, następnie W10a: ElGamal i Cramer–Shoup. Do zadania 5 przeczytaj W10b: RSA.

RSA

Rivest–Shamir–Adleman. Nazwiska autorów kryptosystemu z kluczem publicznym.

Rama rozwiązania: zapisz Setup, KeyGen, Enc i Dec. Oznacz klucz publiczny odbiorcy, jego klucz tajny i losowość konkretnego szyfrowania. Zapisz jawnie wywołanie Enc z wiadomością oraz wywołanie Dec z otrzymanym szyfrogramem. Dopiero potem podstaw działania grupowe.

1. ElGamal. Dla $(U,V)=(g^r,m\cdot A^r)$ wyprowadź deszyfrowanie. Przestrzenią wiadomości jest grupa. Wyjaśnij, dlaczego kodowanie dowolnego pliku do jednego elementu grupy nie jest automatycznym krokiem.
2. Modyfikowalność. Przekształć szyfrogram tak, aby zaszyfrowana wiadomość zmieniła się na $m\cdot\Delta$. Zbuduj atak z wyrocznią deszyfrującą, przestrzegając zakazu zapytania o dokładny szyfrogram wyzwania.
3. Dowód IND-CPA. Otrzymujesz $(g,A,U,T)$. Zaszyfruj wybraną wiadomość jako $(U,m_b\cdot T)$. Pokaż oba rozkłady. W jakiej grze redukcja nie potrzebuje znać sekretu klucza publicznego?
4. KEM–DEM. Opisz typy wejścia i wyjścia kapsułkowania, wyprowadzania klucza i AEAD. Rozdziel błędy dekapsulacji od odrzucenia znacznika. Wyjaśnij rolę kontekstu i długości kluczy.

   KEM

   Key Encapsulation Mechanism. Mechanizm enkapsulacji klucza.

   DEM

   Data Encapsulation Mechanism. Mechanizm symetrycznej ochrony danych w szyfrowaniu hybrydowym.

5. Pogłębienie. Dlaczego surowe RSA jest deterministyczne? Jaką rolę pełni schemat kodowania w szyfrowaniu i podpisie RSA? Nie traktuj dowodu dla jednego schematu jako dowodu dla dowolnego użycia potęgowania RSA.

C9. Anonimowość i podpisy pierścieniowe

Przygotowanie: W11.

1. Eksperyment anonimowości. Zapisz pierścień, dwie możliwe tożsamości podpisującego, bit wyzwania, ujawniany podpis i dostępne klucze. Wskaż, co trzeba wykluczyć, aby zadanie nie było trywialne.
2. Dowód OR. Dla kluczy $A_1,\ldots,A_n$ i znanego sekretu $a_j$ odtwórz protokół z W11. Sprawdź każde równanie weryfikacyjne i warunek $\sum_i c_i=c$.

   OR

   or. Lub, czyli alternatywa logiczna. To angielskie słowo, nie akronim. Dowód OR dotyczy spełnienia co najmniej jednej z podanych relacji.

3. Równość rozkładów. Ustal globalne wyzwanie $c$ oraz akceptujący transkrypt. Porównaj liczbę i prawdopodobieństwo wyborów losowych prowadzących do niego przy dwóch różnych świadkach. Następnie uwzględnij także niezależne losowanie $c\overset{\$}{\leftarrow}\mathbb Z_q$. Wyjaśnij różnicę między prawdopodobieństwem warunkowym $q^{-(2n-1)}$ a bezwarunkowym $q^{-2n}$. Oddziel nierozróżnialność świadka od niepodrabialności.
4. Metadane. Wymień kanały ujawniające autora mimo algebraicznie anonimowego podpisu, np. dobór pierścienia, czas wysłania i źródło połączenia. Które z nich obejmuje powyższa gra?
5. Pogłębienie: hierarchie. W demonstratorze HRS odróżnij bezpośrednich poprzedników od zbioru potencjalnych podpisujących na liściach. Dlaczego administracyjnie znany autor demonstracji nie jest polem publicznego podpisu?

   HRS

   hierarchical ring signatures. Hierarchiczne podpisy pierścieniowe.

Wynik pracy: dokładny rozkład lub eksperyment. Sam fakt, że podpis nie zawiera jawnego nazwiska, nie jest dowodem anonimowości.

C10. Zaprzeczalność i dowód dla odbiorcy

Przygotowanie: W5: MAC, Schnorr i Stinson–Wu, W9: podpisy, W10: uwierzytelnienie sesji oraz W11: anonimowość i zaprzeczalność.

1. MAC a podpis. Alicja i Bob znają wspólny klucz MAC. Bob przedstawia zewnętrznej osobie wiadomość i znacznik. Dlaczego nie dowodzi tym, że autorem była Alicja? Porównaj sytuację z podpisem publicznie weryfikowalnym.

2. Symulacja transkryptu. Użyj symulatora Schnorra do wygenerowania akceptującej rozmowy. Co przekonuje uczestniczącego weryfikatora, a co może przekonać osobę widzącą wyłącznie zapis? Uwzględnij moment wyboru wyzwania.

3. Cel bezpieczeństwa. Rozróżnij uwierzytelnienie partnera podczas rozmowy i możliwość późniejszego przypisania treści. Podaj scenariusz, w którym oba cele nie powinny występować naraz.

4. Pogłębienie: model. Zapisz, kto symuluje, jakie klucze zna, czy ma interakcję oraz które ujawnienia są dopuszczalne. Dlaczego twierdzenie o jednym transkrypcie nie daje automatycznie pełnej zaprzeczalności sesyjnego protokołu?

5. Weryfikator zna odpowiedź. Odtwórz uczciwy transkrypt Stinsona–Wu, znając tylko klucz publiczny $A$. Wyjaśnij, dlaczego weryfikator może go symulować, a podsłuchujący nie otrzymuje przez to sposobu odpowiedzi na cudze wyzwanie.

6. Zmiana modelu. Ujawnij $r$ weryfikatora Stinsona–Wu. Zbuduj odpowiedź bez sekretu dowodzącego. Czy atak odzyskuje ten sekret? Czy usunięcie kontroli skrótu daje takie samo uprawnienie, czy inne?

7. Fiat–Shamir. Dla symulowanego Schnorra sprawdź osobno równanie grupowe i warunek wyzwania z hasza. Wyjaśnij, dlaczego nie wystarczy po prostu poprawić $c$ po zbudowaniu $X$. Następnie sprawdź, dlaczego upublicznienie $r=\mathcal H(m)$ w Stinsonie–Wu nie daje podpisu.

Wynik pracy: dwie osobne listy założeń dla bezpieczeństwa podczas sesji i dla późniejszej interpretacji jej zapisu. Każdy atak zapisz jako algorytm z jawnymi wejściami, bez ukrytego dostępu do sekretu.

C11. Współdzielenie, rozgłaszanie i zobowiązania

Przygotowanie: W13: Shamir i wykluczanie odbiorców. Do zadania 5 przeczytaj W14: zobowiązania Pedersena.

1. Shamir. W $\mathbb Z_{101}$ przyjmij $f(z)=42+7\cdot z+3\cdot z^2$. Oblicz pięć udziałów dla $z=1,\ldots,5$. Odtwórz sekret z udziałów 1, 3 i 5. Współczynniki interpolacji policz w ciele, nie na liczbach zmiennoprzecinkowych.
2. Prywatność dwóch udziałów. Dla dowolnego proponowanego sekretu policz liczbę wielomianów stopnia co najwyżej 2 zgodnych z dwoma ustalonymi udziałami. Wyjaśnij, dlaczego trzeba losować współczynniki jednostajnie, również dopuszczając zero.
3. Błędny udział. Zmień jeden udział i odtwórz sekret. Czy podstawowy Shamir sam wykrywa oszustwo? Odróżnij dzielenie sekretu od weryfikowalnego dzielenia sekretu.
4. Wykluczenie. W systemie drzewa kluczy zaznacz odwołanego odbiorcę i poddrzewa, którymi można pokryć pozostałych. Wyjaśnij różnicę między odwołaniem przyszłego dostępu a odebraniem już poznanego klucza.
5. Pogłębienie: Pedersen. Dla $C=g^m\cdot h^r$ i nieznanego $\log_g h$ udowodnij ukrywanie przy jednostajnym $r$. Z dwóch otwarć o różnych wiadomościach wyprowadź $\log_g h$. Co się dzieje, jeśli twórca parametrów zna ten logarytm?

C12. Obwód, etykiety i prywatny widok

Przygotowanie: W6: grupy i problemy DH, W12: OT i modele prywatności, następnie garbled circuits.

OT

Oblivious Transfer. Transfer utajniony. Odbiorca poznaje wybraną wartość, a nadawca nie poznaje jego wyboru.

1. Rozpisz tabelę funkcji $d=(a\land b)\oplus c$. Dla ustalonego wejścia Boba wskaż, jakie informacje o wejściu Alicji wynikają z samego wyniku. Wyjaśnij, dlaczego ich ujawnienie nie musi naruszać definicji prywatności.
2. Dla losowych bitów $\pi_u,\pi_v$ ułóż cztery wiersze tabeli według $p_u(x)=x\oplus\pi_u$ i $p_v(y)=y\oplus\pi_v$. Pokaż, że numer wiersza nie jest jawną parą $(x,y)$.
3. Zdefiniuj wejścia symulatora dla półuczciwego wykonawcy. Wskaż, dlaczego wydanie obu etykiet Boba zmienia model. Oddziel rolę OT od roli szyfrowania wierszy.
4. Sprawdź równanie Free-XOR dla wszystkich czterech par bitów. Wyjaśnij, dlaczego wspólna różnica etykiet wymaga odpowiedniego założenia, a nie tylko zwykłej deklaracji „używamy AES”.
5. Dla 1000 bramek AND, 4000 bramek XOR i 128-bitowych bloków oblicz rozmiar samych tabel w trzech wariantach z wykładu. Wynik podaj w bajtach i KiB. Wypisz pominięte składniki komunikacji.

   AND

   and. I, czyli koniunkcja logiczna. To angielskie słowo, nie akronim. Bramka AND zwraca 1 tylko wtedy, gdy oba wejścia mają wartość 1.

   KiB

   kibibyte. Kibibajt, czyli 1024 bajty.

Punkt kontrolny: dla half-gates same tabele zajmują $2\cdot128\cdot1000/8=32000$ bajtów. Nie jest to rozmiar całego protokołu ani pomiar szybkości implementacji.

C13. Próg i dowód znajomości sekretu

Przygotowanie: identyfikacja progowa.

1. W $\mathbb Z_{101}$ przyjmij $f(z)=17+9\cdot z$. Oblicz udziały 1, 2 i 3. Dla każdego z trzech podzbiorów dwuelementowych policz wagi Lagrange’a i odtwórz wyraz wolny.
2. Dla $I=\{1,3\}$ wybierz $u_1=8,u_3=12,c=7$. Oblicz odpowiedzi częściowe i ich sumę. Sprawdź skalarną tożsamość poprzedzającą równanie grupowe.
3. Zbuduj symulator końcowego transkryptu dla uczciwego weryfikatora. Wyjaśnij, dlaczego nie jest to jeszcze symulator pełnego widoku złośliwego koordynatora.
4. Wyprowadź wzór odzyskania udziału po resecie jego nonce. Wskaż, które identyfikatory i wagi muszą pozostać takie same w obu transkryptach.
5. Udowodnij równanie składania progowego BLS. Porównaj klucz weryfikacji z multipodpisem kilku niezależnych kluczy. Określ, co musi być uwierzytelnione przed weryfikacją udziałów.

Punkt kontrolny: dla $I=\{1,3\}$ wagi wynoszą 52 i 50 modulo 101. Odpowiedzi sumują się do 38, co odpowiada $8+12+7\cdot17$ modulo 101. Grupa rzeczywistego demonstratora ma inny, kryptograficznie duży rząd.

C14. Dopuszczalne obliczenie na szyfrogramach

Przygotowanie: szyfrowanie homomorficzne.

1. Rozwiń wszystkie cztery wykładniki w równaniu deszyfrowania iloczynu. Zaznacz wyrazy, które się znoszą. Dla każdego argumentu pairingu wypisz jego typ.
2. Pokaż, jak komponentowe mnożenie szyfrogramów w $G_T^4$ odpowiada dodawaniu ich wiadomości. Dlaczego ten sam krok nie mnoży wiadomości?
3. Wyprowadź granicę $|z|\le n\cdot B_x\cdot B_y$ dla iloczynu skalarnego. Zaproponuj test przekroczenia zakresu dekodowania bez sugerowania, że problemem jest zawsze przekroczenie modułu.
4. Pokaż atak na poufność małej wiadomości w szyfrogramie $G_1$, jeżeli obok $k\cdot P_1$ opublikowano również $k\cdot P_2$. Wykorzystaj pairing do sprawdzenia kandydata wiadomości.
5. Wyjaśnij różnicę między utajnieniem wejść, poprawnością homomorfizmu i dowodem poprawnego wykonania żądanej funkcji przez złośliwy serwer.

C15. Koszt i granice nowoczesnych mechanizmów

Przygotowanie: złożoność, PQC, SNARK. Do zadania 4 potrzebne są również W14: zobowiązania i otwarcia.

PQC

Post-Quantum Cryptography. Kryptografia postkwantowa.

SNARK

Succinct Non-interactive Argument of Knowledge. Zwięzły nieinteraktywny argument wiedzy.

1. Dla bezpośredniej weryfikacji BLS i Schnorra zbuduj koszt symboliczny. Następnie podstaw własne pomiary, bez traktowania wyniku jako uniwersalnego rankingu schematów.

2. Wyjaśnij, dlaczego trzy elementy dowodu nie oznaczają stałego czasu przetworzenia dowolnie długiego wejścia publicznego.

3. Wyprowadź pozostały błąd po odjęciu $s^\mathsf{T}\cdot u$ w przykładzie LWE. Dla $q=100$ wskaż obszary poprawnego dekodowania bitów. Dlaczego ten mały rachunek nie określa bezpiecznych parametrów ML-KEM?

   LWE

   Learning With Errors. Problem uczenia z błędami, związany z równaniami zaburzonymi szumem.

   ML-KEM

   Module-Lattice-Based Key-Encapsulation Mechanism. Mechanizm enkapsulacji klucza oparty na kratach modułowych. ML oznacza tu kraty modułowe, a nie uczenie maszynowe.

4. Zaproponuj relację do dowodzenia poprawnego iloczynu skalarnego danych związanych zobowiązaniami. Oddziel wejście publiczne, świadek i warunki zakresu. Sprawdź, czy wynik jest liczony jako liczba całkowita, czy w ciele skończonym.

5. Dla migracji do KEM postkwantowego wypisz, co zmieniasz w ustanawianiu klucza, a co nadal należy do uwierzytelniania i AEAD.

6. Liczba operacji a czas. Rozpisz lewostronne square-and-multiply dla dodatniego wykładnika $n$. Zacznij od najwyższego bitu równego 1, ustaw wynik na podstawę i przetwarzaj pozostałe bity. Wyprowadź liczbę podniesień do kwadratu i dodatkowych mnożeń jako funkcję długości bitowej $\ell$ oraz wagi Hamminga $w$, czyli liczby jedynek. Otrzymasz odpowiednio $\ell-1$ i $w-1$. Porównaj 13 i 15, zapisując oba przebiegi. Co ujawnia sama liczba operacji? Dlaczego nawet identyczna liczba operacji dla wszystkich skalarów nie dowodzi stałego czasu programu? Wskaż rolę rozgałęzień, dostępu do pamięci oraz arytmetyki biblioteki. Pomiar wykonasz w L9.6.

C16. Delegacja, typy i ukryte przyporządkowanie

Przygotowanie: reenkrypcja i miksy.

1. Ten sam odbiorca. Wyprowadź rerandomizację ElGamala w obu notacjach. Dla ustalonego $r$ i jednostajnego $t\in\mathbb Z_q$ udowodnij, że $r+t$ ma rozkład jednostajny. Czy to samo zdanie pozostaje dokładnie prawdziwe po wykluczeniu zera z dziedziny $t$?
2. Nowy odbiorca. Odtwórz algebraicznie BBS. Wyprowadź odwrotność delegacji, złożenie dwóch delegacji i odzyskanie sekretu Alicji przez Boba wraz z proxy. Przy każdym kroku podaj, kto zna jego argumenty.

   BBS

   Blaze–Bleumer–Strauss. Nazwiska autorów omawianej reenkrypcji. Nie chodzi o generator Blum–Blum–Shub.

3. Kontrola typów AFGH. Rozpisz wejście i wyjście każdej operacji. W którym kroku pierwszy składnik przechodzi z $G_1$ do $G_T$? Dlaczego nie można ponownie użyć tej samej funkcji reenkrypcji?

   AFGH

   Ateniese–Fu–Green–Hohenberger. Nazwiska autorów omawianego schematu reenkrypcji z pairingiem.

4. Sekret a zdolność odczytu. Wyprowadź $a_1\cdot P_2$ z klucza delegacji AFGH i $b_2$. Pokaż odszyfrowanie szyfrogramu Alicji bez poznania skalaru $a_1$. Sformułuj dwie różne własności bezpieczeństwa, które rozdziela ten przykład.
5. Brakujące składniki miksu. Dla czterech szyfrogramów opisz algorytm śledzenia przy samym tasowaniu i przy samej rerandomizacji. Co zmienia ich połączenie? Jakie dodatkowe założenia są potrzebne, zanim nazwiesz wynik anonimowym?
6. Nie wystarczy iloczyn. Dla dwóch szyfrogramów ElGamala pomnóż drugi składnik jednego przez $\Delta\ne1$, a drugiego przez $\Delta^{-1}$. Iloczyn pozostaje taki sam. Wybierz wiadomości i $\Delta$, dla których multizbiór wiadomości się zmienia. Jaką relację powinien zamiast tego dowodzić shuffle?

Wynik pracy: równania poprawności, jawne algorytmy ataków i tabela „gwarancja / założenia / czego gwarancja nie obejmuje”.

C17. RSA: poprawność, kodowanie i redukcja FDH

FDH

Full Domain Hash. Haszowanie o pełnej dziedzinie wyników.

Punkt wyjścia: RSA i dowód FDH. Rozdziel argument poprawności od założenia obliczeniowego i eksperymentu bezpieczeństwa.

1. Dla $p=61$, $r=53$, $e=17$ oblicz $N$, funkcję Eulera $\varphi(N)=(p-1)\cdot(r-1)$ i odwrotność $d=e^{-1}\bmod\varphi(N)$. Sprawdź szyfrowanie i odszyfrowanie reprezentanta $65$. Powtórz rachunek dla $61$, który nie należy do $\mathbb Z_N^*$. Uzasadnij oba wyniki przez CRT, nie przez niepoprawne zastosowanie twierdzenia Eulera do nieodwracalnej reszty. Następnie oblicz $\lambda(N)$ jako najmniejszą wspólną wielokrotność $p-1$ i $r-1$. Wyjaśnij, dlaczego warunek modulo $\varphi(N)$ wystarcza, choć standard dopuszcza także odwrotność modulo $\lambda(N)$.

   CRT

   Chinese Remainder Theorem. Chińskie twierdzenie o resztach.

2. W eksperymencie IND-CPA dla surowego RSA wybierz dwie różne wiadomości i opisz przeciwnika wygrywającego bez klucza prywatnego. Następnie skonstruuj akceptowaną parę wiadomość–podpis dla surowego podpisu RSA bez zapytania o podpis. Wyjaśnij, dlaczego ten drugi atak nie daje podpisu dowolnego z góry wskazanego tekstu.
3. Dla OAEP z modułem 2048-bitowym i SHA-256 policz maksymalną długość wiadomości. Czy 190 polskich znaków musi się zmieścić? Odpowiedź uzasadnij różnicą między znakiem a bajtami UTF-8.

   OAEP

   Optimal Asymmetric Encryption Padding. Kodowanie wiadomości przed szyfrowaniem asymetrycznym.

   UTF-8

   Unicode Transformation Format, 8-bit. Kodowanie znaków Unicode za pomocą jednostek 8-bitowych. Jeden znak może wymagać kilku bajtów.

4. Narysuj dwa kierunki maskowania OAEP. Wskaż, z czego deszyfrujący odtwarza zalążek, a potem blok danych. Dla PSS wskaż, które pola sprawdza się przy weryfikacji. Wyjaśnij, dlaczego sama długość podpisu nie wystarcza do identyfikacji schematu.

   PSS

   Probabilistic Signature Scheme. Probabilistyczny schemat podpisu.

5. Zbuduj tabelę symulatora FDH z dwoma wpisami. Zasymuluj kolejność: podpis $m_1$, hasz $m_1$, hasz $m_2$, ponowny hasz $m_2$. Nie znasz $d$. Wybierz $J=2$ przed rozpoczęciem i zapisz, które odpowiedzi umiesz wygenerować.
6. Dokończ redukcję dla świeżego fałszerstwa na $m_2$. Osobno omów żądanie podpisu $m_2$, fałszerstwo innej wiadomości oraz brak wcześniejszego zapytania o hasz wiadomości końcowej. Wyjaśnij składniki $q_H+q_S+1$.
7. Uzasadnij jednostajność zwykłych odpowiedzi $u_m^e$. W którym miejscu używasz tego, że potęgowanie jest permutacją? Dlaczego redukcja nie może wybrać docelowej pozycji po zobaczeniu fałszerstwa?
8. Porównaj dowody FDH i Schnorra. Zapisz: trudna instancja, sposób symulacji, warunek przerwania i wynik ekstrakcji. Nie opisuj FDH jako zastosowania forking lemma.

Wynik: rachunek RSA, dwa jawne ataki na surowe konstrukcje i kompletny opis redukcji wraz z granicą sukcesu. Wskaż odpowiedni fragment pracy Bellare’a i Rogawaya oraz rozdziały RFC 8017. Nie przypisuj standardowi dowodu, który dotyczy innego kodowania.

C18. Uwierzytelnianie: poprawny podpis w złym kontekście

Punkt wyjścia: FIDO2 i passkeys, OIDC i SSO.

FIDO2

Fast IDentity Online. Rodzina standardów uwierzytelniania. FIDO2 łączy standard przeglądarkowy WebAuthn z protokołem CTAP.

OIDC

OpenID Connect. Warstwa uwierzytelniania oparta na mechanizmie delegowania dostępu OAuth 2.0.

SSO

Single Sign-On. Jednokrotne logowanie wykorzystywane przez wiele usług.

1. Wypisz bajty objęte podpisem odpowiedzi WebAuthn. Wskaż miejsce wyzwania, origin, skrótu RP ID i flag UP/UV. Które z tych pól wchodzą do podpisu przez dodatkowy skrót?

   WebAuthn

   Web Authentication. Standard uwierzytelniania w aplikacjach internetowych z użyciem klucza publicznego.

   RP

   Relying Party. Usługa polegająca na wyniku uwierzytelnienia.

   ID

   identifier / identification. Identyfikator / identyfikacja, zależnie od nazwy pola. RP ID identyfikuje usługę, a ID Token przekazuje informację o uwierzytelnieniu.

   UP

   User Presence. Obecność użytkownika potwierdzona interakcją z uwierzytelniaczem.

   UV

   User Verification. Lokalna weryfikacja użytkownika przez uwierzytelniacz.

2. Rozważ poprawnie podpisaną odpowiedź starej transakcji. Dlaczego jej matematyczna weryfikacja może dawać prawdę, a decyzja RP musi być negatywna? Porównaj to z odpowiedzią, w której napastnik zmienił bajt już po podpisaniu.
3. Dla podanego równania ECDSA wyprowadź $X=u\cdot P$ w uczciwym przebiegu. Wymień warunki zakresu i przypadki odrzucenia. Następnie wskaż, których kontroli WebAuthn ten rachunek jeszcze nie obejmuje.

   ECDSA

   Elliptic Curve Digital Signature Algorithm. Algorytm podpisu cyfrowego na krzywych eliptycznych.

4. Narysuj przepływ kodu OIDC z backendem. Oddziel komunikaty przez przeglądarkę od połączenia backend–IdP. W którym kanale przekazywane jest publiczne wyzwanie PKCE, a w którym sekret?

   PKCE

   Proof Key for Code Exchange. Powiązanie wymiany kodu autoryzacyjnego z sekretem klienta.

5. Dostawca podpisał ID Token z poprawnymi czasami i użytkownikiem, ale dla innego aud. Czy aplikacja może go przyjąć? Co zmienia poprawny aud, ale niezgodny nonce?
6. Podaj atak na logowanie, który nie wymaga fałszowania podpisu. Określ założenia o przeglądarce, TLS i stanie serwera. Nie nazywaj bezpieczeństwa podpisu dowodem całego systemu.

   TLS

   Transport Layer Security. Protokół ochrony komunikacji, zapewniający m.in. poufność i integralność.

7. Wyjaśnij, dlaczego TOTP można przekazać dalej w ataku phishingowym. Jakie dodatkowe związanie ma WebAuthn? Dlaczego synchronizowany passkey i klucz sprzętowy nie mają identycznych założeń o przechowywaniu sekretu?

   TOTP

   Time-based One-Time Password. Hasło jednorazowe zależne od czasu.

8. Zaprojektuj bezpieczne przypisanie tożsamości z dwóch dostawców. Wyjaśnij znaczenie pary $(\mathrm{iss},\mathrm{sub})$ i ryzyko automatycznego łączenia kont według samego adresu e-mail.

Wynik: diagram, tabela „kontrola → zagrożenie” i rozdzielenie trzech własności: niepodrabialności podpisu, świeżości transakcji oraz poprawnego przypisania konta. Przy każdym wymaganiu podaj źródło normatywne lub zaznacz, że jest to polityka wybranej aplikacji.

Od zadania do lektury publikacji

Wybierz jeden kierunek, zamiast próbować jednocześnie opanować wszystkie pogłębienia.

Możliwe rozwinięcie do pracy magisterskiej lub dalszych badań ustalamy indywidualnie. Podstawą może być odtworzenie opublikowanej konstrukcji z bibliografii, odtworzenie jednego dowodu i rzetelny test implementacji. Wyniki z nieopublikowanych projektów nie są częścią tego zestawu.

Literatura: odnośniki do źródeł i oryginalnych twierdzeń znajdują się przy rozdziałach wykładu. Laboratoria przekładają wybrane rachunki na wykonywalne testy.