Comment puis-je déterminer les valeurs initiales du générateur de nombres pseudo-aléatoires si la séquence est donnée?

Supposons que je sache qu'une séquence de nombres aléatoires a été générée par un générateur congruentiel linéaire. C'est,

$x_{n+1}=(aX_n+c) \bmod m$

Si on me donne la période entière (ou au moins une grande sous-séquence contiguë de celle-ci), comment puis-je reconstruire les paramètres $a,c,m$ et $x_0$ qui ont produit cette séquence? Je recherche une méthode générale qui pourra déterminer les paramètres initiaux si le générateur de nombres pseudo-aléatoires est connu.

random-number-generation inverse-problem Paul
la source

Que sait-on précisément? À partir d'une sous-séquence contiguë, vous ne pouvez pas dire où la séquence a commencé

x_{0}

$x_0$ , sauf si les éléments sont indexés en séquence. Si

m

$m$ est connu, alors

a

$a$ et

c

$c$ sont facilement découverts.

hardmath

Réponses:

Voir l'article Comment casser un générateur linéaire congruentiel , Haldir ("Reverse Engineering Team", déc. 2004):

Dans cet article, je présenterai une méthode qui résoudra toutes les valeurs du LCG, y compris le module avec au moins six nombres consécutifs de sortie PRNG.

L'article comprend un code source de «preuve de concept» écrit en C, utilisant le NTL de Victor Shoup pour une arithmétique de précision étendue.

hardmath
la source

Ce fut un grand papier! :) Connaissez-vous une méthode plus générale qui pourrait s'appliquer à d'autres générateurs de nombres aléatoires, pas seulement congruentielle linéaire?

Paul

@Paul: On peut bien sûr trouver des RNG qui sont facilement "résolus" pour leurs paramètres à partir de données de sortie suffisantes (problème inverse), mais il semblerait que plus le RNG est meilleur (plus l'apparence de la sortie est aléatoire), plus l'inverse est difficile problème serait. La solution du cas LCG est liée à certains effets de regroupement dimensionnel qui sont bien connus, ce qui rend les paires de valeurs générées non uniformément réparties. Pour plus d'informations, voir Conception d'un générateur cryptographiquement puissant en transformant des séquences générées linéairement

hardmath