Kryptografia: listy zadań

Jak zacząć i jak czytać schematy

W tym kursie badamy, co odbiorca może sprawdzić bez poznania sekretu drugiej strony. Najpierw poznajesz działającą konstrukcję, następnie zmieniasz jeden jej element i szukasz konsekwencji. Wariant oznaczony jako zadanie do analizy nie jest rekomendacją do użycia w systemie.

1. Identyfikacja, lista 1. Dowodzący przekonuje weryfikatora w bieżącej rozmowie, że zna sekret związany z ustalonym kluczem publicznym.
2. Podpisy, listy 2–4. Dowód wiążemy z wiadomością. Podpis może sprawdzić także ktoś, kto nie uczestniczył w jego tworzeniu.
3. Anonimowość, listy 5–6. Sprawdzamy uprawnienie jednego członka zbioru, lecz nie ujawniamy, którego. Podpis i interaktywny dowód to nadal różne obiekty.
4. Uzgadnianie klucza, listy 7 i 9. Łączymy zgodność klucza z uwierzytelnieniem partnera i analizujemy ujawnienie sekretów. Lista 8 pozwala osobno policzyć koszt tych mechanizmów.
5. Szyfrowanie, lista 10. Badamy poufność wiadomości oraz różnicę między ukryciem treści a ochroną przed jej modyfikacją.

Uczestnicy i widoczne informacje

Dowodzący zna sekret; weryfikator sprawdza komunikaty; przeciwnik działa z uprawnieniami podanymi w zadaniu. Transkrypt jest zapisem publicznej wymiany, nie zrzutem wszystkich zmiennych programu. Sekret długoterminowy służy wielu wykonaniom. Losowość efemeryczna jest świeża dla konkretnego wykonania i nie powinna być ponownie używana.

Klucz publiczny sam nie potwierdza nazwiska. Gdy mówimy o identyfikacji Alicji, zakładamy, że weryfikator ma wiarygodne powiązanie jej tożsamości z kluczem. Certyfikat jest jednym ze sposobów ustanowienia takiego powiązania.

Dwa rodzaje wartości, dwa różne moduły

W listach opartych na logarytmie dyskretnym zakładamy grupy rzędu pierwszego i niezerowe skalarne klucze prywatne. Parametry RSA definiujemy osobno w liście 4. Te założenia określają, gdzie wolno obliczać odwrotności i z jakiej dziedziny pochodzą klucze.

W zapisie $G=\langle g\rangle$ generator $g$ pozwala uzyskać wszystkie $q$ elementów grupy. Skalary są liczbami z $\mathbb Z_q$; dodajemy je i mnożymy modulo $q$. Gwiazdka w $\mathbb Z_q^*$ wyklucza zero. Dla pierwszego $q$ każda niezerowa wartość ma odwrotność modularną.

Jeśli grupę realizujemy jako podgrupę modulo liczby pierwszej $p$, elementy grupy mnożymy modulo $p$, a wykładniki liczymy modulo $q$. Dzielenie w grupie oznacza mnożenie przez odwrotność, nie dzielenie zmiennoprzecinkowe. Na krzywej eliptycznej tę samą abstrakcyjną operację zapisujemy addytywnie: $g^a\ \longleftrightarrow\ a\cdot Q$. Nie potęgujemy współrzędnych punktu.

Funkcja haszująca: najpierw sprawdź typ wyniku

• Hasz do skalaru: $\H:\{0,1\}^*\to\mathbb Z_q$. Wynik służy jako wyzwanie lub wykładnik, np. $c=\H(m,R)$ w podpisie Schnorra.
• Hasz do punktu: $\H_{G_1}:\{0,1\}^*\to G_1$. Indeks wskazuje grupę wyniku. W poprawnym BLS liczymy $M=\H_{G_1}(m)$ i $\sigma=a\cdot M$. To nie jest skalar, przez który można podzielić podpis.
• Inne typy wyjść: $\mathsf{KDF}$ wyprowadza klucze bitowe; $\mathcal D_\ell$ zwraca maskę długości $\ell$ bitów; $F_{\rm FDH}$ w liście RSA mapuje do $\mathbb Z_N^*$. Żadna z tych funkcji nie oznacza hasza do $\mathbb Z_q$.
• Wadliwy zamiennik: $\mathcal{H}_{\mathrm{bad}}$ oznacza funkcję celowo zdefiniowaną źle w danym zadaniu. Jej definicja jest lokalna. Nie nadajemy jej nazwy $\H_{G_1}$, nawet jeśli formalnie zwraca punkt tej grupy.

Punkt w poprawnej grupie to za mało. Bezpieczne haszowanie do grupy nie udostępnia łatwo obliczalnego logarytmu wyniku względem generatora. Funkcja jest publiczna i deterministyczna; nie oznacza to publicznej znajomości takiego logarytmu. Kontrprzykłady z listy 3 badają właśnie różnicę między poprawnym typem a wymaganymi własnościami bezpieczeństwa.

Argumenty haszy zapisujemy skrótowo jako wiadomości, punkty lub krotki. Rzeczywiste wejścia to ich jednoznaczne kodowania bajtowe, z rozdzieleniem domen dla protokołów i ról. W demonstratorze BLS za haszowanie do $G_1$ odpowiada mcl.hashAndMapToG1; mcl.hashToFr ma wynik skalarny. Nie są zamienne. Notacja nie stanowi deklaracji zgodności bajtowej demonstratora ze standardowym profilem BLS ani konkretnym zestawem RFC 9380.

Gdy angielski wykład rozpatruje ogólną grupę $G$, zapis $\H_G$ wskazuje tę właśnie grupę. Analogicznie $\H_{G_2}$ zwraca punkt $G_2$. Zachowujemy typy grup, nie zmieniamy ich tylko dla ujednolicenia liter. Źródła: RFC 9380: hash-to-curve; MCL WebAssembly.

Jak napisać rozwiązanie

1. Wypisz dane. Kto zna sekret, kto wybiera losowość, kiedy przychodzi wyzwanie i jakie zapytania może wykonać przeciwnik?
2. Sprawdź typy i poprawność. Podstaw uczciwe obliczenia do testu. Przy każdej odwrotności wyklucz zero; przy XOR uzgodnij długości ciągów bitów.
3. Zapisz atak jako algorytm. Wyprowadź jego wynik wyłącznie z dostępnych informacji, a potem sprawdź go tym samym równaniem co uczciwy odbiorca.
4. Podaj zakres wniosku. Jeden udany przykład nie dowodzi bezpieczeństwa, a brak znalezionego ataku nie jest dowodem jego braku. Osobno oceniaj poprawność, podszycie, fałszerstwo, anonimowość i poufność.

Wzory opisują modele dydaktyczne. Demonstratory pokazują ich rachunek; ujawniają sekrety na ekranie, aby można było go prześledzić. Nie służą do przechowywania rzeczywistych kluczy ani zabezpieczania danych.

Zasady zaliczenia ćwiczeń

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

Lista nr 1 — wprowadzenie

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

Lista nr 1 — punkt odniesienia: klasyczny Schnorr

Najpierw ustalamy publiczne parametry grupy i klucz publiczny. Sekret jest niezerowy. W tym punkcie odniesienia i obu demonstratorach Schnorra losujemy niezależnie wartość jednorazową oraz wyzwanie z całego ciała skalarów, z dopuszczeniem zera. Niektóre warianty zadań poniżej celowo zawężają ten zbiór; uwzględnij to, gdy liczysz dokładne prawdopodobieństwa.

Trzy wiadomości mają różne role: zobowiązanie utrwala wybór dowodzącego, nieprzewidywalne wyzwanie uniemożliwia przygotowanie odpowiedzi z góry, a odpowiedź łączy to wyzwanie z sekretem. Weryfikator zna klucz publiczny, lecz nie otrzymuje ani sekretu, ani wartości jednorazowej. Sam zapis równania nie wystarczy, jeżeli zmienimy tę kolejność.

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.

Losowość protokołu: wyciek, ustawianie i reset

Wartość $x$ z poprzedniego schematu jest sekretem efemerycznym: służy jednemu wykonaniu. Sekret $a$ jest długoterminowy. Przejęcie tej pierwszej wartości może jednak ujawnić także tę drugą. Nazwy ephemeral leakage i randomness leakage odnoszą się tutaj do wycieku losowości wykonania; setting i injection opisują możliwość jej narzucenia. W katalogu publikacji grupujemy te scenariusze pod hasłem randomness leakage and setup.

• Wyciek: urządzenie losuje $x$, a przeciwnik poznaje tę wartość przez dopuszczony w modelu interfejs ujawnienia.
• Ustawianie lub wstrzyknięcie: przeciwnik dostarcza do urządzenia wybraną przez siebie, dozwoloną wartość $x$ przed jej użyciem. Chodzi o losowość wewnętrzną, nie o wybór publicznej wiadomości do podpisania.
• Reset lub ponowne użycie: przywrócenie stanu może spowodować powtórzenie tej samej losowości. Przeciwnik nie musi znać jej wartości. Reset nie oznacza automatycznie ustawienia zera ani żadnej znanej stałej.

Najpierw sprawdź, czy losowość rzeczywiście się powtarza. Na przykład deterministyczne wyprowadzanie jej z klucza i wiadomości może po resecie dać różne wartości dla różnych wiadomości. Samo ponowne uruchomienie urządzenia nie dowodzi ponownego użycia tego samego zobowiązania.

Znana losowość: wystarcza jedna odpowiedź

Klasyczny Schnorr zwraca skalar $s=x+a·c$. Wszystkie poniższe rachunki na skalarach wykonujemy modulo $q$. Jeśli przeciwnik zna $x$ i otrzymał odpowiedź na niezerowe wyzwanie, oblicza:

Nie ma znaczenia dla tego rachunku, czy przeciwnik poznał losowość, czy wcześniej sam ją ustawił. Dla $c=0$ odpowiedź nie zawiera składnika z kluczem, więc ten wzór nie ma zastosowania.

Powtórzona, nieznana losowość: odejmujemy odpowiedzi

Dwa akceptowane przebiegi z tym samym kluczem i zobowiązaniem, lecz różnymi wyzwaniami, dają:

Odejmując, usuwamy nieznane $x$. Dopiero niezerowa różnica wyzwań pozwala wykonać odwrócenie:

Przykład: użyjmy wcześniejszych parametrów $q=11$, $a=3$ i $x=4$. Wyzwania $c=2$ oraz $c^{\prime }=7$ dają odpowiedzi 10 i 3. Przy znanej losowości liczymy $(10-4)·2^{-1}=3$. Przy samej wiedzy o powtórzeniu liczymy $(10-3)·{(2-7)}^{-1}=3$. Oba wyniki są liczone modulo 11, ale w drugim rachunku nie używamy wartości 4.

W podpisie Schnorra wyzwanie wynika z haszowania. Inna wiadomość zwykle daje inne wyzwanie, lecz warunkiem jest różnica wyzwań modulo $q$, a nie sama różnica wiadomości. Jeśli losowość nie jest wspólna, po odjęciu pozostaje dodatkowa niewiadoma i powyższy wzór nie odzyskuje klucza.

Ta sama algebra w ataku i w dowodzie

W dowodzie wiedzy lub redukcji bezpieczeństwa parę akceptowanych przebiegów może uzyskać ekstraktor, cofając wykonanie przeciwnika (rewinding) albo stosując lemat o rozwidleniu (forking lemma). W ataku parę może dostarczyć reset urządzenia. Wspólne jest rugowanie niewiadomej; uprawnienia do uzyskania tej pary i prawdopodobieństwo sukcesu trzeba uzasadnić osobno.

Niech $B$ będzie ustaloną podstawą w grupie rzędu $q$. Jeżeli zamiast skalaru protokół ujawnia tylko element grupy $B^{x+a·c}$, analogiczne działania mogą dać $B^a$, nie skalar $a$. Pairing umożliwia sprawdzanie relacji między elementami grup, lecz nie odczytuje wykładników. Szczegółowe wyprowadzenie znajduje się w System Security II.

Model pozwalający narzucać losowość może również odtworzyć jej uczciwe losowanie i ujawnienie, jeżeli zgadzają się faza protokołu, dziedzina wartości i moment ujawnienia. Nie utożsamiamy jednak automatycznie wszystkich modeli wycieku ze wszystkimi modelami ustawiania. Przykłady konkretnych interfejsów podają modyfikacja Schnorra (2016), jej wersja czasopismowa (2020) oraz anonimowa identyfikacja, §2 (2019).

Ćwiczenie kontrolne. Sprawdź oba rachunki z przykładu. Następnie ustaw jednakowe wyzwania i wskaż, dlaczego nie wolno obliczyć odwrotności. Na końcu zmień losowość drugiego przebiegu: wypisz niewiadome, które pozostają po odjęciu odpowiedzi. Oddziel możliwość odzyskania klucza od samej poprawności transkryptów.

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 grupie multiplikatywnej modulo $p$

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

Lista nr 1 — 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 transkryptu akceptowanego przez weryfikatora.
4. Wyjaśnij, czy atakujący musi znać logarytm dyskretny klucza publicznego $A$.

Lista nr 1 — 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. Zaprojektuj atakującego, który wybiera i wysyła $X$ przed otrzymaniem wyzwania $c$, a następnie konstruuje odpowiedź $s$ pozwalającą przejść weryfikację.
4. Oceń, czy wyzwanie $c$ rzeczywiście utrudnia podszycie się.

Lista nr 1 — 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.

Lista nr 1 — 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?

Lista nr 1 — 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 dowolnie 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.

Lista nr 1 — zadanie porównawcze

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.

Lista nr 2 — podpisy

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

Co oznacza fałszerstwo?

W modelu EUF-CMA przeciwnik zna klucz publiczny i może otrzymywać podpisy wybranych wiadomości. Wygrywa, gdy poda akceptowany podpis pod nową wiadomością, której nie przekazał do podpisania. Nie musi odzyskać klucza. Przy każdym ataku zapisz, ile podpisów uzyskał i dlaczego wynik dotyczy nowej wiadomości.

$\mathcal H(m,R)$ oznacza hasz jednoznacznego kodowania wiadomości i zobowiązania, z wynikiem w dziedzinie wyzwań. Samo połączenie napisów bez określenia granic pól może być niejednoznaczne. Warianty z $m+R$, mnożeniem lub XOR wymagają zadeklarowania reprezentacji; tekst wiadomości i element grupy nie są automatycznie liczbami tego samego typu.

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 $\mathrm{\mathscr{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=a·Q$, $R=r·Q$, $h=\mathrm{\mathscr{H}}(m,R)$, $s=[r+a·h]modq$ oraz warunek $s·Q=R+h·A$.

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=\mathrm{\mathscr{H}}(m,R)modq$, $s=[r+a·h]modq$ i test $g^s=R·A^{h}modp$.

Lista nr 2 — zadanie 1: wariant z $h=\mathrm{\mathscr{H}}(m)$

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 $\mathrm{\mathscr{H}}(m,R)$ w podpisie Schnorra.

Lista nr 2 — zadanie 3: $h=m·R$

1. Wyjaśnij, w jakiej domenie iloczyn $m·R$ 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 $\mathrm{\mathscr{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 ze skrótem 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 opartych na tej konstrukcji.

Lista nr 3 — podpisy BLS

Trzecia lista dotyczy podpisów BLS. Celem jest zrozumienie, dlaczego w tym schemacie poprawna definicja funkcji ${\mathscr{H}}_{G_1}$ jako bezpiecznej funkcji hash-to-curve jest kluczowa.

Lista nr 3 — jeden sekret, klucze w dwóch grupach

Ten sam sekret $a$ może mieć dwie publiczne reprezentacje: $A_1=a·P\in G_1$ oraz $A_2=a·Q\in G_2$. Nie losujemy dwóch niezależnych sekretów. Pary $(a,A_1)$ i $(a,A_2)$ współdzielą ten sam skalar.

Standardowy BLS nie wymaga obu kluczy. Gdy podpis jest w $G_1$, do jego weryfikacji wystarcza $A_2$ w $G_2$. Taką orientację opisuje projekt specyfikacji CFRG BLS, §2.1 (Internet-Draft, dokument roboczy). Profil rozszerzony wprowadzamy tu jako dodatkowy model do ćwiczeń, nie jako wymóg standardu. W dalszych równaniach $A=A_2$.

W zapisie potęgowym te same klucze to $A_1=P^a$ i $A_2=Q^a$. Są to elementy różnych grup. Przy parowaniu typu 3, jak w tym demo, nie zakładamy efektywnego przekształcenia klucza z jednej grupy źródłowej do drugiej. Znając sekret, użytkownik oblicza oba klucze bez takiego przekształcenia.

Publiczny test zgodności

Najpierw sprawdzamy, czy oba klucze są poprawnymi, niezerowymi punktami odpowiednich podgrup rzędu $q$. Następnie, bez znajomości $a$, sprawdzamy:

Pierwszy argument każdego parowania należy do $G_1$, drugi do $G_2$, a porównujemy elementy $G_T$. Dla kluczy utworzonych z tego samego sekretu obie strony wynoszą ${e(P,Q)}^a$, co wynika z dwuliniowości.

Dlaczego działa też implikacja odwrotna? Zapiszmy $A_1=u·P$ oraz $A_2=v·Q$, gdzie $u,v\in {\mathbb{Z}}_q$. Test daje ${e(P,Q)}^u={e(P,Q)}^v$. Element $e(P,Q)$ ma rząd $q$, więc $u=v$ w ${\mathbb{Z}}_q$. Klucze reprezentują zatem ten sam skalar.

Zgodność nie jest dowodem znajomości sekretu. Skopiowanie cudzej pary kluczy również przechodzi ten test. Nie potwierdza on tożsamości użytkownika ani posiadania sekretu. Nie jest też dowodem niepodrabialności podpisu.

Poprawność a dowód bezpieczeństwa

Równanie weryfikacji podpisu pozostaje takie samo w obu profilach. W dowodzie bezpieczeństwa trzeba jednak jawnie podać, co otrzymuje przeciwnik. Dla profilu rozszerzonego otrzymuje również $A_1$. Redukcja musi umieć przygotować tę dodatkową, zgodną reprezentację z danych swojego wyzwania. Nie wolno pomijać tego kroku ani uzasadniać bezpieczeństwa samym testem zgodności kluczy.

Lista nr 3 — punkt odniesienia: poprawny podpis BLS

W poprawnym BLS haszujemy wiadomość do punktu grupy, a następnie mnożymy ten punkt przez klucz sekretny. Wynikiem haszowania jest punkt, nie znany skalar służący do przemnożenia stałego generatora.

Funkcja ${\mathscr{H}}_{G_1}:{\{0,1\}}^{*}\to G_1$ jest funkcją hash-to-curve (hash-to-point). W analizie BLS modelujemy ją jako wyrocznię losową do grupy. Dla ustalonej wiadomości i parametrów każdy oblicza ten sam punkt $M={\mathscr{H}}_{G_1}(m)$. Mapowanie nie ujawnia jednak logarytmu dyskretnego tego punktu względem stałego generatora $P$.

Nieprzewidywalność nie oznacza tajności ani ponownego losowania. Punkt $M$ jest publicznie obliczalny. W modelu wyroczni losowej wynik dla nowej wiadomości jest nieprzewidywalny przed zapytaniem o nią; znajomość wcześniejszych wyników nie pozwala go przewidzieć. Niezerowy punkt grupy rzędu pierwszego sam jest generatorem, ale ${\mathscr{H}}_{G_1}(m)$ nie zastępuje stałych parametrów $P$ i $Q$ nowymi parametrami przy każdym podpisie.

Równanie poniżej zakłada poprawne punkty wejściowe. Przy przyjmowaniu danych z zewnątrz weryfikator najpierw sprawdza kodowanie, przynależność klucza i podpisu do właściwych podgrup oraz odrzuca zerowy klucz publiczny. Samo porównanie wyników parowania nie zastępuje tej walidacji.

1. Traktuj ten wariant jako kryptograficzny punkt odniesienia dla całej listy nr 3.
2. Zwracaj uwagę, czy funkcja ${\mathscr{H}}_{G_1}$ 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$.

Lista nr 3 — jedna konstrukcja, dwie notacje

Na tablicy często używam zapisu potęgowego, ponieważ jest krótszy. W opisie grup punktów krzywej $X^a$ oznacza wtedy dokładnie tę samą operację co $a·X$: mnożenie punktu przez skalar. Nie potęgujemy jego współrzędnych.

W poniższym zestawieniu $X$ i $Y$ są punktami tej samej grupy źródłowej, $G_1$ albo $G_2$. Litery oznaczają te same obiekty w obu kolumnach; zmienia się wyłącznie konwencja zapisu działania grupowego.

Jeżeli generator oznaczamy literą $g$, zapis $g^a$ ma na krzywej tę samą interpretację co $a·g$. Zapis $P^a$ nie oznacza więc przeniesienia punktu do innej grupy ani potęgowania liczby modulo $p$. W demonstratorach BigInt modulo $p$ pracujemy natomiast rzeczywiście w grupie multiplikatywnej liczb.

To samo równanie weryfikacji

W obu notacjach weryfikator sprawdza $e(\sigma ,Q)=e(M,A)$. Dwuliniowość wyjaśnia, dlaczego test akceptuje podpis utworzony przez właściciela sekretu:

Wyniki parowania należą do $G_T$; potęgowanie ${e(M,Q)}^a$ wykonujemy w tej grupie docelowej. Zmiana notacji w $G_1$ i $G_2$ nie zamienia miejscami argumentów parowania: pierwszy nadal należy do $G_1$, drugi do $G_2$.

BLS a Schnorr. W BLS ${\mathscr{H}}_{G_1}(m)$ jest punktem, a podpis to $a·{\mathscr{H}}_{G_1}(m)$. W podpisie Schnorra skrót wyznaczający wyzwanie jest skalarem; w wariancie z listy nr 2 jest to $h=\mathscr{H}(m,R)\in {\mathbb{Z}}_q$, gdzie $R$ jest zobowiązaniem. Są to różne typy wyników i różne role funkcji haszującej.

Źródła: Boneh, Drijvers, Neven: definicja BLS w zapisie potęgowym; RFC 9380: haszowanie do punktów krzywej.

Demonstrator WASM — poprawny podpis BLS

Demonstrator pokazuje klasyczny wariant BLS z haszowaniem wiadomości do $G_1$ i kluczem publicznym w $G_2$. Obliczamy $M={\mathscr{H}}_{G_1}(m)$, $A=a·Q$, $\sigma =a·M$, a weryfikacja sprawdza warunek $e(\sigma ,Q)=e(M,A)$.

Punkt wiadomości wyznacza mcl.hashAndMapToG1, a podpis oblicza mcl.mul. Wejściem haszowania jest jednoznaczny zapis JSON.stringify(['bls', m]), zawierający etykietę domeny i wiadomość. Nie jest to kodowanie wiadomości do wykładnika. Demo pokazuje algebraiczny rdzeń BLS; nie deklaruje zgodności bajtowej z określonym standardowym zestawem parametrów BLS.

Dodatkowo obliczamy $A_1=a·P$, aby pokazać profil rozszerzony. Przycisk „Sprawdź klucze” porównuje dwa parowania bez używania sekretu; nie sprawdza podpisu wiadomości. Demo pracuje wyłącznie na punktach wygenerowanych lokalnie w odpowiednich podgrupach, nie przyjmuje kluczy z zewnątrz. Sekret pokazujemy tylko dydaktycznie. Test wydajności obejmuje haszowanie, podpis i jego weryfikację, bez generowania i testu zgodności kluczy.

Lista nr 3 — zadanie 1: stała funkcja ${\mathscr{H}}_{\mathrm{bad}}(m)=P_0$

Celowo wadliwy wariant. Funkcja ${\mathscr{H}}_{\mathrm{bad}}$ jest zdefiniowanym poniżej zamiennikiem, a nie poprawną funkcją ${\mathscr{H}}_{G_1}$.

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.
5. Profil rozszerzony. Rozpatrz dodatkowo przypadek, gdy znany jest skalar $b$ taki, że $P_0=b·P$. Czy publiczny $A_1$ pozwala wtedy fałszować bez zapytania o podpis? Wyjaśnij, dlaczego nie należy automatycznie zakładać znajomości takiego $b$ dla dowolnego punktu $P_0$.

Lista nr 3 — zadanie 2: liniowa funkcja ${\mathscr{H}}_{\mathrm{bad}}(m)=\mathrm{enc}(m)·P$

Celowo wadliwy wariant. Funkcja ${\mathscr{H}}_{\mathrm{bad}}$ jest zdefiniowanym poniżej zamiennikiem, a nie poprawną funkcją ${\mathscr{H}}_{G_1}$.

Celowo błędny wariant do analizy. W tym zadaniu zastępujemy hash-to-curve publicznym kodowaniem wiadomości do skalaru i mnożeniem stałego generatora przez ten skalar. Funkcja $\mathrm{enc}$ oznacza tu jawne publiczne kodowanie. Nie jest to definicja poprawnego BLS ani mapowanie używane w demonstratorze powyżej.

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 ${\mathscr{H}}_{\mathrm{bad}}$ jest tu wadą.
4. Profil rozszerzony. Pokaż, jak obliczyć podpis z samego publicznego skalaru $\mu$ i klucza $A_1$, bez znajomości sekretu i bez żadnego zapytania o podpis. Sprawdź wynik równaniem parowania. Porównaj z atakiem po jednym podpisie w profilu minimalnym.
5. Oceń, co dzieje się w przypadku $\mathrm{enc}(m)=0$ i czy to dodatkowo pogarsza bezpieczeństwo.

Lista nr 3 — zadanie 3: zbyt krótki skrót ${\mathscr{H}}_{\mathrm{bad}}(m)=\tau (m)·P$

Celowo wadliwy wariant. Funkcja ${\mathscr{H}}_{\mathrm{bad}}$ jest zdefiniowanym poniżej zamiennikiem, a nie poprawną funkcją ${\mathscr{H}}_{G_1}$.

1. Wyjaśnij, dlaczego tak zdefiniowana funkcja ${\mathscr{H}}_{\mathrm{bad}}$ 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 ${\mathscr{H}}_{G_1}$ zachowywała się jak bezpieczna funkcja hash-to-curve o dużej odporności na kolizje.
5. Atak niezależny od kolizji. W profilu minimalnym wykorzystaj jeden podpis dla niezerowego skrótu i przeskalowanie jak w zadaniu 2. W profilu rozszerzonym wykorzystaj bezpośrednio $A_1$. Wyjaśnij, dlaczego samo wydłużenie skrótu nie usuwa tej wady.

Lista nr 3 — zadanie 4: homomorficzna funkcja ${\mathscr{H}}_{\mathrm{bad}}$

Celowo wadliwy wariant. Funkcja ${\mathscr{H}}_{\mathrm{bad}}$ jest zdefiniowanym poniżej zamiennikiem, a nie poprawną funkcją ${\mathscr{H}}_{G_1}$.

Dziedzina tego zadania. $\mathbb M$ ma publicznie obliczalne działanie $m_1\cdot m_2$ zamknięte w zbiorze wiadomości, a $\operatorname{enc}$ ma własność podaną poniżej. Ten iloczyn oznacza działanie na wiadomościach, nie mnożenie punktów krzywej. W ataku wybierz wiadomości tak, aby wynik działania nie był żadną z wcześniej podpisanych wiadomości.

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 ${\mathscr{H}}_{\mathrm{bad}}$ 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.
5. Silniejszy atak. Czy w profilu minimalnym wystarczy jeden podpis z niezerowym kodowaniem, zamiast dwóch? W profilu rozszerzonym skonstruuj podpis bez jakiegokolwiek zapytania, korzystając z $A_1$. Wskaż, dlaczego te ataki nie wymagają homomorficzności kodowania.

Lista nr 3 — zadanie 5: łatwy logarytm dyskretny w obrazie ${\mathscr{H}}_{\mathrm{bad}}$

Celowo wadliwy wariant. Funkcja ${\mathscr{H}}_{\mathrm{bad}}$ jest zdefiniowanym poniżej zamiennikiem, a nie poprawną funkcją ${\mathscr{H}}_{G_1}$.

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 ${\mathscr{H}}_{\mathrm{bad}}\left(m_1\right)=b_1·P$, przy czym $b_1\ne 0$. Pokaż, jak odzyskać punkt $a·P$.
3. Dla dowolnej nowej wiadomości $m_2$ oblicz $b_2$ z warunku ${\mathscr{H}}_{\mathrm{bad}}\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 rozwiązywać problemu logarytmu dyskretnego dla dowolnego punktu grupy $G_1$. Wystarcza możliwość wyznaczenia logarytmu punktu zwróconego przez tę wadliwą funkcję ${\mathscr{H}}_{\mathrm{bad}}$ dla znanej wiadomości.
5. Profil rozszerzony. Punkt odzyskiwany w poprzednich krokach jest teraz publicznym kluczem $A_1$. Pokaż atak bez zapytania o podpis. Wyjaśnij, dlaczego nie można go przenieść na poprawne hash-to-curve, które nie ujawnia logarytmu punktu względem $P$.

Lista nr 3 — tabela porównawcza

Po przeanalizowaniu wszystkich schematów BLS uzupełnij tabelę osobno dla profilu minimalnego i rozszerzonego. Przy każdym ataku podaj liczbę potrzebnych podpisów, warunki jego wykonania i nową wiadomość będącą celem fałszerstwa.

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 ${\mathscr{H}}_{\mathrm{bad}}$, zbyt małą odporność na kolizje oraz łatwy logarytm dyskretny w obrazie funkcji ${\mathscr{H}}_{\mathrm{bad}}$.
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 $F_{\mathrm{FDH}}$ nie może zachowywać prostych zależności algebraicznych między wiadomościami, ponieważ prowadzi to do fałszerstw.

Parametry RSA i dziedzina wiadomości

Tu $N=p\cdot q$ oznacza iloczyn dwóch różnych liczb pierwszych. Litera $q$ jest w tej liście czynnikiem modułu RSA, nie rzędem grupy z poprzednich list. $\varphi(N)=(p-1)\cdot(q-1)$ liczy elementy $\mathbb Z_N^*$. Wybieramy $\gcd(e,\varphi(N))=1$ i $d=e^{-1}\bmod\varphi(N)$. Publiczne są $(N,e)$; sekretne pozostają $d$ i czynniki modułu.

W zadaniach 1–2 wiadomości są kanonicznymi zapisami liczb z $\mathbb Z_N^*$, a $\operatorname{enc}(m)$ zwraca tę liczbę. Dzięki temu dla obliczonego reprezentanta potrafimy zapisać odpowiadającą wiadomość. Nie zakładamy umiejętności odwracania dowolnej funkcji haszującej. W zadaniu 3 wiadomości kodujemy jako liczby całkowite z jawnie określonego zakresu; suma użyta w ataku musi należeć do tego zakresu i opisywać nową wiadomość.

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 $F_{\mathrm{FDH}}$ 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 $F_{\mathrm{FDH}}$ 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)(\mathrm{mod}N)$.
3. Wyjaśnij, dlaczego brak funkcji $F_{\mathrm{FDH}}$ 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 ${\mathscr{H}}_{\mathrm{bad}}(m)={\mu }^2$

Celowo wadliwy wariant. Funkcja ${\mathscr{H}}_{\mathrm{bad}}$ zastępuje właściwy pełnodziedzinowy hasz RSA $F_{\mathrm{FDH}}$; nie oznacza funkcji hash-to-curve.

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)(\mathrm{mod}N)$.
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 ${\mathscr{H}}_{\mathrm{bad}}(m)=g^{\mu }$

Celowo wadliwy wariant. Funkcja ${\mathscr{H}}_{\mathrm{bad}}$ zastępuje właściwy pełnodziedzinowy hasz RSA $F_{\mathrm{FDH}}$; nie oznacza funkcji hash-to-curve.

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 ${\mathscr{H}}_{\mathrm{bad}}$ 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 $F_{\mathrm{FDH}}$ 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

Dziedzina akceptacji. Klucze i zobowiązania należą do ustalonej podgrupy. W wariancie z pracy zobowiązania $R_i$ muszą być parami różne i różne od jedynki. Podpisujący losuje składniki niepodpisujących bez powtórzeń i bez jedynki, a następnie ponawia losowanie $u$, jeśli domknięcie narusza te warunki. Weryfikator odrzuca niedopuszczalne składniki przed sprawdzeniem równania. Analiza anonimowości uwzględnia ten sam rozkład z odrzucaniem dla każdego możliwego podpisującego.

Cały podpis tworzy jedna osoba. Samodzielnie wyznacza wszystkie zobowiązania $R_i$, korzystając z kluczy publicznych pozostałych członków i tylko własnego klucza prywatnego. Inni członkowie nie muszą być online. Nie jest to wspólne podpisywanie przez cały pierścień.

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.

Warunki wykonania. Klucze pierścienia są różne i nieidentycznościowe, $1\le n\le q-1$. W kroku 2 powtarzamy losowanie $u$, dopóki $R_j$ nie jest różne od jedynki i wszystkich pozostałych zobowiązań. Nie losujemy przy tym ponownie pozostałych $R_i$. W kroku 4 wyzwania obliczamy z wiadomości i zobowiązań; nie są dodatkowymi niezależnymi danymi podpisu. Herranz–Sáez, § 4.2–4.3.

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 $t_i$ i $R_i$ dla $i\ne j$.
3. Oblicz przewidywania dla wszystkich indeksów, nie znając wcześniej $j$. Jeśli dokładnie jedno zobowiązanie różni się od przewidywanego, wskaż jego znaczenie. Uwzględnij przypadek, gdy domknięcie przypadkowo zgadza się z przewidywaniem i test nie wyróżnia żadnego indeksu.
4. Oszacuj skuteczność tego rozróżniania przy zadanym rozkładzie domknięcia. Nie utożsamiaj wysokiej skuteczności z gwarancją sukcesu w każdym wykonaniu.

Przyjmij publiczną regułę uzyskania różnych niezerowych wartości z $F$ (np. jawny licznik prób przy danym indeksie). Reguła musi pozwalać odtworzyć kandydaturę dla każdego indeksu i nie może sama kodować numeru podpisującego.

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 j$.
3. Odróżnij ujawnienie ziarna od listy oznaczonych indeksami losowości: brak jednego indeksu na takiej liście już sam wskazuje deklarowanego podpisującego. Przy ziarnie sprawdź wszystkie indeksy i przypadek przypadkowej zgodności domknięcia.
4. Oceń, czy taki wariant zachowuje zaprzeczalność i anonimowość w sensie praktycznym.

Rozpoznanie gałęzi przy założeniu, że ujawniono rzeczywiście użyte ziarno, nie jest automatycznie dowodem autorstwa dla osoby trzeciej. Samo algebraiczne otwarcie zobowiązań nie dowodzi pochodzenia ujawnionych danych ani tożsamości ich twórcy.

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 $s$, losowe $R_1,\dots ,R_{n-1}$ i wyznacza ostatnią wartość $R_n$ z równania weryfikacyjnego, otrzymując cały podpis $\sigma$.
2. Wyprowadź jawny wzór na $R_n$.
3. Wyjaśnij, dlaczego lokalne wyzwania $h_i=\mathrm{\mathscr{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 j$ 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$.

Spójność z dziedziną akceptacji. Z małego przedziału odrzucamy zero i losujemy bez powtórzeń; potrzebujemy co najmniej $n-1$ dopuszczalnych wartości. Jeżeli dopuszczalny podzbiór ma $B$ punktów, domknięcie trafia do niego z prawdopodobieństwem $(B-(n-1))/(q-n)$ po ustaleniu pozostałych punktów. Dopiero mała wartość tego ilorazu uzasadnia dużą skuteczność rozpoznawania.

Lista nr 5 — zadanie 6: publicznie rozpoznawalne obciążenie rozkładu generatora

Ustal kodowanie i udział dopuszczalnych elementów grupy spełniających predykat. Prefiks kodowania punktu może zawierać stałe bity lub znaczniki. Predykat musi być osiągalny; inaczej generator nigdy nie zakończy losowania.

1. Wyjaśnij, dlaczego poprawność podpisu nadal może być zachowana mimo tego błędu implementacyjnego.
2. Pokaż, że dla wszystkich $i\ne j$ zachodzi $P\left(R_i\right)=\mathrm{true}$, natomiast dla $R_j$ prawdopodobieństwo wyznacza udział elementów spełniających predykat w dopuszczalnym zbiorze domknięć. Wartość około $2^{-16}$ wymaga dodatkowo w przybliżeniu jednostajnego rozkładu tych 16 bitów.
3. Pod warunkiem, że predykat jest rzadki w dopuszczalnym zbiorze domknięć, wyjaśnij, dlaczego Weryfikator może z 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 $j$.
3. Wyjaśnij, dlaczego opisana próba kompresji narusza anonimowość tej konstrukcji. Odróżnij ten wniosek od ogólnego ograniczenia długości podpisów pierścieniowych: przedstawiony argument nie dowodzi takiego ograniczenia dla wszystkich schematów.
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.

Lista nr 6 — anonimowe interaktywne systemy identyfikacji

Szósta lista dotyczy anonimowych interaktywnych systemów identyfikacji. Najpierw analizujemy standardowy wektorowy dowód OR, a następnie osobno sprawdzamy wariant z agregacją.

Lista nr 6 — punkt odniesienia: wektorowy dowód OR Schnorra

Dowód OR dotyczy alternatywy: „znam sekret co najmniej jednego z tych kluczy”. Ustalamy uporządkowaną listę różnych kluczy należących do ustalonej podgrupy i różnych od jej elementu neutralnego $L=(A_1,\ldots,A_n)$. Tylko dowodzący zna indeks $j$ i sekret $a_j$. Poniżej wyzwania łączymy dodawaniem w $\mathbb Z_q$; nie operacją XOR na napisach.

1. Przygotuj symulowane gałęzie. Dla $i\ne j$ losuj niezależnie $c_i,s_i\in\mathbb Z_q$ i oblicz $X_i=g^{s_i}\cdot A_i^{-c_i}$. Te równania można przygotować bez sekretów innych osób.
2. Ustal prawdziwą gałąź. Wylosuj $x\in\mathbb Z_q$, oblicz $X_j=g^x$ i wyślij cały wektor $(X_1,\ldots,X_n)$.
3. Odbierz wyzwanie. Weryfikator dopiero teraz losuje niezależne $c\in\mathbb Z_q$. Dowodzący oblicza $c_j=c-\sum_{i\ne j}c_i\pmod q$ i $s_j=x+a_j\cdot c_j\pmod q$.
4. Sprawdź każdą gałąź. Dowodzący wysyła wszystkie pary $(c_i,s_i)$. Po walidacji typów weryfikator akceptuje tylko wtedy, gdy zachodzi warunek sumy i każde równanie osobno:

W gałęziach symulowanych równości wynikają z definicji zobowiązań. W gałęzi rzeczywistej wynikają ze znajomości sekretu. Dwa akceptowane transkrypty z tym samym wektorem zobowiązań i różnymi wyzwaniami globalnymi muszą różnić się w co najmniej jednym $c_i$. Dla takiego indeksu wydobywamy $a_i=(s_i-s'_i)\cdot(c_i-c'_i)^{-1}\pmod q$. Możliwość wydobycia sekretu z takich dwóch transkryptów nazywamy szczególną rzetelnością (special soundness). Nie jest to metoda ustalania autora pojedynczego publicznego transkryptu.

Dla uczciwego, jednostajnego wyzwania pary $(c_i,s_i)$ mają jednakowy rozkład dla każdej rzeczywistej gałęzi, z jedynym ograniczeniem sumy wyzwań. Zobowiązania są wtedy odtwarzalne z równań. Ten argument dotyczy transkryptu; wycieki losowości zmieniają obserwację. Podstawa: I. Damgård, On Σ-protocols, kompozycja OR; Cramer, Damgård i Schoenmakers, CRYPTO 1994.

Lista nr 6 — zadanie 1: wariant z agregacją do analizy

Wariant do analizy, nie ogólny zamiennik dowodu OR. Poniższa kompresja zachowuje równanie dla uczciwego uczestnika, lecz odrzuca indywidualne testy gałęzi. Zbadaj, czy nadal dowodzi znajomości sekretu przy kluczach wybieranych przez przeciwnika.

1. Wykaż poprawność algebraiczną protokołu.
2. Wyjaśnij, dlaczego transkrypt $(X,c,s,c_1,\dots ,c_n)$ nie powinien ujawniać indeksu $j$ rzeczywistego Dowodzącego. Zwróć uwagę na rolę sumarycznego zobowiązania $X$ oraz warunku $c=\sum _i{c}_i$.
3. Porównaj ten protokół z podpisem pierścieniowym Herranza-Sáeza z listy nr 5. Wskaż różnice w interaktywności, w roli Weryfikatora, w sposobie wyznaczania wyzwań oraz w tym, że tutaj chodzi o anonimową identyfikację, a nie o publicznie weryfikowalny podpis pod wiadomością.
4. Wyjaśnij, dlaczego taki protokół jest bliższy schematowi identyfikacji Schnorra niż podpisowi pierścieniowemu Schnorra, mimo podobieństwa algebraicznego.

Sprawdzenie na powiązanych kluczach

Przyjmij $q>2$, nieznany przeciwnikowi logarytm $A_1$ i zarejestrowany przez niego drugi klucz $A_2=A_1^2$. Klucze są różne i nie są jedynką. Przeciwnik zna tylko $t$, wysyła $X=g^t$, a po otrzymaniu $c$ podaje $c_1=2\cdot c$, $c_2=-c$ i $s=t$, modulo $q$.

Oba agregowane testy przechodzą bez użycia sekretu któregokolwiek klucza. Nie jest to atak na wektorowy dowód OR powyżej. Wyjaśnij, jaką rolę ma rejestracja kluczy i dlaczego samą poprawność agregacji trzeba oddzielić od dowodu wiedzy. Zakaz powiązanych kluczy wyklucza ten przykład, ale sam nie stanowi pełnego dowodu bezpieczeństwa wariantu.

Lista nr 7 — AKE

Siódma lista dotyczy protokołów uwierzytelnionego uzgadniania klucza, czyli AKE. Dla każdego z poniższych schematów należy odpowiedzieć, czy jest bezpieczny. Jeżeli nie, trzeba wskazać atak. Jeżeli tak, trzeba wyjaśnić intuicję bezpieczeństwa.

Najpierw nazwij oczekiwaną własność

• Zgodność: uczciwe pasujące sesje wyliczają ten sam klucz.
• Uwierzytelnienie: akceptacja jest związana z właściwym partnerem i bieżącą wymianą, a nie tylko z dowolnym poprawnym podpisem.
• Tajność: przeciwnik nie odróżnia klucza chronionej sesji od niezależnego ciągu o tej samej długości, przy jawnie dozwolonych ujawnieniach.

DH, KDF i MAC. Wynik Diffiego–Hellmana jest elementem grupy. KDF wyprowadza z jego jednoznacznego kodowania i kontekstu klucze bitowe właściwej długości. MAC to kod uwierzytelniający wiadomość pod kluczem symetrycznym, nie adres karty sieciowej. Dla różnych ról stosujemy odrębne klucze lub domeny. Podpis i MAC w SIGMA pełnią różne zadania; ważne są oba sprawdzenia przed akceptacją. Krawczyk, SIGMA.

W każdym zadaniu określ aktywność przeciwnika: może tylko obserwować, czy także podmieniać, powtarzać i opóźniać komunikaty? Zweryfikuj parametry i przynależność odebranych elementów do grupy. Nie przenoś twierdzenia o opublikowanym protokole na skrót dydaktyczny bez sprawdzenia jego kodowań, walidacji i modelu.

Lista nr 7 — zadanie 1: klasyczny Diffie-Hellman bez uwierzytelnienia