Powiedzieć Wam sekret?
03.02.2010 - Agata Murawska
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 na części, z których wystarczy do odtworzenia informacji wygląda nieco inaczej:
Skoro ciąg jest rosnący, to iloczyn jest najmniejszym iloczynem elementów ciągu . Oznaczmy go zatem przez .
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..Podobnie iloczyn ostatnich elementów ciągu: jest największym takim iloczynem - oznaczmy go zatem, analogicznie, jako . Warunek z ostatniego podpunku brzmi teraz nieco czytelniej: . Skoro najmniejszy -elementowy pociąg ciągu jest większy, niż , to każdy podciąg -elementowy jest większy. Podobnie z drugiej strony - skoro największy podciąg -elementowy jest mniejszy, niż , to każdy inny pociąg -elementowy także, siłą rzeczy, jest mniejszy od . Przejdźmy do odzyskiwania sekretu, mając do dyspozycji kompletów wartości: Szukane przez nas jest rozwiązaniem układu równań: ... 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 . Na szczęście, jest mniejsze od każdego możliwego iloczynu liczb z ciągu , 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ż 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 (i mniej) liczb jest, z założenia, mniejszy od . Większy sekret - większe wymaganiaWszystko 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. Z tego typu modyfikacją jesteśmy w stanie sobie poradzić. Niech będzie liczbą generałów w sztabie. Podzielimy sekret na części, z których otrzyma prezydent, a pozostałe zostaną rozdzielone po równo między generałów. Za możemy przyjąć dowolną liczbę nie większą od - w zależności od tego, ile władzy chcemy dać sztabowi. Problem pojawia się gdy chcemy na przykład pozwolić podjąć decyzję generałom lub generałowi i 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. |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com