È male che la mia chiave ed25519 sia così breve rispetto a una chiave RSA?

35

Recentemente ho generato una nuova chiave SSH nel formato ed25519. La chiave pubblica è lunga solo 69 byte, mentre la mia vecchia chiave RSA è di 373 byte.

Dalla mia percezione ed25519 è il formato più recente e sicuro.

Quindi, perché non è meglio qui?

    
posta Alex 24.09.2015 - 16:20
fonte

2 risposte

56

No, più lungo non è migliore.

Lasciami spiegare. In crittografia simmetrica , le chiavi sono solo mazzi di bit e tutte le sequenze di bit sono chiavi valide. Non hanno una struttura interna. Se si utilizzano algoritmi decenti, il migliore attacco possibile su una chiave per la crittografia simmetrica è forza bruta : l'utente malintenzionato tenta tutte le chiavi possibili finché non trova quella giusta. Se la chiave ha n bit, allora ci sono 2 n possibili chiavi, e l'attaccante, in media, troverà quella giusta dopo aver provato metà di essi, ovvero 2 n -1 . Le chiavi più lunghe rendono quindi la forza bruta più dura; in tal caso, più a lungo è meglio.

(Si noti che c'è un limite a questo: quando le chiavi sono sufficientemente lunghe che la forza bruta non è più fattibile, aumentare la lunghezza della chiave non rende le cose "più sicure" in alcun modo significativo. Quindi, per le chiavi simmetriche, più lunghe è meglio fino a quando sono abbastanza lunghi, a quel punto più lungo è solo più lungo.)

RSA e EdDSA si riferiscono alla crittografia asimmetrica dove le cose sono completamente diverse. Una chiave per la crittografia asimmetrica è un oggetto matematico che ha una struttura interna specifica; rompere la chiave consiste nel dipanare quella struttura, e può essere fatto molto più efficientemente rispetto a provare tutte le possibili chiavi private. Prendi nota dei due punti:

  • Contro la forza bruta, ciò che conta non è la lunghezza della chiave pubblica , ma quella della chiave privata , poiché ciò che l'utente malintenzionato vuole è il privato chiave, non la chiave pubblica.

  • La forza bruta non è l'attacco più efficace contro le chiavi utilizzate nella crittografia asimmetrica.

Per le chiavi RSA, l'attacco ha successo mediante il factoring del modulo. La fattorizzazione di interi è un problema a lungo studiato; con l'algoritmo più noto, spezzare una chiave RSA a 2048 bit (cioè una chiave pubblica RSA il cui modulo è un intero di 2048 bit) richiede circa 2 110 o operazioni elementari.

Per le chiavi EdDSA, la chiave pubblica è un punto P su una curva ellittica, tale che P = xG dove x è la chiave privata (un numero intero a 256 bit) e G è un punto di curva convenzionale. L'algoritmo più conosciuto per il recupero di x da P e G richiede circa 2 128 operazioni elementari, cioè più che per una chiave RSA a 2048 bit. In generale, per rompere una chiave pubblica curva ellittica n , lo sforzo è 2 n / 2 .

Rompere la chiave è ben oltre ciò che è fattibile con la tecnologia esistente o prevedibile. Ma in un punto di vista "accademico", la chiave EdDSA è un po 'più strong della chiave RSA; inoltre, le curve ellittiche ti danno più sicurezza per bit (tecnicamente, diciamo che la fattorizzazione dei numeri interi è un problema sub-esponenziale).

Vedi questo sito per ulteriori informazioni su questo argomento.

    
risposta data 24.09.2015 - 16:37
fonte
6

Non sono soddisfatto della mia risposta precedente che ha portato a confondere l'ipotesi sul metodo di compressione usato in ed25519, quindi proverò ancora una volta per coloro che non vogliono saltare sulla matematica della EC (Elliptic Curve ulteriormente) per essere in grado capire perché le chiavi EC sono così brevi da comparare con le chiavi RSA.

Dato che il mio inglese è tutt'altro che perfetto, è meglio che cada qui IMHO link abbastanza buoni a questo argomento.

Per coloro che vogliono veramente capire la "magia" della CE (ma vogliono ancora evitare di cadere profondamente innamorato della matematica) ed essere in grado di capire - "perché la CE può gestire la crittografia più strong di RSA usando chiavi molto più piccole" , - Vi consiglio di leggere l'articolo completo su arstechnica.com " Un primer relativamente facile da comprendere sulla crittografia a curva ellittica "

L'autore illustra l'essenza di EC con immagini che aiutano a comprendere il concetto in pochi passaggi.

BTW,interessanteestrattosuEC:

Youcancomputehowmuchenergyisneededtobreakacryptographicalgorithmandcomparethatwithhowmuchwaterthatenergycouldboil.Thisisakindofacryptographiccarbonfootprint.Bythismeasure,breakinga228-bitRSAkeyrequireslessenergythanittakestoboilateaspoonofwater.Comparatively,breakinga228-bitellipticcurvekeyrequiresenoughenergytoboilallthewateronearth.ForthislevelofsecuritywithRSA,you'dneedakeywith2,380bits.

PerquellichenonvoglionoscavareinternidellaCEsottoilcofano,ConsiglioalmenodileggereeseguireunsommarioriassuntopraticosullacrittografiainSSHchevalelapenadedicaredeltempoaleggerlo.Illinkèqui: secure-secure-shell

Le soluzioni pronte per copiare / incollare (fornite dalla community di github) per vari SO sono qui: WiKi di Secure-Secure-Shell (ma consiglio vivamente di leggere l'articolo precedente su github prima di andare lì)

Risposta precedente:

Q: "The public key is only 69 bytes long while my old RSA key is 373 bytes. So why isn't longer better here?"

Oltre alla spiegazione di Tom "perché le chiavi sono più corte almeno altrettanto ugualmente sicure" - secondo la carta originale di coloro che hanno creato ed25519 da qui: link :

Oltre a "ugualmente sicure" le chiavi corte di ed25519 sono "internamente" compresse . La chiave ed25519 non compressa sarà quasi due volte più lunga.

P.S.

Per evitare confusione o errata interpretazione della compressione dei punti utilizzata in ed25519, è NON una compressione regolare come in un archivio zip (!!!). Grazie a @diagprov per aver aiutato a correggere la mia risposta nei commenti con una buona e semplice spiegazione della compressione dei punti e per il collegamento che descrive compressione punto

Riferimento dal documento sopra (Pagina # 2):

  • Small keys. Public keys consume only 32 bytes. The times for compression and decompression are again included.
    
risposta data 08.04.2016 - 08:50
fonte

Leggi altre domande sui tag