D
D
daniilkening2022-02-21 19:11:01
Cryptography
daniilkening, 2022-02-21 19:11:01

How to predict next numbers for linear congruette generator?

Linear Congruential Generator (lcg). Ss+1 = (aS + c) mod m* For educational purposes, I want to try to hack the random function of the Pawn programming language. The conditions are as follows: The random(37) function generates numbers from 0 to 36. The output is the numbers 1 19 10 7 33 10 18 12 31 . On the Internet, I found the coefficient m of this LCG. m = 2^31 . There is also a code that makes it possible for us to predict the next numbers, provided that we know all 3 coefficients.

#include <stdio.h>
#include <time.h>
#define SIZE 6
unsigned long int seed = 1;

unsigned int lcg() {
    int a = 16807;
    int c = 12345;
    unsigned int m = 2147483648;
    
    seed = (seed * a) % m;
    return seed;
    
}

int main() {

    unsigned int mods[SIZE] = {1 , 19 , 10 , 7 , 33 , 10};
    int cur = 0;
    while(cur < 6) {
        if(mods[cur] == lcg() % 37) { cur++; }
         else { cur = 0; }   
        
    }
    while(1){
    printf("%u\n",  lcg() % 37);
    getchar();
    }
    return 0;
}


How to find out the missing coefficients? I heard about the LLL method, but I don’t understand at all how it works, and how to accept it here.

Answer the question

In order to leave comments, you need to log in

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question