Tajne udostępnianie przy użyciu chińskiego twierdzenia o resztach

Tajne udostępnianie polega na odzyskaniu tajnego S z zestawu udziałów, z których każdy zawiera częściowe informacje na temat sekretu. Chińskie twierdzenie o resztach (CRT) stwierdza, że dla danego układu równoczesnych równań kongruencji rozwiązanie jest unikalne w pewnym $Z / n Z$ , gdzie $n > 0$ w pewnych odpowiednich warunkach na kongruencjach. Tajne udostępnianie może zatem użyć CRT do uzyskania udziałów przedstawionych w równaniach kongruencji, a tajemnicę można odzyskać, rozwiązując układ kongruencji, aby uzyskać unikalne rozwiązanie, które będzie tajemnicą do odzyskania.

Sekretne schematy udostępniania: kilka typów

Istnieje kilka typów schematów udostępniania informacji tajnych . Najbardziej podstawowymi typami są tak zwane progowe , w których liczy się tylko liczność zbioru akcji. Innymi słowy, mając sekret S i n udziałów, każdy zbiór udziałów t jest zbiorem o najmniejszej liczności , z którego można odzyskać sekret, w tym sensie, że żaden zbiór udziałów t-1 nie wystarczy, aby dać S . Jest to znane jako struktura dostępu progowego . Takie schematy nazywamy ( t , n ) progowe schematy udostępniania tajemnic lub schemat t -out-of- n .

udostępniania tajemnic progowych różnią się między sobą sposobem generowania udziałów, zaczynając od określonej tajemnicy. Pierwszy z nich to progowy schemat współdzielenia sekretów Shamira , który opiera się na interpolacji wielomianowej w celu znalezienia S z danego zestawu udziałów, oraz geometryczny schemat udostępniania sekretów George'a Blakleya , który wykorzystuje metody geometryczne do odzyskania tajnego S. Progowe udostępnianie tajnych informacji schematy oparte na CRT zawdzięczają Mignotte i Asmuth-Bloom, używają specjalnych ciągów liczb całkowitych wraz z CRT.

Chińskie twierdzenie o resztach

Niech ${\ Displaystyle k \ geqslant 2, m_ {1}, ..., m_ {k} \ geqslant 2$ i $Displaystyle b_ {1}, ..., b_ {k} \ in \ mathbf {Z}}$ . System kongruencji

{\ Displaystyle {\ rozpocząć {przypadki} x \ równoważnik & b_ {1} \ {\ bmod {\}} m_ {1} \\&\ vdots \ \x\equiv &b_{k}\ {\bmod {\ }}m_{k}\\\end{przypadki}}}

ma rozwiązania w $Z$ wtedy i tylko wtedy, gdy ${\ Displaystyle b_ {i} \ równoważnik b_ {j} {\ bmod {(}} m_ {i}, m_ {j} )}$ dla wszystkich ${\ Displaystyle 1 \ leqslant i, j \ leqslant k}$ , gdzie ${\ Displaystyle (m_ {i}, m_ {j})}$ oznacza Największy wspólny dzielnik GCD ) $mi i$ m $j .$ Ponadto w tych warunkach układ ma unikalne rozwiązanie w $Z / n Z$ , gdzie ${\ Displaystyle n = [m_ {1}, ..., m_ {k}]}$ , co oznacza najmniejszą wspólną wielokrotność (LCM) ${\ Displaystyle m_ {1}, ..., m_ {k}}$ .

Tajne udostępnianie za pomocą CRT

Ponieważ chińskie twierdzenie o resztach dostarcza nam metody jednoznacznego wyznaczania liczby S modulo k -wiele względnie pierwszych liczb całkowitych ${\ Displaystyle m_ {1}, m_ {2}, ..., m_ {k}}$ , biorąc pod uwagę, że ${\ Displaystyle S <\ prod _ {i = 1} ^{k}m_{i}}$ , to pomysł polega na skonstruowaniu schematu, który określi sekret S przy dowolnych k udziałach (w tym przypadku resztę S modulo każdej z liczb $m i$ ), ale nie ujawni sekretu podanego mniej niż k takich Akcje.

Ostatecznie wybieramy n względnie pierwszych liczb całkowitych ${\ Displaystyle m_ {1}<m_ {2}<... <m_ {n}}$ takie, że S jest mniejsze niż iloczyn dowolnego wyboru k tych liczb całkowitych, ale jednocześnie jest większe niż dowolny wybór k-1 z nich. Wtedy udziały ${\ Displaystyle s_ {1}, s_ {2}, ..., s_ {n}}$ są zdefiniowane przez ${\ Displaystyle s_ {i} = S {\ bmod {\}} m_{i}}$ dla $, n}$ . W ten sposób dzięki CRT możemy jednoznacznie wyznaczyć S z dowolnego zbioru k lub więcej udziałów, ale nie mniej niż k . Zapewnia to tzw struktura dostępu progowego .

Ten warunek na S można również uznać za

{\ Displaystyle \ prod _ {i = nk + 2} ^ {n} m_ {i}<S <\ prod _ {i = 1} ^ {k} m_ {i}.}

Ponieważ S jest mniejszy niż najmniejszy iloczyn k liczb całkowitych, będzie mniejszy niż iloczyn dowolnego k z nich. Ponadto, będąc większym niż iloczyn największych $k - 1$ liczb całkowitych, będzie większy niż iloczyn dowolnego $k - 1$ z nich.

Istnieją dwa schematy tajnego udostępniania , które zasadniczo wykorzystują ten pomysł, schematy Mignotte'a i schematy Asmutha-Blooma, które wyjaśniono poniżej.

Progowy schemat udostępniania tajemnic Mignotte

udostępniania tajemnic progowych Mignotte'a wykorzystuje, wraz z CRT, specjalne sekwencje liczb całkowitych zwane sekwencjami ( k , n ) -Mignotte, które składają się z n liczb całkowitych parami względnie pierwszych , tak że iloczyn najmniejszego k z nich to większy niż iloczyn $k - 1$ największych. Ten warunek jest kluczowy, ponieważ schemat opiera się na wybraniu sekretu jako liczby całkowitej między dwoma produktami, a ten warunek zapewnia, że co najmniej k akcje są potrzebne, aby w pełni odzyskać tajemnicę, bez względu na to, jak zostaną wybrane.

Formalnie niech $2 \leq k \leq n$ będzie liczbami całkowitymi. A ( k , n ) -Mignotte sekwencja jest ściśle rosnącą sekwencją dodatnich liczb całkowitych ${\ Displaystyle m_ {1}<\ cdots <m_ {n}}$ , gdzie ${\ Displaystyle (m_ {i}, m_ {j}) = 1}$ dla wszystkich $1 \leq ja < jot \leq n$ tak, że ${\ Displaystyle m_ {nk + 2} \ cdots m_ {n}<m_ {1} \ cdots m_ {k}}$ . Niech ${\ Displaystyle \ alfa = m_ {nk + 2} \ cdots m_ {n}}$ i ${\ Displaystyle \ beta = m_ {1 }\cdots m_{k}}$ ; nazywamy liczby całkowite leżące ściśle między dozwolonym zakresem a $.$ $\ displaystyle \ beta}$ Budujemy ( k , n ) - progowy $liczbę całkowitą$ udostępniania tajemnic Wybieramy tajne S jako losową w autoryzowanym zakresie Obliczamy dla każdego $1 \leq i \leq n$ modulo redukcji $mi z$ S , $si które$ nazywamy , to są udziały. $_$ dla k różnych _

{\ Displaystyle {\ rozpocząć {przypadki} x \ równoważnik & s_ {i_ {1}} \ {\ bmod {\}} m_ {i_ {1}}\\&\vdots \\x\equiv &s_{i_{k}}\ {\bmod {\ }}m_{i_{k}}\\\end{przypadki}}}

Zgodnie z $system$ twierdzeniem o są względnie pierwsze ma ${\ Displaystyle m_ {i_ {1}} \ cdots m_ {i_ {k}}}$ . Dzięki konstrukcji naszych udziałów to rozwiązanie to nic innego jak tajne S do odzyskania.

Progowy schemat udostępniania tajemnic Asmuth-Bloom

Ten schemat wykorzystuje również specjalne sekwencje liczb całkowitych. Niech $2 \leq k \leq n$ będzie liczbami całkowitymi. Rozważamy sekwencję całkowitych względnie pierwszych dodatnich ${\ Displaystyle m_ {0}<... <m_ {n}}$ takie, że ${\ Displaystyle m_ {0} \ cdot m_ {n-k + 2} \ cdots m_ {n}<m_ {1} \ cdots m_ {k}}$ . Dla tej podanej sekwencji wybieramy sekret S jako losową liczbę całkowitą w zbiorze $0 Z / m Z$ .

Następnie wybieramy losową liczbę całkowitą $α$ taką, że ${\ Displaystyle S + \ alfa \ cdot m_ {0}<m_ {1} \ cdots m_ {k}}$ . Obliczamy modulo $ja,$ $dla$ 1 $\leq \leq n,$ to ja ${\ Displaystyle I_ {i} = (s_ {i}, m_ {i})}$ . Teraz dla dowolnych k różnych udziałów ${\ Displaystyle I_ {i_ {1}}, ..., I_ {i_ {k}}}$ , rozważamy system kongruencji

${\ Displaystyle {\ rozpocząć {przypadki} x \ równoważnik & s_ {i_ {1}} \ {\ bmod {\}} m_ {i_ {1}}\\&\vdots \\x\equiv &s_{i_{k}}\ {\bmod {\ }}m_{i_{k}}\\\end{przypadki}}}$

Z chińskiego twierdzenia o resztach , ponieważ ${k}}}$ są parami względnie pierwsze , system ma unikalne rozwiązanie $S 0$ modulo ${\ Displaystyle m_ {i_{1}}\cdots m_{i_{k}}}$ . Dzięki konstrukcji naszych udziałów tajemnicą S jest moduł $redukcji 0$ $m 0$ S .

Należy zauważyć, że schemat udostępniania tajemnicy z progiem Mignotte ( k , n ) nie jest doskonały w tym sensie, że zbiór mniej niż k akcji zawiera pewne informacje o tajemnicy. Schemat Asmutha-Blooma jest doskonały: $α$ jest niezależny od tajnego $S$ i

${\ Displaystyle \ lewo. {\ rozpocząć {tablica} {r} \ prod _ {i = nk + 2} ^ {n}m_{i}\\\alpha \end{array}}\right\}<{\frac {\prod _{i=1}^{k}m_{i}}{m_{0}}} }$

Dlatego $α$ może być dowolną liczbą całkowitą modulo

{\ Displaystyle \ prod _ {i = nk + 2} ^ {n} m_ {i}.}

Ten iloczyn $k - 1$ modułów jest największym z dowolnych n wybranych $k - 1$ możliwych produktów, dlatego każdy podzbiór $k - 1$ równoważności może być dowolną liczbą całkowitą modulo jego iloczynu i żadna informacja z $S$ nie wycieka.

Przykład

Poniżej znajduje się przykład schematu Asmutha-Blooma. Ze względów praktycznych wybieramy małe wartości dla wszystkich parametrów. Wybieramy k=3 i n=4 . M $13, m_ {3 } = 17}$ , 17 {\ Displaystyle m_ {0} = 3, i ${\ displaystyle m_ {4} = 19}$ . Spełniają wymaganą sekwencję Asmutha-Blooma, ponieważ ${\ Displaystyle 3 \ cdot 17 \ cdot 19 <11 \ cdot 13 \ cdot 17}$ .

$, że$ naszym sekretem $S$ jest 2. Wybierz spełniając warunek wymagany dla schematu Asmutha-Blooma Następnie i obliczamy udziały dla każdej z liczb całkowitych 11, 13, 17 i 19. Są to odpowiednio $,$ rozważmy jeden możliwy zestaw 3 udziałów: spośród 4 możliwych zestawów 3 udziałów bierzemy zbiór {1,12,2} i pokazujemy, że odzyskuje on tajemnicę S=2. Rozważmy następujący system kongruencji:

{\ Displaystyle {\ rozpocząć {przypadki} x \ równoważnik i 1 \ {\ bmod {\}} 11 \\ x \ równoważnik i 12 \ {\ bmod {\ }}13\\x\równoważnik &2\ {\bmod {\ }}17\\\koniec {przypadków}}}

Aby rozwiązać system, niech ${\ Displaystyle M = 11 \ cdot 13 \ cdot 17}$ . Z konstruktywnego algorytmu rozwiązywania takiego systemu wiemy, że rozwiązaniem systemu jest ${\ Displaystyle x_ {0} = 1 \ cdot e_ {1} +12\cdot e_{2}+2\cdot e_{3}}$ , gdzie każde $e i$ znajduje się w następujący sposób:

Przez $_$ Bézouta ponieważ liczby całkowite $r ja$ $__$ _ przy użyciu rozszerzonego algorytmu euklidesowego , takiego, że ${\ displaystyle r_ {i}. m_ {i} + s_ {i}. M / m_ {i} = 1}$ . Ustaw $\ Displaystyle e_ {i} = s_ {i} \ cdot M / m_ {i}}$ .

Z tożsamości ${\ Displaystyle 1 = 1 \ cdot 221-20 \ cdot 11 = ( -5)\cdot 187+72\cdot 13=5\cdot 143+(-42)\cdot 17}$ , otrzymujemy, że ${\ Displaystyle e_ {1} = 221, e_ {2} = -935, e_ {3} = 715}$ i unikalne rozwiązanie modulo ${\ Displaystyle 11 \ cdot 13 \ cdot 17}$ wynosi 155. Wreszcie ${\ Displaystyle S = 155 \ równoważnik 2 \ mod 3}$ .

Zobacz też

Oded Goldreich , Dana Ron i Madhu Sudan , chiński pozostały z błędami, IEEE Transactions on Information Theory, tom. 46, nr 4, lipiec 2000, strony 1330-1338.
Mignotte M. (1983) Jak podzielić się sekretem. W: Beth T. (red.) Kryptografia. EUROCRYPT 1982. Notatki z wykładów z informatyki, tom 149. Springer, Berlin, Heidelberg.
CA Asmuth i J. Bloom. Modułowe podejście do zabezpieczania kluczy. IEEE Transactions on Information Theory, IT-29(2):208-210, 1983.
Sorin Iftene. Ogólne tajne udostępnianie oparte na chińskim twierdzeniu o resztach z zastosowaniami w e-głosowaniu. Notatki elektroniczne w informatyce teoretycznej (ENTCS). Tom 186, (lipiec 2007). Strony 67–84. Rok wydania: 2007. ISSN 1571-0661 .
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów, wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN 0-262-03293-7 . Sekcja 31.5: Chińskie twierdzenie o resztach, strony 873-876.
Ronalda Cramera . Podstawowe udostępnianie tajemnic (wykłady 1-2), notatki z zajęć. Październik 2008, wersja 1.1.

Linki zewnętrzne

https://web.archive.org/web/20091209071915/http://www.cryptolounge.org/wiki/Ronald_Cramer