Kryptografia II stopień

W10b. RSA: od arytmetyki do szyfrowania i podpisu

Jedna para odwrotnych operacji nie jest jeszcze dwoma bezpiecznymi schematami. RSA daje publiczne potęgowanie, które łatwo odwrócić posiadaczowi sekretu. Szyfrowanie musi dodatkowo ukrywać wiadomość. Podpis musi wiązać wynik z dokumentem tak, aby przeciwnik nie potrafił stworzyć nowej akceptowanej pary. Dlatego obie funkcjonalności potrzebują innych kodowań.

Setup i KeyGen: wspólna podstawa RSA

Setup przyjmuje $1^\lambda$ i ustala profil $pp$: rozmiar modułu, reguły generowania kluczy, kodowania oraz parametry konkretnego szyfrowania albo podpisu. KeyGen przyjmuje $pp$ i zwraca parę $(pk,sk)$. W zapisie podstawowym $pk=(N,e)$, a $sk=(N,d)$. Implementacja może dodatkowo zachować tajne czynniki i współczynniki CRT. Zaraz wyjaśnimy, skąd biorą się te liczby.

CRT

Chinese Remainder Theorem. Chińskie twierdzenie o resztach.

Dwie kompletne konstrukcje mają odrębne krotki: $\Pi_{\mathrm{OAEP}}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ oraz $\Pi_{\mathrm{PSS}}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Sign},\mathsf{Verify})$. Wspólna arytmetyka nie oznacza zalecenia ponownego użycia tego samego klucza w różnych protokołach.

Dlaczego można odwrócić potęgowanie

Zaczynamy od największego wspólnego dzielnika, oznaczanego $\gcd(a,b)$. Na przykład $\gcd(12,18)=6$. Gdy $\gcd(e,L)=1$, rozszerzony algorytm Euklidesa znajduje całkowite $d,t$ spełniające $e\cdot d+L\cdot t=1$. Zatem $d$ jest odwrotnością $e$ modulo $L$.

Funkcja Eulera $\varphi(N)$ liczy, ile liczb ze zbioru $\{1,\ldots,N-1\}$ jest względnie pierwszych z $N$, czyli ma z $N$ największy wspólny dzielnik równy 1. Na przykład $\varphi(8)=4$, bo warunek ten spełniają dokładnie $1,3,5,7$. Te klasy reszt tworzą grupę $\mathbb Z_N^*$, więc $\varphi(N)=|\mathbb Z_N^*|$.

Chińskie twierdzenie o resztach, CRT, mówi tutaj, że para reszt modulo różne liczby pierwsze $p,r$ wyznacza dokładnie jedną resztę modulo $p\cdot r$. Przykładowo liczba równa 2 modulo 3 i 3 modulo 5 to 8 modulo 15. Dlatego późniejsze wykazanie równości modulo oba czynniki wystarczy do równości modulo ich iloczyn.

Wybieramy dwie różne duże nieparzyste liczby pierwsze $p,r$. Litera $r$ oznacza tu drugi czynnik modułu, nie losowość protokołu. Dla ich iloczynu mamy:

Skąd ten iloczyn? Odwracalna reszta modulo $N$ musi być niezerowa zarówno modulo $p$, jak i modulo $r$. Mamy odpowiednio $p-1$ i $r-1$ możliwości. CRT przyporządkowuje każdej takiej parze dokładnie jeden element $\mathbb Z_N^*$.

Wykładnik publiczny $e$ wybieramy tak, aby $3\le e<N$ i $\gcd(e,\varphi(N))=1$. Następnie obliczamy wykładnik prywatny $d$ jako dodatnią odwrotność $e$ modulo $\varphi(N)$:

Zapis $e^{-1}$ oznacza tutaj odwrotność modularną, nie ułamek $1/e$. Równoważnie $e\cdot d=1+k\cdot\varphi(N)$ dla pewnej liczby całkowitej $k$. Klucz publiczny to $(N,e)$, a prywatny to $(N,d)$. Czynniki $p,r$ i wartość $\varphi(N)$ również pozostają tajne. Implementacja może zachować dodatkowe współczynniki CRT. Tutaj $e$ nie oznacza pairingu.

Dlaczego odzyskujemy wejście? Dla $x\in\mathbb Z_N^*$ twierdzenie Eulera daje $x^{\varphi(N)}\equiv1\pmod N$. Stąd:

RSA działa także dla reprezentantów $x\in\{0,\ldots,N-1\}$, które nie należą do $\mathbb Z_N^*$. Nie wolno wtedy bezpośrednio użyć twierdzenia Eulera. Aby uzasadnić odzyskanie $x$ z $y=x^e\bmod N$, rozpatrujemy osobno dwa przypadki modulo $p$:

• Jeżeli $x=0\bmod p$, również $x^{e\cdot d}=0\bmod p$.
• W przeciwnym przypadku małe twierdzenie Fermata daje $x^{p-1}=1\bmod p$. Ponieważ $p-1$ dzieli $\varphi(N)$, otrzymujemy $x^{e\cdot d}=x\bmod p$.

Ten sam argument działa modulo $r$. CRT daje zatem

To wyjaśnia poprawność także wtedy, gdy $x$ nie jest odwracalne modulo $N$. Natomiast założenie RSA, użyte później w dowodzie FDH, dotyczy znalezienia pierwiastka losowego elementu grupy $\mathbb Z_N^*$. Faktoryzacja wystarcza do odwracania RSA. Ogólnej równoważności tych problemów nie znamy.

Mały rachunek do sprawdzenia: $p=61$, $r=53$, $N=3233$, $\varphi(N)=60\cdot52=3120$, $e=17$, $d=2753$. Mamy $17\cdot2753=46801=1+15\cdot3120$. Dla $x=65$ otrzymujemy $y=2790$, a $2790^{2753}\bmod3233=65$. To liczby do nauki, nie parametry ochrony danych.

Związek z zapisem w standardzie. LCM (least common multiple) to najmniejsza wspólna wielokrotność. W PKCS #1, RFC 8017, §3.2 wystarcza słabszy warunek $e\cdot d\equiv1\pmod{\lambda(N)}$, gdzie funkcja Carmichaela dla naszego modułu spełnia:

PKCS

Public-Key Cryptography Standards. Seria standardów kryptografii z kluczem publicznym.

Ostatni symbol oznacza, że $\lambda(N)$ dzieli $\varphi(N)$. Dlatego wybór $d$ według funkcji Eulera spełnia także warunek standardu. To nie są jednak te same funkcje ani identyczne warunki na $d$. W naszym przykładzie $\lambda(N)=780$, a $\varphi(N)=3120$. Wartość $d'=413$ spełnia warunek modulo $780$, lecz nie modulo $3120$. Mimo to wykonuje tę samą prywatną operację RSA co $2753$, ponieważ wykładniki różnią się o $3\cdot780$. Funkcji $\lambda(N)$ nie należy też mylić z parametrem bezpieczeństwa $\lambda$ w Setup.

Wprowadzenie używa funkcji Eulera, aby bezpośrednio powiązać wybór kluczy z liczbą elementów grupy i twierdzeniem o potęgowaniu. Tę podstawę przedstawia także oryginalna praca Rivesta, Shamira i Adlemana, §§V–VI. Przy korzystaniu z biblioteki obowiązuje jej profil generowania kluczy, nie mały przykład dydaktyczny.

Dlaczego „surowe RSA” nie wystarcza

Szyfrowanie deterministyczne zdradza porównanie. Przeciwnik wybiera dwie wiadomości, sam liczy ich potęgi publicznym kluczem i porównuje wynik z wyzwaniem. Nie musi odwracać żadnej potęgi.

Algebra pozwala zmieniać szyfrogram. Dla $c=x^e\bmod N$ i wybranego $a\in\mathbb Z_N^*$:

To podobna lekcja jak przy ElGamalu: odwracalność rachunku nie oznacza odporności na aktywną modyfikację. „Podpis” $\sigma=x^d\bmod N$ bez kodowania również zawodzi. Przeciwnik wybiera $\sigma$, oblicza $x=\sigma^e\bmod N$ i ma akceptowaną parę bez pytania o podpis. Nie wybrał wcześniej treści $x$, ale już to łamie podstawowy cel egzystencjalnej niepodrabialności w tak zdefiniowanej domenie wiadomości.

RSA-OAEP

RSA-OAEP

RSA Encryption Scheme with Optimal Asymmetric Encryption Padding. Schemat szyfrowania RSA z kodowaniem OAEP.

Cel: szyfrować krótką wiadomość kluczem publicznym RSA, stosując losowe kodowanie OAEP przed potęgowaniem. Parametry RSA i konwersje bajtów z poprzedniej części pozostają bez zmian. Teraz określamy pełny interfejs szyfrowania, a następnie rozpisujemy wnętrze kodowania i jego kontroli.

OAEP

Optimal Asymmetric Encryption Padding. Kodowanie wiadomości przed szyfrowaniem asymetrycznym.

Enc: kodowanie i publiczna potęga

Wejście: profil $pp$, klucz publiczny $(N,e)$ i wiadomość bajtowa $M$ dopuszczalnej długości. Etykieta $L$ jest uzgodnionym jawnym parametrem kontekstu, a nie sekretem. Wyjście: szyfrogram $C$ długości modułu w bajtach. Przekroczenie limitu wejścia oznacza błąd szyfrowania.

RSAES-OAEP szyfruje ciąg bajtów $M$, nie dowolnie duży plik jedną potęgą. Niech $k$ oznacza długość modułu w bajtach, $h$ długość skrótu, a $L$ uzgodnioną etykietę kontekstu. Funkcja $\operatorname{Hash}$ poniżej zwraca bajty, nie skalar ani punkt krzywej. $\operatorname{MGF1}(s,\ell)$ rozwija zalążek $s$ do $\ell$ bajtów przez haszowanie zalążka z kolejnymi czterobajtowymi licznikami i obcięcie wyniku do zadanej długości.

MGF1

Mask Generation Function. Funkcja generowania maski. MGF1 oznacza konkretną konstrukcję tej funkcji.

1. Tworzymy $\mathrm{DB}=\operatorname{Hash}(L)\mathbin\Vert\mathrm{PS}\mathbin\Vert\mathtt{01}\mathbin\Vert M$. $\mathrm{PS}$ jest odpowiednio długim ciągiem zer.
2. Losujemy niezależny zalążek $s$ długości $h$ bajtów.
3. Maskujemy blok: $\mathrm{maskedDB}=\mathrm{DB}\oplus\operatorname{MGF1}(s,k-h-1)$.
4. Maskujemy zalążek: $\mathrm{maskedSeed}=s\oplus\operatorname{MGF1}(\mathrm{maskedDB},h)$.
5. Łączymy $\mathrm{EM}=\mathtt{00}\mathbin\Vert\mathrm{maskedSeed}\mathbin\Vert\mathrm{maskedDB}$. Zamieniamy bajty na liczbę, podnosimy do $e$ modulo $N$ i zapisujemy wynik w dokładnie $k$ bajtach.

Dec: prywatna potęga i kontrola kodowania

Wejście: profil $pp$, klucz tajny $(N,d)$, szyfrogram $C$ i ta sama uzgodniona etykieta $L$. Wyjście: odzyskana wiadomość $M$ albo $\bot$. Sprawdzamy długość i zakres reprezentanta szyfrogramu. Następnie wykonujemy operację prywatną. Zdejmujemy maski w odwrotnej kolejności i kontrolujemy całe kodowanie, w tym skrót etykiety. Błędne kodowanie oznacza odrzucenie. Różne szczegóły błędów i czasy ich obsługi nie powinny tworzyć wyroczni dla napastnika.

PSS

Probabilistic Signature Scheme. Probabilistyczny schemat podpisu.

RSASSA-PSS

RSA Signature Scheme with Appendix, with Probabilistic Signature Scheme encoding. Podpis RSA z kodowaniem PSS. Wiadomość towarzyszy podpisowi, a nie jest z niego odzyskiwana.

EMSA-PSS

Encoding Method for Signature with Appendix, Probabilistic Signature Scheme. Metoda kodowania wiadomości dla podpisu PSS.

Ograniczenie długości wynosi $|M|\le k-2\cdot h-2$. Dla modułu 2048-bitowego i SHA-256 to $256-64-2=190$ bajtów. Praktyczna ochrona większych danych używa konstrukcji hybrydowej, np. szyfruje losowy klucz danych, a sam plik chroni AEAD. Dokładny format i kompozycję wybiera się z konkretnego protokołu.

RSA-PSS

Cel: podpisać wiadomość za pomocą RSA i umożliwić publiczne sprawdzenie podpisu. PSS określa kodowanie podpisywanego skrótu z losową solą oraz jego kontrolę. Nie jest szyfrowaniem wiadomości kluczem prywatnym.

Sign: kodowanie i prywatna potęga

Wejście: profil $pp$, klucz tajny $(N,d)$ i wiadomość $M$. Profil określa hasz, MGF1 i długość soli. Wyjście: podpis $\sigma$, zapisany w dokładnie tylu bajtach co moduł. Wiadomości nie szyfrujemy.

W RSASSA-PSS wiadomość pozostaje dostępna weryfikatorowi. Celem jest jej uwierzytelnienie, nie ukrycie. Najpierw liczymy skrót $h_M=\operatorname{Hash}(M)$ i losujemy sól. Następnie:

Zapis $\mathtt{00}^{8}$ oznacza osiem zerowych bajtów. Budujemy blok zer, separator $\mathtt{01}$ i sól. Maskujemy ten blok przez MGF1 wywołaną na $h'$. Zerujemy wymagane najwyższe bity i dołączamy $h'$ oraz końcowy bajt $\mathtt{bc}$. Kodowanie używa $\operatorname{bitlen}(N)-1$ bitów. Jego reprezentanta podnosimy do $d$ modulo $N$.

Verify: kontrola zgodności z wiadomością

Wejście: profil $pp$, klucz publiczny $(N,e)$, wiadomość $M$ i podpis $\sigma$. Wyjście: 1 albo 0. Weryfikator sprawdza długość i zakres podpisu, podnosi jego reprezentanta do $e$, sprawdza format, odzyskuje sól i przelicza zależność z wiadomością. Zwraca 1 wyłącznie po przejściu wszystkich kontroli. Nie „odszyfrowuje podpisanego dokumentu”. Dwa podpisy tej samej wiadomości zwykle się różnią dzięki soli. Różne wyniki nie oznaczają różnych kluczy.

Jeszcze nie wykonano obliczeń.

Co należy do standardu, a co do implementacji

RSAEP

RSA Encryption Primitive. Podstawowa operacja szyfrująca RSA.

RSADP

RSA Decryption Primitive. Podstawowa operacja deszyfrująca RSA.

Podstawowym dokumentem mechanizmów jest PKCS #1 v2.2, RFC 8017, §§3–9. Jest to uzgodniona specyfikacja opublikowana jako RFC kategorii Informational. Dobór parametrów, kodowania kluczy i dozwolonych algorytmów należy dodatkowo do profilu wdrożenia. Nie przenosimy dawnych domyślnych parametrów dokumentu do nowej aplikacji bez sprawdzenia.

Obliczenia prywatne zwykle przyspiesza CRT. Dla wejścia $y$ liczymy $y^{d\bmod(p-1)}\bmod p$ i $y^{d\bmod(r-1)}\bmod r$, a potem składamy wynik. Implementacja musi chronić się przed kanałami bocznymi i błędami obliczeń. Blinding losowo przekształca wejście przed tajną operacją i usuwa maskę po niej. Samo użycie CRT nie daje tych zabezpieczeń.

RSA może podpisywać transkrypt w TLS 1.3, ale TLS 1.3 nie stosuje starej wymiany klucza przez szyfrowanie RSA. To przykład, dlaczego nazwa algorytmu nie określa jeszcze jego roli. Zobacz RFC 8446, §§1.2 i 4.2.3. Wymagania dla generowania kluczy i podpisów RSA oraz ECDSA opisuje także FIPS 186-5. RSA nie jest postkwantowe. Zwiększenie modułu nie zastępuje migracji do innej rodziny problemów, omawianej w W15.

TLS

Transport Layer Security. Protokół ochrony komunikacji, zapewniający m.in. poufność i integralność.

ECDSA

Elliptic Curve Digital Signature Algorithm. Algorytm podpisu cyfrowego na krzywych eliptycznych.

Powiązania: dowód RSA-FDH, C17, L12.

W10c. RSA-FDH: sfałszowany podpis rozwiązuje trudne zadanie

W dowodzie Schnorra potrzebujemy dwóch odpowiedzi i odejmowania równań. W RSA-FDH jeden właściwie umieszczony podpis może już być rozwiązaniem instancji RSA. Trudność polega na przygotowaniu symulacji, która nie zna klucza prywatnego, a mimo to odpowiada na legalne żądania podpisów.

RSA-FDH: algorytmy i cel przeciwnika

Jest to schemat $\Pi_{\mathrm{FDH}}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Sign},\mathsf{Verify})$. Setup ustala profil RSA oraz regułę haszowania do pełnej domeny właściwego modułu. KeyGen tworzy $pk=(N,e)$ oraz $sk=(N,d)$ zgodnie z opisem kluczy RSA. Dopiero dla tego $N$ określona jest docelowa grupa hasza. Sign przyjmuje $pp$, $sk$ i wiadomość $m$, a zwraca $\sigma\in\mathbb Z_N^*$. Verify przyjmuje $pp$, $pk$, $m$ i $\sigma$, a zwraca 1 albo 0. Szczegóły haszowania odróżniają ten schemat od PSS.

Używamy klucza RSA $(N,e)$ z poprzedniego rozdziału. Oznaczenie $\mathcal H_{\mathrm{FDH}}$ dotyczy osobnej wyroczni o pełnej domenie wyjściowej RSA:

Weryfikacja wymaga reprezentanta $0\le\sigma<N$ i równości $\sigma^e=\mathcal H_{\mathrm{FDH}}(m)\bmod N$. Indeks FDH odróżnia tę funkcję od $\mathcal H$ do $\mathbb Z_q$ i $\mathcal H_{G_1}$ do grupy krzywej. Sam krótki SHA-256 zamieniony na liczbę nie jest losowaniem z pełnej grupy $\mathbb Z_N^*$.

W eksperymencie EUF-CMA przeciwnik $\mathcal A$ dostaje klucz publiczny. Może adaptacyjnie pytać wyrocznię losową i wyrocznię podpisującą. Wygrywa, jeżeli zwróci akceptowaną parę $(m^*,\sigma^*)$, przy czym $m^*$ nigdy nie było pytaniem do wyroczni podpisującej. Samo wcześniejsze zapytanie o hasz $m^*$ jest dozwolone. Nie wymagamy, aby przeciwnik odzyskał $d$.

Symulator wybiera miejsce trudności przed uruchomieniem ataku

Algorytm redukcji $\mathcal B$ dostaje $(N,e,Y)$, gdzie $Y$ jest losowe w $\mathbb Z_N^*$. Jego celem jest znaleźć $z$ takie, że $z^e=Y\bmod N$. Nie zna $d$, $p$ ani $r$.

Niech $q_H$ ogranicza liczbę zapytań przeciwnika o hasz, a $q_S$ liczbę żądań podpisu. Ustawiamy $Q=q_H+q_S+1$. Dodatkowa jedynka pozwala utworzyć wpis podczas końcowej weryfikacji, nawet jeśli przeciwnik nie pytał wcześniej o hasz sfałszowanej wiadomości. Redukcja losuje $J$ jednostajnie z $\{1,\ldots,Q\}$ przed uruchomieniem $\mathcal A$. Pozycje liczą różne wiadomości w tabeli, a nie powtórzenia zapytań.

Symbol $\bot$ oznacza brak znanego pierwiastka. Programowanie wyroczni nie daje przeciwnikowi prawa do zmiany hasza. Jest narzędziem redukcji w idealizowanym modelu. Zwykła implementacja nie może przestawiać SHA-256 na życzenie.

Jedna prywatna tabela, dwa publiczne interfejsy

Redukcja przechowuje dla każdej wiadomości parę $T[m]=(h_m,u_m)$. Pierwsza składowa jest odpowiedzią na zapytanie o hasz. Druga jest znanym podpisem, jeżeli redukcja potrafi go przygotować. Obie wyrocznie najpierw sprawdzają tę samą tabelę. Nie prowadzą niezależnych losowań dla tej samej wiadomości.

Przy zwykłym nowym wpisie redukcja zaczyna od jednostajnego $u_m\in\mathbb Z_N^*$. To będzie podpis. Następnie wylicza $h_m=u_m^e\bmod N$ i zapisuje obie wartości. Jeżeli przyszło zapytanie o hasz, zwraca tylko $h_m$. Jeżeli przyszło żądanie podpisu, zwraca tylko $u_m$. Kolejne zapytanie drugiego rodzaju korzysta z już gotowej pary. Nie modyfikuje wcześniej ujawnionego hasza.

1. Najpierw Hash: powstaje para $(h_m,u_m)$, ale przeciwnik otrzymuje tylko hasz. Potencjalny podpis pozostaje prywatny do żądania Sign.
2. Najpierw Sign: powstaje ta sama para, przeciwnik otrzymuje podpis, a przyszła odpowiedź Hash jest już ustalona. Przeciwnik może również sam obliczyć publiczne $u_m^e$.
3. Powtórzone pytanie: odczyt z tabeli bez ponownego losowania. FDH jest tutaj deterministycznym schematem podpisu, inaczej niż PSS ze świeżą solą.
4. Wyjątkowy wpis $J$: zamiast znanego podpisu zapisujemy $(Y,\bot)$. Hash może zwrócić $Y$, ale Sign tego wpisu musi przerwać symulację.

Tabela oraz informacja o pozycji $J$ są wewnętrznym stanem redukcji, nie komunikatem protokołu. Nie dostaje ich ani przeciwnik, ani rzeczywisty podpisujący. W symulacji redukcja zastępuje usługę podpisującą, zamiast prosić ją o użycie nieznanego klucza. Podgląd całej tabeli na rysunku służy wyłącznie studentowi. Wyciekanie tego stanu nie jest dozwolonym zapytaniem w rozpatrywanym eksperymencie.

Odwrócona kolejność obliczeń, identyczny rozkład pary

Dla zwykłego wpisu porównajmy dwa sposoby przygotowania pary hasz–podpis. Uczciwy schemat wybiera losowy hasz i oblicza jego prywatny pierwiastek. Symulator losuje pierwiastek i stosuje publiczne potęgowanie. Zmienił się kierunek przygotowania pary, nie jej rozkład.

Niech $\varphi(N)=|\mathbb Z_N^*|$. Dla dowolnych $a,b\in\mathbb Z_N^*$ oba sposoby dają

Wynika to z bijektywności potęgowania RSA. Każdy hasz ma dokładnie jeden pierwiastek w tej grupie. Nie wystarczyłaby jednostajność samych haszy, gdyby podpisy nie były z nimi odpowiednio skorelowane. Tutaj zgadza się cały rozkład pary. Tabela zachowuje go także przy obu kolejnościach zapytań i ich powtórzeniach.

Przeciwnik nie obserwuje kolejności wewnętrznych obliczeń ani prywatnych losowań. W tym modelu nie dostaje też ich pomiarów czasowych. Z samych dostarczanych wartości nie może wykryć zamiany dla zwykłych wpisów. Jest to równość rozkładów, mocniejsza niż jedynie obliczeniowa nierozróżnialność. Cała redukcja może jednak przerwać na Sign wpisu $J$. Nie twierdzimy, że symulator zawsze odpowie na wszystko. Do przerwania zachowuje zgodny widok, a zdarzenie trafienia świeżej fałszywej wiadomości opisujemy osobno poniżej.

Jeszcze nie wykonano obliczeń.

Rozkład odpowiedzi, świeżość i sukces

1. Zgodność rozkładu. Dla zwykłego wpisu $u_m$ jest jednostajne, a potęgowanie jest bijekcją. Wynik $u_m^e$ jest więc jednostajny w tej samej grupie co $Y$. Tabela zachowuje spójność odpowiedzi i podpisów.
2. Właściwe trafienie. Rozpatrzmy zdarzenie, że $\mathcal A$ tworzy poprawne fałszerstwo i $J$ jest pozycją $m^*$. Świeżość $m^*$ oznacza, że redukcja nigdy nie musiała podpisywać tego wpisu. Nie przerwała więc symulacji z tego powodu.
3. Ekstrakcja bez cofania. Poprawność fałszerstwa daje $(\sigma^*)^e=Y\bmod N$. Redukcja zwraca po prostu $z=\sigma^*$.

Jeżeli prawdopodobieństwo udanego fałszerstwa wynosi $\epsilon$, ten prosty argument daje

Można formalnie sprzęgnąć prawdziwy eksperyment z symulacją dla każdego wyboru $J$. Do chwili ewentualnego przerwania widoki mają ten sam rozkład. Dla każdego udanego świeżego fałszerstwa dokładnie jeden z $Q$ wyborów wskazuje jego wpis i nie wymusza przerwania. Nieużyte pozycje oznaczają nietrafione losowania, nie pozwalają wybierać $J$ po zobaczeniu wyniku.

Czas redukcji obejmuje czas przeciwnika, obsługę tabeli, losowanie odwracalnych reszt i najwyżej $Q$ publicznych potęgowań. Wyraźny czynnik $Q$ jest stratą redukcji. Nie jest atakiem o koszcie $Q$ ani optymalną granicą dla FDH. Ważny jest tu kompletny argument bazowy, nie deklaracja ciasności.

Algorytm redukcji: jeden wybór celu, jedna wspólna tabela

Poniższy zapis zbiera cały dowód w jeden wykonywalny logicznie algorytm. Redukcja zna wyłącznie $(N,e,Y)$ i swoje losowania. Nie wylicza pierwiastka $Y$ przed otrzymaniem fałszerstwa. Wiersze tabeli numerujemy w chwili pierwszego pojawienia się nowej wiadomości, niezależnie od rodzaju zapytania.

Inicjalizacja:
    Q = q_H + q_S + 1
    J = jednostajna pozycja od 1 do Q
    T = pusta tabela, Signed = pusty zbiór

Ensure(m):
    jeżeli m jest w T, zwróć T[m]
    i = liczba wierszy T + 1
    jeżeli i = J, wpisz T[m] = (i, Y, brak pierwiastka)
    w przeciwnym razie:
        wylosuj jednostajne u z odwracalnych reszt modulo N
        wpisz T[m] = (i, u^e mod N, u)
    zwróć T[m]

Hash(m):
    (i, h, u) = Ensure(m)
    zwróć h

Sign(m):
    (i, h, u) = Ensure(m)
    dodaj m do Signed
    jeżeli i = J, przerwij całą próbę redukcji
    zwróć u

Po otrzymaniu (m*, sigma*):
    odrzuć, jeśli m* jest w Signed lub sigma* ma zły zakres
    (i, h, u) = Ensure(m*)
    odrzuć, jeśli (sigma*)^e mod N != h lub i != J
    zwróć sigma* jako pierwiastek RSA dla Y

Dlaczego zgadywanie ma koszt dokładnie Q, a nie jeszcze jeden iloczyn strat?

Wyobraźmy sobie pomocniczy uczciwy eksperyment, w którym znamy także prywatny klucz RSA. Możemy w nim obsłużyć wszystkie zapytania i dopiero do analizy dołożyć niezależny losowy indeks $J$. Każdy wiersz ma ten sam jednostajny rozkład hasza. W wybranym wierszu można ten hasz utożsamić z jednostajnym wyzwaniem $Y$. To sprzężenie rozkładów, nie polecenie wyboru $Y$ przez rzeczywistą redukcję.

Niech $I^*$ będzie indeksem wiadomości poprawnego świeżego fałszerstwa w tym eksperymencie. Dla każdego udanego przebiegu jest dokładnie jedna dobra pozycja $J=I^*$ spośród $Q$. Nieużyte pozycje nadal są możliwymi nietrafionymi wyborami. Z niezależności pomocniczego $J$:

Na tym zdarzeniu wiadomość celu nie wystąpiła w Sign, bo fałszerstwo jest świeże. Rzeczywista redukcja nie potrzebuje więc nieznanego pierwiastka do żadnej wcześniejszej odpowiedzi. Może wykonać cały ten przebieg. Otrzymany podpis spełnia $(\sigma^*)^e=Y$ i jest rozwiązaniem zadania.

Nie mnożymy dodatkowo przez prawdopodobieństwo „nie było przerwania”. Na dobrym zdarzeniu brak takiego przerwania już wynika ze świeżości. To najważniejsze powiązanie definicji EUF-CMA z rachunkiem redukcji. Na pozostałych zdarzeniach redukcja może przerwać albo nie trafić celu.

Różnica względem forking lemma

RSA-FDH nie potrzebuje dwóch transkryptów. Trudna instancja znajduje się w jednym wyniku hasza. Przeciwnik zwraca jej pierwiastek jako podpis. W Schnorrze trudna instancja jest w kluczu publicznym, a rozwiązanie wydobywamy dopiero z dwóch zgodnych równań z różnymi wyzwaniami.

W ostatnim wierszu „odpowiedź Hash” oznacza wyzwanie $c_j$, a nie skalarną odpowiedź podpisu $z$. Szczegóły tych trzech redukcji rozwijamy w części o pełnych dowodach.

Co dokładnie cytujemy

Bellare i Rogaway, The Exact Security of Digital Signatures: How to Sign with RSA and Rabin, EUROCRYPT 1996, analizują FDH oraz konstruują PSS. Powyżej pokazaliśmy dydaktyczny wariant zgadywania wpisu, z jawnym doliczeniem zapytania końcowego. Nie jest to dowód bezpieczeństwa całego PKCS #1 ani powód, by zastępować PSS własnym kodowaniem. Późniejsze ulepszenia redukcji FDH nie zmieniają tej różnicy między schematem, modelem i konkretną granicą.

Sprawdź rozumienie: dlaczego zwrócenie losowego elementu grupy zamiast $u_m^e$ utrudniłoby podpisywanie? Dlaczego trafienie wpisu podpisanej wiadomości nie daje dozwolonego fałszerstwa? Dlaczego nie używamy tu forking lemma? Zadania i warianty przerwania: C17 i L12.