Folosind algoritmul lui Shor pentru a accesa mesajele RSA fără factoring

De cele mai multe ori oamenii au uitat că scopul real al adversarului împotriva criptării este accesarea mesajului. De exemplu, în cazul RSA, vorbim despre factorizarea modulului pentru a ajunge la cheia privată pentru a dezvălui mesajele criptate. Dacă nu se folosește criptarea adecvată, atunci în loc de factoring se poate încerca spațiul posibil pentru mesaje sau atacul cube-root.

În cazul RSA, dacă vreodată este construită o dimensiune reală pentru Algoritmul de găsire a perioadei lui Shor atacatorul poate factorul de modul și apoi poate dezvălui mesajele folosind cheia privată în timp polinomial sau mai bine în BQP.

• Este posibil cu un algoritm lui Shor modificat (sau altul) care nu ia în considerare modulul, dar dezvăluie mesajul criptat sub RSA manual sau RSA căptuşit corespunzător?
• Există o lucrare publicată asemănătoare cu aceasta?

Acest lucru este semnificativ doar în cazul în care dezvăluirea mesajelor fără factoring poate necesita mai puțin QBit decât algoritmul lui Original Shor.

Pentru un modul RSA, algoritmul lui Shor va returna (cu mare probabilitate) un factor mare de ordinul multiplicativ al unui element de bază modulo $N$. Diferiți algoritmi clasici adjuvanti pot folosi acest lucru pentru a returna factorii de $N$, dar în egală măsură s-ar putea folosi direct această ieșire pentru a calcula un exponent de decriptare eficient, fără a se deranja să calculeze factorii. Mai exact, dacă $k$ este rezultatul algoritmului lui Shor apoi rezolvarea $de\equiv 1\pmod{100!k}$ va oferi probabil un exponent de decriptare eficient $d$ (trebuie avut grijă ca $100!$ nu are factori în comun cu $e$, dar putem doar să le împărțim).

Această abordare economisește doar timp la post-procesarea clasică și nimic la calculul cuantic. Algoritmul lui Shor este destul de eficient și este dificil să veniți cu îmbunătățiri semnificative. Un caz în care este posibil ca un singur mesaj să fie mai ieftin de atacat este dacă știm/credem că textul cifrat are o ordine multiplicativă semnificativ mai mică modulo $N$. Apoi putem alege în mod specific mesajul nostru să fie baza atacului nostru folosind algoritmul lui Shor. În acest caz, putem parametriza transformarea Fourier cuantică pentru a recupera comenzi până la o anumită limită $b$ mai degrabă decât plină $\lambda(N)$, necesitând aproximativ 2 miliarde de dolari QFT qubits mai degrabă decât $2\lambda(N)$ QFT qubits. Nu există nimic în manualele RSA sau RSA cu umplutură standardizată care să împiedice ordinele multiplicative mici, dar sunt puțin probabile.

ETA: Dacă recuperăm o comandă mică, să zicem, $r$ apoi rezolvarea $de\equiv 1\pmod r$ furnizează un exponent de decriptare care funcționează pentru elementul de ordine mică, dar nu ar funcționa pentru un text cifrat general. Probabilitatea de a avea o comandă mică va depinde puternic de factorii de $p-1$ și $q-1$. A foarte limita superioară brută a proporției de texte cifrate care au ordine mai mică decât $b$ va fi $$\sum_{d|\lambda(N):d>\lambda(N)/b}\frac1d.$$

Pot să dau doar un răspuns foarte simplu la minte.

În cea a lui N. David Mermin Informatică cuantică: o introducere, în explicația sa despre criptarea RSA din Secțiunea 3.3, spune el

Găsirea eficientă a perioadei este de interes în această setare criptografică nu numai pentru că duce direct la factoring eficient (așa cum este descris în Secțiunea 3.10), ci și pentru că o poate conduce pe Eve direct la o modalitate alternativă de a decoda mesajul lui Alice $b$ fără ca ea să știe sau să fie nevoită să calculeze factorii $p$ și $q$ de $N$ [Cheia publică a lui Bob]. Iată cum funcționează:

Apoi continuă să explice cum să decriptezi mesajul folosind algoritmul lui Shor pentru constatarea perioadei într-un mod destul de simplu. Abia mai târziu, în secțiunea 3.10, după ce a terminat complet de explicat cum să folosească algoritmul lui Shor pentru decriptarea directă a RSA, atunci separat explicați cum poate algoritmul de găsire a perioadei lui Shor de asemenea poate fi folosit pentru factorizarea numerelor mari (care, la rândul lor, poate fi apoi folosit și pentru a sparge RSA într-un mod diferit).

Această din urmă metodă pare puțin mai complicată de înțeles pentru mine, dar nu știu care metodă necesită mai multe resurse de calcul. Bănuiesc că sunt destul de aproape de echivalent, deoarece cred că diferă doar în post-procesarea clasică și nu în utilizarea transformării cuantice Fourier. (Deși, cred că post-procesarea clasică este de fapt blocajul computațional pentru algoritmul lui Shor, așa că poate că există o diferență semnificativă în resurse.)