Funzioni hash: concetti e nozioni di base

Nei vari settori dell'informatica vengono utilizzate le funzioni di hash. Sono progettati, da un lato, per semplificare significativamente lo scambio di dati tra gli utenti e l'elaborazione di file utilizzati per vari scopi, dall'altro, per ottimizzare gli algoritmi per garantire il controllo dell'accesso alle risorse corrispondenti. La funzione di hash è uno degli strumenti chiave per fornire la protezione tramite password dei dati e per organizzare lo scambio di documenti firmati con la firma digitale. Esistono numerosi standard attraverso i quali i file possono essere memorizzati nella cache. Molti di loro sono sviluppati da specialisti russi. In quali varianti possono essere rappresentate le funzioni hash? Quali sono i principali meccanismi per la loro applicazione pratica?

Cos'è?

Per prima cosa, esplora il concetto di funzione hash. Questo termine è comunemente inteso come un algoritmo per convertire una certa quantità di informazioni in una sequenza più breve di simboli mediante metodi matematici. L'importanza pratica della funzione di hash può essere rintracciata in una varietà di aree. Quindi, possono essere utilizzati durante il controllo di file e programmi per l'integrità. Inoltre, le funzioni hash crittografiche vengono utilizzate negli algoritmi di crittografia.

caratteristiche

Considerare le caratteristiche chiave degli algoritmi studiati. Tra quelli:

• la presenza di algoritmi interni per convertire i dati della lunghezza originale in una sequenza di caratteri più breve;
• apertura per verifica crittografica;
• la presenza di algoritmi per crittografare in modo affidabile i dati originali;
• adattamento alla decrittografia quando sono coinvolte piccole potenze di calcolo.

Tra le altre proprietà più importanti della funzione hash:

• capacità di elaborare matrici di dati iniziali di lunghezza arbitraria;
• generare blocchi hash di lunghezza fissa;
• distribuire uniformemente i valori delle funzioni all'uscita.

Gli algoritmi considerati suggeriscono anche la sensibilità all'input dei dati a un livello di 1 bit. Cioè, anche se, condizionatamente parlando, almeno 1 lettera cambia nel documento sorgente, la funzione di hash apparirà diversa.

Requisiti hash

Esistono numerosi requisiti per le funzioni hash pensate per l'uso pratico in una determinata area. Innanzitutto, l'algoritmo appropriato dovrebbe essere sensibile alle modifiche nella struttura interna dei documenti con hash. Cioè, nella funzione di hash deve essere riconosciuto, se stiamo parlando di un file di testo, di permutazioni di paragrafo, sillabazioni. Da un lato, il contenuto del documento non cambia, dall'altro - la sua struttura viene regolata e questo processo dovrebbe essere riconosciuto durante l'hashing. In secondo luogo, l'algoritmo considerato deve convertire i dati in modo che l'operazione inversa (trasformando l'hash nel documento originale) sia praticamente impossibile. In terzo luogo, la funzione di hash dovrebbe comportare l'uso di tali algoritmi, che praticamente escludono la probabilità della formazione della stessa sequenza di caratteri sotto forma di un hash, in altre parole - l'emergere delle cosiddette collisioni. Considereremo la loro essenza un po 'più tardi.

I requisiti contrassegnati, che la funzione di hash deve rispettare, possono essere soddisfatti principalmente attraverso l'uso di complessi approcci matematici.

struttura

Cerchiamo di studiare quale può essere la struttura delle funzioni considerate. Come notato sopra, tra i principali requisiti per gli algoritmi considerati è garantito l'unidirezionalità della crittografia. Una persona che ha solo un hash a sua disposizione dovrebbe difficilmente essere in grado di ottenere il documento di origine sulla base.

In quale struttura è possibile utilizzare una funzione hash per tali scopi? Un esempio della sua compilazione può essere: H (hash, ovvio, hash) = f (T (testo), H1), dove H1 è l'algoritmo di elaborazione del testo T. Questa funzione blocca T in modo tale che senza conoscere H1, aprirlo come completo il file sarà quasi impossibile.

Utilizzo pratico delle funzioni di hash: download di file

Ora esaminiamo più in dettaglio le opzioni per l'utilizzo delle funzioni di hash nella pratica. L'uso di algoritmi appropriati può essere utilizzato durante la scrittura di script per il download di file da server Internet.

Nella maggior parte dei casi, viene determinato un determinato checksum per ogni file: questo è l'hash. Dovrebbe essere lo stesso per un oggetto che si trova sul server e scaricato sul computer dell'utente. Se questo non è il caso, il file potrebbe non aprirsi o potrebbe non avviarsi correttamente.

Funzione hash ed EDS

L'uso delle funzioni hash è comune quando si organizza lo scambio di documenti contenenti una firma digitale. In questo caso, il file firmato viene sottoposto a hash in modo che il destinatario possa verificare che sia autentico. Sebbene formalmente la funzione di hash non sia inclusa nella struttura della chiave elettronica, può essere registrata nella memoria flash dell'hardware con cui sono firmati i documenti, come ad esempio, eToken.

Una firma elettronica è la crittografia dei file con l'uso di chiavi pubbliche e private. Cioè, un messaggio crittografato con la chiave privata è allegato al file sorgente e l'EDS è verificato utilizzando la chiave pubblica. Se la funzione di hash di entrambi i documenti è la stessa, il file conservato dal destinatario viene riconosciuto come autentico e la firma del mittente viene riconosciuta come valida.

L'hashing, come abbiamo notato sopra, non è direttamente un componente di EDS, tuttavia, rende possibile ottimizzare in modo molto efficace gli algoritmi per l'attivazione delle firme elettroniche. Quindi, solo l'hash può essere crittografato, e non il documento stesso. Di conseguenza, la velocità di elaborazione dei file aumenta in modo significativo, allo stesso tempo diventa possibile fornire meccanismi più efficienti per proteggere l'EDS, dal momento che l'enfasi nelle operazioni di calcolo in questo caso non sarà sull'elaborazione dei dati originali, ma sull'assicurazione della forza crittografica della firma. La funzione di hash rende anche possibile firmare una varietà di tipi di dati e non solo testo.

Controllo della password

Un'altra possibile area di applicazione dell'hash è l'organizzazione di algoritmi di verifica password impostati per limitare l'accesso a determinate risorse di file. Come possono essere coinvolti determinati tipi di funzioni hash nella risoluzione di tali problemi? Molto semplice

Il fatto è che nella maggior parte dei server, l'accesso al quale è soggetto a delimitazione, le password sono memorizzate sotto forma di valori hash. Questo è abbastanza logico: se le password sono state presentate nel modulo di testo originale, gli hacker che hanno ottenuto l'accesso potrebbero leggere facilmente i dati segreti. A sua volta, sulla base dell'hash calcolare la password non è facile.

Come viene controllato l'accesso dell'utente quando si utilizzano gli algoritmi considerati? La password immessa dall'utente viene controllata rispetto a ciò che è memorizzato nella funzione di hash che è memorizzata sul server. Se i valori dei blocchi di testo sono gli stessi, l'utente ottiene l'accesso necessario alle risorse.

La funzione hash più semplice può essere utilizzata come strumento per il controllo della password. Ma in pratica, gli specialisti IT utilizzano spesso algoritmi crittografici multistadio complessi. Di norma, sono integrati dall'applicazione degli standard trasferimento dati tramite un canale sicuro - in modo che gli hacker non possano rilevare o calcolare la password trasmessa dal computer dell'utente al server - prima di controllarla con i blocchi di testo con hash.

Hash Collisions

Nella teoria delle funzioni di hash, tale fenomeno viene fornito come collisione. Qual è la sua essenza? Una collisione di hash è una situazione in cui due file diversi hanno lo stesso codice hash. Questo è possibile se la lunghezza della sequenza di caratteri di destinazione è piccola. In questo caso, la probabilità di una corrispondenza hash sarà maggiore.

Per evitare collisioni, si raccomanda, in particolare, di utilizzare un doppio algoritmo chiamato "hashing della funzione hash". Comporta la formazione di codice aperto e chiuso. Molti programmatori nella risoluzione di problemi importanti consigliano di non utilizzare le funzioni di hash nei casi in cui non è necessario e sempre di testare gli algoritmi appropriati per la migliore compatibilità con determinati tasti.

Storia dell'aspetto

I fondatori della teoria delle funzioni di hash possono essere considerati i ricercatori Carter, Wegman, Simonson, Bierbrauer. Nelle prime versioni, gli algoritmi corrispondenti erano usati come un toolkit per la formazione di immagini uniche di sequenze di caratteri di lunghezza arbitraria con il conseguente obiettivo di identificarle e verificarne l'autenticità. A sua volta, l'hash, secondo i criteri specificati, dovrebbe avere una lunghezza di 30-512 bit. Come caratteristica particolarmente utile delle funzioni corrispondenti, è stata considerata la sua idoneità per l'utilizzo come risorsa di una ricerca rapida di file o per ordinarli.

Standard Hash popolari

Consideriamo ora gli standard popolari in cui è possibile rappresentare le funzioni hash. Tra quelli - CRC. Questo algoritmo è un codice ciclico, chiamato anche checksum. Questo standard è caratterizzato dalla semplicità e allo stesso tempo dall'universalità: attraverso di esso è possibile eseguire l'hash della più ampia gamma di dati. CRC è uno degli algoritmi non crittografici più comuni.

A loro volta, durante la crittografia, gli standard MD4 e MD5 sono ampiamente utilizzati. Un altro algoritmo di crittografia popolare è SHA-1. In particolare, è caratterizzato da una dimensione hash di 160 bit, che è maggiore di quella di MD5 - questo standard supporta 128 bit. Esistono standard russi che regolano l'uso delle funzioni hash, - GOST R 34.11-94, oltre a sostituirlo con GOST R 34.11-2012. Si può notare che il valore hash fornito dagli algoritmi adottati nella Federazione Russa è di 256 bit.

Gli standard in questione possono essere classificati per vari motivi. Ad esempio, ci sono quelli che usano algoritmi bloccati e specializzati. La semplicità dei calcoli basati sugli standard del primo tipo è spesso accompagnata dalla loro bassa velocità. Pertanto, in alternativa agli algoritmi di blocco, possono essere coinvolti quelli che implicano una minore quantità di operazioni di calcolo. È consuetudine attribuire agli standard ad alta velocità, in particolare MD4, MD5 e SHA sopra menzionati. Considerare le specifiche degli algoritmi di hashing speciali sull'esempio di SHA in modo più dettagliato.

Funzionalità dell'algoritmo SHA

L'uso delle funzioni di hash basate sullo standard SHA è spesso effettuato nel campo dello sviluppo di strumenti di firma digitale per i documenti DSA. Come notato sopra, l'algoritmo SHA supporta un hash a 160 bit (fornendo un cosiddetto "digest" di una sequenza di caratteri). Lo standard inizialmente considerato divide una serie di dati in blocchi di 512 bit. Se necessario, se la lunghezza dell'ultimo blocco non raggiunge la cifra specificata, la struttura del file viene completata con 1 e il numero di zeri necessario. Inoltre alla fine del blocco corrispondente si adatta il codice che fissa la lunghezza del messaggio. L'algoritmo considerato comprende 80 funzioni logiche, mediante le quali vengono elaborate 3 parole, rappresentate in 32 bit. Anche nell'uso standard SHA di 4 costanti viene fornito.

Hash Algorithms Comparison

Esaminiamo come le proprietà delle funzioni di hash relative ai diversi standard siano correlate, per esempio, confrontando le caratteristiche dello standard russo GOST R 34.11-94 e lo SHA americano, che abbiamo discusso sopra. Prima di tutto, va notato che l'algoritmo sviluppato nella Federazione Russa prevede l'implementazione di 4 operazioni di crittografia per 1 ciclo. Questo corrisponde a 128 round. A sua volta, per 1 round, quando si attiva SHA, si presume che siano calcolati circa 20 comandi, mentre il numero totale di round è 80. Pertanto, utilizzando SHA è possibile elaborare 512 bit di dati sorgente durante 1 ciclo. Allo stesso tempo, lo standard russo è in grado di eseguire operazioni per ciclo di 256 bit di dati.

Le specifiche del nuovo algoritmo russo

Sopra, abbiamo notato che lo standard GOST R 34.11-94 è stato sostituito da uno nuovo - GOST R 34.11-2012 "Stribog". Esaminiamo le sue specifiche in modo più dettagliato.

Attraverso questo standard, possono essere implementate funzioni di hash crittografiche, come nel caso degli algoritmi discussi sopra. Si può notare che l'ultimo standard russo supporta un blocco di dati di input nella quantità di 512 bit. I principali vantaggi di GOST R 34.11-2012:

• alto livello di sicurezza dal cracking dei cifrari;
• affidabilità, supportata dall'uso di strutture comprovate;
• calcolo operativo della funzione di hash, la mancanza di trasformazioni nell'algoritmo, che complicano la costruzione della funzione e rallentano il calcolo.

I noti vantaggi del nuovo standard russo di crittografia crittografica consentono di utilizzarlo quando si organizza un flusso di documenti che soddisfa i criteri più rigorosi specificati nelle disposizioni della normativa normativa.

Specificità delle funzioni hash crittografiche

Consideriamo più in dettaglio come i tipi di algoritmi che studiamo possano essere usati nel campo della crittografia. Il requisito chiave per le funzioni corrispondenti è la resistenza alle collisioni, che abbiamo menzionato sopra. Cioè, i valori delle funzioni hash duplicati non dovrebbero essere formati se questi valori sono già presenti nella struttura dell'algoritmo adiacente. Altri criteri sopra riportati dovrebbero anche soddisfare le funzioni crittografiche. È chiaro che c'è sempre qualche possibilità teorica di recuperare un file sorgente basato su hash, specialmente se c'è un potente strumento di calcolo in accesso. Tuttavia, questo scenario dovrebbe essere ridotto al minimo, grazie a solidi algoritmi di crittografia. Quindi, sarà molto difficile calcolare la funzione di hash se la sua forza computazionale corrisponde alla formula 2 ^ {n / 2}.

Un altro importante criterio di un algoritmo crittografico è una modifica dell'hash in caso di correzione del set di dati iniziale. Sopra, abbiamo notato che gli standard di crittografia dovrebbero avere una sensibilità di 1 bit. Pertanto, questa proprietà è un fattore chiave per garantire una protezione affidabile della password per l'accesso ai file.

Schemi iterativi

Esaminiamo ora in che modo è possibile creare algoritmi di hashing crittografici. Tra gli schemi più comuni per risolvere questo problema c'è l'uso di un modello sequenziale iterativo. Si basa sull'uso della cosiddetta funzione di compressione, in cui il numero di bit di ingresso è sostanzialmente maggiore di quelli registrati in uscita.

Ovviamente, la funzione di compressione deve soddisfare i criteri necessari per la forza crittografica. Nello schema interattivo, la prima operazione per l'elaborazione del flusso di dati di input è suddivisa in blocchi, la cui dimensione viene calcolata in bit. L'algoritmo corrispondente coinvolge anche variabili temporali di un dato numero di bit. Il primo valore utilizza un numero noto, mentre i blocchi di dati successivi vengono combinati con il valore della funzione in questione nell'output. Il valore hash diventa il bit di uscita per l'ultima iterazione, che tiene conto dell'intero flusso di input, incluso il primo valore. Viene fornito un cosiddetto "effetto valanga" dell'hashing.

La principale difficoltà che caratterizza l'hashing implementato come uno schema iterativo è che a volte è difficile creare funzioni hash se il flusso di input non è identico alle dimensioni del blocco in cui è suddiviso l'array di dati iniziale. Ma in questo caso, lo standard di hashing può essere definito algoritmi mediante il quale il flusso originale può essere espanso in un modo o nell'altro.

In alcuni casi, i cosiddetti algoritmi multi-pass possono essere coinvolti nell'elaborazione dei dati all'interno di uno schema iterativo. Suggeriscono la formazione di un "effetto valanga" ancora più intenso. Tale scenario presuppone la formazione di array di dati ripetuti, e solo secondariamente vi è l'espansione.

Algoritmo di blocco

La funzione di compressione può anche essere basata su un algoritmo di blocco mediante il quale viene eseguita la crittografia. Quindi, al fine di aumentare il livello di sicurezza, è possibile utilizzare come blocco dati i blocchi di dati da sottoporre all'iterazione corrente, come chiave e il risultato delle operazioni ottenute durante l'esecuzione della funzione di compressione. Di conseguenza, l'ultima iterazione fornirà l'output dell'algoritmo. La sicurezza hash si correlerà con la robustezza dell'algoritmo coinvolto.

Tuttavia, come abbiamo notato sopra, considerando vari tipi di funzioni di hash, gli algoritmi di blocco sono spesso accompagnati dalla necessità di utilizzare grandi poteri computazionali. Se non sono disponibili, la velocità di elaborazione dei file potrebbe non essere sufficiente per risolvere problemi pratici associati all'uso delle funzioni hash. Allo stesso tempo, la criptoresistenza richiesta può essere realizzata con un piccolo numero di operazioni con i flussi di dati di origine, in particolare gli algoritmi che abbiamo considerato sono adatti a risolvere tali problemi: MD5, SHA, standard di crittografia crittografica russa.