Powiedzieć Wam sekret?

03.02.2010 - Agata Murawska
TrudnośćTrudność

Wszystkie schematy kryptografii asymetrycznej opierają się na jednym podstawowym założeniu - nasz klucz prywatny musi być dla nas dostępny. Co zatem zrobić, gdy był zapisany na zepsutej karcie magnetycznej, zagubionym gwizdku USB czy po prostu na dysku, który uległ awarii?
Jeśli w przeszłości byliśmy wystarczająco zapobiegliwi i opowiedzieliśmy nasz sekret komuś innemu, jesteśmy uratowani.
Zaraz, zaraz! Ale jak to: opowiedzieliśmy nasz sekret?! Przecież klucze prywatne nie służą do tego, żeby rozpowiadać je komukolwiek! Racja - dlatego właśnie nauczymy się robić to w sposób bezpieczny. Powierzymy nasz wielki sekret nie jednej osobie, a wielu - ale tak, że każda będzie znać tylko fragment, z którego nie da się wywnioskować nic konkretnego. Sprytne, prawda?

Oczywiście, metody dzielenia sekretu, które omówimy za chwilę, nadają się równie dobrze do przechowywania kopii zapasowej naszego klucza prywatnego, jak i do zabezpieczania sejfu, czy przekazywania kolejnym pokoleniom rodzinnej tajemnicy.

Podzielimy się po równo..

Jak najprościej podzielić sekret? Powiedzmy, że klucz prywatny Alicji, $ D $, ma zostać podzielony między $ k $ osób tak, żeby żadna z nich nie mogła samodzielnie odtworzyć całej wiadomości. Posłuży się ona w tym celu operacją XOR i losowością.

XOR, czyli inaczej alternatywa wykluczająca (eXclusive OR) to operacja na bitach. Jej działanie przedstawia tabelka:
XOR Istotne jest, że przy operacji XOR nie ma znaczenia rozstawienie nawiasów ani kolejność argumentów. Spróbuj udowodnić tę własność!
Diagram Venna dla operacji XOR wygląda tak:
XOR Często stosowane oznaczenia na tę operację to np $ \oplus $ i $ \dot{\lor} $. XOR można przedstawić jako: $  p\oplus q = (p \land \neg q) \lor (\neg p \land q) $

Cały algorytm podziału sekretu jest stosunkowo prosty:

1. Losujemy $ k-1 $ ciągów bitów $ R_1,\dots R_{k-1} $ o długości takiej, jak długość $ D $
2. Obliczamy $ R=D \oplus R_1 \oplus R_2 \dots \oplus R_{k-1} $ (na każdym bicie wiadomości osobno).
3. Pierwszym $ k-1 $ osobom przekazujemy po jednym ciągu bitów $ R_i $ (każdej osobie inny ciąg).
4. Ostatnia osoba otrzymuje szyfr $ R $.

Jak Alicja może odzyskać klucz mając wszystkie ciągi $ R_i $ oraz wygenerowany przy ich pomocy i z użyciem $ D $ ciąg $ R $?

Skoro $ R = D \oplus (R_1 \oplus R_2 \dots \oplus R_{k-1}) $, to można zauważyć, że $ D = R \oplus (R_1 \oplus R_2 \dots \oplus R_{k-1}) $. Jest nam wszystko jedno, w jakiej kolejności będziemy wykonywać obliczenia (XOR jest przemienny), ważne, że mając wiadomości od wszystkich $ k $ osób - potrafimy odtworzyć $ D $.
Równocześnie, ponieważ $ R_i $ były losowe, znajomość któregokolwiek z nich nic nie daje osobie, której powierzymy jeden z takich ciągów. Podobnie znajomość samego $ R $, powstałego przez losowe zgaszanie i zapalanie bitów w oryginalnym podpisie, nie daje żadnej wiedzy o $ D $.

..a jednak to nie było mądre.

Czy zatem Alicja może spać spokojnie? Nie całkiem.
Żadna ilość osób mniejsza, niż $ k $, nie jest w stanie odtworzyć naszej wiadomości - jeśli wśród tych osób nie ma ostatniej, posiadającej $ R $, ta obserwacja jest oczywista, bo generowaliśmy $ R_i $ bez związku z naszym kluczem. Ale nawet jeśli $ R $ jest znane, a brakuje choćby jednego z $ R_i $ jest dokładnie tak samo źle - każdy bit wiadomości, powstałej przez "xorowanie" posiadanej przez nas części danych, mógł zostać zmieniony tym ostatnim losowym ciągiem (widać to wyraźnie, jeśli popatrzeć uważnie na tabelkę operacji - z wartości $ 0 $ da się zrobić przy pomocy $ \oplus $ zarówno $ 1 $ jak i $ 0 $, podobnie z wartości $ 1 $)
Na pierwszy rzut oka wydaje się, że to dobrze - ale co, jeśli Alicja pokłóci się z jedną z zaufanych osób, przyjaciółka wyjedzie na narty, albo, o zgrozo, ktoś zgubi tajną liczbę, która została mu powierzona? Och, oczywiście my, na miejscu Alicji, mogliśmy po prostu rozsiać informację na jakichś serwerach, zamiast ufać znajomym. Jednak nadal, jeśli jeden z nich uległ awarii, jesteśmy w kropce, zwłaszcza, jeśli ta awaria spowodowała uszkodzenie fragmentu wiadomości. Nie będzie możliwe odzyskanie "sekretu", niezależnie od tego, jak był ważny.

W idealnym świecie nieskończonej pamięci

Powiedzmy, że chcemy podzielić sekret między $ 8 $ osób, z których każde $ 5 $ ma móc go odtworzyć. Można wówczas dla każdego pięcioosobowego podzbioru stworzyć osobny podział sekretu w taki sposób, jak powyżej. Ile jest takich podziałów sekretu? A co, jeśli mamy do obdarowania sekretem więcej, na przykład $ 20 $ osób, a odtworzyć informację może dowolne $ 10 $ z nich?

A może istnieje lepsza metoda? Taka, w której obrażenie się kilku osób (o ile oczywiście nie będzie ich za dużo) nie spowoduje katastrofy? Na nasze (i Alicji) szczęście - istnieje. Jak zwykle w takich przypadkach, ulepszenie efektu końcowego zwiększa też niestety poziom skomplikowania rozwiązania - chyba, że dysponujemy nieograniczoną pamięcią

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com