Kryptografia — lista nr 1

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$ , 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 —

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

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.

1. Wprowadzenie do listy

We wszystkich zadaniach zakładamy, że $G = ⟨ g ⟩$ jest grupą cykliczną rzędu $q$ , a sekret Dowodzącego ma postać $a \in ℤ_{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.

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

.

4

Weryfikator akceptuje wtedy i tylko wtedy, gdy

g^{s} = X A 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$ .

3. 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)

.

4

Weryfikator sprawdza, czy

g^{s} = {(A 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ę.

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

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.

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

oraz

W = g^{a x}

.

4

Weryfikator sprawdza, czy

g^{s} = g^{c} 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?

6. 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)

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

4

Weryfikator akceptuje, gdy

g^{s} = {(A X^{c} W)}^{c} 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.

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

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

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.

8. Odniesienie do schematu Schnorra

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

.

4

Weryfikator sprawdza, czy

g^{s} = X 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.