Mignotte-kaavio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 26. kesäkuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 9 muokkausta .

Mignotte-malli on kynnyksen salainen jakamismalli , joka on rakennettu alkulukujen avulla . Mahdollistaa salaisuuden (numeron) jakamisen osapuolten kesken siten, että kuka tahansa osallistuja voi palauttaa sen, mutta osallistujat eivät voi palauttaa salaisuutta. Kaava perustuu Kiinan jäännöslauseeseen . $n$ $k$ $k-1$

Historia

Ranskalainen tiedemies Maurice Mignotte ehdotti järjestelmää ensimmäisen kerran vuonna 1982 yhdeksi vaihtoehdoksi Adi Shamirin kuvaaman kynnysjärjestelmän käyttämiselle . Shamir itse ehdotti ratkaisua käyttämällä polynomiinterpolaatiota äärellisessä kentässä, jossa salaisuus oli itse polynomi. Mignotte puolestaan pystyi tarjoamaan yksinkertaisemman ratkaisun, joka perustuu modulaariseen lähestymistapaan - tietty luku on salaisuus ja sen jäännös modulo tietty luku on osittainen salaisuus. Mignotten muokattu kaava on Asmuth-Bloom -kaavio . Molemmissa skeemoissa salaisuuden palauttamiseen käytetään kiinalaista jäännöslausetta, jonka muotoilu määrittelee ainutlaatuisen ratkaisun (salaisuuden) [1] . $(k,n)$

Secret Sharing Scheme

Kiinan jäännöslause

Kaava perustuu kiinalaisen jäännöslauseen käyttöön, jonka avulla käyttäjät, joilla on osa salaisuudesta, voivat palauttaa itse salaisuuden ja ainutlaatuisella tavalla. Lauseen on olemassa useita versioita, sanotaan seuraavaksi yleiseksi: Olkoon . Sitten yhtälöjärjestelmä $k\geqslant 2,m_{1},\dots ,m_{k}\geqslant 2,b_{1},\dots ,b_{k}\in \mathbb {Z}$

${\begin{cases}x\equiv b_{1}\mod m_{1}\\\vdots \\x\equiv b_{k}\mod m_{k}\end{cases))$ on ratkaisuja jos ja vain jos . Lisäksi, jos pelkistetyssä järjestelmässä on ratkaisuja , sillä on ainutlaatuinen ratkaisu in määrittää pienimmän yhteisen kerrannaisen . Jos , Kiinan jäännöslausetta kutsutaan standardiksi [2] . $\mathbb {Z}$ $b_{i}\equiv b_{j}\mod (m_{i},m_{j})\forall 1\leqslant i,j\leqslant k$ $\mathbb {Z}$ $\mathbb {Z} _{[m_{1},\dots ,m_{k}]},[m_{1},\dots ,m_{k}]$ ${\displaystyle m_{1},\dots ,m_{k))$ $(m_{i},m_{j})=1\forall 1\leqslant i<j\leqslant k$

Kynnyksen salaiset jakamisjärjestelmät

Oletetaan, että on n käyttäjää numeroituina välillä - ja joukko ryhmiä , joissa ovat kaikki ryhmän aliryhmät . Itse asiassa salainen jakamisjärjestelmä on tapa luoda salaisuuksia siten, että: $yksi$ $n$ ${\mathcal {A}}\subseteq P({1,2,\dots ,n})$ $P({1,2,\dots ,n})$ $\{1,2,\pisteet,n\}$ ${\mathcal {A}}$ $(S,(I_{1},\dots ,I_{n}))$

(oikeus) Jokaiselle , kaikkien läsnäollessa löytämisen ongelma on "yksinkertainen" $A\in {\mathcal {A}}$ $S$ $minä$
(turvallisuus) Jokaiselle , löytämisongelma on "ratkaisematon" $A\in P({1,2,\dots ,n})\setminus {\mathcal {A}}$ $S$

$\mathcal{A}$ kutsumme pääsyrakennetta - salaisuudeksi ja - varjoiksi . Kutsutaan elementtijoukkoja valtuutusryhmistä . Ihanteellisessa salaisuuden jakamisjärjestelmässä minkään sellaisen ryhmän varjo, joka ei ole valtuutusryhmä, ei anna (informaatioteorian kannalta) tietoa salaisuudesta. On todistettu, että missä tahansa ihanteellisessa salaisuuden jakamisjärjestelmässä jokaisen varjon koon ei tulisi olla pienempi kuin itse salaisuuden koko. Luonnollinen edellytys on, että pääsyrakenteen tulee olla monotoninen, eli: . Kaikki käyttöoikeusrakenteet on kuvattu hyvin käyttämällä valtuutusryhmien vähimmäisjoukkoa: . Voit myös kuvata käyttöoikeusrakenteen, jolla ei ole valtuutusominaisuuksia: . Sitä kuvaa hyvin "ei-valtuutettujen" ryhmien enimmäismäärä: $S$ $I_{1},\dots ,I_{n}$ $S$ $A$ $\mathcal{A}$ $(\forall B\in P(\{1,2,\dots ,n\}))((\olemassa A\in {\mathcal {A)))(A\subseteq B)\Rightarrow B\ {\mathcal {A)))$ $\mathcal{A}$ ${\mathcal {A}}_{min}=\{A\in {\mathcal {A}}\mid (\forall B\in {\mathcal {A}}\setminus \{A\}) (\neg B\subseteq A)\}$ ${\bar {\mathcal {A}}}=P(\{1,2,\dots ,n\})\setminus {\mathcal {A}}$ ${\bar {\mathcal {A}}}_{max}=\{A\in {\bar {\mathcal {A}}}\mid (\forall B\in {\bar {\mathcal { A}}}\setminus \{A\})(\neg A\subseteq B)\}$

Ensimmäisissä salaisissa jakamisjärjestelmissä vain osallistujien määrällä oli merkitystä salaisuuden palauttamisessa. Tällaisia järjestelmiä on kutsuttu kynnyksen salaisiksi jakamisjärjestelmiksi. Olkoon , silloin pääsyrakennetta kutsutaan -kynnyspääsyrakenteeksi. $n\geqslant 2,2\leqslant k\leqslant n$ ${\mathcal {A}}=\{A\in P({1,2,\dots ,n})\mid |A|\geqslant k\}$ $(k,n)$

On myös syytä harkita, että -kynnyskäyttörakenteissa: $(k,n)$

${\bar {\mathcal {A}}}=\{A\in P(\{1,2,\dots ,n\})\mid |A|\leqslant k-1\}$

${\mathcal {A}}_{min}=\{A\in P(\{1,2,\dots ,n\})\mid |A|=k\}$

${\bar {\mathcal {A}}}_{max}=\{A\in P(\{1,2,\dots ,n\})\mid |A|=k-1\}$ .

Kaikkia salaisuuden jakamismenetelmiä kutsutaan myös kynnysarvosalaisuuden jakamisjärjestelmiksi [1] . $A$ $(k,n)$

Mignotte-sekvenssi

Mignotten kynnyksen salainen jakamisjärjestelmä käyttää erityisiä numerosarjoja, joita kutsutaan Mignotte-sekvensseiksi. Antaa olla kokonaisluku, , ja . -Mignotte-sekvenssi on positiivisten koprime -jonojen sarja siten, että viimeinen lause vastaa myös seuraavaa: [1] $n$ $n \geqslant 2$ $2\leqslant k\leqslant n$ $(k,n)$ ${\displaystyle p_{1}<p_{2}<\dots <p_{n))$ ${\displaystyle \prod _{i=0}^{k-2}p_{ni}<\prod _{i=1}^{k}p_{i))$ $\max _{1\leqslant i_{1}<\dots <i_{k-1}\leqslant n}(p_{i_{1}}\dots p_{i_{k-1}})<\ min _{1\leqslant i_{1}<\dots <i_{k}\leqslant n}(p_{i_{1}}\dots p_{i_{k}})$

Algoritmi

Kun otetaan huomioon Mignotte-julkinen avain, järjestelmä toimii seuraavasti:

Salaisuus valitaan satunnaislukuna siten, että missä . Toisin sanoen salaisuuden on oltava välillä ja $S$ $\beta <S<\alpha$ ${\displaystyle \alpha =\prod _{i=1}^{k}p_{i},\beta =\prod _{i=0}^{k-2}p_{ni))$ ${\displaystyle p_{1}*p_{2}*\dots *p_{k))$ ${\displaystyle p_{n-k+2}*\dots *p_{n))$
Osakkeet lasketaan kaikilta osin $I_{i}=S\mod p_{i}$ $1 \leqslant i \leqslant n$
Kun sinulla on erilaisia varjoja , voit saada salaisuuden käyttämällä kiinalaisen jäännöslauseen vakioversiota - se on ainoa ratkaisu järjestelmän moduloimiseksi: $k$ $I_{i_{1}},\dots ,I_{i_{k}}$ $S$ $p_{i_{1}}\dots p_{i_{k}}$

${\begin{cases}x\equiv I_{i_{1}}\mod p_{i_{1}}\\\vdots \\x\equiv I_{i_{k}}\mod p_{i_{ k}}\end{cases}}$ Salaisuus on ratkaisu yllä olevaan järjestelmään, lisäksi se on sisällä , koska . Toisaalta, kun on vain erilaisia varjoja , voimme sanoa, että missä on ainoa ratkaisu alkuperäisen järjestelmän moduloimiseksi (tässä tapauksessa: . [1] Hyväksyttävän turvallisuustason saavuttamiseksi Mignotte-sekvenssit, joilla on suuri arvo [ 3 ] Ilmeisesti Mignotte-skeemalla ei ole merkittävää kryptografista vahvuutta , mutta se voi olla hyödyllinen sovelluksissa, joissa varjojen tiiviys on ratkaiseva tekijä. $S$ ${\displaystyle Z_{{p_{i_{1))},\dots ,p_{i_{k))))$ $S<\alpha$ $k-1$ $I_{i_{1}},\dots ,I_{i_{k-1}}$ $S\equiv x_{0}\mod p_{i_{1}}\dots p_{i_{k-1}}$ $x_{0}$ $p_{i_{1}}\dots p_{i_{k-1}}$ $S>\beta \geqslant p_{i_{1}}\dots p_{i_{k-1}}>x_{0}$ $(k,n)$ ${\dfrac {\alpha -\beta }{\beta }}$

Esimerkki

Oletetaan, että haluat jakaa salaisuuden käyttäjien kesken, jotta kuka tahansa voi palauttaa sen. $n = 6$ $k=5$

Valitsemme Minotte-sekvenssin . $p_{1}=5,p_{2}=7,p_{3}=11,p_{4}=13,p_{5}=17,p_{6}=19$
Laske tälle sekvenssille , . $\alpha =p_{1}*p_{2}*p_{3}*p_{4}*p_{5}=85085$ $\beta =p_{3}*p_{4}*p_{5}*p_{6}=46189$
Valitsemme sellaisen , että esimerkiksi . $S$ $\beta <S<\alpha$ $S=50000$
Laskemme osuudet : $I_{i}=S\mod p_{i}$ $I_{1}=50000\mod 5=0,I_{2}=50000\mod 7=6,I_{3}=50000\mod 11=5,I_{4}=50000\mod 13=2 ,I_{5}=50000\mod 17=3,I_{6}=50000\mod 19=11$
Salaisuuden palauttamiseksi ratkaisemme varjojen yhtälöjärjestelmän (oletetaan, että osallistujat 1-5 palauttavat salaisuuden): $k$

${\begin{cases}x\equiv 0\mod 5\\x\equiv 6\mod 7\\x\equiv 5\mod 11\\x\equiv 2\mod 13\\x\equiv 3\ mod 17\end{cases}}$ .

Kiinan jäännöslauseen muotoilusta tiedämme, että ratkaisu on ainutlaatuinen.

Muutokset Mignotte-skeemaan

Yleistetty Mignotte-sekvenssi

Tietyssä kynnyskaaviossa sekvenssin elementit eivät välttämättä ole koprime. Antaa olla kokonaisluku, . Yleistetty Mignotte-sekvenssi on positiivisten kokonaislukujen sarja siten, että . On helppo nähdä, että mikä tahansa Mignotte -sekvenssi on yleistetty Mignotte -sekvenssi. Lisäksi, jos kerromme jokaisen yleistetyn sekvenssin elementin kiinteällä elementillä , saadaan myös yleistetty Mignotte -sekvenssi. Laajennettu Mignotte-skeema toimii samalla tavalla kuin tavallinen ja ja . Tässä tapauksessa salaisuuden löytämiseksi on käytettävä yleistettyä versiota kiinalaisesta jäännöslauseesta. [neljä] $n$ $n\geqslant 2,2\leqslant k\leqslant n$ $(k,n)$ ${\displaystyle p_{1},\dots ,p_{n))$ $\max _{1\leqslant i_{1}<\dots <i_{k-1}\leqslant n}([p_{i_{1}},\dots ,p_{i_{k-1}} ])<\min _{1\leqslant i_{1}<\dots <i_{k}\leqslant n}([p_{i_{1}},\dots ,p_{i_{k}}])$ $(k,n)$ $(k,n)$ $\delta \in Z,(\delta ,p_{1},\dots ,p_{n})=1$ $(k,n)$ $\alpha =\min _{1\leqslant i_{1}<\dots <i_{k}\leqslant n}([p_{i_{1)),\dots ,p_{i_{k))] )$ $\beta =\max _{1\leqslant i_{1}<\dots <i_{k-1}\leqslant n}([p_{i_{1)),\dots ,p_{i_{k- yksi}}])$

Painotettu salainen jakaminen

Kaavaa voidaan soveltaa myös painotetun salaisen jakamisjärjestelmän toteuttamiseen. Tasapainojärjestelmissä, joka on klassinen Mignotte-skeema, jokainen osallistuja saa samanarvoisen varjon. Kaavaa voidaan kuitenkin muokata niin, että osallistujat, joilla on suurempi varjopaino, tarvitsevat vähemmän muita varjoja kuin osallistujat, joilla on pienempi varjopaino.

Olkoon salaisuus, missä ovat käyttäjän varjojen painot. Luodaan Mignotte -sekvenssi, jossa . Sitten , Missä on mielivaltainen osio asettaa sellainen, että $S(k,n,N,P)$ $P=(p_{1},\dots ,p_{N})$ ${\näyttötyyli (k, W)}$ $W=\sum _{i=1}^{n}p_{i}$ $P_{i}=[\{P_{j}^{\prime }\mid j\in P_{a_{j}}\}]\forall 1\leqslant i\leqslant N$ $P_{a_{1}},\dots ,P_{a_{N}}$ $\{1,2,\dots ,W\}$ $|P_{a_{i}}|=p_{i}\forall 1\leqslant i\leqslant N$

Voit nähdä, että varjon koon ja painon välillä on yksi yhteen vastaavuus: esimerkiksi bitti on varjo, jonka paino on 1, varjo painolla painaa bittejä. Mignotte-mallin toteuttaminen painotetulla salaisen jakamisen kanssa ei ole tarkoituksenmukaista, koska Mignotte-sekvenssin ja painotetun pääsykynnysrakenteen generointi on työ- ja resurssiintensiivinen tehtävä. On olemassa yksinkertaisempia ja tehokkaampia painotettuja salaisia jakamisjärjestelmiä, jotka myös poistavat riippuvuuden varjon painon ja koon välillä. [5] $p_{i}$ $p_{i}*n$

Samanlaiset mallit

Asmuth-Bloom -kaavio [6] , joka myös perustuu kiinalaiseen jäännöslauseeseen, otettiin käyttöön ensimmäisen kerran vuonna 1983. Suurin ero on, että generointia vaativan Mignotte-sekvenssin sijaan on valittava alkuluku, siihen liittyvä koprime-lukusarja sekä jokin satunnaisluku, jolla salaisuus salataan, ja varjot lasketaan sen perusteella. salattu salaisuus. Asmuth-Bloom-järjestelmästä puuttuu joitain Mignotte-järjestelmän haittoja: $n$

Aluetta, jolta voit valita salaisuuden, ei ole rajoitettu
Joukko alle käyttäjän varjoja ei anna tietoa salaisuudesta $k$

On olemassa useita painotettuja salaisia jakamisjärjestelmiä, jotka perustuvat Mignotte-järjestelmään. Esimerkkinä tässä on kaavio, joka on julkaistu Indianan yliopiston ja Purduen yliopiston yhteisessä työssä.

Oletetaan, että esitetty paino on , ja on käytettyjen numeroiden pituus bitteinä. Oletamme myös, että . On huomattava, että todellisissa järjestelmissä . $w$ $n$ $w<n$ $w\ll n$
Tässä tapauksessa valitsemme salaisuuden bittien pituudella (jos se on pienempi, täydennämme sitä esimerkiksi toistamalla salaisia bittejä tai lisäämällä satunnaisia bittejä ). $S$ $w*n$
Käyttäjälle , jolla on osuutensa paino , valitsemme bittipituisen alkuluvun ja sellaisen, että . Alkuluvut valitaan tässä tapauksessa algoritmin toiminnan yksinkertaistamiseksi, piirin oikeaan toimintaan riittää, että valitaan pareittain koprime-luvut. $U_{i}$ $p_{i}$ $P_{i}$ $p_{i}*n$ $p_{i}<w$
Lasketaan ja määritetään käyttäjän osuus muodossa . ${\displaystyle r_{i}=S\mod P_{i))$ $U_{i}$ $s_{i}=\{(r_{i},p_{i})\}$
Kun salaisuutta palautetaan, mikä tahansa käyttäjäryhmä on sellainen, että se voi muodostaa yhtälöjärjestelmän: $U_{i_{1}},U_{i_{2}},\dots ,U_{i_{l}}$ $p_{i_{1}}+p_{i_{2}}+\pisteet +p_{i_{l}}>w$

${\begin{cases}S\equiv r_{i_{1}}\mod P_{i_{1}}\\S\equiv r_{i_{2}}\mod P_{i_{2}}\ \\vdots \\S\equiv r_{i_{l}}\mod P_{i_{l}}\\\end{cases}}$ ja laske S käyttämällä Kiinan jäännöslausetta. Koska koko on bittiä, modulotuotteen koko koostuu vähintään :sta, voidaan nähdä, että vaikka . Tämä mahdollistaa salaisuuden laskemisen ainutlaatuisella tavalla. Osuuksien painojen summan ehtoa voidaan heikentää arvoon , niin jos pituus on vähintään , joten on tarpeen rajoittaa biteihin . Jos tämä ei ole mahdollista, voit tallentaa piirin ottamalla käyttöön lisäelementin, jonka moduuli on pienin alkuluku bittejä, elementin murto-osa on . Tätä elementtiä voidaan käyttää lisäyhtälönä yllä olevassa järjestelmässä, jolloin salaisuus voidaan palauttaa ainutlaatuisella tavalla. Tässä kaaviossa eliminoidaan yksi painotetun salaisuuden jakamisen tavanomaisen järjestelmän päähaitoista - mikä tahansa osuus voidaan kuvata pisteellä , eikä tällä pisteellä ole suhdetta oman painonsa ja koonsa välillä. $S$ $w*n$ ${\hat {P}}=P_{i_{1}}*P_{i_{2}}*\dots *P_{i_{n}}$ $(p_{i_{1}}+p_{i_{2}}+\pisteet +p_{i_{l}})*nl$ ${\hat {P}}>S$ $w<n$ $S$ $p_{i_{1}}+p_{i_{2}}+\pisteet +p_{i_{l}}\geqslant w$ $p_{i_{1}}+p_{i_{2}}+\pisteet +p_{i_{l}}=w$ ${\näyttötyyli {\hattu {P}}}$ $w*n-w+1$ $S$ $w*nw$ $H_{P}$ $w$ ${\displaystyle H_{s}=S\mod H_{P))$ $P_{i_{1}}*P_{i_{2}}*\dots *P_{i_{l}}*H_{P}>S$ $si}$ ${\näyttötyyli (r_{i}, P_{i})}$

Tätä mallia voidaan myös muokata toimimaan useiden salaisuuksien kanssa. Oletetaan, että sinun täytyy jakaa salaisuuksia , jokainen salaisuus koostuu palasista. Lisätään salaisuudet yhteen, jolloin saadaan yksi pieni salaisuus. Kolme tapausta on otettava huomioon: $S_{1},\pisteet ,S_{k}$ $n$ $k*n$

$k<w$ : Lisää satunnaisia bittejä kokoon asti $w*n$
$k=w$ : Älä tee mitään
$k>w$ : Otetaan käyttöön lisäelementti painolla [5] ${\näyttötyyli (kw)}$

Kaavion suorituskyky

Merkittävä osa piirin suoritusajasta kuluu Mignotte-sekvenssien ja koprime-moduulien generointiin. Oletetaan, että on osakkeita , joiden painot vastaavasti. Osakkeiden kokonaispaino on , salaisuuden paljastamiseen vaadittava paino - , numerobittien koko . ${\displaystyle s_{1},s_{2},\dots ,s_{N))$ ${\displaystyle p_{1},p_{2},\dots ,p_{N))$ $p_{1}+p_{2}+\dots +p_{N}=W$ $w$ $n$

Mignotte-sekvenssin luominen koostuu useista vaiheista:

Parittaisen koprimen luominen . Vallitseva operaatio on LCM :n löytäminen , sen monimutkaisuus on . Jokaiselle luodulle uudelle luvulle on tarpeen tarkistaa, onko se pareittain koprime jokaisen edellisen alkion kanssa, joten pareittain koprimelukujen muodostamiseksi monimutkaisuus on . $W$ $P_{1},\dots ,P_{W}$ $O(n^{2})$ $W$ $O(W^{2}n^{2})$
Niiden lajittelu, sen monimutkaisuus on . $O(Wlog(W)n)$
Kuntotarkastus . Kahden pituisten bittien ja bittien kertomisen monimutkaisuus on . Tarkistuksen monimutkaisuus on . ${\displaystyle \prod _{i=0}^{w-2}P_{Wi}<\prod _{j=1}^{w}P_{j))$ $l$ $v$ $O(lv)$ $O(w^{2}n^{2})$

Siten Mignotte-sekvenssin luomisen kokonaismonimutkaisuus on . $O(W^{2}n^{2})$

Moduulin luomiseksi painon omaavan käyttäjän on kerrottava koon numerot . Moduulien luomisen monimutkaisuus on . Siten moduulin luomisen kokonaismonimutkaisuus on myös . $p_{i}$ $p_{i}$ $n$ $N$ $O((p_{1}-2)n^{2}+(p_{2}-1)n^{2}+\pisteet +(p_{N}-1)n^{2}) =O((WN)n^{2})$ $O(W^{2}n^{2})$

Piirillä ei ole hyvää suorituskykyä, koska sitä on mahdollista muokata ja siten päästä eroon tarpeesta generoida Mignotte-sekvenssejä. Kaaviot esittävät Mignotte-skeemaan perustuvan järjestelmän suorituskyvyn analyysin tulokset salaisuuden ja itse järjestelmän painotetulla erolla. Graafin rakentamiseksi valittiin -kynnyskaavio, jossa oli yksi salaisuus, ja sen mukaisesti [5] . ${\näyttötyyli (4,15)}$ $p_{i}=1$ ${\hat {p}}=(1,2,3,\pisteet ,1,2,3)$

Kaavan haitat

Sillä ei ole kryptografista vahvuutta, koska jopa epätäydellinen joukko käyttäjiä voi tarjota tietoja salaisuudesta.
Se ei ole yksinkertainen periaatteessa tai toteutuksessa. Mignotte-sekvenssien ja kynnyspääsyrakenteiden luominen on vaikea ja resursseja vaativa prosessi.
Alueella, jolta voit valita salaisuuden, on rajoituksia: sen on oltava välillä ja . Tämän tosiasian tietäminen antaa myös lisätietoa hyökkääjälle. $S$ ${\displaystyle p_{1}*p_{2}*\dots *p_{k))$ ${\displaystyle p_{n-k+2}*\dots *p_{n))$
Hyvän kryptografisen vahvuuden takaamiseksi on välttämätöntä luoda suuria arvoja , mikä on myös resurssiintensiivistä tehtävää. ${\dfrac {\alpha -\beta }{\beta }}$
Hyökkääjä voi huijata järjestelmän käyttäjiä muuttamalla salaisuutta.

Tunkeilijoiden käyttäytymissuunnitelmat

Hyökkääjien käyttäytymistä kynnysjärjestelmissä kuvaavat kaksi mallia: CDV-malli, jossa hyökkääjät tietävät salaisuuden ja yrittävät lähettää vääriä tietoja muille osallistujille, ja OKS-malli, jossa hyökkääjät eivät tiedä salaisuutta. etukäteen. Tavallisessa Mignotte-mallissa yksi hyökkääjä voi aina pettää käyttäjiä CDV-mallissa ja suurella todennäköisyydellä OKS-mallissa. Oletetaan, että osallistujat jakavat salaisuuden ja käyttäjä päättää huijata. Siksi sen on muutettava varjonsa niin , että . Anna . Kiinan jäännöslauseen avulla saamme , eli esitämme sen muodossa . Koska Mignotte-sekvenssi tunnetaan, voimme löytää . Voit valita missä $k-1$ ${\displaystyle i_{1},i_{2},\dots ,i_{k))$ $i_1$ $I_{i_{1))$ $I_{i_{1}}^{\prime }$ $S^{\prime }\neq S,S\in (\beta ,\alpha )$ $l=p_{i_{2}}p_{i_{3}}\dots p_{i_{k}},r=p_{i_{1}}p_{i_{2}}\dots p_{i_ {k}}\Rightarrow S=pl+q,p\in \mathbf {Z} _{b_{1}},q\in \mathbf {Z} _{I}$ $S\mod l=S^{\prime }\mod l=q$ ${\displaystyle S^{\prime ))$ $p^{\prime }l+q$ ${\displaystyle p_{1},\dots ,p_{k))$ $l$ $p^{\prime }=p\pm 1$ $I_{i_{1}}^{\prime }=(I_{i_{1}}\pm l)\mod p_{i_{1}}\Rightarrow S^{\prime }=(p\pm 1)l+q=(S\pm l)\mod r$

CDV-mallissa hyökkääjä tietää salaisuuden, joten käyttämällä ilmaisua hän voi varmistaa, että (kuva 1) olemassaolo on taattu, jos osallistujat eivät pysty määrittämään salaisuutta. Siksi hyökkääjä voi huijata järjestelmän osallistujia todennäköisyydellä 1. Lisäksi tässä mallissa hyökkääjä voi hallita arvoa laskemalla suoraan : sta , jossa $S^{\prime }=(S\pm l)\mod r$ $S^{\prime }\in (\beta ,\alpha )$ ${\displaystyle S^{\prime ))$ $k-1$ ${\displaystyle S^{\prime ))$ $q$ $S$ $I_{i_{1}}^{\prime }=S^{\prime }\mod p_{i_{1}}$ $S^{\prime }=p^{\prime }l+q,p^{\prime }\in \mathbb {Z} _{\beta }:S^{\prime }\in (\beta ,\alpha )$

OKS-mallissa, koska hyökkääjä ei tiedä salaisuutta, hän ei voi tarkistaa epätasa-arvojen ja . Siinä tapauksessa hän voi aina käyttää . Ainoa vaihtoehto, jossa petos voidaan paljastaa, on mistä (Kuva 2) tai (Kuva 3). Siksi onnistuneen petoksen todennäköisyys on [7] $Sl<\beta$ $S+l>\alpha$ $I_{i_{1}}^{\prime }=(I_{i_{1}}+l)\mod p_{1}$ $S+l>\alpha$ $S^{\prime }=(S+l)\mod r<\beta$ $S^{\prime }=(S+l)\mod r>\alpha$ $1-{\frac {1}{[{\frac {\alpha -\beta }{l}}]}}$

Esimerkki

Anna . Sitten salaisuudelle luodaan varjot . Oletetaan, että jäsenet 1,2,3 ovat yhdistäneet panoksensa ja jäsen 1 haluaa huijata. Sitten hän laskee ja muuttaa osuutensa siten, että . Tässä tapauksessa yhtälöjärjestelmän ratkaisemisen jälkeen osallistujat palauttavat väärän salaisuuden , joka on myös välillä ja . Tämän avulla käyttäjä 1 voi saada todellisen salaisuuden: [7] $n=5,k=3,p_{1}=661,p_{2}=673,p_{3}=677,p_{4}=683,p_{5}=691\Rightarrow \alpha = 301165481,\beta =471953$ $S=500000$ $I_{1}=284,I_{2}=634,I_{3}=374,I_{4}=44,I_{5}=407$ $p_{2}*p_{3}=455621$ $I_{1}^{\prime }=(I_{1}+p_{2}p_{3})\mod p_{1}=476$ ${\begin{cases}x\equiv 476\mod 661\\x\equiv 634\mod 673\\x\equiv 374\mod 677\end{cases))$ $S^{\prime }=(S+p_{2}p_{3})\mod p_{1}p_{2}p_{3}=955621$ $\alpha$ $\beeta$ $S=(S^{\prime }-p_{2}p_{3})\mod p_{1}p_{2}p_{3}=500000$

Kaavion muutokset

Voit välttää tällaisen petoksen seuraavasti:

Esittelemme jälleenmyyjän, joka luo -Mignotte-sekvenssin . Myös jakaja generoi erilaisia alkulukuja , jotka ovat riittävän suuria. Salaisuus valitaan siten, että . Osakkeet ovat . Salainen palautusprosessi on sama kuin tavallisessa Mignotte-järjestelmässä. Kun salaisuus on palautettu, kuka tahansa osallistuja voi määrittää petoksen vertaamalla jakajan toimittamiin tietoihin. Siten hyökkääjä voi pettää osallistujan todennäköisyydellä [7] $(k,n)$ ${\displaystyle p_{1},p_{2},\dots ,p_{n))$ $n$ $m_{1},\dots ,m_{n}$ ${\frac {\alpha -\beta }{\beta \max _{1\leqslant i_{1}<\dots <i_{k-1}\leqslant n}(m_{i_{1))* \dots *m_{i_{k-1}})}}$ $S$ $\beta <S<\alpha$ $I_i$ $(S\mod p_{i},S\mod m_{i}p_{i},m_{i})$ ${\displaystyle S^{\prime ))$ $i$ ${\displaystyle S^{\prime }\mod m_{i))$ $j$ ${\displaystyle {\frac {1}{m_{j))))$

Muistiinpanot

↑ 1 2 3 4 Maurice Mignotte, 1983, s. 371-375
↑ Yleinen salainen jakaminen perustuu kiinalaiseen jäännöslauseeseen (englanniksi) (linkki ei ole käytettävissä) . Elektroniset muistiinpanot tietojenkäsittelyteoriassa (2007). Haettu 18. marraskuuta 2013. Arkistoitu alkuperäisestä 3. joulukuuta 2013.
↑ Evangelos Kranakis, 1986, s. 9
↑ Yleistys Mignotten salaisesta jakamisjärjestelmästä (eng.) (downlink) . Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2004). Käyttöpäivä: 12. joulukuuta 2013. Arkistoitu alkuperäisestä 3. joulukuuta 2013.
↑ 1 2 3 Uusi lähestymistapa painotettuun monisalaiseen jakamiseen (englanniksi) (linkki ei ole käytettävissä) . Elektroniset muistiinpanot tietojenkäsittelyteoriassa (2011). Haettu 18. marraskuuta 2013. Arkistoitu alkuperäisestä 19. joulukuuta 2012.
↑ CA Asmuth ja J. Bloom, 1986, s. 208-210
↑ 1 2 3 Huijaamisen havaitseminen ja huijarin tunnistaminen CRT-pohjaisissa salaisissa jakamisjärjestelmissä . Al. I. Cuza” University Iasi, Romania (2009). Haettu 18. marraskuuta 2013. Arkistoitu alkuperäisestä 10. toukokuuta 2012.

Kirjallisuus

M. mignotte . Kuinka jakaa salaisuus (englanniksi) // Tietojenkäsittelytieteen luentomuistiinpanot. - 1983. - Voi. 149 . - s. 371-375 . - doi : 10.1007/3-540-39466-4_27 . (linkki ei saatavilla)
E. Kranakis . Primality and Cryptography (englanti) // Wiley-Teubner-sarja tietojenkäsittelytieteessä. - 1986. - Voi. 1 . — s. 9 .
C. A. Asmuth ja J. Bloom . Modulaarinen lähestymistapa avainten turvaamiseen // IEEE Transactions on Information Theory. - 1986. - Voi. 2 . — s. 208-210 .

Linkit

Yleinen salainen jakaminen perustuu kiinalaiseen jäännöslauseeseen (englanniksi) (downlink) . Elektroniset muistiinpanot tietojenkäsittelyteoriassa (2007). Käyttöpäivä: 12. joulukuuta 2013. Arkistoitu alkuperäisestä 3. joulukuuta 2013.
Uusi lähestymistapa painotettuun monisalaiseen jakamiseen (englanniksi) (linkki ei ole käytettävissä) . Elektroniset muistiinpanot tietojenkäsittelyteoriassa (2011). Käyttöpäivä: 12. joulukuuta 2013. Arkistoitu alkuperäisestä 19. joulukuuta 2012.
Huijaamisen havaitseminen ja huijarin tunnistaminen CRT-pohjaisissa salaisissa jakamisjärjestelmissä . Al. I. Cuza” University Iasi, Romania (2009). Haettu: 12. joulukuuta 2013.
Yleistys Mignotten salaisesta jakamisjärjestelmästä (eng.) (downlink) . Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2004). Käyttöpäivä: 12. joulukuuta 2013. Arkistoitu alkuperäisestä 3. joulukuuta 2013.