È possibile (e pratico) cercare una stringa per pattern ripetuti a lunghezza arbitraria?

5

Recentemente ho sviluppato un enorme interesse per la crittografia e sto esplorando alcuni dei punti deboli dei codici a blocchi in modalità ECB. Uno scenario di attacco comune riguarda i cookie crittografati, i cui campi possono essere rappresentati come stringhe esadecimali relativamente brevi.

Fino ad ora, mi sono affidato ai miei occhi per individuare blocchi ripetuti, ma questo è piuttosto noioso. Mi chiedo quale tipo di algoritmi (se presente) possa aiutarmi ad automatizzare la mia ricerca di pattern ripetuti all'interno di una stringa.

Qualcuno può indicarmi la giusta direzione?

    
posta blz 05.11.2012 - 10:21
fonte

2 risposte

4

Ci sono due algoritmi ampiamente usati per questo compito: l'Indice di Coincidenza (IC) e il metodo di Kasinski. Googling per entrambi dovrebbe produrre un buon numero di visite. Il metodo di Kasiski è più vecchio - almeno IMO, l'IC è più efficace, specialmente se stai lavorando con una quantità limitata di testo cifrato. Il metodo can di Kasiski funziona bene, ma generalmente richiede più testo cifrato prima che diventi efficace.

Probabilmente dovrei aggiungere: entrambi questi sono realmente destinati ad attaccare i codici di sostituzione polialfabetici. Il primo passo in ciascuno è il tentativo di trovare la lunghezza della chiave utilizzata. Nel tuo caso, lavorando con i codici a blocchi in modalità ECB, probabilmente conosci già la dimensione del blocco (che è probabilmente l'equivalente più vicino della lunghezza della chiave in un cifrario di sostituzione polialfabetico). Quello che ti rimane è in gran parte questione di camminare tra i blocchi e contare quante volte si verifica un blocco per vedere se riesci a trovare le ripetizioni. Stando così le cose, probabilmente è più semplice saltare la maggior parte dell'algoritmo, e basta usare qualcosa come una tabella hash per contare il numero di volte in cui si verificano diversi valori di blocco.

La maggior parte degli algoritmi di ricerca delle stringhe normali (ad es. Knuth-Morris-Pratt, Boyer-Moore-Horspool) sono di scarsa utilità in questa ricerca.

    
risposta data 07.11.2012 - 00:08
fonte
5

Donald Knuth ha scritto molto sulla teoria del pattern matching delle stringhe. Molti algoritmi sono molto efficienti nel tempo e costanti nascoste. Qui puoi trovare alcuni buoni algoritmi:

link

    
risposta data 06.11.2012 - 17:22
fonte

Leggi altre domande sui tag