Dzielenie sekretów (secret sharing) w kryptografii — definicja i metody
Poznaj dzielenie sekretów w kryptografii: definicje, metody Shamir/Blakley, zastosowania (RSA, bankowość, wojsko) i praktyczne zabezpieczenia kluczy.
Dzielenie sekretów (ang. secret sharing) to termin odnoszący się do metod podziału sekretu (np. klucza kryptograficznego) pomiędzy wiele osób w taki sposób, że każda osoba otrzymuje tylko część informacji. Aby odtworzyć cały sekret konieczna jest współpraca większej liczby uczestników — pojedyncza część sama w sobie nie wystarcza. Pierwsze formalne schematy dzielenia sekretów opracowali niezależnie Adi Shamir i George Blakley w 1979 roku. Oba ich podejścia zapoczątkowały powstanie tzw. schematów progowych i dalszych uogólnień.
Idea schematu progowego
Najczęściej spotykanym rodzajem jest schemat progowy (t,n) — sekret dzieli się na n udziałów w taki sposób, że dowolne t udziałów (t ≤ n) pozwala odtworzyć sekret, natomiast każde zestawienie mniejszych niż t udziałów nie daje żadnej użytecznej informacji o sekrecie. W praktyce oznacza to, że system toleruje utratę części udziałów oraz chroni przed pojedynczym kompromisem. Rolę rozdającego pełni zwykle dealer, który generuje udziały i rozdaje je uczestnikom.
Schemat Shamira — wielomiany nad ciałami skończonymi
Schemat Shamira opiera się na własnościach wielomianów nad ciałami skończonymi. Dla progu t dealer wybiera losowy wielomian stopnia t−1, którego wyraz wolny to sekret s (wartość w pewnym ciele skończonym, np. modulo pierwsza p większego od sekretu). Następnie oblicza wartość tego wielomianu w n różnych punktach x1, x2, …, xn i rozdaje każdemu uczestnikowi parę (xi, yi). Każde t takich punktów jednoznacznie określa wielomian i tym samym wyraz wolny s (rekonstrukcja np. za pomocą interpolacji Lagrange’a). Znajomość mniej niż t punktów nie daje żadnej informacji o s — jest to więc schemat doskonale tajny (information-theoretic / perfect secrecy).
Schemat Blakleya — metoda geometryczna
Schemat Blakleya wykorzystuje geometrię: sekret reprezentowany jest jako punkt w przestrzeni d-wymiarowej, a każdy udział to hiperpłaszczyzna zawierająca ten punkt. Zbiór odpowiedniej liczby hiperpłaszczyzn przetnie się dokładnie w punkcie sekretu. Metoda Blakleya jest koncepcyjnie prosta, lecz zwykle nie jest idealna (rozmiar udziałów może być większy niż rozmiar sekretu).
Właściwości i odmiany schematów
- Perfect (doskonałe) — mniej niż t udziałów nie daje żadnej informacji o sekrecie (tak jest w Shamirze).
- Idealne — rozmiar pojedynczego udziału jest równy rozmiarowi sekretu (Shamir jest zarówno doskonały, jak i idealny w typowym ustawieniu). Schemat Blakleya zwykle nie jest idealny.
- Ramp schemes — schematy „stopniowe”, w których mniejsze niż t udziały ujawniają pewne ograniczone informacje, ale nadal wymagają więcej niż m udziałów do pełnego odtworzenia; stosowane, gdy dopuszczalne jest pewne kompromitowanie informacji w zamian za mniejsze udziały.
- Access structures — uogólnienia, w których do odtworzenia sekretu uprawnione są określone (monotoniczne) zbiory uczestników, niekoniecznie wszystkie zestawy o rozmiarze ≥ t.
Problemy praktyczne i rozszerzenia
- Verifiable Secret Sharing (VSS) — dodaje mechanizmy weryfikacji udziałów, aby zapobiec oszustwom ze strony rozdającego lub uczestników (np. Pedersen VSS wykorzystuje zobowiązania kryptograficzne).
- Distributed Key Generation (DKG) — eliminuje potrzebę zaufanego rozdającego: uczestnicy wspólnie generują sekret w sposób rozproszony, każdy otrzymuje swój udział bez pojedynczego punktu zaufania.
- Proactive secret sharing — mechanizmy okresowego odświeżania udziałów, które chronią przed przeciwnikiem gromadzącym udziały w czasie (tzw. mobilny przeciwnik).
- Ochrona przed złośliwymi uczestnikami — wymaga protokołów wykrywania i korekcji błędnych lub sfałszowanych udziałów (np. poprzez VSS i protokoły awaryjnego usuwania uczestników).
Zastosowania
Dzielenie sekretów jest wykorzystywane tam, gdzie wymagana jest wysoka bezpieczność i wielopodmiotowa kontrola dostępu. Przykłady:
- Zabezpieczenie kluczy prywatnych (np. dystrybucja tajnego klucza w systemie podpisów). Jednym z przykładów, w którym stosuje się dzielenie sekretów, jest kryptosystem RSA: klucz prywatny można podzielić, aby zapobiec temu, by pojedyncza osoba mogła sporządzać podpisy lub odszyfrowywać dane.
- Systemy bankowe i wojskowe — przechowywanie krytycznych kluczy w sposób wielostronny.
- Proaktywne systemy bezpieczeństwa, backupy kluczy, zarządzanie root key w infrastrukturze PKI, wielopodpisowe portfele kryptowalut (threshold signatures zamiast klasycznego multisig).
- Zastosowania w protokołach MPC (secure multi-party computation) oraz przy rozproszonym tworzeniu podpisów (threshold ECDSA, threshold Schnorr, BLS).
Krótki przykład schematu Shamira (ilustracja)
Prosty przykład na małej arytmetyce modulo p = 11. Niech sekret s = 7, próg t = 3. Dealer wybiera losowy wielomian stopnia 2, np. f(x) = 7 + 3x + 2x^2 (wartości liczone mod 11). Oblicza udziały dla x = 1,2,3,4,...:
- f(1) = 7 + 3 + 2 = 12 ≡ 1 (mod 11)
- f(2) = 7 + 6 + 8 = 21 ≡ 10 (mod 11)
- f(3) = 7 + 9 + 18 = 34 ≡ 1 (mod 11)
Każdy z uczestników otrzymuje parę (xi, yi) — np. (1,1), (2,10), (3,1). Mając dowolne trzy takie punkty można odtworzyć wielomian (np. przez interpolację Lagrange’a) i wyodrębnić wyraz wolny 7 jako sekret. Znajomość jednej lub dwóch par nie ujawnia sekretu.
Podsumowanie
Dzielenie sekretów to kluczowa technika w kryptografii pozwalająca rozproszyć odpowiedzialność i zwiększyć odporność systemu na kompromitacje. Schematy takie jak Shamir i Blakley dają różne możliwości konstrukcyjne; praktyczne wdrożenia sięgają po rozszerzenia — VSS, DKG, mechanizmy proaktywne — by sprostać wymaganiom bezpieczeństwa w środowiskach z nieufnymi uczestnikami i zagrożeniami praktycznymi.
Metoda Shamira
W tej metodzie dowolne t z n akcji może być użyte do odzyskania sekretu. Idea jest taka, że wielomian stopnia t-1 jest zdefiniowany przez t punktów na wielomian: Potrzeba dwóch punktów, aby zdefiniować linię prostą, trzech, aby zdefiniować krzywą kwadratową, czterech dla sześciennej, i tak dalej. Potrzeba t punktów, aby zdefiniować wielomian stopnia t-1. W ten sposób można zbudować wielomian, którego pierwszy współczynnik jest tajny; jest n losowo wybranych współczynników. Każdy gracz otrzymuje jeden z n współczynników. Jeśli jest co najmniej t graczy, to mogą oni odtworzyć oryginalną krzywą i zdobyć sekret.
Pytania i odpowiedzi
P: Czym jest secret sharing?
O: Secret sharing to sposób dzielenia się sekretem przez wiele osób. Każda osoba zna część sekretu, który jest udostępniany, ale wiele osób musi współpracować, aby odtworzyć sekret.
P: Kto opracował metodę secret sharing?
O: Adi Shamir i George Blakley opracowali metodę tajnego współdzielenia, niezależnie od siebie, w 1979 roku.
P: Proszę podać przykład zastosowania metody secret sharing?
O: Podano przykład kryptosystemu RSA, w którym wykorzystywana jest metoda secret sharing. Wykorzystuje on tajny klucz, który jest dystrybuowany wśród wielu osób, dzięki czemu żadna osoba nie może złożyć podpisu.
P: Dlaczego tajne współdzielenie jest ważne w takich obszarach jak banki czy wojsko?
O: Tajne współdzielenie jest ważne w obszarach takich jak banki czy wojsko, ponieważ zapewnia dodatkową warstwę bezpieczeństwa. Nawet jeśli część sekretu jednej osoby zostanie ujawniona lub utracona, wiele innych osób nadal może odtworzyć sekret.
P: Jak wygląda współdzielenie sekretu w prostszej konfiguracji?
O: W łatwiejszej konfiguracji części graczy mogą być łączone w celu utworzenia sekretu, ale każda część zawiera dodatkowe informacje.
P: Jaka jest różnica między łatwiejszą konfiguracją dzielenia się sekretami a innymi konfiguracjami?
O: Łatwiejsza konfiguracja dzielenia się sekretem jest mniej bezpieczna z punktu widzenia teorii informacji, ponieważ odgadnięcie dwóch brakujących części będzie łatwiejsze niż odgadnięcie sekretu, gdy żadne części nie są znane. Druga konfiguracja jest bezpieczna z punktu widzenia teorii informacji.
P: Czy istnieją różne metody bezpiecznego udostępniania sekretów?
O: Tak, istnieją różne metody bezpiecznego dzielenia się sekretami.
Przeszukaj encyklopedię