Come gestire una variabile dict con 2^50 elementi?

Question

Devo trovare gli hash SHA256 di 2^25 stringhe casuali. E poi cerca la collisione (usando il paradosso del compleanno per l'ultimo, diciamo, solo 50 bit dell'hash).

Sto memorizzando la stringa: hash pair in una variabile dict. Quindi ordina la variabile con i valori (non le chiavi) e quindi cerca la collisione usando un ciclo O (n).

Il problema è che poiché ci sono 2^25 stringhe e i loro 2^25 hash, quindi la variabile dict ha 2^50 valori al suo interno. Questo è ESTREMAMENTE intenso in termini di risorse. Quindi, come faccio a farlo con RAM limitata, ad esempio, circa 1 GB?

Cosa ho già provato:
1. Esecuzione con uno spazio di scambio da 6 GB. Il programma si è svolto durante la notte e non è stato ancora completato. Questo è essenzialmente ancora più lento di una ricerca O (n_square)! Gli hash vengono calcolati con l'utilizzo della RAM di circa 3,2 GB. Ma dopo, quando si tratta del comando sort, la RAM utilizzata inizia a sparare di nuovo! Ho anche se il pitone sorta usi in-Place-Quicksort :(
2. Ho conservato solo gli hash e ha trovato una collisione. Ma non sono riuscito a trovare la stringa corrispondente in quanto non conservarlo.

io non dovrei uso database ecc. Al massimo un file di testo ma non aiuta.Inoltre, sono abbastanza nuovo per Python ma non mi permetto di limitare il livello della tua risposta

PS: questo è un compito. aver trovato le collisioni in meno di un minuto con 300 MB di RAM.Non so se questo è vero.Ho risolto il problema ma la risposta è irraggiungibile! Al lavoro quindi non ho accesso al codice adesso.

Codice:

from Crypto.Hash import SHA256 
import os 
import random 
import string 
from operator import itemgetter 

def shaa(): 

    trun=[] 
    clist={} 
    for i in range(0,33554432): 

     sha=SHA256.new(str(i)).hexdigest() 
     sha=int(bin(int(sha,16))[-50:],2) 
     clist[i]=sha 

    print 'Hashes done.' 

    clist=sorted(clist.items(), key=itemgetter(1)) 
    for i in range(0,33554432): 

     if(clist[i]==clist[i+1]): 
      #print string[i],string[i+1] 
      print clist[i] 
      return 1 
    return 2 

result=2 
while(result==2): 
    result=shaa() 

Answer 1

mi piacerebbe andare per qualcosa di simile:

aperta 16 file (aperto in modo binario dovrebbe andare bene, questo sarà più facile se tutte le tue corde hanno la stessa lunghezza). Genera stringhe e hash e li scrive in un file a seconda dei primi 4 bit dell'hash. Quindi caricare ed elaborare ciascun file separatamente. Ciò ridurrà l'utilizzo della memoria di un fattore di 16. (Naturalmente è possibile utilizzare qualsiasi numero di file purché non si esauriscano gli handle di file. Dovendo aprire e chiudere ogni file su ogni accesso diventerà piuttosto lento).

Se la generazione di stringhe e hash è relativamente economica, non è nemmeno necessario utilizzare i file. Basta fare 16 passaggi, e in ogni passaggio mantenere solo thoses hash i bocconcini superiori di cui corrisponde il numero di pass.

Answer 2

Perché non si utilizza un dizionario da ultimi 50-bit-of-hash a stringa?

Answer 3

Dividere l'hash per esempio in gruppi di 10 caratteri. E nidificano i valori in questo modo si avrà ricerca ricorsiva ma dovrebbe essere più veloce

Answer 4

Un modo per risolvere il problema consiste nell'utilizzare un campo di bit molto lungo, in modo che ogni hash sia mappato su una determinata posizione nel 2^25bit blocco di memoria lungo.

Un modo migliore, ma non 100% -assicurazione per risolvere questo tipo di problemi viene effettuato tramite Bloom filter o altre strutture di dati probabilistiche.

Un filtro Bloom è una struttura di dati probabilistici spazio-efficienti che viene utilizzata per verificare se un elemento è un membro di un set. I falsi positivi sono possibili, ma i falsi negativi non lo sono; cioè una query restituisce "inside set (may be wrong)" o "decisamente non in set".

I filtri di fioritura hanno un forte vantaggio di spazio rispetto ad altre strutture di dati per la rappresentazione di insiemi, come alberi di ricerca binaria autobilanciante, tentativi, tabelle hash o matrici semplici o elenchi collegati delle voci.

Un filtro Bloom con errore 1% richiede solo circa 9,6 bit per elemento, indipendentemente dalla dimensione degli elementi.

Quindi, 9,6 bit per 2^25 elementi, avranno bisogno solo di 38,4 MiB di memoria.

Answer 5

penso che l'intuizione chiave qui - che io mi Ammetto eluso per qualche tempo, fino a quando sono tornato in questo un paio di ore più tardi - è che l'hash sha256 digerire è proprio hash. In altre parole, non è necessario eseguire alcun hashing o creazione di set aggiuntivi. Tutto quello che devi fare è creare una tabella hash personalizzata, usando il digest sha256 come hash. Per risparmiare spazio, non memorizzare le stringhe; è sufficiente creare un array di bit (utilizzando le operazioni di spostamento su numeri interi in una serie di interi creati con table = numpy.zeros(table_size/bits_per_int + 1, dtype='i')) per rilevare le collisioni e quindi salvare le stringhe in collisione in un hast mapping hash alle stringhe per la ricerca in un secondo passaggio.

table_size dovrebbe essere un grande primo - ne ho preso uno leggermente più grande di 2 ** 31, che è stato creato per una tabella 268MB - perché questo produrrà poche nuove collisioni/falsi positivi (introdotti dall'operazione modulo sull'hash). È possibile salvare le stringhe stesse in un file di testo, che può essere ripetuto.

Quindi per qualsiasi stringa, l'indice del bit corrispondente da impostare sarebbe index = int(hashlib.sha256('foo').hexdigest(), base=16) % table_size. Quindi calcolare il major_index = index/bits_in_int e il minor_index = index % bits_in_int, utilizzare le operazioni di spostamento e bit a bit su minor_index per controllare e memorizzare il bit corretto nell'int a table[major_index] e così via.

Ora fare un passaggio attraverso le stringhe. Ogni volta che una stringa genera un hash che esegue il mapping su un bit che è già stato impostato, memorizzare una coppia hash:string in un dizionario. O meglio ancora, memorizzare una coppia hash:[string_list], aggiungendo nuove stringhe all'elenco in caso di collisioni multiple. Ora per qualsiasi coppia di stringhe in collisione (a, b), il dizionario conterrà l'hash e il valore di b. Quindi esegui un secondo passaggio attraverso le stringhe, esegui l'hashing a turno e controlla il dizionario per ogni hash. Se l'hash è nel dizionario e la stringa non è già nell'elenco corrispondente, aggiungere la stringa all'elenco. Alcune delle stringhe nel dizionario non corrisponderanno alle vere collisioni; lo [string_list] per la maggior parte di questi hash sarà solo lungo un elemento e le coppie hash:[string_list] potrebbero essere scartate. Le altre sono probabilmente vere collisioni derivanti dalla stessa funzione hash, piuttosto che dall'operazione modulo. Tuttavia, potresti ancora avere alcuni falsi positivi per estirpare, in quei casi in cui c'era sia un vero che un falso positivo; dovrai ricontrollare gli elenchi risultanti per i falsi positivi.

BasicWolf suggerimento di utilizzare un filtro di fioritura è un buon, e potrebbe risultare in una tabella più piccola. Ma aggiunge molte complicazioni; Non mi sono preoccupato Ho provato il metodo di cui sopra su stringhe con terminazione nuova da '0\n' a '33554431\n' e ho trovato due hash con una sovrapposizione a 54 bit. Ci sono voluti 11 minuti, e l'utilizzo massimo della memoria era di circa 350MB (anche se questo potrebbe essere ridotto.) Ho fatto un po 'di profilazione e ho scoperto che la maggior parte del tempo era spesa per calcolare gli offset per il bit-table.La codifica di questo in c probabilmente fornirebbe un significativo aumento di velocità, pre-hashing e memorizzazione degli hash e anche le stringhe sarebbero d'aiuto.

In realtà, ho cercato di pre-hashing le corde, e sostituito il mio piuttosto ad hoc numpy BitArray-based con un bitarray dal modulo di estensione c-based del same name. Ciò ha ridotto il tempo di esecuzione a poco più di 2 minuti, mantenendo il profilo di memoria di circa 350 MB.

Abbastanza vicino per il lavoro di governo, penso. Poiché si tratta di un compito, non posterò il codice, ma sono lieto di fornire ulteriori suggerimenti.