Kryptografia — listy nr 1, nr 2, nr 3, nr 4, nr 5, nr 6, nr 7 i nr 8

Zasady zaliczenia ćwiczeń

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

Na ćwiczeniach będą rozwiązywane i omawiane zadania z list opublikowanych na stronie wykładowcy.
Po zakończeniu omawiania na ćwiczeniach danej listy zadań prowadząca ćwiczenia będzie przydzielała wybrane zadania konkretnym osobom do realizacji pisemnej i oddania w formacie PDF poprzez moduł zadań w MS Teams. Na realizację studenci będą mieli tydzień.
Za każde z przydzielonych zadań można otrzymać od 0 do 5 punktów. Nadesłanie rozwiązania po terminie będzie skutkowało obniżeniem liczby uzyskanych punktów o 1 za każdy rozpoczęty tydzień spóźnienia.
W trakcie semestru zostaną ponadto przeprowadzone dwa zapowiedziane sprawdziany. Za każdy z nich można otrzymać od 0 do 5 punktów. Jeżeli studentka lub student nie może uczestniczyć w sprawdzianie, może nadrobić punktację aktywnością w trakcie zajęć.
Podstawą do obliczenia oceny z ćwiczeń jest średnia punktów C, liczona zgodnie ze wzorem C = 0,4 · Z + 0,6 · S, gdzie Z oznacza średnią punktów z przydzielonych zadań, a S oznacza średnią punktów ze sprawdzianów.
Średnia C może zostać podwyższona przez prowadzącą ćwiczenia w zależności od aktywności studentki lub studenta na ćwiczeniach. Każde poprawnie rozwiązane przy tablicy zadanie podnosi średnią C o 0,2. Z własnych notatek dotyczących rozwiązań zadań z listy można korzystać przy tablicy tylko w wyjątkowych sytuacjach i za zgodą prowadzącej ćwiczenia.
Średnia C po uwzględnieniu aktywności jest zaokrąglana do najbliższej oceny, z wyjątkiem wartości 2,5, którą zaokrągla się do 2.

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.

Schemat odniesienia dla klasycznego Schnorra — Schemat odniesienia: klasyczny Schnorr.

Przebieg poprawnego protokołu: klucz publiczny $A = a Q$ , zobowiązanie $X = x Q$ , odpowiedź $s = [x + a c] mod q$ , weryfikacja $s Q = X + c A$ .

Ładowanie biblioteki WASM MCL...

1. Parametry

Krzywa i generator grupy.

Krzywa BLS12_381

Generator Q —

2. Klucze

Losowanie sekretu i klucza publicznego.

sk = a —

pk = A = aQ —

3. Zobowiązanie

Losowanie wartości efemerycznej.

x —

X = xQ —

4. Wyzwanie

Losowe wyzwanie od Weryfikatora.

c —

5. Odpowiedź

Obliczenie odpowiedzi protokołu.

s = [x + ac] mod q —

6. Weryfikacja

Sprawdzenie warunku akceptacji.

L = sQ —

R = X + cA —

Wynik —

Test wydajności nie został jeszcze uruchomiony.

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 + a c] mod q$ i test $g^{s} = X \cdot A^{c}$ .

Możesz ustawić bardzo małe parametry, np. 23 / 11 / 2, albo większe. Aktywuj tylko takie, dla których $q | (p - 1)$ oraz $g^{q} \equiv 1 (mod p)$ .

Demonstrator BigInt jest gotowy.

1. Parametry

Generator i rząd podgrupy. Parametry możesz wpisać ręcznie i zatwierdzić przyciskiem albo klawiszem Enter. Jeżeli nie znasz poprawnego generatora dla wpisanych p i q, użyj przycisku wyznaczania g.

p (moduł)

q (rząd podgrupy)

g (generator)

Aktywne p, q, g 1019, 509, 3

2. Klucze

Losowanie sekretu i klucza publicznego.

sk = a —

pk = A = g^a mod p —

3. Zobowiązanie

Losowanie wartości efemerycznej.

x —

X = g^x mod p —

4. Wyzwanie

Wyzwanie w zbiorze Zq.

c —

5. Odpowiedź

Obliczenie odpowiedzi modulo q.

s = [x + ac] mod q —

6. Weryfikacja

Porównanie obu stron równania.

L = g^s mod p —

R = X · A^c mod p —

Wynik —

Test wydajności nie został jeszcze uruchomiony.

Lista nr 1 — wprowadzenie

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

A = g^{a}

Cel analizy każdego schematu

Sprawdzić poprawność schematu dla uczciwego Dowodzącego.
Ocenić, czy schemat jest bezpieczny jako schemat identyfikacji.
Jeśli nie jest bezpieczny, podać atak podszycia się.
Oddzielić pojęcia: poprawność, rzetelność i odporność na fałszerstwo.

Sam fakt, że równanie weryfikacyjne jest algebraicznie poprawne, nie oznacza jeszcze bezpieczeństwa. Kluczowym sygnałem błędu jest możliwość dopasowania odpowiedzi po poznaniu wyzwania.

Lista nr 1 — zadanie 1: analiza pierwszego schematu

Schemat 1

1

Dowodzący losuje

x \in ℤ_{q} *

, oblicza

X = g^{x}

i wysyła

X

.

2

Weryfikator losuje

c \in ℤ_{q} *

i wysyła

c

.

3

Dowodzący odsyła

s = [x + a + c] (\mod q)

.

4

Weryfikator akceptuje wtedy i tylko wtedy, gdy

g^{s} = X \cdot A \cdot g^{c}

.

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

Lista nr 1 — zadanie 2: analiza drugiego schematu

Schemat 2

1

Dowodzący losuje

x

, oblicza

X = g^{x}

i wysyła

X

.

2

Weryfikator wysyła wyzwanie

c

.

3

Dowodzący odsyła

s = [c (x + a)] (\mod q)

.

4

Weryfikator sprawdza, czy

g^{s} = {(A \cdot X)}^{c}

.

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

Lista nr 1 — zadanie 3: analiza trzeciego schematu

Schemat 3

1

Dowodzący losuje

x

, oblicza

X = g^{x}

i wysyła

X

.

2

Weryfikator wysyła wyzwanie

c

.

3

Dowodzący odsyła

s = [x a c] (\mod q)

oraz

W = g^{a x}

.

4

Weryfikator akceptuje, gdy

g^{s} = W^{c}

.

Wykaż poprawność dla uczciwego Dowodzącego.
Zauważ, że w warunku akceptacji nie występuje bezpośrednio ani $A$ , ani $X$ . Czy to jest sygnał ostrzegawczy? Uzasadnij.
Sprawdź, czy osoba nieznająca $a$ może dobrać $s$ i $W$ tak, by przejść test.
Jeśli tak, zapisz pełny atak krok po kroku.
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

Schemat 4

1

Dowodzący wysyła

X = g^{x}

.

2

Weryfikator wysyła

c

.

3

Dowodzący odsyła

s = [c + x a] (\mod q)

oraz

W = g^{a x}

.

4

Weryfikator sprawdza, czy

g^{s} = g^{c} \cdot W

.

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

Lista nr 1 — zadanie 5: analiza piątego schematu

Schemat 5

1

Dowodzący wysyła

X = g^{x}

.

2

Weryfikator wysyła

c

.

3

Dowodzący odsyła

s = [(a + c x) (c + a x)] (\mod q)

W = g^{a x^{2}} Z = g^{x a^{2}}

4

Weryfikator akceptuje, gdy

g^{s} = {(A \cdot X^{c} \cdot W)}^{c} \cdot Z

Rozwiń algebraicznie obie strony warunku akceptacji i sprawdź poprawność.
Ustal, czy zależność weryfikacyjna naprawdę wymusza znajomość sekretu $a$ .
Sprawdź, czy atakujący może arbitralnie wybrać część odpowiedzi, a resztę dopasować.
Oceń, czy większa złożoność wzorów poprawia bezpieczeństwo, czy tylko zaciemnia obraz.
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.

Nr schematu	Czy jest poprawny?	Czy jest bezpieczny?	Typ ataku / obserwacja	Główny błąd konstrukcyjny
1
2
3
4
5

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

Lista nr 1 — punkt odniesienia: klasyczny Schnorr

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

Schemat Schnorra

1

Dowodzący wysyła

X = g^{x}

.

2

Weryfikator wysyła

c

.

3

Dowodzący odsyła

s = [x + c a] mod q

.

4

Weryfikator sprawdza, czy

g^{s} = X \cdot A^{c}

.

Wyjaśnij, czym strukturalnie Schnorr różni się od analizowanych konstrukcji.
Pokaż, dlaczego odpowiedź w Schnorrze nie daje się łatwo sfałszować po poznaniu wyzwania.
Wskaż, które z analizowanych schematów przypominają Schnorra tylko powierzchownie.
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.

Zakładamy grupę cykliczną $G = ⟨ g ⟩$ rzędu $q$ , sekret $a$ , klucz publiczny $A = g^{a}$ , wiadomość $m$ oraz podpis $σ$ . Wszystkie działania skalarne traktujemy jako wykonywane w $ℤ_{q}$ . W zadaniu 4 zapis $m \oplus R$ interpretujemy jako operację XOR po wcześniejszym zakodowaniu

m

i

R

do bitstringów tej samej długości. Następnie trzeba ocenić, czy wynik takiej operacji da się sensownie odwzorować do $ℤ_{q}$ i użyć jako skalaru

h

.

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$ .

Poprawny podpis Schnorra

1

Podpisujący losuje

r \in ℤ_{q}

i oblicza

R = g^{r}

.

2

Wyznacza

h = H (m, R)

.

3

Oblicza

s = [r + a h] mod q

i zwraca

σ = (R, s)

.

4

Weryfikator wyznacza

h = H (m, R)

i akceptuje wtedy i tylko wtedy, gdy

g^{s} = R \cdot A^{h}

.

Traktuj ten wariant jako kryptograficzny punkt odniesienia dla całej listy nr 2.
Przy analizie kolejnych zadań zawsze sprawdzaj, czy zachowano poprawne związanie wiadomości z $R$ przez $H (m, R)$ .
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 = H (m, R)$ , $s = [r + a h] mod q$ oraz warunek $s Q = R + h A$ .

Ładowanie biblioteki WASM MCL...

1. Parametry

Krzywa i generator grupy.

Krzywa BLS12_381

Generator Q —

2. Klucze

Losowanie sekretu i klucza publicznego.

sk = a —

pk = A = aQ —

3. Wiadomość

Treść podpisywanej wiadomości.

m

Aktywna wiadomość To jest wiadomość testowa.

4. Losowanie r

Wartość efemeryczna i zobowiązanie.

r —

R = rQ —

5. Skrót i podpis

Obliczenie $h$ i $s$ .

h = H(m, R) —

s = [r + ah] mod q —

6. Weryfikacja

Sprawdzenie podpisu.

L = sQ —

P = R + hA —

Wynik —

Test wydajności nie został jeszcze uruchomiony.

Demonstrator BigInt — poprawny podpis Schnorra w $ℤ_{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 + a h] mod q$ i test $g^{s} = R \cdot A^{h} mod p$ .

Demonstrator podpisu BigInt jest gotowy.

1. Parametry

Możesz użyć małych lub większych parametrów podgrupy Schnorra.

p (moduł)

q (rząd podgrupy)

g (generator)

Aktywne p, q, g p=1019, q=509, g=3

2. Klucze

Losowanie sekretu i klucza publicznego.

sk = a —

pk = A = g^a mod p —

3. Wiadomość

Treść podpisywanej wiadomości.

m

Aktywna wiadomość To jest wiadomość testowa.

4. Losowanie r

Wartość efemeryczna i zobowiązanie.

r —

R = g^r mod p —

5. Skrót i podpis

Obliczenie $h$ i $s$ .

h = H(m, R) mod q —

s = [r + ah] mod q —

6. Weryfikacja

Sprawdzenie podpisu.

L = g^s mod p —

P = R · A^h mod p —

Wynik —

Test wydajności nie został jeszcze uruchomiony.

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

Schemat podpisu 1

1

Podpisujący losuje

r \in ℤ_{q} *

, oblicza

R = g^{r}

.

2

Wyznacza

h = H (m)

.

3

Oblicza

s = [r + a h] mod q

i zwraca podpis

σ = (R, s)

.

4

Weryfikator wyznacza

h = H (m)

i akceptuje wtedy i tylko wtedy, gdy

g^{s} = R \cdot A^{h}

.

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

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

Schemat podpisu 2

1

Podpisujący losuje

r

, oblicza

R = g^{r}

.

2

Wyznacza

h = m + R

.

3

Oblicza

s = [r + a h] mod q

i zwraca

σ = (R, s)

.

4

Weryfikator wyznacza

h = m + R

i sprawdza, czy

g^{s} = R \cdot A^{h}

.

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

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

Schemat podpisu 3

1

Podpisujący losuje

r

, oblicza

R = g^{r}

.

2

Wyznacza

h = m R

.

3

Oblicza

s = [r + a h] mod q

i zwraca

σ = (R, s)

.

4

Weryfikator wyznacza

h = m R

i sprawdza warunek

g^{s} = R \cdot A^{h}

.

Wyjaśnij, w jakiej domenie iloczyn $m R$ miałby być liczony.
Sprawdź, czy takie związanie wiadomości z $R$ daje odporność na fałszerstwo, czy tylko pozór związania.
Zbadaj, czy można dobrać podpis dla wybranej wiadomości bez znajomości sekretu $a$ .
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)

Schemat podpisu 4

1

Podpisujący losuje

r

, oblicza

R = g^{r}

.

2

Wyznacza

h = m \oplus R

, gdzie

\oplus

oznacza bitowy XOR po odpowiednim zakodowaniu danych.

3

Oblicza

s = [r + a h] mod q

i zwraca

σ = (R, s)

.

4

Weryfikator wyznacza

h = m \oplus R

w tej samej interpretacji i akceptuje, gdy

g^{s} = R \cdot A^{h}

.

Podpowiedź interpretacyjna: można przyjąć, że najpierw kodujemy

m

i

R

jako bitstringi tej samej długości, następnie liczymy ich bitowy XOR, a otrzymany wynik interpretujemy jako liczbę całkowitą i redukujemy modulo

q

, aby dostać skalar

h \in ℤ_{q}

. To jest wygodna formalizacja do analizy, a nie standardowa konstrukcja podpisu Schnorra.

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.
Wyjaśnij, czy wynik XOR można potraktować jako sensowny odpowiednik wyzwania $h$ używanego w podpisie Schnorra.
Zbadaj, czy przy naturalnych interpretacjach XOR i mapowania do $ℤ_{q}$ możliwe jest skuteczne fałszerstwo podpisu.
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$

Schemat podpisu 5

1

Podpisujący losuje

r

, oblicza

R = g^{r}

oraz

X = g^{a r}

.

2

Wyznacza

h = H (m, R)

.

3

Oblicza

s = [h + r a] mod q

i zwraca podpis

σ = (R, s, X)

.

4

Weryfikator wyznacza

h = H (m, R)

i akceptuje, gdy

g^{s} = g^{h} \cdot X

.

Wykaż poprawność równania weryfikacyjnego dla uczciwego Podpisującego.
Zauważ, że weryfikacja nie korzysta bezpośrednio z klucza publicznego $A$ . Oceń znaczenie tego faktu.
Sprawdź, czy atakujący może dobrać $s$ i $X$ tak, by przejść weryfikację bez znajomości $a$ .
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$

Schemat podpisu 6

1

Podpisujący losuje

r

, oblicza

R = g^{r}

oraz

X = g^{a r}

.

2

Wyznacza

h = H (m, R, X)

.

3

Oblicza

s = [h + r a] mod q

i zwraca

σ = (R, s, X)

.

4

Weryfikator wyznacza

h = H (m, R, X)

i akceptuje, gdy

g^{s} = g^{h} \cdot X

.

Sprawdź poprawność schematu dla uczciwego Podpisującego.
Oceń, czy dodanie $X$ do wejścia funkcji skrótu naprawia zasadniczy problem z poprzedniego schematu.
Zbadaj, czy atakujący może dobrać podpis po wyborze $R$ , $X$ i $s$ bez znajomości sekretu.
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.

Nr schematu	Czy jest poprawny?	Czy jest bezpieczny?	Typ ataku / obserwacja	Główny błąd konstrukcyjny
1
2
3
4
5
6

Wskaż, które schematy zachowują zasadniczą strukturę podpisu Schnorra, a które jedynie powierzchownie go przypominają.
Wskaż, w których przypadkach problemem jest zły sposób definiowania $h$ , a w których brak związania podpisu z kluczem publicznym.
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.

Zakładamy grupy cykliczne $G_{1}$ , $G_{2}$ i $G_{T}$ rzędu pierwszego $q$ oraz parowanie dwuliniowe $e : G_{1} \times G_{2} \to G_{T}$ . Niech $P \in G_{1}$ i $Q \in G_{2}$ będą publicznymi generatorami, $a \in ℤ_{q}$ sekretem, a $A = a Q$ kluczem publicznym. Jeżeli w zadaniu pojawiają się zapisy typu $μ P$ , rozumiemy przez to $μ = enc (m) \in ℤ_{q}$ , gdzie

enc

jest jawnym publicznym kodowaniem wiadomości do skalaru.

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ą.

Poprawny podpis BLS

1

Podpisujący wyznacza

M = H (m) \in G_{1}

, gdzie

H

jest poprawną funkcją hash-to-curve.

2

Oblicza podpis

σ = a M \in G_{1}

.

3

Weryfikator akceptuje wtedy i tylko wtedy, gdy

e (σ, Q) = e (H (m), A)

.

Traktuj ten wariant jako kryptograficzny punkt odniesienia dla całej listy nr 3.
Zwracaj uwagę, czy funkcja $H$ naprawdę zachowuje się jak bezpieczne mapowanie wiadomości do punktu grupy.
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 (m)$ , $A = a Q$ , $σ = a M$ , a weryfikacja sprawdza warunek $e (σ, Q) = e (M, A)$ .

Ładowanie biblioteki WASM MCL...

1. Parametry

Krzywa i generatory grup.

Krzywa BLS12_381

Generator P w G1 —

Generator Q w G2 —

2. Klucze

Losowanie sekretu i klucza publicznego.

sk = a —

pk = A = aQ —

3. Wiadomość

Treść podpisywanej wiadomości.

m

Aktywna wiadomość To jest wiadomość BLS.

4. Hash-to-Curve

Mapowanie wiadomości do punktu grupy.

M = H(m) —

5. Podpis

Obliczenie $σ = a H (m)$ .

σ —

6. Weryfikacja

Porównanie obu stron równania parowań.

L = e(σ, Q) —

P = e(H(m), A) —

Wynik —

Test wydajności nie został jeszcze uruchomiony.

Lista nr 3 — zadanie 1: stała funkcja $H (m) = P_{0}$

Schemat BLS 1

1

Dla każdej wiadomości przyjmujemy

H (m) = P_{0} \in G_{1}

, gdzie

P_{0}

jest stałym publicznym punktem.

2

Podpisujący oblicza

σ = a P_{0}

.

3

Weryfikator sprawdza, czy

e (σ, Q) = e (P_{0}, A)

.

Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
Wyjaśnij, dlaczego podpis na jednej wiadomości staje się automatycznie podpisem na każdej innej wiadomości.
Opisz możliwie najsilniejszy atak fałszerstwa na ten schemat.
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 (m) = enc (m) P$

Schemat BLS 2

1

Dla wiadomości

m

wyznaczamy publiczny skalar

μ = enc (m) \in ℤ_{q}

i przyjmujemy

H (m) = μ P

.

2

Podpisujący oblicza

σ = a μ P

.

3

Weryfikator sprawdza, czy

e (σ, Q) = e (μ P, A)

.

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

Lista nr 3 — zadanie 3: zbyt krótki skrót $H (m) = τ (m) P$

Schemat BLS 3

1

Niech

τ (m)

oznacza bardzo krótki publiczny skrót wiadomości, na przykład 16-bitową wartość uzyskaną z obcięcia SHA-256.

2

Przyjmujemy

H (m) = τ (m) P \in G_{1}

.

3

Podpisujący oblicza podpis

σ = a τ (m) P

, a Weryfikator sprawdza

e (σ, Q) = e (τ (m) P, A)

.

Wyjaśnij, dlaczego tak zdefiniowana funkcja $H$ prowadzi do łatwych kolizji wiadomości.
Pokaż, jak wykorzystać znalezienie dwóch wiadomości $m_{1} \neq m_{2}$ z $τ (m_{1}) = τ (m_{2})$ do sfałszowania podpisu.
Oceń, jak rośnie skuteczność ataku wraz ze skracaniem wartości $τ$ .
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$

Schemat BLS 4

1

Niech

enc : 𝕄 \to ℤ_{q}

będzie publicznym kodowaniem wiadomości do skalarów, spełniającym własność

enc (m_{1} \cdot m_{2}) = enc (m_{1}) + enc (m_{2})

modulo

q

.

2

Definiujemy

H (m) = enc (m) P \in G_{1}

.

3

Podpisujący oblicza podpis

σ = a H (m) = a enc (m) P

.

4

Weryfikator sprawdza, czy

e (σ, Q) = e (enc (m) P, A)

.

Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
Załóż, że atakujący zna podpisy $σ_{1}$ pod $m_{1}$ oraz $σ_{2}$ pod $m_{2}$ . Pokaż, że suma $σ_{1} + σ_{2}$ jest poprawnym podpisem pod wiadomością $m_{1} \cdot m_{2}$ .
Wyjaśnij, dlaczego publiczna homomorficzność funkcji $H$ umożliwia składanie podpisów bez znajomości sekretu $a$ .
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$

Schemat BLS 5

1

Zakładamy, że dla każdej wiadomości

m

funkcja

H (m)

zwraca punkt

M \in G_{1}

, dla którego można efektywnie wyznaczyć skalar

b \in ℤ_{q}

spełniający

M = b P

.

2

Podpisujący oblicza podpis

σ = a M = a b P

.

3

Weryfikator sprawdza standardowy warunek BLS:

e (σ, Q) = e (H (m), A)

.

Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
Załóż, że atakujący zna jeden poprawny podpis $σ_{1}$ pod wiadomością $m_{1}$ i potrafi obliczyć $b_{1}$ takie, że $H (m_{1}) = b_{1} P$ , przy czym $b_{1} \neq 0$ . Pokaż, jak odzyskać punkt $a P$ .
Dla dowolnej nowej wiadomości $m_{2}$ oblicz $b_{2}$ z warunku $H (m_{2}) = b_{2} P$ i skonstruuj poprawny podpis pod $m_{2}$ bez znajomości sekretu $a$ .
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.

Nr schematu	Czy jest poprawny?	Czy jest bezpieczny?	Typ ataku / obserwacja	Główny błąd konstrukcyjny
1
2
3
4
5

Wskaż, które schematy są poprawne algebraicznie, ale całkowicie nieodporne na fałszerstwo.
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$ .
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.

Zakładamy moduł RSA $N = p q$ , wykładnik publiczny $e$ oraz wykładnik prywatny $d$ spełniające $e d \equiv 1 (\mod φ (N))$ . Dla czytelności przyjmujemy, że funkcja

H

mapuje wiadomości do zbioru odwracalnych reszt modulo $ℤ_{N}^{*}$ i że weryfikacja sprawdza warunek $σ^{e} \equiv H (m) (\mod N)$ . Jeżeli w zadaniu pojawia się zapis $μ = enc (m)$ , rozumiemy przez to jawne publiczne kodowanie wiadomości do elementu odwracalnego modulo

N

.

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.

Poprawny podpis RSA-FDH

1

Podpisujący oblicza wartość

y = H (m) \in ℤ_{N}^{*}

.

2

Wyznacza podpis

σ = y^{d} (\mod N)

.

3

Weryfikator akceptuje wtedy i tylko wtedy, gdy

σ^{e} \equiv H (m) (\mod N)

.

Traktuj ten wariant jako punkt odniesienia dla całej listy nr 4.
Zwracaj uwagę, czy funkcja $H$ rzeczywiście usuwa przewidywalne zależności algebraiczne między wiadomościami.
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

Schemat RSA 1

1

Dla wiadomości

m

obliczamy jej reprezentanta

μ = enc (m) \in ℤ_{N}^{*}

.

2

Podpisujący wyznacza podpis

σ = μ^{d} (\mod N)

.

3

Weryfikator sprawdza, czy

σ^{e} \equiv μ (\mod N)

.

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

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

Schemat RSA 2

1

Dla wiadomości

m

obliczamy

μ = enc (m) \in ℤ_{N}^{*}

i definiujemy

H (m) = μ^{2} (\mod N)

.

2

Podpisujący oblicza podpis

σ = {(μ^{2})}^{d} (\mod N)

.

3

Weryfikator sprawdza, czy

σ^{e} \equiv μ^{2} (\mod N)

.

Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
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 $enc (m_{3}) \equiv enc (m_{1}) enc (m_{2}) (\mod N)$ .
Wyjaśnij, dlaczego publiczna transformacja $μ \mapsto μ^{2}$ nie usuwa struktury multiplikatywnej, tylko ją zachowuje.
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 (m) = g^{μ}$

Schemat RSA 3

1

Ustalamy publiczny element

g \in ℤ_{N}^{*}

. Dla wiadomości

m

obliczamy

μ = enc (m)

i definiujemy

H (m) = g^{μ} (\mod N)

.

2

Podpisujący oblicza podpis

σ = {(g^{μ})}^{d} (\mod N)

.

3

Weryfikator sprawdza, czy

σ^{e} \equiv g^{μ} (\mod N)

.

Wykaż poprawność algebraiczną schematu dla uczciwego Podpisującego.
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ą $enc (m_{3}) = enc (m_{1}) + enc (m_{2})$ .
Wyjaśnij, dlaczego homomorfizm w wykładniku, czyli zależność $g^{μ + ν} = g^{μ} \cdot g^{ν}$ modulo $N$ , wystarcza do fałszerstwa.
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.

Nr schematu	Czy jest poprawny?	Czy jest bezpieczny?	Typ ataku / obserwacja	Główny błąd konstrukcyjny
1
2
3

Wskaż, które konstrukcje są poprawne algebraicznie, ale nieodporne na fałszerstwo.
Odróżnij trzy źródła słabości: całkowity brak haszowania, zachowanie struktury multiplikatywnej oraz zachowanie struktury addytywnej w wykładniku.
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 opiera się na pracy Forking Lemmas in the Ring Signatures' Scenario, J. Herranz, G. Sáez, IACR ePrint 2003/067, opublikowanej także na konferencji INDOCRYPT 2003. Punkt odniesienia poniżej odpowiada poprawnej konstrukcji, natomiast dalsze zadania analizują celowo zmienione warianty dydaktyczne, które mają pokazać, co narusza anonimowość. Zakładamy liczby pierwsze $p$ i $q$ takie, że $q | (p - 1)$ , generator $g$ podgrupy rzędu $q$ oraz funkcję $H (m, R) \in ℤ_{q}$ . Publiczny klucz i-tego uczestnika oznaczamy przez $A_{i} = g^{x_{i}} (\mod p)$ , gdzie $x_{i}$ jest jego kluczem prywatnym. Indeks rzeczywistego Podpisującego oznaczamy przez $j$ . Małą literą $s$ oznaczamy końcowy skalar podpisu w równaniu weryfikacyjnym, natomiast symbolem $σ$ oznaczamy cały podpis jako krotkę.

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.

Podpis pierścieniowy Herranza-Sáeza

1

Niech

A_{j}

będzie publicznym kluczem rzeczywistego Podpisującego. Dla każdego

i \neq j

losuje on pomocniczy skalar

t_{i} \in ℤ_{q}

i wyznacza

R_{i} = g^{t_{i}} (\mod p)

.

2

Losuje niezależny skalar

u \in ℤ_{q}

i oblicza

R_{j} = g^{u} / \prod_{i \neq j} A_{i}^{H (m, R_{i})} (\mod p)

.

3

Dla wszystkich

i

definiuje

h_{i} = H (m, R_{i})

i oblicza

s = [u + \sum_{i \neq j} t_{i} + x_{j} h_{j}] (\mod q)

, a następnie zwraca podpis

σ = (R_{1}, \dots, R_{n}, s)

.

4

Weryfikator sprawdza dla wszystkich

i

, że

h_{i} = H (m, R_{i})

, oraz weryfikuje równanie

g^{s} = \prod_{i} R_{i} \cdot \prod_{i} A_{i}^{h_{i}} (\mod p)

.

Traktuj ten wariant jako punkt odniesienia dla całej listy nr 5.
Zwracaj uwagę, które elementy podpisu są losowane przez rzeczywistego Podpisującego, a które są wyznaczane tak, aby zamknąć równanie weryfikacyjne.
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

Schemat pierścieniowy 1

1

Rozważ poprawny podpis pierścieniowy

σ = (R_{1}, \dots, R_{n}, s)

wygenerowany zgodnie z powyższym algorytmem dla wiadomości

m

.

2

Załóż, że pierścień składa się z publicznych kluczy

A_{1}, \dots, A_{n}

oraz że wszystkie wartości

R_{i}

są różne i różne od

1

.

3

Interesuje nas prawdopodobieństwo, z jakim ten sam podpis mógł zostać wygenerowany przez dowolnego członka pierścienia.

Wykaż poprawność algebraiczną schematu.
Pokaż, że dla ustalonego poprawnego podpisu każdy członek pierścienia mógł go wygenerować z takim samym prawdopodobieństwem.
Wyjaśnij, dlaczego z tego wynika anonimowość bezwarunkowa w sensie pracy Herranza i Sáeza.
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

Schemat pierścieniowy 2

1

Rozważ modyfikację schematu, w której dla wszystkich

i \neq j

nie losujemy pomocniczych skalarów

t_{i}

, lecz definiujemy je deterministycznie jako

t_{i} = F (m, A_{1}, \dots, A_{n}, i) \in ℤ_{q}

, gdzie

F

jest publiczną funkcją deterministyczną, na przykład funkcją haszującą mapującą dane wejście do wykładnika modulo

q

.

2

Dla

i \neq j

otrzymujemy zatem publicznie przewidywalne wartości

R_{i} = g^{t_{i}}

, a jedynie

R_{j}

jest nadal wyznaczane przez domknięcie równania weryfikacyjnego.

3

Interesuje nas to, czy taki wariant nadal chroni anonimowość rzeczywistego Podpisującego.

Wyjaśnij, dlaczego poprawność algebraiczna podpisu nadal może być zachowana.
Pokaż, że Weryfikator może samodzielnie odtworzyć wszystkie wartości $t_{i}$ i $R_{i}$ dla $i \neq j$ .
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.
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

Schemat pierścieniowy 3

1

Rozważ wariant, w którym dla wszystkich

i \neq j

wartości

t_{i}

są generowane pseudolosowo z ziarna

ρ

znanego wyłącznie rzeczywistemu Podpisującemu, na przykład

t_{i} = PRG (ρ, i) \in ℤ_{q}

.

2

Dla

i \neq j

mamy więc

R_{i} = g^{t_{i}}

, natomiast

R_{j}

jest nadal wyznaczane algebraicznie przez domknięcie równania i nie pochodzi z generatora

PRG

.

3

Załóż, że po opublikowaniu podpisu rzeczywisty Podpisujący ujawnia ziarno

ρ

albo wszystkie wygenerowane wartości

t_{i}

dla

i \neq j

.

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

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

Schemat pierścieniowy 4

1

Ktoś proponuje uproszczenie: zamiast lokalnych wartości

h_{i} = H (m, R_{i})

używamy jednej wspólnej wartości

h = H (m)

.

2

Weryfikacja ma wtedy postać

g^{s} = \prod_{i} R_{i} \cdot {(\prod_{i} A_{i})}^{h} (\mod p)

.

3

Sprawdź, czy takie uproszczenie zachowuje bezpieczeństwo schematu.

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 $σ$ .
Wyprowadź jawny wzór na $R_{n}$ .
Wyjaśnij, dlaczego lokalne wyzwania $h_{i} = H (m, R_{i})$ są istotne dla bezpieczeństwa konstrukcji.
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

Schemat pierścieniowy 5

1

Rozważ poprawny schemat Herranza-Sáeza, ale załóż, że dla wszystkich

i \neq j

generator losuje pomocnicze skalary

t_{i}

nie z całego

ℤ_{q}

, lecz z małego publicznego przedziału

{0, 1, \dots, 2^{t} - 1}

, gdzie

2^{t} ≪ q

.

2

Dla

i \neq j

publikujemy więc wartości

R_{i} = g^{t_{i}}

, w których logarytm dyskretny względem

g

leży w bardzo małym zakresie. Składnik

R_{j}

jest nadal wyznaczany przez domknięcie równania weryfikacyjnego.

3

Interesuje nas wyłącznie anonimowość schematu, a nie jego poprawność algebraiczna.

Wyjaśnij, dlaczego poprawność równania weryfikacyjnego nadal jest zachowana.
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}$ .
Wyjaśnij, dlaczego z dużym prawdopodobieństwem wszystkie indeksy $i \neq j$ zostaną rozpoznane jako „niepodpisujący”, a rzeczywisty Podpisujący pozostanie jedynym indeksem bez małego logarytmu.
Oceń, jak zmienia się skuteczność ataku wraz ze wzrostem parametru $t$ .

Lista nr 5 — zadanie 6: publicznie rozpoznawalny bias generatora

Schemat pierścieniowy 6

1

Rozważ poprawny schemat Herranza-Sáeza, ale załóż, że dla wszystkich

i \neq j

generator odrzuca próbki tak długo, aż otrzyma wartość

R_{i} = g^{t_{i}}

spełniającą publicznie sprawdzalny warunek, na przykład: pierwsze 16 bitów kodowania

R_{i}

jest równe zeru.

2

Składnik

R_{j}

rzeczywistego Podpisującego jest nadal wyznaczany algebraicznie przez domknięcie równania i nie przechodzi takiego filtrowania.

3

Niech

P (R)

oznacza publiczny predykat „zakodowana wartość

R

zaczyna się od 16 zer”.

Wyjaśnij, dlaczego poprawność podpisu nadal może być zachowana mimo tego błędu implementacyjnego.
Pokaż, że dla wszystkich $i \neq j$ zachodzi $P (R_{i}) = true$ , natomiast dla $R_{j}$ prawdopodobieństwo spełnienia tego warunku wynosi w przybliżeniu $2^{- 16}$ .
Wyjaśnij, dlaczego Weryfikator może z bardzo dużym prawdopodobieństwem wskazać rzeczywistego Podpisującego jako jedyny indeks niespełniający predykatu $P$ .
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

Schemat pierścieniowy 7

1

Ktoś proponuje skrócenie podpisu pierścieniowego. Zamiast publikować wszystkie pełne wartości

R_{i}

dla członków pierścienia, chce dla niepodpisujących wyznaczać je z krótkiego opisu

τ

, na przykład z hasza albo ziarna generatora, tak aby Weryfikator mógł je sobie odtworzyć.

2

Jedynie składnik rzeczywistego Podpisującego, czyli

R_{j}

, pozostaje „prawdziwym” elementem grupy wyznaczanym przez domknięcie równania weryfikacyjnego i nie daje się odtworzyć z tego samego krótkiego opisu.

3

Zbadaj, czy taka kompresja może zachować anonimowość schematu.

Wyjaśnij, dlaczego dla zachowania anonimowości rozkłady wszystkich wartości $R_{i}$ muszą być nierozróżnialne z punktu widzenia Weryfikatora.
Pokaż, że jeśli dla niepodpisujących wartości $R_{i}$ są odtwarzalne z krótkiego opisu $τ$ , a dla rzeczywistego Podpisującego nie są, to sam fakt tej odróżnialności ujawnia indeks $j$ .
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.
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.

Nr schematu	Czy jest poprawny?	Czy jest anonimowy?	Czy jest bezpieczny?	Typ obserwacji / ataku
1
2
3
4
5
6
7

Odróżnij trzy poziomy analizy: poprawność algebraiczną, anonimowość oraz odporność na fałszerstwo.
Wyjaśnij, dlaczego w podpisach pierścieniowych sam fakt poprawności równania weryfikacyjnego nie wystarcza ani do anonimowości, ani do bezpieczeństwa.
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. Niech będzie dany następujący interaktywny anonimowy protokół identyfikacji Schnorra.

W tej liście zakładamy liczby pierwsze

p

i

q

takie, że

q | (p - 1)

, generator

g

podgrupy rzędu

q

oraz zbiór kluczy publicznych

A_{1}, \dots, A_{n}

, gdzie

A_{i} = g^{a_{i}}

. Rzeczywisty Dowodzący ma własny klucz prywatny

a_{j}

oraz zna cały zbiór kluczy publicznych

{A_{1}, \dots, A_{n}}

, z którego wybiera anonimowy zbiór odniesienia. Weryfikator również zna wszystkie te klucze publiczne i właśnie względem tego pełnego zbioru sprawdza poprawność transkryptu. Indeks rzeczywistego Dowodzącego oznaczamy przez

j

. Wartości

c_{i}

są lokalnymi udziałami wyzwania, natomiast

c

jest globalnym wyzwaniem wybranym przez Weryfikatora.

Lista nr 6 — zadanie 1: anonimowy interaktywny Schnorr

W tym wariancie jeden z użytkowników, znający własny sekret długoterminowy oraz publiczne klucze wszystkich członków rozważanego zbioru, udowadnia swoją przynależność do tego zbioru. Transkrypt protokołu nie powinien ujawniać, który dokładnie indeks jest rzeczywisty.

1-z-

n

anonimowy protokół Schnorra

1

Niech

A_{j}

będzie rzeczywistym Dowodzącym. Dla każdego

i \neq j

losuje on

s_{i}, c_{i} \in ℤ_{q}

i wyznacza

X_{i} = g^{s_{i}} / A_{i}^{c_{i}} (\mod p)

.

2

Losuje

x \in ℤ_{q}

i oblicza

X_{j} = g^{x}

. Następnie wyznacza sumaryczne zobowiązanie

X = \prod_{i} X_{i} (\mod p)

i wysyła

X

do Weryfikatora.

3

Weryfikator losuje globalne wyzwanie

c \in ℤ_{q}

i odsyła je Dowodzącemu.

4

Dowodzący oblicza

c_{j} = [c - \sum_{i \neq j} c_{i}] (\mod q)

, następnie

s_{j} = [x + a_{j} c_{j}] (\mod q)

oraz

s = [\sum_{i} s_{i}] (\mod q)

. Odsyła

s

oraz wszystkie wartości

c_{1}, \dots, c_{n}

.

5

Weryfikator akceptuje wtedy i tylko wtedy, gdy zachodzą równania

g^{s} = X \cdot \prod_{i} A_{i}^{c_{i}} (\mod p)

oraz

c = [\sum_{i} c_{i}] (\mod q)

.

Wykaż poprawność algebraiczną protokołu.
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}$ .
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ą.
Wyjaśnij, dlaczego taki protokół jest bliższy schematowi identyfikacji Schnorra niż podpisowi pierścieniowemu Schnorra, mimo podobieństwa algebraicznego.

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.

W tej liście przez

{id}_{I}

i

{id}_{R}

oznaczamy identyfikatory stron, przez

{Cert}_{I}

i

{Cert}_{R}

ich certyfikaty, a przez

{PK}_{I} = g^{a}

i

{PK}_{R} = g^{b}

długoterminowe klucze publiczne zawarte w tych certyfikatach. Wartości

X = g^{x}

i

Y = g^{y}

oznaczają wartości efemeryczne. Jeżeli w zadaniu pojawia się symbol

K

, oznacza on kandydata na klucz sesyjny. W zadaniu o SIGMA dodatkowo używamy oznaczenia

K_{DH}

na wspólny sekret Diffiego-Hellmana, z którego wyprowadzane są klucze

K_{s}

i

K_{m}

.

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

Schemat AKE 1

1

Inicjator losuje

x \in ℤ_{q}^{*}

, oblicza

X = g^{x}

i wysyła

X

.

2

Strona odpowiadająca losuje

y \in ℤ_{q}^{*}

, oblicza

Y = g^{y}

i odsyła

Y

.

3

Inicjator oblicza

K = H (Y^{x})

, a strona odpowiadająca oblicza

K = H (X^{y})

.

Wykaż, że w uczciwym wykonaniu obie strony uzyskują ten sam klucz sesyjny.
Wyjaśnij, dlaczego mimo poprawności algebraicznej ten wariant nie zapewnia uwierzytelnienia partnera sesji.
Zademonstruj pełny atak pośrednika (man-in-the-middle): pokaż, jak przeciwnik podstawia własne wartości efemeryczne i uzgadnia dwa różne klucze, po jednym z każdą ze stron.
Wskaż, dlaczego sam klasyczny Diffie-Hellman nie jest jeszcze protokołem AKE w sensie kryptograficznym.

Lista nr 7 — zadanie 2: SIGMA jako punkt odniesienia oraz wariant osłabiony bez MAC

To zadanie odwołuje się do klasycznej rodziny protokołów SIGMA opisanej przez Hugona Krawczyka w pracy SIGMA: the ‘SIGn-and-MAc’ Approach to Authenticated Diffie-Hellman and Its Use in the IKE Protocols, CRYPTO 2003. W opisie poniżej identyfikatory stron oznaczamy przez

{id}_{I}

i

{id}_{R}

, ich certyfikaty przez

{Cert}_{I}

i

{Cert}_{R}

, a klucze publiczne odczytywane z tych certyfikatów przez

{PK}_{I}

i

{PK}_{R}

. Podpisy są tworzone przy użyciu odpowiednich kluczy prywatnych

{sk}_{I}

i

{sk}_{R}

, a następnie weryfikowane za pomocą kluczy publicznych z certyfikatów. W poprawnym wariancie SIGMA obie strony najpierw wyznaczają wspólny sekret Diffiego-Hellmana

K_{DH} = g^{x y} = Y^{x} = X^{y}

. Następnie wyprowadzają z niego klucz sesyjny

K_{s} = H (K_{DH}, 0)

oraz klucz do MAC

K_{m} = H (K_{DH}, 1)

. W takim uproszczeniu funkcja

H

pełni rolę prostej funkcji wyprowadzania kluczy: ten sam wspólny sekret jest haszowany z różnymi znacznikami domeny, aby otrzymać dwa rozdzielone kryptograficznie klucze o różnych zastosowaniach. Sam

MAC

można rozumieć jako krótki znacznik uwierzytelniający liczony z identyfikatora strony przy użyciu klucza

K_{m}

, na przykład w stylu HMAC. To właśnie MAC nad tożsamością wiąże wspólny sekret z identyfikatorem partnera; usunięcie tego składnika prowadzi do wariantu podatnego na ataki typu identity misbinding / unknown key-share. Zob. IACR PDF oraz stronę materiałów CRYPTO 2003.

Najpierw potraktuj poprawny SIGMA jako punkt odniesienia. Następnie przejdź do wariantu osłabionego, w którym usunięto MAC nad tożsamością.

Poprawny SIGMA

1

Inicjator losuje

x \in ℤ_{q}^{*}

, oblicza

X = g^{x}

i wysyła

X

.

2

Strona odpowiadająca losuje

y \in ℤ_{q}^{*}

, oblicza

Y = g^{y}

, wyznacza wspólny sekret

K_{DH} = X^{y}

, a następnie oblicza

K_{s} = H (K_{DH}, 0)

oraz

K_{m} = H (K_{DH}, 1)

. Następnie tworzy podpis przy użyciu swojego klucza prywatnego

{sk}_{R}

pod parą

(X, Y)

i odsyła

Y, {Cert}_{R}, {Sig}_{{sk}_{R}} (X, Y), {MAC}_{K_{m}} ({id}_{R})

.

3

Inicjator weryfikuje certyfikat

{Cert}_{R}

, odczytuje z niego klucz publiczny

{PK}_{R}

, sprawdza podpis

{Sig}_{{sk}_{R}} (X, Y)

za pomocą

{PK}_{R}

, następnie wyznacza wspólny sekret

K_{DH} = Y^{x}

, oblicza

K_{s} = H (K_{DH}, 0)

oraz

K_{m} = H (K_{DH}, 1)

, po czym sprawdza

{MAC}_{K_{m}} ({id}_{R})

. Następnie tworzy podpis przy użyciu swojego klucza prywatnego

{sk}_{I}

pod parą

(Y, X)

i odsyła

{Cert}_{I}, {Sig}_{{sk}_{I}} (Y, X), {MAC}_{K_{m}} ({id}_{I})

.

4

Strona odpowiadająca weryfikuje certyfikat

{Cert}_{I}

, odczytuje z niego klucz publiczny

{PK}_{I}

, sprawdza podpis

{Sig}_{{sk}_{I}} (Y, X)

za pomocą

{PK}_{I}

oraz sprawdza

{MAC}_{K_{m}} ({id}_{I})

. Klucz sesyjny obu stron ma postać

K_{s}

.

Wariant osłabiony: same podpisy

1

Inicjator losuje

x \in ℤ_{q}^{*}

, oblicza

X = g^{x}

i wysyła

X

.

2

Strona odpowiadająca losuje

y \in ℤ_{q}^{*}

, oblicza

Y = g^{y}

, a następnie tworzy podpis przy użyciu swojego klucza prywatnego

{sk}_{R}

pod parą

(X, Y)

i odsyła

Y, {Cert}_{R}, {Sig}_{{sk}_{R}} (X, Y)

.

3

Inicjator weryfikuje certyfikat

{Cert}_{R}

, odczytuje z niego klucz publiczny

{PK}_{R}

, sprawdza podpis

{Sig}_{{sk}_{R}} (X, Y)

za pomocą

{PK}_{R}

, oblicza

K = H (Y^{x})

i odsyła

{Cert}_{I}, {Sig}_{{sk}_{I}} (Y, X)

, gdzie podpis jest utworzony przy użyciu klucza prywatnego inicjatora

{sk}_{I}

.

4

Strona odpowiadająca weryfikuje certyfikat

{Cert}_{I}

, odczytuje z niego klucz publiczny

{PK}_{I}

, sprawdza podpis

{Sig}_{{sk}_{I}} (Y, X)

za pomocą

{PK}_{I}

i oblicza

K = H (X^{y})

.

Wyjaśnij, jak działa poprawny SIGMA i wskaż, które elementy odpowiadają za uwierzytelnienie wartości efemerycznych, a które za związanie klucza sesyjnego z identyfikatorami ${id}_{I}$ i ${id}_{R}$ .
Podaj intuicję bezpieczeństwa poprawnego SIGMA: wyjaśnij, dlaczego podpisy nie wystarczają same z siebie oraz po co potrzebny jest osobny MAC nad tożsamością.
Porównaj poprawny SIGMA z wariantem osłabionym bez MAC i wskaż dokładnie, jaki składnik został usunięty.
Przedstaw przykład ataku na wariant osłabiony: pokaż atak błędnego związania tożsamości (identity misbinding / unknown key-share), w którym przeciwnik doprowadza jedną ze stron do błędnego przekonania, z kim współdzieli klucz.
Wyjaśnij, dlaczego usunięcie MAC nad identyfikatorami ${id}_{I}$ i ${id}_{R}$ niszczy własność poprawnego związania klucza sesyjnego z tożsamościami stron.

Lista nr 7 — zadanie 3: liniowe domknięcie z wyzwaniami $c$ i $d$

Schemat AKE 3

1

Inicjator losuje

x \in ℤ_{q}^{*}

, oblicza

X = g^{x}

i wysyła

X

.

2

Strona odpowiadająca losuje

y, c \in ℤ_{q}^{*}

, oblicza

Y = g^{y}

i odsyła

Y, c

.

3

Inicjator losuje

d \in ℤ_{q}^{*}

, oblicza

s = [x + a + c] (\mod q)

i wysyła

d, s

.

4

Strona odpowiadająca sprawdza, czy

g^{s} = X \cdot {PK}_{I} \cdot g^{c}

. Jeżeli tak, oblicza

K = H (X^{y})

, następnie wyznacza

w = [y + b + d] (\mod q)

i wysyła

w

.

5

Inicjator sprawdza, czy

g^{w} = Y \cdot {PK}_{R} \cdot g^{d}

. Jeżeli tak, oblicza

K = H (Y^{x})

.

Sprawdź poprawność algebraiczną testów wykonywanych przez obie strony.
Oceń, czy równania weryfikacyjne rzeczywiście wiążą wartości efemeryczne z sekretami długoterminowymi $a$ i $b$ .
Zdecyduj, czy atakujący może doprowadzić do zaakceptowania sesji bez znajomości jednego z sekretów długoterminowych. Jeżeli tak, opisz atak krok po kroku.
Jeżeli uznasz schemat za niebezpieczny, wskaż dokładnie, która zależność liniowa otwiera drogę do ataku.

Lista nr 7 — zadanie 4: mnożnikowe wiązanie przez $c$ i $d$

Schemat AKE 4

1

Inicjator losuje

x \in ℤ_{q}^{*}

, oblicza

X = g^{x}

i wysyła

X

.

2

Strona odpowiadająca losuje

y, c \in ℤ_{q}^{*}

, oblicza

Y = g^{y}

i odsyła

Y, c

.

3

Inicjator losuje

d \in ℤ_{q}^{*}

, oblicza

s = [c (x + a)] (\mod q)

i wysyła

d, s

.

4

Strona odpowiadająca sprawdza, czy

g^{s} = {({PK}_{I} \cdot X)}^{c}

. Jeżeli tak, oblicza

K = H (X^{y})

, następnie wyznacza

w = [d (y + b)] (\mod q)

i wysyła

w

.

5

Inicjator sprawdza, czy

g^{w} = {({PK}_{R} \cdot Y)}^{d}

. Jeżeli tak, oblicza

K = H (Y^{x})

.

Sprawdź, czy obie strony zaakceptują sesję w uczciwym wykonaniu protokołu.
Porównaj ten wariant z zadaniem 3 i oceń, czy zastąpienie sum przez iloczyny rzeczywiście wzmacnia bezpieczeństwo.
Zbadaj, czy atakujący może dobrać komunikaty tak, aby przejść testy weryfikacyjne bez znajomości sekretu długoterminowego jednej ze stron.
Jeżeli znajdziesz atak, opisz, które zależności algebraiczne są tu publicznie sprawdzalne i jak są wykorzystywane przez przeciwnika.

Lista nr 7 — zadanie 5: bezpośrednie mieszanie sekretu długoterminowego z efemerycznym

Schemat AKE 5

1

Inicjator losuje

x \in ℤ_{q}^{*}

, oblicza

X = g^{[x + a]}

i wysyła

X

.

2

Strona odpowiadająca losuje

y \in ℤ_{q}^{*}

, oblicza

Y = g^{[y + b]}

i odsyła

Y

.

3

Inicjator oblicza

K = H (Y^{[x + a]})

, a strona odpowiadająca oblicza

K = H (X^{[y + b]})

, gdzie długoterminowe sekrety

a

i

b

odpowiadają odpowiednio kluczom publicznym

{PK}_{I}

i

{PK}_{R}

.

Wykaż, że obie strony uzyskują ten sam klucz sesyjny w uczciwym wykonaniu protokołu.
Zastanów się, jakie informacje o sekretach długoterminowych są ukryte w komunikatach $X$ i $Y$ .
Oceń, czy taki schemat chroni przed atakiem pośrednika (man-in-the-middle) oraz czy zapewnia uwierzytelnienie partnera sesji.
Jeżeli uznasz konstrukcję za niebezpieczną, wskaż, czy problem wynika z braku jawnej weryfikacji partnera, z ujawniania zbyt silnej struktury algebraicznej, czy z obu tych powodów jednocześnie.

Lista nr 7 — zadanie 6: klucz sesyjny z prostego wyrażenia symetrycznego

Schemat AKE 6

1

Inicjator losuje

x \in ℤ_{q}^{*}

, oblicza

X = g^{x}

i wysyła

X

.

2

Strona odpowiadająca losuje

y \in ℤ_{q}^{*}

, oblicza

Y = g^{y}

i odsyła

Y

.

3

Inicjator oblicza

K = H ({PK}_{R}^{x} \cdot Y^{x} \cdot {(g^{2})}^{a})

.

4

Strona odpowiadająca oblicza

K = H (X^{y} \cdot X^{b} \cdot {PK}_{I}^{2})

.

Najpierw uprość oba wyrażenia na klucz sesyjny i sprawdź, czy w uczciwym wykonaniu dają ten sam wynik.
Oceń, czy sam fakt zgodności algebraicznej wystarcza tutaj do bezpieczeństwa AKE.
Zbadaj, czy atakujący może manipulować wartościami $X$ i $Y$ tak, aby doprowadzić strony do uzgodnienia klucza bez rzeczywistego uwierzytelnienia partnera.
Porównaj ten wariant z klasycznym pomysłem Diffiego-Hellmana: wskaż, czego brakuje, aby uzyskać pełnoprawny i bezpieczny protokół AKE.

Lista nr 7 — tabela porównawcza

Po przeanalizowaniu wszystkich sześciu schematów AKE uzupełnij tabelę porównawczą.

Nr schematu	Czy jest poprawny?	Czy jest bezpieczny?	Typ ataku / obserwacja	Główny błąd konstrukcyjny
1
2
3
4
5
6

Odróżnij poprawność algebraiczną od bezpieczeństwa AKE: zgodność klucza po obu stronach nie oznacza jeszcze odporności na atak.
Wskaż, które schematy zawodzą przez brak właściwego uwierzytelnienia partnera, a które przez zbyt prostą strukturę algebraiczną komunikatów.
Sformułuj jedną wspólną zasadę: co musi wiązać klucz sesyjny z tożsamościami stron i ich wartościami efemerycznymi, aby nie dało się przeprowadzić ataku przez podstawienie komunikatów.

Lista nr 8 — analiza złożoności poprawnych protokołów

Ósma lista dotyczy analizy złożoności. Celem jest oszacowanie kosztu działania poprawnych protokołów i odróżnienie złożoności obliczeniowej, pamięciowej oraz komunikacyjnej.

W tej liście nie analizujemy bezpieczeństwa błędnych wariantów, tylko koszt poprawnych konstrukcji będących punktami odniesienia na tej stronie. Dotyczy to również omawianych na wykładzie wariantów podpisu BLS: multi-podpisu, podpisu agregowanego i podpisu pierścieniowego. Złożoność obliczeniową opisuj za pomocą najbardziej kosztownych operacji właściwych dla danego modelu: potęgowań i mnożeń w grupach multiplikatywnych, mnożeń skalarnych i dodawań punktów na krzywych eliptycznych, operacji parowania w protokołach opartych o parowania, a także wywołań funkcji haszujących i funkcji hash-to-curve. Złożoność pamięciową opisuj przez liczbę przechowywanych skalarów i elementów grupowych po stronie każdej ze stron protokołu. W protokołach interaktywnych dodatkowo oszacuj liczbę rund, liczbę wiadomości oraz łączny rozmiar komunikacji, używając oznaczeń

| G |

,

| G_{1} |

,

| G_{2} |

,

| G_{T} |

i

| ℤ_{q} |

na rozmiary zakodowanych elementów.

Lista nr 8 — zadanie 1: klasyczny schemat identyfikacji Schnorra

Punkt odniesienia

1

Weź jako punkt odniesienia poprawny, klasyczny interaktywny schemat identyfikacji Schnorra z listy nr 1.

2

Policz osobno koszt Dowodzącego i Weryfikatora.

3

Uwzględnij koszt obliczeniowy, pamięciowy i komunikacyjny.

Oszacuj liczbę potęgowań, mnożeń grupowych, dodawań w $ℤ_{q}$ oraz wywołań funkcji haszującej po stronie Dowodzącego i Weryfikatora.
Oszacuj, ile skalarów i ile elementów grupy musi równocześnie przechowywać każda ze stron.
Policz liczbę wiadomości, liczbę rund oraz łączny rozmiar komunikacji w bitach.
Porównaj koszty z wersją demonstracyjną w grupie multiplikatywnej modulo $p$ oraz z wersją na krzywej eliptycznej: wskaż, które operacje pozostają strukturalnie tym samym kosztem, a które zmieniają interpretację.

Lista nr 8 — zadanie 2: anonimowy interaktywny Schnorr 1-z- $n$

Punkt odniesienia

1

Weź jako punkt odniesienia poprawny anonimowy interaktywny protokół z listy nr 6.

2

Traktuj

n

jako parametr wejściowy opisujący rozmiar zbioru możliwych tożsamości.

3

Interesuje nas, jak cena anonimowości rośnie wraz z

n

.

Oszacuj koszt obliczeniowy Dowodzącego i Weryfikatora jako funkcję $n$ .
Wskaż, które operacje wykonywane są dla każdego indeksu $i$ , a które tylko dla rzeczywistego indeksu $j$ .
Oszacuj pamięć potrzebną do przechowywania wartości $X_{i}$ , $c_{i}$ i ewentualnych pomocniczych sum lub iloczynów.
Policz złożoność komunikacyjną: liczbę rund, liczbę wiadomości oraz rozmiar każdej wiadomości w zależności od $n$ .
Porównaj wynik z klasycznym Schnorrem z zadania 1 i opisz, który składnik złożoności jest ceną za anonimowość.

Lista nr 8 — zadanie 3: poprawny podpis Schnorra

Punkt odniesienia

1

Weź jako punkt odniesienia poprawny podpis Schnorra z listy nr 2.

2

Policz koszt Podpisującego i Weryfikującego.

3

Ponieważ schemat nie jest interaktywny, uwzględnij tylko rozmiar podpisu i kluczy, a nie liczbę rund protokołu.

Oszacuj koszt obliczenia podpisu oraz koszt weryfikacji, oddzielając potęgowania lub mnożenia skalarne od pozostałych operacji.
Oszacuj pamięć potrzebną przy generowaniu podpisu i przy jego weryfikacji.
Podaj rozmiar podpisu w bitach jako funkcję rozmiaru skalaru i elementu grupowego.
Porównaj koszt podpisu Schnorra z interaktywnym schematem identyfikacji Schnorra: wskaż, co zyskujemy, a co tracimy przechodząc od protokołu interaktywnego do podpisu.

Lista nr 8 — zadanie 4: poprawny podpis BLS, jego warianty oraz poprawny podpis RSA-FDH

Punkt odniesienia

1

Weź jako punkty odniesienia poprawny podpis BLS z listy nr 3, omawiane na wykładzie warianty BLS: multi-podpis, podpis agregowany i podpis pierścieniowy, a także poprawny podpis RSA-FDH z listy nr 4.

2

Dla wszystkich wariantów BLS uwzględnij osobno koszt funkcji hash-to-curve, operacji w

G_{1}

i

G_{2}

oraz operacji parowania.

3

W wariantach wielostronnych oznacz przez

n

liczbę uczestników agregacji lub rozmiar pierścienia. Dla multi-podpisu BLS przyjmij, że wielu podpisujących podpisuje tę samą wiadomość. Dla podpisu agregowanego BLS przyjmij, że agregowane są podpisy pod wiadomości

m_{1}, \dots, m_{n}

. Dla podpisu pierścieniowego BLS przyjmij, że anonimowość uzyskujemy kosztem zależnym od rozmiaru pierścienia

n

.

4

W podpisie RSA-FDH uwzględnij osobno koszt potęgowania przy podpisywaniu i przy weryfikacji.

Oszacuj koszt obliczeniowy Podpisującego i Weryfikującego dla pojedynczego podpisu BLS oraz dla RSA-FDH.
Oszacuj koszt obliczeniowy tworzenia i weryfikacji multi-podpisu BLS jako funkcję liczby podpisujących $n$ . Wyraźnie wskaż koszt po stronie każdego podpisującego, koszt agregacji oraz koszt weryfikacji końcowej.
Oszacuj koszt obliczeniowy tworzenia i weryfikacji podpisu agregowanego BLS dla $n$ podpisów. Wyjaśnij, jak zmienia się liczba wywołań funkcji hash-to-curve, mnożeń grupowych i operacji parowania.
Oszacuj koszt obliczeniowy i pamięciowy podpisu pierścieniowego BLS jako funkcję rozmiaru pierścienia $n$ . Wskaż, które elementy kosztu rosną liniowo z $n$ , a które pozostają stałe.
Porównaj rozmiar podpisu, rozmiar klucza publicznego oraz pamięć roboczą potrzebną przy podpisywaniu i weryfikacji w podpisie BLS, jego trzech wariantach oraz w RSA-FDH.
Wskaż, która operacja dominuje w weryfikacji podpisu BLS i jego wariantów, a która w weryfikacji podpisu RSA-FDH.
Wyjaśnij, dlaczego w protokołach opartych o parowania sama liczba mnożeń grupowych nie wystarcza do uczciwego oszacowania kosztu.

Lista nr 8 — zadanie 5: podpis pierścieniowy Herranza-Sáeza

Punkt odniesienia

1

Weź jako punkt odniesienia poprawny podpis pierścieniowy Herranza-Sáeza z listy nr 5.

2

Traktuj rozmiar pierścienia

n

jako parametr wejściowy.

3

Interesuje nas zarówno koszt obliczeń, jak i długość samego podpisu.

Oszacuj koszt obliczeniowy Podpisującego i Weryfikującego jako funkcję $n$ .
Podaj rozmiar podpisu $σ = (R_{1}, \dots, R_{n}, s)$ w bitach i porównaj go z rozmiarem zwykłego podpisu Schnorra.
Oszacuj pamięć potrzebną do przechowywania wszystkich składników $R_{i}$ i pomocniczych wartości $h_{i}$ .
Wyjaśnij, dlaczego długość podpisu i koszt weryfikacji rosną liniowo z rozmiarem pierścienia oraz jak ten fakt łączy się z analizą anonimowości z listy nr 5.

Lista nr 8 — zadanie 6: poprawny SIGMA

Punkt odniesienia

1

Weź jako punkt odniesienia poprawny protokół SIGMA z listy nr 7.

2

Policz osobno koszt Inicjatora i strony odpowiadającej.

3

Uwzględnij wyznaczenie wspólnego sekretu Diffiego-Hellmana, wyprowadzenie

K_{s}

i

K_{m}

, podpisy oraz MAC.

Oszacuj liczbę najdroższych operacji po stronie obu stron: potęgowań lub mnożeń skalarnych, operacji podpisu, operacji weryfikacji podpisu, wywołań funkcji haszującej i obliczeń MAC.
Oszacuj pamięć roboczą potrzebną do przechowywania wartości efemerycznych, wspólnego sekretu, kluczy $K_{s}$ i $K_{m}$ , podpisów oraz znaczników MAC.
Policz liczbę rund i wiadomości oraz oszacuj ich łączny rozmiar, zakładając że przesyłane są wartości $X$ , $Y$ , klucze publiczne, podpisy i MAC.
Porównaj koszt poprawnego SIGMA z kosztem klasycznego nieuwierzytelnionego Diffiego-Hellmana z listy nr 7 i wskaż, za które własności bezpieczeństwa płacimy dodatkowymi operacjami i komunikacją.

Lista nr 8 — tabela porównawcza

Po przeanalizowaniu wszystkich poprawnych protokołów uzupełnij tabelę porównawczą złożoności.

Protokół	Złożoność obliczeniowa	Złożoność pamięciowa	Złożoność komunikacyjna	Dominująca operacja
Identyfikacja Schnorra
Anonimowy interaktywny Schnorr 1-z- $n$
Podpis Schnorra			brak interakcji; tylko rozmiar podpisu
Podpis BLS			brak interakcji; tylko rozmiar podpisu
Multi-podpis BLS			brak interakcji; tylko rozmiar podpisu
Podpis agregowany BLS			brak interakcji; tylko rozmiar podpisu
Podpis pierścieniowy BLS			brak interakcji; rozmiar podpisu zależny od $n$
Podpis RSA-FDH			brak interakcji; tylko rozmiar podpisu
Podpis pierścieniowy Herranza-Sáeza			brak interakcji; rozmiar podpisu zależny od $n$
SIGMA

Uzupełnij tabelę zarówno w postaci asymptotycznej, jak i w postaci bardziej konkretnej, podając liczbę najdroższych operacji.
Wskaż, które protokoły są najtańsze obliczeniowo, które najtańsze komunikacyjnie, a które najdroższe pamięciowo.
Wyjaśnij, w jaki sposób anonimowość, publiczna weryfikowalność oraz uwierzytelnione uzgadnianie klucza wpływają na koszt protokołu.

Kryptografia — listy nr 1, nr 2, nr 3, nr 4, nr 5, nr 6, nr 7 i nr 8

Zasady zaliczenia ćwiczeń

Demonstrator WASM - klasyczny Schnorr

1. Parametry

2. Klucze

3. Zobowiązanie

4. Wyzwanie

5. Odpowiedź

6. Weryfikacja

Demonstrator BigInt - klasyczny Schnorr w Zp*

1. Parametry

2. Klucze

3. Zobowiązanie

4. Wyzwanie

5. Odpowiedź

6. Weryfikacja

Lista nr 1 — wprowadzenie

Lista nr 1 — zadanie 1: analiza pierwszego schematu

Lista nr 1 — zadanie 2: analiza drugiego schematu

Lista nr 1 — zadanie 3: analiza trzeciego schematu

Lista nr 1 — zadanie 4: analiza czwartego schematu

Lista nr 1 — zadanie 5: analiza piątego schematu

Lista nr 1 — zadanie porównawcze

Lista nr 1 — punkt odniesienia: klasyczny Schnorr

Lista nr 2 — podpisy

Lista nr 2 — punkt odniesienia: poprawny podpis Schnorra

Demonstrator WASM — poprawny podpis Schnorra

1. Parametry

2. Klucze

3. Wiadomość

4. Losowanie r

5. Skrót i podpis

6. Weryfikacja

Demonstrator BigInt — poprawny podpis Schnorra w ℤp*

1. Parametry

2. Klucze

3. Wiadomość

4. Losowanie r

5. Skrót i podpis

6. Weryfikacja

Lista nr 2 — zadanie 1: wariant z h=H(m)

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

Lista nr 2 — zadanie 3: h=mR

Lista nr 2 — zadanie 4: h=m⊕R (XOR)

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

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

Lista nr 2 — tabela porównawcza

Lista nr 3 — podpisy BLS

Lista nr 3 — punkt odniesienia: poprawny podpis BLS

Demonstrator WASM — poprawny podpis BLS

1. Parametry

2. Klucze

3. Wiadomość

4. Hash-to-Curve

5. Podpis

6. Weryfikacja

Lista nr 3 — zadanie 1: stała funkcja H(m)=P0

Lista nr 3 — zadanie 2: liniowa funkcja H(m)=enc(m)P

Lista nr 3 — zadanie 3: zbyt krótki skrót H(m)=τ(m)P

Lista nr 3 — zadanie 4: homomorficzna funkcja H

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

Lista nr 3 — tabela porównawcza

Lista nr 4 — podpisy RSA Full Domain Hash

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

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

Lista nr 4 — zadanie 2: słaba funkcja H(m)=μ2

Lista nr 4 — zadanie 3: słaba funkcja H(m)=gμ

Lista nr 4 — tabela porównawcza

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

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

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

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

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

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

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

Lista nr 5 — zadanie 6: publicznie rozpoznawalny bias generatora

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

Lista nr 5 — tabela porównawcza

Lista nr 6 — anonimowe interaktywne systemy identyfikacji

Lista nr 6 — zadanie 1: anonimowy interaktywny Schnorr

Demonstrator BigInt — poprawny podpis Schnorra w $ℤ_{p} *$

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

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

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

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

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

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

Lista nr 3 — zadanie 1: stała funkcja $H (m) = P_{0}$

Lista nr 3 — zadanie 2: liniowa funkcja $H (m) = enc (m) P$

Lista nr 3 — zadanie 3: zbyt krótki skrót $H (m) = τ (m) P$

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

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

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

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

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

Lista nr 7 — zadanie 3: liniowe domknięcie z wyzwaniami $c$ i $d$

Lista nr 7 — zadanie 4: mnożnikowe wiązanie przez $c$ i $d$

Lista nr 8 — zadanie 2: anonimowy interaktywny Schnorr 1-z- $n$