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.