L'esponente pubblico RSA dovrebbe essere solo in {3, 5, 17, 257 o 65537} a causa di considerazioni di sicurezza?

Non esiste alcuna debolezza nota per qualsiasi esponente pubblico breve o lungo per RSA, a patto che l'esponente pubblico sia "corretto" (ovvero relativamente primo a p-1 per tutti i numeri primi p che dividono il modulo).

Se usi un piccolo esponente e non usi alcun padding per la crittografia e cripti lo stesso identico messaggio con più pubblico distinto le chiavi, quindi il tuo messaggio è a rischio: se e = 3 e cripti il messaggio m con le chiavi pubbliche n ₁ , n ₂ e n ₃ , allora hai c _i = m ³ mod n _i per i = 1 a 3 . Tramite il Teorema dei rimanenti cinesi , puoi quindi ricostruire m ³ mod n ₁ n ₂ n ₃ , che risulta essere m ³ (senza alcun modulo) perché n ₁ n ₂ n ₃ è un numero intero maggiore. Un'estrazione di radice cubica (non modulare) è quindi sufficiente per estrarre m .

Il punto debole, qui, è not il piccolo esponente; piuttosto, è l'uso di un padding improprio (vale a dire, nessun padding a tutti) per la crittografia. Il riempimento è molto importante per la sicurezza di RSA, indipendentemente dalla crittografia o dalla firma; se non utilizzi un padding adeguato (come quelli descritti in PKCS # 1 ), allora hai molti punti deboli, e quello delineato nel paragrafo sopra non è il più grande, di gran lunga. Tuttavia, ogni volta che qualcuno fa riferimento a una debolezza correlata all'esponente, egli si riferisce più o meno direttamente a questo evento. È un po 'di tradizione antica e scorretta, che a volte è invertita in una proibizione contro gli eminenti big (poiché è un mito, il mito inverso è anche un mito e non è più - e non meno - - motivata); Credo che questo sia ciò che osservi qui.

Tuttavia, si possono trovare alcuni motivi per cui un grande esponente pubblico deve essere evitato:

• I piccoli esponenti pubblici promuovono l'efficienza (per le operazioni a chiave pubblica).

• Ci sono problemi di sicurezza riguardo al fatto di avere un piccolo esponente privato ; un attacco per il recupero delle chiavi è stato descritto quando la lunghezza dell'esponente privato non supera il 29% della lunghezza dell'esponente pubblico. Quando si vuole forzare l'esponente privato a essere breve (ad esempio per accelerare le operazioni con le chiavi private), è più o meno necessario utilizzare un grande esponente pubblico (grande quanto il modulo); richiedere che l'esponente pubblico sia breve può quindi essere considerato una sorta di contromisura indiretta.

• Alcune implementazioni RSA ampiamente implementate soffocano su grandi esponenti pubblici RSA. Per esempio. il codice RSA in Windows (CryptoAPI, utilizzato da Internet Explorer per HTTPS) insiste sulla codifica dell'esponente pubblico all'interno di una singola parola a 32 bit; non può elaborare una chiave pubblica con un esponente pubblico più grande.

Tuttavia, "i rischi possono essere grandi" sembra la giustificazione generica ("questo è un problema di sicurezza" è il solito modo di dire "non l'abbiamo implementato ma non vogliamo ammettere alcun tipo di pigrizia").

Gli sviluppatori sono semplicemente errati. Non c'è niente di sbagliato con l'esponente 0x4451 (decimale 17489); non crea alcun problema di sicurezza.

Molto tempo fa la gente pensava che i piccoli esponenti fossero un problema, a causa di un attacco che Thomas Pornin spiegava con l'invio dello stesso messaggio a più destinatari. Ma oggi capiamo che gli esponenti non c'entrano nulla; il problema è stato il riempimento improprio. Questi attacchi sono impediti dall'uso corretto del padding. Qualsiasi libreria di crittografia che valga la pena di essere utilizzata correttamente si è ben adattata all'uso di padding adeguato (altrimenti hai problemi ben peggiori).

Quindi non c'è una buona ragione per una libreria crittografica che vieti categoricamente l'uso di quell'esponente.

Detto questo, dal punto di vista delle prestazioni, più l'esponente è piccolo, migliori sono le prestazioni. La scelta migliore è e = 3, perché offre le migliori prestazioni e non ha noti problemi di sicurezza. (In realtà, e = 2 è anche un po 'meglio, ma è anche noto come crittografia Rabin, tuttavia questo schema non è così conosciuto e richiede un codice leggermente diverso, quindi non è ampiamente utilizzato.)

Questi cinque numeri sono primi Fermat .

Poiché sono del tipo 2 ^k + 1, la crittografia è m ^e = m · (( m ² ) ² ... _{k times} ...) ² , che è più semplice e più veloce di esponenziazione con un esponente di dimensioni simili nel caso generale .

Poiché sono i primi, il test che e è coprime a ( p - 1) ( q - 1) è solo un test che e non lo divide.

Quindi è più probabile che si tratti di velocità o di convenzioni piuttosto che di sicurezza. Non che ci sia qualcosa di sbagliato nell'essere efficienti. Ma per sicurezza, chiedi un riferimento come suggerita un'altra risposta .

Vedi anche questo post .

Non sono a conoscenza di alcun motivo per cui l'esponente pubblico di una chiave RSA dovrebbe essere solo nel set {3,5,17,257,65537}. Come accennato, esponenti piccoli come 3 o 5 sono più rischiosi da usare, perché gli effetti negativi degli errori di implementazione (come l'imbottitura inappropriata) possono essere maggiori. Il NIST consente solo esponenti pubblici di dimensioni superiori a 2 ^ 16, ma non conosco un motivo per la loro decisione.

Non dovresti essere soddisfatto dalla risposta fornita dagli sviluppatori della libreria che usi e chiedere un riferimento concreto. Troppo spesso, si scopre che alcuni fogli sono stati fraintesi. Potrei ad esempio immaginare che alcuni sviluppatori leggano la sezione 4 del documento "Possiamo fidarci del software crittografico? Difetti crittografici in GNU Privacy Guard v1.2.3" di Phong Nguyen e giunge a una conclusione errata, come quella riportata sopra. Questo documento nota che quando la chiave pubblica generata da GnuPG risulta essere un valore insolito come 65539, l'utente malintenzionato viene a conoscenza di alcune informazioni sulla chiave segreta. La conclusione è che l'algoritmo di generazione delle chiavi di GnuPG potrebbe essere migliorato, ma non che 65539 sia una chiave pubblica non valida.

Non sono riuscito a trovare alcun riferimento al fatto che altri valori per l'esponente pubblico siano vulnerabili. Per motivi di prestazioni, è consigliabile utilizzare un esponente pubblico vicino a una potenza di 2, in base alla RSA. com guida all'algoritmo RSA

Secondo Wikipedia , il NIST non consente un esponente pubblico inferiore a 65537, poiché gli esponenti più piccoli sono problema se non sono adeguatamente imbottiti.

Per citare il documento del 1997 di Don Coppersmith "Piccole soluzioni alle equazioni polinomiali e vulnerabilità RSA a basso esponente":

RSA encryption with exponent 3 is vulnerable if the opponent knows two-thirds of the message.

Anche se questo potrebbe non essere un problema se viene utilizzato lo schema di padding RSA-OAEP, lo schema di padding PKCS # 1 (che viene fornito come schema di riempimento corretto nelle risposte di seguito) è vulnerabile se viene utilizzato l'esponente pubblico 3. p>