Quale schema asimmetrico fornisce la firma più breve, pur essendo sicuro?

Non è possibile avere uno schema di firma sicuro in meno di 50 bit. Dimostrazione: l'utente malintenzionato può enumerare tutte le sequenze di 50 bit finché non viene trovata una corrispondenza. In effetti, un punto delle firme digitali è che l'algoritmo verification può essere calcolato da tutti, poiché utilizza solo la chiave pubblica (che, per definizione, è pubblica).

Il meglio che puoi sperare, in teoria, è la firma dei bit n per una sicurezza di 2 ⁿ . La soglia di inflibilità tradizionale era n = 80 bit, ma l'inesorabile progresso della tecnologia tende a risollevarlo. I crittografi moderni tendono a saltare a 128 bit, perché è un potere di due, quindi bello (nonostante Kant, la maggior parte dei giudizi estetici sono relativi). 100 bit dovrebbero essere al sicuro per un bel po 'di tempo, però.

Tra gli algoritmi di firma noti che si ritiene siano sicuri, BLS è al momento il migliore della classe ; produrrà firme di dimensioni 2n bit per un livello di sicurezza di 2 ⁿ , quindi stai contemplando firme di dimensioni da 160 a 200 bit almeno . Ci sono algoritmi che possono andare al di sotto (fino a circa 1.4 * n ) ma hanno una storia piuttosto lunga di rottura e fissazione e rottura di nuovo (sto parlando di SFLASH e del suo genere), quindi il loro uso non è veramente raccomandato e non esiste uno standard direttamente utilizzabile.

Un'altra possibilità è usare RSA con padding ISO / IEC 9796-2 . Come mostra l'articolo collegato, ci sono alcune sottigliezze riguardo al suo utilizzo. Questo schema di firma è uno schema "con ripristino" che significa che mentre la firma è piuttosto ingombrante (1024 bit se si utilizza una chiave RSA a 1024 bit), può anche incorporare alcuni dei dati firmati; quindi, se il tuo problema riguarda l'aggiunta di una firma a un messaggio, questo schema genererà un sovraccarico relativamente basso. Come spiegato nell'articolo, ottieni una protezione 2 ⁶¹ per un overhead di firma di 22 byte, ovvero 176 bit; per ottenere una buona sicurezza, dovresti usare una funzione di hash con una dimensione di uscita di, diciamo, 224 bit, che porta a un overhead di firma di 240 bit - non buono come i 200 bit di un BLS di forza equivalente, ma meglio rispetto ai 400 bit di DSA o ECDSA (per lo stesso livello di intensità).

Il problema con una firma breve è che rende più facile ottenere una collisione. Inoltre, non è altrettanto facile renderlo troppo lungo da eseguire (utilizzando un hash lento o iterazioni in aumento) poiché la dimensione del file può variare in base agli ordini di grandezza. Se lo fai abbastanza lentamente da firmare "salve", allora sarà davvero difficile firmare una versione sfocata di 50 gigabyte. Pertanto, l'opzione più semplice che ci rimane è quella di aumentare il numero di bit e quindi aumentare il numero di tentativi richiesti per ottenere una collisione se l'algoritmo non è altrimenti rotto.

Vale anche la pena notare che la dimensione della chiave non ha nulla a che fare con la dimensione della firma. La dimensione dell'hash è ciò che determina la dimensione della firma perché una firma è un hash del file che viene quindi crittografato con la chiave privata in modo tale che la chiave pubblica possa decodificarlo e confrontarlo con il proprio calcolo dell'hash. Finché non utilizzi uno schema di crittografia che richiede il riempimento, la lunghezza della firma è completamente indipendente dalla dimensione della chiave.

Modifica: Ok, per la domanda aggiornata sembra che tu non stia effettivamente cercando una firma. Una firma prende un hash di un file e quindi lo crittografa con la chiave privata, quindi a) altri possono verificare che il file non sia cambiato e b) altri possono verificare che tu lo attesti. Funziona perché qualcuno non può creare un altro file che si adatti allo stesso valore di hash.

Quello che stai cercando è una sfida / risposta in grado di verificare che la chiave sia trattenuta dalla persona che sta cercando di entrare. Questo è generalmente fatto con una chiave simmetrica piuttosto che una chiave asimmetrica e un timestamp è crittografato e quindi hash per ridurre la lunghezza. Il problema è che l'hash per ridurre la lunghezza genererà un sistema pubblico / privato perché entrambe le parti devono essere in grado di eseguire l'azione. Suppongo che un breve output possa essere derivato da una firma di chiave privata, ma ho la sensazione che sarebbe significativamente più debole (nessuna ragione dimostrabile, ma non è stato fatto per quello che ne so) che usare una chiave simmetrica.

Il risultato più recente in questa direzione è il titolo intitolato " Le firme più corte di sempre " (ePrint: 2016 / 911), che utilizza la crittografia multivariata. Sostiene di ottenere le firme a 110 bit al livello di sicurezza a 80 bit. Tuttavia, lo schema presenta i seguenti inconvenienti:

• Assunzione di sicurezza relativamente non testata (rispetto a (EC) DSA / BLS)
• Rendimenti decrescenti a livelli di sicurezza più elevati (ad esempio, la sicurezza a 100 bit richiede 171 bit)
• Tempo di verifica lento per le firme più piccole (~ 1 secondo)
• Chiave pubblica relativamente grande (da 25 a 100 kilobyte)

Un vantaggio potenziale, oltre alle dimensioni di firma brevi, è:

• Si crede che la crittografia multivariata sia più resistente agli attacchi quantici rispetto alla (EC) DSA / BLS

Se hai davvero bisogno di firme molto brevi e puoi vivere con gli svantaggi, allora potresti provarlo. Si noti tuttavia che la crittografia, per sua natura, è un soggetto conservatore; stai molto meglio attenendoti a uno schema collaudato a meno che tu non abbia davvero bisogno di altro.

Un'alternativa a (EC) DSA è lo schema di firma Schnoor, che nella sua forma originale riduce la dimensione della firma da 4t-bit a 3t-bit per le congetture 2 ^t -bit sicurezza e al massimo 2 firme ^{t / 2} per chiave. Ad esempio, a livello di sicurezza a 96 bit, una firma richiede 36 byte.

La descrizione di riferimento è: Claus-Peter Schnorr, Generazione di firme efficiente da Smart Cards , in Journal of criptology, 1991 . Lo schema è noto per essere applicabile a qualsiasi gruppo di ordine $ q $ in cui il problema DL è difficile.

Discuto alcune possibili varianti in questa domanda :

• sbarazzarsi dell'RNG utilizzato per la firma, ovvero una debolezza comprovata del (EC) DSA e simili, sostituendolo con un MAC deterministico, come in Ed25519 ;
• utilizzando gli hash salati con la chiave pubblica / l'ID utente;
• reinghing l'hash t-bit a 2t-bit prima dell'uso.

Le ultime due modifiche mirano a argomenti di sicurezza più forti (lo stretto hash pubblico t-bit è tra due hash salati); fanno non mirano a rimuovere un punto debole in una configurazione specifica.