Asmuth-Bloom séma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2014. június 24-én felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

Az Asmuth-Bloom séma egy prímszámok felhasználásával felépített titkos küszöbérték-megosztási séma . Lehetővé teszi a titok (szám) felek közötti megosztását oly módon, hogy bármely résztvevő visszaszerezze azt. $n$ $m$

Leírás

Legyen valami megosztandó titok. Válasszon egy nagyobb prímszámot , mint . Az egymáshoz viszonyított prímszámokat úgy választjuk meg , hogy: $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}*\dots d_{m}>p*d_{n-m+2}*d_{n-m+3}*\dots *d_{n))$

Egy véletlen számot választunk és kiszámítunk $r$

M'=M+rp

A részvények kiszámítása:

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

A résztvevők megadva ${\displaystyle \left\{p,d_{i},k_{i}\right\))$

Most a kínai maradék tételt használva lehetséges a titok visszaszerzése több megosztás birtokában. $M$ $m$

Példa

Tegyük fel, hogy meg kell osztanunk a titkot négy résztvevő között oly módon, hogy bármelyikük hárman visszaszerezhesse ezt a titkot (két résztvevő pedig nem). Vagyis egy (3,4)-küszöb sémát kell megvalósítani. $M=2$

Prímszámként a -t választjuk , koprímként - . Ellenőrizzük, hogy: $p=3$ $11,13,17,19$

$\forall i:d_{i}>p$ $\forall i:i\in \{11,13,17,19\},i>p=3$
${\megjelenítési stílus 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álasszon ki egy véletlen számot , és számolja ki: $r=51$

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

Kiszámoljuk a részesedéseket:

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

Most próbáljuk meg visszaállítani az eredeti titkot, a , , megosztások birtokában . Készítsünk egyenletrendszert: $\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

A kínai maradéktétel segítségével helyreállíthatjuk . $M'$

Ennek tudatában megtudjuk a titkot. $M'$

M\equiv M'\mod p

M\equiv 155\mod 3\equiv 2

Ebben a példában (mivel 155<17*19) két résztvevő csendben visszaállítja a titkot. M'-nek nagyobbnak kell lennie, mint a jogosulatlan résztvevők részesedésének szorzata.

Egy általánosított Asmuth–Bloom séma polinomiális gyűrűben több változóban

Tekintsünk egy többváltozós polinomgyűrűt egy Galois-mező felett . Rögzítsünk valamilyen monomiális sorrendet. Ekkor egy polinom modulo ideál redukciója egyedileg definiált. Legyenek nulldimenziós ideálok és néhány polinom. Akkor igaz az állítás: az összehasonlítások rendszere $\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 {esetek}}

vagy inkonzisztens, vagy egyedi megoldással rendelkezik az ideálok modulo legkisebb közös többszöröse (LCM) . Abban az esetben, ha az ideálok páronkénti koprímek, azaz , akkor az általánosított kínai maradéktételt kapjuk, és a rendszer megoldása mindig létezik. ${\displaystyle I_{1},I_{2},\cdots ,I_{t))$ $I_{i}+I_{j}=1,\forall i\neq j$

Tekintsük először a Mignotte-séma általánosítását . A titok valamilyen polinom lesz , a résztvevő kap egy modulust és egy résztitkot . A hozzáférési struktúra megvalósításához szükséges és elégséges, hogy a titok a résztvevők bármely engedélyezett részhalmazából az ideálok LCM-jére csökkenjen, és ne legyen ilyen a tiltott részhalmazoknál. $C(X)$ $én$ $I_i$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

Az általánosított Asmuth-Bloom sémában van egy további modul , és a titok a . Ebben a sémában ezt köztes titoknak nevezik. $I_0$ $s_{i}(X)=C(X)\ {\bmod {\ }}I_{i}$ $C(X)$

A séma tökéletessége

A titkos megosztási sémát tökéletesnek nevezzük, ha a résztvevők tiltott részhalmaza nem kap további információt a titokról, kivéve a priori. Más szóval, a titok eloszlása egyenletes marad még a tiltott részhalmaz résztvevőinek részleges titkai jelenlétében is. Az Asmuth-Bloom séma, ellentétben a Mignotte sémával, tökéletes lehet.

A tökéletesség kritériumának kidolgozásához megvizsgáljuk az Asmuth-Bloom sémát a gyűrűben . Jelölje a monomok redukált modulo halmazával és a lineáris fesztávval . Hadd is $\mathbb {F} _{q}[X]$ $RT(I)$ $én$ $RP(I)$ $RT(I)$

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

a monomiálisok halmaza, amelyek az összes megengedett részhalmaz ideáljának metszéspontjában helyezkednek el . Vegye figyelembe, hogy a köztes titok . $RT$ $C(X)\in RP(M_{2})$

Tétel. Az Asmuth-Bloom séma egy gyűrűben akkor és csak akkor tökéletes, ha a következő feltételek teljesülnek: $\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))

Bizonyíték.

Szükség. Legyen egy tökéletes Asmuth-Bloom séma, de a tétel első feltétele nem teljesül, azaz . Ezután az ilyen résztvevők lehetséges titkos értékeinek készlete szűkíthető: . Ezért a séma tökéletlen – ellentmondást kaptunk. $\exists I_{i}:I_{i}+I_{0}=D\neq 0$ $c(X)\equiv s_{i}(X)\ {\bmod {\ }}D$

Az első feltétel teljesüljön, de a második ne, azaz létezik olyan tiltott részhalmaz , amelyre . Más szóval, van egy monom . Tekintsük a polinomot $A$ $RT(I^{A}I_{0})\not \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) ,

hol van a részhalmazból a résztvevők által visszanyert megosztott részleges titok . $s^{A}(X)$ $A$

Vegye figyelembe, hogy a polinom ekkor eleget tesz a következő feltételeknek: $f_{m}(X)$

egy)

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

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

3) Tartalmazza a monomit .

m

Ezért ,. Hadd . A kínai maradéktétel szerint a rendszerre $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}}

-ben van egy egyedi megoldás , de szerkesztés szerint ez a megoldás polinom . Másrészt , ami azt jelenti, hogy a titok értéke lehetetlen - ismét ellentmondást kaptunk. $RP(I^{A}I_{0})$ $g(X)$ $m\in g(X)\notin RP(M_{2})$ $c'(X)$

Megfelelőség. Teljesüljenek a tétel feltételei. Mutassuk meg, hogy a titok egyenletesen eloszlik a tiltott részhalmazból származó részleges titkok jelenlétében. Tekintsünk egy tetszőleges tiltott részhalmazt és a polinomok halmazát $A\notin\Gamma$

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

a köztes titok lehetséges értékeinek halmaza.

Rögzítsük a titok valamilyen értékét, majd van egy egyedi polinom , amely a kínai maradéktétel szerint $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}

Tekintsünk most 2 esetet:

1) Ha , akkor minden titkos érték egyetlen köztes titoknak felel meg a halmazból , azaz. a titok egyenletesen eloszlik az alhalmazból származó részleges titkok jelenlétében . $RT(I^{A}I_{0})=M_{2}$ $V$ $A$

2) Akkor hagyjuk . Minden olyan polinomhoz , amely legalább egy monomit tartalmaz -ból , hozzárendeljük a polinomot ${\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

Nyilvánvaló, hogy . Ezután minden titkos érték egy köztes titkhalmaznak felel meg ${\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

Nyilvánvaló, hogy a készletek egyenértékűek. Ezért a titok minden értékéhez tartozó halmazban ugyanannyi lehetséges köztes titok értéke található, ami a titok egyenletes eloszlását jelenti még a tiltott részhalmazból származó részleges titkok jelenlétében is. ${\displaystyle C^{j))$ $V$

A tétel bizonyítást nyert.

Irodalom

Schneier B. Asmuth-Bloom séma // Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód: C. - M . : Triumf, 2002. - S. 589-590. — 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .
Asmuth C. , Bloom J. A kulcsok védelmének moduláris megközelítése // IEEE Trans . inf. Elmélet / F. Kschischang - IEEE , 1983. - 1. kötet. 29, Iss. 2. - P. 208-210. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1983.1056651
Shenets N. N. Az ideális moduláris titkos megosztási sémákról polinomiális gyűrűkben több változóban // International Congress on Informatics: Information Systems and Technologies : materials of the International Scientific Congress 31 Oct. - Minsk : BGU , 2011. - V. 1. Az Alkalmazott Matematikai és Informatikai Kar cikkei. - S. 169-173. — ISBN 978-985-518-563-6
Stinson, D. R. Kriptográfia: elmélet és gyakorlat. - Chapman és Hall/CRC, 2005. - P. 512. - ISBN 978-1584885085 .