înregistrare Logare
Puncte:0
arsenne lupulupin avatar Crypto

Rezolvarea unui jurnal discret cu BsGs

drapel jo
arsenne lupulupin

Dacă luăm în considerare un grup G cu modul p, ordinea q cu $p=2*q+1$, și generator $g=2$ ($ p$, $q$ numere prime uriașe), există o modalitate de a rezolva problema logului discret $ g^x = y $ pentru un y dat, folosind algoritmul pasilor giganți ȘI faptul că $x$ este de forma: $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in \mathbb{N} $ fără a fi necesară stocarea tuturor pașilor mici într-o tabelă hash, ceea ce este imposibil având în vedere mărimea numerelor $p$ și $q$.

Editați | ×: The $ \alpha_i $ valorile sunt necunoscute atacatorului.

editarea 2: $\alpha_i \in [0,\infty] $

96
0 + 0
poncho avatar
drapel my
poncho
Atacatorul cunoaște valorile $\alpha_i$?
0
Răspunde
kelalaka avatar
drapel in
kelalaka
De fapt, $\alpha_i \in \{0,1\}$? Dacă $\mathbb{N} = \mathbb{Z}^+$ sau $\mathbb{N} = \mathbb{Z}^+ \cup \{0\}$, nu există un acord comun în acest sens.
1
Răspunde
Puncte:0
poncho avatar Crypto
drapel my
poncho

există o modalitate de a rezolva problema jurnalului discret $g^x=y$ Pentru o $y$ dat, folosind algoritmul pași giganți

Nicio modalitate practică dacă $p, q$ sunt mari.

Chiar dacă $x$ se știe că este în formă $ x = \sum_{i=0}^{10} \alpha_i * 2^i $ $:\alpha_i \in \mathbb{N} $ ?

Fiecare potențial $x$ poate fi exprimat în această formă; considera $\alpha_1 = \alpha_2 = ... = \alpha_{10} = 0$ și $\alpha_{0} = x$. Prin urmare, știind asta $x$ este exprimabil în acea formă nu oferă nicio informație suplimentară; BsGs este utilizabil numai dacă modulul este suficient de mic (și întrebarea presupune că nu este)

0 + 0
Ievgeni avatar
drapel cn
Ievgeni
Nu $x
0
Răspunde
poncho avatar
drapel my
poncho
@levgeni: dacă vorbim despre valori care **pot** fi exprimate în acea formă, avem $x \ge 2047$ (și asta cu convenția că $0 \not\in \mathbb{N}$; în caz contrar , toate valorile $x$ pot fi exprimate în această formă).
0
Răspunde
poncho avatar
drapel my
poncho
@levgeni: și, dacă $x
0
Răspunde
kelalaka avatar
drapel in
kelalaka
@poncho Cred că levgeni susține că, chiar dacă $x>2046$, nu înseamnă că $x$ nu este trivial de mic. Cea mare este clară, totuși cele mici au nevoie de o metrică.
0
Răspunde
poncho avatar
drapel my
poncho
@kelalaka: nu inteleg argumentul tau; dacă interpretăm întrebarea „este DLog rezolvabil dacă presupunem că exponentul este aleatoriu, condiționat de a fi exprimabil în forma dată?” Cu această înțelegere, răspunsul meu este corect - cum interpretați întrebarea?
0
Răspunde
kelalaka avatar
drapel in
kelalaka
@poncho dacă $x$ este mic (nici o măsurătoare aici), dar cunoaștem limita, atunci BsG-urile pot fi parametrizate pentru a se rezolva mai repede, nu? Și din nou, dacă $x$ este mic, atunci de fapt nu avem nevoie de BsG-uri, îl putem forța brute așa cum putem forța brută de la 1 la $2^{48}$ pentru posibilul $x$'. Sau presupui implicit $x$ uniform aleatoriu?
0
Răspunde
Ievgeni avatar
drapel cn
Ievgeni
@poncho Ok, am crezut că $\alpha$-urile sunt biți. Sunt puțin pierdut cu toate editările. Încă nu înțeleg de ce ai vorbit despre $2046$. Aș dori să-mi șterg $-1$, dar pot doar dacă vă editați mesajul.
0
Răspunde
poncho avatar
drapel my
poncho
@levgeni: dacă $0 \not\in \mathbb{N}$, atunci minimul $\sum_1^{10} 2^i\alpha_i$ poate fi este 2046. Unele definiții ale $\mathbb{N}$ nu includ 0, alții fac.
0
Răspunde
Ievgeni avatar
drapel cn
Ievgeni
Dar suma din întrebare începe la zero, deci ar trebui să fie de 2047$?
0
Răspunde
poncho avatar
drapel my
poncho
@levgeni: Folosesc $\alpha_0$ ca valoare care se schimbă, și astfel avem efectiv $x = \alpha_0 + 2046$ - $\alpha_0 = 0$ nu este permis, așa că avem $x > 2046$
0
Răspunde
Ievgeni avatar
drapel cn
Ievgeni
@Ievgeni : Bine, mulțumesc pentru explicație. Am inteles. Dar se pare că în cele din urmă valorile $alpha$ pot fi egale cu zero.
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.