Sekret Podziałowy Adiego Shamira: Podział Sekretu Tak, Żeby Jedna Osoba Nie Mogła Go Samodzielnie Zrekonstruować

Problem: Zaufanie bez pojedynczego punktu awarii

Cenne sekrety, takie jak klucz główny otwierający cały zaszyfrowany system bazy danych firmy, stwarzają niepokojące dylematy. Oddanie klucza jednej osobie oznacza pojedynczy punkt awarii: ta osoba mogła go zgubić, zostać pod wpływem lub złośliwie z niego skorzystać. Rozdanie pełnej kopii wielu osobom zamiast redukować ryzyko, je go nawet mnoży, ponieważ każda z nich sama mogłaby wycieknąć lub nadużyć sekret. Organizacje pragną raczej schematu progowego: podziel sekrety na fragmenty, zwane udziałami, i przydziel jeden udziało każdej ze wskazanych zaufanych osób, tak aby jakąkolwiek grupę co najmniej o określonej progowej liczbie (np. trzy osoby spośród pięciu akcjonariuszy) mogła połączyć swoje udziały w celu odtworzenia oryginalnego sekretu, ale żadna mniejsza grupa, nawet dwie osoby spośród pięciu, nie uzyskałaby w ogóle żadnych korzyści, ani nawet częściowego wskazania, co ten sekret zawiera. Jest to znacznie silniejsze gwarancje niż zwykłe dzielenie haseł lub szyfrowanie, ponieważ musi ono obowiązywać nawet wobec akcjonariuszy, którzy chcą podzielić się wszystkim, co wiedzą i spróbować każdej sztuczki, aby zgadnąć resztę. Przed pracą Shamura z 1979 roku, budowanie takiego schematu z niezachwianymi matematycznymi gwarancjami, zamiast tylko nieformalnej niedbałości, było zupełnie niewykonalne. Kluczowe odkrycie polegało na rozpoznaniu, że klasyczny instrument z algebry, fakt, że krzywe są określane przez określony liczbę punktów, może zostać ponownie wykorzystany jako prymityw kryptograficzny o udowodnionej ochronie.

Elegancki Triunf: Ukrywanie Tajemnic wewnątrz Wielomianu

Wprowadzenie metody Shamira polegało na zakodowaniu tajemnicy jako pojedynczej liczby i ukryciu tej liczby jako współczynnika losowo wygenerowanego wielomianu. Aby zbudować schemat, w którym dowolny zestaw k udziałów może odtworzyć tajemnicę, należy wygenerować losowy wielomian o stopniu k-1, czyli taki, który ma k współczynników. Stały współczynnik tego wielomianu, jego wartość przy zerze, jest ustawiony równy tajemnicy, a wszystkie pozostałe współczynniki są całkowicie losowo wybierane. Ten wielomian definiuje krzywą, a dealer oblicza n różnych punktów na tej krzywej, po jednym dla każdego z n osób, które będą posiadać udział; udział to proste para współrzędnych składająca się z wartości wejściowej i wyniku wielomianu w tym punkcie. Rozdawanie tych punktów oznacza rozdawanie udziałów. Powód, dla którego to działa, wynika z klasycznej zasady algebry: wielomian o stopniu k-1 jest jednoznacznie określony przez dokładnie k punktów na jego krzywej. Mając dowolne k udziałów, współwłaściciele mogą użyć interpolacji Lagrange'a, dobrze znanego techniki do odtworzenia unikalnego wielomianu przechodzącego przez zadaną kolekcję punktów, a po odtworzeniu pełnego wielomianu po prostu odczytują jego stały współczynnik, wartość przy zerze, aby odzyskać tajemnicę. Cała arytmetyka jest zwykle wykonywana w ciele skończonym, a nie nad zwykłymi liczbami rzeczywistymi, co utrzymuje liczby ograniczone i sprawia, że gwarancje bezpieczeństwa są matematycznie czyste i udowodnione.

Dlaczego k punktów ujawnia wszystko, a k-1 punktów niczego,

Piękrem w scheme Shamira jest nie tylko to, że k udziałów jest wystarczających, ale również to, że k-1 udziałów jest wykazanie bezużyteczne. Z dokładnie k punktami istnieje tylko jeden i jedyny wielomian stopnia k-1 przechodzący przez wszystkie z nich, więc rekonstrukcja jest jednoznaczna i dokładna. Ale usuń nawet jeden z tych punktów, pozostawiając tylko k-1 udziałów, i sytuacja się całkowicie zmienia: istnieje niesko wiele wielomianów stopnia k-1 przechodzących przez te k-1 punkty, a co najważniejsze, dla każdej możliwej wartości sekretu istnieje jakiś wielomian o odpowiednim stopniu, zgodny z wszystkimi znanymi udziałami, którego wyraz stały równa się tej wartości. Innymi słowy, k-1 udziałów jest matematycznie spójne z absolutnie każdym możliwym sekretem, co oznacza, że współudziałowcy nie uzyskali żadnej informacji, nie przesunięcie prawdopodobieństwa, nie zawężenie zakresu przypuszczeń, dosłownie nic poza tym, co wiedzieli przed zobaczeniem jakichkolwiek udziałów. Właściwość tę nazywa się bezpieczeństwem informatycznym i jest to znacznie silniejsze gwarancja niż oferują większość systemów kryptograficznych, ponieważ zachowuje się nawet wobec przeciwnika o nieograniczonych zasobach obliczeniowych. Nie ma żadnych sprytnych obliczeń, nie ma przeszukiwania siłowego, nie ma żadnego częściowego skrótu, który pomógłby grupie poniżej progu; sekret nie jest jedynie trudny do znalezienia, ale rzeczywiście jest niezdecydowany przez informacje, które posiadają.

Przykładowy przykład: Dwa z trzech udziałów przy użyciu prostej linii

Najprostsza wersja schematu wykorzystuje próg dwóch, co oznacza, że wystarczy dwa z trzech udziałów, a opiera się wyłącznie na prostej linii, ponieważ linia jest wielomianem o stopniu pierwszym i jest jednoznacznie określona dokładnie dwoma punktami. Załóżmy, że sekret to liczba 10. Dealer wybiera losową linię, której wartość w zerze wynosi 10, na przykład linię opisowaną jako y równa się 10 plus 3 razy x. Zauważ, że 3 tutaj jest losowo wybranym współczynnikiem, a 10, wartość w zerze, to ukryty sekret. Dealer oblicza trzy udziały, oceniając tę linię w trzech różnych wartościach wejściowych: dla x równa się 1, y równa się 13, dając punkt udziału jeden, trzynaście; dla x równa się 2, y równa się 16, dając punkt udziału dwa, szesnaście; i dla x równa się 3, y równa się 19, dając punkt udziału trzy, dziewiętnaście. Każdy z trzech osób otrzymuje dokładnie jeden z tych trzech punktów i nic więcej. Jeśli jakiekolwiek dwie osoby posiadające udziały, na przykład osoby posiadające jeden, trzynaście i trzy, dziewiętnaście, spotkają się, mogą użyć prostych obliczeń algebraicznych, aby dopasować unikalną linię przechodzącą przez te dwa punkty, odkryć, że jej wartość w zerze wynosi 10, a tym samym odzyskać sekret. Jednak jeśli dostępna jest tylko jedna osoba posiadająca udział, na przykład osoba posiadająca dwa, szesnaście, ten pojedynczy punkt leży na nieskończonej liczbie możliwych linii, każda z nich implikująca inny sekret, więc żadnej informacji o liczbie 10 nie ujawnia się wcale.

Realne Zastosowania: Ochrona Kluczy Początkowych i Cyfrowych Fortepianów

Sposób Sharira na dzielenie sekretu wykracza daleko poza zainteresowanie akademickie, przenikając do codziennej infrastruktury tam, gdzie pojedynczy klucz główny jest po prostu zbyt niebezpieczny, aby powierzyć go jednej osobie lub maszynie. Często spotyka się podział klucza kryptograficznego głównego na kilka osób lub zaufanych administratorów, tak aby nikt, nawet jeśli zostanie on skompromitowany, niedbacznym lub zmusił do działania, nie mógł samodzielnie odblokować krytycznych systemów; odzyskanie klucza wymaga zgody większości uczestniczących w procesie, co również chroni przed utratą lub zapomnieniem klucza przez jedną osobę. Narzędzie HashiCorp Vault, szeroko stosowane do zarządzania sekretami i kluczami szyfrującymi w nowoczesnej infrastrukturze, wykorzystuje dokładnie ten schemat dla swojego procesu odblokowywania, rozdzielając udziały w kluczu na wielu operatorów tak, aby po ponownym uruchomieniu sejfu konieczna była obecność określonej liczby z nich do współpracy. W świecie kryptowalut rozwiązania dotyczące przechowywania zabezpieczonych dużych aktywów często stosują tę samą ideę do kluczy prywatnych lub nasion portfeli, dzieląc je na geograficznie oddzielone udziały lub urządzenia sprzętowe, tak aby pojedynczo skradzione urządzenie, pojedyncze zhakowane laptop lub pojedynczy złośliwy działacz nie mógł opróżnić funduszy, a legalni właściciele nadal mogli odzyskać dostęp poprzez połączenie wystarczającej liczby elementów. Podobnie fundamentalna logika pojawia się również w bezpiecznym wielopartyjnym obliczeniu, planowaniu awaryjnym dla sekretów organizacyjnych oraz wszelkiego rodzaju sytuacjach, w których potrzebne jest zaufanie rozproszone, opierające się na solidnej matematycznej podstawie zamiast jedynie polityki proceduralnej.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Shamir's Secret Sharing: Splitting a Secret So No Single Person Can Reconstruct It Alone i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.