Funzione di hash crittografico. Che cos'è l'hash o l'hashing?

Che cos'è un hash? Una funzione hash è una trasformazione matematica di informazioni in una stringa di lunghezza breve e specifica.

Perché è necessario? L'analisi che utilizza le funzioni hash viene spesso utilizzata per controllare l'integrità di file importanti del sistema operativo, programmi importanti e dati importanti. Il controllo può essere effettuato sia secondo necessità che su base regolare.

Come è fatto? Innanzitutto, determinano l'integrità di quali file devono essere monitorati. Per ogni file, il suo valore di hash viene calcolato utilizzando un algoritmo speciale, con il risultato che viene salvato. Dopo il tempo richiesto, viene effettuato un calcolo simile e i risultati vengono confrontati. Se i valori differiscono, le informazioni contenute nel file sono state modificate.

Quali caratteristiche dovrebbe avere una funzione hash?

• deve essere in grado di convertire dati di lunghezza arbitraria in fissi;
• deve avere un algoritmo aperto in modo da poterne indagare la forza crittografica;
• dovrebbe essere unilaterale, cioè non dovrebbe esserci alcuna possibilità matematica di determinare i dati iniziali dal risultato;
• dovrebbe "resistere" alle collisioni, cioè non dovrebbe produrre gli stessi valori per dati di input diversi;
• non dovrebbe richiedere grandi risorse di calcolo;
• al minimo cambiamento dei dati di input, il risultato dovrebbe cambiare in modo significativo.

Quali sono i popolari algoritmi di hashing? Le seguenti funzioni hash sono attualmente in uso:

• CRC - Codice di ridondanza ciclica o checksum. L'algoritmo è abbastanza semplice, ha un gran numero di variazioni a seconda della lunghezza di output richiesta. Non crittografico!
• MD 5 è un algoritmo molto popolare. Come la sua versione precedente, MD 4 è una funzione crittografica. La dimensione dell'hash è 128 bit.
• SHA -1 è anche una funzione crittografica molto popolare. La dimensione dell'hash è 160 bit.
• GOST R 34.11-94 - Standard crittografico russo per il calcolo delle funzioni hash. La dimensione dell'hash è di 256 bit.

Quando un amministratore di sistema può utilizzare questi algoritmi? Spesso, quando si scarica qualsiasi contenuto, ad esempio programmi dal sito Web del produttore, musica, film o altre informazioni, viene calcolato un valore di checksum in base a un determinato algoritmo. Per motivi di sicurezza, dopo il download, è necessario calcolare autonomamente la funzione hash e confrontare il valore con quanto indicato sul sito web o nell'allegato al file. L'hai mai fatto?

Cosa rende più conveniente calcolare l'hash? Ora ci sono un gran numero di tali utilità, sia a pagamento che gratuite. Personalmente mi è piaciuto HashTab. In primo luogo, durante l'installazione, l'utilità è incorporata come una scheda nelle proprietà del file, in secondo luogo, consente di scegliere un gran numero di algoritmi di hashing e, in terzo luogo, è gratuita per uso privato non commerciale.

Cos'è il russo? Come accennato in precedenza, in Russia esiste uno standard di hashing GOST R 34.11-94, ampiamente utilizzato da molti produttori di prodotti per la sicurezza delle informazioni. Uno di questi strumenti è il programma per correggere e monitorare lo stato iniziale del pacchetto software FIX. Questo programma è un mezzo per monitorare l'efficacia dell'uso dei sistemi di sicurezza delle informazioni.

FIX (versione 2.0.1) per Windows 9x / NT / 2000 / XP

• Calcolo dei checksum di file specificati utilizzando uno dei 5 algoritmi implementati.
• Fissazione e successivo controllo dello stato iniziale del pacchetto software.
• Confronto delle versioni del pacchetto software.
• Fissazione e controllo delle directory.
• Controllo delle modifiche nei file specificati (directory).
• Formazione di report nei formati TXT, HTML, SV.
• Il prodotto ha un certificato FSTEC per NDV 3 No. 913 fino al 01 giugno 2013.

E per quanto riguarda la firma digitale? Il risultato del calcolo della funzione hash, insieme alla chiave segreta dell'utente, va all'ingresso dell'algoritmo crittografico, dove viene calcolata la firma digitale. A rigor di termini, la funzione di hash non fa parte dell'algoritmo EDS, ma spesso viene eseguita apposta per escludere un attacco utilizzando una chiave pubblica.

Oggigiorno molte applicazioni di e-commerce consentono di archiviare la chiave segreta dell'utente in un'area token privata (ruToken, eToken) senza la possibilità tecnica di estrarla da lì. Il token stesso ha un'area di memoria molto limitata, misurata in kilobyte. Per firmare un documento, non c'è modo di trasferire il documento al token stesso, ma trasferire l'hash del documento al token e ottenere un EDS in uscita è molto semplice.

Annotazione: In questa lezione viene formulato il concetto di funzione hash, nonché una breve panoramica degli algoritmi per la generazione di funzioni hash. Inoltre, viene considerata la possibilità di utilizzare algoritmi di crittografia a blocchi per formare una funzione hash.

Lo scopo della lezione: familiarizzare con il concetto di "funzione hash", nonché con i principi di tali funzioni.

Concetto di funzione hash

Funzione hashè una funzione matematica o di altro tipo che, per una stringa di lunghezza arbitraria, calcola un valore intero o un'altra stringa di lunghezza fissa. Matematicamente si può scrivere così:

dove M è il messaggio originale, talvolta chiamato prototipo e h è il risultato chiamato valore hash (e anche codice hash o digerire i messaggi(dall'inglese. riassunto del messaggio)).

Il significato della funzione hash è determinare la caratteristica della preimmagine: il valore della funzione hash. Questo valore di solito ha una certa dimensione fissa, come 64 o 128 bit. Il codice hash può essere ulteriormente analizzato per risolvere qualsiasi problema. Quindi, ad esempio, l'hashing può essere utilizzato per confrontare i dati: se due array di dati hanno codici hash diversi, è garantito che gli array saranno diversi; se sono gli stessi, è molto probabile che gli array siano gli stessi. Nel caso generale, non esiste corrispondenza biunivoca tra i dati originali e il codice hash a causa del fatto che il numero di valori delle funzioni hash è sempre inferiore al numero di varianti dei dati di input. Pertanto, ci sono molti messaggi di input che danno gli stessi codici hash (tali situazioni sono chiamate collisioni). La probabilità di collisioni gioca un ruolo importante nella valutazione della qualità delle funzioni hash.

Le funzioni hash sono ampiamente utilizzate nella crittografia moderna.

La funzione hash più semplice può essere costruita utilizzando l'operazione "somma modulo 2" come segue: otteniamo la stringa di input, aggiungiamo tutti i byte modulo 2 e restituiamo il byte risultato come valore della funzione hash. La lunghezza del valore hash in questo caso sarà di 8 bit, indipendentemente dalla dimensione del messaggio di input.

Ad esempio, supponiamo che il messaggio digitalizzato originale fosse il seguente (in formato esadecimale):

Traduciamo il messaggio in forma binaria, scriviamo i byte uno sotto l'altro e aggiungiamo i bit in ogni colonna modulo 2:

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Il risultato (0110 0101 (2) o 65 (16)) sarà il valore della funzione hash.

Tuttavia, tale funzione di hash non può essere utilizzata per scopi crittografici, ad esempio per generare una firma elettronica, poiché è abbastanza facile modificare il contenuto di un messaggio firmato senza modificare il valore del checksum.

Pertanto, la funzione hash considerata non è adatta per applicazioni crittografiche. In crittografia, una funzione hash è considerata buona se è difficile creare due preimmagini con lo stesso valore hash e anche se l'output della funzione non dipende esplicitamente dall'input.

Formuliamo i requisiti di base per le funzioni hash crittografiche:

• la funzione hash deve essere applicabile a messaggi di qualsiasi dimensione;
• il calcolo del valore della funzione dovrebbe essere fatto abbastanza rapidamente;
• con un valore noto della funzione hash, dovrebbe essere difficile (quasi impossibile) trovare un'adeguata preimmagine di M;
• con un messaggio noto M, dovrebbe essere difficile trovare un altro messaggio M' con lo stesso valore hash del messaggio originale;
• dovrebbe essere difficile trovare una coppia di messaggi casuali diversi con lo stesso valore hash.

Creare una funzione hash che soddisfi tutti questi requisiti non è un compito facile. Va inoltre ricordato che i dati di dimensione arbitraria vengono ricevuti all'input della funzione e il risultato dell'hash non dovrebbe essere lo stesso per dati di dimensioni diverse.

Attualmente, in pratica, le funzioni vengono utilizzate come funzioni hash che elaborano blocco per blocco il messaggio di input e calcolano il valore hash h i per ogni blocco M i del messaggio di input in base alle dipendenze della forma

h io = H (M io, h io-1),

dove h i-1 è il risultato ottenuto calcolando la funzione hash per il precedente blocco di dati di input.

Di conseguenza, l'output della funzione hash h n è una funzione di tutti gli n blocchi del messaggio di input.

Utilizzo di algoritmi di crittografia a blocchi per generare una funzione hash

È possibile utilizzare una funzione hash di blocco come funzione hash. Se l'algoritmo di blocco utilizzato è crittograficamente sicuro, anche la funzione hash basata su di esso sarà affidabile.

Il modo più semplice per utilizzare l'algoritmo di blocco per ottenere un codice hash è crittografare il messaggio in modalità CBC. In questo caso, il messaggio viene presentato come una sequenza di blocchi, la cui lunghezza è pari alla lunghezza del blocco dell'algoritmo di crittografia. Se necessario, l'ultimo blocco viene riempito a destra con degli zeri per ottenere un blocco della lunghezza desiderata. Il valore hash sarà l'ultimo blocco di testo crittografato. A condizione che venga utilizzato un algoritmo di crittografia a blocchi affidabile, il valore hash risultante avrà le seguenti proprietà:

• è praticamente impossibile senza la conoscenza della chiave di crittografia calcolare il valore hash per un dato array aperto di informazioni;
• è praticamente impossibile selezionare dati aperti per un dato valore di funzione hash senza conoscere la chiave di crittografia.

Il valore hash formato in questo modo viene solitamente chiamato inserto imitazione o autenticatore e viene utilizzato per verificare l'integrità del messaggio. Pertanto, la rappresentazione dell'inserimento è una combinazione di controllo che dipende da dati aperti e informazioni sulla chiave segreta. Lo scopo dell'utilizzo di un inserto simulato è rilevare tutte le modifiche accidentali o intenzionali nell'array di informazioni. Il valore ottenuto dalla funzione hash durante l'elaborazione del messaggio di input viene aggiunto al messaggio nel momento in cui si sa che il messaggio è corretto. Il destinatario verifica l'integrità del messaggio calcolando la rappresentazione del messaggio ricevuto e confrontandolo con il codice hash ricevuto, che deve essere trasmesso in modo sicuro. Uno di questi metodi sicuri può essere la crittografia della rappresentazione con la chiave privata del mittente, ad es. creazione di una firma. È anche possibile crittografare il codice hash ricevuto con un algoritmo di crittografia simmetrica se il mittente e il destinatario hanno una chiave di crittografia simmetrica comune.

Il processo specificato per ottenere e utilizzare un inserto simulato è descritto nello standard nazionale GOST 28147-89. Lo standard propone di utilizzare i 32 bit meno significativi del blocco ricevuto all'uscita dell'operazione di cifratura dell'intero messaggio nella modalità di concatenazione di blocchi cifrati per controllare l'integrità del messaggio trasmesso. Allo stesso modo, qualsiasi blocco può essere utilizzato per formare un inserto imitativo. algoritmo di crittografia simmetrica.

Un altro modo possibile per utilizzare un cifrario a blocchi per generare un codice hash è il seguente. Il messaggio originale viene elaborato in sequenza in blocchi. L'ultimo blocco viene riempito con zeri, se necessario, a volte la lunghezza del messaggio viene aggiunta all'ultimo blocco come numero binario. In ogni fase, criptiamo il valore hash ottenuto nella fase precedente, prendendo come chiave il blocco di messaggio corrente. L'ultimo valore crittografato ricevuto sarà il risultato finale dell'hash.

In effetti, ci sono molti altri possibili schemi per usare un cifrario a blocchi per formare una funzione di hash. Sia М i - il blocco del messaggio originale, hi - il valore della funzione hash allo stadio i-esimo, f - l'algoritmo di crittografia a blocchi utilizzato nella modalità di sostituzione semplice, - l'operazione di addizione modulo 2. Quindi, per esempio, sono possibili i seguenti schemi per la formazione della funzione hash:

In tutti questi schemi, la lunghezza del valore hash generato è uguale alla lunghezza del blocco crittografato. Tutti questi, così come alcuni altri schemi per l'utilizzo dell'algoritmo di crittografia a blocchi per calcolare i valori hash, possono essere applicati in pratica.

Il principale svantaggio delle funzioni hash progettate sulla base di algoritmi a blocchi è la velocità di funzionamento relativamente bassa. La forza crittografica richiesta può essere ottenuta in un numero inferiore di operazioni sui dati di input. Esistono algoritmi di hashing più veloci, progettati in modo indipendente, da zero, in base ai requisiti di forza crittografica (i più comuni sono MD5, SHA-1, SHA-2 e GOST R 34.11-94).

Eccetera.). La scelta di una particolare funzione hash è determinata dalle specificità del problema da risolvere. Gli esempi più semplici di funzioni hash sono il checksum o CRC.

Nel caso generale, non c'è corrispondenza biunivoca tra i dati originali e il codice hash. Pertanto, ci sono molti array di dati che forniscono gli stessi codici hash, le cosiddette collisioni. La probabilità di collisioni gioca un ruolo importante nella valutazione della "qualità" delle funzioni hash.

Checksum

Semplice, estremamente veloce e facilmente implementabile negli algoritmi hardware utilizzati per proteggere da distorsioni involontarie, inclusi errori hardware.

In termini di velocità di calcolo, è decine e centinaia di volte più veloce delle funzioni hash crittografiche e molto più semplice nell'implementazione hardware.

Il pagamento per una velocità così elevata è la mancanza di forza crittografica: una facile opportunità per adattare un messaggio a un importo predeterminato. Inoltre, di solito il numero di bit dei checksum (numero tipico: 32 bit) è inferiore agli hash crittografici (numeri tipici: 128, 160 e 256 bit), il che significa la possibilità di collisioni indesiderate.

Il caso più semplice di un tale algoritmo è la divisione di un messaggio in parole a 32 o 16 bit e la loro somma, che viene utilizzata, ad esempio, in TCP / IP.

In genere, tale algoritmo è necessario per tenere traccia di errori hardware tipici, come diversi bit di errore consecutivi fino a una determinata lunghezza. La cosiddetta famiglia di algoritmi. I "codici di ridondanza ciclica" soddisfano questi requisiti. Questi includono, ad esempio, il CRC32 utilizzato nell'hardware ZIP.

Funzioni di hash crittografico

Tra le molte funzioni hash esistenti, è consuetudine distinguere quelle crittograficamente forti utilizzate nella crittografia. Una funzione hash crittograficamente forte deve prima di tutto avere resistenza alla collisione di due tipi:

Usando l'hashing

Le funzioni hash vengono utilizzate anche in alcune strutture dati come le tabelle hash e gli alberi cartesiani. I requisiti per la funzione hash in questo caso sono diversi:

• buon mix di dati
• algoritmo di calcolo veloce

Riconciliazione dei dati

In generale, questa applicazione può essere descritta come il controllo di alcune informazioni per identificare l'originale, senza utilizzare l'originale. Per la verifica viene utilizzato il valore hash delle informazioni da verificare. Ci sono due direzioni principali di questa applicazione:

Controllo degli errori

Ad esempio, il checksum può essere trasmesso sul canale di comunicazione insieme al testo principale. Alla fine della ricezione, il checksum può essere ricalcolato e confrontato con il valore trasmesso. Se viene rilevata una discrepanza, significa che si è verificata una distorsione durante la trasmissione ed è possibile richiedere un nuovo tentativo.

In questo caso, un analogo domestico dell'hashing può essere una tecnica quando, durante lo spostamento, il numero di bagagli viene mantenuto in memoria. Quindi, per controllare, non è necessario ricordare ogni valigia, ma è sufficiente contarle. Una partita significherà che nessuna valigia è stata persa. Cioè, il numero di bagagli è il suo codice hash.

Controllo della passphrase

Nella maggior parte dei casi, le passphrase non vengono archiviate sugli oggetti di destinazione, vengono archiviati solo i loro valori hash. Non è pratico memorizzare le passphrase, poiché in caso di accesso non autorizzato a un file con frasi, l'attaccante scoprirà tutte le passphrase e sarà in grado di utilizzarle immediatamente e, durante l'archiviazione dei valori hash, conoscerà solo i valori hash ​​non reversibili nei dati originali, in questo caso, in passphrase. Durante la procedura di autenticazione viene calcolato il valore hash della passphrase immessa e confrontato con quello memorizzato.

Un esempio in questo caso è il sistema operativo GNU/Linux e Microsoft Windows XP. Memorizzano solo i valori hash delle passphrase dagli account utente.

Velocizzare il recupero dei dati

Ad esempio, quando si scrivono campi di testo nel database, è possibile calcolare il loro codice hash e inserire i dati nella sezione corrispondente a questo codice hash. Quindi, durante la ricerca dei dati, dovrai prima calcolare il codice hash del testo e si saprà immediatamente in quale sezione è necessario cercarli, ovvero non dovrai cercare nell'intero database, ma solo in una delle sue sezioni (questo velocizza notevolmente la ricerca).

L'analogo quotidiano dell'hashing in questo caso può essere il posizionamento delle parole nel dizionario in ordine alfabetico. La prima lettera di una parola è il suo codice hash e, durante la ricerca, non esaminiamo l'intero dizionario, ma solo la lettera richiesta.

Elenco algoritmi

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• RIPEMD-160
• RIPEMD-320
• Snefru
• Tigre (Idromassaggio
• Checksum Internet IP (RFC 1071)

Link

Fondazione Wikimedia. 2010.

Guarda cos'è il "codice hash" in altri dizionari:

Codice hash- il risultato di una combinazione aritmetica con tutti i byte del codice del programma o del set di dati. Il risultato dell'algoritmo di hashing include solo alcuni byte e l'algoritmo è costruito in modo tale che qualsiasi modifica del codice o dei dati del programma con ... ... Terminologia ufficiale

Codice hash- il risultato di una combinazione aritmetica con tutti i byte del codice del programma o del data set. Il risultato dell'algoritmo di hashing include solo alcuni byte e l'algoritmo è costruito in modo tale che qualsiasi modifica del codice o dei dati del programma con ... ...

codice di autenticazione del messaggio utilizzando la funzione hash- (ITU T H.235.3, ITU T H.235.1). Argomenti di telecomunicazione, concetti di base Codice di autenticazione del messaggio con hash EN HMAC ... Guida tecnica per traduttori

In programmazione, una hash table è una struttura dati che implementa l'interfaccia di un array associativo, ovvero permette di memorizzare coppie (chiave, valore) ed eseguire tre operazioni: l'operazione di aggiunta di una nuova coppia, un'operazione di ricerca e un operazione di cancellazione... Wikipedia

MAC (codice di autenticazione del messaggio) significa fornire protezione dall'imitazione nei protocolli di autenticazione dei messaggi con i partecipanti che si fidano l'uno dell'altro di un set speciale di caratteri che viene aggiunto a ... ... Wikipedia

L'hashing (a volte l'hashing) converte un array di dati di input di lunghezza arbitraria in una stringa di bit di output di lunghezza fissa. Tali trasformazioni sono anche chiamate funzioni di hash o funzioni di piegatura e i loro risultati ... ... Wikipedia

Questo articolo riguarda il codice. Per il metodo di brainstorming, vedere la scheda CRC. Algoritmo di controllo della ridondanza ciclica (CRC) per il calcolo del checksum, progettato per verificare l'integrità ... ... Wikipedia

- (abbreviazione di codice di autenticazione del messaggio basato su hash, codice hash di autenticazione del messaggio). Avere un modo per verificare l'integrità delle informazioni trasmesse o archiviate in un ambiente inaffidabile è parte integrante e necessaria del mondo ... ... Wikipedia

MI 2891-2004: Raccomandazione. GSOEE. Requisiti generali per il software degli strumenti di misura- Terminologia MI 2891 2004: Raccomandazione. GSOEE. Requisiti generali per il software degli strumenti di misura: si tratta di informazioni di misurazione presentate in una forma adatta alla trasmissione, interpretazione o elaborazione. Definizioni del termine da ... ... Dizionario-libretto di riferimento dei termini della documentazione normativa e tecnica

Eccetera.). La scelta di una particolare funzione hash è determinata dalle specificità del problema da risolvere. Gli esempi più semplici di funzioni hash sono il checksum o CRC.

Nel caso generale, non c'è corrispondenza biunivoca tra i dati originali e il codice hash. Pertanto, ci sono molti array di dati che forniscono gli stessi codici hash, le cosiddette collisioni. La probabilità di collisioni gioca un ruolo importante nella valutazione della "qualità" delle funzioni hash.

Checksum

Semplice, estremamente veloce e facilmente implementabile negli algoritmi hardware utilizzati per proteggere da distorsioni involontarie, inclusi errori hardware.

In termini di velocità di calcolo, è decine e centinaia di volte più veloce delle funzioni hash crittografiche e molto più semplice nell'implementazione hardware.

Il pagamento per una velocità così elevata è la mancanza di forza crittografica: una facile opportunità per adattare un messaggio a un importo predeterminato. Inoltre, di solito il numero di bit dei checksum (numero tipico: 32 bit) è inferiore agli hash crittografici (numeri tipici: 128, 160 e 256 bit), il che significa la possibilità di collisioni indesiderate.

Il caso più semplice di un tale algoritmo è la divisione di un messaggio in parole a 32 o 16 bit e la loro somma, che viene utilizzata, ad esempio, in TCP / IP.

In genere, tale algoritmo è necessario per tenere traccia di errori hardware tipici, come diversi bit di errore consecutivi fino a una determinata lunghezza. La cosiddetta famiglia di algoritmi. I "codici di ridondanza ciclica" soddisfano questi requisiti. Questi includono, ad esempio, il CRC32 utilizzato nell'hardware ZIP.

Funzioni di hash crittografico

Tra le molte funzioni hash esistenti, è consuetudine distinguere quelle crittograficamente forti utilizzate nella crittografia. Una funzione hash crittograficamente forte deve prima di tutto avere resistenza alla collisione di due tipi:

Usando l'hashing

Le funzioni hash vengono utilizzate anche in alcune strutture dati come le tabelle hash e gli alberi cartesiani. I requisiti per la funzione hash in questo caso sono diversi:

• buon mix di dati
• algoritmo di calcolo veloce

Riconciliazione dei dati

In generale, questa applicazione può essere descritta come il controllo di alcune informazioni per identificare l'originale, senza utilizzare l'originale. Per la verifica viene utilizzato il valore hash delle informazioni da verificare. Ci sono due direzioni principali di questa applicazione:

Controllo degli errori

Ad esempio, il checksum può essere trasmesso sul canale di comunicazione insieme al testo principale. Alla fine della ricezione, il checksum può essere ricalcolato e confrontato con il valore trasmesso. Se viene rilevata una discrepanza, significa che si è verificata una distorsione durante la trasmissione ed è possibile richiedere un nuovo tentativo.

In questo caso, un analogo domestico dell'hashing può essere una tecnica quando, durante lo spostamento, il numero di bagagli viene mantenuto in memoria. Quindi, per controllare, non è necessario ricordare ogni valigia, ma è sufficiente contarle. Una partita significherà che nessuna valigia è stata persa. Cioè, il numero di bagagli è il suo codice hash.

Controllo della passphrase

Nella maggior parte dei casi, le passphrase non vengono archiviate sugli oggetti di destinazione, vengono archiviati solo i loro valori hash. Non è pratico memorizzare le passphrase, poiché in caso di accesso non autorizzato a un file con frasi, l'attaccante scoprirà tutte le passphrase e sarà in grado di utilizzarle immediatamente e, durante l'archiviazione dei valori hash, conoscerà solo i valori hash ​​non reversibili nei dati originali, in questo caso, in passphrase. Durante la procedura di autenticazione viene calcolato il valore hash della passphrase immessa e confrontato con quello memorizzato.

Un esempio in questo caso è il sistema operativo GNU/Linux e Microsoft Windows XP. Memorizzano solo i valori hash delle passphrase dagli account utente.

Velocizzare il recupero dei dati

Ad esempio, quando si scrivono campi di testo nel database, è possibile calcolare il loro codice hash e inserire i dati nella sezione corrispondente a questo codice hash. Quindi, durante la ricerca dei dati, dovrai prima calcolare il codice hash del testo e si saprà immediatamente in quale sezione è necessario cercarli, ovvero non dovrai cercare nell'intero database, ma solo in una delle sue sezioni (questo velocizza notevolmente la ricerca).

L'analogo quotidiano dell'hashing in questo caso può essere il posizionamento delle parole nel dizionario in ordine alfabetico. La prima lettera di una parola è il suo codice hash e, durante la ricerca, non esaminiamo l'intero dizionario, ma solo la lettera richiesta.

Elenco algoritmi

• SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
• RIPEMD-160
• RIPEMD-320
• Snefru
• Tigre (Idromassaggio
• Checksum Internet IP (RFC 1071)

Link

Fondazione Wikimedia. 2010.

• Hashan Moheyan
• Codice hash

Guarda cos'è una "funzione hash" in altri dizionari:

Funzione hash- una funzione che esegue l'hashing di una matrice di dati mappando i valori da un insieme di valori (molto) ampio a un insieme di valori (significativamente) più piccolo. In inglese: Funzione hash Vedi anche: Cryptographic Algorithms Financial ... ... Vocabolario finanziario

funzione di hash crittografico- Una funzione che converte il testo di lunghezza arbitraria in testo di lunghezza fissa (nella maggior parte dei casi più corta). L'applicazione principale della funzione hash si trova nello schema della firma digitale. Poiché la funzione di hash viene calcolata più velocemente di una firma digitale, invece di ... ...

Funzione hash unidirezionale- funzione hash, che è una funzione computazionalmente irreversibile. In inglese: Funzione hash one way Vedi anche: Cryptographic Algorithms Financial Dictionary Finam ... Vocabolario finanziario

TIGER - funzione hash- Funzione hash TIGER, sviluppata da Ros Anderson ed Eli Biham nel 1996. La funzione hash TIGER è una nuova funzione hash veloce progettata per essere molto veloce sui computer moderni, in particolare sui computer a 64 bit. TIGRE ... ... Wikipedia

funzione hash unidirezionale- Per una funzione unidirezionale, è computazionalmente impossibile trovare due argomenti diversi per i quali i suoi valori sono gli stessi. [] Argomenti sicurezza delle informazioni IT funzione hash unidirezionale ... Guida tecnica per traduttori

Tiger (funzione hash)- Funzione di hash Tiger, sviluppata da Ros Anderson ed Eli Biham nel 1995. Tiger è stato progettato per funzionare particolarmente velocemente su computer a 64 bit. Tiger non ha restrizioni sui brevetti, può essere utilizzato liberamente come con ... ... Wikipedia

funzione di hashing- funzione hash 1. Una funzione che controlla il processo di immissione dei dati in una tabella hash, definendo (indirizzi delle celle libere. 2. Una funzione che rappresenta la mappatura di un frammento di un messaggio aperto in una stringa crittografata di lunghezza fissa. In . .. ... Guida tecnica per traduttori

Tabella hash- In programmazione, una tabella hash è una struttura dati che implementa l'interfaccia di un array associativo, ovvero consente di memorizzare coppie (chiave, valore) ed eseguire tre operazioni: l'operazione di aggiunta di una nuova coppia, un'operazione di ricerca e un'operazione di cancellazione... Wikipedia

Codice hash- Hashing (a volte hashing) che converte un array di dati di input di lunghezza arbitraria in una stringa di bit di output di lunghezza fissa. Tali trasformazioni sono anche chiamate funzioni di hash o funzioni di piegatura e i loro risultati ... ... Wikipedia

Collisione della funzione hash- La collisione della funzione hash H è costituita da due diversi blocchi di dati di input xey tali che H (x) = H (y). Le collisioni esistono per la maggior parte delle funzioni hash, ma per le funzioni hash "buone" la frequenza della loro occorrenza è vicina al minimo teorico. In ... ... Wikipedia

Gli algoritmi di ricerca che abbiamo considerato sono generalmente basati su un'operazione di confronto astratto. Sostanzialmente si distingue da questa serie il metodo di distribuzione della ricerca, descritto in "Tabelle dei simboli e alberi binari di ricerca", in cui l'elemento con la chiave i è memorizzato nella i-esima posizione della tabella, che permette di fare riferimento ad esso direttamente. La ricerca di distribuzione utilizza i valori delle chiavi come indici di array anziché gli operandi dell'operazione di confronto; il metodo stesso si basa sul fatto che le chiavi sono numeri interi distinti dello stesso intervallo degli indici della tabella. In questo capitolo esamineremo l'hashing, una ricerca distributiva avanzata utilizzata nelle applicazioni di ricerca più tipiche in cui le chiavi non hanno proprietà così convenienti. Il risultato finale dell'utilizzo di questo approccio è completamente diverso dai metodi basati sul confronto: invece di spostarci attraverso le strutture dati del dizionario confrontando le chiavi di ricerca con le chiavi negli elementi, proviamo ad accedere agli elementi nella tabella direttamente eseguendo un'aritmetica conversione delle chiavi in ​​indirizzi di tabella.

Gli algoritmi di ricerca di hashing hanno due parti distinte. Il primo passaggio consiste nel calcolare una funzione hash che converta la chiave di ricerca in un indirizzo nella tabella. Idealmente, chiavi diverse sarebbero associate a indirizzi diversi, ma spesso due o più chiavi diverse possono fornire lo stesso indirizzo nella tabella. Pertanto, la seconda parte della ricerca di hashing è il processo di risoluzione delle collisioni, che gestisce tali chiavi. Una delle tecniche di risoluzione dei conflitti che esamineremo in questo capitolo utilizza elenchi collegati, quindi trova un uso diretto in situazioni dinamiche in cui è difficile prevedere in anticipo il numero di chiavi di ricerca. Gli altri due metodi di risoluzione delle collisioni raggiungono livelli elevati prestazione ricerca in quanto gli elementi sono memorizzati in una matrice fissa. Vedremo come questi metodi possono essere migliorati in modo che possano essere utilizzati anche nei casi in cui la dimensione della tabella non può essere prevista in anticipo.

L'hashing è un buon esempio dell'equilibrio tra tempo e memoria. Se non ci fossero limiti alla quantità di memoria utilizzata, qualsiasi ricerca potrebbe essere eseguita con un solo accesso alla memoria, semplicemente utilizzando la chiave come indirizzo di memoria, come in una ricerca allocativa. Tuttavia, questo caso ideale di solito non è realizzabile, poiché le chiavi lunghe possono richiedere un'enorme quantità di memoria. D'altra parte, se non ci fossero restrizioni su tempi di consegna, si potrebbe cavarsela con una quantità minima di memoria utilizzando il metodo di ricerca sequenziale. L'hashing è un modo per utilizzare una quantità accettabile di memoria e tempo e per trovare un equilibrio tra questi due estremi. In particolare, qualsiasi equilibrio può essere mantenuto semplicemente modificando la dimensione della tabella, piuttosto che riscrivere il codice o scegliere altri algoritmi.

L'hashing è uno dei problemi classici dell'informatica: i suoi vari algoritmi sono stati studiati in dettaglio e sono ampiamente utilizzati. Vedremo che con ipotesi sciolte, possiamo sperare di supportare le operazioni di ricerca e inserimento nelle tabelle dei simboli a tempo costante, indipendentemente dalle dimensioni della tabella.

Questo valore atteso è la prestazione teorica ottimale per qualsiasi implementazione della tabella dei simboli, ma l'hashing non è ancora una panacea per due ragioni principali. All'inizio, tempi di consegna dipende dalla lunghezza della chiave, che può essere significativa nelle applicazioni reali che utilizzano chiavi lunghe. In secondo luogo, l'hashing non fornisce implementazioni efficienti di altre operazioni sulla tabella dei simboli, come select o sort. In questo capitolo esamineremo più da vicino queste e altre questioni.

Funzioni hash

Innanzitutto è necessario risolvere il problema del calcolo di una funzione hash che converta le chiavi in ​​indirizzi di tabella. Di solito, l'implementazione di questo calcolo aritmetico non è difficile, ma devi comunque stare attento a non incappare in vari sottili trabocchetti. Se hai una tabella che può contenere M elementi, hai bisogno di una funzione che converta le chiavi in ​​numeri interi nell'intervallo. Una funzione di hash ideale dovrebbe essere facile da calcolare e apparire come una funzione casuale: per qualsiasi argomento, i risultati dovrebbero, in un certo senso, essere equiprobabili.

La funzione hash dipende dal tipo di chiave. A rigor di termini, è necessaria una funzione di hash separata per ogni possibile tipo di chiave. Per migliorare l'efficienza, di solito è desiderabile evitare conversioni di tipo esplicite e rivolgersi invece all'idea di trattare la rappresentazione binaria delle chiavi in ​​una parola macchina come un numero intero che può essere utilizzato nei calcoli aritmetici. L'hashing precede i linguaggi di alto livello: era comune nei primi computer trattare un valore come una chiave stringa o un numero intero. In alcuni linguaggi di alto livello, è difficile creare programmi che dipendono dalla rappresentazione delle chiavi in ​​un particolare computer, poiché tali programmi sono intrinsecamente dipendenti dalla macchina e quindi difficili da trasferire su un altro computer. Le funzioni hash dipendono in genere dal processo di conversione da chiave a numero intero, quindi può essere difficile ottenere sia l'indipendenza della macchina che l'efficienza nelle implementazioni di hashing. In genere, semplici chiavi intere oa virgola mobile possono essere convertite con una sola operazione della macchina, ma le chiavi stringa e altri tipi di chiavi composite sono più costosi e richiedono maggiore attenzione all'efficienza.

Probabilmente la situazione più semplice è quando le chiavi sono numeri in virgola mobile da un intervallo fisso. Ad esempio, se le chiavi sono numeri maggiori di 0 e minori di 1, puoi semplicemente moltiplicarli per M, arrotondare il risultato all'intero inferiore e ottenere un indirizzo nell'intervallo tra 0 e M - 1; un tale esempio è mostrato in Fig. 14.1. Se le chiavi sono maggiori di s e minori di t, possono essere scalate sottraendo s e dividendo per ts, portandole nell'intervallo di valori tra 0 e 1, quindi moltiplicando per M per ottenere l'indirizzo nella tabella .

Riso. 14.1.

Per convertire i numeri in virgola mobile nell'intervallo tra 0 e 1 in indici per una tabella la cui dimensione è 97, questi numeri vengono moltiplicati per 97. In questo esempio, si sono verificate tre collisioni: per gli indici 17, 53 e 76. Valori hash ​​sono determinati dai bit più alti della chiave, i bit meno significativi non svolgono alcun ruolo. Uno degli obiettivi di progettazione di una funzione hash è correggere questo squilibrio in modo che ogni bit venga preso in considerazione durante il calcolo.

Se le chiavi sono interi di w-bit, possono essere convertite in numeri in virgola mobile e divise per 2 w per ottenere numeri in virgola mobile compresi tra 0 e 1, e poi moltiplicate per M come nel paragrafo precedente. Se le operazioni in virgola mobile richiedono molto tempo e i numeri non sono abbastanza grandi da causare un overflow, lo stesso risultato può essere ottenuto utilizzando operazioni aritmetiche intere: è necessario moltiplicare la chiave per M, quindi eseguire uno spostamento a destra per w cifre dividere per 2 w (o, se la moltiplicazione trabocca, eseguire lo spostamento e poi la moltiplicazione). Tali metodi sono inutili per l'hashing, a meno che le chiavi non siano distribuite uniformemente nell'intervallo, poiché il valore dell'hash è determinato solo dalle cifre iniziali della chiave.

Un metodo più semplice ed efficiente per i numeri interi di w-bit - uno dei metodi di hashing forse più comunemente usati - scegliendo una tabella di numeri primi come dimensione M e calcolando il resto di k per M, ad es. h (k) = k mod M per qualsiasi chiave intera k. Questa funzione è chiamata funzione hash modulare. È molto facile da calcolare (k% M in C ++) ed è efficiente per ottenere una distribuzione uniforme dei valori chiave tra valori inferiori a M. Un piccolo esempio è mostrato in Fig. 14.2.

Le tre colonne di destra mostrano il risultato dell'hashing delle chiavi a 16 bit elencate a sinistra utilizzando le seguenti funzioni:

v% 97 (sinistra)

v% 100 (centro) e

(int) (a * v)% 100 (destra),

dove a = 0,618033. Le dimensioni della tabella per queste funzioni sono rispettivamente 97, 100 e 100. I valori sembrano casuali (poiché le chiavi sono casuali). La seconda funzione (v% 100) utilizza solo le due cifre più a destra dei tasti e pertanto potrebbe mostrare prestazioni scadenti per le chiavi non casuali.

L'hashing modulare si applica anche alle chiavi in ​​virgola mobile. Se le chiavi si trovano in un intervallo ridotto, è possibile ridimensionarle a numeri compresi tra 0 e 1.2 w per ottenere numeri interi di w-bit e quindi utilizzare una funzione di hash modulare. Un'altra opzione consiste nell'utilizzare semplicemente la rappresentazione binaria della chiave come operando della funzione hash modulare (se disponibile).

L'hashing modulare viene utilizzato ogni volta che si accede ai bit che compongono le chiavi, siano essi numeri interi di parole macchina, sequenze di caratteri composte da parole o qualsiasi altra cosa possibile. Una sequenza di caratteri casuali racchiusa in una parola macchina non è esattamente la stessa delle chiavi intere casuali, poiché non tutti i bit vengono utilizzati per la codifica. Ma entrambi questi tipi (e qualsiasi altro tipo di chiave codificata per adattarsi a una parola macchina) possono essere fatti sembrare indici casuali su una piccola tabella.

Il motivo principale per scegliere una tabella hash prime come la dimensione M per l'hashing modulare è mostrato in Fig. 14.3. Questo esempio di dati di caratteri a 7 bit tratta la chiave come un numero di base 128, una cifra per ogni carattere nella chiave. Ora corrisponde al numero 1816567, che si può scrivere anche come

perché in ASCII i caratteri n, o e w corrispondono ai numeri 1568 = 110, 1578 = 111 e 1678 = 119. La scelta della dimensione della tabella M = 64 per questo tipo di chiave non ha successo, poiché l'aggiunta di valori multipli di 64 (o 128) a x non modifica il valore di x mod 64 - per qualsiasi chiave, il valore hash è il valore degli ultimi 6 bit di questa chiave. Naturalmente, una buona funzione di hash dovrebbe considerare tutte le cifre della chiave, specialmente per le chiavi simboliche. Situazioni simili possono verificarsi quando M contiene un fattore che è una potenza di 2. Il modo più semplice per evitarlo è scegliere un numero primo come M.

Ogni riga di questa tabella contiene: una parola di 3 lettere, la rappresentazione ASCII di quella parola come numero a 21 bit in notazione ottale e decimale e funzioni hash modulari standard per le dimensioni della tabella 64 e 31 (le due colonne più a destra) . La dimensione della tabella 64 porta a risultati indesiderati perché solo i bit più a destra della chiave vengono utilizzati per ottenere il valore hash e le lettere nelle parole del linguaggio comune sono distribuite in modo non uniforme. Ad esempio, tutte le parole che terminano con la lettera y hanno un valore hash di 57. Al contrario, un semplice valore di 31 provoca meno collisioni in una tabella che è più della metà delle dimensioni.

L'hashing modulare è molto facile da implementare, tranne per il fatto che la dimensione della tabella deve essere un numero primo. Per alcune applicazioni, puoi accontentarti di un piccolo numero primo noto o cercare in un elenco di numeri primi noti uno che sia vicino alla dimensione della tabella richiesta. Ad esempio, i numeri uguali a 2 t - 1 sono primi quando t = 2, 3, 5, 7, 13, 17, 19 e 31(e per nessun altro valore di t< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.

Questa tabella dei primi più grandi inferiori a 2 n per , può essere utilizzato per allocare dinamicamente una tabella hash quando si desidera che la dimensione della tabella sia un numero primo. Per ogni dato valore positivo nell'intervallo coperto, questa tabella può essere utilizzata per determinare un numero primo che è meno di 2 volte diverso da esso.

Un altro modo per gestire le chiavi intere consiste nel combinare i metodi moltiplicativo e modulare: si moltiplica la chiave per una costante tra 0 e 1, quindi si divide modulo M. In altre parole, è necessario utilizzare una funzione. Esiste una relazione tra i valori, M e la radice effettiva della chiave che potrebbe teoricamente portare a un comportamento anomalo, ma se si utilizza un valore arbitrario di a, non c'è quasi nessun problema in un'applicazione reale. Spesso il valore φ = 0,618033 ... (rapporto aureo) viene scelto come a.

Molte altre varianti sono state esplorate su questo argomento, in particolare funzioni di hash che possono essere implementate utilizzando istruzioni macchina efficienti come shift ed evidenziazione mascherata (vedi la sezione dei collegamenti).

In molte applicazioni che utilizzano tabelle di simboli, le chiavi non sono numeri e non sono necessariamente brevi; più spesso sono stringhe alfanumeriche, che possono essere piuttosto lunghe. Quindi, come si calcola la funzione hash per una parola come averylongkey?

Nel codice ASCII a 7 bit questa parola corrisponde al numero a 84 bit \ begin (align *) 97 \ cdot 128 ^ (11) & + 118 \ cdot 128 ^ (10) + 101 \ cdot 128 ^ (9) + 114 \ cdot 128 ^ (8) + 121 \ cdot 128 ^ (7) \\ & + 108 \ cdot 128 ^ (6) + 111 \ cdot 128 ^ (5) + 110 \ cdot 128 ^ (4) + 103 \ cdot 128 ^ (3) \\ & + 107 \ cdot 128 ^ (2) + 101 \ cdot 128 ^ (1) + 121 \ cdot 128 ^ (0), \ end (allinea *),

che è troppo grande per eseguire le normali funzioni aritmetiche sulla maggior parte dei computer. E spesso devi gestire chiavi molto più lunghe.

Per calcolare la funzione hash modulare per le chiavi lunghe, queste vengono trasformate pezzo per pezzo. È possibile sfruttare le proprietà aritmetiche della funzione modulo e utilizzare l'algoritmo di Horner (vedere la sezione 4.9 "Tipi di dati astratti"). Questo metodo si basa su un altro modo di scrivere i numeri corrispondenti ai tasti. Per questo esempio, scrivi la seguente espressione: \ begin (align *) ((((((((97 \ cdot 128 ^ (11) & + 118) \ cdot 128 ^ (10) + 101) \ cdot 128 ^” ( 9) + 114) \ cdot 128 ^ (8) + 121) \ cdot 128 ^ (7) \\ & + 108) \ cdot 128 ^ (6) + 111) \ cdot 128 ^ (5) + 110) \ cdot 128 ^ (4) + 103) \ cdot 128 ^ (3) \\ & + 107) \ cdot 128 ^ (2) + 101) \ cdot 128 ^ (1) + 121. \ end (align *)

Cioè, il numero decimale corrispondente alla codifica dei caratteri della stringa può essere calcolato guardandolo da sinistra a destra, moltiplicando il valore accumulato per 128 e quindi aggiungendo il valore del codice del carattere successivo. Nel caso di una stringa lunga, questo modo di calcolare alla fine porterà a un numero più grande di quanto un computer possa mai immaginare. Tuttavia, questo numero non è necessario, poiché è necessario solo un (piccolo) resto per dividerlo per M. Il risultato può essere ottenuto senza nemmeno memorizzare un grande valore accumulato, poiché in qualsiasi momento durante il calcolo, puoi scartare un multiplo di M - ogni volta che esegui moltiplicazioni e addizioni, devi solo memorizzare il resto della divisione modulo M. Il risultato sarà lo stesso come se avessimo l'opportunità di calcolare un numero lungo e poi eseguire la divisione (vedi Esercizio 14.10). Questa osservazione porta a un modo aritmetico semplice di calcolare funzioni hash modulari per stringhe lunghe — vedere il Programma 14.1. Questo programma usa un trucco finale: invece della base 128, usa il numero primo 127. Il motivo di questo cambiamento è discusso nel prossimo paragrafo.

Esistono molti modi per calcolare le funzioni di hash all'incirca allo stesso costo dell'hashing modulare utilizzando il metodo di Horner (una o due operazioni aritmetiche per ogni carattere nella chiave). Per le chiavi casuali, questi metodi sono praticamente gli stessi, ma le chiavi reali raramente sono casuali. La capacità di randomizzare chiavi reali a basso costo porta alla considerazione di algoritmi di hashing randomizzati, poiché abbiamo bisogno di funzioni hash che generino indici casuali su una tabella indipendentemente dalla distribuzione delle chiavi. La randomizzazione è facile, dal momento che non è necessario aderire letteralmente alla definizione di hashing modulare: è sufficiente utilizzare tutte le cifre della chiave per calcolare un numero intero inferiore a M.

Programma 14.1. Funzione hash per i tasti stringa

M = 96 e a = 128 (in alto),

M = 97 e a = 128 (centro) e

M = 96 e a = 127 (in basso)

La distribuzione non uniforme nel primo caso è il risultato dell'uso irregolare delle lettere e della persistenza dell'irregolarità dovuta al fatto che sia la dimensione della tabella che il fattore sono multipli di 32. Gli altri due esempi sembrano casuali poiché la dimensione e il fattore della tabella sono numeri relativamente primi.

Il Programma 14.1 mostra un modo per farlo: usare una base semplice invece di una potenza di 2 e un intero corrispondente alla rappresentazione ASCII della stringa. Nella fig. 14.5 fig. La Figura 14.5 mostra come questa modifica migliora la distribuzione delle tipiche chiavi stringa. In teoria, i valori hash generati dal Programma 14.1 possono dare risultati scadenti per le dimensioni della tabella che sono multipli di 127 (sebbene in pratica questo sarà probabilmente quasi invisibile); per creare un algoritmo randomizzato, si potrebbe scegliere a caso il valore del moltiplicatore. Un approccio ancora più efficiente consiste nell'utilizzare valori casuali dei coefficienti nel calcolo e valori casuali diversi per ciascuna cifra chiave. Questo approccio produce un algoritmo randomizzato chiamato hashing universale.

In teoria, una funzione di hash universale perfetta è quella per cui la probabilità di collisione tra due chiavi diverse in una tabella di dimensione M è esattamente 1/M. Si può dimostrare che usando come coefficiente a nel Programma 14.1, non un valore arbitrario fisso, ma una sequenza di valori diversi casuali, trasforma l'hashing modulare in una funzione di hash universale. Tuttavia, il costo della generazione di un nuovo numero casuale per ogni carattere nella chiave è solitamente inaccettabile. In pratica, il compromesso mostrato nel Programma 14.1 può essere ottenuto non memorizzando un array di diversi numeri casuali per ogni simbolo chiave, ma variando i coefficienti generando una semplice sequenza pseudo-casuale.

Per riassumere, per utilizzare l'hashing per implementare una tabella di simboli astratta, è necessario prima estendere l'interfaccia del tipo astratto per includere un'operazione di hash, che mappa le chiavi a numeri interi non negativi più piccoli della dimensione della tabella M.