Séminaire Algorithmique : « Discussion autour du Générateur Sac à dos », Florette Martinez (ENS Ulm)

Le Générateur Sac à dos, proposé en 1985 par Rueppel et Massey est un générateur pseudo aléatoire (PRNG) qui combine un premier PRNG faible, le LFSR, et un problème dur ,le problème de la somme de sous-ensemble, dérivé du problème de sac à dos. Ce générateur a été attaqué avec succès par Knellwolf et Meyer en 2011.

Je discuterai ici d’une variante plus efficace de cette attaque et des différentes attaques que j’ai pu proposer avec Damien Vergnaud et Charles Bouillaguet contre des variantes de ce générateur.