înregistrare Logare
Puncte:1
hambam avatar Crypto

Complexitatea temporală a unui atac cu forță brută asupra SSS Secret Sharing a lui Shamir

drapel in
hambam

Am căutat peste tot în lucrările academice despre complexitatea timpului a unui atac cu forță brută asupra unei chei Shamir's Secret Sharing. Sunt confuz între dacă este $O(p^k)$ sau $O(p)$, astfel încât $p$ este modulo de criptare și $k-1$ este gradul polinomului de criptare. Pentru că practic, dacă vom reconstrui polinomul de criptare, este echivalent cu forțarea brută a tuturor $p$ valori posibile pentru $k$ coeficienți, ceea ce duce la an $O(p^k)$ algoritm. Dar căutând direct secretul care este coeficientul constant al polinomului și știind asta $S<p$, duce la o $O(p)$ algoritm. Poate cineva să-mi spună, vă rog, care este cea potrivită și dacă este $O(p^k)$, de ce nu funcționează algoritmul liniar?

127
1 + 0
Puncte:3
poncho avatar Crypto
drapel my
poncho

Am căutat peste tot în lucrările academice despre complexitatea timpului a unui atac cu forță brută asupra unei chei Shamir's Secret Sharing.

Un atac cu forță brută nu este posibil; chiar dacă ai putea efectua orice calcul arbitrar, cu $k-1$ acțiuni, tot nu ați obține informații despre secret (presupunând că a fost folosită aleatorie pentru a genera acțiuni; dacă acestea ar fi generate printr-un generator de numere aleatoare deterministe, ați putea).

Pentru că practic, dacă vom reconstrui polinomul de criptare, este echivalent cu forțarea brută a tuturor $p$ valori posibile pentru $k$ coeficienți, ceea ce duce la an $O(p^k)$ algoritm.

Nu, chiar și asta nu funcționează, pentru că nu există nicio modalitate de a determina dacă ați găsit polinomul corect; pentru orice valoare posibilă a secretului, există un număr egal de polinoame care sunt în concordanță cu acesta. Prin urmare, nu obțineți nicio informație (chiar și informații probabilistice) despre secret.

0 + 5
hambam avatar
drapel in
hambam
multumesc pentru raspunsul rapid! dar am găsit aici [link] (https://www.ijcaonline.org/archives/volume155/number13/kannan-2016-ijca-912051.pdf) că *Valoarea lui p nu ar trebui să fie prea mică sau ar putea fi susceptibilă la atacul cu forța brută. Dacă valoarea lui p este de 128 de biți, aceasta oferă 2^128 de valori posibile, ceea ce este un interval prea mare pentru ca forța brută să o încerce vreodată*. Ce înseamnă atunci?
0
Răspunde
Aman Grewal avatar
drapel gb
Aman Grewal
Dacă există o modalitate de a verifica secretul, acesta poate fi forțat, dar asta nu atacă cu adevărat SSS.
1
Răspunde
hambam avatar
drapel in
hambam
@AmanGrewal, deci asta înseamnă că atacarea SSS este echivalentă cu reconstruirea polinomului folosit în criptare și nu numai cu regăsirea secretului?
0
Răspunde
poncho avatar
drapel my
poncho
@HamzaBa-mohammed: acel comentariu pe care l-ai găsit este greșit
1
Răspunde
poncho avatar
drapel my
poncho
@AmanGrewal: „dacă există o modalitate de a verifica secretul”; Ei bine, da, dacă poți căuta prin toate valorile secrete posibile și poți detecta care este cea potrivită, da, poți să o înveți. Cu toate acestea, nu utilizați acțiunile; nu vă oferă nicio informație pe care să nu le aveți deja
3
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

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.