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 🙂
Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]
Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.