Niniejszy artykuł został opublikowany w miesięczniku Delta z lutego 2011.
Zaczniemy od przypomnienia kilku podstawowych własności wielomianów nad liczbami rzeczywistymi. Skupmy się najpierw na funkcji kwadratowej $f(x) = a x^2 + b x + c$. To, co będzie nas interesowało, to ile
Prezentowana wyżej własność funkcji kwadratowej uogólnia się dla wielomianów wyższych stopni. Sformułujemy ściśle odpowiednie twierdzenie.
Twierdzenie 1
Jeśli liczby rzeczywiste $x_1, x_2,\ldots,x_{n+1}$ są parami różne, to przez ustalone punkty $P_1 = (x_1, y_1), P_2=(x_2, y_2),\ldots, P_{n+1} = (x_{n+1},y_{n+1})$ przechodzi dokładnie jeden wielomian nad liczbami rzeczywistymi stopnia co najwyżej $n$.
Powyższy fakt chcemy uogólnić jeszcze bardziej. Otóż twierdzenie jest wciąż prawdziwe, jeśli zmienimy zbiór, nad którym rozpatrywane są wielomiany. Przykładowo - to samo stwierdzenie w świecie liczb zespolonych również jest prawdziwe. Dla osób zaznajomionych z podstawami algebry będzie jasne, jeśli powiemy, że jest ono prawdziwe nad każdym ciałem. Dla naszych rozważań nie będzie potrzeba dokładna definicja tej struktury. Zajmiemy się jednym konkretnym przykładem. Otóż niech $p$ będzie liczbą pierwszą oraz $Z_p$ - zbiorem liczb od naturalnych od $0$ do $p-1$. Wraz z tym zbiorem skojarzymy działania dodawania i mnożenia. Przyjmiemy, że aby dodać dwie liczby z tego zbioru, dodajemy je w sposób tradycyjny, po czym jako wynik bierzemy resztę z dzielenia przez $p$. Dla mnożenia robimy analogicznie. Poniższy przykład ilustruje te definicje dla $p = 13$: $$ 3 + 11 = 1$$ $$ 4 \cdot 6 = 11 $$ $$ 9 \cdot 9 + 10 = 0 $$ Nad taką dziwaczną strukturą będziemy badać tradycyjne wielomiany. Ponownie przyjmijmy $p=13$ oraz $w_1(x)=x^3 + 2 x^2 + 6$, $w_2(x) = x^5 + 3$, $w_3(x) = x + 4$. Mamy wówczas przykładowo: $$ w_1(4) = 11$$ $$ w_2(4) = 0$$ $$ w_3(10) = 1$$ Jak uprzedziliśmy w tym świecie również zachodzi twierdzenie o wielomianach:
Twierdzenie 2
Jeśli elementy ciała $x_1, x_2,\ldots,x_{n+1} \in Z_p$ są parami różne, to przez ustalone punkty $P_1 = (x_1, y_1), P_2=(x_2, y_2),\ldots, P_{n+1} = (x_{n+1},y_{n+1})$ przechodzi dokładnie jeden wielomian nad $Z_p$ stopnia co najwyżej $n$, o ile $n<p$.
A gdzie w tym wszystkim podział sekretu? Jeszcze chwila cierpliwości i wszystko się wyjaśni. Mamy już potrzebny aparat matematyczny, czas więc na ogólne wprowadzenie w problematykę sekretów, spisków i wzajemnej nieufności. ("Kontrola jest najwyższą formą zaufania", Włodzimierz Iljicz Lenin, filozof)
Rozważmy uproszczoną sytuację, gdzie pewna grupa $k$ osób ma jakiś wspólny sekret $M$, który interpretujemy jako jedną liczbę z przedziału $0,\ldots,p-1$, czy raczej - mówiąc językiem algebry - jako element ciała $Z_p$. Chcemy
Poziom bezpieczeństwa 1
(Opisany tutaj poziom bezpieczeństwa da się uzyskać znacznie prościej niż opisano to niżej. Wystarczy pierwszym $k-1$ osobom dać losowe liczby $\ell_i$, a ostatniej: $M - \sum_{i=1}^{k-1} \ell_i$. Przedstawione rozumowanie jest podane, ponieważ poźniej następują jego uogólnienia, których nie da już tak łatwo uzyskać.)
Dowolna podgrupa $k-1$ nic nie wie o $M$. Pełna grupa $k$ osób jest w stanie odtworzyć $M$.
Na chwilę wróćmy do świata wielomianów. Niech $W$ będzie losowym wielomianem nad $Z_p$ stopnia $k-1$, takim że $W(0) = M$. Tylko ten wielomian będzie nam potrzebny, aby rozdzielić sekret. Pierwszej osobie zdradzimy wartość $W(1)$, drugiej -- $W(2)$, $\ldots$ itd. Ostatnia k-ta osoba pozna $W(k)$. Teraz z Twierdzenia 2 dostajemy, że informacje posiadane przez te osoby pozwalają odtworzyć wielomian, a więc i obliczyć $W(0)$, to znaczy poznać sekret $M$. Gdy zabraknie choć jednej osoby, to wielomian nie jest wyznaczony jednoznacznie i wiadomość pozostaje tajna.
Co tu jest jeszcze do dowiedzenia?
Powyższe rozumowanie jest poprawne, zawiera jednak oczywiście pewne uproszczenia i luki w dowodzie. Nie będziemy wszystkiego uzupełniać. Chcemy jednak dokładnie określić, co należałoby ściśle dowieść, aby móc stwierdzić, że opisany schemat jest bezpieczny.
Przede wszystkim nie zdefiniowaliśmy precyzyjnie, co rozumiemy przez sformułowanie, że wiadomość jest tajna. Nie wystarczy powiedzieć, że posiadana wiedza nie wystarcza do jednoznacznego odtworzenia sekretu $M$. Mogłoby się przecież tak zdarzyć, że - w skrajnym przypadku - zostaną tylko dwie możliwości. Pierwsze przybliżenie definicji mogłoby więc iść w tę właśnie stronę. Tzn chcielibyśmy, aby posiadana wiedza nie mogła wykluczyć żadnego kandydata na $M$. Jednak również i taka definicja jest za słaba. Nie wyklucza bowiem przypadku, gdy posiadana wiedza pozwala stwierdzić, że na przykład $M$ wynosi $23821$ z prawdopodobieństwem $0.9$. (a nie $\frac{1}{p}$ jak pewnie byśmy oczekiwali). Najsilniejsza definicja jest właśnie tak sformułowana, tzn w języku probabilistyki: Dana wiadomość jest tajna, jeśli posiadana wiedza nie pozwala na ustalenie innego rozkładu prawdopodobieństw tajnego sekretu niż rozkład jednostajny.
Okazuje się, że dzielenie sekretu za pomocą wielomianu spełnia tę najsilniejszą definicją. Zachęcamy do udowodnienia tego faktu, a przynajmniej dokładnego sformułowania, co tak naprawdę trzeba udowodnić.
Dalsze zastosowania
Wielomiany dają nam jeszcze inne ciekawe możliwości (ponownie $k$ oznacza liczbę osób):
Poziom bezpieczeństwa 2
Dowolna podgrupa $k-4$ nic nie wie o $M$. Każda podgrupa $k-3$ osób jest w stanie odtworzyć $M$.
Powyższe bezpieczeństwo uzysujemy następująco: losujemy wielomian stopnia $k-4$ o wartości $M$ w zerze. Osobom dajemy kolejne wartości $W(1), W(2), \ldots$. Ponownie Twierdzenie 2 dowodzi tezy. Lczba $4$ została tu wybrana przykładowo, można wybrać dowolną inną. Oczywiście, żeby zachować pełną ścisłość należy udowodnić trudniejszy fakt dotyczący prawdopodobieństw rozkładu.
To jednak nie koniec. Jako ostatnią rzecz, proponujemy ćwiczenie. Prosimy czytelnika o pokazanie jak użyć techniki wielomianów do takiego poziomu bezpieczeństwa:
Poziom bezpieczeństwa 3
Nie k oznacza liczbę pięcioosobowych rozłącznych grup osób. Chcemy, aby do poznania sekretu konieczne była większość (a więc co najmniej trzy osoby) z co najmniej $\frac{k}{2}$ grup.
Wskazówka: Początkowo rozwiązujemy problem w starym modelu dla $k$ osób wszystkich i $\frac{k}{2}$ potrzebnych do odzyskania sekretu. Następnie uzyskane punkty traktujemy jako kelejne sekrety, które w obrębie grupy ponownie szyfrujemy za pomocą tej samej techniki, ale - tym razem - dla pięciu osób łącznie i trzech potrzebnych do odszyfrowania.
Brak komentarzy:
Prześlij komentarz