Rozważmy scenariusz, w którym konieczne jest zapewnienie bezpieczeństwa bankowego skarbca. Uważa się, że jest on całkowicie niedostępny bez klucza, który otrzymujesz w pierwszy dzień pracy. Twoim celem jest niezawodnie przechować klucz.

Załóżmy, że postanowiłeś cały czas trzymać klucz przy sobie, udostępniając dostęp do skarbca w razie potrzeby. Szybko jednak zrozumiesz, że takie rozwiązanie w praktyce nie skaluję się normalnie, ponieważ za każdym razem do otwarcia skarbca wymagana jest twoja fizyczna obecność. A co z obiecanym urlopem? Co więcej, jeszcze bardziej przeraża pytanie: co jeśli zgubisz jedyny klucz?

Myśląc o urlopie, postanawiasz zrobić kopię klucza i powierzyć ją innemu pracownikowi. Jednak zdajesz sobie sprawę, że to również nie jest idealne. Podwajając liczbę kluczy, podwajasz także możliwości kradzieży klucza.

Zdesperowany, niszczysz duplikat i decydujesz się podzielić oryginalny klucz na pół. Teraz, myślisz, dwie zaufane osoby z fragmentami klucza muszą fizycznie być obecne, aby zebrać klucz i otworzyć skarbiec. Oznacza to, że złodziej musi ukraść dwa fragmenty, co jest dwa razy trudniejsze niż kradzież jednego klucza. Jednak wkrótce uświadamiasz sobie, że ten schemat niewiele różni się od posiadania jednego klucza, ponieważ jeśli ktoś zgubi połowę klucza, całego klucza nie można odzyskać.

Problem można rozwiązać za pomocą serii dodatkowych kluczy i zamków, ale przy takim podejściu szybko zaistnieje potrzeba wielu kluczy i zamków. Postanawiasz, że w idealnym schemacie klucz powinien być podzielony, aby bezpieczeństwo nie zależało całkowicie od jednej osoby. Dochodzisz również do wniosku, że powinno istnieć pewne progi liczby fragmentów, aby przy utracie jednego fragmentu (lub jeśli osoba poszła na urlop) cały klucz pozostawał funkcjonalny.

Jak podzielić sekret

O takim typie schematu zarządzania kluczami myślał Adi Shamir w 1979 roku, gdy opublikował swoją pracę „Jak podzielić sekret”. W artykule krótko wyjaśniono tzw. schemat progowy do efektywnego podziału tajnej wartości (np. klucza kryptograficznego) na części. Następnie, gdy i tylko gdy co najmniej z części są zbierane, tajemnica może być łatwo odzyskana. .

Z punktu widzenia bezpieczeństwa kluczową cechą tego schematu jest to, że atakujący nie powinien dowiedzieć się niczego, jeśli nie ma przynajmniej części. Nawet posiadanie części nie powinno dawać żadnych informacji. Nazywamy tę cechę bezpieczeństwem semantycznym.

Interpolacja wielomianowa

Schemat progowy Shamira oparty jest na koncepcji interpolacji wielomianowej. Jeśli nie jesteś zaznajomiony z tą koncepcją, jest to naprawdę dość proste. Ogólnie rzecz biorąc, jeśli kiedykolwiek rysowałeś punkty na wykresie i potem łączyłeś je liniami lub krzywymi, już ją stosowałeś!

Przez dwa punkty można przeprowadzić nieskończoną liczbę wielomianów stopnia 2. Aby wybrać z nich jeden — potrzebny jest trzeci punkt. Ilustracja: Wikipedia

Rozważmy wielomian o stopniu jeden, . Jeśli chcesz narysować tę funkcję na wykresie, ile punktów potrzebujesz? Cóż, wiemy, że jest to funkcja liniowa, która tworzy linię i dlatego potrzebne są co najmniej dwa punkty. Następnie rozważmy funkcję wielomianową o stopniu dwa, . Jest to funkcja kwadratowa, więc do narysowania wykresu potrzeba co najmniej trzech punktów. A co z wielomianem o stopniu trzy? Co najmniej cztery punkty. I tak dalej.

Naprawdę fajną rzeczą w tej właściwości jest to, że, biorąc pod uwagę stopień funkcji wielomianowej i co najmniej punktów, możemy wyprowadzić dodatkowe punkty dla tej funkcji wielomianowej. Ekstrapolację tych dodatkowych punktów nazywamy interpolacją wielomianową.

Sporządzanie tajemnicy

Możesz już zrozumieć, że tutaj wkracza w grę inteligentny schemat Shamira. Załóżmy, że nasza tajemnica — to . Możemy zamienić w punkt na wykresie i wymyślić funkcję wielomianową o stopniu , która spełnia ten punkt. Przypomnijmy, że będzie naszym progiem wymaganych fragmentów, więc jeśli ustawimy próg na trzy fragmenty, musimy wybrać funkcję wielomianową o stopniu dwa.

Nasz wielomian będzie miał postać , gdzie i — losowo wybrane dodatnie liczby całkowite. Po prostu tworzymy wielomian o stopniu , gdzie współczynnik wolny  jest naszą tajemnicą , a każdy z następnych członkom przypisano losowo wybrany dodatni współczynnik. Jeśli wrócimy do pierwotnego przykładu i założymy, że , to wtedy otrzymamy funkcję .

Na tym etapie możemy generować fragmenty, łącząc unikalne liczby całkowite w , gdzie (ponieważ to jest nasza tajemnica). W tym przykładzie chcemy rozdać cztery fragmenty z progiem trzy, dlatego losowo generujemy punkty i wysyłamy po jednym punkcie do każdego z czterech zaufanych osób, strażników klucza. Informujemy również ludzi, że , ponieważ to jest uznawane za informację publiczną i jest niezbędne do odzyskania .

Odzyskiwanie tajemnicy

Już omówiliśmy koncepcję interpolacji wielomianowej i to, co leży u podstaw schematu progowego Shamira . Gdy jakiekolwiek trzy z czterech zaufanych osób chcą odzyskać , muszą tylko przeprowadzić interpolację swoimi unikalnymi punktami. W tym celu mogą określić swoje punkty i obliczyć interpolacyjny wielomian Lagrange'a, używając następującego wzoru. Jeśli programowanie jest dla Ciebie jaśniejsze niż matematyka, to π jest zasadniczo operatorem for, który mnoży wszystkie wyniki, a σ to for, który wszystko sumuje.

Przy możemy to rozwiązać w następujący sposób, aby zwrócić naszą pierwotną funkcję wielomianową:

Ponieważ wiemy, że , odzyskiwanie można przeprowadzić po prostu:

Użycie niebezpiecznej arytmetyki całkowitej

Choć z powodzeniem zastosowaliśmy podstawowy pomysł Shamira , mamy problem, który ignorowaliśmy do tej pory. Nasza funkcja wielomianowa używa niebezpiecznej arytmetyki całkowitej. Zauważ, że dla każdego dodatkowego punktu, który napastnik uzyskuje na wykresie naszej funkcji, pozostaje mniej możliwości dla innych punktów. Możesz to zobaczyć na własne oczy, gdy rysujesz wykres przy rosnącej liczbie punktów dla funkcji wielomianowej używającej arytmetyki całkowitej. To jest kontrproduktywne dla naszego zadeklarowanego celu bezpieczeństwa, ponieważ napastnik nie powinien absolutnie nic wiedzieć, dopóki nie otrzyma przynajmniej fragmentów.

Aby pokazać, jak słaba jest schemat arytmetyki całkowitej, rozważmy scenariusz, w którym napastnik uzyskał dwa punkty i zna informację publiczną, że . Z tej informacji może wywnioskować , równy dwóm, i wprowadzić znane wartości do wzoru i .

Następnie napastnik może znaleźć , obliczając :

Ponieważ zdefiniowaliśmy jako losowo wybrane liczby całkowite dodatnie, istnieje ograniczona liczba możliwych . Dzięki tym informacjom napastnik może wywnioskować , ponieważ wszystko, co jest większe niż 5, uczyni ujemnym. Okazuje się to prawdą, ponieważ zdefiniowaliśmy

Następnie napastnik może obliczyć możliwe wartości , zastępując do :

Z ograniczonym zestawem opcji dla staje się jasne, jak łatwo jest dobrać i zweryfikować wartości . Jest tylko pięć możliwości.

Rozwiązanie problemu z niebezpieczną arytmetyką całkowitą

Aby wyeliminować tę podatność, Shamir proponuje stosowanie arytmetyki modularnej, zastępując na , gdzie i — zbiorem wszystkich liczb pierwszych.

Szybko przypomnijmy sobie, jak działa arytmetyka modularna. Zegar z wskazówkami to już znana koncepcja. Używa on zegarów, które są . Gdy wskazówka godzinowa przechodzi obok dwunastej, wraca z powrotem do jednego. Ciekawą właściwością tego systemu jest to, że patrząc na zegar, nie możemy wywnioskować, ile obrotów wykonała wskazówka godzinowa. Jednak jeśli wiemy, że wskazówka godzinowa minęła 12 cztery razy, możemy całkowicie określić liczbę minionych godzin za pomocą prostego wzoru , gdzie  — to nasz dzielnik (tutaj ),  — to współczynnik (ile razy dzielnik bez reszty przechodzi w liczbę pierwotną, tutaj ), a  — to reszta, którą zazwyczaj zwraca operator modułu (tutaj ). Znajomość wszystkich tych wartości pozwala nam rozwiązać równanie dla , ale jeśli pominiesz współczynnik, nigdy nie będziesz mógł odzyskać pierwotnej wartości.

Można pokazać, jak to poprawia bezpieczeństwo naszego schematu, zastosowując schemat do naszego poprzedniego przykładu i używając . Nasza nowa funkcja wielomianowa , a nowe punkty . Teraz strażnicy klucza mogą ponownie użyć interpolacji wielomianowej do odtworzenia naszej funkcji, tylko tym razem operacje dodawania i mnożenia muszą być połączone z redukcją modulo (np. ).

Zakładając, że napastnik dowiedział się o dwóch z tych nowych punktów, , a informacje publiczne . Tym razem atakujący na podstawie całej dostępnej mu informacji wprowadza następujące funkcje, gdzie  — zbiór wszystkich dodatnich liczb całkowitych, a reprezentuje współczynnik modułu .

Teraz nasz przestępca ponownie znajduje , obliczając :

Następnie ponownie stara się wyprowadzić , zastępując do :

Tym razem ma poważny problem. W równaniu brakuje wartości , i . Ponieważ istnieje nieskończona liczba kombinacji tych zmiennych, nie może uzyskać żadnych dodatkowych informacji.

Rozważania dotyczące bezpieczeństwa

Schemat dzielenia sekretów Shamira oferuje bezpieczeństwo z punktu widzenia teorii informacji. Oznacza to, że matematyka jest odporna nawet na atakującego z nieograniczoną mocą obliczeniową. Jednak schemat wciąż zawiera kilka znanych problemów.

Na przykład schemat Shamira nie tworzy weryfikowalnych fragmentów, to znaczy ludzie mogą swobodnie przedstawiać fałszywe fragmenty i utrudniać odtworzenie prawidłowego sekretu. Wrogi przechowawca fragmentów z wystarczającymi informacjami może nawet wyprodukować inny fragment, zmieniając według własnego uznania. Problem ten rozwiązuje się za pomocą weryfikowalnych schematów dzielenia sekretów, takich jak schemat Feldmana.

Innym problemem jest to, że długość dowolnego fragmentu jest równa długości odpowiadającego mu sekretu, więc długość sekretu jest łatwa do określenia. Problem ten rozwiązuje trywialne wypełnienie sekretu dowolnymi liczbami do stałej długości.

Na koniec ważne jest, aby zauważyć, że nasze obawy dotyczące bezpieczeństwa mogą wykraczać poza sam schemat. W przypadku rzeczywistych aplikacji kryptograficznych często istnieje zagrożenie atakami z boku, kiedy atakujący stara się wydobyć użyteczne informacje z czasu wykonywania aplikacji, pamięci podręcznej, awarii itp. Jeśli to budzi obawy, podczas rozwoju należy dokładnie rozważyć zastosowanie środków zabezpieczających, takich jak funkcje i wyszukiwanie o stałym czasie wykonania, zapobiec zapisaniu pamięci na dysku oraz przemyśleć szereg innych kwestii, które wykraczają poza ten artykuł.

Demo

Na tej stronie jest interaktywna demonstracja schematu dzielenia sekretów Shamira. Demonstracja powstała na bazie biblioteki ssss-js, która sama w sobie jest portem JavaScript popularnego programu ssssZwróć uwagę, że obliczanie dużych wartości , i może zająć trochę czasu.

Źródło: habr.com