Break the broken cipher

Question

I have designed a simple random generator that cycles two numbers in a chaotic way using a multiply and modulus method. It works great for that.

If I were to use it as a cipher generator it would however be vulnerable to a known plaintext attack, given that an attacker can reverse engineer the seed from a series of random numbers in a computationally efficient manner.

To prove the cipher broken find a legal pair of seed values that generate 7 zeros in a row in the range [0;255], using as little power, CPU-time etc. as possible.

Here is the random generator written in JavaScript:

function seed(state1,state2){
    //Constants
    var mod1=4294967087
    var mul1=65539
    var mod2=4294965887
    var mul2=65537
    function random(limit){
        //Cycle each state variable 1 step
        state1=(state1*mul1)%mod1
        state2=(state2*mul2)%mod2
        //Return a random variable
        return (state1+state2)%limit
    }
    //Return the random function
    return random
}

//Initiate the random generator using 2 integer values,
//they must be in the ranges [1;4294967086] and [1;4294965886]
random=seed(31337,42)
//Write 7 random values in the range [0;255] to screen
for(a=0;a<7;a++){
    document.write(random(256)+"<br>")
}

I have made a tool for testing candidate number pairs, it can be found here.

For the next 3 days, no spoilers allowed, an answer must contain only a set of numbers, and it should of course be a different set from those posted by previous solvers. Thereafter you are encouraged to post code and explain your approach.

Edit, quarantine is over:
Answers should contain both a unique set of numbers and explanation and code to document the solving method.

Most elegant solution wins.

For the record:
Writing a program that can find a solution quickly is elegant.
Making a program that utilize the features of a GPU efficiently to do it even faster is elegant.
Doing the job on a piece of "museumware" is elegant.
Finding a solution method that can feasibly be utilized using only pen and paper is very elegant.
Explaining your solution in an instructive and easily understandable manner is elegant.

Using multiple or very expensive computers is inelegant.

Answer 1

44014022 / 164607120

It is in C++, uses 1 GB of memory, and took about 45 seconds to find this first pair. I'll update the time once it finds them all.

Code below. It first finds all pairs that generate 4 zeros, then whittles those down by simple trial (see the check method). It finds pairs that generate 4 zeros by generating two large arrays, one which contains the first 4 low-order bytes of the state1 generator, and the second which contains the negative of the first 4 low-order bytes of the state2 generator. These arrays are then sorted and searched for a match, which corresponds to the overall generator outputting 4 zeros to start.

The arrays are too big to store in memory, so it does the work in batches sized to just fit in memory.

Looks like the complete run will take ~12 hours.

Edit: Improved the code so it only takes ~1 hour to get all possible seeds. Now it generates the tables into 256 different files, one for each first byte of output. We can then process each file independently so we don't have to regenerate data.

Edit: Turns out you can generate the 256 subtables individually instead of all at once, so no disk needed. Running time down to ~15 minutes using 256MB.

#include <stdio.h>
#include <stdint.h>
#include <algorithm>
using namespace std;

#define M1 65539
#define N1 4294967087
#define M2 65537
#define N2 4294965887
#define MATCHES 7

// M^-1 mod N                                                                                                                                                        
#define M1_INV 3027952124
#define M2_INV 1949206866

int npairs = 0;

void check(uint32_t seed1, uint32_t seed2) {
  uint32_t s1 = seed1;
  uint32_t s2 = seed2;
  for (int i = 0; i < MATCHES; i++) {
    s1 = (uint64_t)s1 * M1 % N1;
    s2 = (uint64_t)s2 * M2 % N2;
    if (((s1 + s2) & 0xff) != 0) return;
  }
  printf("%d %u %u\n", npairs++, seed1, seed2);
}

struct Record {
  uint32_t signature; // 2nd through 5th generated bytes                                                                                                             
  uint32_t seed;      // seed that generated them                                                                                                                    
};
// for sorting Records                                                                                                                                               
bool operator<(const Record &a, const Record &b) {
  return a.signature < b.signature;
}

int main(int argc, char *argv[]) {
  Record *table1 = (Record*)malloc((N1/256+1)*sizeof(*table1));
  Record *table2 = (Record*)malloc((N2/256+1)*sizeof(*table2));

  for (int i = 0; i < 256; i++) {  // iterate over first byte                                                                                                        
    printf("first byte %x\n", i);

    // generate signatures (bytes 2 through 5) for all states of generator 1                                                                                         
    // that generate i as the first byte.                                                                                                                            
    Record *r = table1;
    for (uint64_t k = i; k < N1; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j < 4; j++) {
        v = (uint64_t)v * M1 % N1;
        sig = (sig << 8) + (v & 0xff);
      }
      r->signature = sig;
      r->seed = k;
      r++;
    }
    Record *endtable1 = r;

    // generate signatures (bytes 2 through 5) for all states of generator 2                                                                                         
    // that generate -i as the first byte.                                                                                                                           
    r = table2;
    for (uint64_t k = (-i & 0xff); k < N2; k += 256) {
      uint32_t sig = 0;
      uint32_t v = k;
      for (int j = 0; j < 4; j++) {
        v = (uint64_t)v * M2 % N2;
        sig = (sig << 8) + (-v & 0xff);
      }
      r->signature = sig;
      r->seed = k;
      r++;
    }
    Record *endtable2 = r;

    sort(table1, endtable1);
    sort(table2, endtable2);

    // iterate through looking for matches                                                                                                                           
    const Record *p1 = table1;
    const Record *p2 = table2;
    while (p1 < endtable1  && p2 < endtable2) {
      if (p1->signature < p2->signature) p1++;
      else if (p1->signature > p2->signature) p2++;
      else {
        check((uint64_t)p1->seed * M1_INV % N1, (uint64_t)p2->seed * M2_INV % N2);
        // NOTE: may skip some potential matches, if p1->signature==(p1+1)->signature or p2->signature==(p2+1)->signature                                            
        p1++;
      }
    }
  }
}

Answer 2

394853262 / 506870

It's the one with the fewest combined digits of the 28 248 pairs I found up to now (including and discounting double zero).

C/C++^*, uses 64GB disk space and up to 4GB memory to brute force all seed pairs in about 80 minutes (single-threaded; most of it is embarassingly parallel).

Posting code tomorrow after I simplify it, nobody cares about my error detection after I removed the errors.

^* and I mean it as multiple languages.