Czym jest szyfrowanie probabilistyczne?

Kryptografia odegrała istotną rolę w rozwoju technologii blockchain, ale nie byłoby to możliwe bez opracowania podstawowej koncepcji tej technologii: szyfrowanie probabilistyczne.

Kiedy mówimy o szyfrowaniu probabilistycznym, mamy na myśli algorytm, który jest w stanie zastosować losowość do mechanizmu szyfrowaniaTwórcy tej funkcji kryptograficznej zależy więc na czymś bardzo prostym: Dla każdego wejścia danych uzyskaj różne dane wyjściowe dla każdej wykonanej interakcji. Zatem algorytmy szyfrowania probabilistycznego starają się zapewnić wyższy poziom bezpieczeństwa niż ten osiągany za pomocą obecnych technik deterministycznych.

Pomysł ten pomaga udoskonalić systemy kryptografia asymetryczna że wiemy. I od tego momentu możemy zrozumieć jego znaczenie: szyfrowanie probabilistyczne jest podstawowym elementem konstrukcyjnym Ochrona prywatności naszego życia cyfrowegonie tylko w blockchain, ale także w Internecie i każdym innym aspekcie tego świata teraz i w niedalekiej przyszłości.

Pierwszy probabilistyczny system szyfrowania

Początków pierwszego probabilistycznego systemu szyfrowania można doszukiwać się w rozwoju Ralph Merkle ze swoją pracą Bezpieczna komunikacja przez niezabezpieczone kanałyPraca ta tak wyprzedzała swoje czasy, że podczas pierwszej prezentacji na konferencji Association for Computing Machinery (ACM) w 1975 r. uznano ją za niemożliwą do zrealizowania.

Ale w 1978 roku, rok po opublikowaniu dzieła przez Whitfield Diffie y Martina Hellmana i jego asymetryczny protokół kryptograficzny Diffiego-Hellmana, został ostatecznie uznany za coś możliwego, co uświadomiło nam jedną rzecz: Narodziny szyfrowania probabilistycznego i systemów kluczy publicznych nie były jedynie możliwością, ale przyszłością kryptografii.

W ten sposób propozycje Ralpha Merkle'a, Whitfielda Diffiego i Martina Hellmana stały się pierwszymi propozycjami kryptograficznymi wykorzystującymi w swoim działaniu elementy szyfrowania probabilistycznego. Ich sukces polegał na tym, że ten nowy schemat był… zdolny do zabezpieczenia dowolnego kanału komunikacji nawet w niebezpiecznym środowisku komunikacyjnym.

Ten przełom doprowadził do powstania jednego z pierwszych i najpowszechniej stosowanych na świecie asymetrycznych systemów szyfrowania z elementami probabilistycznymi: algorytmu RSA. RSA jest nadal używany w internecie i wielu systemach cyfrowych na całym świecie. Oczywiście, cała ta struktura jest również wykorzystywana w innych asymetrycznych systemach kryptograficznych, takich jak… ECDSA, EdDSA, Schnorr, co między innymi jasno pokazuje skalę znaczenia tego postępu.

Ulepszanie systemu

Jednak algorytmy probabilistyczne w RSA są w rzeczywistości rzadko stosowane. Generalnie służą one do jednej podstawowej funkcji: Generatory liczb pseudolosowych lub PRNGPrzypomnijmy, że generatory liczb losowych (PRNG) pomagają nam uzyskać liczby i entropię, które możemy uznać za bezpieczne, a tym samym stanowią podstawę bezpieczeństwa naszych obecnych algorytmów szyfrowania asymetrycznego. Generatory te są tworzone przy użyciu algorytmów probabilistycznych, a zatem algorytmy szyfrowania asymetrycznego są uważane za algorytmy probabilistyczne, mimo że nie w pełni implementują ten schemat.

Choć jest to wystarczająco bezpieczne, nawet według naszych obecnych standardów, bezpieczeństwo tych algorytmów można zwiększyć, rozszerzając wykorzystanie własności probabilistycznych na resztę algorytmu szyfrowania. Oznacza to, że zastosowanie losowości nie tylko do generatora liczb, ale także do całego systemu szyfrowania, byłoby ogromnym krokiem naprzód, porównywalnym z samymi narodzinami kryptografii asymetrycznej.

To właśnie to dzieło dwóch wielkich kryptografów zrealizowało, Shafiego Goldwassera y Silvio mikali (twórca AlgorandW 1982 roku Goldwasser i Micali zaprezentowali znany protokół kryptograficzny Goldwasser-Micali. Jego przełomowym osiągnięciem było to, że jest to pierwszy w pełni probabilistyczny system kryptograficzny znany na całym świecie.

Praca Goldwassera i Micaliego tworzy bezpieczny system asymetryczny oparty na problem reszt kwadratowych opisany przez Carla Friedricha Gaussa w 1801 roku. Ten problem matematyczny jest szeroko stosowany w kryptografii, a najlepszym przykładem jego implementacji jest algorytm PRNG BBS (generator liczb pseudolosowych BBS), stworzony w 1986 roku przez Lenore Blum, Manuela Bluma i Michaela Shuba.

To właśnie w oparciu o ten system Goldwasser i Micali stworzyli algorytm zdolny do generowania probabilistycznej funkcji kaskadowej, w której każda wartość wygenerowana przez faktoryzację losowo wygenerowanych liczb służy do zasilania całkowicie probabilistycznego algorytmu szyfrowania. W ten sposób tekst może być pobierany i szyfrowany sekwencyjnie. Każda sekwencja daje zupełnie inny wynik. Nigdy nie zobaczysz tego samego pliku z identycznym szyfrowaniem, niezależnie od liczby iteracji szyfrowania, które wykonasz. Szczegółowe matematyczne wyjaśnienie tego systemu znajdziesz tutaj. powiązanie.

Bezpieczeństwo systemu szyfrowania probabilistycznego

Po co więc osiągać ten poziom? Odpowiedź jest prosta: poprawić nasze bezpieczeństwoSystem szyfrowania probabilistycznego wprowadzony przez Goldwassera i Micali jest prawdopodobnie jedną z największych zagadek kryptoanalizy, jakie można rozwiązać.

Na przykład, Tekst składający się z 500 znaków miałby ponad 10^100000 różnych kombinacji szyfrowaniaTo poziom wydajności, który jest obecnie niemożliwy do analizy obliczeniowej. Jest on nawet większy niż możliwości szyfrowania osiągalne za pomocą algorytmów takich jak AES, ECDSA i EdDSA razem wziętych.

Problem z probabilistycznymi systemami szyfrowania polega na tym, że ich tworzenie przy użyciu maszyn deterministycznych zawsze generuje lukę lub przestrzeń, w której Nie możemy w pełni zweryfikować jego bezpieczeństwaMówiąc prościej, teoretycznie są one doskonałe, ale formalnie, na poziomie implementacji algorytmicznej, nie możemy zagwarantować ich całkowitego bezpieczeństwa. Problem ten mógłby zostać zasadniczo rozwiązany dzięki kolejnemu przełomowi w erze komputerowej: komputerom kwantowym, ponieważ z samej swojej natury są one probabilistyczne, co pozwala nam w pełni zweryfikować bezpieczeństwo tych systemów kryptograficznych.

Oprócz tworzenia wydajnych algorytmów, ponieważ istniejące implementacje szyfrowania probabilistycznego są nieefektywne obliczeniowo, a ich bezpieczeństwo nie uzasadnia oferowanej mocy obliczeniowej i wydajności, konieczne są dalsze badania w tej dziedzinie, zanim będziemy mogli w końcu opracować złożone algorytmy, które w pełni wykorzystają potencjał tego nowego udoskonalenia w naszych systemach szyfrowania. Na razie musimy poczekać jeszcze trochę i udoskonalić probabilistyczne podstawy, które już chronią nasze obecne implementacje.