Powiedzieć Wam sekret?

03.02.2010 - Agata Murawska
TrudnośćTrudność

A może by tak po chińsku?

Można o dzieleniu sekretów myśleć także w kategoriach bardziej teorioliczbowych - wtedy algorytm podziału wiadomości $ D $ na $ n $ części, z których $ k $ wystarczy do odtworzenia informacji wygląda nieco inaczej:

1. Ustalamy ciąg liczb parami względnie pierwszych $ m_1 < m_2 < \dots < m_n $, większych od $ 1 $. Liczby te mają spełniać warunek $ m_1 m_2\dots m_k > D >m_n m_{n-1} \dots m_{n-k+2} $
2. Obliczamy fragmenty sekretu do podziału: $ I_i $ takie, że $ D\equiv I_i (\mod m_i) $.
3. Obliczamy $ M=m_1 m_2\dots m_n $.
4. Do $ i $-tej osoby wysyłamy trójkę $ (I_i, m_i, M) $.

Co dokładnie oznacza warunek na iloczyn $ m_i $ w kroku pierwszym? Przeczytajmy go dokładniej:

  • $ 1 <m_1 < m_2 < \dots < m_n $
  • $ m_i $ są parami względnie pierwsze
  • $ m_1 m_2\dots m_k > D >m_n m_{n-1} \dots m_{n-k+2} $
Skoro ciąg $ <m_i> $ jest rosnący, to iloczyn $ m_1 m_2\dots m_k $ jest najmniejszym iloczynem $ k $ elementów ciągu $ <m_i> $. Oznaczmy go zatem przez $ \min_{m_i}(k) $.
Podobnie iloczyn $ k-1 $ ostatnich elementów ciągu: $ m_n m_{n-1} \dots m_{n-k+2} $ jest największym takim iloczynem - oznaczmy go zatem, analogicznie, jako $ \max_{m_i}(k-1) $.
Warunek z ostatniego podpunku brzmi teraz nieco czytelniej: $ \min_{m_i}(k) > D > \max_{m_i}(k-1) $.
Skoro najmniejszy $ k $-elementowy pociąg ciągu $ <m_i> $ jest większy, niż $ D $, to każdy podciąg $ k $-elementowy jest większy.
Podobnie z drugiej strony - skoro największy podciąg $ k-1 $-elementowy jest mniejszy, niż $ D $, to każdy inny pociąg $ k-1 $-elementowy także, siłą rzeczy, jest mniejszy od $ D $.
Podobnie jak wcześniej, sposób podziału tajemnicy (przynajmniej po krótkim wyjaśnieniu) nie wygląda groźnie ani skomplikowanie. Dlaczego zatem dzielimy sekret "po chińsku"? Za moment tajemnica się rozwikła..

Przejdźmy do odzyskiwania sekretu, mając do dyspozycji $ k $ kompletów wartości: $ (I_{i_1}, m_{i_1}, M), (I_{i_2}, m_{i_2}, M), \dots (I_{i_k}, m_{i_k}, M) $ Szukane przez nas $ D $ jest rozwiązaniem układu równań:
$ I_{i_1} \equiv D \mod m_{i_1} $
$ I_{i_2} \equiv D \mod m_{i_2} $
...
$ I_{i_k} \equiv D \mod m_{i_k} $
Czy czegoś to nam nie przypomina?
Chińskie twierdzenie o resztach mówi, że taki układ równań ma dokładnie jedno rozwiązanie wśród liczb mniejszych od $ m_{i_1}m_{i_2}\dots m_{i_k} $. Na szczęście, $ D $ jest mniejsze od każdego możliwego iloczynu $ k $ liczb z ciągu $ <m_i> $, więc odtworzenie go jest możliwe przy użyciu standardowego algorytmu podanego w artykule o ChTwoR.
Znaleźliśmy Chińczyków, pozostaje więc tylko uzasadnić, że mniej niż $ k $ osób nie jest w stanie odkryć sekretu - ale ponownie, jest to prosty wniosek z chińskiego twierdzenia o resztach - wystarczy przypomnieć sobie, że każdy iloczyn $ k-1 $ (i mniej) liczb jest, z założenia, mniejszy od $ D $.

Większy sekret - większe wymagania

Wszystko to bardzo pięknie - ale czasem zdarzają się sekrety, których nie można tak po prostu podzielić i rozdać byle komu. Na przykład, jeśli chcemy zabezpieczyć kody głowic atomowych, prezydent powinien mieć możliwość podjęcia decyzji co do ich użycia nawet przy sprzeciwie całego sztabu. Z drugiej strony, sztab pod nieobecność prezydenta powinien móc podjąć decyzję samodzielnie.

Klucz

Z tego typu modyfikacją jesteśmy w stanie sobie poradzić. Niech $ n $ będzie liczbą generałów w sztabie. Podzielimy sekret na $ 2n $ części, z których $ n $ otrzyma prezydent, a pozostałe zostaną rozdzielone po równo między generałów. Za $ k $ możemy przyjąć dowolną liczbę nie większą od $ n $ - w zależności od tego, ile władzy chcemy dać sztabowi.

Problem pojawia się gdy chcemy na przykład pozwolić podjąć decyzję $ 2 $ generałom lub $ 1 $ generałowi i $ 2 $ pułkownikom i tak dalej - jednak da się to zrobić, jednak metody stosowane w ogólnych przypadkach są dalece zbyt skomplikowane, żeby je tu omawiać.

Ktoś tu kłamie..

We wszystkich przedstawionych schematach powtarza się niestety jeden, dość istotny problem. Nie jesteśmy w stanie w żaden sposób zweryfikować, czy powiernicy naszego sekretu nie okłamali nas - w szczególności, jeśli nawet odkryjemy, że nas oszukano, nie umiemy stwierdzić, kto jest sabotażystą. Wymyślono metody dzielenia sekretu odporne na tego typu oszustwa. Przy ich wykorzystaniu możliwe staje się wdrożenie systemu e-votingu, wyborów elektronicznych, w których wyborca rozgłasza swój głos wielu osobom w formie sekretu, zamiast przekazywać do serwera zliczającego głosy. Być może w tym właśnie kierunku będzie zmierzać przyszłość elektronicznych głosowań?

Obrazki płaszczyzn w artykule pochodzą z wikipedii.
Źródła oraz informacja o licencji, na jakiej zostały opublikowane:

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com