Perché e = 65537 è usato per la maggior parte della crittografia RSA?

L'algoritmo RSA usa l'esponenziazione modulare con numeri molto grandi. Tipicamente, consiste nell'elevare un numero di 2048 bit alla potenza di un altro numero di 2048 bit e dividere con un altro numero di 2048 bit. Questo è un sacco di aritmetica intera. Ciò che viene fatto in pratica per semplificare questo processo è un algoritmo Square-Multiply, dove l'esponente viene "masticato", dei suoi 2048 bit, un bit alla volta. Questo riduce effettivamente il calcolo complessivo da un numero impossibilmente grande di esponenziamenti a circa 2048. Anche all'interno di questo, quando l'esponente è 65537, è uguale a 2**16 + 1, che comprende solo 17 bit - il che significa solo 17 moltiplicazioni modulari. Ci sono solo due bit 1 nella rappresentazione binaria di 65537. Questo semplifica ulteriormente il calcolo.

Inoltre, il calcolo della chiave pubblica viene eseguito principalmente da un dispositivo client, come uno smartphone o un tablet. Date le limitazioni di elaborazione e di potenza di questi dispositivi, ha senso mantenere il calcolo della chiave pubblica il più semplice possibile.

La chiave privata, invece, deve essere complessa - riempiendo il maggior numero possibile di 2048 bit, in modo da renderla impossibile da indovinare. I calcoli della chiave privata sono molto più complicati, e sono eseguiti principalmente dai server, che hanno molta più potenza di calcolo e in molti casi, hanno speciali coprocessori HW per eseguire i calcoli RSA molto velocemente. Ricordate anche che un client è responsabile dell'esecuzione dei propri calcoli della chiave pubblica RSA, mentre il server esegue i calcoli della chiave privata per un gran numero di client che vogliono connettersi con lui.