Distance d'unicité

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant la cryptologie.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

La distance d'unicité est un terme de cryptographie qui fait référence au nombre minimal moyen de textes chiffrés, avec une même clef, nécessaire pour que l'on puisse la retrouver sans ambiguité.

Formellement, si on note $C 1,..., C n$ des cryptogrammes, tous chiffrés à partir de la clef $K$ , la distance d'unicité est le plus petit entier $n$ tel que

h (K | C 1,..., C n) = 0

où $h$ désigne la fonction entropie de Shannon.

Supposons que l'on connaisse la focntion de chiffrement $E:\mathcal{K}\times\mathcal{M}\to\mathcal{C}$ . Si on connait de plus $C 1 = E (k, m 1)$ , mais pas $k$ ou $m 1$ , et que l'on essaie de retrouver la clef de chiffrement utiliser, on est confronté au problème que, en régle générale, il existe, plusieurs couples $(m' j, k' j)$ peuvent donner $c 1 = E (k' j, m' j)$ --- idéalement, pour toute clef $k$ , l'application $m\mapsto E(k,m)$ est une permutation. Si on dispose d'autre $c i$ la clef $k$ utilisée pour chiffrer doit apparaitre dans chaque liste de couple. La distance d'unicité $d$ correspond au nombre moyen de cryptogrammes nécessaires pour que seule la clef $k$ possède cette propriété. Autrement dit, heuristiquement, si on connait $d$ cryptogrammes, on connait la clef. Il est toutefois important de préciser que cela ne presume pas de l'effort de calcul nécessaire pour obtenir effectivement la clef : on sait juste que l'on a suffisamment d'information pour calculer la clef de chiffrement; trouver la clef est un autre problème.