Este sigură criptarea fiecărui număr separat folosind RSA?

Să presupunem că RSA este considerată o metodă „securizată” pentru criptare. RSA este menit să codifice o secvență de baze de numere întregi $27$. Dacă folosim un $n=pq$ este greu de factor. Este încă sigur dacă codificăm fiecare număr întreg (litera) separat, mai degrabă decât întreaga frază o dată?

Edit: Nu mă așteptam să primesc răspunsuri atât de grozave. Multumesc tuturor!

Cu căptușeală adecvată (cum ar fi OAEP), utilizarea RSA pentru a cripta octeți sau caractere individuali sau chiar biți este într-adevăr sigură*. Desigur, este, de asemenea, incredibil de risipitor, deoarece transformi fiecare 8 biți de text simplu în ceva de genul 2048 sau mai mulți biți de text cifrat și petreci mult timp CPU în acest proces, dar ineficiența nu este (de obicei) o problemă de securitate.

Fără umplutură, totuși, folosind RSA pentru a cripta fie caracterele unice sau mesajele scurte sunt nesigure, deoarece o astfel de criptare „RSA” este vulnerabilă la mai multe atacuri, permițând decriptarea mesajelor fără cheia privată. Unele dintre aceste atacuri includ:

• Atacul ghicitului: generați o listă de câteva sute (sau câteva trilioane) de texte clare mai mult sau mai puțin plauzibile și criptați fiecare dintre ele cu cheia publică. Verificați dacă rezultatul se potrivește cu mesajul pe care doriți să îl decriptați. Dacă da, tocmai ați găsit textul simplu corect.

  Acest atac va distruge complet orice schemă folosind manualul RSA pentru a cripta caractere sau octeți unici, deoarece este ușor să criptați fiecare caracter sau octet cu cheia publică și, astfel, să obțineți un dicționar complet al tuturor textelor cifrate posibile. Dar funcționează și oricând spațiul de text simplu este suficient de mic (sau atacatorul poate ghici că textul clar aparține probabil unui set suficient de mic) încât să poată fi enumerat pe un computer (sau pe un grup de computere).

• The $e$-th root attack: Dacă modulul public $e$ este mic (cum ar fi $e = 3$) și textul simplu $m$ (după ce a fost codificat ca număr) este, de asemenea, suficient de mic încât $m^e < n$, apoi criptarea RSA manuală poate fi înfrântă pur și simplu prin calculul $e$-a rădăcină a textului cifrat $c = m^e \bmod n$. Variațiile acestui atac pot fi, de asemenea, făcute să funcționeze dacă $m^e < kn$ pentru un număr întreg mic $k$ (să zicem, mai puțin de un trilion), pur și simplu prin testarea forței brute dacă $e$-a rădăcină a $c + jn$ este un număr întreg pentru toți $j$ din $0$ pâna la $k$. Deși acest atac este ușor de evitat (de ex.prin utilizarea unei umpluturi de criptare adecvate și/sau prin utilizarea unui exponent public mai mare, cum ar fi comunul $e = 2^{16} + 1 = 65537$), în mod surprinzător, multe scheme RSA naive concepute de amatori (sau concepute pentru a fi rupte în mod deliberat, de exemplu, într-un CTF) pot cădea în fața ei.

^{*) În sensul asigurării confidenţialităţii şi securitate semantică împotriva unui atacator pasiv cu interceptare, presupunând că cheia RSA este generată corespunzător și suficient de lungă pentru a rezista atacurilor de factoring, că generatorul de numere aleatorii utilizat pentru OAEP nu este compromis și că nu au fost făcute alte greșeli evidente de implementare și că existența și lungimea mesajului nu sunt confidențiale. Chiar și atunci, orice schemă de stil „ECB” care criptează textul câte un caracter este, desigur, foarte maleabilă și astfel vulnerabilă la manipularea de către un atacator activ.}

Deși RSA nu este destinat criptării, se poate folosi RSA pentru criptare. Dacă cineva folosește TextBook RSA, atunci va fi nesigur, deoarece criptarea este gratuită, atunci orice atacator poate verifica valorile. Numim asta oracolul de criptare și este gratuit pe sistemele cu cheie publică

Un simplu Oracol de criptare RSA joc...

def Ind_CPA_RSA(adversar, țintă):
    (e,n,d,...) = generate_RSA_key() //keygen part

    def RSA_encryption_oracle_PKCS#1_v1.5(text simplu): //Oracul de criptare
        EM = PKCS#1_v1.5_padding(text simplu)
        ciphertext = EM^e mod n
        returnează text cifrat

    pentru fiecare m din posibil_spațiu_mesaj: //interogări
        c = RSA_encryption_oracle_PKCS#1_v1.5(m)
        dacă c == țintă
            print(tinta)
            întoarce succesul
    eșecul de întoarcere

Așadar, adversarul încearcă toate mesajele posibile cât de mult poate, pentru a vedea egalitatea pentru a câștiga.

În manual RSA dacă exponent public $e=3$ atunci atacul rădăcinilor cubice funcționează pentru toate mesajele astfel încât $len(m) < \sqrt[3]{n}$.

Pentru toate celelalte atacuri, articolul lui Dan Boneh este un bun punct de plecare;

• 1999, Douăzeci de ani de atacuri asupra criptosistemei RSA, Dan Boneh.

$$\textbf{Nu utilizați niciodată Text Book RSA atâta timp cât știți ce faceți!}$$

Pentru a fi sigur, trebuie să utilizați criptarea RSA cu umplutură adecvată PKCS#1 v1.5 (RSAES-PKCS1-v1_5) sau OAEP (RSAES-OAEP) căptușeală. Aceste umpluturi adaugă randomizare pentru a realiza criptarea probabilistică.

Fiecare folosește codificări speciale pentru a realiza acest lucru, cum ar fi umplutura PKCS#1 v1.5;

EM = 0x00 || 0x02 || PS || 0x00 || M.

M este mesajul. The PS constau din partea de randomizare

Generați un șir de octet PS cu lungimea k - mLen - 3 constând din octeți non-zero generați pseudoaleatoriu. Lungimea PS va fi de cel puțin opt octeți.

De exemplu pentru RSA pe 2048 de biți; $k = 256$, $mLen=4$ atunci PS lungimea este de 249 de octeți de aleatorie pentru un mesaj de dimensiunea unei litere. Prin urmare, atacatorul nu poate testa valorile cu oracolul de criptare. Restul ataca problema RSA.

În mod similar, OAEP are caracter aleatoriu și OAEP s-a dovedit că are securitate IND-CCA1. Preferați OAEP față de PKCS#1 v1.5, deoarece are multe atacuri din cauza implementărilor necorespunzătoare.

Dacă cineva dorește un articol academic despre valorile criptării RSA, aici este articolul paywall;

• 2020, Adecvarea RSA pentru criptarea datelor în bloc, Pranshu Bajpai et. al.

Dacă fiecare caracter este criptat independent, atunci de fiecare dată când caracterul „a” apare în textul simplu, se mapează la același simbol unic de orice lungime (de exemplu, 0x157a05c8). Și invers, de fiecare dată când vedeți 0x157a05c8 în textul cifrat, acesta trebuie să se mapeze la „a” în textul simplu. În cele din urmă, indiferent de cât de lungi sunt jetoanele de ieșire, dacă intrarea este criptată câte un octet (8 biți) la un moment dat, există doar 256 de jetoane de ieșire posibile, la fel ca numărul de jetoane de intrare posibile.

Asta nu mai este RSA. E o cifr de substituție, iar acestea sunt trivial de rupere folosind o serie de tehnici simple. Nu utilizați RSA ca algoritm de criptare, ci mai degrabă ca un funcția de derivare a tastei. Dar asta nu face ca cifra de substituție în sine să fie mai puternică.