Rupeți RSA fără umplutură folosind un atac de masă curcubeu

Da, atacul din întrebare ar funcționa pentru modulo scăzut al exemplului.Termenul „dicționar” este mai potrivit decât „tabel curcubeu” (folosit în contextul realizării unui tabel compact de hasheuri precalculate).

Atacurile reale nu pot funcționa în acest fel. În RSA, așa cum este practicat, este imposibil să construiți un dicționar suficient de mare, deoarece ar dura prea mult timp pentru a construi (proporțional cu modulul $n$, care este de obicei de cel puțin 2048 de biți în prezent). Cu toate acestea, dacă Alice a criptat un mesaj despre care se știe că aparține unui set mic (cum ar fi numele de pe lista de clasă) direct cu manualul RSA $m\mapsto c:=m^e\bmod n$, atunci este posibil să se decripteze $c$ prin criptarea fiecărui mesaj posibil și testarea care se potrivește $c$. O căutare secvenţială a $m$ în rola de clasă va face: un dicţionar al corespunzătoare $c$ este util doar dacă există mai multe mesaje (și RSA nu este practic folosit prin împărțirea mesajelor în bucăți mici, ca în întrebare).

Umplutura de criptare aleatorie rezolvă această problemă, prin reversibil întoarcerea unui mesaj $m$ într-un reprezentant de mesaj suficient de aleatoriu $\widetilde m\in[0,n)$. Apoi, manualul RSA poate fi aplicat în siguranță $\widetilde m$, conform ipotezei RSA: pentru cheia publică adecvată $(n,e)$ și Aleatoriu $x\în[0,n)$, e greu de găsit $x$ din $x^e\bmod n$.

cum poate decriptorul (Bob) să „elimine” acele biți aleatorii dacă nu le cunoaște?

Imaginea de ansamblu este că există o convenție între Alice și Bob despre ce fragmente $\widetilde m$ sunt umpluturi (dintre care unele aleatoare) adăugate de Alice, care ar trebui eliminate de Bob. Această descriere simplificată este destul de apropiată de tehnica de umplutură învechită din RSAES-PKCS1-v1_5. Modernul RSAES-OAEP are pași suplimentari, așa că toți cu excepția (cel mult) 8 biți de $\widetilde m$ apar aleatoriu chiar și atunci când $m$ nu este (care se obține printr-o transformare criptografică simetrică reversibilă după aplicarea unei umpluturi aleatorii, care difuzează aleatorietatea), dar ideea rămâne.