Rozważmy sytuację, w której konieczne jest zapewnienie bezpieczeństwa skarbca bankowego. Uważa się, że jest ono absolutnie nie do sforsowania bez klucza, który dostaje się pierwszego dnia pracy. Twoim celem jest zachowanie bezpieczeństwa klucza.

Załóżmy, że zdecydujesz się nosić klucz zawsze przy sobie, udzielając dostępu do sejfu tylko wtedy, gdy zajdzie taka potrzeba. Jednak szybko zorientujesz się, że to rozwiązanie nie sprawdza się w praktyce, ponieważ Twoja fizyczna obecność jest wymagana za każdym razem, gdy magazyn jest otwierany. A co z wakacjami, które ci obiecano? Co więcej, jeszcze bardziej przerażające jest: co się stanie, jeśli zgubisz swój jedyny klucz?

Myśląc o wakacjach, decydujesz się wykonać kopię klucza i powierzyć ją innemu pracownikowi. Jednak rozumiesz, że to również nie jest rozwiązanie idealne. Podwajając liczbę kluczy, podwajasz także ryzyko ich kradzieży.

W desperacji niszczysz duplikat i decydujesz się podzielić oryginalny klucz na pół. Teraz uważasz, że aby złożyć klucz i otworzyć skarbiec, muszą być obecne dwie zaufane osoby posiadające fragmenty klucza. Oznacza to, że złodziej musiałby ukraść dwa fragmenty, co jest dwa razy trudniejsze niż kradzież jednego klucza. Jednak szybko zdajesz sobie sprawę, że ten schemat nie jest lepszy od jednego klucza, ponieważ jeśli ktoś zgubi połowę klucza, odzyskanie całego klucza będzie niemożliwe.

Problem można rozwiązać za pomocą serii dodatkowych kluczy i zamków, ale takie podejście szybko będzie wymagało много klucze i zamki. Postanawiasz, że najlepszym rozwiązaniem będzie rozdzielenie klucza, aby bezpieczeństwo nie zależało wyłącznie od jednej osoby. Wnioskujesz również, że musi istnieć jakiś próg liczby fragmentów, tak aby w przypadku utraty jednego fragmentu (lub wyjazdu osoby na wakacje) cały klucz pozostał funkcjonalny.

Jak podzielić się sekretem

Tego typu schemat zarządzania kluczami wymyślił Adi Shamir w 1979 r., kiedy opublikował swoją pracę „Jak dzielić się sekretem”. W artykule krótko wyjaśniono tzw. schemat progowy umożliwiający efektywne dzielenie wartości tajnej (np. klucza kryptograficznego) na strony. Wtedy, kiedy i tylko wtedy, gdy przynajmniej z części są zbierane, łatwo jest przywrócić sekret .

Z punktu widzenia bezpieczeństwa ważną cechą tego schematu jest to, że atakujący nie powinien dowiedzieć się absolutnie niczego, jeśli nie ma przynajmniej strony. Nawet obecność części nie powinny dostarczać żadnych informacji. Nazywamy tę nieruchomość bezpieczeństwo semantyczne.

Interpolacja wielomianowa

Schemat progowy Shamira zbudowany wokół koncepcji interpolacja wielomianowa. Jeśli nie znasz tej koncepcji, jest ona tak naprawdę dość prosta. W rzeczywistości, jeśli kiedykolwiek rysowałeś punkty na wykresie i łączyłeś je liniami lub krzywymi, to już z pewnością z niej korzystałeś!

Przez dwa punkty można przeprowadzić nieograniczoną liczbę wielomianów stopnia 2. Aby wybrać ten jedyny potrzebny jest trzeci punkt. Ilustracja: Wikipedia

Rozważmy wielomian pierwszego stopnia, . Ile punktów jest potrzebnych, aby przedstawić tę funkcję na wykresie? Wiemy, że jest to funkcja liniowa, która tworzy linię prostą i dlatego potrzebne są co najmniej dwa punkty. Następnie rozważymy funkcję wielomianową stopnia drugiego, . Jest to funkcja kwadratowa, więc do narysowania wykresu potrzebne są co najmniej trzy punkty. Co powiesz na wielomian trzeciego stopnia? Co najmniej cztery punkty. I tak dalej, i tak dalej.

Naprawdę fajne w tej własności jest to, że biorąc pod uwagę stopień funkcji wielomianowej i co najmniej punktów, możemy wyznaczyć dodatkowe punkty dla tej funkcji wielomianowej. Ekstrapolację tych dodatkowych punktów nazywamy interpolacja wielomianowa.

Wymyślanie sekretu

Pewnie już zauważyłeś, że sprytny plan Szamira wchodzi tu w grę. Załóżmy, że nasz sekret - jest . Możemy się przekształcić do punktu na wykresie i wymyśl funkcję wielomianową o stopniu , co spełnia ten punkt. Przypomnijmy, że będzie naszym progiem wymaganych fragmentów, więc jeśli ustawimy próg na trzy fragmenty, musimy wybrać funkcję wielomianową stopnia drugiego.

Nasz wielomian będzie miał postać Gdzie и — losowo wybrane liczby całkowite dodatnie. Konstruujemy po prostu wielomian o stopniu , gdzie jest współczynnikiem swobodnym  - to jest nasz sekret i każdy z kolejnych członkowie mają losowo wybrany dodatni współczynnik. Jeśli wrócimy do pierwotnego przykładu i założymy, że , a następnie otrzymujemy funkcję .

Na tym etapie możemy generować fragmenty poprzez łączenie unikalne liczby całkowite w Gdzie (bo to nasz sekret). W tym przykładzie chcemy rozłożyć cztery fragmenty z progiem trzech, więc losowo generujemy punkty i wysyłamy po jednym punkcie każdej z czterech zaufanych osób, strażników klucza. Informujemy również, że ponieważ jest to informacja publiczna i niezbędna do odzyskania .

Przywracanie tajemnicy

Omówiliśmy już koncepcję interpolacji wielomianowej i to, w jaki sposób leży ona u podstaw schematu progowego Shamira. . Gdy którykolwiek z trzech z czterech powierników chce przywrócić , oni po prostu muszą interpolować z własnymi, unikalnymi cechami. Aby to zrobić, mogą zdefiniować swoje punkty i obliczyć wielomian interpolacyjny Lagrange'a korzystając z następującego wzoru. Jeśli lepiej rozumiesz programowanie niż matematykę, to pi jest w zasadzie operatorem for, który mnoży wszystkie wyniki, a sigma jest for, co wszystko łączy.

w możemy rozwiązać to w następujący sposób i odzyskać naszą oryginalną funkcję wielomianową:

Ponieważ wiemy, że , powrót do zdrowia wykonuje się to po prostu:

Korzystanie z niebezpiecznej arytmetyki całkowitej

Chociaż udało nam się z powodzeniem zastosować podstawową ideę Shamira , pozostał nam problem, który do tej pory ignorowaliśmy. Nasza funkcja wielomianowa używa niebezpiecznej arytmetyki liczb całkowitych. Należy zauważyć, że z każdym dodatkowym punktem, jaki atakujący uzyska na naszym wykresie funkcji, zmniejsza się liczba możliwości uzyskania innych punktów. Można to zobaczyć na własne oczy, kreśląc wykres funkcji wielomianowej z rosnącą liczbą punktów, korzystając z arytmetyki liczb całkowitych. Jest to sprzeczne z naszym deklarowanym celem bezpieczeństwa, ponieważ atakujący nie powinien wiedzieć absolutnie nic, dopóki nie uzyska przynajmniej paprochy.

Aby pokazać, jak słaby jest schemat arytmetyki liczb całkowitych, rozważmy scenariusz, w którym atakujący ma dwa punkty i zna informacje publiczne, które . Z tych informacji może wywnioskować , równe dwa i podstaw znane wartości do wzoru и .

Następnie atakujący może znaleźć , policzywszy :

Ponieważ zdefiniowaliśmy jako losowo wybrane liczby całkowite dodatnie, istnieje ograniczona liczba możliwych . Wykorzystując te informacje, atakujący może wywnioskować , ponieważ wszystko większe niż 5 będzie działać negatywny. Okazuje się, że to prawda, ponieważ ustaliliśmy,

Następnie atakujący może obliczyć możliwe wartości wymiana в :

Z ograniczonym zakresem opcji dla staje się jasne, jak łatwo jest wybierać i sprawdzać wartości . Tutaj jest tylko pięć opcji.

Rozwiązanie problemu z niebezpieczną arytmetyką całkowitą

Aby wyeliminować tę lukę, Shamir proponuje wykorzystanie arytmetyki modularnej, zastępując na Gdzie и — zbiór wszystkich liczb pierwszych.

Przypomnijmy sobie szybko jak działa arytmetyka modularna. Zegar ze wskazówkami to powszechnie znany koncept. Ona używa zegarka, który jest . Gdy wskazówka godzinowa minie liczbę dwanaście, wraca do liczby jeden. Ciekawą właściwością tego systemu jest to, że patrząc na zegar 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 dokładnie określić liczbę godzin, które upłynęły, korzystając z prostego wzoru Gdzie  - to jest nasz dzielnik (tutaj ),  — to jest współczynnik (ile razy dzielnik bez reszty wchodzi do liczby pierwotnej, tutaj ) i  — jest to reszta, która jest zwykle zwracana przez wywołanie operatora modulo (tutaj ). Znajomość wszystkich tych wartości pozwala nam rozwiązać równanie , ale jeśli pominiemy jakiś współczynnik, nigdy nie będziemy w stanie przywrócić pierwotnej wartości.

Możemy pokazać, jak to poprawia bezpieczeństwo naszego schematu, stosując go do naszego poprzedniego przykładu i używając . Nasza nowa funkcja wielomianowa i nowe punkty . Teraz klucznicy mogą ponownie wykorzystać interpolację wielomianową do rekonstrukcji naszej funkcji, tyle że tym razem operacje dodawania i mnożenia muszą być połączone z redukcją modulo. (na przykład ).

Załóżmy, że atakujący, korzystając z tego nowego przykładu, dowiedział się dwóch z tych nowych punktów, i informacji publicznej . Tym razem atakujący, opierając się na wszystkich posiadanych przez siebie informacjach, wyprowadza następujące funkcje, gdzie  — zbiór wszystkich liczb całkowitych dodatnich i reprezentuje współczynnik modułu .

Teraz nasz napastnik znalazł go ponownie , obliczywszy :

Następnie próbuje się wycofać ponownie wymiana в :

Tym razem ma poważny problem. W formule nie ma wartości , и . Ponieważ istnieje nieskończenie wiele kombinacji tych zmiennych, nie może on uzyskać żadnych dodatkowych informacji.

Względy bezpieczeństwa

Tajny plan dzielenia się informacjami Shamira sugeruje bezpieczeństwo z punktu widzenia teorii informacji. Oznacza to, że matematyka jest odporna nawet na ataki ze strony atakujących dysponujących nieograniczoną mocą obliczeniową. Jednakże program ten nadal ma kilka znanych problemów.

Na przykład plan Szamira nie tworzy sprawdzone fragmenty, to znaczy, że ludzie mogą swobodnie przedstawiać fałszywe fragmenty i przeszkadzać w przywróceniu właściwej tajemnicy. Wrogi opiekun fragmentów, dysponujący wystarczającą ilością informacji, mógłby nawet wytworzyć inny fragment, zmieniając według własnego uznania. Problem ten rozwiązuje się za pomocą weryfikowalne schematy dzielenia się tajemnicami, takie jak program Feldmana.

Innym problemem jest to, że długość dowolnego fragmentu jest równa długości odpowiadającego mu sekretu, zatem długość sekretu jest łatwa do ustalenia. Ten problem jest rozwiązany trywialnie farsz sekret zawierający dowolne liczby do ustalonej długości.

Na koniec należy zauważyć, że nasze obawy dotyczące bezpieczeństwa mogą wykraczać poza sam program. W przypadku rzeczywistych zastosowań kryptograficznych często istnieje zagrożenie atakami typu side-channel, w ramach których atakujący próbuje wyodrębnić przydatne informacje z czasu wykonywania aplikacji, pamięci podręcznej, awarii itp. Jeśli jest to niepokojące, podczas tworzenia aplikacji należy dokładnie rozważyć zastosowanie środków ochronnych, takich jak funkcje i wyszukiwania o stałym czasie, zapobieganie zrzucaniu pamięci na dysk i szereg innych działań wykraczających poza zakres tego artykułu.

Демо

Na aktualizacja Zaprezentowano interaktywną demonstrację tajnego schematu dzielenia się informacjami Szamira. Demonstracja została przeprowadzona na podstawie biblioteki ssss-js, który sam w sobie jest portem JavaScript popularnego programu ssss. Należy pamiętać, że obliczanie dużych wartości , и może to potrwać chwilę.

Źródło: www.habr.com