Calcolo della friabilità di un determinato metodo di crittografia

-1

Presto farò un progetto molto importante per la scuola. L'obiettivo principale del mio progetto è trovare un modo matematico per calcolare la friabilità di un determinato metodo di cifratura del testo cifrato. Esiste un modo per calcolare quanto tempo impiegherebbe un computer per rompere una crittografia RSA o un cifrario Vigenère o anche un cifrario sostitutivo monoalfabetico? Ed è possibile per un computer o per creare un algoritmo (s) per un computer qualcosa di simile all'analisi di frequenza?

    
posta Daniel Yalda 21.11.2014 - 15:59
fonte

1 risposta

2

Per "algoritmi crittografici simmetrici" (crittografia simmetrica, MAC ...), le cose sono semplici: un algoritmo crittografico non-rotto è tale che utilizza una chiave n -bit, e il più veloce il metodo per trovare la chiave è provare tutte le chiavi possibili finché non viene trovato quello giusto (che si chiama ricerca esauriente o forza bruta ). L'algoritmo è detto "non-rotto" proprio perché non esiste un metodo conosciuto più veloce della ricerca esauriente. Con una ricerca esaustiva e una chiave n -bit, il numero medio di tentativi prima di premere il tasto giusto è 2 n -1 . Quindi basta moltiplicare quel numero per il tempo che impiega a provare una chiave, e si ha il tempo di attacco completo. Ricerca approfondita è un problema imbarazzante parallelo , il che significa che con il doppio dei computer la soluzione è due volte più veloce.

Lo sforzo di provare una chiave dipende dall'algoritmo e dal contesto. Ad esempio, per la crittografia con un codice a blocchi, di solito è sufficiente decrittografare un blocco (cosa fatta in poche decine o centinaia di cicli di clock su una CPU) per vedere se il corrispondente blocco decrittografato è plausibile o meno (ad esempio, si conosce il testo in chiaro è un file XML e si cerca l'intestazione XML nel primo blocco). Quando si tenta di rompere un MAC, è necessario ricalcolarlo per ogni chiave, che può essere costoso se il MAC originale è stato calcolato su, ad esempio, un file da 50 MB.

La ricerca esaustiva è l'attacco di scelta sugli algoritmi simmetrici, in cui le chiavi sono solo mazzi di bit e qualsiasi sequenza di bit della giusta dimensione è un possibile valore chiave. Non è così per gli algoritmi asimmetrici come RSA e ECDSA, dove le chiavi hanno una grande struttura matematica interna, e rompere la chiave significa sbrogliare quella struttura, che normalmente può essere fatta molto più velocemente che provare tutte le sequenze di bit. Poiché la matematica è coinvolta, le cose sono piuttosto complesse. Vedi questo sito per le stime dei costi. Nota che si tratta di costo , non solo tempo : a seconda del tipo di cosa che stai tentando di fare, potresti aver bisogno di un sacco di CPU e molta RAM molto veloce.

I crittosistemi dell'era pre-computer, come Vigenere e il suo genere, sono invariabilmente deboli e fragili in una frazione di secondo. Fondamentalmente, tutti i sistemi che erano pratici (un operatore umano poteva eseguirli senza passare un giorno intero a crittografare una frase semplice) erano anche fragili attraverso la pura mente di alcuni individui specializzati ( Edgar Allan Poe si diceva che fosse estremamente bravo in questo tipo di attività). Ciò che un cervello umano potrebbe fare in un giorno indietro nel 19 ° secolo, è ora fattibile in meno di un secondo con un computer. E sì, l'analisi della frequenza e tutta la rottura possono essere completamente automatizzati (un buon esercizio di programmazione, ma niente di concettualmente difficile).

A proposito di Poe, leggi questo . Questo è Poe che spiega (attraverso una breve storia) come rompere un cifrario di sostituzione, in tutta la sua gloria analitica; scrivere tutti i passaggi come un programma per computer è una semplice traduzione dalla prosa di Poe all'aridità della sintassi di un linguaggio di programmazione.

    
risposta data 21.11.2014 - 16:26
fonte