Rozważmy scenariusz, w którym trzeba zabezpieczyć skarbiec bankowy. Uważany jest za całkowicie nie do zdobycia bez klucza, który dostajesz już pierwszego dnia pracy. Twoim celem jest bezpieczne przechowywanie klucza.
Załóżmy, że decydujesz się mieć klucz zawsze przy sobie, zapewniając dostęp do magazynu w razie potrzeby. Szybko jednak zorientujesz się, że takie rozwiązanie nie sprawdza się w praktyce, ponieważ przy każdym otwarciu magazynu wymagana jest Twoja fizyczna obecność. A co z obiecanymi ci wakacjami? Poza tym pytanie jest jeszcze bardziej przerażające: co by było, gdybyś zgubił swój jedyny klucz?
Z myślą o urlopie decydujesz się na wykonanie kopii klucza i powierzeniu go innemu pracownikowi. Jednak rozumiesz, że to też nie jest idealne. Podwajając liczbę kluczy, podwajasz także ryzyko kradzieży kluczy.
W desperacji niszczysz duplikat i decydujesz się podzielić oryginalny klucz na pół. Można by pomyśleć, że dwie zaufane osoby posiadające fragmenty klucza musiałyby być fizycznie obecne, aby odebrać klucz i otworzyć skarbiec. Oznacza to, że złodziej musi ukraść dwie sztuki, co jest dwa razy trudniejsze niż kradzież jednego klucza. Jednak szybko zdajesz sobie sprawę, że ten schemat nie jest dużo lepszy niż tylko jeden klucz, ponieważ jeśli ktoś zgubi połowę klucza, nie będzie można odzyskać całego klucza.
Problem można rozwiązać za pomocą szeregu dodatkowych kluczy i zamków, ale takie podejście będzie szybko wymagało много klucze i zamki. Decydujesz, że idealnym rozwiązaniem byłoby dzielenie klucza, aby bezpieczeństwo nie było całkowicie zależne od jednej osoby. Dochodzisz również do wniosku, że musi istnieć jakiś próg liczby fragmentów, tak aby w przypadku zgubienia jednego fragmentu (lub jeśli ktoś pojedzie na wakacje) cały klucz pozostał funkcjonalny.
Jak podzielić się tajemnicą
O tego rodzaju schemacie zarządzania kluczami myślał Adi Shamir w 1979 roku, kiedy publikował swoją pracę . W artykule pokrótce wyjaśniono tzw 
schemat progowy umożliwiający efektywne dzielenie tajnej wartości (takiej jak klucz kryptograficzny) na Części. Wtedy, kiedy i tylko wtedy, przynajmniej z części są zmontowane, możesz łatwo przywrócić sekret .
Z punktu widzenia bezpieczeństwa ważną właściwością tego schematu jest to, że atakujący nie powinien wiedzieć absolutnie niczego, jeśli nie posiada przynajmniej Części. Nawet obecność części nie powinny dostarczać żadnych informacji. Nazywamy tę właściwość bezpieczeństwo semantyczne.
Interpolacja wielomianowa
Schemat progu Shamira zbudowany wokół koncepcji interpolacja wielomianowa. Jeśli nie znasz tej koncepcji, jest ona całkiem prosta. Tak naprawdę, jeśli kiedykolwiek narysowałeś punkty na wykresie, a następnie połączyłeś je liniami lub krzywymi, już tego użyłeś!
Przez dwa punkty można narysować nieograniczoną liczbę wielomianów stopnia 2. Aby wybrać z nich ten jedyny potrzebny jest trzeci punkt. Ilustracja:
Rozważmy wielomian o stopniu pierwszym, . Jeśli chcesz przedstawić tę funkcję na wykresie, ile punktów potrzebujesz? Wiemy, że jest to funkcja liniowa tworząca linię i dlatego potrzebuje co najmniej dwóch punktów. Następnie rozważmy funkcję wielomianową stopnia drugiego, . Jest to funkcja kwadratowa, więc do wykreślenia wykresu potrzebne są co najmniej trzy punkty. A co powiesz na wielomian o stopniu trzecim? Co najmniej cztery punkty. I tak dalej i tak dalej.
Naprawdę fajną rzeczą w tej właściwości jest to, że biorąc pod uwagę stopień funkcji wielomianu i co najmniej punktów, możemy wyprowadzić dodatkowe punkty dla tej funkcji wielomianu. Nazywamy to ekstrapolacją tych dodatkowych punktów interpolacja wielomianowa.
Zmyślanie tajemnicy
Być może już zdałeś sobie sprawę, że w tym miejscu wchodzi w grę sprytny plan Shamira. Powiedzmy nasz sekret - jest . Możemy zawrócić do punktu na wykresie i wymyśl funkcję wielomianową ze stopniem , co spełnia ten punkt. Przypomnijmy Ci to będzie naszym progiem wymaganych fragmentów, więc jeśli ustawimy próg na trzy fragmenty, musimy wybrać funkcję wielomianową o stopniu drugim.
Nasz wielomian będzie miał postać Gdzie и — losowo wybrane dodatnie liczby całkowite. Po prostu konstruujemy wielomian ze stopniem , gdzie wolny współczynnik - To jest nasz sekret i dla każdego z kolejnych warunkach istnieje losowo wybrany współczynnik dodatni. Jeśli wrócimy do pierwotnego przykładu i założymy to , wtedy otrzymujemy funkcję .
W tym momencie możemy wygenerować fragmenty poprzez połączenie unikalne liczby całkowite w Gdzie (bo to nasza tajemnica). W tym przykładzie chcemy rozdzielić cztery fragmenty z progiem trzech, więc losowo generujemy punkty i wyślij po jednym punkcie każdej z czterech zaufanych osób, opiekunów klucza. Informujemy o tym także ludzi , ponieważ jest to informacja publiczna i niezbędna do odzyskania danych .
Odzyskanie tajemnicy
Omówiliśmy już koncepcję interpolacji wielomianowej i jej znaczenie dla schematu progowego Shamira . Kiedy którekolwiek z trzech z czterech powierników chce przywrócić , wystarczy interpolować z własnymi, unikalnymi punktami. Aby to zrobić, mogą określić swoje punkty i oblicz wielomian interpolacji Lagrange'a, korzystając z następującego wzoru. Jeśli programowanie jest dla ciebie jaśniejsze niż matematyka, to pi jest w zasadzie operatorem for, co mnoży wszystkie wyniki, a sigma jest for, co sumuje wszystko.
w możemy rozwiązać to w ten sposób i zwrócić naszą oryginalną funkcję wielomianową:
Ponieważ wiemy, że , powrót do zdrowia zrobione po prostu:
Używanie niebezpiecznej arytmetyki liczb całkowitych
Chociaż z powodzeniem zastosowaliśmy podstawową ideę Shamira pozostaje nam problem, który do tej pory ignorowaliśmy. Nasza funkcja wielomianowa wykorzystuje niebezpieczną arytmetykę liczb całkowitych. Należy pamiętać, że dla każdego dodatkowego punktu, jaki atakujący uzyska na wykresie naszej funkcji, możliwości zdobycia innych punktów są mniejsze. Można to zobaczyć na własne oczy, wykreślając rosnącą liczbę punktów dla funkcji wielomianowej za pomocą arytmetyki liczb całkowitych. Przynosi to efekt przeciwny do zamierzonego w stosunku do naszego wyznaczonego celu bezpieczeństwa, ponieważ osoba atakująca nie powinna wiedzieć absolutnie nic, dopóki przynajmniej tego nie dowie się paprochy.
Aby zademonstrować, jak słaby jest obwód arytmetyki liczb całkowitych, rozważmy scenariusz, w którym atakujący uzyskał dwa punkty i zna informację publiczną, że . Z tych informacji może wywnioskować równy dwa i wstaw znane wartości do wzoru и .
Osoba atakująca może wtedy znaleźć , liczenie :
Ponieważ zdefiniowaliśmy jako losowo wybrane dodatnie liczby całkowite, istnieje ograniczona liczba możliwych . Korzystając z tych informacji, osoba atakująca może wywnioskować , ponieważ wystarczy wszystko, co jest większe niż 5 negatywny. Okazuje się to prawdą, ponieważ ustaliliśmy
Osoba atakująca może następnie obliczyć możliwe wartości wymiana в :
Z ograniczonymi opcjami staje się jasne, jak łatwo jest wybrać i sprawdzić wartości . Tutaj jest tylko pięć opcji.
Rozwiązanie problemu z niebezpieczną arytmetyką liczb całkowitych
Aby wyeliminować tę lukę, Shamir sugeruje użycie arytmetyki modułowej, zastępując na Gdzie и — zbiór wszystkich liczb pierwszych.
Przypomnijmy sobie szybko, jak działa arytmetyka modułowa. Zegar ze wskazówkami to znana koncepcja. To znaczy używa zegarka . Gdy tylko wskazówka godzinowa minie dwunastą, wraca do pierwszej. Ciekawą właściwością tego systemu jest to, że patrząc na zegarek, nie jesteśmy w stanie wywnioskować, ile obrotów wykonała wskazówka godzinowa. Jeśli jednak wiemy, że wskazówka godzinowa minęła 12 cztery razy, możemy całkowicie określić liczbę godzin, które minęły, za pomocą prostego wzoru Gdzie jest naszym dzielnikiem (tutaj ), to współczynnik (ile razy dzielnik przechodzi do pierwotnej liczby bez reszty, tutaj ) i to reszta, która zwykle zwraca wywołanie operatora modulo (tutaj ). Znajomość wszystkich tych wartości pozwala nam rozwiązać równanie , ale jeśli przegapimy współczynnik, nigdy nie będziemy w stanie przywrócić pierwotnej wartości.
Możemy zademonstrować, jak poprawia to bezpieczeństwo naszego schematu, stosując schemat do naszego poprzedniego przykładu i używając . Nasza nowa funkcja wielomianowa i nowe punkty . Teraz osoby odpowiedzialne za klucze mogą ponownie użyć interpolacji wielomianowej do zrekonstruowania naszej funkcji, tylko tym razem operacjom dodawania i mnożenia musi towarzyszyć redukcja modulo (na przykład ).
Korzystając z tego nowego przykładu, załóżmy, że atakujący nauczył się dwóch z tych nowych punktów: i informacji publicznej . Tym razem atakujący, w oparciu o wszystkie posiadane informacje, wyprowadza następujące funkcje: gdzie jest zbiorem wszystkich dodatnich liczb całkowitych, oraz reprezentuje współczynnik modułu .
Teraz nasz napastnik znajduje ponownie , obliczanie :
Potem próbuje ponownie wymiana в :
Tym razem ma poważny problem. Brakujące wartości formuły , и . Ponieważ istnieje nieskończona liczba kombinacji tych zmiennych, nie może on uzyskać żadnych dodatkowych informacji.
Względy bezpieczeństwa
Sugeruje to plan tajnego udostępniania Shamira bezpieczeństwo z punktu widzenia teorii informacji. Oznacza to, że matematyka jest odporna nawet na atakującego z nieograniczoną mocą obliczeniową. Jednak obwód nadal zawiera kilka znanych problemów.
Na przykład schemat Shamira nie tworzy fragmenty do sprawdzeniaoznacza to, że ludzie mogą swobodnie prezentować fałszywe fragmenty i utrudniać odzyskanie prawidłowego sekretu. Wrogi opiekun fragmentów posiadający wystarczające informacje może nawet wyprodukować kolejny fragment poprzez zmianę według własnego uznania. Ten problem rozwiązano za pomocą weryfikowalne schematy udostępniania tajnych informacji, takie jak schemat Feldmana.
Innym problemem jest to, że długość dowolnego fragmentu jest równa długości odpowiadającego mu sekretu, więc długość sekretu jest łatwa do ustalenia. Problem ten można rozwiązać banalnie wyściółka tajne z dowolnymi liczbami do ustalonej długości.
Na koniec należy zauważyć, że nasze obawy dotyczące bezpieczeństwa mogą wykraczać poza sam projekt. W przypadku rzeczywistych aplikacji kryptograficznych często istnieje ryzyko ataków typu side-channel, podczas których osoba atakująca próbuje wydobyć przydatne informacje z czasu wykonywania aplikacji, buforowania, awarii itp. Jeśli stanowi to problem, podczas opracowywania należy dokładnie rozważyć użycie środków ochronnych, takich jak funkcje i wyszukiwania w czasie stałym, zapobiegające zapisywaniu pamięci na dysku, a także szereg innych kwestii, które wykraczają poza zakres tego artykułu.
Демо
Na Istnieje interaktywna demonstracja planu udostępniania sekretów Shamira. Pokaz oparty na bibliotece , który sam w sobie jest portem JavaScript tego popularnego programu . Należy pamiętać, że obliczanie dużych wartości , и może chwilę potrwać.
Źródło: www.habr.com