algoritmo RSA (Rivest-Shamir-Adleman) (Italiano)
L’algoritmo RSA è la base di un criptosistema — una suite di algoritmi di crittografia che sono utilizzati per specifici servizi di sicurezza o scopi, che consente la crittografia a chiave pubblica ed è ampiamente usato per proteggere dati sensibili, in particolare quando viene inviato su una rete non sicura, come la rete internet.,
RSA è stato descritto pubblicamente nel 1977 da Ron Rivest, Adi Shamir e Leonard Adleman del Massachusetts Institute of Technology, anche se la creazione di un algoritmo a chiave pubblica da parte del matematico britannico Clifford Cocks è stata mantenuta classificata dal GCHQ del Regno Unito fino al 1997.
La crittografia a chiave pubblica, nota anche come crittografia asimmetrica, utilizza due chiavi diverse ma collegate matematicamente: una pubblica e una privata. La chiave pubblica può essere condivisa con tutti, mentre la chiave privata deve essere mantenuta segreta.,
Nella crittografia RSA, sia la chiave pubblica che quella privata possono crittografare un messaggio; la chiave opposta a quella utilizzata per crittografare un messaggio viene utilizzata per decrittografarlo. Questo attributo è uno dei motivi per cui RSA è diventato l’algoritmo asimmetrico più utilizzato: fornisce un metodo per assicurare la riservatezza, l’integrità, l’autenticità e il non ripudio delle comunicazioni elettroniche e dell’archiviazione dei dati.
Molti protocolli come secure shell, OpenPGP, S/MIME e SSL / TLS si basano su RSA per le funzioni di crittografia e firma digitale., Viene anche utilizzato nei programmi software-i browser sono un esempio ovvio, in quanto devono stabilire una connessione sicura su una rete non sicura, come Internet, o convalidare una firma digitale. La verifica della firma RSA è una delle operazioni più comunemente eseguite nei sistemi connessi alla rete.
Perché viene utilizzato l’algoritmo RSA
RSA deriva la sua sicurezza dalla difficoltà di factoring grandi numeri interi che sono il prodotto di due grandi numeri primi., Moltiplicare questi due numeri è facile, ma determinare i numeri primi originali dal totale – o factoring-è considerato irrealizzabile a causa del tempo che ci vorrebbe usando anche i supercomputer di oggi.
L’algoritmo di generazione di chiavi pubbliche e private è la parte più complessa della crittografia RSA. Due grandi numeri primi, p e q, vengono generati utilizzando l’algoritmo di test di primalità Rabin-Miller. Un modulo, n, viene calcolato moltiplicando p e q. Questo numero viene utilizzato sia dalle chiavi pubbliche che da quelle private e fornisce il collegamento tra di esse., La sua lunghezza, solitamente espressa in bit, è chiamata lunghezza della chiave.
La chiave pubblica è costituita dal modulo n e da un esponente pubblico, e, che normalmente è impostato su 65537, poiché è un numero primo non troppo grande. La figura e non deve essere un numero primo selezionato segretamente, poiché la chiave pubblica è condivisa con tutti.
La chiave privata è costituita dal modulo n e dall’esponente privato d, che viene calcolato utilizzando l’algoritmo Euclideo esteso per trovare l’inverso moltiplicativo rispetto al totiente di n.,
Continua a leggere o guarda il video qui sotto per una spiegazione più dettagliata di come funziona l’algoritmo RSA.
Come funziona l’algoritmo RSA?
Alice genera le sue chiavi RSA selezionando due numeri primi: p = 11 e q = 13. Il modulo è n = p×q=143. Il totiente è n ((n)=(p−1)x (q−1)=120. Sceglie 7 per la sua chiave pubblica RSA e e calcola la sua chiave privata RSA usando l’algoritmo Euclideo esteso, che le dà 103.
Bob vuole inviare ad Alice un messaggio criptato, M, così ottiene la sua chiave pubblica RSA (n, e) che, in questo esempio, è (143, 7)., Il suo messaggio di testo non crittografato è proprio il numero 9 ed è codificato in un testo cifrato C, come segue:
a Me mod n = 97 mod 143 = 48 = C
Quando Alice riceve il messaggio di Bob, ha decifra usando la sua chiave privata RSA (d, n) come segue:
Cd mod n = 48103 mod 143 = 9 = M
utilizzo Di chiavi RSA per firmare digitalmente un messaggio, Alice avrebbe bisogno di creare un hash — un messaggio digest del messaggio Bob — encrypt il valore di hash con la sua chiave privata RSA, e aggiungere la chiave del messaggio., Bob può quindi verificare che il messaggio sia stato inviato da Alice e non sia stato modificato decifrando il valore hash con la sua chiave pubblica. Se questo valore corrisponde all’hash del messaggio originale, solo Alice avrebbe potuto inviarlo-autenticazione e non ripudio-e il messaggio è esattamente come lo ha scritto-integrità.
Alice potrebbe, ovviamente, crittografare il suo messaggio con la chiave pubblica RSA di Bob-riservatezza-prima di inviarlo a Bob. Un certificato digitale contiene informazioni che identificano il proprietario del certificato e contiene anche la chiave pubblica del proprietario., I certificati sono firmati dall’autorità di certificazione che li emette e possono semplificare il processo di ottenimento delle chiavi pubbliche e verifica del proprietario.
RSA security
RSA security si basa sulla difficoltà computazionale del factoring di interi di grandi dimensioni. Man mano che la potenza di calcolo aumenta e vengono scoperti algoritmi di factoring più efficienti, aumenta anche la capacità di calcolare numeri sempre più grandi.
La forza di crittografia è direttamente legata alla dimensione della chiave e il raddoppio della lunghezza della chiave può fornire un aumento esponenziale della forza, sebbene comprometta le prestazioni., Le chiavi RSA sono in genere lunghe 1024 o 2048 bit, ma gli esperti ritengono che le chiavi a 1024 bit non siano più completamente sicure contro tutti gli attacchi. Questo è il motivo per cui il governo e alcune industrie si stanno muovendo per una lunghezza chiave minima di 2048 bit.
Salvo una svolta imprevista nel calcolo quantistico, ci vorranno molti anni prima che siano necessarie chiavi più lunghe, ma la crittografia a curva ellittica (ECC) sta guadagnando il favore di molti esperti di sicurezza come alternativa a RSA per implementare la crittografia a chiave pubblica. Può creare chiavi crittografiche più veloci, più piccole ed efficienti.,
Hardware e software moderni sono ECC-ready, e la sua popolarità è destinata a crescere, in quanto può fornire una sicurezza equivalente con minore potenza di calcolo e l’utilizzo delle risorse della batteria, che lo rende più adatto per le applicazioni mobili di RSA. Infine, un team di ricercatori, che comprendeva Adi Shamir, un co-inventore di RSA, ha creato con successo una chiave RSA a 4096 bit utilizzando la crittanalisi acustica; tuttavia, qualsiasi algoritmo di crittografia è vulnerabile agli attacchi.