Schéma Asmuth-Bloom

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. června 2014; kontroly vyžadují 4 úpravy .

Schéma Asmuth-Bloom je schéma tajného sdílení prahových hodnot vytvořené pomocí prvočísel . Umožňuje vám sdílet tajemství (číslo) mezi stranami takovým způsobem, že jej mohou získat všichni účastníci. $n$ $m$

Popis

Nechte být nějakým tajemstvím, které chcete sdílet. Vyberte prvočíslo větší než . Čísla relativně prvočísla jsou vybrána tak, že: $M$ $p$ $M$ $n$ ${\displaystyle d_{1},d_{2},\dots ,d_{n))$

$\forall i:d_{i}>p$
$\forall i:d_{i}<d_{i+1}$
${\displaystyle d_{1}*d_{2}*\tečky d_{m}>p*d_{n-m+2}*d_{n-m+3}*\tečky *d_{n))$

Vybere se a vypočítá náhodné číslo $r$

M'=M+rp

Akcie se počítají:

{\displaystyle k_{i}=M'\mod d_{i))

Účastníci jsou uvedeni ${\displaystyle \left\{p,d_{i},k_{i}\right\))$

Nyní pomocí čínské věty o zbytku je možné získat tajemství tím, že budete mít více sdílení. $M$ $m$

Příklad

Předpokládejme, že potřebujeme sdílet tajemství mezi čtyři účastníky takovým způsobem, aby je mohli získat všichni tři (a dva účastníci nemohli). To znamená, že je nutné zavést (3,4)-prahové schéma. $M=2$

Jako prvočíslo zvolíme , jako koprimé - . Kontrolujeme, že: $p=3$ $11,13,17,19$

$\forall i:d_{i}>p$ $\forall i:i\in \{11,13,17,19\},i>p=3$
${\displaystyle d_{1}<d_{2}<d_{3}<d_{4))$ $11<13<17<19$
${\displaystyle d_{1}*d_{2}*\tečky d_{m}>p*d_{n-m+2}*d_{n-m+3}*\tečky *d_{n))$ ${\displaystyle d_{1}*d_{2}*d_{3}>p*d_{3}*d_{4))$ $11*13*17>3*17*19$

Vyberte náhodné číslo a vypočítejte: $r=51$

M'=M+rp=2+51*3=155

Vypočítáme podíly:

{\displaystyle k_{i}=M'\mod d_{i))

k_{1}=155\mod 11=1

k_{2}=155\mod 13=12

k_{3}=155\mod 17=2

k_{4}=155\mod 19=3

Nyní se pokusíme obnovit původní tajemství s podíly , , . Udělejme soustavu rovnic: $\left\{3,11,1\right\}$ $\left\{3,13,12\right\}$ $\left\{3,17,2\right\}$

1=M'\mod 11

12=M'\mod 13

2=M'\mod 17

Můžeme se zotavit pomocí čínské věty o zbytku . $M'$

Když to víme, získáme tajemství. $M'$

M\equiv M'\mod p

M\equiv 155\mod 3\equiv 2

V tomto příkladu (od 155<17*19) dva účastníci tiše obnoví tajemství. M' musí být větší než součin podílů neoprávněných účastníků.

Zobecněné schéma Asmuth–Bloom v polynomickém kruhu v několika proměnných

Uvažujme polynomiální kruh v několika proměnných nad Galoisovým polem . Nechť se stanoví nějaký monomiální řád. Pak je jednoznačně definována redukce polynomického modulu a ideálu. Dovolit být ideály nulové dimenze a být nějaké polynomy. Pak platí tvrzení: systém srovnání $\mathbb {F} _{q}[X]$ $X=(x_{1},\cdots ,x_{n})$ $\mathbb {F} _{q}$ ${\displaystyle I_{1},I_{2},\cdots ,I_{t))$ $s_{1}(X),s_{2}(X),\cdots ,s_{t}(X)\in \mathbb {F} _{q}[X]$

{\begin{cases}c(X)&\equiv s_{1}(X)\ {\bmod {\ }}I_{1}\\c(X)&\equiv s_{2}(X )\ {\bmod {\ }}I_{2}\\&\vdots \\c(X)&\equiv s_{t}(X)\ {\bmod {\ }}I_{t}\\\end {případy}}

je buď nekonzistentní, nebo má jedinečné řešení modulo nejmenší společný násobek (LCM) ideálů . V případě, že ideály jsou párové coprime, tedy , máme zobecněnou čínskou větu o zbytku a řešení systému vždy existuje. ${\displaystyle I_{1},I_{2},\cdots ,I_{t))$ $I_{i}+I_{j}=1,\forall i\neq j$

Nejprve zvažte zobecnění schématu Mignotte . Tajenka bude nějaký polynom , účastník dostane modul a částečnou tajenku . Pro implementaci přístupové struktury je nutné a postačující, aby tajemství bylo redukováno modulo LCM ideálů z jakékoli povolené podmnožiny účastníků a nebylo takové pro zakázané podmnožiny. $C(X)$ $i$ $I_i$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

Ve zobecněném schématu Asmuth-Bloom existuje další modul a tajemství je . V tomto schématu se nazývá střední tajemství. $I_0$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

Dokonalost schématu

Schéma sdílení tajemství se nazývá dokonalé, pokud zakázaná podmnožina účastníků neobdrží žádné další informace o tajemství, s výjimkou a priori. Jinými slovy, rozdělení tajemství zůstává jednotné i v případě dílčích tajemství účastníků ze zakázané podmnožiny. Schéma Asmuth-Bloom, na rozdíl od schématu Mignotte, může být dokonalé.

Abychom vytvořili kritérium dokonalosti, prozkoumáme schéma Asmuth-Bloom v kruhu . Označme množinou monomiálů redukovaného modulo a lineárním rozpětím . Nechte také $\mathbb {F} _{q}[X]$ $RT(I)$ $já$ $RP(I)$ $RT(I)$

I^{B}={\mbox{HOK}}[I_{i},i\in B],\ M_{2}=\bigcap _{B\in \Gamma }RT(I^{B })

je množina monočlenů, které leží v průsečíku ideálů všech povolených podmnožin. Všimněte si, že střední tajemství . $RT$ $C(X)\in RP(M_{2})$

Teorém. Schéma Asmuth–Bloom v prstenu je dokonalé tehdy a pouze tehdy, jsou-li splněny následující podmínky: $\mathbb {F} _{q}[X]$

1) .

I_{0}+I_{i}=1,\forall i\in J

2) .

{\displaystyle \forall A\notin \Gamma :RT(I^{A}I_{0})\subseteq M_{2))

Důkaz.

Potřeba. Nechť existuje dokonalé Asmuth-Bloomovo schéma, ale není splněna první podmínka věty, tj . Pak lze sadu možných tajných hodnot pro takového účastníka zúžit: . Proto je schéma nedokonalé - dostali jsme rozpor. $\exists I_{i}:I_{i}+I_{0}=D\neq 0$ $c(X)\equiv s_{i}(X)\ {\bmod {\ }}D$

Nechť je splněna první podmínka, ale druhá ne, tj. existuje zakázaná podmnožina taková, že . Jinými slovy, existuje jednočlenný . Zvažte polynom $A$ $RT(I^{A}I_{0})\not \subset M_{2}$ $m\in RT(I^{A}I_{0})\obrácené lomítko M_{2}$

g(X)=s^{A}(X)+(mm({\bmod {I}}^{A}))=s^{A}(X)+f_{m}(X) ,

kde je sdílené částečné tajemství získané účastníky z podmnožiny . $s^{A}(X)$ $A$

Všimněte si, že polynom pak splňuje následující podmínky: $f_{m}(X)$

jeden)

f_{m}(X)\in I^{A}

f_{m}(X)\in RP(I^{A}I_{0})

3) Obsahuje monomial .

m

Proto, . Nechte _ Podle čínské věty o zbytku pro systém $g(X)\in RP(I^{A}I_{0})$ $c'=g(X)\ {\bmod {\ }}I_{0}$

{\begin{cases}C(X)\equiv s^{A}(X)\ {\bmod {\ }}I^{A}\\C(X)\equiv c'(X)\ {\bmod {\ }}I_{0}\\\end{cases}}

existuje jedinečné řešení v , ale konstrukcí je toto řešení polynom . Na druhou stranu , což znamená, že hodnota pro tajemství je nemožná - opět jsme dostali rozpor. $RP(I^{A}I_{0})$ $g(X)$ $m\in g(X)\notin RP(M_{2})$ $c'(X)$

Přiměřenost. Nechť jsou splněny podmínky věty. Ukažme, že tajemství zůstává rovnoměrně rozložené v přítomnosti dílčích tajemství ze zakázané podmnožiny. Uvažujme libovolnou zakázanou podmnožinu a množinu polynomů $A\notin\Gamma$

{\displaystyle V=\{s^{A}(X)+f(X)|f(X)\v I^{A},f(X)\v LP(M_{2})\))

je sada možných hodnot středního tajemství.

Opravme nějakou hodnotu tajenky Pak existuje jedinečný polynom , takový , že podle čínské věty o zbytku $c^{j}(X)\in RP(I_{0})$ $g^{j}(X)\in LP(I^{A}I_{0})$

g^{j}(X)\equiv s^{A}(X)\ {\bmod {\ }}I^{A}

g^{j}(X)\equiv c^{j}(X)\ {\bmod {\ }}I_{0}

Zvažte nyní 2 případy:

1) Jestliže , pak každá tajná hodnota odpovídá jednomu mezilehlému tajnému klíči z množiny , tj. tajemství zůstává rovnoměrně distribuováno v přítomnosti dílčích tajemství z podmnožiny . $RT(I^{A}I_{0})=M_{2}$ $PROTI$ $A$

2) Nechte tedy . Ke každému polynomu obsahujícímu alespoň jeden monom z , přiřadíme polynom ${\displaystyle RT(I^{A}I_{0})\subset M_{2))$ $f(X)\in RP(M_{2})$ $M_{2}\setminus RT(I^{A}I_{0})$

{\overline {f))(X)=f(X)-f(X)\ {\bmod {\ }}RT(I^{A}I_{0})\neq 0

Je zřejmé, že . Potom každá tajná hodnota odpovídá sadě mezilehlých tajných klíčů ${\overline {f}}(X)\in I^{A}I_{0}$ $c^{j}(X)\in RP(I_{0})$

C^{j}=\{g^{j}(X),g^{j}(X)+{\overline {f}}(X)|{\overline {f}}(X) \in I^{A}I_{0},{\overline {f}}(X)\in RP(M_{2})\}\subset V

Je zřejmé, že sady jsou ekvivalentní. Proto je v množině pro každou hodnotu tajemství stejný počet možných hodnot mezilehlého tajemství, což znamená rovnoměrné rozdělení tajemství i za přítomnosti dílčích tajemství ze zakázané podmnožiny. $C^{j}$ $PROTI$

Věta byla prokázána.

Literatura

Schneier B. Schéma Asmuth-Bloom // Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M .: Triumf, 2002. - S. 589-590. — 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
Asmuth C. , Bloom J. Modulární přístup k ochraně klíčů // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1983. - Sv. 29, Iss. 2. - S. 208-210. — ISSN 0018-9448 ; 1557-9654 – doi:10.1109/TIT.1983.1056651
Shenets N. N. O ideálních modulárních schématech sdílení tajných informací v polynomiálních kruzích v několika proměnných // Mezinárodní kongres o informatice: Informační systémy a technologie : materiály Mezinárodního vědeckého kongresu 31. - Minsk : BGU , 2011. - V. 1. Statuty Fakulty aplikované matematiky a informatiky. - S. 169-173. — ISBN 978-985-518-563-6
Stinson, D. R. Kryptografie: teorie a praxe. - Chapman a Hall/CRC, 2005. - S. 512. - ISBN 978-1584885085 .