Distance d'unicité

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 retrouver la clef de chiffrement sans ambiguïté.

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

h désigne la fonction entropie de Shannon.

Supposons que l'on connaisse la fonction de chiffrement E:\mathcal{K}\times\mathcal{M}\to\mathcal{C}. Si on connaît 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 utilisée, 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 apparaître 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 connaît d cryptogrammes, on connaît la clef. Il est toutefois important de préciser que cela ne présume 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.

Références[modifier | modifier le code]

Cours de cryptographie, de G. Zémor - Cassini, 2000. (section 2.4.3)