We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Security
  3. Cryptography
  4. PRNG Sequence Guessing
  5. Discussions

PRNG Sequence Guessing

  • denalilumma
     + 1 comment

    Tough challenge! I've studied a lot of related information: https://en.wikipedia.org/wiki/Linear_congruential_generator https://jazzy.id.au/2010/09/20/cracking_random_number_generators_part_1.html https://jazzy.id.au/2010/09/21/cracking_random_number_generators_part_2.html https://www.youtube.com/playlist?list=PL5KkMZvBpo5CdoOxa3dqll2n6KsXqerYO http://crypto.stackexchange.com/questions/2086/predicting-values-from-a-linear-congruential-generator https://en.wikipedia.org/wiki/Chinese_remainder_theorem https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity http://codegolf.stackexchange.com/questions/69582/b%C3%A9zouts-identity

    But have not been able to implement a working solution so far.

    Any pointers on where to look next, or how to break down the problem welcome. Thank you!

    Below is my code in Python 2.

    Right now I am attempting to assert that the first 10 values are correct (same as what is given in the first example). I'll use that as a way to debug further, unless there are other suggestions.

    import time

class Random:
    
    def __init__(self, seed=None):
        if seed is None:
            seed = int(time.time() * 1000)
        self._seed = seed
        
    def get_seed(self):
        return self._seed
    
    def set_seed(self, seed):
        self._seed = (seed ^ 0x5deece66d) & ((1 << 48) -1)

    def next(self, bits):
        
        if bits < 1:
            bits = 1
        elif bits > 32:
            bits = 32

        self._seed = (self._seed * 0x5deece66d + 0xb) & ((1 << 48) -1)
        retval = self._seed >> (48 - bits)
        
        if retval & (1 << 31):
            retval -= (1 << 32)

        return retval
    
    def nextInt(self, n=None):
        """
        Return random int in [0, `n`).
        If `n` is not supplied, random 32-bit int will be returned
        """
        if n is None:
            return self.next(32)

        if n <= 0:
            raise valueError("Argument must be positive!")

        if not (n & (n-1)):
            return (n * self.next(31)) >> 31

        bits = self.next(31)
        val = bits % n
        while (bits - val + n - 1) < 0:
            bits = self.next(31)
            val = bits % n

        return val


def find_seed(arr):
    v1 = arr[0]
    v2 = arr[1]
    seed = None
    for i in xrange(65536):
        seed = v1 * 65536 + 1
        if (((seed * 0x5deece66d + 0xB) & ((1 << 48) -1)) >> 16) == v2:
            break
    return seed


def get_next_10(r):
    ret_arr = []
    for i in xrange(10):
        ret_arr.append(r.nextInt(1000))
        
    return ret_arr


n = int(raw_input().strip())
test_case_1 = [643, 953, 522, 277, 464, 366, 321, 409, 227, 702]
test_case_2 = [877, 654, 2, 715, 229, 255, 712, 267, 19, 832]
for i in xrange(n):
    # get input     
    arr = map(int, raw_input().strip().split(' '))
    # find seed
    s = find_seed(arr)
    # set seed
    r = Random()
    r.set_seed(s)
    # assert the first 10 numbers are correct from the simple use case
    for j in xrange(10):
        print 'test_case_1 nextInt is: ' + str(test_case_1[j])
        print 'nextInt is: ' + str(r.nextInt(1000))
    # get next ten
    r_a = get_next_10(r)
    print ' '.join(str(x) for x in r_a)