Este posibil să se aplice RSA pe numere complexe?

RSA este un algoritm popular de criptare cu cheie publică. Are câteva presupuneri matematice.Adică, nu se poate aplica RSA pe elemente ale oricărei structuri algebrice. Elementele din anumite structuri algebrice sunt eligibile doar pentru utilizare în RSA.

Vreau să știu dacă numerele complexe se încadrează în acele structuri algebrice particulare sau nu. Dacă nu, din cauza lipsei carei numere complexe de proprietate au devenit neeligibile cel puțin teoretic?

Ansamblul complexelor $\mathbb C$ este nepotrivit pentru RSA. Acest lucru se datorează faptului că RSA (ca toată criptografia) mapează textul simplu și textul cifrat la seturi finite (de ex. $\mathbb Z_n$ sau este subset $\mathbb Z_n^*$), și $\mathbb C$ este infinit.

Orice efort de a prezenta un subset finit de $\mathbb C$ potrivit pentru RSA și folosind înmulțirea nativă eșuează. În detaliul includerii $0$ sau nu, necesitatea ca aceasta multime sa fie inchisa sub inmultire ne lasa cu multimea $\{e^{2i\pi/n}\text{ pentru }i\in\mathbb N\text{ cu }i<n\}$ ca singura posibilitate. Această mulțime este trivial izomorfă cu grupul $(\mathbb Z_n,+)$și, prin urmare, nu duce la un criptosistem sigur.

^{Pe de altă parte, putem face o relație de echivalență $\sim$, compatibil cu înmulțirea în (un subset de) $\mathbb C$ [adică: pentru orice $a$, $a'$, $b$, $b'$ în $\mathbb C$ (sau subsetul menționat), $a\sim a'$ și $b\sim b'$ implică $a\,b\sim a'\,b'$ ], astfel încât setul de clase de echivalenţă este finită, iar înmulțirea rezultată este internă pe grupul de coeficient. Un exemplu banal consideră $\mathbb Z_n\subset\mathbb R\subset\mathbb C$, și $\sim$ definit ca echivalență modulo $n$ pentru acel subset de $\mathbb C$. Acest răspuns oferă un exemplu mai interesant. Există și mai multe posibilități dacă redefinim în continuare multiplicarea, inclusiv an Analog de curbă eliptică a RSA, care poate fi remapată cu ușurință $\mathbb C$. Nu văd că acestea se potrivesc cu întrebarea inițială, deoarece schimbăm atât setul (prin restricție) cât și operația (pentru a-l păstra intern).}

Dat $p,q$ a formei 4k $+3$, putem defini numere complexe mod $p$ sau mod $q$. Formularul garantează că $-1$ nu are rădăcină pătrată acolo, așa că lucrăm cu o extensie pătratică a $GF(p)$ și $GF(q)$, adică $$GF(p^2) \simeq GF(p)[i]/(i^2+1)$$ și $$GF(q^2) \simeq GF(q)[i]/(i^2+1).$$

Combinându-le, putem defini RSA peste $(\mathbb{Z}/n\mathbb{Z})[i]/(i^2+1)$, $n=pq$, adică numere complexe în care părțile reale și imaginare sunt definite mod $n$. Aritmetica (înmulțirea, adunarea etc.) se face similar numerelor complexe. De exemplu. $$(a+bi)(c+di)\equiv (ac-bd) + (ad+bc)i \pmod{n}$$ (valorile stocate ca perechi $(a,b)$ și $(c,d)$).

Ordinea grupului multiplicativ este $\mathrm{lcm}(p^2-1, q^2-1)$, deci avem nevoie $$e\cdot d \equiv 1 \pmod{\mathrm{lcm}(p^2-1, q^2-1)}.$$

Desigur, factoring $n$ încalcă schema, deci nu crește securitatea.

O altă problemă posibilă este că numerele complexe au norma (pătratului), care este multiplicativă și ușor de calculat fără a ști. $p$ și $q$: $$N(a+bi) \equiv a^2+b^2 \pmod{n},$$ $$N(c) \equiv N(m^e) \equiv N(m)^e \pmod{n}.$$ Din moment ce norma trăiește în $GF(p)\ori GF(q)$, reducem la mod de bază RSA $n$. Dacă un atacator poate sparge cumva RSA mod $n$, atacatorul recuperează apoi norma mesajului.

Rezumat:

Este posibil să se definească RSA peste numere complexe modulo prime, totuși avantajele acestui lucru nu sunt clare, deoarece securitatea nu crește în comparație cu RSA de bază, iar eficiența scade puțin.

Nu văd alte atacuri semnificative asupra acestei scheme, m-aș bucura să știu dacă există.

Actualizare: În loc de $\sqrt{-1}$ putem folosi oricare altul $\sqrt{d}$ care nu se află în câmpul de bază, adică să lucrezi cu $\mathbb{Z}[\sqrt{d}]/n\mathbb{Z}$. Aceasta s-a făcut într-o variantă de Semnături OSS. (OSS a fost rupt, dar numai pentru că este slab în sine, RSA definit peste numere întregi pătratice ar trebui să fie ok.)

Elementele din anumite structuri algebrice sunt eligibile doar pentru utilizare în RSA.

Nu sunt exact ce vrei să spui prin asta. Criptarea RSA poate fi (și de obicei este) văzută ca:

• Luați un șir de biți text simplu (până la o lungime maximă ceva mai mică decât dimensiunea modulului)

• Rulați-l printr-o funcție de umplutură pentru a-l converti (plus ceva aleatoriu) într-un număr între 0 și N-1

• Rulați operația publică RSA subiacentă pentru a o converti într-un alt număr între 0 și N-1

• Convertiți acel număr în șirul de biți de text cifrat.

(și operațiunile de decriptare și semnătură sunt similare).

Ca atare, orice valoare care poate fi reprezentată prin șirul de biți (dimensiune mărginită) poate fi gestionată de RSA.

Acum, acest lucru distruge proprietățile homomorfe ale RSA (nu este un accident; acestea sunt rareori utile utilizatorului și pot fi utile pentru un atacator, așa că vrem să le distrugă); pe de altă parte, nu este clar cât de utile ar fi oricum numerelor complexe.

Desigur, criptarea RSA poate fi aplicată numerelor complexe, deoarece numerele complexe sunt mapate cu date arbitrare, reprezentate ca două numere reale (fie mărime și fază, fie reale și imaginare). Dacă RSA poate fi aplicat numerelor reale, atunci este ușor extins la numere complexe. În cele din urmă, ambele sunt reprezentate ca date care pot fi criptate.