Continuen els intents de trencar l'algorisme RSA utilitzant ordinadors quàntics. Un grup xinès afirma estar en condicions de trencar l'algorisme RSA-2048.

Els algorismes criptogràfics de clau pública, també coneguts com a criptografia asimètrica, es basen en algorismes matemàtics que actualment no són fàcils de calcular. En altres paraules, l'algorisme és fàcil de manejar en una direcció mentre que és gairebé impossible en l'altra direcció.

L'algorisme RSA es va crear en 1977 a partir del treball dels inventors Ronald Rivest, Adi Shamir i Leonard Adleman (les inicials dels cognoms corresponen a l'abreviatura RSA).

RSA s'usa avui dia en tots els nivells, i sempre que la clau sigui prou llarga i es generi correctament, la informació protegida per RSA està segura.

Alguns algorismes de clau pública utilitzen la factorització d'un nombre enter, un procés al fet que a nivell de càlcul és fàcil de fer però molt difícil de realitzar l'operació inversa. El calculo invers és molt costós a nivell de computació, és a dir, un ordinador normal podria trigar milers d'anys a realitzar el càlcul.

En concret, RSA basa el seu funcionament precisament en la factorització: donat un nombre natural N molt gran, no existeix un mètode ràpid per tornar als dos nombres primers P i Q que, en multiplicar-los, donen com a resultat N. Per tant, si la multiplicació de dos números és una operació molt senzilla de realitzar, la factorització no ho és en absolut i històricament s'ha mantingut com un dels problemes més complexos de calcular.

Pots utilitzar els mètodes d'Euler, Fermat, Dixon i Shor o "força bruta" per intentar factoritzar un nombre. Com hem vist, en el cas d'RSA, si s'han utilitzat claus molt febles, és possible desxifrar un missatge xifrat: recentment un grup d'investigadors va aconseguir fins i tot utilitzar l'antic algorisme de Pierre de Fermat per desxifrar informació protegida amb RSA.

Els ordinadors quàntics estan canviant les regles en el camp de la supercomputació. Els problemes que es poden resoldre amb un ordinador quàntic són, de fet, gran part dels quals no es poden gestionar amb les tecnologies de la informació tradicionals, precisament per l'esmentat cost computacional.

Per tant, factoritzar una clau criptogràfica es torna més que factible amb la computació quàntica.

El NIST (Institut Nacional d'Estàndards i Tecnologia) ens ha recordat repetidament que és recomanable actuar a temps per no trobar-nos en una situació d'emergència amb algorismes criptogràfics considerats assegurances que de sobte es tornen poc de confiança.

Un estudi realitzat per Craig Gidney i Martin Ekerå va demostrar que serien necessaris 20 milions de qubits per factoritzar amb èxit una clau RSA-2048 en només 8 hores.

Sobre el paper, es tracta d'un gran esforç si es té en compte que l'ordinador quàntic IBM Osprey té 433 qubits i que l'empresa espera aconseguir els 4.000 qubits en 2025.

Encara que la intenció d'IBM és desenvolupar ordinadors quàntics amb més qubits, la meta de 20 milions de qubits sembla molt llunyana.

El conegut criptògraf estatunidenc Bruce Schneier crida l'atenció sobre una recerca recentment publicada per un grup d'investigadors xinesos.

Els investigadors xinesos afirmen poder trencar RSA-2048 fins i tot si en la pràctica això encara no s'ha fet. Segons les conclusions de la recerca, només un ordinador quàntic de 372 qubits seria suficient per desxifrar els missatges protegits amb l'algorisme RSA-2048, però el grup xinès afirma que no té un ordinador quàntic tan poderós.

Els autors de la recerca han demostrat que poden factoritzar nombres de 48 bits utilitzant un ordinador quàntic de 10 qbit. Disposar d'un ordinador quàntic de 372 qubits no és impossible ja que ordinador quàntic d'IBM més potent té 433 qubits.

El que han fet els investigadors és combinar les tècniques clàssiques de factorització destinades a reduir la xarxa amb un algorisme d'optimització de tipus quàntic aproximat: d'aquesta manera s'han pogut reduir aquests 20 milions de qubits a tan només 372.

Segons Schneier, el treball de l'equip xinès es basa en l'enfocament del problema de factorització de Peter Schnorr: és un document controvertit perquè descriu un algorisme que funciona bé amb mòduls més petits, aproximadament del mateix ordre que els provats pel grup xinès, però falla a mesura que augmenta la grandària de la clau. El document xinès afirma que les tècniques quàntiques adoptades permeten eludir les limitacions de l'algorisme de Schnorr, però falten diversos elements per resoldre del trencaclosques.

Schneier, escriu que després d'una anàlisi més profunda del treball realitzat per l'equip xinès, no hi ha motius per a la preocupació.