Semnarea RSA - Întrebare privind falsificarea existențială și prefixul mesajului. Este unul ciudat

Sunt nou în asta. Te rog fii amabil. Am o întrebare teoretică pe care aș dori să o verificăm:

Bob și Alice fac semnarea RSA fără o funcție hash -- doar pun un mesaj și primesc o semnătură.

Mesajele pe care Bob și Alice le trimit unul altuia sunt numere aleatorii.

Fără o funcție hash implicată, un atacator poate crea un mesaj cu semnătura dorită. Dar ei nu pot controla mesajul.

Cu toate acestea, deoarece Bob și Alice își trimit reciproc numere aleatorii, acest atacator ar putea crea un mesaj cu aspect valid. Adică, o semnătură validă pe un număr aparent aleatoriu.

Dar Bob și Alice vor să facă această schemă sigură, așa că adaugă un prefix cunoscut la mesajele lor. Ele adaugă ceva structură.

Deci, în loc de un mesaj care arată ca: 484262 Arată astfel: prefix_484262

Iată ceea ce vreau să fie verificat:

Adăugând prefixul cunoscut, un atacator poate falsifica mesaje doar prin forță brută și, ca urmare, securitatea acestei scheme este proporțională cu lungimea prefixului.

Adică, lungimea prefixului contează. De exemplu, dacă prefixul era doar un octet, probabil că atacatorul ar avea nevoie doar de aproximativ 255 de încercări pentru a falsifica un mesaj care funcționează. Dar, dacă prefixul ar fi doi octeți, atacatorul ar avea nevoie de 65.536 de încercări.

Celălalt lucru pe care vreau să-l verific este:

Cunoașterea prefixului nu este un avantaj pentru forțarea brută a mesajelor (în afară de faptul că atacatorul știe cum trebuie să arate rezultatul).

Multumesc pentru orice ajutor. Apreciez asta.

Presupun că sistemul de semnătură propus primește un mesaj $M$, îl convertește într-un număr întreg $m$ mai puțin decât $n$ prin adăugarea oarecum a unei constante fixe $c$ în stânga expresiei de $M$ de ca $i$ cifre într-o bază $b\ge2$ (baza 10 la întrebare) astfel $m:=c\,b^i+M$, apoi construiește semnătura $\sigma=\mathrm{Sig}(M)$ per manual RSA cu cheie privată $(n,d)$, acesta este $\sigma:=m^d\bmod n$; iar verificatorul dat $(n,e)$ și $(M,\sigma)$ (sau doar $\sigma$) calculează $\sigma^e\bmod n$ apoi verifica asta $c\,b^i+M$. Deocamdată las nespecificat dacă $i$ este fix sau depinde de $M$ (si cum).

Adăugând prefixul cunoscut, un atacator poate falsifica mesaje doar prin forță brută și, ca urmare, securitatea acestei scheme este proporțională cu lungimea prefixului.

Pentru ca această propoziție să aibă vreo șansă să fie adevărată, trebuie să adăugăm „până la punctul prefixul $c$ devine atât de mare încât factorizarea de $n$ devine cel mai simplu atac". Presupun asta în cele ce urmează.

Această propoziție pare adevărată (dar nu avem o dovadă) dacă luăm drept definiție a securității pentru semnătură Nefalsificare existențială în cazul unui atac de mesaj cunoscut, în care adversarii au cheia publică $(n,e)$ plus un număr de valide $(M_j,\sigma_j)$ perechi pentru aleatoriu $M_j$, și încercați să expuneți a $(M,\sigma)$ pereche pentru $M$ niciunul dintre $M_j$.

Dar asta e incorect dacă luăm Nefalsificare existențială sub atacul cu mesaje alese, în care adversarului i se permite să solicite semnătură $\sigma_j$ a oricărui mesaj $M_j$ la alegerea lor, înainte de a expune $(M,\sigma)$ ca mai sus. Problema este că sub acest model de securitate există atacuri mai bune decât forța brută.

• Atacul este ușor dacă ne permitem $i$ să fie numărul de cifre ale $M$ în bază $b$ (fie cu sau fără suprimarea zerourilor de început) și utilizați un mic exponent public $e$ (de exemplu, 3): un atacator găsește semnătura oricărui mesaj $M$ consideră potrivit (până la o anumită limită de dimensiune) din semnătura mesajului $M'=M\,b^e$ dacă $M$ este suficient de scurt pentru a satisface $c\,b^{i'}+M'=c\,b^{i+e}+M\,b^e<n$ cerinţă, din moment ce $\mathrm{Sig}(M')\,b^{-1}\bmod n=\mathrm{Sig}(M)$.
• Pentru fix $i$, lucrurile sunt mai grele, dar Desmedt și Odlyzko atacul permite falsificarea cu dificultate mult mai mică decât forța brută, departe de a fi dublat atunci când permitem $c$ să fie de două ori mai mare și chiar sub-exponențială cu $\log_2(c)$.
• Atacul anterior devine mai ușor dacă ne permitem $i$ fix pentru un dat $c$, dar egală cu dimensiunea $c$ în bază $b$.

Cunoașterea prefixului nu este un avantaj pentru forțarea brută a mesajelor (în afară de faptul că atacatorul știe cum trebuie să arate rezultatul).

Motivația semnăturii este de a permite verificarea fără informații secrete, iar secretizarea prefixului contravine. O să presupun totuși.

Apoi, acea afirmație este corectă, cu excepția atacurilor nerealiste numai cu cheie, dar discutabilă tocmai din motivul care o face corectă: adversarii cunosc cel puțin unul. $(M_0,\sigma_0)$ pereche pe lângă cheia publică $(n,e)$, și astfel pot găsi cu ușurință prefixul $c$ prin calcul ${\sigma_0}^e\bmod n$.