Przeskocz do treści

Delta mi!

Loading

Mała Delta

Tajemnica

Wojciech Czerwiński

o artykule ...

  • Publikacja w Delcie: listopad 2016
  • Publikacja elektroniczna: 1 listopada 2016
  • Autor: Wojciech Czerwiński
    Afiliacja: adiunkt, Instytut Informatyki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (417 KB)

Mam pewien sekret, może lepiej nawet powiedzieć: tajemnicę. Nie mogę sobie pozwolić, żeby ktoś ją poznał. Sprawa jest poważna, ujawnię ją dopiero za pewien czas, gdy tylko Świat będzie na to gotowy. Może to rozwiązanie pewnego ważnego problemu matematycznego, zresztą, nie będę dzwonił kluczami do tajemnic. W każdym razie nie mogę sobie również pozwolić, żeby na wypadek mojej śmierci ta informacja przepadła bezpowrotnie. Co robić?

obrazek

Na szczęście, opracowałem pewien plan. Podzielę się tą informacją ze służbami specjalnymi. Wybrałem trzy: ABW, CIA i Mosad. Czy mogę jednak w pełni ufać służbom specjalnym? Chyba nie. Dlatego chcę dostarczyć im takie informacje, żeby żadna pojedyncza instytucja nie mogła samodzielnie odkryć nawet kawałka mojej tajemnicy. Co więcej, chcę to zrobić tak, by nawet dwie z nich, jeśli się potajemnie zmówią, nie zdołały odtworzyć ani litery z mojego sekretu. System musi być taki, że dopiero gdy wszystkie trzy służby udostępnią sobie dostarczone przeze mnie informacje, będą w stanie odtworzyć cokolwiek z tajemnicy. Co więcej, chcę, żeby wówczas odtworzyły już wszystko, bo mam nadzieję, że stanie się to jedynie na wypadek mojej śmierci.

Pozostaje pytanie: jak to zrobić? A może nawet właściwsze w tej sytuacji: czy to się w ogóle da zrobić? Okazuje się, że szczęśliwie się da. Zachęcam Ambitnych Czytelników do próby samodzielnego stworzenia takiego systemu.

A robi się to tak. Przedstawiam mój sekret w postaci ciągu zero-jedynkowego. Bitem będziemy nazywać dowolną cyfrę takiego ciągu, czyli zero lub jedynkę. Nietrudno zauważyć, że mogę znaleźć takie przedstawienie bez problemu, na przykład każdą literę alfabetu przedstawiam w postaci ciągu sześciu bitów, da się to zrobić, bo liter alfabetu jest nie więcej niż 26 = 64. Teraz mogę się więc skupić na tym, jak podzielić pewien ciąg bitów na trzy kawałki. Nie mogę po prostu przekazać pierwszej jednej trzeciej ABW, drugiej CIA, a trzeciej Mosadowi, bo w sposób oczywisty bez wysiłku każdy z nich znałby sporą część tajemnicy.

Żeby wyjaśnić system, konieczne jest zdefiniowanie funkcji xor, która jako argumenty bierze pewną liczbę bitów, a zwraca jeden. Definiujemy ją jako

xor(b1,...,bk) = (b1 +⋅⋅⋅+ bk) mod2,

czyli resztę z dzielenia sumy bitów przez dwa. Możemy rozszerzyć funkcję |xor w taki sposób, że jako argumenty bierze ona pewną liczbę ciągów bitowych jednakowej długości, powiedzmy dla ustalenia uwagi, długości |m. Wtedy

xor(w1,...,wk) = xor(w1[1],...,wk[1]) ...xor(w1[m],...,wk[m]),

gdzie przez |w[i] oznaczamy i -tą literę słowa w. Czyli, innymi słowy, nowy |xor po prostu xoruje argumenty litera po literze. Przykładowo

xor(11001,01000,10111) = xor(1,0,1)xor(1,1,0)xor(0, 0,1)xor(0, 0,1)xor(1,0,1) = 00110.

A teraz system - jest banalnie prosty! Powiedzmy, że moja tajemnica przedstawiona w postaci ciągu bitów ma długość m. Jej wartość oznaczmy przez | t. Najpierw losuję dwa losowe ciągi bitów | w1 i | w2 długości | m, to będą te przeznaczone dla ABW i CIA. Teraz definiuję trzeci ciąg, dla Mosadu, |w3 = xor(w1,w2,t). Tylko dlaczego to działa?

Zauważmy najpierw, że |t = xor(w1,w2,w3). Żeby się przekonać, że to prawda, spójrzmy na i -ty bit. Wiemy, że w3[i] = xor(w1[i],w2[i],t[i]). A więc suma w1[i],w2[i],t[i] oraz w3[i] jest parzysta. Z tego zaś wynika, że | xor(w1[i],w2[i],w3[i]) = t[i]. Gdy powtórzymy rozumowanie dla każdego |i między 1 a m, otrzymamy, że faktycznie t = xor(w1,w2,w3). Czyli ABW, CIA i Mosad współpracując, mogą odtworzyć moją tajemnicę.

Trzeba jednak jeszcze sprawdzić, czy istotnie żadne dwie służby bez trzeciej łącząc swoje siły, nie będą w stanie odkryć żadnej informacji. Jasne jest, że ABW i CIA mają ciągi losowe, więc nie zrobią z nimi niczego sensownego bez Mosadu. Pozostają pozostałe pary - skupmy się na parze CIA i Mosad, bo sytuacja jest identyczna dla pary ABW i Mosad. Przyjrzyjmy się i -temu bitowi. Wyobraźmy sobie, że CIA i Mosad patrzą na swoje bity i widzą w2[i] = 0,w3[i] = 0. To im jednak nie daje żadnej wiedzy o | t[i], bo może być tak, że | w1[i] = 0 = t[i] oraz tak, że |w1[i] = 1 = t[i] - każda z tych dwóch opcji jest równie prawdopodobna. Podobnie dla każdej kombinacji w2[i] i |w3[i] oraz dla każdego innego indeksu i. Polecamy Czytelnikom Ambitnym doprecyzowanie tego argumentu.

Nietrudno zauważyć, że opisany system da się uogólnić na dowolne |N służb. Jeszcze ciekawszym pytaniem jest, co zrobić, gdy chcę, by dowolne |K z |N służb, spotykając się, odtworzyło całą tajemnicę, ale już żadne |K− 1 służb nie mogło odkryć niczego. Wtedy potrzebne są bardziej zaawansowane techniki, pisaliśmy o tym w Delcie 2/2011.