înregistrare Logare
Puncte:2
J. Doe avatar Crypto

Există metode criptografice $f,g,h$ cu $f(g(h(x)))=h(g(f(x)))=g(h(f(x)))$ și găsirea $ x$ pentru $c=f^ig^jh^k(x)$ dat mai greu decât $O(i+j+k)$?

drapel at
J. Doe

Există metode criptografice $f,g,h$ care poate fi aplicat în orice ordine unei intrări $x$ rezultând în același timp același rezultat $r$: $$f(g(h(x)))=h(g(f(x)))=ghf(x)=fhg(x)=hfg(x)=gfh(x) = r$$ Același lucru pentru funcția lor inversă: $$f^{-1}(g^{-1}(h^{-1}(r)))=h^{-1}(g^{-1}(f^{-1}(r) )))=g^{-1}(h^{-1}(f^{-1}(r)))) =...= x$$ Dacă acum $f,g,h,$ este aplicat $i,j,k$-de ori la o intrare $x$ găsirea/calcularea $x$ pentru dat $c$ $$c=f^i(g^j(h^k(x)))$$ ar trebui să fie cât mai greu posibil și cu aceasta luând mai mult decât $O(|i|+|j|+|k|)$ trepte.
Tehnica de calcul $f,g,h$ iar inversele lor trebuie să dureze un timp similar pentru fiecare intrare (independent de $i,j,k$).

În plus $f,g,h$ produce un ciclu ca $f(f(....f(x)...)) = x$ cu dimensiunea $F,G,H$ cu $F\aprox G \aprox H \gg 1$

Și întâmplător $x$ poate fi generat fără cunoașterea parametrului secret din $f,g,h$.

Țintă: Se dau două aleatorii $x_1,x_2$ cu $x_2=f^ig^jh^k(x_1)$ calcularea/găsirea $i,j,k$ ar trebui să fie cât mai greu posibil în timp ce numărul de diferite $x$ ar trebui să fie cât mai mic posibil.
Nu de preferat, dar unele combinații de $x_1,x_2$ poate să nu aibă niciunul $i,j,k$

107
0 + 0
kodlu avatar
drapel sa
kodlu
va trebui să motivați și să despachetați această supă cu alfabet dacă doriți ca cineva să se uite serios la asta. în primul rând, de ce alegi compozițiile în ordinea pe care o faci? sunt 3! compoziții posibile și alegeți 3 dintre ele. cum sunt motivate/relatate proprietățile inverse. în cele din urmă, spui O(i+j+k). Să presupunem că considerați constantă complexitatea f și a inversului (f) etc. Vă rugăm să editați întrebarea direct în loc să răspundeți în comentarii.
0
Răspunde
Puncte:3
Daniel S avatar Crypto
drapel ru
Daniel S

Lăsa $N$ să fie produsul a două numere prime mari și puternice, adică $N=pq$, $p=2r+1$, $q=2s+1$ cu $p$, $q$, $r$ și $s$ toate prime. De asemenea, avem nevoie de 3 numere care sunt rădăcini primitive pentru ambele $r$ și $s$ (date rădăcini primitive mod $r$ anunț $s$ putem face acest lucru cu teorema chineză a restului). Vom considera aceste trei numere ca fiind 3, 5 și 7 de mai jos. Presupunem că $N$ este greu de factorizat și de rezolvat logaritmi discreti modulo $N$ este si greu.

Lăsa $x$ fie orice pătrat în $\mathbb Z/N\mathbb Z$ (de exemplu, alegeți un element aleatoriu și pătrați-l). Acum lasa $f(x)=x^3\mod N$, $g(x)=x^5\mod N$ și $h(x)=x^7\mod N$. Notă $f(g(h(x)))=x^{105}\mod N$ si la fel pentru celelalte comenzi. Există o relație similară a inverselor (deși calculul inversului este la fel de greu ca decriptarea RSA).

Calcul rapid al $f^ig^jh^k(x)$ ne-ar permite să facem un pas gigant de criptare RSA, despre care se crede că este greu dacă nu cunoaștem factorii $N$.

Aplicații repetate în sfârșit $f$, $g$ și $h$ produce un ciclu de lungime $\mathrm{lcm}((r-1),(s-1))$ dacă nu $x$ este fie a $r$al sau $s$modulo de putere $N$ (ceea ce este puțin probabil să dispară).

0 + 0
J. Doe avatar
drapel at
J. Doe
Arata interesant. Voi face niște teste/mă gândesc la asta înainte de a-l marca ca răspuns. De exemplu. inversul este unic? de exemplu. rădăcină pătrată de $5 \mod 11$ ar putea fi $4$ și $7$. Cu aceasta, câți pași de calcul $f,g,h$ sunt necesari pentru a găsi $i,j,k$ pentru $x_1,x_2$ dat. Nu este posibilă nicio proiecție? Nu ar fi necesar ca $N$ să fie foarte mare pentru a evita factorizarea? Mai mic decât mod a prim [$N = 2 pqr+1$](https://crypto.stackexchange.com/questions/70282/how-safe-is-a-prime-with-p-2-cdot-q- cdot-r-cdot-s-cdot-t1-for-discrete-lo)?
0
Răspunde
Daniel S avatar
drapel ru
Daniel S
Inversurile sunt unice dacă rămânem la exponenți care sunt rădăcini primitive atât pentru $r$ cât și pentru $s$. „Proiectarea” ar trebui să fie posibilă numai dacă cineva cunoaște ordinea grupului, care este echivalent cu factorizarea $N$, și da $N$ va trebui să fie mare, iar adversarul dvs. nu ar trebui să aibă capacități cuantice. Dacă se folosește un prim în loc de un compozit, atunci este posibil să faceți un pas uriaș deoarece ordinea grupului este cunoscută.
2
Răspunde
J. Doe avatar
drapel at
J. Doe
Pare să funcționeze, foarte interesant, mulțumesc din nou pentru răspuns. Singurul dezavantaj este dimensiunea mare de $N$. Din câte știu, sunt necesari cel puțin 1000 de biți pentru a evita factorizarea. În cazul în care factorizarea este cunoscută, proiecția și pasul gigant este posibil și cu acest $\aproximativ 2^{250}$ pași sunt necesari pentru a rezolva acest lucru (găsiți $i,j,k$ pentru $x_1$ la $x_2$ aleatoriu) ceea ce este imposibil. Schimbarea lui în ceva mai rezonabil, cum ar fi $2^{128}$, ar face posibilă din nou factorizarea $N$ un număr de $512$biți. Pentru cazul de utilizare țintă, caut o cantitate mai mică de valori diferite ($
0
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.