Bardzo gładki haszysz

Bardzo gładki hasz (VSH)
Ogólny
Projektanci	Scott Contini, Arjen K. Lenstra , Ron Steinfeld
Opublikowane po raz pierwszy	2005
Następcy	VSH*
Szczegół
Podsumuj rozmiary	1024 bity i więcej

W kryptografii Very Smooth Hash (VSH) to kryptograficzna funkcja skrótu, która została wynaleziona w 2005 roku przez Scotta Continiego, Arjena Lenstrę i Rona Steinfelda. Udowodnione bezpieczeństwo oznacza, że znalezienie kolizji jest tak trudne, jak jakiś znany trudny problem matematyczny. W przeciwieństwie do innych, dających się udowodnić, bezpiecznych , odpornych na kolizje skrótów, VSH jest wydajny i użyteczny w praktyce. Asymptotycznie wymaga tylko jednego mnożenia na log( n ) bitów wiadomości i używa arytmetyki typu RSA. Dlatego VSH może być przydatny w środowiskach wbudowanych, w których przestrzeń na kod jest ograniczona.

Zaproponowano dwa główne warianty VSH. Po pierwsze, znalezienie kolizji jest równie trudne, jak znalezienie nietrywialnego modułowego pierwiastka kwadratowego z bardzo gładkiej liczby modulo n . Drugi wykorzystuje pierwszy moduł p (bez zapadni ), a jego dowód bezpieczeństwa polega na trudności znalezienia dyskretnych logarytmów bardzo gładkich liczb modulo p . Obie wersje mają podobną wydajność.

VSH nie nadaje się jako substytut losowej wyroczni , ale może być użyty do zbudowania potencjalnie bezpiecznej losowej funkcji skrótu z zapadnią. Ta funkcja może zastąpić funkcję zapadni używaną w schemacie podpisu Cramer-Shoup , zachowując jej możliwe do udowodnienia bezpieczeństwo, jednocześnie przyspieszając czas weryfikacji o około 50%.

VSN i VSSR

Wszystkie kryptograficzne funkcje skrótu, które są obecnie szeroko stosowane, nie są oparte na trudnych problemach matematycznych. Te nieliczne funkcje, które są zbudowane na twardych problemach matematycznych, nazywamy dającymi się udowodnić bezpieczeństwem . Wiadomo, że znalezienie kolizji jest równie trudne, jak rozwiązanie trudnego problemu matematycznego. W przypadku podstawowej wersji funkcji Very Smooth Hash tym trudnym problemem jest znalezienie modułowych pierwiastków kwadratowych (VSSR) pewnych liczb specjalnych (VSN). Zakłada się, że jest to tak trudne, jak rozkładanie liczb całkowitych na czynniki .

Dla ustalonej stałej c i n liczba całkowita m jest bardzo gładką liczbą (VSN) , jeśli największy czynnik pierwszy m wynosi co najwyżej (log n ) ^c .

Liczba całkowita b jest modulo n bardzo gładkiej reszty kwadratowej , jeśli największa liczba pierwsza w rozkładzie na czynniki b s wynosi co najwyżej (log n ) ^c i istnieje liczba całkowita x taka, że ${\ Displaystyle b \ równoważnik x ^ {2}\mod n}$ . Mówi się, że liczba całkowita x jest modułowym pierwiastkiem kwadratowym z b .

Interesują nas tylko nietrywialne pierwiastki kwadratowe, takie, gdzie x ² ≥ n . Jeśli x ² < n , pierwiastek można łatwo obliczyć za pomocą algorytmów z pól o charakterystyce 0, takich jak pole rzeczywiste. Dlatego nie nadają się do prymitywów kryptograficznych.

Bardzo gładki nietrywialny modułowy pierwiastek kwadratowy (VSSR) to następujący problem: Niech n będzie iloczynem dwóch nieznanych liczb pierwszych o mniej więcej tej samej wielkości i niech ${\ displaystyle k \ leq (\ log n) ^{c}}$ . p $, p_ {3} = 5, \ kropki}$ ₀ być ciągiem liczb pierwszych. VSSR to następujący problem: Biorąc pod uwagę n , znajdź takie, że ${\ Displaystyle x \ in \ mathbb {Z} _ {n} ^ {*}}$ ${\ displaystyle \textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}}$ i co najmniej jedno z e ,..., e _k jest nieparzyste.

Założenie VSSR jest takie, że nie ma probabilistycznego wielomianu (w ${\ displaystyle \ log n}$ ) algorytmu czasu, który rozwiązuje VSSR z prawdopodobieństwem nie do pominięcia . Jest to uważane za bezużyteczne założenie w praktyce, ponieważ nie mówi, dla jakiego rozmiaru modułów VSSR jest trudne obliczeniowo. Zamiast tego stosuje się obliczeniowe założenie VSSR . Mówi, że zakłada się, że rozwiązanie VSSR jest tak trudne, jak rozłożenie na czynniki trudnego do uwzględnienia modułu bitowego, gdzie ${\ displaystyle s}$ ${\ displaystyle s}$ jest nieco mniejszy niż rozmiar ${\ displaystyle n}$ .

Przykłady VSN i VSSR

Niech parametry zostaną ustalone w następujący sposób: ${\ displaystyle c = 5}$ i ${\ displaystyle n = 31}$ .

Wtedy ${\ Displaystyle m_ {1} = 35 = 5 \ cdot 7}$ jest bardzo gładką liczbą w odniesieniu do tych parametrów, ponieważ ${=}} ~ 7,37}$ ${\ Displaystyle (\ log 31) ^$ ${5} ~ {\$ jest większa niż wszystkie pierwsze. Z drugiej strony $Displaystyle$ $\ cdot 11}$ nie jest VSN poniżej n $n = 31}$ .

b $}$ $)$ jest bardzo gładką resztą kwadratową modulo, $ponieważ$ gładką liczbą ( i ${\ Displaystyle x_ {1} = 3}$ takie, że ${\ Displaystyle x_ {1} ^ {2} = b_ {1}}$ (mod ${\ Displaystyle n}$ ). Jest to trywialny modułowy pierwiastek kwadratowy, ponieważ $do$ nie jest uwzględniany przy podnoszeniu

b ${\ displaystyle b_ {2} = 15}$ jest również bardzo gładką resztą kwadratową modulo $\ displaystyle n}$ . Wszystkie czynniki pierwsze są mniejsze niż 7,37, a modułowy pierwiastek kwadratowy wynosi ${\ Displaystyle x_ {2} = 20}$ od ${\ Displaystyle 20 ^ {2} = 400 \ równoważnik 15}$ (mod ${\ displaystyle n}$ ). Jest to zatem pierwiastek nietrywialny. Problem VSSR polega na znalezieniu ${\ Displaystyle x_ {2}}$ dany ${\ Displaystyle b_ {2}}$ i ${\ Displaystyle n}$ . I przypuszczamy, że jest to obliczeniowo tak trudne, jak faktoryzacja. n $\ displaystyle n}$

Algorytm VSH, wersje podstawowe

Niech $n}$ $niech$ złożonym pierwszych Niech ${\ Displaystyle k}$ , długość bloku, będzie największą liczbą całkowitą taką, że ${\ Displaystyle \ textstyle \ prod _ {i = 1} ^ {k} p_ {i}<n }$ . niech ${\ displaystyle m}$ być ${\ Displaystyle \ ell}$ -bitową wiadomością do mieszania składającą się z bitów ${\ Displaystyle (m_ {1}, \ ldots, m_ {\ ell})}$ i założyć, że ${\ Displaystyle \ ell <2 ^ {k}}$ . Aby obliczyć skrót ${\ displaystyle m}$ :

₀ x = 1
Niech $liczbą$ najmniejsza liczba całkowita większa lub $bloków$ . Niech ${\ Displaystyle m_ {i} = 0}$ dla ${\ Displaystyle l <i \ równoważnik Lk}$ (dopełnienie)
Niech ${\ Displaystyle \ textstyle \ ell = \ suma _ {i = 1} ^ {k} l_ {i} 2 ^ {i-1}}$ z $} \ in \ {0,1 \}}$ $Displaystyle \ ell _ {$ być binarną reprezentacją długości wiadomości i zdefiniować ${\ styl wyświetlania m_{Lk+i}=\ell _{i}}$ dla ${\ Displaystyle 1 \ równoważnik ja \ równoważnik k}$ .
dla j = 0, 1, ..., L kolejno obliczamy ${\ Displaystyle x_ {j + 1} = x_ {j }^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n}$
powrót x _{L + 1} .

Funkcja w kroku 4 jest nazywana funkcją kompresji.

Właściwości VSH

Długość wiadomości nie musi być znana z góry.
Znalezienie kolizji w VSH jest tak samo trudne jak rozwiązanie VSSR. Zatem VSH jest (silnie) odporny na kolizje , co implikuje również drugi opór przedobrazowy. Nie udowodniono, że VSH jest odporny na przedobrazy.
Funkcja kompresji nie jest odporna na kolizje. Niemniej jednak funkcja skrótu VSH jest odporna na kolizje w oparciu o założenie VSSR. Zmieniona wersja VSH, zwana VSH* , wykorzystuje funkcję kompresji odporną na kolizje i jest około 5 razy szybsza podczas mieszania krótkich wiadomości.
Ponieważ długość wyjściowa VSH jest długością bezpiecznego modułu RSA, VSH wydaje się w praktyce całkiem odpowiedni do konstruowania podpisów RSA „hash-then-sign” dla dowolnie długich wiadomości. Jednak taki podpis musi być starannie zaprojektowany, aby zapewnić jego bezpieczeństwo. Naiwne podejście można łatwo złamać w ramach CPA (atak z wybranym tekstem jawnym) .
Wydajność : koszt każdej iteracji jest mniejszy niż koszt 3 mnożeń modułowych. Podstawowa wersja VSH całkowicie wymaga pojedynczego mnożenia na bity wiadomości ${\ Displaystyle \ Omega (\ log n / \ log \ log n)}$ .

Warianty VSH

Zaproponowano kilka ulepszeń, przyspieszeń i wydajniejszych wariantów VSH. Żaden z nich nie zmienia podstawowej koncepcji funkcji. Te ulepszenia nazywają się:

Cubing VSH (zamiast kwadratu).
VSH ze zwiększoną liczbą małych liczb pierwszych.
VSH ze wstępnie obliczonymi iloczynami liczb pierwszych.
Szybki VSH.
Szybki VSH ze zwiększoną długością bloku.

Wariant VSDL i VSH-DL

VSH -DL jest dyskretnym wariantem logarytmu VSH, który nie ma zapadni , jego bezpieczeństwo zależy od trudności znalezienia dyskretnego logarytmu modulo a liczba pierwsza p .

Bardzo gładki logarytm dyskretny (VSDL) to problem polegający na tym, że mając bardzo gładką liczbę, chcemy znaleźć jej logarytm dyskretny modulo pewną liczbę n .

$pierwszą$ $-tą$ w poprzedniej sekcji, przez liczbę . $będzie$ ponadto stałą stałą i będzie pierwszą z $=$ $Displaystyle p = 2q + 1$ { $\$ niech ${\ Displaystyle k \ równoważnik (\ log p) ^ {c}}$ . VSDL to następujący problem: biorąc pod $.$ , znajdź liczby ${\ Displaystyle e_ {1}, ..., e_ {k}}$ takie, że ${\ Displaystyle 2 ^ {e_ {1}} \ równoważnik \prod _{i=2}^{k}p_{i}^{e_{i}}\mod p}$ z ${\ Displaystyle | e_ {i} | <q}$ dla ${\ Displaystyle i = 1, ..., k}$ co najmniej jeden z ${\ displaystyle e_ {1}, ..., e_ {k}}$ .

Założenie VSDL jest takie, że nie ma probabilistycznego wielomianu (w ${\ displaystyle \ log p}$ ) algorytmu czasu, który rozwiązuje VSDL z prawdopodobieństwem nie do pominięcia . Istnieje silny związek między twardością VSDL a twardością obliczania logarytmu dyskretnego modulo $,$ przypomina, ale jest nieco słabsze niż związek między VSSR a rozkładem na czynniki całkowite.

Bezpieczeństwo VSH

Wysoka odporność na kolizje to jedyna sprawdzona właściwość VSH. Nie implikuje to odporności na preimage ani innych ważnych właściwości funkcji skrótu, a autorzy stwierdzają, że „VSH nie powinien być używany do modelowania losowych wyroczni ” i nie może być zastępowany konstrukcjami, które od nich zależą ( sygnatury RSA , niektóre adresy MAC ). VSH nie powinien być uważany za funkcję skrótu ogólnego przeznaczenia, jak zwykle rozumianą w inżynierii bezpieczeństwa .

Właściwość multiplikatywna

VSH jest multiplikatywny: Niech x , y i z będą trzema ciągami bitów o równej długości, gdzie z składa się tylko z bitów zerowych, a łańcuchy spełniają warunek x AND y = z . Łatwo zauważyć, że H(z)H(x OR y) ≡ H(x)H(y) (mod n) . W rezultacie VSH ulega klasycznemu atakowi polegającemu na zamianie pamięci na czas, który ma zastosowanie do skrótów multiplikatywnych i addytywnych.

$^ { \ell }}$ $2$ można wykorzystać do skonstruowania ataku przedobrazowego na VSH składającego się z $bitów$ który ma złożoność, a nie zgodnie z oczekiwaniami.

Atak na okrojoną wersję

VSH generuje bardzo długi skrót (zwykle 1024 bity). Nic nie wskazuje na to, że obcięty skrót VSH zapewnia bezpieczeństwo współmierne do długości skrótu.

Istnieje częściowy atak kolizyjny na VSH obcięty do najmniej znaczących l bitów.

Złożoność tego ataku na VSH jest następująca:

Wstępne obliczenie tabeli w trybie offline: ${\ Displaystyle 2 ^ {\ ell / 3}}$ czas i przestrzeń.
Znajdowanie kolizji: iteracje ${\ displaystyle 2 ^ {\ ell / 3}} .$
$.$ $funkcji$ : mniej więcej jak oczekiwano z z dobrymi

To prawdopodobnie wyklucza zastosowanie VSH w schematach podpisów cyfrowych, które dają podpisy krótsze niż wynik mieszania VSH, takich jak schematy podpisów z krzywą eliptyczną.

Zobacz też