Dzielenie sekretu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Dzielenie sekretu (współdzielenie tajemnicy) to protokół kryptograficzny, w której pewien sekret jest dzielony na fragmenty i rozdawany uczestnikom w taki sposób, że odtworzyć go może jedynie określona podgrupa użytkowników.

Celem protokołu jest ochrona wiadomości przed utratą zabezpieczającego ją klucza. Wykonanie większej ilości kopii klucza zmniejszałoby bezpieczeństwo systemu, a mniejsza liczba kopii klucza zwiększałaby ryzyko zgubienia ich wszystkich. Protokoły współdzielenia tajemnicy realizują pierwszy przypadek, poprawiając niezawodność systemu, jednak bez zwiększania ryzyka.

Formalnie, w protokole uczestniczy osoba dzieląca, która przygotowuje fragmenty, i gracze którzy je przechowują. Protokół określamy jako (t, n)-progowy, jeśli fragmentów jest n, a do odtworzenia sekretu trzeba zebrać ich t. Dowolny zbiór t-1 fragmentów powinien być całkowicie losowy, i nie pozwalać na odtworzenie nawet części sekretu.

Dzielenie sekretu zostało opracowane niezależnie przez Adi Shamira i George Blakleya w 1979 roku.

Ograniczenia na dzielenie sekretu[edytuj | edytuj kod]

Protokoły dzielenia sekretu zaprojektowane przez Adi Shamira i George Blakleya są bezpieczne teorio-informacyjnie, co oznacza że nawet przeciwnik dysponujący nieograniczoną mocą obliczeniową nie jest w stanie ich oszukać.

Wynikają z tego pewne ograniczenia, które musi spełniać każdy taki protokół:

  • Każdy fragment sekretu musi mieć długość co najmniej równą długości sekretu. Formalnie można to udowodnić w terminach teorii informacji, ale ma to też intuicyjne wyjaśnienie: Skoro t-1 fragmentów nie pozwala odtworzyć ani jednego bitu informacji, a t pozwala odtworzyć wszystkie, ostatni fragment musi zawierać wystarczającą liczbę bitów.
  • Protokół musi używać losowych bitów. Każdy bit tajnej informacji podzielonej w sposób (t, n)-progowy wymaga użycia t-1 losowych bitów. Intuicyjnie wynika to z faktu że do uzyskania podziału potrzebnych jest t-1 losowych fragmentów o wielkości równej wielkości sekretu.

Trywialne dzielenie sekretu[edytuj | edytuj kod]

Dzielenie (n, n)-progowe jest trywialne do uzyskania: Zapisujemy sekret jako liczbę s z jakiegoś przedziału, np. od 0 do k-1. Generujemy n-1 fragmentów z losowych liczb mniejszych od k. s_1,s_2,...,s_{n-1}. Ostatni fragment wyliczamy: s_n=s - s_1 - s_2 - ... - s_{n-1} \bmod k. Mając wszystkie fragmenty możemy wyliczyć ich sumę mod k, otrzymując s. Każdy mniejszy zbiór fragmentów generuje losowy wynik.

Przykład: Sekret s to liczba od 0 do 9999, załóżmy że wynosi 1410

  • losujemy s_1, powiedzmy 915
  • losujemy s_2, powiedzmy 6321
  • losujemy s_3, powiedzmy 4530
  • obliczamy s_4 = (1410 - 915 - 6321 - 4530) \bmod 10000 = -10356 \bmod 10000 = - 356

Jeśli wszyscy uczestnicy będą chcieli poznać sekret, dodają swoje fragmenty i otrzymają:

(s_1 + s_2 + s_3 + s_4)\bmod 10000 = 11410 \bmod 10000 = 1410

Jeśli nie mamy ograniczeń pamięciowych, możemy użyć tej metody do wygenerowania dowolnego schematu dzielenia sekretu. Dla dowolnego zbioru graczy który ma mieć możliwość odtworzenia sekretu generujemy wtedy osobny podział. Przykładowo jeśli chcemy żeby z trzech graczy każdych dwóch mogło odtworzyć sekret, generujemy trzy niezależne podziały (2, 2)-progowe. Takie podejście szybko staje się niepraktyczne: przykładowo gdy każdych 10 z 20 graczy ma móc odtworzyć sekret, musielibyśmy stworzyć ponad 180 tysięcy podziałów. Dlatego wykorzystuje się bardziej zaawansowane protokoły podziału.

Protokół Shamira[edytuj | edytuj kod]

Dwa punkty wyznaczają jednoznacznie prostą, trzy punkty wyznaczają parabolę, i ogólnie n punktów wyznacza jednoznacznie wielomian stopnia n-1. W protokole Shamira osoba dzieląca wybiera wielomian stopnia t-1, którego wartość np. w zerze jest równa sekretowi. Jako fragmenty sekretu udostępniane są wartości tego wielomianu w różnych punktach. Zebranie t punktów pozwala dokonać interpolacji wielomianu i wyznaczyć jego wartość w zerze.

Operowanie zwykłymi wielomianami jest niepraktyczne – przy dużej losowości jego współczynników wartości w różnych punktach mogą zajmować sporo miejsca. Dlatego zwykle dla oszczędności definiuje się te wielomiany nad ciałami skończonymi, takimi jak np. liczby całkowite modulo p. W ten sposób każdy fragment zajmuje tyle miejsca ile sekret, gdyż współrzędne x dla kolejnych graczy mogą być jawne. Ilość losowych bitów potrzebnych do wygenerowania wielomianu również jest minimalna.

Protokół Blakleya[edytuj | edytuj kod]

Dwie nierównoległe proste na płaszczyźnie przecinają się w jednym punkcie. Trzy płaszczyzny w przestrzeni również przecinają się w jednym punkcie. Ogólnie n podprzestrzeni o kowymiarze 1 w n-wymiarowej przestrzeni wyznacza jeden punkt. Tajna informacja może zostać zakodowana jako jedna ze współrzędnych tego punktu. Jeśli byłaby zakodowana we wszystkich współrzędnych, wtedy posiadanie części fragmentów pozwalałoby wyznaczyć pewne zależności pomiędzy nimi, co oznaczałoby że protokół nie jest całkowicie bezpieczny.

Jeden fragment Dwa fragmenty wyznaczające prostą Trzy fragmenty wyznaczające punkt
Protokół Blakleya w trzech wymiarach. Każdy fragment jest płaszczyzną, tajna informacja jest ukryta w położeniu wspólnego punktu. Dwa fragmenty nie wystarczają do jego określenia, mogą jednak powiedzieć jak się mają do siebie współrzędne tego punktu (wyznaczają prostą na której on leży).

Protokół Blakleya w tej postaci zużywa więcej pamięci na przechowywanie sekretów niż protokół Shamira. Można jednak nałożyć dodatkowe warunki na postać fragmentów, uzyskując protokół równie efektywny do tamtego.

Rozwinięcia protokołu[edytuj | edytuj kod]

Dając uczestnikom różne liczby fragmentów możemy manipulować grupami które mogą odtworzyć sekret (przykładowo może to być dowolny zestaw akcjonariuszy posiadający 51% akcji). Bardziej skomplikowane podziały można uzyskać przez dzielenie fragmentów sekretu na kolejne sekrety.

Dzielenie sekretu często umożliwia łatwe dodawanie do siebie sekretów bez ich ujawniania, a przy dodatkowej wymianie informacji również ich mnożenie. Przy zastosowaniu weryfikowalnego dzielenia sekretu (VSS) stanowi to podstawę obliczeń wielopodmiotowych.