Kryptografia II stopień

W6. Grupy, klucze i problemy trudne

Publiczna informacja pozwala szyfrować lub sprawdzać wynik, ale nie powinna umożliwiać odzyskania sekretu. Para kluczy rozdziela uprawnienia: do publicznej operacji nie potrzeba prawa do operacji prywatnej. Nadal potrzebujemy sposobu ustalenia, czy publiczny klucz naprawdę należy do zamierzonego partnera.

Grupa, generator i skalar bez skrótów myślowych

Najpierw zapis potęgowy. Do zrozumienia Schnorra, Okamoto czy wymiany Diffiego–Hellmana wystarczą na początek reguły mnożenia potęg. Będziemy pisać $g^a$, także gdy implementacja reprezentuje ten element jako punkt krzywej. Najpierw poznamy rolę sekretu, komunikatów i równania weryfikacji. Dopiero potem połączymy te operacje z działaniami biblioteki.

Grupa to zbiór z odwracalnym, łącznym działaniem, elementem neutralnym i odwrotnościami. Nie oznacza tu grupy użytkowników. Grupa cykliczna $G=\langle g\rangle$ jest generowana przez jeden element $g$: kolejne jego potęgi przechodzą przez wszystkie elementy. Rząd $q$ jest liczbą elementów. Będziemy najczęściej używać pierwszego $q$.

Skalar $a$ jest liczbą z ciała $\mathbb Z_q$, czyli klasą reszt modulo $q$. Symbol $\mathbb Z_q^*$ wyklucza zero. Sekret $a\in\mathbb Z_q^*$ daje klucz publiczny $A=g^a$. Oznaczenia przypominają duże i małe litery celowo: skalar i odpowiadający mu element grupy są różnymi obiektami. Z publicznego $A$ potrafimy wykonywać działania grupowe, ale nie zakładamy znajomości $a$.

Mały przykład do rachunku: w podgrupie modulo $47$ generator $g=2$ ma rząd $q=23$. Dla $a=7$ dostajemy $A=34$. Elementy grupy mnożymy modulo 47, a wykładniki dodajemy i mnożymy modulo 23. Te parametry są zbyt małe do ochrony danych. Ich zadaniem jest pokazanie dwóch różnych miejsc redukcji.

Na krzywej eliptycznej współrzędne punktu również mają własne ciało. Jego charakterystyka nie jest tym samym co rząd podgrupy skalarów. Pomylenie tych liczb daje błędny protokół, nie inny sposób zapisu tego samego rachunku.

Jedno działanie grupowe, dwa sposoby zapisu

Konwencja kursu. Schematy i ich animowane przebiegi objaśniamy najpierw przez iloczyny i potęgi w grupie. Dotyczy to Schnorra, Okamoto, Stinsona–Wu, wymiany klucza i szyfrowania ElGamala. Tak samo zaczynamy objaśnienie BLS. Zapis addytywny pojawia się w wyraźnie oznaczonym przejściu do realizacji na krzywej lub w porównaniu obu notacji. Nie zmieniamy zapisu tylko dlatego, że demonstrator korzysta z MCL.

BLS

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

MCL

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

Biblioteka nie narzuca protokołowi pairingu. MCL wykonuje dodawanie punktów i mnożenie ich przez skalary. Udostępnia też osobną operację pairingu. Schnorr, Okamoto, Stinson–Wu, Diffie–Hellman i ElGamal jej nie potrzebują. Weryfikacja BLS i omawianej zmodyfikowanej identyfikacji rzeczywiście z niej korzysta.

W ciele $\mathbb Z_q$ każdy niezerowy skalar ma odwrotność. Dlatego można rozwiązać równanie $d\cdot a=t$ jako $a=t\cdot d^{-1}$, jeśli $d\ne0$. W grupie łatwo wykonujemy działanie i odwracamy element, ale nie zakładamy możliwości odzyskania wykładnika. Możemy obliczyć $(g^a)^b=g^{a\cdot b}$ znając $b$, nawet gdy nie znamy $a$.

Wykładniki liczymy modulo $q$. Potęga oznacza powtarzanie działania grupowego, a nie obowiązkowo potęgowanie liczby całkowitej. W przykładzie modulo 47 działaniem jest mnożenie reszt. W grupie punktów krzywej to samo rozumowanie korzysta z dodawania punktów. Tych dwóch realizacji nie utożsamiamy jako zbiorów liczb.

W zapisie addytywnym generator oznaczymy przez $P$. Wtedy $a\cdot P$ oznacza wielokrotne dodawanie realizowane wydajnym algorytmem, a $\mathcal O$ jest punktem neutralnym. Przejście z $g^a$ na $a\cdot P$ zmienia notację operacji, nie kolejność komunikatów ani sens sprawdzanego równania. Nie podnosimy osobno współrzędnych punktu do potęgi.

Dla elementów grupy $A,X$ i skalara $c$ otrzymujemy następujący słownik:

Litery $A$ i $X$ oznaczają w obu kolumnach odpowiadające sobie elementy grupy. Nie są skalarami. Sumy w wykładnikach nadal są sumami skalarów. Na przykład odpowiedź $s=u+a\cdot c$ nie zmienia się przy przejściu do zapisu addytywnego.

RFC 8235, §2–3 przedstawia Schnorra w podgrupie multiplikatywnej modulo liczbę pierwszą oraz na krzywej. Dokument używa odpowiedzi z minusem. W tym kursie zachowujemy odpowiedź z plusem i odpowiadające jej równanie weryfikacji. Nie mieszamy tych konwencji.

Od wzoru do programu: rachunek w ciele

Po co ten fragment? Własna implementacja musi umieć wykonać działanie, a nie tylko zapisać jego symbol. Poniższy warsztat rozwija podstawy potrzebne w C0a i L0a. Zaczynamy od reszt całkowitych, przechodzimy do wielomianów, a dopiero potem do współrzędnych punktów. Małe parametry służą nauce i testom. Nie zapewniają bezpieczeństwa.

W ciele można dodawać, odejmować, mnożyć i dzielić przez każdy niezerowy element. Dla pierwszego $p$ ciało $\mathbb F_p$ realizujemy jako reszty $0,\ldots,p-1$. Po działaniu wybieramy jednego reprezentanta przez redukcję modulo $p$. Dla złożonego modułu to ogólnie pierścień, nie ciało. Na przykład $5\cdot5=0$ w $\mathbb Z_{25}$, więc niezerowe $5$ nie ma odwrotności. Ciało o 25 elementach zbudujemy inaczej.

Odwrotność modularna. Rozszerzony algorytm Euklidesa, extended Euclidean algorithm, EEA, oblicza liczby $s,t$ spełniające $s\cdot a+t\cdot n=\gcd(a,n)$. Symbol $\gcd$ oznacza największy wspólny dzielnik, NWD. Gdy NWD wynosi 1, odwrotnością $a$ modulo $n$ jest $s\bmod n$. Gdy NWD jest większy od 1, odwrotność nie istnieje. Nie wolno zastąpić jej ilorazem zmiennoprzecinkowym.

Przykładowo $17=3\cdot5+2$ i $5=2\cdot2+1$. Podstawienie wsteczne daje $1=7\cdot5-2\cdot17$, więc $5^{-1}=7$ w $\mathbb F_{17}$. Ten sam rachunek można prowadzić wraz z resztami. Zacznij od $(r_0,r_1)=(n,a\bmod n)$ i $(s_0,s_1)=(0,1)$. W każdej iteracji oblicz $d=\lfloor r_0/r_1\rfloor$ i jednocześnie zastąp pary przez $(r_1,r_0-d\cdot r_1)$ oraz $(s_1,s_0-d\cdot s_1)$. Po osiągnięciu $r_1=0$ sprawdź $r_0=1$ i zwróć $s_0\bmod n$.

Rozszerzenie ciała: współczynniki zamiast reszt modulo potęgi

Niech $f(t)$ będzie nierozkładalnym wielomianem stopnia $d$ nad $\mathbb F_p$. Definiujemy $\mathbb F_{p^d}=\mathbb F_p[t]/(f)$. Element reprezentujemy przez $a_0+a_1\cdot t+\cdots+a_{d-1}\cdot t^{d-1}$. Współczynniki liczymy modulo $p$, a wynik mnożenia wielomianów redukujemy modulo $f$. To dwie odrębne redukcje, żadna nie jest redukcją całkowitą modulo $p^d$.

• Dodawanie: dodaj współczynniki o tych samych indeksach modulo $p$.
• Mnożenie: wykonaj splot współczynników. Następnie odejmuj odpowiednią wielokrotność $f$, aby usuwać najwyższy wyraz, aż stopień wyniku będzie mniejszy od $d$.
• Dzielenie wielomianów: współczynnik potrzebny do usunięcia najwyższego wyrazu uzyskujemy przez odwrotność współczynnika wiodącego dzielnika w $\mathbb F_p$.
• Odwrotność: wielomianowy EEA znajduje $s(t)\cdot a(t)+v(t)\cdot f(t)=b$, gdzie $b$ jest niezerową stałą. Odwrotność to $b^{-1}\cdot s(t)\bmod f(t)$. Dla zera odrzucamy żądanie.

Dla $p=5$ wybierzmy $f(t)=t^2+2$. Kwadraty modulo 5 to $0,1,4$, a równanie $t^2=3$ nie ma rozwiązania. Wielomian kwadratowy bez pierwiastka jest nierozkładalny. Oznaczając resztę $t$ przez $\alpha$, otrzymujemy $\alpha^2=3$. Na przykład $(2+\alpha)\cdot(4+3\cdot\alpha)=2$ oraz $\alpha^{-1}=2\cdot\alpha$. Każdy z 25 elementów jest parą współczynników, nie pojedynczą resztą modulo 25.

Jak sprawdzić nierozkładalność? Brak pierwiastków wystarcza dla stopnia 2 lub 3. Dla stopnia 4 już nie, bo możliwy jest iloczyn dwóch nierozkładalnych wielomianów kwadratowych. W małych zadaniach sprawdź dzielenie przez wszystkie moniczne wielomiany stopnia od 1 do $\lfloor d/2\rfloor$. Jeżeli żaden nie dzieli $f$, nie ma rozkładu na dwa czynniki dodatnich stopni. To prosta metoda dydaktyczna, nie wydajny algorytm dla dużych parametrów.

Ciało binarne i znaczenie kolejności bitów

W $\mathbb F_2$ dodawanie i odejmowanie to XOR. W laboratoryjnej reprezentacji wielomianu bit numer $i$ od prawej jest współczynnikiem przy $t^i$. Liczba 0x53 oznacza więc $t^6+t^4+t+1$. XOR całych słów dodaje wielomiany, lecz zwykłe mnożenie liczb całkowitych wprowadza przeniesienia i nie mnoży elementów tego ciała.

Mnożenie bez przeniesień wykonujemy tak: ustaw wynik na zero, czytaj kolejne bity drugiego czynnika, a dla każdego bitu 1 dodaj XOR-em odpowiednio przesunięty pierwszy czynnik. Zredukuj wynik wielomianem modułu. Można również redukować po każdym przesunięciu. Nie wolno pomylić tych algorytmów z mnożeniem liczb całkowitych modulo liczbę kodującą wielomian.

W AES modułem jest $f(t)=t^8+t^4+t^3+t+1$, o zapisie 0x11b. Operacja xtime(a) mnoży przez $t$. Przesuń bajt o jeden bit w lewo, zachowaj osiem młodszych bitów i dodaj XOR-em 0x1b, jeśli przed przesunięciem najstarszy bit był równy 1. Dla 0x83 wynik to 0x1d. To właśnie redukcja wyrazu $t^8$, nie dodatkowy sekret szyfru.

Wzory działania i kodowania ciał oraz krzywych zestawia SEC 1, rozdział 2. Rachunek bajtowy AES definiuje FIPS 197, §4.2. Własne obliczenia porównujemy z tymi specyfikacjami i z niezależną implementacją.

GHASH: od bloków do znacznika GCM

To opcjonalne rozwinięcie AEAD z W4. Najpierw potrzebne są powyższe działania w ciele binarnym. GCM używa ciała $\mathbb F_{2^{128}}$ z modułem $t^{128}+t^7+t^2+t+1$. Konwencja bitowa NIST jest odwrotna do powyższego przykładu AES: lewy bit bloku odpowiada współczynnikowi przy $t^0$. Jedynka ciała ma kod 80 i 15 zerowych bajtów. Nie przenosimy bez konwersji reprezentacji z L0a.

Do mnożenia dwóch bloków $U,V$ można bezpośrednio zastosować algorytm 1 standardu. Ustaw $Z=0$, $W=V$ i przeglądaj bity $U$ od lewej. Dla bitu 1 wykonaj $Z\leftarrow Z\oplus W$. Następnie przesuń $W$ o jeden bit w prawo. Jeżeli przed przesunięciem prawy bit $W$ był równy 1, dodaj XOR-em stałą e1 i 15 zerowych bajtów. Po 128 krokach $Z$ jest iloczynem. Kierunek przesunięcia wynika z kodowania współczynników.

Niech $H=\mathsf{AES}_K(0^{128})$ będzie tajnym elementem ciała. To duże $H$ nie oznacza funkcji $\mathcal H$. Dla bloków $S_1,\ldots,S_n$ długości 128 bitów obliczamy

W GCM blokami $S_i$ nie są same bajty wiadomości. Oznaczmy dane dodatkowe przez $A$, a szyfrogram bez znacznika przez $C$. Zbuduj wejście:

Długości mierzymy w bitach. Liczby $v=(-|A|)\bmod128$ i $u=(-|C|)\bmod128$ należą do $\{0,\ldots,127\}$. Symbol $[x]_{64}$ to 64-bitowy zapis liczby $x$ od najbardziej znaczącego bajtu. Dane już wyrównane nie dostają dodatkowego pełnego bloku zer. Blok długości występuje zawsze, nawet przy pustych danych. Pozwala odróżnić rzeczywiste końcowe zera od zer dopełnienia.

Dla przykładu z 2 bajtami AAD i 16 bajtami szyfrogramu wejście ma trzy bloki: AAD i 14 zerowych bajtów, cały szyfrogram oraz dwie 64-bitowe liczby 16 i 128. Nie są to długości 2 i 16. Zmiana długości wpływa więc na wejście uwierzytelnienia, nawet jeśli wartości dopisanych bajtów są zerami.

Przy 96-bitowym nonce $N$ ustal $J_0=N\Vert0^{31}\Vert1$. Pełny 128-bitowy znacznik ma postać $T=\mathsf{AES}_K(J_0)\oplus Y_n$. Licznik szyfrowania danych zaczyna się od zwiększenia prawego 32-bitowego pola $J_0$, więc nie używa tej samej maski co znacznik. Osobno sprawdzamy ograniczenia długości i unikalność nonce. Inna długość nonce wymaga innego wyznaczenia $J_0$, którego ten wariant zadania nie używa.

Punkt kontrolny: dla 128-bitowego zerowego klucza, zerowego 96-bitowego nonce oraz pustych $A,C$ mamy $Y_n=0$ i T = 58e2fccefa7e3061367f1d57a4e7455a. Ten mały przypadek sprawdza maskę i obsługę pustych danych, ale nie wystarcza do testowania mnożenia. Sprawdź także bloki niezerowe i niewyrównane długości. Źródło definicji: NIST SP 800-38D, algorytmy 1–4. Sam GHASH nie jest pełnym MAC ani haszem odpornym na kolizje.

Krzywa nad ciałem pierwszym: wszystkie przypadki działania

Tutaj przechodzimy jawnie do realizacji addytywnej. Niech $p>3$ będzie pierwsze. Dla krzywej $E:y^2=x^3+a_E\cdot x+b_E$ wymagamy $4\cdot a_E^3+27\cdot b_E^2\ne0$ w $\mathbb F_p$. Współczynniki $a_E,b_E$ opisują krzywą, nie klucz użytkownika. Elementy grupy to jej punkty oraz osobny punkt neutralny $\mathcal O$.

Dla $P=(x_1,y_1)$ mamy $-P=(x_1,-y_1)$. Zawsze $P+\mathcal O=P$ i $P+(-P)=\mathcal O$. Dla dwóch pozostałych punktów $P,Q=(x_2,y_2)$ obliczamy nachylenie $\ell$, a potem współrzędne wyniku:

Wszystko liczymy w $\mathbb F_p$, łącznie z odwrotnościami. Dla podwojenia punktu o $y_1=0$ wynikiem jest $\mathcal O$, a nie dzielenie przez zero. Dla poprawnych punktów przypadek tego samego $x$ jest albo podwojeniem, albo dodaniem punktu przeciwnego. Najpierw obsługujemy przypadki wyjątkowe, dopiero potem wzór.

Na krzywej $y^2=x^3+2\cdot x+2$ nad $\mathbb F_{17}$ weźmy $P=(5,1)$. Przy podwojeniu $\ell=(3\cdot25+2)\cdot2^{-1}=13$ w ciele. Dostajemy $2\cdot P=(6,3)$ i po kolejnym dodaniu $3\cdot P=(10,6)$. Każdy wynik ponownie podstaw do równania krzywej. To dobry test kodu, ale nie samodzielny dowód łączności prawa grupowego.

Skalary a współrzędne. Jeżeli $P$ ma pierwszy rząd $q$, to $(k\bmod q)\cdot P=k\cdot P$. Nie wolno zamiast tego redukować $k$ modulo $p$. Współrzędne nadal należą do $\mathbb F_p$. Dla obcych danych najpierw sprawdź poprawne kodowanie i równanie krzywej, następnie podgrupę, a osobno dozwolenie punktu neutralnego. Przy $\#E(\mathbb F_p)=h\cdot q$ i $\gcd(h,q)=1$ warunek $q\cdot Q=\mathcal O$ wybiera jedyną podgrupę rzędu $q$. Bez tego założenia nie przedstawiaj testu jako ogólnego dowodu przynależności do dowolnie wybranej podgrupy.

Opcjonalnie: krzywa w charakterystyce 2

W zadaniu binarnym przyjmujemy $E:y^2+x\cdot y=x^3+a_E\cdot x^2+b_E$ nad $\mathbb F_{2^d}$, z $b_E\ne0$. Nie używamy wzorów dla $p>3$. Tutaj $-(x,y)=(x,x+y)$. Neutralny punkt obsługujemy tak samo jak wcześniej. Dla $x_1\ne x_2$:

Przy $P=Q$ i $x_1\ne0$ używamy $\ell=x_1+y_1\cdot x_1^{-1}$, $x_3=\ell^2+\ell+a_E$ i $y_3=x_1^2+(\ell+1)\cdot x_3$. Przy podwojeniu punktu o $x_1=0$ wynikiem jest $\mathcal O$. Dwa różne poprawne punkty o tym samym $x$ są przeciwne. Dodawanie w tych wzorach oznacza XOR reprezentacji wielomianowych, a mnożenie i odwrotność korzystają z modułu ciała. Dla $a_E=b_E=1$ punkt $(0,1)$ spełnia równanie i ma rząd 2. Reguły prawa grupowego podaje SEC 1, §2.2.

Potęgowanie, drabinka i liczenie operacji

Wróćmy do zapisu multiplikatywnego $B^k$ w dowolnej grupie. Nie mnożymy $k$ razy. Zapisz $k$ binarnie jako bity $b_{\ell-1},\ldots,b_0$, z $b_{\ell-1}=1$ dla $k>0$.

Square-and-multiply, czyli kwadratowanie i mnożenie, zaczyna od $R=B$ i czyta pozostałe bity od lewej. Dla każdego wykonuje $R\leftarrow R^2$, a dla bitu 1 dodatkowo $R\leftarrow R\cdot B$. Dla dodatniego $k$ potrzeba $\ell-1$ kwadratowań i $\operatorname{wt}(k)-1$ dodatkowych mnożeń, gdzie $\operatorname{wt}$ jest liczbą bitów 1. Dla $k=0$ zwracamy element neutralny. Wariant zaczynający od $R=1_G$ i czytający wszystkie bity ma inne liczniki. Dlatego w benchmarku podaj wariant.

Drabinka: zacznij od $(R_0,R_1)=(1_G,B)$ i czytaj wszystkie bity. Dla bitu 0 zastąp parę przez $(R_0^2,R_0\cdot R_1)$, a dla bitu 1 przez $(R_0\cdot R_1,R_1^2)$. Aktualizacja jest jednoczesna. Jeśli dotąd odczytano liczbę $v$, niezmiennikiem jest $(R_0,R_1)=(B^v,B^{v+1})$. Kolejny bit zmienia $v$ na $2v+b$, co uzasadnia obie reguły. Po zakończeniu zwróć $R_0$.

Dla $k=13$, czyli bitów 1101, niezmiennik drabinki opisuje kolejno pary wykładników $(1,2),(3,4),(6,7),(13,14)$. Powyższy wariant wykonuje 4 kwadratowania i 4 mnożenia. Square-and-multiply wykonuje 3 kwadratowania i 2 mnożenia. Dla krzywej kwadratowanie zastępujemy podwojeniem punktu, a mnożenie dodawaniem punktów.

Stała liczba działań nie dowodzi stałego czasu. Warunek zależny od tajnego bitu, dostęp do pamięci i sama arytmetyka dużych liczb mogą ujawniać informacje. Pythonowe przykłady służą rachunkowi i pomiarowi, nie ochronie sekretu przed kanałem czasowym. Podstawy algorytmiczne: Handbook of Applied Cryptography, rozdział 14.

Od elementu matematycznego do jednoznacznych bajtów

Protokół haszuje i przesyła bajty. Umowa musi określać grupę, jej parametry, kolejność bajtów, długość każdego pola i obsługę błędnych danych. Dla małej krzywej dydaktycznej można wybrać wyłącznie nieskompresowany format SEC 1: 04, następnie $x$ i $y$ jako liczby big-endian po $\lceil\log_2(p)/8\rceil$ bajtów. Punkt neutralny ma osobny kod 00. Jego dopuszczenie zależy od roli w protokole. Tych kodów nie przenosimy automatycznie do formatu BLS12-381 biblioteki.

BLS12-381

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

Odbiorca odrzuca złą długość, niewłaściwy znacznik i współrzędne spoza zakresu. Nie redukuje obcej współrzędnej modulo $p$, bo dopuściłby kilka kodowań tego samego punktu. Następnie sprawdza punkt i podgrupę. Dla krotek o zmiennych długościach można poprzedzać każde pole jego 32-bitową długością w bajtach, ustalając limit $2^{32}-1$. Dodaj etykietę protokołu i jego wersji. Para ab, c musi mieć inne kodowanie niż a, bc.

W teście zgodności sprawdź zarówno $\mathsf{Decode}(\mathsf{Encode}(P))=P$, jak i odrzucenie niekanonicznych wejść. Potem porównaj dokładne bajty i wartości hasza między dwoma programami. Dopiero na takiej wspólnej reprezentacji porównujemy podpisy i wspólne sekrety.

Pairing najpierw jako rachunek wykładników

Pairing to wydajnie obliczalne odwzorowanie $e:G_1\times G_2\to G_T$, gdzie grupy mają zgodny pierwszy rząd $q$. W zapisie potęgowym wybierzmy generatory $g_1\in G_1$, $g_2\in G_2$. Dwuliniowość oznacza:

To pozwala sprawdzać relacje pomiędzy ukrytymi wykładnikami, bez ich odczytywania. W demonstratorze te same generatory noszą nazwy $P_1,P_2$, a grupy źródłowe są zapisane addytywnie. Grupa docelowa pozostaje multiplikatywna:

Niedegeneracja wymaga, aby pairing odpowiednich generatorów nie dawał elementu neutralnego. Typy mają znaczenie: pierwszy argument należy do $G_1$, drugi do $G_2$. W używanym typie asymetrycznym nie zakładamy wydajnego przenoszenia dowolnego punktu pomiędzy tymi grupami. MCL reprezentuje je odrębnymi typami, a wynik parowania ma typ $G_T$.

WebAssembly

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

Pełny zapis elementu $G_T$ jest długi, ponieważ reprezentuje element rozszerzenia ciała. Porównujemy całe obiekty MCL, nie ich skrócone etykiety na rysunku. Zmiana wykładnika z $x\cdot y$ na $x\cdot y+1$ jest testem negatywnym. Punkty oraz obie strony równania powstają w MCL WebAssembly.

Hasze mają różne typy wyników

Teraz znamy zarówno ciało skalarów, jak i grupy pairingu. Możemy precyzyjnie rozdzielić funkcje, które wcześniej nazywaliśmy ogólnie haszami. Indeks $G_1$ oznacza poprawne haszowanie do grupy, nie publicznie znany logarytm wyniku.

Co zakładamy jako trudne

Najpierw motywacja: Alicja publikuje $A=g^a$, Bob publikuje $B=g^b$. Alicja zna $a$, więc liczy $B^a$. Bob zna $b$, więc liczy $A^b$. Oba wyniki to $g^{a\cdot b}$. Podsłuchujący widzi $g,A,B$, lecz nie dostaje $a,b$. To rdzeń wymiany Diffiego–Hellmana (DH). Na razie wyjaśnia tylko zgodność obliczeń. Nie potwierdza tożsamości, co będzie głównym problemem W10.

DL oznacza logarytm dyskretny. CDH to obliczeniowy problem DH, a DDH to decyzyjny problem DH. W DDH porównujemy krotkę z prawdziwym wspólnym elementem i krotkę, której ostatni element jest losowany niezależnie, jednostajnie w tej samej grupie.

DL

discrete logarithm / discrete logarithm problem. Logarytm dyskretny / problem logarytmu dyskretnego.

CDH

Computational Diffie–Hellman. Obliczeniowy problem Diffiego–Hellmana.

Algorytm DL rozwiązuje CDH, a CDH pozwala testować DDH. Odwrotne implikacje nie wynikają z tej obserwacji. Pairing może zmienić trudność problemu decyzyjnego, dlatego określamy grupy i dostępne reprezentacje.

W7. Identyfikacja: Schnorr, symulacja i ekstrakcja

Potrzeba: weryfikator chce teraz sprawdzić, czy rozmówca kontroluje sekret przypisany do zarejestrowanego klucza. Klucz publiczny musi być wcześniej powiązany z kontem lub osobą. Sam protokół nie ustala nazwiska na podstawie równania.

Interfejs identyfikacji interaktywnej

Schemat ma parametry, generowanie kluczy oraz dwa współdziałające algorytmy:

Algorytm $\mathsf P$ (prover, dowodzący) działa z kluczem tajnym. Algorytm $\mathsf V$ (verifier, weryfikator) korzysta z klucza publicznego. Oba utrzymują lokalny stan sesji i wymieniają komunikaty. Zapis

oznacza wykonanie rozmowy i odczyt decyzji weryfikatora. Bit $b=1$ oznacza akceptację. Klamry kątowe nie są iloczynem skalarnym ani pojedynczą funkcją wykonywaną przez jedną stronę. Poprawność wymaga, aby uczciwa rozmowa dla kluczy z KeyGen kończyła się akceptacją. Odporność na podszywanie mówi osobno, że przeciwnik bez wymaganego sekretu nie powinien doprowadzić do takiej akceptacji w dozwolonym modelu.

Własność ZK, zero knowledge, czyli wiedzy zerowej, jest dodatkowym wymaganiem dotyczącym ujawnianej informacji. Nie każdy protokół identyfikacji ją spełnia. Dla trójwiadomościowego Schnorra poniżej najpierw wykażemy dokładnie HVZK, wiedzę zerową wobec uczciwego weryfikatora. Nie będziemy jej utożsamiali z ochroną przed dowolnym zachowaniem rozmówcy.

HVZK

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

Schnorr jako zestaw wywołań

Używamy grupy $G$ pierwszego rzędu $q$, generatora $g$ i parametrów $pp=(G,q,g)$. Setup wybiera taki profil. KeyGen losuje $a\overset{\$}{\leftarrow}\mathbb Z_q$ i zwraca $(pk,sk)=(A,a)$, gdzie $A=g^a$. Teraz rozpiszmy lokalne kroki $\mathsf P$ i $\mathsf V$. Ich nazwy są naszym opisem interfejsu, nie dodatkowymi założeniami protokołu.

Co pozostaje w urządzeniu, a co trafia do rozmówcy

Każdy stan jest przypisany do jednej lokalnej sesji. Nie wolno użyć tego samego $st_P$ do odpowiedzi na drugie wyzwanie. Matematyka nie usuwa konieczności pilnowania tej reguły w urządzeniu. Właśnie jej złamanie wykorzystamy później w ataku z resetem. W poprawnym wykonaniu sekret $a$ służy wyłącznie do lokalnego wywołania Respond.

Mechanizm i poprawność

Chcemy przekonać weryfikatora, że znamy $a$ dla $A=g^a$, bez wysyłania sekretu. Publiczne $A$ jest stwierdzeniem, a $a$ świadkiem jego prawdziwości w odpowiedniej relacji. Nie wystarcza samo zapewnienie, że klucz istnieje. Każdy element tej grupy ma logarytm. Istotna jest znajomość odpowiedniej wartości.

Zerowa wiedza dotyczy tego, co rozmowa ujawnia. Dowód znajomości dotyczy możliwości wydobycia świadka z odpowiednio skutecznego dowodzącego w modelu ekstrakcji. To dwa warunki, które należy argumentować oddzielnie.

Dowodzący zna sekret $a$. Losuje niezależny, jednorazowy skalar $u\overset{\$}{\leftarrow}\mathbb Z_q$ i oblicza zobowiązanie $X$. Weryfikator po otrzymaniu $X$ losuje wyzwanie $c$. Odpowiedź oznaczymy przez $s$. Schnorr ma trzy wiadomości:

Dowodzący wysyła $X$ przed otrzymaniem $c$. Weryfikator sprawdza $g^s=X\cdot A^c$. Podstawienie dowodzi kompletności. Nie dowodzi jeszcze wiedzy zerowej ani znajomości sekretu przez oszusta.

Cała kontrola poprawności mieści się w prawach działań na potęgach:

Weryfikator zna $g,A,X,c,s$. Do tego obliczenia nie potrzebuje ani $a$, ani $u$. Przy poprawnych parametrach i wejściach sprawdza zgodność elementów grupy, nie odczytuje ukrytych wykładników.

Przebieg, który można policzyć ręcznie

Dla $g=2$ modulo 47, rzędu $q=23$, sekretu $a=7$ i nonce $u=9$ mamy $A=34$ i $X=42$. Przy wyzwaniu $c=3$ odpowiedź wynosi $s=9+7\cdot3=7\bmod23$. Weryfikator oblicza $2^7=34\bmod47$ oraz $42\cdot34^3=34\bmod47$. Wyniki są zgodne.

Widać przy tym, dlaczego kolejność ma znaczenie. Dowodzący ustala zobowiązanie, zanim pozna wyzwanie. Gdyby znał wyzwanie wcześniej, mógłby dobrać $X$ do dowolnej odpowiedzi. Właśnie ten rachunek wykorzystuje następny podrozdział, ale w innym celu.

Symulator bez sekretu

Losujemy $c,s$ i obliczamy $X=g^s\cdot A^{-c}$. Dla ustalonego $a,c$ przesunięcie $u\mapsto u+a\cdot c$ jest bijekcją ciała. Uczciwe i symulowane transkrypty mają dokładnie ten sam rozkład przy jednostajnej losowości z całego $\mathbb Z_q$.

Gdy implementacja wyklucza zerowy nonce. Profil notebooka w L3 losuje $u\ne0$ i odrzuca $X=1_G$, gdzie $1_G$ jest elementem neutralnym. W notacji addytywnej to punkt $\mathcal O$. Symulator tego profilu losuje $c,s$ z całego $\mathbb Z_q$, oblicza $X=g^s\cdot A^{-c}$ i powtarza losowanie pary, jeśli $X=1_G$. Warunkujemy oba rozkłady tym samym zdarzeniem. Dla każdego $c$ odpada dokładnie jedna wartość $s=a\cdot c$, zatem próba jest przyjmowana z prawdopodobieństwem $(q-1)/q$. Każdy pozostały transkrypt ma prawdopodobieństwo $1/(q\cdot(q-1))$. Symulator nadal nie potrzebuje $a$. Nie wolno porównywać tego rozkładu z niezmienionym symulatorem, który dopuszcza neutralne zobowiązanie.

W obu opisach wyzwanie pochodzi z całego $\mathbb Z_q$. Jeśli pokazujemy atak z ujawnionym nonce i dzieleniem przez $c$, demonstrator wybiera $c\ne0$, aby wykonać ten konkretny rachunek. To jawne ograniczenie przykładu, a nie zmiana definicji wszystkich protokołów Schnorra.

To HVZK, wiedza zerowa dla uczciwego weryfikatora. Symulator wybiera wyzwanie przed zobowiązaniem. Nie podszywa się więc automatycznie pod dowodzącego w żywej rozmowie. Złośliwy weryfikator może uzależnić wyzwanie od zobowiązania, co wymaga odrębnego argumentu.

Co porównujemy w definicji? Widok weryfikatora obejmuje komunikaty, jego wejście i własną losowość. Symulator ma wytworzyć nierozróżnialny widok bez świadka. Wersja doskonała daje równe rozkłady, statystyczna małą odległość rozkładów, a obliczeniowa nierozróżnialność dla wydajnego testu. W prostym przykładzie Schnorra dla uczciwego weryfikatora otrzymujemy równość rozkładów.

Dwa transkrypty ujawniają świadka

Przy tym samym $X$ i $c\ne c'$:

Dzielimy równania, skracamy $X$ i korzystamy z pierwszego rzędu grupy. Ekstraktor nie zakłada, że przeciwnik policzył odpowiedź uczciwym algorytmem. Wystarczają dwa zaakceptowane równania.

To szczególna rzetelność protokołu, nazywana special soundness. Jeden transkrypt nie wystarcza: symulator właśnie potrafi go stworzyć bez sekretu. Oszust może przygotować odpowiedź na zgadnięte wyzwanie. Błąd wiedzy dla pełnej przestrzeni wyzwań jest związany z $1/q$. Dopiero odpowiedni sukces ponad ten próg i możliwość cofnięcia stanu pozwalają uzasadnić ekstrakcję.

Ten sam Schnorr w implementacji na krzywej

Punkt $P_2$ pełni tu rolę generatora $g$. MCL wykonuje rzeczywiste mnożenia punktów przez skalary na BLS12-381. Zmienia się reprezentacja operacji, nie protokół. Klucze są demonstracyjne.

Co pozostaje po pierwszym przebiegu? Przeciwnik zna publiczny klucz $A$ i trzy komunikaty $(X,c,s)$. Nie zna $a$ ani $u$. Reset w drugim przebiegu przywraca ten sam nonce, więc ponownie pojawia się to samo $X$. Weryfikator przesyła inne wyzwanie $c'$, dopiero potem otrzymuje odpowiedź $s'$. Oba transkrypty dotyczą jednego klucza publicznego. Odjęcie odpowiedzi usuwa nieznany nonce. Ekstrakcja wykorzystuje wyłącznie zapisane komunikaty, a poprawność wyniku można sprawdzić publicznie przez $g^a=A$.

Reset rzeczywistego urządzenia jest tu uprawnieniem atakującego. Przewijanie przeciwnika w dowodzie jest natomiast narzędziem ekstraktora. W obu sytuacjach przydatny jest ten sam rachunek dwóch transkryptów, lecz nie są to te same możliwości w rzeczywistym protokole. Ujawnienie nonce to jeszcze inny przypadek: wystarcza jedna rozmowa i poznane $u$, o ile $c\ne0$.

Powiązania: C5, L3, pełny dowód identyfikacji i rachunek rewindingu.