W12 Kodowanie i Kryptografia Rozdzielanie tajemnicy 1g, PWr, IV Semestr, Kryptografia i Kodowanie
[ Pobierz całość w formacie 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 x © Robert Borowiec * 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 x © Robert Borowiec * 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 Y f () x = v ⋅ x m − + v ⋅ x m − 2 + ..... v + m − 1 m − 2 0 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. © Robert Borowiec * 2003-10-13 Kryptografia, Wykład XII Strona 4/9 1 Przykład wielomianu Y Przez dwa dowolne punkty na płaszczyźnie możemy poprowadzić nieskończenie wiele funkcji parabolicznych f ( x )= ax 2 + bx + c X 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. © Robert Borowiec * 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 x © Robert Borowiec * 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. x © Robert Borowiec * 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 ). x © Robert Borowiec * 2003-10-13 Kryptografia, Wykład XII Strona 8/9 KONIEC Dziękuję za uwagę © Robert Borowiec 2003-10-13 Kryptografia, Wykład XII Strona 9/9 [ Pobierz całość w formacie PDF ] |