Principe du tableau PITABLE

Le tableau PITABLE de RC2 contient les 256 octets de 0 à 255 dans un ordre permuté. RFC 2268 indique que ce tableau provient « des chiffres de π », mais ne décrit aucun procédé. Chaque implémentation du chiffre utilise exactement la même séquence, ce qui impose l’existence d’une méthode déterministe et publique.

Construction algorithmique

La solution repose sur le Fisher–Yates shuffle. On initialise une liste S contenant les valeurs 0…255. Pour chaque position i de 2 à 256, on échange S[i‑1] avec un élément S[j] choisi aléatoirement parmi les i premières positions. L’aléa provient des décimales de π, lues trois à la fois, soit un nombre x compris entre 0 et 999. Si x est inférieur à n·⌊1000/n⌋ (où n est le nombre de positions disponibles), on accepte x mod n comme indice j. Sinon le triplet est rejeté et trois nouveaux chiffres sont lus. Cette étape de rejet garantit une distribution uniforme même lorsque 1000 n’est pas divisible par n. Le processus consomme exactement 828 décimales de π et effectue 21 rejets, dont deux se produisent au point de Feynman (six 9 consécutifs à la 762ᵉ décimale).

input: d = 3,1,4,1,5,9,2,6,5,3,…
rand(n):
  loop
    x ← next three digits of d   // 0…999
    if x < n·⌊1000/n⌋:
      return x mod n
    // otherwise discard x
S ← [0,1,…,255]
for i ← 2 to 256:
  j ← rand(i)
  swap S[j], S[i‑1]
return S                // = PITABLE

Analyse de l'unicité et de la recherche

Le nombre total de permutations possibles pour 256 éléments est d’environ 10^507. Une recherche exhaustive a testé près de 100 000 combinaisons : quatre sources numériques, sept stratégies de lecture, six ordres de mélange, 300 points de départ et les deux tables du RFC. Une seule configuration a reproduit intégralement le tableau : le shuffle de Fisher–Yates avec trois décimales de π et le rejet décrit ci‑dessus. Toute variante (changement de source, largeur de lecture, omission du rejet) ne dépasse pas le niveau de hasard, confirmant que la méthode identifiée n’est pas une coïncidence.

Table secondaire et points de départ

RFC 2268 comporte une seconde permutation, appelée Table[], utilisée pour encoder la longueur de clé effective. Elle correspond exactement au même algorithme, mais démarre à la cinquième décimale de π (5926…). Ainsi, les deux tables sont générées par un unique générateur, exécuté à partir de deux positions d’amorçage différentes, tout en consommant le même nombre total de décimales (828) et le même nombre de rejets (21).