Jak mogę określić początkowe wartości generatora liczb pseudolosowych, jeśli podana jest sekwencja?

10

Załóżmy, że wiedziałem, że losowa sekwencja liczb została wygenerowana przez liniowy generator kongruencjalny. To jest,

xn+1=(aXn+c)modm

Jeśli jestem biorąc pod uwagę cały okres (lub przynajmniej znaczna przyległe podciąg z nim), w jaki sposób można zrekonstruować parametrów i x_0 że wytwarzany tej sekwencji? Szukam ogólnej metody, która byłaby w stanie określić początkowe parametry, jeśli znany jest generator liczb pseudolosowych.a,c,mx0

random-number-generation inverse-problem Paweł
źródło
Co dokładnie wiadomo? Na podstawie ciągłej podsekwencji nie można ustalić, od której sekwencji rozpoczyna się x0 , chyba że elementy są indeksowane w sekwencji. Jeżeli m jest znana, wówczas i C mogą być łatwo wykryte. zado
matematyka

Odpowiedzi:

11

Zobacz artykuł Jak złamać liniowy generator zbieżny , Haldir („Zespół inżynierii odwrotnej”, grudzień 2004):

W tym artykule przedstawię metodę, która rozwiąże wszystkie wartości LCG, w tym moduł o sześciu lub więcej kolejnych liczbach wyjściowych PRNG.

Artykuł zawiera kod źródłowy „proof of concept” napisany w C, wykorzystujący NTL Victora Shoupa do rozszerzonej arytmetyki precyzyjnej.

matematyka
źródło
To był świetny papier! :) Czy znasz bardziej ogólną metodę, która mogłaby mieć zastosowanie do innych generatorów liczb losowych, a nie tylko liniowej zbieżności?
Paweł
@Paul: Można oczywiście znaleźć RNG, które można łatwo „rozwiązać” dla ich parametrów z wystarczających danych wyjściowych (problem odwrotny), ale wydaje się, że im lepszy RNG (bardziej losowy wygląd wyniku), tym trudniejsze jest odwrócenie problem byłby. Rozwiązanie przypadku LCG wiąże się z pewnymi dobrze znanymi efektami grupowania wymiarowego, co powoduje, że pary generowanych wartości są nierównomiernie rozmieszczone. Aby uzyskać więcej informacji, zobacz Projekt generatora kryptograficznie silnego poprzez przekształcenie sekwencji generowanych liniowo
hardmath