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 < m cieni jest problemem złożonym obliczeniowo.
Metoda wielomianu interpolacyjnego L
agrange'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 = M), możliwa jest przy pomocy wielomianu
interpolacyjnego Lagrange'a :
m m
W(x) =
∑
mis
∏ (
x - xij
) / (
xis - xij
)
mod p
s=1 j=1,m
≠
s
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
x1 = 1
m1 = W(1) mod 13 = 26 (mod 13) = 0
dla
x2 = 2
m2 = W(2) mod 13 = 55 (mod 13) = 3
dla
x3 = 3
m3 = W(3) mod 13 = 98 (mod 13) = 7
dla
x4 = 4
m4 = W(4) mod 13 = 155 (mod 13) = 12
dla
x5 = 5
m5 = W(5) mod 13 = 226 (mod 13) = 5
Odtworzenie sekretu na podstawie znajomości m2 , m3 i m5 :
W(x) = m2
[(
x - x3
) / (
x2 - x3
)] [(
x - x5
) / (
x2 - x5
)] +
+ m3
[(
x - x2
) / (
x3 - x2
)] [(
x - x5
) / (
x3 - x5
)] +
+ m5
[(
x - x2
) / (
x5 - x2
)] [(
x - x3
) / (
x5 - x3
)] (
mod p)
M = W(0) = m2
[
x3
/ (
x2 - x3
)] [
x5
/ (
x2 - x5
)] +
+ m3
[
x2
/ (
x3 - x2
)] [
x5
/ (
x3 - x5
)] +
+ m5
[
x2
/ (
x5 - x2
)] [
x3
/ (
x5 - x3
)] (
mod p)
M = W(0)
= 3
[
3
/
- 1
][
5
/
- 3
] +
7
[
2
/1][
5
/
- 2
] +
5
[
2
/ 3][
3
/ 2] (
mod 13)
= 15 - 35 + 5 (mod 13) = -15 mod 13 = (-15 + 26) mod 13
= 11 mod 13 = 11
Metody progowe w „sytuacji konkurujących stronnictw”
Inną odmianą sytuacji wymagającej zastosowania metod progowych do współdzielenia sekretów jest tzw.
„sytuacja konkurujących stronnictw”. Niech uczestniczy w systemie K grup uczestników, liczących po n
k
członków każda (k = 1, 2, ... , K). Grupy te mają współdzielić pewien sekret M , zaś kryterium odtworzenia
sekretu niech będzie brzmiało następująco :
„Do odtworzenia sekretu niezbędna jest obecność co najmniej m
k
spośród n
k
członków z każdej grupy
k”.
Sposób rozwiązania 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 = M
1 *
M
2 *
...
*
M
K
.
Dla każdego k określa się wielomian stopnia m
k
- 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ć jedynie „swój” czynnik sekretu M
k
, wykorzystując m k swych cieni, lecz
nie jest w stanie odtworzyć całego sekretu. Do jego odtworzenia niezbędna jest odpowiednia ilość cieni z każdej
grupy.