Dzielenie sekretu
Dzielenie sekretu (współdzielenie tajemnicy) – 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 -progowy, jeśli fragmentów jest a do odtworzenia sekretu trzeba zebrać ich Dowolny zbiór 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 Szamira i George Blakleya w 1979 roku.
Ograniczenia na dzielenie sekretu
[edytuj | edytuj kod]Protokoły dzielenia sekretu zaprojektowane przez Adi Szamira 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 fragmentów nie pozwala odtworzyć ani jednego bitu informacji, a 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 -progowy wymaga użycia losowych bitów. Intuicyjnie wynika to z faktu że do uzyskania podziału potrzebnych jest losowych fragmentów o wielkości równej wielkości sekretu.
Trywialne dzielenie sekretu
[edytuj | edytuj kod]Dzielenie -progowe jest trywialne do uzyskania: Zapisujemy sekret jako liczbę z jakiegoś przedziału, np. od do Generujemy fragmentów z losowych liczb mniejszych od Ostatni fragment wyliczamy: Mając wszystkie fragmenty, możemy wyliczyć ich sumę mod otrzymując Każdy mniejszy zbiór fragmentów generuje losowy wynik.
Przykład: Sekret to liczba od 0 do 9999, załóżmy, że wynosi 1410,
- losujemy powiedzmy 915,
- losujemy powiedzmy 6321,
- losujemy powiedzmy 4530,
- obliczamy
Jeśli wszyscy uczestnicy będą chcieli poznać sekret, dodają swoje fragmenty i otrzymają:
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 -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 punktów wyznacza jednoznacznie wielomian stopnia W protokole Shamira osoba dzieląca wybiera wielomian stopnia 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 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 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 podprzestrzeni o kowymiarze w -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.
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.