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 d" 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 d" 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 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 = 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 spośród n członków z każdej grupy
k k
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 M ... M .
1 * 2 * * K
Dla każdego k określa się wielomian stopnia m - 1 o losowych współczynnikach a i, k :
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 , wykorzystując m k swych cieni, lecz
k
nie jest w stanie odtworzyć całego sekretu. Do jego odtworzenia niezbędna jest odpowiednia ilość cieni z każdej
grupy.