Crittografia: bug nella generazione delle chiavi pubbliche tramite RSA

lucchettoL’Electronic Frontier Foundation’s SSL Observatory è un progetto che si occupa di raccogliere e analizzare i certificati usati per la crittografia di siti internet tramite HTTPS. I tecnici verificano la vulnerabilità di tutti i certificati SSL pubblici e documentano il lavoro delle autorità di certificazione, fornendo così dati utili sulle infrastrutture di crittografia ai ricercatori interessati.

Utilizzando i dati dell’osservatorio, un team di ricercatori americani ed europei guidato da Lenstra del Politecnico di Losanna ha effettuato un controllo delle chiavi pubbliche utilizzate per la crittografia HTTPS. Il gruppo di ricercatori ha scoperto che migliaia di chiavi basate sull’algoritmo RSA (il più usato online) non offrono una sicurezza efficace a causa di errori negli algoritmi di generazione di numeri casuali.

L’algoritmo RSA si basa su due diverse chiavi, una pubblica che viene usata per cifrare e una privata usata per decifrare.
Ma in pratica come funziona? Spieghiamolo velocemente.
Otteniamo la chiave pubblica moltiplicando tra loro due numeri primi molto grandi e rendiamola nota a tutti. Chiunque può scrivere un messaggio e cifrarlo utilizzando la nostra chiave pubblica. Quando il messaggio cifrato ci verrà inviato tutti potranno vederlo, ma nessuno potrà decifrarlo perché non avrà a disposizione la chiave privata. Noi, invece, essendo a conoscenza dei due numeri primi utilizzati per la creazione della chiave pubblica possiamo decifrare facilmente il codice.
Come si può evincere dalla spiegazione è fondamentale che nessun altro all’infuori del creatore della chiave pubblica conosca i fattori di partenza e che questi ultimi siano generati in modo casuale, così da garantire l’integrità della crittografia.

È proprio questo il problema riscontrato dai crittografi: i sistemi che generano i numeri primi non sono infallibili e a volte i numeri non sono davvero casuali. Per dimostrare la loro teoria, i ricercatori hanno effettuato un test su 7milioni di chiavi pubbliche e sono risaliti ai fattori di ben 27mila di queste.
Il problema si fa ancora più serio se pensiamo che per eseguire il test e risalire alle chiavi private, ai ricercatori, è bastato utilizzare l’algoritmo di Euclide (lo stesso del calcolo del MCD) e che c’è quindi un alta probabilità che già qualcun altro sia arrivato a scoprire questa falla.

Non si conoscono ancora i motivi per cui diversi software di crittografia siano risultati imperfetti, ma le conseguenze sono molto gravi. Informazioni riservate come password o messaggi potrebbero essere alla portata di tutti e questo mette a rischio i sistemi di banking online, di ecommerce e di posta elettronica.

Lo studio verrà reso ufficiale ad una conferenza sulla crittografia che si terrà in agosto in California, ma i ricercatori hanno pensato di rendere pubblica immediatamente la loro ricerca per rendere noto il problema a tutti.

Speriamo che tutti i bug relativi alla crittografia siano trovati e risolti al più presto, in modo da garantire sicurezza e riservatezza a tutti gli utenti del web.

Lascia un commento

Tutti i campi sono obbligatori.
L'indirizzo email non verrà pubblicato

 

Commenti

  1. avatarTEO

    Questo commento è rivolto a Tania Severini, quale autrice dell’articolo CRITTOGRAFIA: BUG NELLA GENERAZIONE DELLE CHIAVI PUBBLICHE TRAMITE RSA.
    Per poter avere disponibile un numero primo il più possibile random si è proceduto come segue:
    1) si è realizzato un programma di ricerca numeri primi, ciascuno costituito di almeno 160 cifre decimali, tramite l’algoritmo probabilistico di Rabin – Miller;
    2) come numero iniziale si è introdotto un numero sempre di 160 cifre battendo in modo casuale sulla tastiera ciascuna delle 160 cifre decimali;
    3) con l’ausilio del suddetto algoritmo si è trovato il primo numero primo successivo al numero di cui al punto 2);
    4) il numero delle Basi utilizzate per trovare tale numero primo sono state 25, per cui il numero primo trovato ha una probabilità inferiore allo 0.000000000000001 di non esserlo.
    Ciò che chiedo all’autrice dell’articolo: il numero primo così trovato si può prendere in considerazione come effettivamente random?

  2. avatarTania Severini Autore

    Ciao,
    non essendo una matematica, nel mio post, ho cercato di non entrare nello specifico delle procedure per la generazione di chiavi random, riportando solamente una notizia che mi aveva incuriosita e che pensavo potesse interessare ai nostri lettori. Quindi, per avere una risposta esaustiva alla tua domanda, ti consiglio di rivolgerti a matematici esperti (ad esempio su math.stackexchange.com).

    Spero di esserti stata d’aiuto e, per finire, ti riporto una contro-domanda suggeritami da un mio collega:
    “Dato che il numero di base dipende da un input dell’utente totalmente casuale, anche il risultato può ritenersi effettivamente random, ma forse la vera domanda dovrebbe essere: quanto è altra la probabilità che il numero primo trovato sia sempre diverso?”

  3. avatarcris

    ora essenzialmente questa è una domanda che mi sono sempre posto
    la distanza dei numeri primi si dice che aumenti tra loro in relazione proprio al numero dei decimali di cui è composto per meglio dire se tra 2 e 100 i primi sono 25 tra 100 e 200 sono 20 e questa è una condizione costantemente in ribasso ,che è proprio quello che dimostrò Gauss,oggi infatti per scoprire i primi si devono testare numeri infiniti composti a volte da decine di milioni di decimali ,per ogni tanto scoprirne uno ,che cmq”ha il suo clamore mediatico” perlomeno tra i matematici.la domanda è questa in una trasmissione a 2048 bit dove i numeri primi da moltiplicare sono composti da 180–230 cifre decimali ma l’intervallo o la frequenza dei numerid primi quale potrà mai essere ??? di 2000 3000 numeri da testare,
    nel momento che prendo un numero composito e lo fattorizzo per tutti i numeri primi che ricascano nel range che ovviamente devo intercettare e avendo un grande data base dove custodisco tutti i primi conosciuti .riesco a trovare la soluzione a rsa per fattorizzare serve solo un numero primo perchè trovato uno mi basterà dividerlo per il numero generato e quando il risultato sara un’altro primo quella e solo quella sarà la soluzione
    io ho sempre pensato che però questo non sia un bug o un errore ,ma che invece sia la porta di accesso che usano le grandi agenzie come NSA per poter controllare il tutto …loro hanno gli strumenti e i metodi per poter fare certe cose
    un’altro po cel’ho pure io!!!!(si fa per dire ovviamente)
    a quel punto si calcola la costante di decodifica con 4 operazioni abbastanza semplici e si ha la chiave per decriptare i codici di accesso di tutto conti bancari informazioni sensibili ect
    il grosso del lavoro non è stato progettare l’algoritmo ma convincere il grande pubblico che è un sistema sicuramente impossibile da analizzare da normali pc o normali persone
    ma che cmq da il potere a grandi agenzie di sapere con certezza cosa uno stia facendo e non parlo di cose personali ma piuttosto arrivare a conscere segreti di stato ordini di servizio che vengono impartiti ect ,,,,,,rendendoci vulnerabili a tutto
    voi che ne pensate ho ragione io???oppure sto omettendo delle cose ??

  4. avatarcris

    quello che si dice nell’articolo è giusto perche da un numero molto grande che viene fattorizzato essendo un numero detto ottale il risultato sara sempre composto da due grandi primi ….molto grandi ma non tropo distanti tra loro in bit
    quindi come da esempio il numero rsa challlenger 100 era cosi compsto:
    RSA-100 = 15226050279225333605356183781326374297180681149613
    80688657908494580122963258952897654000350692006139

    i suoi fattori …quindi i primi tra loro moltiplicati erano:
    RSA-100 = 37975227936943673922808872755445627854565536638199
    * 40094690950920881030683735292761468389214899724061

    come noterete sono 2 numeri composti dallo stesso numero di decimali
    se il numero fosse stato veramente random poteva essere anche fatto così:234567 *234567234567234567234567234567234567
    il risultato di tale numero che non so se sia formato veramente da 2 primi sarebbe questo
    55021732510732510732510732510732510677489
    ora provate a fattorizzare questo se ci riuscite minimo vi servono 3 /4 mesi e il risultato sarebbe sempre e cmq solo compsto dai 2 numeri “primi” che lo hanno generato ora vi presento la mia teoria

    55021732510732510732510732510732510677489 : 234567 =234567234567234567234567234567234567

    55021732510732510732510732510732510677489
    : 234567234567234567234567234567234567
    =234567
    basterà conoscere la chiave pubblica
    scansionare i numeri range che un computer potrebbe fare in 30 secondi ma anche tutti dal 2 in poi e il primo numero che da come risultato un’altro primo sara la chiave privata
    non smetterò mai di pensare che sia sempre stato così e che la stessa forza dell’intelligents americana sia basata su questo

  5. avatarFrancesco Di Noto

    La crittografia RSA sembra proprio che cominci a scricchiolare…
    Dal prossimo anno infatti tutte le chiavi pubbliche con meno di 600 cifre saranno sostituite da numeri con più di 600 cifre, i cosiddetti numeri RSA – 2048, per i quali la teoria computazionale prevede 15 miliardi di anni per la loro violazione. Noi possiamo dimostrare che si può ridurre tale tempo ad un terzo, cioè a 5 miliardi di anni, ma è una magra consolazione, sono sempre troppi! Con i futuri computer quantistici ancora in fase sperimentale si ridurrebbe a 15 anni, e con la nostra scorciatoia a soli 5 anni, ma sono sempre troppi! Sarebbe comunque bene, per la Società RSA , correre ai ripari. Proporrei all’Istituto Clay, quello dei problemi del Millennio, di sostituire la congettura di Poincarè, ormai dimostrata dal russo Perlmann , che ha rifiutato il premio di un milione di dollari (mah!), con un nuovo problema: un nuovo metodo matematico che salvi la stessa RSA da possibili violazioni, rendendola molto più sicura, anche più della concorrente crittografia ECC (curve ellittiche) attualmente dieci volte più sicura della RSA a parità di lunghezza delle sue chiavi pubbliche. Francesco

  6. avatarFrancesco Di Noto

    Un commento per Cris. I numeri RSA sono prodotti tra due numeri primi di grandezza comparabile tra di loro, cioè in genere con un rapporto inferiore a 2 o poco più di 2, e con lo stesso numero di cifre, quindi mi sembra strano che siano prodotti da un algoritmo random, tranne che tale algoritmo tenga conto di tale rapporto massimo, che peraltro già risulta dai numeri RSA già fattorizzati, reperibili su Wikipedia (RSA Challenger). Quindi anche le chiavi pubbliche vendute a clienti come Banche, eserciti ecc. avranno la stessa caratteristica. Solo se fossero veramente random in assoluto uscirebbero fuori numeri primi come quelli riportati da Cris, con rapporto q/p molto più elevati , con pericolo di facile fattorizzazione, poichè p= 234567 è molto piccolo rispetto a q. Per due numeri primi di grandezza simile, invece, il tempo necessario è molto più lungo. Inoltre non credo che la NSA sappia fattorizzare in tempi ragionevoli i numeri RSA ,
    perchè in tal caso il segreto durerebbe poco (i segreti della bomba atomica, com’è noto, durarono per soli cinque anni); oppure gli americani hanno imparato finalmente a mantenere bene i loro segreti strategici (questo della fattorizzazione dei numeri RSA, se esiste, dura invece da circa 40 anni) L’altra possibilità è che questo segreto ancora non esiste,
    e la crittografia RSA è veramente o ben difficilmente inviolabile, per cui resiste ai tentativi degli hacker.
    Francesco
    .