To tylko jedna z 4 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
METODY PROGOWE
Często istnieje potrzeba powierzenia sekretu wielu uczestnikom systemu w taki sposób, by sam sekret nie był
znany żadnej z osób po powierzeniu jej odpowiedniego „fragmentu”, zaś jego odtworzenie wymagało
zgromadzenia w jednym miejscu pewnej minimalnej liczby „fragmentów”. Rozwiązania tego zagadnienia noszą
nazwę metod progowych (threshold methods), i polegają na „podziale” sekretu na n części, zwanych cieniami,
udziałami (shadows, shares) w taki sposób, by na podstawie m ≤ n części móc odtworzyć całość.
Klasycznym przykładem jest wykorzystanie metod progowych do ochrony kluczy kryptograficznych. Względy
bezpieczeństwa przemawiają za tym, by klucze kryptograficzne o znaczeniu strategicznym (np. klucze prywatny
i publiczny administratora systemu) były chronione przed ujawnieniem lub zniszczeniem. Przechowywanie
jednej lub wielu kopii takiego klucza nie jest rozwiązaniem bezpiecznym. Dlatego stosuje się podział klucza k na
wiele "podkluczy" (k1, k2, ... , kn) i rozdziela między n dysponentów.
Metody progowe powinny spełniać następujące warunki :
• znajomość m ≤ n cieni sekretu umożliwia łatwe odtworzenie sekretu;
• odtworzenie sekretu na podstawie znajomości i
(…)
… złożonym obliczeniowo.
Metoda wielomianu interpolacyjnego Lagrange'a(A.Shamir)
Metoda wykorzystuje fakt, że n + 1 punktów jednoznacznie określa wielomian stopnia n.
Określa się wielomian stopnia m - 1 o losowych współczynnikach ai :
W(x) = (a m-1 x m-1 + ... + a1 x + a0) mod p,
gdzie p jest liczbą pierwszą większą niż M i n, zaś a0 = M jest wartością liczbową „ukrywanego” metodą
progową sekretu;
W(0) = M mod p = M
Arbitralnie (np. wykorzystując generator liczb losowych) wybiera się n różnych liczb xi (często rezygnuje się z
„losowości” wybierając kolejne liczby naturalne 1, 2, ..., n).
Cienie wiadomości M określa się z zależności :
mi = W(xi) mod p
Rekonstrukcja wielomianu (i zarazem współczynnika a0
interpolacyjnego Lagrange'a :
m
m
W(x) = ∑ mis ∏
( x - xij) / ( xis - xij)
s=1
j=1,m≠ s
= M), możliwa jest przy pomocy wielomianu
mod p
Przykład :
Niech wartość sekretu M = 11, ilość cieni n = 5, zaś wartość progowa m = 3.
Po określeniu modułu przekształcenia p = 13 i losowo wybranych współczynników :
a2 = 7 i a1 = 8
odpowiedni wielomian Lagrange’a przyjmuje postać :
W(x) = 7 x 2 + 8 x + 11 ( mod 13)
Wyznacza się pięć cieni :
dla
dla
dla
dla
dla
x1 = 1
x2 = 2
x3 = 3
x4 = 4
x5 = 5
m1 = W(1) mod 13 = 26 (mod 13…
… tego problemu zostanie pokazany na przykładzie metody wielomianu Lagrange’a, lecz
podobne podejście można zastosować w przypadku dowolnej innej metody progowej.
Dokonuje się rozkładu sekretu M na K czynników (dowolnych) :
M = M1 * M2 * ...* MK .
Dla każdego k określa się wielomian stopnia mk - 1 o losowych współczynnikach a i, k :
W k (x) = (a mk-1, k x mk-1 + ... + a1, k x + a0, k ) mod p ,
gdzie p jest liczbą pierwszą, wspólną dla wszystkich grup i większą od M i liczby wszystkich uczestników
systemu (z wszystkich „konkurujących stronnictw”), zaś a0,k = Mk jest jednym z czynników „ukrywanego”
metodą progową sekretu.
Ostateczny wielomian Lagrange’a :
W (x) = W 1 (x) * W 2 (x) * ... * W K (x)
Cienie wiadomości M k określa się z zależności :
mi,k = W k (xi) mod p
Każda grupa jest w stanie odtworzyć…
… mod p = M
Arbitralnie (np. wykorzystując generator liczb losowych) wybiera się n różnych liczb xi (często rezygnuje się z
„losowości” wybierając kolejne liczby naturalne 1, 2, ..., n).
Cienie wiadomości M określa się z zależności :
mi = W(xi) mod p
Rekonstrukcja wielomianu (i zarazem współczynnika a0
interpolacyjnego Lagrange'a :
m
m
W(x) = ∑ mis ∏
( x - xij) / ( xis - xij)
s=1
j=1,m≠ s
= M), możliwa…
... zobacz całą notatkę
Komentarze użytkowników (0)