W12_Kodowanie i Kryptografia_Rozdzielanie tajemnicy_1g.pdf

Kryptografia

Rozdzielanie tajemnicy

dr Robert Borowiec

Politechnika Wrocławska

Instytut Telekomunikacji i Akustyki

pokój 908, C-5

tel. 3203083

e-mail: robert.borowiec@ita.pwr.wroc.pl

www: lstwww.ita.pwr.wroc.pl/ ~ RB/

Wykład XII

30-minut

Dzielenie wiadomość pomiędzy grupę

osób

¾ Protokół dzielenia informacji pomiędzy grupę N osób jest

następujący:

¾ Arbiter generuje N -1 losowych kluczy: k 1 , k 2 ,.. k N-1 o tej

samej długości co wiadomość M .

¾ Arbiter oblicza sumę modulo 2 wszystkich kluczy i

dzielonej wiadomości w wyniku czego wyznacza

kryptogram C

¾ k 1 ⊕,k 2 ⊕,..,⊕ k N-1 ⊕M=C

¾ Rozdziela pomiędzy osoby klucze k i oraz szyfrogram C .

¾ Wyznaczenie wiadomość jawnej jest możliwe po

zsumowaniu wszystkich kluczy i kryptogramu

2003-10-13

Kryptografia, Wykład XII

Strona 2/9

Dzielenie wiadomości

¾ Wady i zalety dzielenia tajemnicy

Ö tajemnica nie może być ujawniona bez zgody

wszystkich zaangażowanych w nią osób;

Ö utrata choćby jednego klucza uniemożliwia

odtworzenie informacji jawnej;

Ö gdy w grupie osób jest oszust, to nie można go

wykryć, ani odczytać informacji .

Ö ujawnienie wiadomości zależy od woli

poszczególnych powierników tajemnicy. Każdy z

nich może skutecznie zablokować odzyskanie

informacji jawnej

2003-10-13

Kryptografia, Wykład XII

Strona 3/9

Progowe dzielenie tajemnicy

¾ W systemach z progowym podziałem tajemnicy wystarczy, że tylko n

kluczy z ogólnej liczby m zostanie ujawnionych. Metoda opiera się na

algorytmie wielomianu interpolacyjnego Lagrange’a .

¾ Idea metody:

Jeżeli dana jest funkcja w postaci wielomianu stopnia m- 1

()

⋅

−

⋅

−

..... v

−

to możemy jednoznacznie wyznaczyć współczynniki wielomianu v i ,

jeżeli będziemy znali wartość funkcji f ( x ) w m punktach x I . Wobec

tego będzie możliwe ułożenie i rozwiązanie układu m równań

liniowych.

2003-10-13

Kryptografia, Wykład XII

Strona 4/9

Przykład wielomianu

Przez dwa dowolne punkty na

płaszczyźnie możemy poprowadzić

nieskończenie wiele funkcji

parabolicznych

f ( x )= ax 2 + bx + c

Przy danych trzech punktach możliwe

jest poprowadzenie już tylko jednej

paraboli.

Do jednoznacznego wyznaczenia

współczynników a , b , c w równaniu

paraboli konieczna jest więc znajomość

co najmniej trzech dowolnych punktów

z n leżących na paraboli.

2003-10-13

Kryptografia, Wykład XII

Strona 5/9

Schemat progowy współdzielenia

tajemnicy

¾ W Wiadomość poufna jest dzielona na n części (cienie),

tak aby m dowolnie wybranych cieni umożliwiało

odtworzenie utajnionej treści.

¾ Schemat protokołu:

Ö Wybierana jest liczba pierwsza p, większa od liczby możliwych

cieni oraz reprezentacji liczbowej informacji jawnej;

Ö W celu dzielenia tajemnicy generowany jest wielomian stopnia

m -1, gdzie m oznacza niezbędny próg ilości znanych kluczy ;

Ö Cienie uzyskuje się przez obliczenie wartości wielomianu

k i = f ( x i ), w n różnych punktach x i =1, 2,..., n ;

Ö Ujawnia się wartości cieni oraz k i oraz znane są x i

2003-10-13

Kryptografia, Wykład XII

Strona 6/9

Schemat progowy współdzielenia

tajemnicy

¾ Zalety i wady

Ö tajemnica nie może być ujawniona bez zgody

wymaganej ilości osób;

Ö utrata nawet części kluczy, jeżeli zachowana została

ich wymagana ilość, nie blokuje odtworzenia

informacji jawnej;

Ö ujawnienie wiadomości zależy od woli grupy, a nie

pojedynczej osoby;

Ö w systemie progowym ( m , n ) można wykryć k

oszukujących, jeżeli dysponujemy m + k kluczami,

przy założeniu, że m + k ≤ n.

2003-10-13

Kryptografia, Wykład XII

Strona 7/9

Protokoły pośrednie i kanał

podprogowy

¾ Protokół przekazania informacji podprogowej ukrytej w

podpisie cyfrowym

¾ Alicja wybiera nie budząca podejrzeń jawna wiadomość.

¾ Kluczem tajnym współdzielonym z Robertem podpisuje

wiadomość ukrywając informacje podprogowa w

podpisie.

¾ Alicja wysyła całą informację przez strażnika do Roberta.

¾ Rober po otrz

¾ Przy uzyciu klucza tajnego, współdzielonegoz bobem

¾ Schemat protokołu:

Ö Wybierana jest liczba pierwsza p, większa od liczby możliwych

cieni oraz reprezentacji liczbowej dzielonej tajemnicy;

Ö W celu dzielenia tajemnicy generowany jest wielomian stopnia

m -1.

Ö Cienie uzyskuje się przez obliczenie wartości wielomianu w n

różnych punktach ki=F(k i ).

2003-10-13

Kryptografia, Wykład XII

Strona 8/9

KONIEC

Dziękuję za uwagę

2003-10-13

Kryptografia, Wykład XII

Strona 9/9

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: