Mignotte-schema

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 juni 2016; kontroller kräver 9 redigeringar .

Mignotte-schemat är ett hemligt delningssystem för tröskelvärden byggt med primtal . Låter dig dela upp hemligheten (numret) mellan parterna på ett sådant sätt att alla deltagare kan återställa den, men deltagarna kommer inte att kunna återställa hemligheten. Schemat är baserat på den kinesiska restsatsen . $n$ $k$ $k-1$

Historik

Systemet föreslogs första gången 1982 av den franske vetenskapsmannen Maurice Mignotte som ett av alternativen för att använda tröskelsystemet som beskrevs av Adi Shamir . Shamir själv föreslog en lösning med polynominterpolation på ett ändligt fält, där hemligheten var själva polynomet. Mignotte, å andra sidan, kunde erbjuda en enklare lösning, baserad på ett modulärt tillvägagångssätt - ett visst nummer är en hemlighet, och dess rest modulo ett visst nummer är en partiell hemlighet. Mignottes modifierade schema är Asmuth-Bloom-schemat . I båda scheman används den kinesiska restsatsen för att återställa hemligheten, vars formulering definierar en unik lösning (hemlighet) [1] . $(k,n)$

Hemligt delningsschema

Kinesisk restsats

Schemat är baserat på användningen av den kinesiska restsatsen, som tillåter användare som har en del av hemligheten att återställa hemligheten själv, och det på ett unikt sätt. Det finns flera versioner av satsen, låt oss kalla följande generella: Låt . Sedan ekvationssystemet $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))$ har lösningar i if and only if . Dessutom, om det reducerade systemet har lösningar i , har det en unik lösning i bestämmer den minsta gemensamma multipeln av . Om , den kinesiska restsatsen kallas standard [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$

Tröskelhemliga delningsscheman

Anta att det finns n användare , numrerade från till , och en uppsättning grupper , där alla undergrupper av gruppen finns . Faktum är att ett hemligt delningsschema är en metod för att generera hemligheter så att: $ett$ $n$ ${\mathcal {A}}\subseteq P({1,2,\dots ,n})$ $P({1,2,\dots,n})$ $\{1,2,\dots,n\}$ ${\mathcal {A}}$ $(S,(I_{1},\dots ,I_{n}))$

(riktighet) För alla är problemet med att hitta i allas närvaro "enkelt" $A\in {\mathcal {A}}$ $S$ $jag$
(säkerhet) För alla , problemet med att hitta är "oberoligt" $A\in P({1,2,\dots ,n})\setminus {\mathcal {A}}$ $S$

$\mathcal{A}$ vi kommer att kalla åtkomststrukturen - en hemlighet och - skuggor . Låt oss anropa uppsättningar av element från behörighetsgrupper . I ett idealiskt schema för hemlighetsdelning ger skuggan av en grupp som inte är en behörighetsgrupp ingen information (i termer av informationsteori) om hemligheten. Det har bevisats att i alla idealiska hemlighetsdelningsscheman bör storleken på var och en av skuggorna inte vara mindre än storleken på själva hemligheten. Den naturliga förutsättningen är att tillträdesstrukturen ska vara monoton, det vill säga: . Alla åtkomststrukturer är väl beskrivna med den minsta uppsättningen av behörighetsgrupper: . Du kan också beskriva en åtkomststruktur som inte har behörighetsegenskaper: . Det beskrivs väl av den maximala uppsättningen "icke-auktorisering"-grupper: $S$ $I_{1},\dots ,I_{n}$ $S$ $A$ $\mathcal{A}$ $(\forall B\in P(\{1,2,\dots,n\}))((\finns A\i {\mathcal {A)))(A\subseteq B)\Högerpil B\ i {\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)\}$

I de första hemliga delningssystemen var endast antalet deltagare viktigt för att återställa hemligheten. Sådana system har kallats tröskelhemlighetsdelningssystem. Låt , då kallas åtkomststrukturen -threshold åtkomststruktur. $n\geqslant 2,2\leqslant k\leqslant n$ ${\mathcal {A}}=\{A\in P({1,2,\dots ,n})\mid |A|\geqslant k\}$ $(k,n)$

Det är också värt att tänka på att för strukturer för -tröskelåtkomst: $(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\}$ .

Alla -hemliga-delningsscheman kommer också att kallas -threshold secret-sharing-scheman [1] . $A$ $(k,n)$

Mignotte-sekvens

Mignottes hemliga delningsschema för tröskelvärden använder speciella nummersekvenser som kallas Mignotte-sekvenser. Låta vara ett heltal, , och . -Mignottesekvens är en sekvens av coprime - positiva sådana att det sista påståendet också motsvarar följande: [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}})$

Algoritm

Med tanke på den offentliga Mignotte-nyckeln fungerar schemat så här:

Hemligheten väljs som ett slumpmässigt tal så att , där . Med andra ord måste hemligheten ligga mellan och $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))$
Aktier beräknas som , för alla $I_{i}=S\mod p_{i}$ $1 \leqslant i \leqslant n$
Med olika skuggor kan du få hemligheten med standardversionen av den kinesiska restsatsen - det kommer att vara den enda lösningen modulo systemet: $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}}$ Hemligheten är lösningen av ovanstående system, dessutom ligger inom , eftersom . Å andra sidan, med bara olika skuggor , kan vi säga att , var är den enda lösningen modulo det ursprungliga systemet (i detta fall: . [1] För att erhålla en acceptabel säkerhetsnivå, Mignotte-sekvenser med ett stort värde [ 3 ] Uppenbarligen har Mignotte-schemat ingen betydande kryptografisk styrka , men det kan vara användbart i applikationer där skuggornas kompakthet är en avgörande faktor. $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 }}$

Exempel

Låt oss säga att du vill dela en hemlighet mellan användare så att vem som helst kan återställa den. $n=6$ $k=5$

Vi väljer Minotte-sekvensen . $p_{1}=5,p_{2}=7,p_{3}=11,p_{4}=13,p_{5}=17,p_{6}=19$
Beräkna för denna sekvens , . $\alpha =p_{1}*p_{2}*p_{3}*p_{4}*p_{5}=85085$ $\beta =p_{3}*p_{4}*p_{5}*p_{6}=46189$
Vi väljer sådana att t.ex. $S$ $\beta <S<\alpha$ $S=50000$
Vi beräknar andelarna : $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$
För att återställa hemligheten löser vi ekvationssystemet för skuggorna (antag att hemligheten återställs av deltagare 1-5): $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}}$ .

Från formuleringen av den kinesiska restsatsen vet vi att lösningen kommer att vara unik.

Ändringar av Mignotte-schemat

Generaliserad Mignotte-sekvens

För ett givet tröskelschema är elementen i sekvensen inte nödvändigtvis coprime. Låta vara ett heltal, . En generaliserad Mignotte-sekvens är en sekvens av positiva heltal så att . Det är lätt att se att vilken Mignotte-sekvens som helst är en generaliserad Mignotte-sekvens. Dessutom, om vi multiplicerar varje element i den generaliserade sekvensen med ett fast element , får vi också en generaliserad Mignotte -sekvens. Det utökade Mignotte-schemat fungerar på samma sätt som det vanliga för och . I det här fallet, för att hitta hemligheten, är det nödvändigt att använda en generaliserad version av den kinesiska restsatsen. [fyra] $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- ett}}])$

Viktad hemlighetsdelning

Systemet kan också tillämpas för att implementera ett viktat hemlighetsdelningssystem. I jämviktsscheman, som är det klassiska Mignotte-schemat, får varje deltagare en skugga av samma värde. Schemat kan dock modifieras så att deltagare med högre skuggvikt kräver färre andra skuggor än deltagare med lägre skuggvikt.

Låt vara hemligheten, var är vikten av användarens skuggor. Låt oss skapa en Mignotte-sekvens, där . Sedan , var är en godtycklig partition av uppsättningen så att $S(k,n,N,P)$ $P=(p_{1},\dots ,p_{N})$ $(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$

Du kan se att det finns en en-till-en-överensstämmelse mellan skuggans storlek och vikt: till exempel, en bit är en skugga med vikten 1, en skugga med en vikt väger bitar. Implementeringen av Mignotte-schemat med en viktad hemlighetsdelning är inte lämplig, eftersom genereringen av Mignotte-sekvensen och den viktade åtkomsttröskelstrukturen är en arbets- och resurskrävande uppgift. Det finns enklare och effektivare vägda hemlighetsdelningssystem som också tar bort beroendet mellan skuggvikt och storlek. [5] $pi}$ $p_{i}*n$

Liknande scheman

Asmuth-Bloom-schemat [6] , också baserat på den kinesiska restsatsen, introducerades först 1983. Huvudskillnaden är att istället för att Mignotte-sekvensen kräver generering, är det nödvändigt att välja ett primtal, en sekvens av samprimtal som är associerade med den, såväl som något slumpmässigt tal som hemligheten krypteras med, och skuggor beräknas baserat på den krypterade hemligheten. Asmuth-Bloom-schemat saknar några av de nackdelar som är inneboende i Mignotte-schemat: $n$

Det finns ingen gräns för området där du kan välja en hemlighet
En uppsättning mindre än användarskuggor ger ingen information om hemligheten $k$

Det finns flera viktade hemliga delningsscheman baserade på Mignotte-schemat. Som ett exempel, här är ett diagram publicerat i ett gemensamt arbete av Indiana University och Purdue University.

Vi antar att den avslöjade vikten är , och är längden på de använda talen i bitar. Det antar vi också . Det bör noteras att i verkliga system . $w$ $n$ $w<n$ $w\ll n$
I det här fallet väljer vi hemligheten med bitarnas längd (om den är mindre kompletterar vi den, till exempel genom att upprepa de hemliga bitarna eller lägga till slumpmässiga bitar ). $S$ $w*n$
För en användare med en vikt av hans andel väljer vi ett primtal av bitlängd och sådant . Primtal väljs i detta fall för att förenkla driften av algoritmen; för korrekt funktion av kretsen är det tillräckligt att välja parvisa samprimtal. $U_{i}$ $pi}$ $Pi}$ $p_{i}*n$ $p_{i}<w$
Låt oss beräkna och definiera användarens andel som . ${\displaystyle r_{i}=S\mod P_{i))$ $U_{i}$ $s_{i}=\{(r_{i},p_{i})\}$
När du återställer en hemlighet är vilken grupp användare som helst sådan att den kan bilda ett ekvationssystem: $U_{i_{1}},U_{i_{2}},\dots ,U_{i_{l}}$ $p_{i_{1}}+p_{i_{2}}+\dots +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}}$ och beräkna S genom att tillämpa den kinesiska restsatsen. Eftersom storleken är bitar, består storleken av modulo-produkten av åtminstone , det kan ses att medan . Det är detta som gör det möjligt att beräkna hemligheten på ett unikt sätt. Det är möjligt att försvaga villkoret för summan av vikter av aktier till , då om längden är minst , så är det nödvändigt att begränsa till bitar. Om detta inte är möjligt kan du spara kretsen genom att införa ett extra element, vars modul är det minsta primtal av bitar, andelen av elementet är . Detta element kan användas som en extra ekvation i ovanstående system, i vilket fall , så hemligheten kan återställas på ett unikt sätt. I detta schema elimineras en av de största nackdelarna med det vanliga schemat med uppdelningen av en viktad hemlighet - vilken andel som helst kan beskrivas med en punkt , och denna punkt har inget samband mellan sin egen vikt och storlek. $S$ $w*n$ ${\hat {P}}=P_{i_{1}}*P_{i_{2}}*\dots *P_{i_{n}}$ $(p_{i_{1}}+p_{i_{2}}+\dots +p_{i_{l}})*nl$ ${\hat {P}}>S$ $w<n$ $S$ $p_{i_{1}}+p_{i_{2}}+\dots +p_{i_{l}}\geqslant w$ $p_{i_{1}}+p_{i_{2}}+\dots +p_{i_{l}}=w$ ${\hat {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}$ $(r_{i},P_{i})$

Detta schema kan också modifieras för att fungera med flera hemligheter. Låt oss säga att du behöver dela hemligheter , varje hemlighet består av bitar. Låt oss lägga ihop hemligheterna och få en bitlångt hemlighet. Tre fall måste övervägas: $S_{1},\dots ,S_{k}$ $n$ $k*n$

$k<w$ : Lägg till slumpmässiga bitar, upp till storlek $w*n$
$k=w$ : göra ingenting
$k>w$ : Låt oss introducera ytterligare ett element med vikt [5] $(kw)$

Schema prestanda

En betydande del av kretsexekveringstiden tas av genereringen av Mignotte-sekvenser och coprime-moduler. Anta att det finns andelar med respektive vikter . Den totala vikten av andelarna kommer att vara , vikten som krävs för att avslöja hemligheten - , storleken på antalet - bitar. ${\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$

Genereringen av Mignonte-sekvensen består av flera steg:

Generering av parvis coprime . Den dominerande operationen är att hitta LCM , dess komplexitet är . För varje nytt tal som genereras är det nödvändigt att kontrollera om det är parvis coprime med vart och ett av de föregående elementen, så för att generera parvis coprime-tal är komplexiteten . $W$ $P_{1},\dots ,P_{W}$ $O(n^{2})$ $W$ $O(W^{2}n^{2})$
Deras sortering, dess komplexitet är . $O(Wlog(W)n)$
Tillståndskontroll . Komplexiteten i att multiplicera två antal längdbitar och bitar är . Verifieringens komplexitet kommer att vara . ${\displaystyle \prod _{i=0}^{w-2}P_{Wi}<\prod _{j=1}^{w}P_{j))$ $l$ $v$ $O(lv)$ $O(w^{2}n^{2})$

Således är den totala komplexiteten för att generera Mignonte-sekvensen . $O(W^{2}n^{2})$

För att generera en modul måste användaren med vikt multiplicera antalet storlek . Komplexiteten i att generera moduler kommer att vara . Således är den totala komplexiteten för modulgenerering också . $pi}$ $pi}$ $n$ $N$ $O((p_{1}-2)n^{2}+(p_{2}-1)n^{2}+\dots +(p_{N}-1)n^{2}) =O((WN)n^{2})$ $O(W^{2}n^{2})$

Kretsen har inte bra prestanda, eftersom det är möjligt att modifiera den och därigenom bli av med behovet av att generera Mignotte-sekvenser. Graferna visar resultaten av analysen av prestandan för ett schema baserat på Mignotte-schemat med en viktad separation av hemligheten och själva schemat. För att bygga en graf valdes ett -tröskelschema med en hemlighet, och följaktligen [5] . $(4,15)$ $p_{i}=1$ ${\hat {p}}=(1,2,3,\dots ,1,2,3)$

Nackdelar med schemat

Har inte kryptografisk styrka, eftersom även en ofullständig uppsättning användare kan ge viss information om hemligheten.
Det är inte enkelt i princip eller i genomförandet. Genereringen av Mignotte-sekvenser och tröskelåtkomststrukturer är en svår och resurskrävande process.
Det finns en begränsning för intervallet där du kan välja en hemlighet: den måste vara mellan och . Att känna till detta ger också ytterligare information till angriparen. $S$ ${\displaystyle p_{1}*p_{2}*\dots *p_{k))$ ${\displaystyle p_{n-k+2}*\dots *p_{n))$
För att säkerställa god kryptografisk styrka är det nödvändigt att generera stora värden , vilket också är en resurskrävande uppgift. ${\dfrac {\alpha -\beta }{\beta }}$
En angripare kan lura användare av systemet genom att ändra hemligheten.

Beteendescheman för inkräktare

Det finns två scheman som beskriver beteendet hos angripare i tröskelscheman: CDV-modellen, där angriparna känner till hemligheten och försöker skicka falska data till andra deltagare, och OKS-modellen, där angriparna inte känner till hemligheten i förskott. I det vanliga Mignotte-schemat kan en angripare alltid lura användare i CDV-modellen och med hög sannolikhet i OKS-modellen. Låt oss säga att deltagarna delar en hemlighet och användaren bestämmer sig för att fuska. Därför måste den ändra sin skugga till så att . Låt . Med den kinesiska restsatsen får vi , det vill säga vi representerar det som . Eftersom Mignotte-sekvensen är känd kan vi hitta . Du kan välja var $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$

I CDV-modellen känner angriparen till hemligheten, så med hjälp av uttrycket kan han försäkra sig om att (fig. 1) existens är garanterad om deltagarna inte kan fastställa hemligheten. Därför kan angriparen lura deltagarna i schemat med sannolikhet 1. Dessutom kan angriparen i denna modell kontrollera värdet av genom att beräkna direkt från : , där $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 )$

I OKS-modellen, eftersom angriparen inte känner till hemligheten, kan han inte kontrollera sanningen om ojämlikheterna och . I så fall kan han alltid använda . Det enda alternativet där bedrägeri kan avslöjas är varifrån (fig. 2) eller (fig. 3). Därför är sannolikheten för framgångsrikt bedrägeri [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}}]}}$

Exempel

Låt . Sedan kommer skuggor att genereras för hemligheten . Låt oss säga att medlemmar 1,2,3 slog ihop sina insatser och medlem 1 vill fuska. Sedan räknar han ut och ändrar sin andel så att . I det här fallet, efter att ha löst ekvationssystemet, kommer deltagarna att återställa fel hemlighet , som också är mellan och . Med detta kan användare 1 få den verkliga hemligheten: [7] $n=5,k=3,p_{1}=661,p_{2}=673,p_{3}=677,p_{4}=683,p_{5}=691\Högerpil \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$ $\alfa$ $\beta$ $S=(S^{\prime }-p_{2}p_{3})\mod p_{1}p_{2}p_{3}=500000$

Schema ändringar

För att undvika sådana bedrägerier kan du göra följande:

En återförsäljare introduceras som genererar en -Mignotte-sekvens . Även dealern genererar olika primtal så att: är tillräckligt stor. Hemligheten är vald så att . Aktierna är . Den hemliga återställningsprocessen är densamma som i standard Mignotte-schemat. Efter att hemligheten har återställts kan vilken deltagare som helst fastställa bedrägeriet genom att jämföra med data som överförts av återförsäljaren. Således kan en angripare lura en deltagare med en sannolikhet [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))))$

Anteckningar

↑ 1 2 3 4 Maurice Mignotte, 1983, s. 371-375
↑ Allmän hemlighetsdelning Baserat på den kinesiska restsatsen (engelska) (länk ej tillgänglig) . Electronic Notes in Theoretical Computer Science (2007). Hämtad 18 november 2013. Arkiverad från originalet 3 december 2013.
↑ Evangelos Kranakis, 1986, sid. 9
↑ En generalisering av Mignottes hemliga delningsschema (eng.) (nedlänk) . Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2004). Datum för åtkomst: 12 december 2013. Arkiverad från originalet 3 december 2013.
↑ 1 2 3 Ett nytt tillvägagångssätt för viktad multi-hemlig delning (engelska) (länk ej tillgänglig) . Electronic Notes in Theoretical Computer Science (2011). Hämtad 18 november 2013. Arkiverad från originalet 19 december 2012.
↑ CA Asmuth och J. Bloom, 1986, sid. 208-210
↑ 1 2 3 Fuskupptäckt och fuskidentifiering i CRT-baserade hemliga delningsscheman . Al. I. Cuza” University Iasi, Rumänien (2009). Hämtad 18 november 2013. Arkiverad från originalet 10 maj 2012.

Litteratur

M. mignotte . Hur man delar en hemlighet (engelska) // Föreläsningsanteckningar i datavetenskap. - 1983. - Vol. 149 . - s. 371-375 . - doi : 10.1007/3-540-39466-4_27 . (inte tillgänglig länk)
E. Kranakis . Primalitet och kryptografi (engelska) // Wiley-Teubner-serien i datavetenskap. - 1986. - Vol. 1 . — S. 9 .
C.A. Asmuth och J. Bloom . En modulär strategi för nyckelskydd // IEEE Transactions on Information Theory. - 1986. - Vol. 2 . — S. 208-210 .

Länkar

Allmän hemlighetsdelning Baserat på den kinesiska restsatsen (engelska) (nedlänk) . Electronic Notes in Theoretical Computer Science (2007). Datum för åtkomst: 12 december 2013. Arkiverad från originalet 3 december 2013.
Ett nytt tillvägagångssätt för viktad multi-hemlig delning (engelska) (länk ej tillgänglig) . Electronic Notes in Theoretical Computer Science (2011). Datum för åtkomst: 12 december 2013. Arkiverad från originalet 19 december 2012.
Fuskupptäckt och fuskidentifiering i CRT-baserade hemliga delningsscheman . Al. I. Cuza” University Iasi, Rumänien (2009). Hämtad: 12 december 2013.
En generalisering av Mignottes hemliga delningsschema (eng.) (nedlänk) . Proceedings of the 6th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (2004). Datum för åtkomst: 12 december 2013. Arkiverad från originalet 3 december 2013.