Powiedzieć Wam sekret?

03.02.2010 - Agata Murawska
TrudnośćTrudność

Znowu liczby pierwsze?!

No cóż, wygląda na to, że po raz kolejny będziemy korzystać z liczb pierwszych. Tak już jest w kryptografii i jej szeroko pojętych okolicach..
Wyobraźmy sobie, że Alicja jest nieco bardziej zapobiegliwa, niż wcześniej. Chce podzielić swój sekret między $ n $ znajomych, ale tak, żeby dowolnych $ k $ z nich mogło dostarczyć jej dane do odtworzenia informacji.
To oczywiście bardzo wygodne rozwiązanie - jeśli na przykład mamy znajomych z wakacji i ze szkoły, przy czym jedni nie znają drugich, to da się podzielić sekret tak, żeby nawet ogólnoszkolna krucjata nie zagroziła bezpieczeństwu naszej słodkiej tajemnicy. Jak? Na przykład w taki sposób: XOR
Nawet jeśli cała szkoła sprzysięgnie się przeciw nam, szkolni znajomi mają w sumie tylko $ 5 $ fragmentów, a do odtworzenia sekretu potrzeba ich $ 6 $. Jesteśmy bezpieczni!

Jak zatem osiągnąć taki efekt? Wszystko po kolei..

Dzielimy sekret

Na początek pomyślmy sobie o prostej. Żeby wyznaczyć prostą, wystarczy znać dwa jej punkty na płaszczyźnie. A co, jeśli chcemy wyznaczyć parabolę? Ile punktów musimy znać, żeby wiedzieć, jak przebiega?
W oparciu o ten pomysł stwórzmy lepszy algorytm podziału:
Podział sekretu jest nadal stosunkowo prosty - dużo prostszy, niż przekonanie się, o jego bezpieczeństwie. Przypomnijmy tylko, że naszym celem jest podzielić sekret $ D $ między $ n $ osób, z których każde $ k $ ma być w stanie odtworzyć $ D $.
1. Wybieramy dużą liczbę pierwszą $ p $ taką, że $ p>n $ i $ p>D $.
2. Wybieramy losowo $ k-1 $ liczb: $ w_1, \dots w_{k-1} $, mniejszych od $ p $.
3. Definiujemy funkcję $ \mathrm{w}(x) = D + \sum_{i=1}^{k-1} {w_i x^i } $.
4. Obliczamy wartości $ \mathrm{w}(1), \mathrm{w}(2), \dots, \mathrm{w}(n) \mod p $.
5. $ i $-tej osobie przekazujemy wartość $ w(i) $.

Uwaga na wielomiany!
Z naszych wcześniejszych rozważań o prostych i parabolach daje się wysnuć wniosek: wielomian stopnia $ m $ jest jednoznacznie wyznaczony przez swoje wartości w dowolnych $ m+1 $ punktach. Przy dzieleniu sekretu tworzymy wielomian $ \mathrm{w}(x) $ stopnia $ k-1 $, zatem wartości w dowolnych $ k $ punktach - zgodnie z powyższym twierdzeniem - wyznaczają go jednoznacznie.
plaszczyzny
Jak widać, wielomian stopnia $ 2 $ nie może zostać wyznaczony przy pomocy $ 2 $ punktów.
Podobnie, wielomian pierwszego stopnia (czyli prosta postaci $ ax+b $) jest wyznaczany przez $ 2 $ punkty, zaś dla dowolnego punktu istnieje nieskończenie wiele prostych, które przez niego przechodzą.
Autorem przedstawionego algorytmu jest Adi Schamir, jeden z pomysłodawców RSA (istnieje uzasadnione podejrzenie, że odpowiada on za literkę 'S'). Równocześnie dość podobny pomysł przedstawił George Blakley, który proponował wyznaczanie sekretu jako punktu przecięcia $ k $ płaszczyzn w przestrzeni $ k-1 $ wymiarowej, gdzie każdy powiernik zna jedną płaszczyznę. Poniżej przykład dla przestrzeni trójwymiarowych:
plaszczyznyplaszczyznyplaszczyzny

Liczy się tylko zero

Wiemy już, jak dzielić sekret przy pomocy wielomianów. Pytanie brzmi teraz: jak odzyskać $ D $, mając danych $ k $ punktów $ (x_i,\mathrm{w}(x_i)) $?
Wystarczy odtworzyć wielomian $ \mathrm{w}(x) $ i policzyć jego wartość dla $ x=0 $. Odtwarzanie wielomianu odbywa się przy pomocy następującego wzoru (nazywanego wzorem interpolacyjnym Lagrange'a):

$$\mathrm{u}(x) = \sum_{i=1}^k (w(x_i) * \prod_{1\leq j\leq k, j\neq i} \frac{x-x_j}{x_i-x_j})$$
Wygląda strasznie, prawda? Może lepiej obejrzeć przykład.
Weźmy wielomian $ \mathrm{w}(x) = 2x^2+4 $ i policzmy jego wartość w punktach $ 1 $, $ 2 $ i $ 4 $.
Otrzymujemy $ \mathrm{w}(1)=6 $, $ \mathrm{w}(2)=12 $ i $ \mathrm{w}(4) = 36 $. Wstawiając to do wzoru Lagrange'a dostaniemy:
$$\mathrm{w}(x) = 6*(\frac{x-2}{-1} \frac{x-4}{-3}) + 12*(\frac{x-1}{1} \frac{x-4}{-2}) + 36*(\frac{x-1}{3} \frac{x-2}{2}) = $$
$$2(x-2)(x-4) - 6(x-1)(x-4) + 6(x-1)(x-2) = $$
$$2(x^2-6x+8) -6(x^2-5x+4)+6(x^2-3x+2)= $$
$$(2x^2-6x^2+6x^2) + (-12x+30x-18x) + (16-24+12) = 2x^2 +4$$
Zgadza się!













W zasadzie można od razu zmienić go tak, żeby obliczyć $ w(0) $:
$$D = \mathrm{u}(0) =  \sum_{i=1}^k (w(x_i) * \prod_{1\leq j\leq k, j\neq i} \frac{x_j}{x_j-x_i})$$
Miłośnikom matematyki polecam formalny dowód poprawności. Upewnimy się w nim, że wielomian, który obliczamy, jest równy początkowemu w każdym z $ k $ punktów i jest stopnia $ k-1 $

Nie dałoby się krócej?
No właśnie. Żeby zapamiętać sekret długości $ l $, rozsyłamy do większej liczby osób informacje tej samej długości. Wydaje się z pozoru, że to bardzo duży narzut - ale tylko do momentu, w którym zdamy sobie sprawę, że $ k-1 $ osób ma nie wiedzieć o sekrecie absolutnie nic, zaś $ k $ ma znać go w całości. Nie ma wyjścia, każdy fragment musi nieść ze sobą informacje o wszystkich bitach.
Można zapytać na koniec - ale po co była ta liczba pierwsza?
W informatyce chcemy ograniczać rozmiar informacji. Wielomiany obliczane modulo liczba pierwsza $ p $ zachowują się równie dobrze jak te o wartościach rzeczywistych, ale dzięki temu, że liczymy $ \mod p $, wszystkie wartości przekazywane naszym powiernikom są ograniczonej wielkości - czyli są mniej więcej rozmiarów samego sekretu.

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com