Crittografia RSA violata? O forse no!

Crittografia RSA violata? O forse no!

Timestamp: 6 gennaio 2023 12:59
Criptovaluta RSA crackata? O forse no! Intelligenza dei dati PlatoBlockchain. Ricerca verticale. Ai.
by Paul Ducklin

C'è stato un po' di confusione nei media tecnologici negli ultimi giorni sul fatto che il venerabile sistema crittografico a chiave pubblica noto come RSA potrebbe presto essere decifrabile.

RSA, come probabilmente saprai, è l'abbreviazione di Rivest-Shamir-Adleman, i tre crittografi che hanno ideato quello che si è trasformato in un sistema di crittografia sorprendentemente utile e longevo attraverso il quale due persone possono comunicare in modo sicuro...

…senza incontrarsi prima per concordare una chiave di crittografia segreta.

In poche parole, RSA non ha una chiave, come una serratura tradizionale, ma due chiavi diverse, uno per bloccare la porta e l'altro per sbloccarla.

Puoi generare abbastanza rapidamente un paio di chiavi uno per bloccare e l'altro per sbloccare, ma dato solo uno di essi, non puoi capire come sia l'altro.

Quindi, ne designi uno come "chiave pubblica", che condividi con il mondo, e mantieni l'altro come "chiave privata".

Ciò significa che chiunque desideri inviarti un messaggio privato può bloccarlo con la tua chiave pubblica, ma (supponendo che tratti davvero la tua chiave privata come privata), solo tu puoi sbloccarlo.

Funzionando al contrario, qualcuno che vuole che tu provi la tua identità può inviarti un messaggio e chiederti di bloccarlo con la tua chiave privata e rispedirlo.

Se la tua chiave pubblica lo sblocca correttamente, allora hanno qualche motivo per pensare che tu sia chi dici.

Stiamo ignorando qui i problemi di come garantire che una chiave pubblica appartenga davvero alla persona che pensi, cosa fare se ti rendi conto che la tua chiave privata è stata rubata e numerose altre complessità operative. Il grosso problema è che RSA ha introdotto un sistema a due chiavi in ​​cui una chiave non può essere elaborata dall'altra, in contrasto con il tradizionale sistema a una chiave, con la stessa chiave per bloccare e sbloccare i tuoi segreti, che era stata in uso da secoli.

Crittografia a chiave pubblica

Vedrai questo tipo di processo variamente indicato come crittografia a chiave pubblica, crittografia pubblico-privato, o crittografia asimmetrica (la crittografia simmetrica, come AES, è dove la stessa chiave viene utilizzata per bloccare e sbloccare i tuoi dati).

Infatti, se conosci davvero la tua storia crittografica, potresti anche averla sentita chiamare con il curioso nome di crittografia non segreta (NSE), perché i crittografi nel Regno Unito avevano avuto un'idea simile alcuni anni prima che R, S e A, ma in quella che si è rivelata un'opportunità enormemente persa, il governo britannico ha deciso di sopprimere la scoperta e di non farlo sviluppare o addirittura pubblicare il processo.

Anche se al giorno d'oggi esistono alternative a RSA che consentono di avere chiavi pubbliche e private più piccole e che si basano su algoritmi che funzionano più velocemente, RSA è ancora ampiamente utilizzato e ci sono ancora molti dati potenzialmente decifrabili che si trovano negli archivi, nei file di registro e acquisizioni di rete protette da RSA al momento della trasmissione.

In altre parole, se l'RSA si rivela facilmente decifrabile (almeno per alcuni sensi di facilità), ad esempio perché arriva un Big Fast Quantum Computer, avremmo un ragionevole motivo di preoccupazione.

Bene, come l'esperto di sicurezza informatica Bruce Schneier osservato di recente, un folto gruppo di scienziati informatici cinesi ha appena pubblicato un documento intitolato Fattorizzazione di numeri interi con risorse sublineari su un processore quantistico superconduttore.

Il grosso problema del factoring di numeri interi (dove si capisce, ad esempio, che 15 = 3×5, o che 15538213 x 16860433 = 261980999226229) è che fare proprio questo è alla base del cracking di RSA, che si basa su calcoli che coinvolgono due numeri primi enormi e casuali.

In RSA, tutti conoscono il numero che ottieni quando moltiplichi quei numeri tra loro (chiamato the PRODOTTI), ma solo la persona che originariamente ha inventato i numeri di partenza sa come è stato creato il prodotto: i fattori insieme formano essenzialmente la loro chiave privata.

Quindi, se potessi suddividere nuovamente il prodotto nella sua coppia unica di fattori primari (come sono conosciuti), saresti in grado di decifrare la crittografia di quella persona.

Il fatto è che se i tuoi numeri primi iniziali sono abbastanza grandi (oggigiorno, 1024 bit ciascuno o più, per un prodotto di 2048 bit o più), non avrai abbastanza potenza di calcolo per valutare il prodotto a parte.

A meno che tu non riesca a fabbricare, acquistare o noleggiare un computer quantistico abbastanza potente, cioè.

Grandi prodotti di prima qualità

Apparentemente, il più grande prodotto principale mai scomposto da un computer quantistico è solo 249919 (491 x 509), che il mio laptop di otto anni può gestire in modo convenzionale, incluso il tempo impiegato per caricare il programma e stampare la risposta, in un tempo così breve che la risposta è variamente riportata come 0 millisecondi o 1 millisecondo.

E, come riportano i ricercatori cinesi, i modi standard per avvicinarsi al cracking RSA con un computer quantistico richiederebbero milioni di cosiddetti qubit (bit di tipo computer quantistico), dove il più grande computer di questo tipo conosciuto oggi ha poco più di 400 qubit.

Come puoi vedere, se RSA-2048 ha bisogno di milioni di qubit per rompersi, hai bisogno di caricare più qubit di quanti siano i bit nel numero che vuoi fattorizzare.

Ma i ricercatori suggeriscono di aver trovato un modo per ottimizzare il processo di cracking in modo che richieda non solo meno di un milione di qubit, ma anche meno qubit rispetto al numero di bit nel numero che stai cercando di decifrare:

Stimiamo che un circuito quantistico con 372 qubit fisici e una profondità di migliaia sia necessario per sfidare RSA-2048 usando il nostro algoritmo. Il nostro studio mostra una grande promessa nell'accelerare l'applicazione degli attuali computer quantistici rumorosi e apre la strada alla fattorizzazione di grandi numeri interi di realistico significato crittografico.

La domanda scottante è...

Hanno ragione?

Se disponiamo già di computer con centinaia di qubit, la fine di RSA-100 è proprio dietro l'angolo?

Semplicemente non abbiamo le competenze matematiche per dirtelo - il loro articolo di 32 pagine non è per i deboli di cuore e nemmeno per il generalista matematico - ma il consenso, almeno per ora, sembra essere…

No.

Tuttavia, questo è un ottimo momento per pensare quanto sei pronto per qualsiasi algoritmo di crittografia o hashing improvvisamente trovato carente, per ragioni quantistiche o meno.

Timestamp:

Di più da Sicurezza nuda