Kryptografia — listy nr 1, nr 2, nr 3, nr 4 i nr 5

Zasady zaliczenia ćwiczeń

Poniższe zasady określają sposób pracy na ćwiczeniach oraz sposób wyliczania oceny z ćwiczeń.

Demonstrator WASM - klasyczny Schnorr

Punkt odniesienia: klasyczny Schnorr w zapisie addytywnym na krzywych eliptycznych. Ta karta pokazuje przebieg poprawnego protokołu, z którym należy porównywać kolejne konstrukcje.

Demonstrator BigInt - klasyczny Schnorr w Zp*

Ten sam punkt odniesienia w grupie multiplikatywnej modulo $p$. Tu również obowiązuje wzór $A=g^a$, $X=g^x$, $s=[x+ac] mod q$ i test $g^s=X{A}^c$.

1. Wprowadzenie do listy

We wszystkich zadaniach zakładamy, że $G=⟨g⟩$ jest grupą cykliczną rzędu $q$, a sekret Dowodzącego ma postać $a\in {\mathbb{Z}}_q*$. Klucz publiczny ma postać:

2. Zadanie 1 — analiza pierwszego schematu

1. Sprawdź, czy uczciwy Dowodzący, znający $a$, zawsze przechodzi weryfikację.
2. Oceń, czy atakujący nieznający $a$ może się skutecznie podszyć.
3. Jeśli schemat jest niebezpieczny, podaj jawny sposób skonstruowania akceptowalnej transkrypcji.
4. Wyjaśnij, czy atakujący musi znać logarytm dyskretny klucza publicznego $A$.

3. Zadanie 2 — analiza drugiego schematu

1. Udowodnij poprawność działania dla uczciwego Dowodzącego.
2. Zbadaj, czy odpowiedź ma właściwą postać z punktu widzenia bezpieczeństwa identyfikacji.
3. Spróbuj zaprojektować atakującego, który po poznaniu $c$ dobiera $X$ lub $s$ tak, aby przejść weryfikację.
4. Oceń, czy wyzwanie $c$ rzeczywiście utrudnia podszycie się.

4. Zadanie 3 — analiza trzeciego schematu

1. Wykaż poprawność dla uczciwego Dowodzącego.
2. Zauważ, że w warunku akceptacji nie występuje bezpośrednio ani $A$, ani $X$. Czy to jest sygnał ostrzegawczy? Uzasadnij.
3. Sprawdź, czy osoba nieznająca $a$ może dobrać $s$ i $W$ tak, by przejść test.
4. Jeśli tak, zapisz pełny atak krok po kroku.
5. Wyjaśnij, czy $W$ pełni tu rolę dowodu wiedzy, czy raczej dodatkowej zmiennej łatwej do sfałszowania.

5. Zadanie 4 — analiza czwartego schematu

1. Udowodnij poprawność schematu dla uczciwego Dowodzącego.
2. Zastanów się, czy równanie weryfikacyjne można spełnić bez znajomości $a$.
3. Czy atakujący może najpierw wybrać dowolne $s$, a potem wyznaczyć $W$ tak, aby przejść weryfikację?
4. Jeśli tak, pokaż pełny atak i oceń, czy schemat rzeczywiście wiąże odpowiedź z sekretem.
5. Porównaj ten schemat z poprzednim — czy problem jest podobny, czy inny?

6. Zadanie 5 — analiza piątego schematu

1. Rozwiń algebraicznie obie strony warunku akceptacji i sprawdź poprawność.
2. Ustal, czy zależność weryfikacyjna naprawdę wymusza znajomość sekretu $a$.
3. Sprawdź, czy atakujący może arbitralnie wybrać część odpowiedzi, a resztę dopasować.
4. Oceń, czy większa złożoność wzorów poprawia bezpieczeństwo, czy tylko zaciemnia obraz.
5. Sformułuj ogólną intuicję: dlaczego bardziej skomplikowane równanie nie musi oznaczać bezpieczniejszego protokołu.

7. Zadanie porównawcze — lista nr 1 jako całość

Dla wszystkich pięciu schematów sporządź tabelę porównawczą i uzupełnij ją po przeprowadzeniu analizy.

1. Wskaż, które schematy są trywialnie fałszowalne.
2. Wskaż, w których przypadkach odpowiedź można skonstruować bez znajomości sekretu.
3. Sformułuj jedną wspólną zasadę projektowania poprawnych schematów identyfikacji typu sigma.

8. Odniesienie do schematu Schnorra

Punkt odniesienia dla całej listy: klasyczny schemat identyfikacji Schnorra.

1. Wyjaśnij, czym strukturalnie Schnorr różni się od analizowanych konstrukcji.
2. Pokaż, dlaczego odpowiedź w Schnorrze nie daje się łatwo sfałszować po poznaniu wyzwania.
3. Wskaż, które z analizowanych schematów przypominają Schnorra tylko powierzchownie.
4. Zaproponuj poprawkę do jednego z błędnych schematów tak, aby zbliżyć go do poprawnego protokołu identyfikacji.

Lista nr 2 — podpisy

Druga lista dotyczy schematów podpisu inspirowanych konstrukcjami schnorrowymi. W każdym zadaniu należy ocenić poprawność algebraiczną, poziom bezpieczeństwa oraz wskazać możliwie najsilniejszy atak, jeżeli schemat nie jest bezpieczny.

Lista nr 2 — punkt odniesienia: poprawny podpis Schnorra

Gdy w tej liście odwołujemy się do standardowego podpisu Schnorra, mamy na myśli wariant, w którym wyzwanie jest związane zarówno z wiadomością, jak i z zobowiązaniem $R$.

1. Traktuj ten wariant jako kryptograficzny punkt odniesienia dla całej listy nr 2.
2. Przy analizie kolejnych zadań zawsze sprawdzaj, czy zachowano poprawne związanie wiadomości z $R$ przez $H(m,R)$.
3. Zwracaj uwagę, czy równanie weryfikacyjne rzeczywiście wiąże podpis z kluczem publicznym $A$.

Demonstrator WASM — poprawny podpis Schnorra

Demonstrator podpisu Schnorra na krzywej eliptycznej w zapisie addytywnym. Punkt odniesienia ma postać $A=aQ$, $R=rQ$, $h=H(m,R)$, $s=[r+ah] mod q$ oraz warunek $sQ=R+hA$.

Demonstrator BigInt — poprawny podpis Schnorra w ${\mathbb{Z}}_p*$

Ta wersja działa w grupie multiplikatywnej modulo $p$. Podpis ma postać $A=g^a$, $R=g^r$, $h=H(m,R) mod q$, $s=[r+ah] mod q$ i test $g^s=R{A}^h mod p$.

Lista nr 2 — zadanie 1: wariant z $h=H\left(m\right)$

1. Wykaż poprawność schematu dla uczciwego Podpisującego.
2. Porównaj ten wariant z poprawnym podpisem Schnorra z punktu odniesienia i oceń, co zmienia pominięcie $R$ w wejściu funkcji skrótu.
3. Zbadaj, czy ten wariant zachowuje bezpieczeństwo podpisu Schnorra, czy też otwiera drogę do fałszerstwa.
4. Wskaż rolę losowej wartości $r$ i wyjaśnij, dlaczego nie wolno jej powtarzać.

Lista nr 2 — zadanie 2: $h=m+R$

1. Najpierw oceń, czy zapis $m+R$ jest dobrze określony bez dodatkowego kodowania.
2. Jeśli przyjmiesz naturalne kodowanie do ${\mathbb{Z}}_q$, zbadaj poprawność i bezpieczeństwo schematu.
3. Sprawdź, czy podpis można sfałszować przez dobranie $R$ lub $s$ po ustaleniu wiadomości.
4. Porównaj ten pomysł z poprawnym użyciem $H(m,R)$ w podpisie Schnorra.

Lista nr 2 — zadanie 3: $h=mR$

1. Wyjaśnij, w jakiej domenie iloczyn $mR$ miałby być liczony.
2. Sprawdź, czy takie związanie wiadomości z $R$ daje odporność na fałszerstwo, czy tylko pozór związania.
3. Zbadaj, czy można dobrać podpis dla wybranej wiadomości bez znajomości sekretu $a$.
4. Porównaj ten schemat z zadaniem 2: czy problem jest zasadniczo ten sam, czy inny?

Lista nr 2 — zadanie 4: $h=m\oplus R$ (XOR)

1. Załóż, że $\oplus$ oznacza bitowy XOR. Oceń, jakie kodowanie wiadomości $m$ i zobowiązania $R$ byłoby potrzebne, aby taki zapis był w ogóle dobrze określony.
2. Wyjaśnij, czy wynik XOR można potraktować jako sensowny odpowiednik wyzwania $h$ używanego w podpisie Schnorra.
3. Zbadaj, czy przy naturalnych interpretacjach XOR i mapowania do ${\mathbb{Z}}_q$ możliwe jest skuteczne fałszerstwo podpisu.
4. Sformułuj ogólny wniosek: dlaczego prosta operacja XOR na $m$ i $R$ nie zastępuje bezpiecznej funkcji skrótu $H(m,R)$.

Lista nr 2 — zadanie 5: podpis z dodatkową wartością $X$

1. Wykaż poprawność równania weryfikacyjnego dla uczciwego Podpisującego.
2. Zauważ, że weryfikacja nie korzysta bezpośrednio z klucza publicznego $A$. Oceń znaczenie tego faktu.
3. Sprawdź, czy atakujący może dobrać $s$ i $X$ tak, by przejść weryfikację bez znajomości $a$.
4. Wyjaśnij, czy wartość $R$ ma tu realny wpływ na bezpieczeństwo podpisu, czy tylko wpływa na obliczenie $h$.

Lista nr 2 — zadanie 6: podpis z hashem zależnym od $X$

1. Sprawdź poprawność schematu dla uczciwego Podpisującego.
2. Oceń, czy dodanie $X$ do wejścia funkcji skrótu naprawia zasadniczy problem z poprzedniego schematu.
3. Zbadaj, czy atakujący może dobrać podpis po wyborze $R$, $X$ i $s$ bez znajomości sekretu.
4. Porównaj ten schemat z zadaniem 5 i wskaż, czy zmiana jest tylko kosmetyczna, czy rzeczywiście istotna.

Lista nr 2 — tabela porównawcza

Po przeanalizowaniu wszystkich schematów uzupełnij tabelę porównawczą dla listy nr 2.

1. Wskaż, które schematy zachowują zasadniczą strukturę podpisu Schnorra, a które jedynie powierzchownie go przypominają.
2. Wskaż, w których przypadkach problemem jest zły sposób definiowania $h$, a w których brak związania podpisu z kluczem publicznym.
3. Sformułuj jedną wspólną zasadę projektowania poprawnych podpisów Schnorra i schematów schnorrowych.

Lista nr 3 — podpisy BLS

Trzecia lista dotyczy podpisów BLS. Celem jest zrozumienie, dlaczego w tym schemacie poprawna definicja funkcji $H$ jako bezpiecznej funkcji hash-to-curve jest absolutnie kluczowa.

Lista nr 3 — punkt odniesienia: poprawny podpis BLS

W poprawnym podpisie BLS wiadomość jest mapowana do punktu grupy przez bezpieczną funkcję hash-to-curve, a nie przez prostą publiczną formułę algebraiczną.

1. Traktuj ten wariant jako kryptograficzny punkt odniesienia dla całej listy nr 3.
2. Zwracaj uwagę, czy funkcja $H$ naprawdę zachowuje się jak bezpieczne mapowanie wiadomości do punktu grupy.
3. W każdym kolejnym zadaniu sprawdzaj, czy z podpisu na jednej wiadomości można wyprowadzić podpis na innej wiadomości bez znajomości sekretu $a$.

Demonstrator WASM — poprawny podpis BLS

Demonstrator pokazuje klasyczny wariant BLS z hashowaniem wiadomości do $G_1$ i kluczem publicznym w $G_2$. Podpis ma postać $M=H\left(m\right)$, $A=aQ$, $\sigma =aM$, a weryfikacja sprawdza warunek $e(\sigma ,Q)=e(M,A)$.

Lista nr 3 — zadanie 1: stała funkcja $H\left(m\right)=P_0$

1. Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
2. Wyjaśnij, dlaczego podpis na jednej wiadomości staje się automatycznie podpisem na każdej innej wiadomości.
3. Opisz możliwie najsilniejszy atak fałszerstwa na ten schemat.
4. Porównaj ten błąd z sytuacją, w której funkcja skrótu w podpisie Schnorra nie zależy w istotny sposób od wiadomości.

Lista nr 3 — zadanie 2: liniowa funkcja $H\left(m\right)=\mathrm{enc}\left(m\right)P$

1. Wykaż poprawność schematu dla uczciwego Podpisującego.
2. Załóż, że atakujący ma podpis ${\sigma }_1$ na wiadomość $m_1$ z ${\mu }_1\ne 0$. Pokaż, jak skonstruować podpis na wiadomość $m_2$ przez odpowiednie przeskalowanie ${\sigma }_1$.
3. Wyjaśnij, dlaczego publiczna liniowość funkcji $H$ jest tu wadą.
4. Oceń, co dzieje się w przypadku $\mathrm{enc}\left(m\right)=0$ i czy to dodatkowo pogarsza bezpieczeństwo.

Lista nr 3 — zadanie 3: zbyt krótki skrót $H\left(m\right)=\tau \left(m\right)P$

1. Wyjaśnij, dlaczego tak zdefiniowana funkcja $H$ prowadzi do łatwych kolizji wiadomości.
2. Pokaż, jak wykorzystać znalezienie dwóch wiadomości $m_1\ne m_2$ z $\tau \left(m_1\right)=\tau \left(m_2\right)$ do sfałszowania podpisu.
3. Oceń, jak rośnie skuteczność ataku wraz ze skracaniem wartości $\tau$.
4. Porównaj ten błąd z poprawnym wymaganiem, aby $H$ zachowywała się jak bezpieczna funkcja hash-to-curve o dużej odporności na kolizje.

Lista nr 3 — zadanie 4: homomorficzna funkcja $H$

1. Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
2. Załóż, że atakujący zna podpisy ${\sigma }_1$ pod $m_1$ oraz ${\sigma }_2$ pod $m_2$. Pokaż, że suma ${\sigma }_1+{\sigma }_2$ jest poprawnym podpisem pod wiadomością $m_1·m_2$.
3. Wyjaśnij, dlaczego publiczna homomorficzność funkcji $H$ umożliwia składanie podpisów bez znajomości sekretu $a$.
4. Porównaj ten atak z zadaniem 2: wskaż, co jest wspólnym źródłem słabości obu konstrukcji.

Lista nr 3 — zadanie 5: łatwy logarytm dyskretny w obrazie $H$

1. Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
2. Załóż, że atakujący zna jeden poprawny podpis ${\sigma }_1$ pod wiadomością $m_1$ i potrafi obliczyć $b_1$ takie, że $H\left(m_1\right)=b_{1}P$, przy czym $b_1\ne 0$. Pokaż, jak odzyskać punkt $aP$.
3. Dla dowolnej nowej wiadomości $m_2$ oblicz $b_2$ z warunku $H\left(m_2\right)=b_{2}P$ i skonstruuj poprawny podpis pod $m_2$ bez znajomości sekretu $a$.
4. Wyjaśnij, dlaczego nie trzeba łamać problemu logarytmu dyskretnego w całej grupie $G_1$; wystarczy, że obraz funkcji $H$ wpada w słaby podzbiór punktów.

Lista nr 3 — tabela porównawcza

Po przeanalizowaniu wszystkich schematów BLS uzupełnij tabelę porównawczą dla listy nr 3.

1. Wskaż, które schematy są poprawne algebraicznie, ale całkowicie nieodporne na fałszerstwo.
2. Odróżnij cztery typy błędów: funkcję stałą, publiczną liniowość lub homomorficzność funkcji $H$, zbyt małą odporność na kolizje oraz łatwy logarytm dyskretny w obrazie funkcji $H$.
3. Sformułuj jedną wspólną zasadę: jakie własności musi mieć funkcja hash-to-curve, aby podpis BLS mógł być bezpieczny.

Lista nr 4 — podpisy RSA Full Domain Hash

Czwarta lista dotyczy podpisów RSA-FDH. Celem jest zrozumienie, że w tym schemacie funkcja $H$ nie może zachowywać prostych zależności algebraicznych między wiadomościami, ponieważ prowadzi to do fałszerstw.

Lista nr 4 — punkt odniesienia: poprawny podpis RSA-FDH

W poprawnym podpisie RSA-FDH najpierw haszujemy wiadomość do pełnej dziedziny modulo $N$, a dopiero potem wykonujemy operację RSA. To właśnie funkcja $H$ ma zniszczyć proste zależności algebraiczne między wiadomościami.

1. Traktuj ten wariant jako punkt odniesienia dla całej listy nr 4.
2. Zwracaj uwagę, czy funkcja $H$ rzeczywiście usuwa przewidywalne zależności algebraiczne między wiadomościami.
3. W kolejnych zadaniach sprawdzaj, czy z jednego lub z dwóch podpisów można skonstruować podpis pod nową wiadomością bez znajomości $d$.

Lista nr 4 — zadanie 1: brak funkcji haszującej

1. Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
2. Załóż, że atakujący zna podpisy ${\sigma }_1$ pod wiadomością $m_1$ oraz ${\sigma }_2$ pod wiadomością $m_2$. Pokaż, że iloczyn ${\sigma }_1{\sigma }_2$ jest poprawnym podpisem pod wiadomością $m_3$ spełniającą $\mathrm{enc}\left(m_3\right)\equiv \mathrm{enc}\left(m_1\right)\mathrm{enc}\left(m_2\right)\left(\mathrm{mod}N\right)$.
3. Wyjaśnij, dlaczego brak funkcji $H$ pozostawia publiczną strukturę multiplikatywną wiadomości i umożliwia fałszerstwo.
4. Porównaj ten błąd z poprawnym podpisem RSA-FDH.

Lista nr 4 — zadanie 2: słaba funkcja $H\left(m\right)={\mu }^2$

1. Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
2. Załóż, że atakujący zna podpisy pod wiadomościami $m_1$ i $m_2$. Pokaż, że iloczyn tych podpisów jest poprawnym podpisem pod wiadomością $m_3$ taką, że $\mathrm{enc}\left(m_3\right)\equiv \mathrm{enc}\left(m_1\right)\mathrm{enc}\left(m_2\right)\left(\mathrm{mod}N\right)$.
3. Wyjaśnij, dlaczego publiczna transformacja $\mu \mapsto {\mu }^2$ nie usuwa struktury multiplikatywnej, tylko ją zachowuje.
4. Porównaj ten błąd z zadaniem 1: wskaż, dlaczego taka funkcja nadal nie spełnia roli bezpiecznego haszowania.

Lista nr 4 — zadanie 3: słaba funkcja $H\left(m\right)=g^{\mu }$

1. Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
2. Przyjmij, że przestrzeń wiadomości jest utożsamiona z liczbami całkowitymi z ustalonego zakresu. Pokaż, że z podpisów pod wiadomościami $m_1$ oraz $m_2$ można skonstruować podpis pod wiadomością $m_3$ spełniającą $\mathrm{enc}\left(m_3\right)=\mathrm{enc}\left(m_1\right)+\mathrm{enc}\left(m_2\right)$.
3. Wyjaśnij, dlaczego homomorfizm w wykładniku, czyli zależność $g^{\mu +\nu }=g^{\mu }·g^{\nu }$ modulo $N$, wystarcza do fałszerstwa.
4. Porównaj to zadanie z zadaniem 2: wskaż, że w obu przypadkach funkcja $H$ zachowuje publiczną zależność algebraiczną między wiadomościami.

Lista nr 4 — tabela porównawcza

Po przeanalizowaniu wszystkich schematów RSA uzupełnij tabelę porównawczą dla listy nr 4.

1. Wskaż, które konstrukcje są poprawne algebraicznie, ale nieodporne na fałszerstwo.
2. Odróżnij trzy źródła słabości: całkowity brak haszowania, zachowanie struktury multiplikatywnej oraz zachowanie struktury addytywnej w wykładniku.
3. Sformułuj jedną wspólną zasadę: jakie własności powinna mieć funkcja $H$ w podpisie RSA-FDH, aby nie dało się z podpisów wyprowadzać kolejnych podpisów metodą czysto algebraiczną.

Lista nr 5 — anonimowość i podpisy pierścieniowe Herranza-Sáeza

Piąta lista dotyczy anonimowości w podpisach pierścieniowych. Punktem odniesienia jest tu schemat Javiera Herranza i Germána Sáeza oparty na podpisie Schnorra.

Lista nr 5 — punkt odniesienia: podpis pierścieniowy Herranza-Sáeza

W poprawnym wariancie każdy członek pierścienia wnosi własny składnik $R$, a lokalne wyzwania mają postać $h=H(m,R)$. To właśnie ta struktura pozwala połączyć poprawność, anonimowość i bezpieczeństwo w modelu losowej wyroczni.

1. Traktuj ten wariant jako punkt odniesienia dla całej listy nr 5.
2. Zwracaj uwagę, które elementy podpisu są losowane przez rzeczywistego Podpisującego, a które są wyznaczane tak, aby zamknąć równanie weryfikacyjne.
3. W kolejnych zadaniach odróżniaj poprawność, anonimowość i odporność na fałszerstwo: są to trzy różne własności.

Lista nr 5 — zadanie 1: poprawność i anonimowość bezwarunkowa

1. Wykaż poprawność algebraiczną schematu.
2. Pokaż, że dla ustalonego poprawnego podpisu każdy członek pierścienia mógł go wygenerować z takim samym prawdopodobieństwem.
3. Wyjaśnij, dlaczego z tego wynika anonimowość bezwarunkowa w sensie pracy Herranza i Sáeza.
4. Porównaj tę własność z klasycznym podpisem Schnorra, który w ogóle nie ukrywa tożsamości Podpisującego.

Lista nr 5 — zadanie 2: deterministyczne składniki dla niepodpisujących

1. Wyjaśnij, dlaczego poprawność algebraiczna podpisu nadal może być zachowana.
2. Pokaż, że Weryfikator może samodzielnie odtworzyć wszystkie wartości $a_i$ i $R_i$ dla $i\ne s$.
3. Wyjaśnij, dlaczego jedyny indeks, dla którego publikowane $R_i$ nie zgadza się z wartością przewidzianą przez funkcję $F$, wskazuje rzeczywistego Podpisującego.
4. Wskaż, dlaczego publiczna deterministyczność składników niepodpisujących całkowicie niszczy anonimowość pierścienia.

Lista nr 5 — zadanie 3: pseudolosowość sterowana ziarnem znanym podpisującemu

1. Wyjaśnij, dlaczego przed ujawnieniem ziarna wariant może wyglądać na anonimowy dla obserwatora zewnętrznego.
2. Pokaż, że po ujawnieniu $\rho$ każdy może sprawdzić równania $R_i=g^{\mathrm{PRG}(\rho ,i)}$ dla wszystkich $i\ne s$.
3. Wyjaśnij, dlaczego brak takiego świadectwa dla jednego indeksu pozwala rzeczywistemu Podpisującemu przekonująco ujawnić własną tożsamość.
4. Oceń, czy taki wariant zachowuje zaprzeczalność i anonimowość w sensie praktycznym.

Lista nr 5 — zadanie 4: niebezpieczne uproszczenie z jednym globalnym wyzwaniem

1. Pokaż, że atakujący może sfałszować podpis bez znajomości żadnego klucza prywatnego: wybiera losowe $\sigma$, losowe $R_1,\dots ,R_{n-1}$ i wyznacza ostatnią wartość $R_n$ z równania weryfikacyjnego.
2. Wyprowadź jawny wzór na $R_n$.
3. Wyjaśnij, dlaczego lokalne wyzwania $h_i=H(m,R_i)$ są istotne dla bezpieczeństwa konstrukcji.
4. Porównaj tę słabość z zadaniami z listy nr 2 i listy nr 4, w których błędnie zdefiniowana funkcja haszująca również otwierała drogę do czysto algebraicznych fałszerstw.

Lista nr 5 — zadanie 5: małe wykładniki dla niepodpisujących

1. Wyjaśnij, dlaczego poprawność równania weryfikacyjnego nadal jest zachowana.
2. Pokaż, że Weryfikator może dla każdego $R_i$ sprawdzić, czy istnieje mały wykładnik $u<2^t$ taki, że $R_i=g^u$.
3. Wyjaśnij, dlaczego z dużym prawdopodobieństwem wszystkie indeksy $i\ne s$ zostaną rozpoznane jako „niepodpisujący”, a rzeczywisty Podpisujący pozostanie jedynym indeksem bez małego logarytmu.
4. Oceń, jak zmienia się skuteczność ataku wraz ze wzrostem parametru $t$.

Lista nr 5 — zadanie 6: publicznie rozpoznawalny bias generatora

1. Wyjaśnij, dlaczego poprawność podpisu nadal może być zachowana mimo tego błędu implementacyjnego.
2. Pokaż, że dla wszystkich $i\ne s$ zachodzi $P\left(R_i\right)=\mathrm{true}$, natomiast dla $R_s$ prawdopodobieństwo spełnienia tego warunku wynosi w przybliżeniu $2^{-16}$.
3. Wyjaśnij, dlaczego Weryfikator może z bardzo dużym prawdopodobieństwem wskazać rzeczywistego Podpisującego jako jedyny indeks niespełniający predykatu $P$.
4. Porównaj ten błąd z zadaniem 5: wskaż różnicę między wyciekiem przez mały logarytm dyskretny a wyciekiem przez jawnie obserwowalny wzorzec w zakodowaniu punktu.

Lista nr 5 — zadanie 7: dlaczego składniki $R_i$ muszą być nierozróżnialne

1. Wyjaśnij, dlaczego dla zachowania anonimowości rozkłady wszystkich wartości $R_i$ muszą być nierozróżnialne z punktu widzenia Weryfikatora.
2. Pokaż, że jeśli dla niepodpisujących wartości $R_i$ są odtwarzalne z krótkiego opisu $\tau$, a dla rzeczywistego Podpisującego nie są, to sam fakt tej odróżnialności ujawnia indeks $s$.
3. Wyjaśnij, dlaczego z tego wynika, że podpis musi zawierać po jednym pełnym, losowo wyglądającym składniku dla każdego członka pierścienia, a więc jego długość jest proporcjonalna do liczby wszystkich członków pierścienia.
4. Porównaj tę obserwację z zadaniami 2, 3, 5 i 6: wskaż, że we wszystkich tych przypadkach anonimowość przegrywa dokładnie wtedy, gdy składnik rzeczywistego Podpisującego przestaje być nierozróżnialny od pozostałych.

Lista nr 5 — tabela porównawcza

Po przeanalizowaniu listy nr 5 uzupełnij tabelę porównawczą dla podpisu pierścieniowego Herranza-Sáeza i opisanych wariantów.

1. Odróżnij trzy poziomy analizy: poprawność algebraiczną, anonimowość oraz odporność na fałszerstwo.
2. Wyjaśnij, dlaczego w podpisach pierścieniowych sam fakt poprawności równania weryfikacyjnego nie wystarcza ani do anonimowości, ani do bezpieczeństwa.
3. Sformułuj jedną wspólną zasadę: jakie elementy konstrukcji Schnorra trzeba zachować, aby uzyskać poprawny i anonimowy podpis pierścieniowy.