Pierwsze kroki z kryptosystemem SRVB

Wstęp

Bezpieczeństwo informacji to fascynująca dziedzina wiedzy, która może obejmować wszystko, od informatyki teoretycznej po inżynierię oprogramowania, a nawet obserwować psychologię ludzkiego błędu.

Kryptografia jest obecnie jednym z wielu anonimowych bohaterów technologicznych naszego codziennego życia. Sieci społecznościowe, bankowość internetowa, wywiad wojskowy i każdy inny system informacyjny, który zajmuje się poufnymi informacjami, w dużym stopniu opierają się na kryptografii. Kryptografia pozwala nam zachować prywatność, co niektórzy uważają za dwunaste prawo człowieka.

Ten artykuł zawiera wprowadzenie do zasad działania kryptosystemów z kluczem publicznym i przedstawia Santana Rocha-Villas Boas (SRVB), kryptosystem opracowany przez autora artykułu i prof. Daniela Santanę Rocha. W chwili pisania tego tekstu autorzy algorytmu przygotowują kampanię, która obejmuje nagrodę finansową dla każdego, kto zdoła złamać kod. Ponieważ w artykule szczegółowo omówimy funkcjonalność algorytmu, jest to najlepsze miejsce do rozpoczęcia pogoni za nagrodą. Więcej informacji można znaleźć na stronie SRVB.

Co to jest kryptosystem?

Kryptografia to dowolna metoda utrudniania interpretacji wiadomości, jednocześnie pozwalająca na wykonalną jej interpretację, o ile zapewniona jest konkretna instrukcja, którą zwykle jest tak zwany „klucz”. Chociaż jest to bardzo szeroka definicja, obejmująca nawet najwcześniejsze techniki, warto wspomnieć, że nie obejmuje ona wszystkiego, co jest związane z bezpieczeństwem informacji.

Oczekuje się, że wyścig technologiczny między metodami szyfrowania i sposobami ich złamania nigdy nie będzie miał ostatecznego zwycięzcy. Oczekuje się, że każda nowa generacja będzie podnosić standardy bezpieczeństwa informacji i kryptoanalizy, czyli zestawu technik systematycznego odszyfrowywania/łamania zaszyfrowanych wiadomości, czyli omijania zabezpieczeń lub szyfrowania.

Aby kryptosystem (dana technika kryptografii) został uznany przez użytkowników za bezpieczny, musi uzyskać zgodę międzynarodowej społeczności ekspertów, a tym samym być publicznie znany, co jest znane jako zasada Kerckhoffsa. Jednak ten sam stan naraża system na kontrolę ze strony światowej społeczności kryptoanalizy, która będzie próbowała wymyślić sposoby systematycznego łamania szyfrów.

W jaki sposób można uczynić dany proces szyfrowania wystarczająco tajnym, aby tylko zamierzeni agenci mogli go odszyfrować, a jednocześnie na tyle publicznym, aby światowa społeczność zajmująca się kryptoanalizą mogła zaświadczyć o jego solidności? Odpowiedzią jest komponent, który jest kluczowym elementem Kryptologii: klucz. Klucz kryptosystemu jest parametrem algorytmu szyfrowania lub deszyfrowania, lub obu. Utrzymując w tajemnicy parametry, a nie rodzinę algorytmów, można osiągnąć oba sprzeczne wymagania. Zakładając, że rodzina parametrów jest wystarczająco duża (być może nieskończona) i każdy z jej składników można udowodnić, że ma odpowiednie właściwości, napastnik nie będzie mógł określić parametrów jedynie na podstawie inspekcji.

Wreszcie, aby klucz działał skutecznie, musi być łatwy do wyprodukowania, ale prawie niemożliwy do odgadnięcia. Dzięki mocy obliczeniowej dzisiejszych komputerów komputer potrzebowałby mniej czasu na odszyfrowanie klucza wygenerowanego przez człowieka, niż jakikolwiek człowiek musiałby to sobie wyobrazić, poza tym, że i tak nie jest opłacalne generowanie kluczy w ten sposób. Z tego powodu klucze są zwykle generowane przez algorytm.

Algorytm generowania kluczy nie może tworzyć przewidywalnych/odtwarzalnych danych wyjściowych w wyniku typowego użycia. Ponieważ algorytmy wykonują procedury bez żadnego inteligentnego procesu, pojawia się pytanie, jak można to zrobić. Odpowiedzią jest przekształcenie algorytmów generowania kluczy w mapy, które przekształcają dużą liczbę naprawdę losowych bitów w klucze. Naprawdę losowe bity można uzyskać z systemu operacyjnego, który generuje je z niepewności we wszechświecie. Niektóre źródła to ruch myszy, opóźnienia pakietów sieciowych, a nawet dedykowany sprzęt, w zależności od aplikacji.

Kryptosystemy klucza publicznego

Przygotuj się na ponowne zaskoczenie, ponieważ teraz przedstawimy koncepcję, która pozornie jest sprzeczna z tym, co przed chwilą powiedzieliśmy: klucz publiczny.

Do tej pory widzieliśmy tworzenie bezpiecznej komunikacji po bezpiecznej wymianie tajnych parametrów (kluczy), ale problem wymiany parametrów przez kanał publiczny pozostaje. W tej chwili przedstawimy koncepcję, która rozwiązuje nieco bardziej namacalny problem: stworzenie bezpiecznego kanału.

Załóżmy, że Alicja współpracuje z Bobem i chcą zachować bezpieczeństwo swoich interakcji w pracy za pomocą szyfrowania. Mogą spotykać się i wymieniać swoje klucze szyfrowania, przekazując sobie nawzajem pamięć flash USB ze swoimi kluczami. Ale co, jeśli Alice i Bob znajdują się na różnych kontynentach. Jak ustanowić bezpieczny kanał tam, gdzie go nie ma?

Wysyłanie kluczy pocztą elektroniczną nie wchodziłoby w grę, ponieważ ich konkurencja Eve może przechwycić wymianę i użyć ich kluczy do późniejszego odczytania wszystkich zaszyfrowanych danych. Gdyby mieli jakikolwiek inny kanał cyfrowy, przez który mogliby przesyłać te wrażliwe dane, nie potrzebowaliby przede wszystkim szyfrowania, a tym samym kluczy. Wysyłanie klucza pocztą fizyczną również może zostać przechwycone, ponieważ na początku wymaga wymiany poufnych informacji. Wysyłanie steganograficznego klucza poprzez ukrywanie się w innych danych byłoby sprytne, ale bezużyteczne, chyba że nadawca jest pewien, że odbiorca i sam odbiorca jest świadomy istnienia takiej wiadomości i wie, jak ją wyodrębnić. Tak się składa, że ​​świadomość istnienia komunikatu wraz z opisem, jak wydobyć klucz z danych, jest samo w sobie rodzajem klucza, który sprowadza nas z powrotem do punktu wyjścia.

Rozwiązaniem jest opracowanie kryptosystemu, dla którego parametr szyfrowania nie jest wystarczający, aby wykonalną konstrukcję oryginalnej wiadomości ^[1] , i zachowanie dla siebie parametru, który umożliwiłby skonstruowanie wiadomości. Nazywamy ten parametr kluczem prywatnym. W oparciu o klucz prywatny można w sposób wykonalny wygenerować zestaw parametrów dla narzędzia szyfrującego, nie powodując, że te nowe parametry same w sobie mogą ujawnić, czym jest klucz prywatny. Ten zestaw parametrów można udostępniać publicznie, ponieważ nie jest tak ważne, kto może coś zaszyfrować, o ile tylko jedna osoba może to odszyfrować. Ponieważ ten zestaw parametrów narzędzia szyfrującego może być upubliczniony, nazywa się go kluczem publicznym.

Kryptografia, w której klucze szyfrowania i odszyfrowywania różnią się, a pierwszego nie można wykorzystać do wydedukowania drugiego, nazywa się kryptografią asymetryczną, podczas gdy kryptografia symetryczna jest tym, co mamy, gdy te klucze są takie same lub można je łatwo wydedukować.

Alicja wysyła Bobowi swój klucz publiczny, który może być używany tylko do szyfrowania rzeczy, które tylko ona może odszyfrować (za pomocą swojego prywatnego klucza, który przechowuje prywatnie) i odwrotnie, Bob wysyła Alicji swój klucz publiczny, który może być używany tylko do szyfrowania rzeczy że on sam może odszyfrować (za pomocą swojego klucza prywatnego, który również przechowuje prywatnie). Ale jak można ewentualnie opublikować parametr algorytmu szyfrowania, z którego nie można wywnioskować dokładnego algorytmu odwrotnego?

Odpowiedź leży w dziedzinie matematyki, która jest najbliżej związana z programowaniem, czyli teorią złożoności obliczeniowej. Każdy, kto zagłębił się wystarczająco głęboko w problemy matematyczne, słyszał o przekształceniach, które są łatwe do wykonania w jeden sposób, ale trudne do odwrotnego. Na przykład w rachunku różniczkowym znalezienie podręcznikowej pochodnej jest zwykle prostym ćwiczeniem, podczas gdy wykonanie odwrotności (jak na przykład rozwiązywanie dowolnej nieco nietrywialnej całki lub podręcznikowego fizycznego ODE lub PDE) wymaga bardziej szczegółowego procesu pierwszego postawienia hipotezy o rodzinach funkcji, które mają zagwarantowane (lub przynajmniej prawdopodobne), że zawierają rozwiązanie (rozwiązania) i rozwiązywają odwrotne problemy, aby znaleźć rozwiązania z tych rodzin.

Przykładem, który jest faktycznie wykorzystywany w kryptosystemie RSA, jest mnożenie dużych liczb pierwszych w porównaniu do faktoryzacji otrzymanego produktu bez wcześniejszej znajomości czynników. Mnożenie jest trywialne, ale rozkładanie na czynniki wymaga losowego ^[2] odgadnięcia czynników pierwszych, które mają setki cyfr. Ważną właściwością operacji jest potrzeba jej odpowiedniego skalowania. Dodanie kilku cyfr do rozmiaru liczb pierwszych w RSA da w wyniku klucz, którego złamanie wymaga tysięcy razy więcej operacji, a jednocześnie nieznacznie zwiększy złożoność procesu szyfrowania. Mówiąc ogólnie, iloczyn liczb pierwszych jest używany do szyfrowania, podczas gdy para czynników pierwszych jest używana do deszyfrowania.

Mając to wszystko na uwadze, przyjrzyjmy się, jak działa kryptosystem SRVB.

Algorytm bazowy — spojrzenie na SRVB

Problem sumy podzbiorów

Jak każdy inny kryptosystem klucza publicznego, SRVB opiera się na trudności w rozwiązaniu konkretnego problemu, który jest łatwy do wyprodukowania. W przypadku SRVB jest to problem sumy podzbiorów, który można opisać w następujący sposób:

Znając liczby całkowite $w$ i $v_1, \cdot \cdot \cdot, v_N \in Z$ znajdź ciąg $b_1, \cdot \cdot \cdot, b_N \in {0,1}$, taki że $ \sum_ {i = 1}^{N} v_i b_i = w $.

Oczywiście problem ten może powstać poprzez losowe wybranie N liczb całkowitych, losowe wybranie ich podzbioru i zsumowanie tego podzbioru - co jest trywialne.

Wyszukiwanie brute-force miałoby złożoność $ O( N * 2^N ) $, obliczając dla każdej kombinacji wartości $b$s. Bardziej wydajne podejście zostało podane przez Horowitza i Sahni w 1972 r., ze złożonością $ O ( N * 2 ^ {N / 2} ) $. Problem jest co najmniej tak samo trudny, jeśli zamienimy $b$si $w$ na $k$-wymiarowe wektory liczb całkowitych. Sfera, w której ma się rozgrywać ten trudniejszy problem, musi jednak mieć również izomorfizm z pierścieniem, w którym ma miejsce łatwiejsza wersja tego samego problemu, jak zobaczymy poniżej. Z tego powodu SRVB wykorzystuje problem sum podzbiorów w liczbach całkowitych Gaussa, gdzie $ k = 2 $.

Istnieje szczególny przypadek, w którym problem ten można łatwo obliczyć przy użyciu algorytmu zachłannego. Jeśli posortujemy współczynniki skalowania sekwencji $ v_1, \cdot \cdot \cdot, v_N $, w których każda liczba całkowita w ciągu jest większa niż suma wszystkich liczb całkowitych, które pojawiły się przed nią ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), można by użyć zachłannego podejścia do znalezienia ciągu b w czasie liniowym. Sekwencja o opisanych właściwościach nazywana jest sekwencją superrosnącą .

Oto prosty opis zachłannego rozwiązania tego przypadku:

1. Zacznij od $ i = N $, aktualnie obserwowanego współczynnika, i $ w' = w $, reszta z $w$

2. Jeśli bieżący współczynnik skalowania jest zbyt duży, aby zmieścić się w tym, co pozostało z $w$, co oznacza $v_i > w'$, ustaw $b_i = 0$ i przejdź do następnego kroku. W przeciwnym razie wiemy, że współczynnik skalujący musi być w sekwencji (ponieważ reszta współczynników jest mniejsza niż $v_i$) i ustawiamy $b_i = 1$.

3. $ w' \Leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$. Jeśli $i > 0$, wróć do kroku 2.

4. Sprawdź, czy teraz $w' == 0$, w przeciwnym razie problem został uszkodzony

Działa to, ponieważ wiemy, że wszystkie mnożniki mniejsze niż obecnie obserwowany nie mogą łącznie pokryć tylu (pod)sum $ w' $, ile jest w stanie pokryć bieżący mnożnik. Jeśli więc pozostała suma jest większa niż aktualny współczynnik, wiemy na pewno, że wszystkie kolejne czynniki razem nie dadzą się zsumować bez pomocy obecnego współczynnika. Z drugiej strony, ponieważ wszystkie mnożniki są dodatnie, jeśli bieżący współczynnik $ v_i $ jest większy niż pozostała suma $ w' $, dodanie jakiegokolwiek innego współczynnika spowoduje, że wynik przewyższy $ w' $ jeszcze bardziej.

Ustawmy notację dla reszty artykułu. Jako czynniki i sumę ciągu superrosnącego wybieramy $ v_1, \cdot \cdot \cdot, v_n $ i $w$, natomiast $ u_1, \cdot \cdot \cdot, u_n $ i $y$ będą publicznie dostępne parametry, które są dostarczane do odzyskiwania $ b_1, \cdot \cdot \cdot, b_n $.

Gdy sekwencja $ u_1, \cdot \cdot \cdot, u_n $ jest wybrana tak, aby nie zwiększała się, a liczba $y$ jest publicznie dostępna, nie podano informacji wystarczających do odzyskania sekwencji $ b_1, \cdot \cdot \cdot , b_n $. Jeśli jednak istnieje ciąg superrosnący $ v_1, \cdot \cdot \cdot, v_n $, który mógłby zastąpić ciąg $ u_1, \cdot \cdot \cdot, u_n $, można by użyć tego ciągu do rozwiązania problemu chciwe podejście.

Poniżej pokażemy, jak to działa.

Wykorzystanie sum podzbiorów w poprzednim kryptosystemie

W 1978 roku Ralph Merkle i Martin Helman opracowali sposób na wykorzystanie tych dwóch paradygmatów plecakowych i liniowości operacji modułu do zbudowania połączenia między dwiema sekwencjami opisanymi w poprzedniej sekcji – tworząc w ten sposób kryptosystem klucza publicznego. Pomysł polegał na przekształceniu prostego plecaka (tego składającego się z superrosnącego wektora liczb całkowitych) w twardy (ten bez tej właściwości) za pomocą operacji liniowej (modułu) z tajnymi argumentami. Transformacja polega na pomnożeniu każdego $v_i$ przez $\theta$ i pobraniu reszty tego iloczynu przez $\alpha$, gdzie $\alpha \gt \sum_{i=1}^N v_i$ i $\gcd (\alpha, \theta) = 1$ (dwa ograniczenia, które wkrótce zostaną uzasadnione). Wynik, sekwencja $u_1, \ldots, u_N$, już się nie zwiększa i można ją uznać za twardy plecak .

Losowa permutacja sekwencji $u_1, \ldots, u_N$ zostanie przekazana stronie, która chce zaszyfrować i wysłać do nas wiadomość. Permutacja jest wykonywana w taki sposób, aby osoba trzecia miała trudniej odgadnąć, jaka jest pierwotna sekwencja superrosnąca. Bloki bitowe wiadomości są używane jako współczynniki $b_1, \ldots, b_N$. Szyfrowanie odbywa się poprzez pomnożenie sekwencji kluczy przez tę sekwencję współczynników i zsumowanie mnożenia do wyniku, który oznaczymy etykietą $y$. Tylko właściciel klucza prywatnego może przekształcić $y$ w odpowiednie $w$, które zostałoby uzyskane, gdyby te same bloki $b_1, \ldots, b_N$ zostały pomnożone przez łatwe liczby całkowite (sekwencja $v_1, \ldots , v_N$). Odbywa się to poprzez pomnożenie $y$ przez $\theta^{-1}$, odwrotność multiplikatywną modułu $\theta$ $\alpha$ (którego istnienie zależy od warunku $\gcd(\alpha, \ theta) = 1$). Innymi słowy, $(\theta * \theta^{-1}) \bmod \alpha = 1$. Następnie obliczamy $w = (y * \theta^{-1}) \bmod a$. Powodem, dla którego gwarantuje się, że to zadziała, jest liniowość modułu , to znaczy, że kombinacja liniowa reszt równa się reszcie kombinacji liniowej.

Jeśli zastosujemy kolejno definicję $u$, pierścień ilorazowy i własność liniowości operatora modułu, to widzimy zgodność:

$ \begin{align} y & = \sum_{i=1}^N b_iu_i \newline & = \sum_{i=1}^N b_i (v_i * \theta \bmod \alpha) \newline & = \sum_{ i=1}^N b_i * v_i * \theta \bmod \alpha \newline & = \left[ \sum_{i=1}^N b_i * v_i * \theta \right] \bmod \alpha \newline & = \ left[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

A zatem łatwą sumę $w$ można uzyskać, mnożąc obie strony przez $\theta^{-1}$ i biorąc moduł przez $\alpha$. Aby to zrobić, trzeba znać zarówno $\alpha$, jak i $\theta$ (które pozwalają łatwo obliczyć $\theta^{-1}$), które mają być traktowane jako prywatne jako części klucza prywatnego.

Jedno pojedyncze ograniczenie, $\alpha \gt \sum_{i=1}^N v_i$, zostało pozostawione nieuzasadnione i oto jego wyjaśnienie: Równość między drugim i trzecim wierszem składa się z równości między klasami reszt ilorazu pierścień liczb całkowitych modulo $\alpha$. Innymi słowy, określa równość pozostałych członków tylko po podzieleniu przez $\alfa$, co nie jest wystarczającym warunkiem równości samych członków . W rezultacie więcej niż jeden wektor wartości $b$ może być odwzorowany w pojedynczy $y$, co zapobiega ograniczenie maksymalnej możliwej podsumy (tj. sumy wszystkich działek $v_i$) $w_{max}$ do być mniejsze niż $\alpha$ dla dowolnej kombinacji wartości $b$.

Jak w każdym innym przypadku codziennego życia, pełna znajomość wszystkich hipotez jest często niemożliwa i nigdy nie jest łatwa. W rezultacie, oceniając, czy dany kryptosystem jest bezpieczny w użyciu, musimy polegać na intuicji matematycznej, co nie daje nam żadnych gwarancji. Sześć lat po jego utworzeniu kryptosystem MH został złamany atakiem A. Shamira. Było jeszcze kilka prób ożywienia MH, z których wiele również się nie powiodło.

Kryptosystem The Santana Rocha - Villas Boas (SRVB)

W 2016 roku, po kilku burzach mózgów z autorem tego artykułu na temat różnie inspirowanych ^[3] możliwości kryptosystemu, Daniel Santana Rocha wpadł na pomysł zastąpienia $\theta$ i $\alpha$ liczbami całkowitymi Gaussa. Z bardziej technicznych powodów takie podejście prowadzi do oporu przed wspomnianym atakiem Szamira.

Wymyślił także blok bitów składający się z wielu kroków opisanej wcześniej liniowej kombinacji twardego plecaka . W każdym z nich na końcu ciągu byłaby dodana nowa (gaussowska) liczba całkowita, równoważna jedności, wyższa od sumy wszystkich poprzednich, a odrzucona byłaby obecnie najmniejsza.

Inne, ale eleganckie, analogiczne ograniczenie dotyczy $\alpha$, które jest teraz liczbą całkowitą Gaussa. Wymagamy $w_{max} \leq \vert\alpha\vert^2$. Powód jest bardzo trudny do sformalizowania, ale na szczęście można go łatwo wywnioskować z eleganckiego opisu:

Wyobraźmy sobie kwadratową kratę w płaszczyźnie liczb zespolonych, której bok jest przeciwprostokątną trójkąta prostokątnego katet a i b, równoległych do osi rzeczywistej i urojonej. Przykład takiej sieci podano poniżej. Liczby całkowite Guassia modulo $\alpha = a + bi$ mogą być reprezentowane przez punkty znajdujące się w takiej siatce. Wewnątrz takiej siatki znajdują się $\vert\alpha\vert^2$ różne punkty. Jeśli wybierzemy wystarczająco duży $\alpha$, możemy dopasować wszystkie liniowe kombinacje łatwego plecaka.

To jest graficzna reprezentacja izomorfizmu $f : Z/n \rightarrow Z[i]/(\alpha)$, gdzie $n = 13$ i $\alpha = a + bi = 3 + 2i$ (zauważ, że $ n$ i $\alpha$ rzeczywiście spełniają wymagania $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $ zgodnie z wymaganiami). Kropki reprezentują liczby całkowite Gaussa, tj. liczby zespolone $a + bi$, gdzie $a$ i $b$ są liczbami całkowitymi. Jak zwykle, oś pozioma reprezentuje część rzeczywistą, podczas gdy pionowa reprezentuje część urojoną. Zatem przesunięcie o jedną kropkę w prawo lub w lewo jest równoznaczne z dodaniem odpowiednio +1 lub -1 do jej aktualnej wartości. Podobnie przesunięcie jednej kropki w górę lub w dół odpowiada dodaniu odpowiednio +i lub -i.

Czerwone kropki to odpowiedniki $0 \bmod(\alpha)$. Oprócz tego pokolorowaliśmy jeszcze 4 pary kropek.

Izomorfizm $f$ jest zdefiniowany przez przekształcenie $i$tego elementu ciągu cyklicznego $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ do $i$tego elementu również cyklicznego ciągu kropek na rysunku, który jest zgodny z następującymi regułami:

1. Zaczyna się od czerwonej kropki pierwszego rzędu;
2. Podąża za poziomymi strzałkami w prawo; oprócz tego
3. Gdy podążanie za strzałkami prowadzi sekwencję poza siatkę, osiągnie jeden z nieczarnych punktów. Zamiast iść do tego punktu, przeskakuje do tego samego kolorowego punktu (tj. równoważnego punktu modulo $\alpha$) wewnątrz tego samego kwadratu; i w końcu
4. Kiedy ten inny niż czarny punkt stanie się czerwony (co dzieje się po przejściu wszystkich pozostałych kolorów), sekwencja przeskakuje do najwyższej czerwonej kropki, w ten sposób ponownie rozpoczynając cykl;

Aby odwzorować co najmniej $Y$ naturalne liczby całkowite, należy wziąć kwadrat o polu $\vert\alpha\vert^2$ (gdzie $\vert\alpha\vert = \sqrt{a^2 + b^2} $ jest według twierdzenia Pitagorasa miarą jego boku) co najmniej tak samo wysoką.

Zauważ, że każdy „skok” zmienia numer wiersza $r$ na $r \leftarrow (r + b)(mod a + b)$, jeśli liczy się wiersze od góry do dołu, i równoważnie na $r \leftarrow (r + a)(mod a + b)$ jeśli liczy się od dołu do góry. Stąd warunkiem koniecznym i wystarczającym, aby każdy wiersz (i kropka) był przeszukiwany dokładnie raz w każdym cyklu, jest to, aby wielkość skoków była równa liczbie wierszy, czyli innymi słowy, $gcd(a,a + b) = gcd(b,a + b) = 1$. Ze względu na własności największego wspólnego operatora dzielnika, oba są równoważne $gcd(a,b) = 1$.

YS Villas Boas zauważył potrzebę współprymatu $a$ i $b$. Aby zachować superwzrost, każda nowa liczba całkowita $w$ dodana na końcu ciągu musi przekraczać sumę wszystkich bieżących ($w > \sum_{i=1}^k v_i$). Zauważył, że aby to osiągnąć, ich mnożące współczynniki $b_i$ musiałyby wynosić co najmniej 1, a zatem każdy bit nie mógł być odwzorowany na współczynniki 0 i 1. Gdyby współczynniki wynosiły 0 i 1, tylko blok złożony tylko z jednego, zadowoliłby superwzrost. Z tego powodu bity 0 i 1 zostały następnie odwzorowane odpowiednio na współczynniki mnożenia 1 i 2.

Wreszcie, mniej trywialnie: podczas każdego kroku dekodowania jedna nowa liczba całkowita $v_1$ ma być znaleziona jako rozwiązanie równania $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} b_i v_i$, gdzie wszystkie $v_i$ i $b_i$ są znane jako $1 < i \leq n$. Ponieważ nie znamy również $b_1$, otrzymujemy układ z jednym równaniem i dwiema zmiennymi, co pozostawia nam jeden stopień swobody. Aby to poprawić, musimy rozstrzygnąć jedną dodatnią wartość (dla uproszczenia 1), która będzie zawsze przypisana do $b_1$, eliminując w ten sposób niejednoznaczność. Tak więc, ponieważ pierwszy współczynnik jest ustalony na 1, aby zakodować $n$ bitów na każdym kroku, nasze sekwencje liczb całkowitych muszą mieć długość $n + 1$.

Ostatnią kwestią techniczną do rozwiązania jest przypadek, w którym rozmiar wiadomości w bajtach nie jest wielokrotnością rozmiaru bloku. Innymi słowy, co zrobić z ewentualnymi pozostałymi bajtami ostatniego bloku danych, aby po odzyskaniu bloków danych zachowane zostały wszystkie bajty oryginalnej treści, ale nie więcej niż one? Rozwiązaliśmy to, powtarzając jeden raz ostatni bajt wiadomości. Po tej kopii następuje losowa sekwencja, w której każdy składnik musi tylko różnić się od poprzedniego. Tak więc, gdy bloki danych są pobierane, ostatni z nich lub, w najgorszym przypadku, przedostatni jest obcinany w ostatnim powtórzeniu bajtów. ^[4]

Pokażmy teraz przykład kryptosystemu SRVB.

Zaczynamy od parametrów:

$k = 4 $;

$m = 4 $;

co daje długość bloku $l = 4 * 4 = 16 $ i ciąg superrosnący $k + 1 = 5 $ naturalnych liczb całkowitych, który jest obsługiwany — tj. liniowo połączony, dodany z wynikiem tej kombinacji liniowej, i zredukowane do ostatnich elementów $k + 1$ —$m = 4$ razy;

Dla uproszczenia, niech następujący będzie (superrosnący) wektor $v_i$:

$(1,2,4,8,16)$

Rzeczywiście, ciąg pierwszych pięciu potęg liczby 2, tylko dlatego, że jest to ciąg superrosnący z pięcioma elementami i najmniejszymi możliwymi ściśle dodatnimi wartościami (w ten sposób unikając 0 w kluczu publicznym, który w trywialny sposób dawałby odpowiednik 0 jego odpowiednika). ).

Jak powiedzieliśmy wcześniej, dla $\alpha = a + bi$, liczby całkowite $a$ i $b$ muszą być względnie pierwsze i zgodnie z nowym ograniczeniem, o którym wspomnieliśmy, musimy zażądać, aby $a^2 + b^2 = \vert\alpha\vert^2 \geq W$. Szybka kalkulacja daje $W = 1590$. Ponieważ $\sqrt{1590} \simeq 39.8$, bardzo wygodnym wyborem $\alpha$ byłoby $\alpha = 39 + 40i$, ponieważ jest wystarczająco duże, aby pomieścić izomorfizm z pierścieniem liczb całkowitych o wartości co najmniej 1590 składników, jednocześnie spełniając $gcd(a,b)=1$. Ponadto musimy wybrać $\theta$ taką, że $gcd(a,\theta)=1$ ^[5] i najlepiej nie za niską, aby $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (również po to, by nie zdradzać informacji). $\theta = 60$ wykonuje pracę, dając:

$-19-1i,1+38i,3-3i,6-6i,12-12i$ ^[6]

Ubrudźmy więc sobie ręce. Odbierz wiadomość Hello Toptal! . Najpierw mapujemy go na tablicę bajtów zgodnie z ASCII i naszą konwencją obcinania bloków danych:

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

Ponieważ nasz blok danych ma długość 16 bitów = 2 bajty, a nasza wiadomość ma 13 znaków, otrzymujemy 7 bloków danych po 2 bajty, z których ostatni zawiera dwukrotną reprezentację bitową znaku '!' . Zaszyfrujmy pierwszy blok krok po kroku. Zwróć szczególną uwagę, ponieważ bity każdego bajtu są brane w kolejności ich znaczenia.

$m=01001000 01100101$

• Pierwszy kawałek pierwszego bajtu: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• Drugi kawałek pierwszego bajtu: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• Pierwszy kawałek drugiego bajtu: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• Drugi kawałek drugiego bajtu: $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

I tak właśnie zmapowaliśmy

„On” $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

Reszta zaszyfrowanej wiadomości wygląda następująco:

„ll” $\strzałka w prawo(12-12i,21-2i,61-3i,185-31i,367-59i)$

„o” $\strzałka w prawo(12-12i,25+33i,65+32i,111+44i,244+124i)$

„Do” $\Strzałka w prawo(12-12i,9+10i,46+12i,149+5i,277+31i)$

„pkt” $\strzałka w prawo(12-12i,3+16i,46+12i,73+23i,201+49i)$

„al” $\Strzałka w prawo(12-12i,4+54i,44+53i,117+193i,231+389i)$

”!!” $\Strzałka w prawo(12-12i,4+54i,32+65i,63+92i,121+247i)$

Teraz do odszyfrowania mamy $\theta^{-1}=60^{-1}=27+i$:

$($”On” $\Rightarrow)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93,223,527)$

Teraz przychodzi algorytm zachłanny:

Najpierw odejmujemy każdy czynnik przyczyniający się pomnożony przez jeden, ponieważ wiadomo, że przyczyniły się one przynajmniej raz na koniec, otrzymując:

• Drugi skubnięcie drugiego bajtu:

$T \leftarrow (527-233-93-47-16) = 148$

$(T \geq 223) = (148 \geq 223) = fałsz \Rightarrow b_1=0 ; T \leftarrow (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = prawda \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = prawda \Rightarrow b_3 = 1; T \leftarrow (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = fałsz \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 16) = 8$

Wynik: 0110;

Reszta: 8 (dodana na początku sekwencji jako nowy najniższy element);

Upuść 527 z finału bieżącej sekwencji;

• Pierwszy kawałek drugiego bajtu:

$T \leftarrow (233-93-47-16-8) = 59$

$(T \geq 93) = (59 \geq 93) = fałsz \Rightarrow b_1 = 0; T \leftarrow(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = prawda \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = fałsz \Rightarrow b_3 = 0; T \leftarrow (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = prawda \Rightarrow b_4 = 1; T \leftarrow (T - 0 * 12) = 4$

Wynik: 0101;

Reszta: 4 (dodawana na początku sekwencji jako nowy najniższy element);

Wyrzuć 233 z finału bieżącej sekwencji;

• Drugi skubnięcie pierwszego bajtu:

$T \leftarrow (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = fałsz \Rightarrow b_1 = 0; T \leftarrow (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = prawda \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = fałsz \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = fałsz \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 4) = 2$

Wynik: 0100;

Reszta: 2 (dodawana na początku sekwencji jako nowy najniższy element);

Drop 93 z finału bieżącej sekwencji;

• Pierwszy kawałek pierwszego bajtu:

$T \leftarrow (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = prawda \Rightarrow b_1 = 1; T \leftarrow (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = fałsz \Rightarrow b_2 = 0; T \leftarrow (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = fałsz \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = fałsz \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 2) = 1$

Wynik: 1000;

Reszta: 1 (dodawana na początku sekwencji jako nowy najniższy element);

Wyrzuć 47 z finału aktualnej sekwencji;

W rezultacie odzyskaliśmy blok danych: „01001000 01100101” zawierający pierwsze dwa znaki „He” naszej wiadomości. Co więcej, poprawnie pobraliśmy również naszą sekwencję superzwiększającą klucza prywatnego $(1,2,4,8,16)$.

Pozostałe mapy bloków danych przebiegają w ten sam sposób.

Porównanie z głównymi kryptosystemami klucza publicznego

SRVB to:

1. Całkowicie darmowy i publiczny;

2. znacznie prostsze i łatwiejsze do zrozumienia i wdrożenia niż ECC ^[7] ;

3. Obfite w klucze, a więc praktycznie bezkosztowe, w przeciwieństwie do RSA, który opiera się na liczbach pierwszych, które są drogie.

Możemy już podsumować najbardziej prawdopodobne podatności. Ponieważ SRVB wywodzi się od MH, łatwo podejrzewać, że będzie podatny na uogólnienie ataku Szamira lub innego, który go przełamie. Chociaż autor miał powody, by sądzić, że tak nie jest, nie zostało to jeszcze potwierdzone (co jest bardzo typowe w przypadku kryptosystemów).

Co dalej?

Rocha zaobserwował kilka uogólnień dotyczących stosowanych pierścieni ilorazowych, które mogą prowadzić do zwiększenia złożoności kryptoanalizy. Zbadamy również te możliwości.

Liniowe zaciemnianie algebraiczne

Tak się składa, że ​​podczas opracowywania i dokumentacji SRVB, Villas Boas wymyślił jeszcze inne podejście do ulepszenia koncepcji plecakowego kryptosystemu klucza publicznego, które nie zostanie tutaj szczegółowo wyjaśnione, aby ten artykuł nie stał się zbyt długi i męczące, ale tutaj jest to przeglądanie. Jeśli nie uda ci się go zrozumieć, nie martw się, po prostu czekaj na wydanie naszego następnego artykułu, w którym dokładniej omówimy szczegóły: Zobacz podzbiór sum $y$, powiedzmy, $N$ iloraz elementów pierścienia $u_i$ (które są izomorficznie odpowiadające dodatnim liczbom całkowitym $v_i$ ciągu superrosnącego, jak poprzednio) jako mnożenie wektora wierszowego tych $u_i$ przez wektor kolumnowy $B$ ( dla binarnych) zer i jedynek ^[8] .

$y = \sum_{i=1}^n u_i b_i = (u_1,\cdot\cdot\cdot,u_n)^T\cdot(b_1,\cdot\cdot\cdot,b_n)$=UB,

gdzie $b_i \w {0,1}$

Teraz wyobraź sobie, że zamiast tego wektora $u_i$, masz po lewej macierz $n$ przez $N$ (z $n < N$) macierz $v_i$ (liczby całkowite ze sekwencja) wektor jako (bez utraty ogólności) jego pierwszy wiersz i wszystkie pozostałe wpisy wypełnione szumem. Zauważ, że teraz pomnożenie V przez ten sam wektor bitów B daje wektor kolumnowy W, który ma $w$ jako pierwszy wpis i szum w pozostałych. Teraz weź tę macierz V i pomnóż ją przez losową ^[9] macierz n przez n R po lewej, definiując macierz n przez N P:

P = RV

Pomysł polega na tym, że Bob używa P jako swojego nowego klucza publicznego. Ze względu na losowość R wektor

$Y = PB = RV B = RW$

ma informację $w$ zasłoniętą przez szum w innych wierszach V. Bob również oblicza z góry i przechowuje wektor wiersza S, który spełnia:

$R^TS^T = e_1$

Kiedy Alicja wysyła Y do Boba, po prostu znajduje SY, ponieważ:

$SY=S(PB)=S((RV)B)=SRVB= {e_1}^TR^{-1}((RV)B)=$

(na razie tylko definicje)

${e_1}^T (VB)={e_1}^TW = w$

(Teraz wykorzystuję asocjację do anulowania Rs)

and then proceeds as before to extract the vector of $b_i$ from $w$ by means of the greedy algorithm.

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

Acknowledgments

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

Słowniczek

1. Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
2. Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
3. Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
4. Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
5. Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
6. Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
7. Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
8. Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
9. Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
10. Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
11. Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
12. Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
13. Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
14. Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
15. Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
16. Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
17. Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
18. Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
19. Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

1. Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
2. Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.