Un team internazionale di scienziati informatici ha stabilito un nuovo record per due dei più importanti problemi computazionali che sono alla base di quasi tutta la crittografia a chiave pubblica attualmente utilizzata nel mondo reale.

La crittografia a chiave pubblica viene utilizzata in numerose applicazioni, tra cui la crittografia di dati sensibili e riservati e firme digitali. Nella crittografia a chiave pubblica, le chiavi arrivano in coppia, un pubblico, e uno privato, e la sicurezza dello schema di crittografia o firma digitale si basa sul fatto che si ritiene che sia computazionalmente intrattabile calcolare la chiave privata dalla chiave pubblica. Il factoring e il logaritmo discreto sono due di questi problemi fondamentali che si ritiene siano difficili da risolvere.

Il team ha preso in considerazione la chiave più grande finora, un intero a 795 bit, e ha anche calcolato un logaritmo discreto di un numero intero a 795 bit. In totale, questo ha richiesto loro circa 35 milioni di ore di tempo di calcolo.

Le dimensioni delle chiavi interrotte da questo calcolo di record non vengono generalmente utilizzate nella pratica dalle moderne applicazioni crittografiche. Però, il raggiungimento di record computazionali regolari è necessario per aggiornare i parametri di sicurezza crittografica e le raccomandazioni sulla dimensione della chiave.

Grazie ai progressi algoritmici, questi calcoli sono stati ottenuti utilizzando una potenza di calcolo molto inferiore a quella stimata sulla base di registrazioni precedenti o della legge di Moore.

I record precedenti erano 768 bit in entrambi i casi. Il precedente record di fattorizzazione risale al 2010, e il precedente record di logaritmo discreto datato 2016.

Poiché sia ​​i record computazionali per il factoring che i log discreti sono stati ottenuti simultaneamente per gli interi della stessa dimensione e sullo stesso hardware computazionale, questo lavoro influenza la comprensione della comunità scientifica sulla relativa difficoltà di questi due problemi. Si credeva comunemente che il problema del logaritmo discreto fosse almeno 10 volte più difficile del factoring. Questo lavoro mostra che la differenza è molto minore, nell'ordine di un fattore tre.