Shamir Secret Sharing

Portfel to aplikacja lub urządzenie do odbierania i wysyłania bitcoinów. Anna chce kopii, która przetrwa utratę części zapisów. Wybiera trzy z pięciu: powstaje pięć różnych udziałów, a dowolne trzy poprawne udziały z tego samego zestawu odtwarzają sekret. Może stracić dwa, ale nie trzy. Potrzebna liczba to próg; ogólnie k z n oznacza k wymaganych udziałów spośród n utworzonych i pozwala stracić n−k. Próg nie rozpoznaje jednak zgody Anny. Jeśli ktoś zdobędzie trzy udziały albo ich posiadacze się porozumieją, odtworzą ten sam sekret. Niższy próg ułatwia odzyskanie, lecz zmniejsza też grupę zdolną zrobić to bez Anny. [1] [6]

Anna niewiele zyska, zapisując wszystkie pięć plików na jednym koncie w chmurze. Utrata lub przejęcie konta dotknie je wszystkie naraz. Kopia wymaga przemyślanego rozmieszczenia, zapisania metody i parametrów oraz sprawdzenia odtwarzania na zaufanym urządzeniu. Jeśli plan ma służyć spadkobiercom, muszą wiedzieć, czego szukają i jak bezpiecznie z tym postępować. Nowy losowy podział tego samego sekretu S tworzy nowy zestaw; starych i nowych udziałów nie miesza się. Wystarczający stary zestaw nadal jednak odtworzy S. Ponowny podział nie unieważnia ujawnionej, użytecznej kopii ani nie zmienia samego sekretu. [1] [4]

Zwykłe odtwarzanie ponownie składa cały sekret na jednym urządzeniu. Jeśli urządzenie zostało przejęte, napastnik może go wtedy poznać. Jeśli sekretem jest Private Key, czyli tajna wartość liczbowa służąca do utworzenia podpisu cyfrowego zatwierdzającego wydanie środków, posiadacz tego klucza może później podpisywać bez kolejnych udziałów. Multisig wymaga natomiast wielu podpisów zgodnie z warunkami konkretnego wydania. Istnieje też podpisywanie progowe: dodatkowy protokół MPC, bezpieczne wspólne obliczenie kilku uczestników, pozwala udziałom współtworzyć podpis bez składania całego klucza. NIST rozróżnia te sytuacje. Sam udział Shamira nie ustanawia takiego protokołu podpisywania. [3] [5] [6]

Dwa programy ze słowem Shamir w nazwie nie muszą odczytywać nawzajem swoich udziałów. Muszą zgadzać się operacje matematyczne, zapis wartości, identyfikatory i przynależność do zestawu. SLIP-39 to konkretny standard oparty na tej metodzie: dodaje listę słów, metadane, czyli informacje pomocnicze, grupy, szyfrowanie i kontrole błędów. Ogólna zasada nie jest więc instrukcją ręcznego podzielenia istniejącej Seed Phrase. Zanim powierzysz portfel takiej kopii, musisz znać obsługiwany format i sprawdzić, czy zamierzona procedura naprawdę pozwala ją odtworzyć. [2]

Przy trzech z pięciu skutek utraty dwóch udziałów jest jasny. Uszkodzony lub podrobiony udział może jednak doprowadzić podstawowe obliczenie do innego sekretu zamiast komunikatu o braku danych. Sama metoda nie potwierdza pochodzenia udziałów ani uczciwości ich twórcy. Wykrywanie i korygowanie błędów oraz verifiable secret sharing, czyli sprawdzanie poprawności podziału, to dodatkowe warstwy z własnymi założeniami. SLIP-39 dodaje na przykład sumę kontrolną i wartość kontrolną zwaną digest. Nie oznacza to, że każda aplikacja Shamir Secret Sharing ma te same kontrole ani że poprawna suma dowodzi wiarygodnego pochodzenia kopii. [2] [5]

W idealnym schemacie mniej niż k pełnych udziałów nie daje napastnikowi żadnej nowej informacji o S, nawet przy nieograniczonych obliczeniach. Udział nie jest widoczną jedną trzecią pierwotnych słów. Właściwość ta wymaga prawidłowej losowości: liczby użyte do podziału są wybierane niezależnie i z jednakowym prawdopodobieństwem. Przewidywalne liczby, ich ponowne używanie lub wyciek z pamięci urządzenia zmieniają sytuację. Osobno trzeba też oceniać dodatkowe dane kontrolne, na przykład digest w SLIP-39. A słabe pierwotne hasło nadal można odgadnąć inną drogą, mimo podziału jego kopii. [1] [2]

Weźmy mały sekret S=5 i wzór f(x)=5+3*x mod 17. mod 17 oznacza resztę z dzielenia przez 17. Trzy udziały to pary (1,8), (2,11), (3,14): pierwsza liczba określa pozycję, druga obliczoną wartość. Z dwóch pierwszych otrzymujemy przyrost 3 i pierwotny sekret 8−3=5. Każda z trzech możliwych par punktów odtworzy tę samą piątkę. Sam punkt (1,8) pasuje zaś do każdego S od 0 do 16, jeśli przyrost wybierzemy jako a=8−S mod 17. Małe liczby służą wyłącznie wyjaśnieniu, nie tworzeniu kopii prawdziwego portfela. [1]

Ogólny wzór to f(x)=S+a1*x+…+a(k−1)*x^(k−1). Wyrażenie to nazywa się wielomianem; S jest sekretem, a pozostałe współczynniki są niezależnymi, równomiernie losowymi elementami ciała skończonego, struktury o dokładnych zasadach dodawania i mnożenia. Udział ma postać (x,f(x)); każde x musi być inne i niezerowe: x=0 ujawniłoby S wprost. Z k punktów interpolacja Lagrange’a oblicza f(0), czyli sekret. Dwie kopie tego samego punktu nie dodają informacji. W ciele pierwszym GF(p) zwykłe dzielenie zastępuje mnożenie przez odwrotność modularną, której iloczyn z dzielnikiem wynosi 1. GF(256) działa też inaczej niż zwykłe reszty modulo 256; mylenie tych operacji byłoby błędem. [1]