Mathematical studies of arithmetical pseudo-random numbers generators

Source abstract

Étude de générateurs pseudo aléatoires en cryptographie mathématique Les générateurs de nombres pseudo-aléatoires linéaires sont faciles à comprendre et à mettre en œuvre. Le plus célèbre d'entre eux est le générateur congruentiel linéaire . Dans la première partie de cette thèse, nous présentons ce générateur et les différents algorithmes de récupération de clés qui ont été conçus contre lui depuis les années soixante-dix. Parce que ce générateur est simple, il a été utilisé pour concevoir des générateurs plus complexes et potentiellement cryptographiquement sûrs comme le Générateur Congruentiel Permuté (présenté et attaqué dans le chapitre 3) et Trifork (présenté et attaqué dans le chapitre 4). Il peut également être généralisé en tant que générateur récursif multiple, mais la plupart des algorithmes connus peuvent être adaptés directement, ce qui signifie que la généralisation n'apporte pas beaucoup plus de sécurité. D'autres générateurs de nombres pseudo-aléatoires linéaires sont basés sur des problèmes difficiles, tels que le Knapsack generator et ses variantes, basées sur le problème du sac à dos. Le Fast Knapsack Generator est attaqué au chapitre 5 en raison de sa ressemblance avec le générateur congruentiel linéaire et le Knapsack generator elliptique est attaqué au chapitre 7. Arrow, décrit et attaqué au chapitre 8, est un générateur de nombres pseudo-aléatoires qui mélange des opérations linéaires et binaires. Il est très rapide et simple à mettre en œuvre. Mais ces opérations binaires et linéaires sont trop faciles à inverser et presque toutes les attaques présentées dans ce chapitre s'exécutent en moins de vingt minutes sur un ordinateur portable standard.