Calculatoarele cuantice ar putea sparge criptarea mai devreme decât se aștepta cu un nou algoritm

Calculatoarele cuantice ar putea sparge criptarea mai devreme decât se aștepta cu un nou algoritm

Marca temporală: 2 octombrie 2023 10:00

Una dintre cele mai bine stabilite și mai perturbatoare utilizări pentru un viitor computer cuantic este capacitatea de a sparge criptarea. Un nou algoritm ar putea reduce semnificativ bariera în realizarea acestui lucru.

În ciuda întregului hype în jurul calculului cuantic, există încă semne de întrebare semnificative în jur pentru ce computere cuantice vor fi de fapt utile. Există speranțe că ar putea accelera totul, de la procesele de optimizare la învățarea automată, dar cât de mai ușor și mai rapid vor fi acestea rămâne neclar în multe cazuri.

Un lucru este însă destul de sigur: un computer cuantic suficient de puternic ar putea face ca schemele noastre criptografice de vârf să nu aibă valoare. În timp ce puzzle-urile matematice care le stau la baza sunt practic de nerezolvat de către computerele clasice, ele ar fi în întregime tratabile pentru un computer cuantic suficient de mare. Aceasta este o problemă, deoarece aceste scheme securizează majoritatea informațiilor noastre online.

Harul salvator a fost faptul că procesoarele cuantice de astăzi sunt departe de tipul de scară necesar. Dar conform unui raportează Ştiinţă, informaticianul Oded Regev de la Universitatea din New York a descoperit un nou algoritm care ar putea reduce în mod substanțial numărul de qubiți necesari.

Abordarea reproșează în esență unul dintre cei mai de succes algoritmi cuantici de până acum. În 1994, Peter Shor de la MIT a conceput o modalitate de a afla care numere prime trebuie să fie înmulțite împreună pentru a da un anumit număr - o problemă cunoscută sub numele de factoring primi.

Pentru un număr mare, aceasta este o problemă incredibil de dificilă, care devine rapid insolubilă pe computerele convenționale, motiv pentru care a fost folosită ca bază pentru schema populară de criptare RSA. Dar, profitând de fenomenele cuantice precum suprapunerea și încurcarea, algoritmul lui Shor poate rezolva aceste probleme chiar și pentru numere incredibil de mari.

Acest fapt a dus la un nivel nu mic de panică în rândul experților în securitate, nu în ultimul rând pentru că hackerii și spionii pot colecta date criptate astăzi și apoi pur și simplu așteaptă dezvoltarea unor computere cuantice suficient de puternice pentru a le sparge. Și, deși au fost dezvoltate standarde de criptare post-cuantică, implementarea lor pe web ar putea dura mulți ani.

Totuși, probabil că va fi o așteptare destul de lungă. Majoritatea implementărilor RSA se bazează pe chei de cel puțin 2048 de biți, ceea ce este echivalent cu un număr de 617 cifre. Cercetătorii Fujitsu recent calculat că ar fi nevoie de un computer cuantic complet tolerant la erori cu 10,000 de qubiți 104 zile pentru a sparge un număr atât de mare.

Cu toate acestea, noul algoritm al lui Regev, descris în a pre-print publicat pe arXiv, ar putea reduce aceste cerințe în mod substanțial. Regev a reelaborat în esență algoritmul lui Shor, astfel încât să fie posibil să găsiți factorii primi ai unui număr folosind mult mai puțini pași logici. Efectuarea operațiunilor într-un computer cuantic presupune crearea de mici circuite din câțiva qubiți, cunoscute sub numele de porți, care efectuează operații logice simple.

În algoritmul original al lui Shor, numărul de porți necesare pentru factorizarea unui număr este pătratul numărului de biți folosiți pentru a-l reprezenta, care este notat ca n2. Abordarea lui Regev ar necesita doar n1.5 porți deoarece caută factori primi efectuând înmulțiri mai mici ale mai multor numere, mai degrabă decât înmulțiri foarte mari ale unui singur număr. De asemenea, reduce numărul de porți necesare utilizând un algoritm clasic pentru a procesa în continuare ieșirile.

În lucrare, Regev estimează că pentru un număr de 2048 de biți, acest lucru ar putea reduce numărul de porți necesare cu două până la trei ordine de mărime. Dacă este adevărat, asta ar putea permite computerelor cuantice mult mai mici să spargă criptarea RSA.

Cu toate acestea, există limitări practice. Pentru început, Regev observă că algoritmul lui Shor beneficiază de o serie de optimizări dezvoltate de-a lungul anilor care reduc numărul de qubiți necesari pentru a-l rula. Nu este încă clar dacă aceste optimizări ar funcționa pe noua abordare.

A mai spus Martin Ekerå, cercetător în calcul cuantic la guvernul suedez Ştiinţă că algoritmul lui Regev pare să aibă nevoie de memorie cuantică pentru a stoca valori intermediare. Furnizarea acelei memorie va necesita qubiți suplimentari și va reduce orice avantaj computațional pe care îl are.

Cu toate acestea, noua cercetare este un memento în timp util că, atunci când vine vorba de amenințarea calculului cuantic la adresa criptării, stâlpii poartă se mișcă constant, iar trecerea la scheme post-cuantice nu se poate întâmpla suficient de rapid.

Credit imagine: Google

Calculatoarele cuantice ar putea sparge criptarea mai devreme decât se aștepta cu noul algoritm PlatoBlockchain Data Intelligence. Căutare verticală. Ai.

Timestamp-ul:

Mai mult de la Singularity Hub