Efficienza del RSA (Rivest Shamir Adleman)

RSA

In crittografia la sigla RSA indica un algoritmo di crittografia asimmetrica, inventato nel 1977 da Ronald Rivest, Adi Shamir e Leonard Adleman utilizzabile per cifrare o firmare informazioni.

Il sistema di crittografia si basa sull’esistenza di due chiavi distinte, che vengono usate per cifrare e decifrare. Se la prima chiave viene usata per la cifratura, la seconda deve necessariamente essere utilizzata per la decifratura e viceversa. La questione fondamentale è che, nonostante le due chiavi siano fra loro dipendenti, non è possibile risalire dall’una all’altra, in modo che se anche si è a conoscenza di una delle due chiavi, non si possa risalire all’altra, garantendo in questo modo l’integrità della crittografia.

Per realizzare un sistema crittografico pubblico con il cifrario asimmetrico è importante che un utente si crei autonomamente entrambe le chiavi, denominate “diretta” e “inversa”, e ne renda pubblica una soltanto. Così facendo si viene a creare una sorta di “elenco telefonico” a disposizione di tutti gli utenti, che raggruppa tutte le chiavi dirette, mentre quelle inverse saranno tenute segrete dagli utenti che le hanno create e da questi utilizzate solo quando ricevono un messaggio cifrato con la rispettiva chiave pubblica dell'”elenco” da parte di un certo mittente, ottenendo in questo modo i presupposti necessari alla sicurezza del sistema.

Per ottenere una discreta sicurezza è necessario utilizzare chiavi binarie di almeno 2048 bit. Quelle a 512 bit sono ricavabili in poche ore.

Efficienza RSA

Dal punto di vista prestazionale (efficienza RSA), l’algoritmo crittografico RSA presenta un tempo di calcolo per la fase di crittazione che è di un ordine di grandezza pari a O(k²), la fase di decrittazione O(k³), mentre la generazione delle chiavi O(k⁴) dove k è la grandezza in bit del numero da cifrare.

È interessante notare come gli algoritmi a chiave pubblica siano sensibilmente più lenti di quelli a chiave privata: infatti, confrontando le prestazioni, si scopre che l’algoritmo DES, nella realizzazione software, è almeno 100 volte più veloce dell’RSA, mentre nella realizzazione hardware si arriva ad una differenza di velocità di circa 1000 o addirittura 10000 volte. Per questo motivo gli algoritmi a chiave pubblica vengono utilizzati, solitamente, solo nella fase iniziale di handshaking della transazione, durante la quale le parti si scambiano una chiave detta di “sessione” utilizzata per la crittazione dei dati durante la trasmissione tra algoritmi a chiave segreta (o chiave simmetrica).

Per quanto riguarda la sicurezza dell’algoritmo RSA si veda l’articolo: Sicurezza del RSA (Rivest Shamir Adleman).