Générateur par rétrécissement

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 ?).

En cryptographie, un générateur par rétrécissement (shrinking generator) est un générateur de nombres pseudo-aléatoires destiné à un chiffrement de flot. Ce principe a été publié en 1993 par Don Coppersmith, Hugo Krawczyk et Yishay Mansour.

Ce générateur est basé sur deux registres à décalage à rétroaction linéaire. Le premier, le registre A, génère les bits de sortie. L'autre, le registre S, contrôle les sorties. A et S sont tous les deux synchronisés sur l'horloge du système. Si le bit du registre S est à 1 alors le bit du registre A est envoyé en sortie du générateur. Si le bit de S est à zéro, aucun bit n'est envoyé en sortie et le générateur avance d'un coup d'horloge. Le gros désavantage de cette approche est une diminution du taux de génération qui devient par la même occasion irrégulier.

Malgré sa simplicité, ce concept a remarquablement bien résisté à la cryptanalyse. Plus de 10 ans après, aucune attaque pratique n'est connue sous l'hypothèse que les polynômes utilisés pour la rétroaction sont secrets et que les deux registres sont suffisamment longs (pour éviter une attaque par force brute sur les états du générateur).

Une variante intéressante est le générateur par auto-rétrécissement. Au lieu d'utiliser un registre pour contrôler la sortie d'un autre, le registre s'auto-régule. La sortie du registre indique comment il doit extraire ses propres bits.