Che cos'è un esempio per una funzione di hash unidirezionale?

Sembra che tu stia parlando di funzioni hash crittografiche , dove è essenziale non poter costruire facilmente input che avere un dato risultato - questo è il significato di "funzione unidirezionale". Le funzioni di hash in generale (ad esempio utilizzate per le tabelle hash) hanno non questo requisito.

L'esempio più semplice di una funzione di hash crittografica è la funzione di Rabin, quadratura modulare. Funziona così:

• Prendi il tuo input come un numero (qualsiasi dato digitale può essere facilmente interpretato come un numero binario).
• Square it.
• Prendi il modulo (il resto della divisione per) N, dove N è il prodotto di due numeri primi e determina la lunghezza del tuo hash.

Usiamo N = 4181.

Ti dico che l'hash è 3666. Il tuo lavoro è trovare X tale che X ^ 2 mod 4181 = 3666. Come lo risolvi?

Ovviamente puoi usare la forza bruta vedendo se 4181 + 3666 è un numero quadrato, quindi prova 4181 * 2 + 3666, quindi 4181 * 3 + 3666, ma ci vorrà per sempre.

Puoi fare dei calcoli seri e scoprire che puoi trovare rapidamente una soluzione se conosci i fattori primi di N. Ma non lo fai, e trova i fattori primi per un gran numero (in uno scenario reale N sarebbe molto più grande) richiede anche per sempre.

Tutte le funzioni di hash sono a senso unico. Le funzioni di hash mappano uno spazio di input larg (er) (potenzialmente infinito) in uno spazio di output piccolo (normalmente) finito.

Se hai familiarità con il Principio di Pigeonhole , questo dovrebbe dirti immediatamente che le funzioni di hash devono essere a senso unico. Se non hai familiarità con il Principio di Pigeonhole, ecco una spiegazione molto semplice:

Il principio di Pigeonhole afferma che non puoi mettere 3 calze in 2 cassetti senza avere almeno un cassetto con almeno 2 calze al suo interno.

Quindi, se hai una funzione che mappa uno spazio di input più grande in uno spazio di output più piccolo, allora avrai almeno due ingressi che si associano allo stesso output, quindi, non è possibile invertire una funzione di hash.

Un esempio molto semplice di una funzione di hash che non utilizza alcuna matematica avanzata, è questa semplice funzione di parità:

def hash(n: Nat)
  if n.even?
    0
  else
    1
  end
end

Come puoi vedere, mappa un grande spazio di input (i numeri naturali) in un piccolo spazio di output (l'insieme {0, 1}). Ed è a senso unico: se ti dico che il risultato è 1 , non puoi dirmi quale sia l'input.

Ecco un semplice esempio:

Un hash della stringa "Hello world!" è "Hel". Se ti viene dato "Hel", non puoi ricreare "Hello world!", Eppure probabilmente non si scontrerà con molte altre stringhe.

Certo, questo hash non è molto buono perché se si tratta di una password, conoscendo le prime tre lettere è molto più semplice forzare la password originale.

Quindi cosa succede se moltiplichiamo ogni valore di lettera di 3 mod 26?

H (7) * 3 -> V (21)
e (4) * 3 -> m (12)
l (11) * 3 -> f (5)

Ora il nostro hash è "Vmf". Certo, si potrebbe invertire questo, ma senza sapere che è stato moltiplicato per 3, questo diventa già un po 'più complicato. Per un computer questo è banale, ma immagina di moltiplicare contro enormi numeri primi. Renderebbe praticamente impossibile la ricerca di un pattern e dovresti dedicare lunghe ore di calcolo per calcolare i possibili valori e provarli.

La conversione in "Vmf" era una questione banale, ma il ripristino a "Hel" non lo è. Questo è esattamente ciò che vogliamo da un hash.

Se l'utente fornisce la stringa "Hello, World!", senza dover salvare la stringa originale, possiamo semplicemente applicare l'hash a "Hello, World!" e ottieni "Vmf" e poi confronta quella stringa con quella che abbiamo sul file ..

"Vmf" === "Vmf"  // Bingo!

E in poche parole, questo è l'hashing. Esistono varie tecniche, ma il concetto è in definitiva lo stesso. Deterministicamente crea una stringa di dati irreversibile da un input.