Distance d'unicité

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 ${\displaystyle C_{1},...,C_{n}}$ des cryptogrammes, tous chiffrés à partir de la clef ${\displaystyle K}$, la distance d'unicité est le plus petit entier ${\displaystyle n}$ tel que

${\displaystyle h(K|C_{1},...,C_{n})=0}$

où ${\displaystyle h}$ désigne la fonction entropie de Shannon.

Supposons que l'on connaisse la fonction de chiffrement ${\displaystyle E:{\mathcal {K}}\times {\mathcal {M}}\to {\mathcal {C}}}$. Si on connaît de plus ${\displaystyle C_{1}=E(k,m_{1})}$, mais pas ${\displaystyle k}$ ou ${\displaystyle 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 ${\displaystyle (m'_{j},k'_{j})}$ peuvent donner ${\displaystyle c_{1}=E(k'_{j},m'_{j})}$ --- idéalement, pour toute clef ${\displaystyle k}$, l'application ${\displaystyle m\mapsto E(k,m)}$ est une permutation. Si on dispose d'autre ${\displaystyle c_{i}}$ la clef ${\displaystyle k}$ utilisée pour chiffrer doit apparaître dans chaque liste de couple. La distance d'unicité ${\displaystyle d}$ correspond au nombre moyen de cryptogrammes nécessaires pour que seule la clef ${\displaystyle k}$ possède cette propriété. Autrement dit, heuristiquement, si on connaît ${\displaystyle 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

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