Strona główna

Jest to szereg kroków, obejmujących dwie lub więcej stron, podejmowanych w celu realizacji zadania. Jest to inaczej mówiąc sekwencja działań, każde z nich musi być kolejno wykonane i żadne nie może być podjęte


Pobieranie 343.43 Kb.
Strona4/10
Data19.06.2016
Rozmiar343.43 Kb.
1   2   3   4   5   6   7   8   9   10

PODZIAŁ WIADOMOŚCI POUFNYCH



Podział wiadomości (ang. Secret splitting) ma na celu takie ukrycie informacji pomiędzy n użytkownikami, by tylko wszyscy z nich pracując zgodnie i tylko wtedy mogli ją odtworzyć.
Najprostszy przykład podziału wiadomości:

  1. użytkownik T chce dokonać podziału wiadomości M między użytkowników A i B, w tym celu generuje ciąg losowy R o tej samej długości co M,

  2. użytkownik T oblicza sumę modulo 2 ciągów M i R, tworząc P,

  3. wysyła P użytkownikowi A , natomiast R użytkownikowi B (może również dokonać tego na odwrót),

  4. użytkownicy A i B by odtworzyć wiadomość muszą wykonać sumę modulo 2 ciągu P i R.

Inaczej to interpretując jest to system z kluczem jednokrotnym.
Podobny system można wykorzystać do podziału wiadomości pomiędzy n użytkowników. Należy wtedy wygenerować n-1 ciągów losowych o długości równej długości wiadomości. Wtedy P jest równe sumie modulo 2 wiadomości i wszystkich ciągów losowych. Następnie należy rozesłać P i pozostałe n-1 ciągów losowych pomiędzy użytkownikami.

Protokół ten zalicza się do protokołów rozjemczych i użytkownik T panuje nad wszystkim. W protokole tym T musi być uczciwy i cieszyć się zaufaniem.

Jest to również protokół z rodzaju wszyscy albo nikt.


Innym zagadnieniem są podziały progowe, gdzie wiadomość dzielimy pomiędzy n użytkowników i ustalamy, że jeżeli zbierze się k lub więcej dowolnych użytkowników (k  n), to mogą oni odtworzyć wiadomość. Części te nazywa się cieniami. Tego typu schematy nazywa się (k, n)- progowymi.
Schemat z wielomianem interpolacyjnym Lagrange’a

Wykorzystuje się tu równania wielomianowe w ciele skończonym.

Mamy wiadomość M, którą chcemy podzielić, w tym celu wykonujemy czynności:
1. Wybieramy liczbę pierwszą p, która jest większa niż liczba możliwych cieni i większa niż wartość tajemnicy, która ma być współdzielona.

2. Generowany jest dowolny wielomian stopnia k-1 (dla k z n osób uprawnionych do odtworzenia wiadomości) postaci:


ak-1 xk-1 + ak-2xk-2 + . . . + a1x + M (mod p)
gdzie współczynniki ak-1, ak-2, . . . , a1 są mniejsze niż p, są wybrane losowo i utrzymane w tajemnicy. Są zapominane po wydaniu cieni osobom upoważnionym, natomiast p jest ujawniane.

3. Wyznaczamy cienie poprzez wyznaczenie wartości wielomianu w n różnych punktach:


li = f(xi)
4. Wysyłamy to poszczególnych użytkowników systemu xi i odpowiadającą jej wartość li.

    1. Do wyznaczenia M musi się zebrać dowolna liczba k osób posiadających cienie. Mogą one wtedy wyznaczyć ak-1, ak-2, . . . , a1 oraz M.


Schemat wektorowy
Twórca – G. R. Blakley. Wykorzystuje punkty w przestrzeni. Wiadomość jest określona jako punkt w przestrzeni k- wymiarowej. Każdy cień jest równaniem hiperpłaszczyzny (k-1)-wymiarowej zawierającej ten punkt. Przecięcie dowolnych k hiperpłaszczyzn wyznacza dokładnie ten punkt.
Schemat Asmutha-Blooma
Wykorzystuje on liczby pierwsze oraz to, że cienie są klasami przystawania liczb z M. Realizowany jest w następujących krokach:


  1. Wybieramy liczbę pierwszą p większą niż M.

  2. Wybieramy n liczb mniejszych niż p: d1, d2, . . . , dn takich, że n wartości d jest uporządkowanych rosnąco tzn. dii+1 i każda liczba di jest względnie pierwsza z każdą inną di


d1  d2  d3  . . . dk > p  dn-k+2  dn-k+3  . . .  dn
inaczej, że iloczyn k najmniejszych di jest większy niż iloczyn p i k-1 największych di, jeżeli w = d1  d2  d3  . . . dk, to wartość w/p jest większa niż iloczyn dowolnych (k-1)di.

  1. Wybieramy losową wartość r z przedziału (0, (w/p)-1) i wyznaczamy cienie postaci:


li = (M + rp) (mod di)
M + rp jest z przedziału (0, w – 1).

  1. Celem wyznaczenia M musimy zgromadzić k cieni wykorzystując chińskie twierdzenie o resztach. Wyznaczamy mając k części oraz wiedząc, że w1 = di1di2 . . . dik , w1  w


M + rp = crt(w1, di1, di2, . . . , dik, li1, li2, . . . , lik)
Stąd

M = (M + rp) – rp.
Jeżeli znamy tylko k-1 cieni li1, li2, . . . , li(k-1), to wartość (M +rp) może być obliczona modulo w2 = di1di2 . . . di(k-1). Ponieważ
w/w2 > p oraz GCD(w2, p) = 1, zatem wartości x spełniające warunek x1 i x  (M + rp) mod w2 są równomiernie rozłożone we wszystkich klasach przystawania modulo p, a więc nie ma wystarczających informacji do obliczania (M + rp).


Chińskie twierdzenie o resztach (przypomnienie)
Jeżeli d1, d2, . . . , dt są liczbami parami względnie pierwszymi oraz n = d1 d2 . . . dt, to układ równań
x mod di = xi dla i = 1, . . . , t
ma wspólne rozwiązanie x w przedziale (0, n-1).

PRZYKŁAD:

Niech M = 3, k = 2, n = 3 , p = 5, d1 = 7, d2 = 9, d3 = 11. Wówczas

l = d1d2 = 7  9 = 63 > 5  11 = p d3 zgodnie z warunkami. Potrzebujemy losową liczbę r z przedziału (0, (63/5)-1). Przyjmujemy r = 9 i mamy

1   2   3   4   5   6   7   8   9   10


©snauka.pl 2016
wyślij wiadomość