Asmuth-Bloom-skema

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 24. juni 2014; checks kræver 4 redigeringer .

Asmuth-Bloom- skemaet er et tærskelhemmeligt delingsskema bygget ved hjælp af primtal . Giver dig mulighed for at dele hemmeligheden (nummeret) mellem parterne på en sådan måde, at alle deltagere kan gendanne den. $n$ $m$

Beskrivelse

Lad være med at dele en hemmelighed. Vælg et primtal større end . Tal , der er relativt prime i forhold til hinanden, er valgt , således at: $M$ $s$ $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}*\dots d_{m}>p*d_{n-m+2}*d_{n-m+3}*\dots *d_{n))$

Et tilfældigt tal vælges og beregnes $r$

M'=M+rp

Aktier beregnes:

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

Deltagerne gives ${\displaystyle \left\{p,d_{i},k_{i}\right\))$

Nu, ved at bruge den kinesiske restsætning , er det muligt at genvinde hemmeligheden ved at have og flere aktier. $M$ $m$

Eksempel

Antag, at vi skal dele hemmeligheden mellem fire deltagere på en sådan måde, at alle tre af dem kan genfinde denne hemmelighed (og to deltagere kunne ikke). Det vil sige, at det er nødvendigt at implementere en (3,4)-tærskelordning. $M=2$

Som et primtal vælger vi , som coprime - . Vi tjekker at: $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}*\dots d_{m}>p*d_{n-m+2}*d_{n-m+3}*\dots *d_{n))$ ${\displaystyle d_{1}*d_{2}*d_{3}>p*d_{3}*d_{4))$ $11*13*17>3*17*19$

Vælg et tilfældigt tal og beregn: $r=51$

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

Vi beregner andele:

{\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

Lad os nu prøve at gendanne den oprindelige hemmelighed med aktierne , , . Lad os lave et ligningssystem: $\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

Vi kan genoprette ved hjælp af den kinesiske restsætning . $M'$

Ved at vide , finder vi hemmeligheden. $M'$

M\equiv M'\mod p

M\equiv 155\mod 3\equiv 2

I dette eksempel (siden 155<17*19) vil to deltagere stille og roligt genoprette hemmeligheden. M' skal være større end produktet af uautoriserede deltageres andele.

Et generaliseret Asmuth-Bloom-skema i en polynomialring i flere variabler

Overvej en polynomialring i flere variable over et Galois-felt . Lad en eller anden monomial rækkefølge blive fastsat. Så er reduktionen af et polynomium modulo et ideal entydigt defineret. Lad være nul-dimensionelle idealer og være nogle polynomier. Så er udsagnet sandt: Systemet af sammenligninger $\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)\i \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 {cases}}

er enten inkonsekvent eller har en unik løsning modulo mindste fælles multiplum (LCM) af idealer . I det tilfælde, hvor idealerne er parvise coprime, dvs. , har vi den generaliserede kinesiske restsætning, og løsningen af systemet eksisterer altid. ${\displaystyle I_{1},I_{2},\cdots ,I_{t))$ $I_{i}+I_{j}=1,\forall i\neq j$

Overvej først en generalisering af Mignotte-ordningen . Hemmeligheden vil være et eller andet polynomium , deltageren får et modul og en delvis hemmelighed . For at implementere adgangsstrukturen er det nødvendigt og tilstrækkeligt, at hemmeligheden reduceres modulo LCM af idealer fra enhver tilladt delmængde af deltagere og ikke er sådan for forbudte delmængder. $C(X)$ $jeg$ $I_i$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

I det generaliserede Asmuth-Bloom-skema er der et ekstra modul , og hemmeligheden er . I denne ordning kaldes det en mellemhemmelighed. $I_0$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

Perfektion af skemaet

En hemmelig delingsordning kaldes perfekt, hvis den forbudte delmængde af deltagere ikke modtager yderligere information om hemmeligheden, undtagen a priori. Med andre ord forbliver fordelingen af hemmeligheden ensartet selv i nærværelse af delvise hemmeligheder for deltagere fra den forbudte undergruppe. Asmuth-Bloom-ordningen kan i modsætning til Mignotte-ordningen være perfekt.

For at udvikle et kriterium for perfektion undersøger vi Asmuth-Bloom-skemaet i ringen . Betegn ved sættet af monomialer reduceret modulo og ved det lineære spænd på . Lad også $\mathbb {F} _{q}[X]$ $RT(I)$ $jeg$ $RP(I)$ $RT(I)$

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

er det sæt af monomialer, der ligger i skæringspunktet mellem idealerne for alle tilladte delmængder. Bemærk, at den mellemliggende hemmelighed . $RT$ $C(X)\in RP(M_{2})$

Sætning. Asmuth-Bloom-skemaet i en ring er perfekt, hvis og kun hvis følgende betingelser er opfyldt: $\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))

Bevis.

Brug for. Lad der være et perfekt Asmuth-Bloom-skema, men den første betingelse for sætningen er ikke opfyldt, dvs. Derefter kan sættet af mulige hemmelige værdier for en sådan deltager indsnævres: . Derfor er ordningen ufuldkommen - vi fik en modsigelse. $\exists I_{i}:I_{i}+I_{0}=D\neq 0$ $c(X)\equiv s_{i}(X)\ {\bmod {\ }}D$

Lad den første betingelse være opfyldt, men den anden ikke, dvs. der eksisterer en forbudt delmængde , således at . Med andre ord er der en monomial . Overvej polynomiet $EN$ $RT(I^{A}I_{0})\ikke \subset M_{2}$ $m\in RT(I^{A}I_{0})\backslash M_{2}$

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

hvor er den delte delvise hemmelighed, som deltagerne har fundet fra undersættet . $s^{A}(X)$ $EN$

Bemærk, at polynomiet så opfylder følgende betingelser: $f_{m}(X)$

en)

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

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

3) Indeholder monomiet .

m

Derfor ,. Lad . Ifølge den kinesiske restsætning, for systemet $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{sager}}

der er en unik løsning i , men ved konstruktion er denne løsning et polynomium . På den anden side, , hvilket betyder, at værdien for hemmeligheden er umulig - igen fik vi en modsigelse. $RP(I^{A}I_{0})$ $g(X)$ $m\in g(X)\notin RP(M_{2})$ $c'(X)$

Tilstrækkelighed. Lad sætningens betingelser være opfyldt. Lad os vise, at hemmeligheden forbliver jævnt fordelt i nærværelse af delvise hemmeligheder fra den forbudte undergruppe. Overvej en vilkårlig forbudt delmængde og mængden af polynomier $A\notin\Gamma$

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

er sættet af mulige værdier for den mellemliggende hemmelighed.

Lad os fastsætte en værdi af hemmeligheden . Så er der et unikt polynomium , sådan at ifølge den kinesiske restsætning $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}

Overvej nu 2 tilfælde:

1) Hvis , så svarer hver hemmelig værdi til en enkelt mellemhemmelighed fra sættet , dvs. hemmeligheden forbliver jævnt fordelt i nærværelse af delvise hemmeligheder fra undergruppen . $RT(I^{A}I_{0})=M_{2}$ $V$ $EN$

2) Lad så . Til hvert polynomium , der indeholder mindst ét monomer fra , tilknytter vi polynomiet ${\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

Det er åbenlyst . Så svarer hver hemmelig værdi til et sæt mellemhemmeligheder ${\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) \i I^{A}I_{0},{\overline {f}}(X)\i RP(M_{2})\}\undersæt V

Det er klart, at sættene er ækvivalente. Derfor er der i sættet for hver værdi af hemmeligheden det samme antal mulige værdier af den mellemliggende hemmelighed, hvilket indebærer en ensartet fordeling af hemmeligheden selv i nærværelse af delvise hemmeligheder fra den forbudte delmængde. ${\displaystyle C^{j))$ $V$

Sætningen er blevet bevist.

Litteratur

Schneier B. Asmuth-Bloom-skema // Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protokoller, algoritmer og kildekode i C. - M. : Triumf, 2002. - S. 589-590. — 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .
Asmuth C. , Bloom J. En modulær tilgang til nøglesikring // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1983. - Vol. 29, Iss. 2. - S. 208-210. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056651
Shenets N. N. Om ideelle modulære hemmelige deleskemaer i polynomialringe i flere variabler // International Congress on Informatics: Information Systems and Technologies : Materials of the International Scientific Congress 31. okt. - Minsk : BGU , 2011. - V. 1. Artikler fra Fakultetet for Anvendt Matematik og Informatik. - S. 169-173. — ISBN 978-985-518-563-6
Stinson, D. R. Kryptografi: teori og praksis. - Chapman og Hall/CRC, 2005. - S. 512. - ISBN 978-1584885085 .