Vulnerabilitatea RSA atunci când M criptat nu este coprime cu N

Când $(N,e)$ este o cheie publică RSA validă cu $N$ produsul a două numere prime secrete distincte $p$ și $q$, există probabilitatea de aproximativ $1/p+1/q$ ca un mesaj aleator $M $ este astfel încât $M^e$ nu este coprim cu $N$. Deoarece atât $p$ cât și $q$ trebuie să fie mari (sute de cifre zecimale) pentru ca RSA să fie sigur, această probabilitate este complet neglijabilă în utilizarea reală a RSA. Întrebarea este să luăm în considerare ceva care în utilizare reală nu va apărea pentru $M$ aleatoriu sau pseudoaleatoriu sau pentru $M\in[1,N)$ ales de cineva care nu știe (și nu poate găsi) factorizarea lui $N$ .

RSA este o permutare de trapă. Asta implică ceva?

Ok, nu m-am gândit la asta.În acest caz, este o vulnerabilitate severă de securitate, deoarece luând GCD-ul textului cifrat (C) și N scurgeri p sau q?

Utilizarea OAEP pe un C care nu este coprim cu N ar dizolva problema?

@Chen: Nu înțeleg ce vrei să spui prin „folosirea OAEP pe C”; dar folosirea OAEP pentru a produce intrarea $M$ pentru criptarea RSA brută $M\mapsto C=M^e\bmod N$ pentru $N$ altfel sigur este practic sigur că va „dizolva problema”, dacă a existat una. Acum putem cifra în siguranță multipli de $p$ sau $q$. Din nou, chiar și atunci când nu utilizați OAEP, nu există nicio problemă practică, deoarece alegerea $M$ sau $C$ în $[1,n)$ cu $\gcd(C,N)\ne1$ este imposibil pentru cineva care nu știe ( nici capabil să găsească) factorizarea lui $N$.

Îmi pare rău, am vrut să folosesc OAEP pe M. Vrei să spui că a alege un M care dă $gcd(C,N)â 1$ intenționat este imposibil fără a cunoaște p și q?

si de ce ar fi imposibil? Ar mai fi posibil cu o probabilitate de succes de 1/p + 1/q?

@Chen nu ar fi diferit de un atacator care doar ghicește factori aleatori de $N$ :)

@Chen: pentru dimensiuni practice $p, q$, adică $2^{-1024}$ sau mai mici, $1/p + 1/q$ este efectiv „imposibil”

întrebarea această in alte limbi: