hashing stesso carattere più volte

Question

sto facendo una sfida di programmazione e sto impazzendo con una delle sfide. Nella sfida, ho bisogno di calcolare l'MD5 di una stringa. La stringa è data nel seguente formato:

n[c]: dove n è un numero e c è un carattere. Ad esempio: b3[a2[c]] =>baccaccacc

Tutto è andato bene fino a quando mi è stata data la seguente stringa:

1[2[3[4[5[6[7[8[9[10[11[12[13[a]]]]]]]]]]]]]

Questa stringhe si trasforma in una stringa con 6227020800 a 's. Questa stringa è più di 6 GB, quindi è quasi impossibile calcolarla in tempo reale. Quindi, ecco la mia domanda:

Ci sono delle proprietà di MD5 che posso usare qui?

So che deve esserci un modulo per farlo in breve tempo, e sospetto che debba essere correlato al fatto che tutta la stringa abbia lo stesso carattere ripetuto più volte.

Answer 1

Probabilmente è stata creata una funzione (ricorsiva) per produrre il risultato come valore singolo. Invece dovresti usare un generatore per produrre il risultato come flusso di byte. Questi puoi quindi alimentare byte per byte nella tua routine hash MD5. La dimensione del flusso non ha importanza in questo modo, avrà solo un impatto sul tempo di calcolo, non sulla memoria utilizzata.

Ecco un esempio utilizzando un parser single-pass:

import re, sys, md5 

def p(s, pos, callBack): 
    while pos < len(s): 
    m = re.match(r'(d+)[', s[pos:]) 
    if m: # repetition? 
     number = m.group(1) 
     for i in range(int(number)): 
     endPos = p(s, pos+len(number)+1, callBack) 
     pos = endPos 
    elif s[pos] == ']': 
     return pos + 1 
    else: 
     callBack(s[pos]) 
     pos += 1 
    return pos + 1 

digest = md5.new() 
def feed(s): 
    digest.update(s) 
    sys.stdout.write(s) 
    sys.stdout.flush() 

end = p(sys.argv[1], 0, feed) 
print 
print "MD5:", digest.hexdigest() 
print "finished parsing input at pos", end 

Answer 2

Tutte le funzioni di hash sono progettati per funzionare con flussi di byte, quindi non si deve innanzitutto generare l'intera stringa, e dopo che hash esso - si dovrebbe generatore di scrittura, che produce blocchi di dati stringa e li alimenta al contesto MD5. E, MD5 utilizza un buffer a 64 byte (o char), quindi sarebbe una buona idea alimentare i blocchi di 64 byte di dati nel contesto.

Answer 3

approfittare delle buone proprietà di hash:

import hashlib 
cruncher = hashlib.md5() 
chunk = 'a' * 100 
for i in xrange(100000): 
    cruncher.update(chunk) 
print cruncher.hexdigest() 

modificare il numero di giri (x = 10000) e la lunghezza dello spezzone (y = 100) in modo che x * y = 13 !. Il punto è che stai alimentando l'algoritmo con dei pezzi della tua stringa (ognuno dei quali x caratteri), uno dopo l'altro, per y volte.