Pomysł na dzisiejszy wpis przyszedł mi do głowy po lekturze tego oto artykułu, który w pierwszej chwili uznałem za humbug - a który końcem końców okazał się prawdą.
Istnieją decyzje, do których podjęcia wymagana jest zgoda co najmniej dwóch osób. Na przykład:
- Odpalenie rakiety z ładunkiem jądrowym z pokładu amerykańskiej łodzi podwodnej wymaga, aby dwaj oficerowie użyli swoich kluczy do aktywowania mechanizmu.
- Depozyty bankowe - w większości banków, do otwarcia depozytu wymagany jest klucz klienta oraz klucz banku.
- W wielu korporacjach, powyżej pewnej kwoty na zleceniu przelewu wychodzącego muszą znaleźć się podpisy dwójki osób z wybranej trójki (zazwyczaj CEO, CFO, kontroler).
A jak to wygląda w kontekście szyfrowania danych?
Podejścia są dwa. Pierwsze to wspomniany w tytule algorytm SSS (Shamir's Secret Sharing), a drugie to kryptografia progowa.
O kryptografii progowej dziś nie napiszę, bo temat jest duży i trudny, a ja jestem leniwa klucha. Ale objaśnię pokrótce o co chodzi w SSS.
Idea jest taka, że grupa osób dostaje uprawnienie dostępu do pewnych tajnych danych, z zastrzeżeniem jednak, że co najmniej X spośród nich musi wyrazić zgodę. Jak to zrealizować?
W sercu algorytmu SSS leży fakt, że wielomian stopnia (X-1) wymaga co najmniej (X) znanych punktów, żeby jednoznacznie ustalić jego współczynniki.
Ci z nas, którzy uważali na lekcjach matematyki w szkole średniej, być może kojarzą, że równanie hiperboli kwadratowej da się odgadnąć mając dane współrzędne trzech punktów, przez które owa hiperbola przechodzi.
Tak więc w przypadku X osób wystarczy skonstruować wielomian (X-1) stopnia z losowymi współczynnikami przy poszczególnych potęgach, a następnie przesunąć go w pionie w taki sposób, żeby jego wykres przecinał oś Y w punkcie reprezentującym tajne dane. Po czym losujemy tyle różnych punktów (x, y) na wykresie tego wielomianu ile osób jest w grupie, każdemu przekazujemy informację o jednym z tych punktów - i już. Gotowe. Od tej pory żeby odkryć tajne dane, co najmniej X osób musi zebrać się do kupy i ujawnić swoje punkty (x, y).
Jedyną "wadą" tego algorytmu (cudzysłów zamierzony) jest jego jednorazowość. W momencie, kiedy owych X osób już się spotka i ujawni swoje klucze, wielomian staje się jawny i nie da się go wykorzystać ponownie. Piszę o tym, ponieważ w praktyce "tajne dane" to zazwyczaj klucz kryptograficzny, za pomocą którego możemy zdeszyfrować dane właściwe (np. jakieś dokumenty). Po ujawnieniu i wykorzystaniu takiego klucza staje się on bezużyteczny. Wspomniana wcześniej kryptografia progowa nie ma tego ograniczenia, ale do jej ogarnięcia potrzeba misia o dużo większym rozumku od mojego.
Oczywiście to, co tu napisałem, to jest tylko szkielet. Obrzucenie go mięchem konkretnych algorytmów i bibliotek to zadanie iście gargantuiczne - na szczęście ktoś już to przed nami zrobił. Jeżeli kodujesz w Pythonie, możesz skorzystać z gotowca w postaci secretsharing (pip install secretsharing), inne języki też mają gotowe rozwiązania (na przykład https://github.com/shinji-san/SecretSharingDotNet w C#).
P.S. Temat może się nieco kojarzyć z opisywaną już tutaj kiedyś kryptografią romantyczną.
P.S.2. Proszę też nie mylić SSS z SSSS. A już w żadnym razie z Waffen-SS 🙂
„równanie hiperboli kwadratowej da się odgadnąć mając dane współrzędne trzech punktów”
Jest mały haczyk, a w zasadzie HAK. Trzeba wiedzieć, że chodzi o hiperbolę, a nie o okrąg, elipsę, czy parabolę lub inną krzywą stopnia drugiego, których jest pieriard. Więc tak na prawdę, jak ktoś szpieguje lub szyfruje od zera, to jest potrzebnych pięć punktów, bo równanie drugiego stopnia tyle (po drobnych przeróbkach) może mieć parametrów.
A jak już o krzywych stopnia 2 to proponuję obejrzenie innej, siostrzanej krzywej, którą ostatnio narysowałem, ale w nieco nietypowy sposób. Proszę wpisać do GPT-5 poniższy tekst:
Narysuj w skali logarytmicznej wykres początkowych 1000 nieparzystych wyrazów ciągu Collatza dla liczby początkowej: c_0 =
3914872801469817381239643396841325131937300787740736195122731882317939031506736131733722915064493652635261729591129819458604271134122288657988792109441938786267505273036551708704337819098853476988304729736665938226905070692698545635059344194713528671580315972059295283686834296717885244903788632474141370587533803188629181045432315122722506566208513961973712674701989174992516688555214151371992852830584796226734318009713611958365649522320179864545439824256535851276904644566585
Za pierwszym razem zbędzie was kodem Pythona lub innymi bzdetami – wtedy twardo i nieustępliwie powtórzcie polecenie: „narysuj wykres”.
Kurdę, nie zrozumiał mnie i narysował parabolę. Gupie elemelki 🙂
A propos, czy jako osoba pracująca w IT, wiesz może, jak działa root/su/sudo w średnich i dużych firmach? Mamy sobie firmę X, średniej wielkości. Ta firma korzysta oczywiście z systemu komputerowego, więc gdzieś musi znajdować się jakiś OS, który tym wszystkim (albo przynajmniej kluczową częścią tego wszystkiego) zarządza. Na szczycie piramidki użytkowników znajduje się osoba z uprawnieniami administratora. Czy ów admin, gdyby mu odbiło, mógłby po prostu zrobić
i do widzenia? Czy może „root access” podzielony jest jakoś na kilka osób? A może to działa jeszcze inaczej?
W dużych korporacjach uprawnienia prawie zawsze są zorganizowane w postaci grup bezpieczeństwa (tak się tłumaczy „security groups”?).
Na ogół jest też dwóch albo trzech gości na całą firmę, którzy mogą uruchomić odpowiednik `rm -rf` z uprawnieniami administratora i narobić przez to niezłego galimatiasu. Nie słyszałem natomiast w tym kontekście o rozwiązaniu analogicznym do dwóch kluczy żeby odpalić atomówkę 🙂
Banki i rakiety chyba nieco nie pasują jako przykład, bo tam potrzebne są oba klucze. Tj. nie ma redundancji kluczy (czy też osób). Taki podział, gdzie potrzebne są wszystkie części jest dużo prostszy, bo wystarczy dać każdemu 1/n klucza. Np. co n-ty bit.
SSS jest o tyle fajny, że można wymagać dowolnej liczby z większej liczby. Np. 3 z 5.
Banki pasują (2 z 3). Rakiety też, powiedzmy: 2 z 2 🙂
Jest różnie. Na pewno jest stosowany wariant z podziałem sekretów (np. hasła) na dwie części, zapisane w osobnych kopertach. Czyli odpowiednik kluczy do rakiet.
Do tego masz backupy (powodzenia w przywracaniu ;-)). Więc teoretycznie to o czym piszesz nie da się wykonać i nie jest tak destrukcyjne. A w praktyce…
Banki 2 z 3? Wydaje mi się, że nie, bo klucz banku zawsze jest wymagany. Kluczy klienckich może być wiele, ale są chyba identyczne.
2 z 2 to szczególny przypadek i wersja z podziałem bitów jest wtedy prostsza. Choć nie wiem czy jest równie bezpieczna.
Pomyliło mi się z korporacją. W banku jest faktycznie 2 na 2. W korpo jest na ogół 2 na 3.