attacco del compleanno

Un attacco del compleanno è un tipo di attacco crittografico utilizzato per la crittanalisi degli algoritmi di cifratura; è così chiamato perché sfrutta i princìpi matematici del paradosso del compleanno nella teoria delle probabilità. L'attacco del compleanno si può riassumere brevemente come segue: data una funzione f, lo scopo dell'attacco è quello di trovare 2 numeri tali che . Tale coppia di valori è chiamata collisione. Il metodo utilizzato per trovare una collisione è semplicemente quello di valutare la funzione f per differenti valori di input che possono essere scelti casualmente o pseudo-casualmente fino a che non si ottiene lo stesso risultato. A causa del paradosso del compleanno questo metodo può essere molto efficiente: specificatamente, se una funzione restituisce i valori del suo codominio con identica probabilità e la dimensione del codominio (ossia il numero di valori possibili) è sufficientemente grande, dopo aver valutato la funzione per circa differenti argomenti, c'è il 50% di probabilità di ottenere una coppia di valori distinti e per cui valga .