Puncte:2

De ce trebuie să modificăm algoritmul Shamir's Secret Sharing

drapel kr

Mă uit la algoritmul de partajare secretă al lui Shamir și îmi este clar cum funcționează, dar nu înțeleg motivul exact pentru care trebuie să găsim un număr prim și să facem aritmetică modulo folosind acel prim.

Pe Wikipedia, se spune că dacă nu folosiți aritmetica modulo, un atacator ar putea obține informații despre valoare fără a avea suficiente acțiuni.

În Joy of Cryptography, pare să justifice necesitatea aritmeticii modulo spunând că coeficienții polinomi trebuie să fie distribuiți uniform în Z, ceea ce nu este fezabil, așa că în schimb folosim Z_p unde o distribuție uniformă este realizabilă.

Pe alte site-uri web (și aici), am văzut unii oameni spunând că modulo era pur și simplu necesar pentru ca valorile să nu devină prea mari.

Pe scurt, nu am putut găsi un motiv definitiv pentru care aritmetica modulară este cu adevărat necesară. Desigur, ar putea fi o combinație a tuturor motivelor menționate mai sus, dar pentru mine este ciudat să văd că toate aceste surse oferă o justificare diferită fără a menționa celelalte motive. Așa că mă poți ajuta să-mi dau seama De ce chiar e nevoie de asta?

kelalaka avatar
drapel in
Un alt [Necesitatea aritmeticii câmpurilor finite și a numărului prim p în Schema de partajare secretă a lui Shamir](https://crypto.stackexchange.com/q/5502/18298)
drapel kr
Da, ambele răspunsuri ajută, mulțumesc mult! Bănuiesc că căutarea cuvântului cheie `mod` a fost greșită și ar fi trebuit să caut un câmp finit. Mulțumesc mult!
Puncte:0
drapel se

Ambele explicații pe care le-ați spus sunt de fapt două fețe ale aceleiași monede.

Cum ați eșantiona un element uniform aleatoriu din $\mathbb{Z}$? Acesta este un set infinit. Chiar dacă ai putea, nu este clar de câți octeți de memorie ai avea nevoie pentru a reprezenta acest „întreg” aleatoriu?

Astfel, trebuie să eșantionăm coeficienți dintr-un set finit de elemente (care pot fi reprezentați în număr fix de octeți). Cu toate acestea, nu toate mulțimile finite vă vor permite să interpolați polinoamele peste. Astfel, trebuie să alegem o mulțime finită cu care funcționează un algoritm de interpolare polinomială cunoscut. Interpolarea Lagrange se întâmplă să funcționeze câmpuri finite (de exemplu.polinoame cu coeficienți într-un câmp finit). Cel mai canonic exemplu de câmp finit sunt numerele întregi mod un număr prim. Aceasta este cea mai simplă reprezentare conceptuală, așa că multe texte vor folosi acest exemplu.

Daniel avatar
drapel ru
Merită remarcat faptul că interpolarea funcționează peste inele finite arbitrare (nu numai câmpuri finite) atâta timp cât au puncte de evaluare $\alpha_0,\ldots,\alpha_n$ astfel încât fiecare diferență diferită de zero este inversabilă. https://crypto.stackexchange.com/questions/48928/shamir-secret-sharing-p-not-prime/96507#96507

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.