Я разработал простой генератор случайных чисел, который циклически переключает два числа, используя метод умножения и модуля. Это прекрасно работает для этого.

Если бы я использовал его в качестве генератора шифров, он, однако, был бы уязвим для известной атаки открытым текстом, учитывая, что злоумышленник может произвести обратное проектирование начального числа из серии случайных чисел вычислительно эффективным способом.

Чтобы доказать, что шифр сломан, найдите правильную пару начальных значений, которые генерируют 7 нулей подряд в диапазоне [0; 255], используя как можно меньше энергии, времени ЦП и т. Д.

Вот генератор случайных чисел, написанный на 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>")
}

Я сделал инструмент для тестирования пар номеров кандидатов, его можно найти здесь .

В течение следующих 3 дней спойлеры запрещены , ответ должен содержать только набор чисел, и он, конечно, должен отличаться от тех, которые были опубликованы предыдущими решателями. После этого вам предлагается опубликовать код и объяснить свой подход.

Изменить, карантин окончен:
ответы должны содержать как уникальный набор чисел, так и пояснения и код для документирования метода решения.

Самое элегантное решение побеждает.

Для справки:
написание программы, которая может быстро найти решение, элегантно.
Создание программы, которая эффективно использует возможности графического процессора, чтобы сделать это еще быстрее, элегантно.
Делать работу над частью «музейной посуды» - это элегантно.
Найти метод решения, который можно реально использовать, используя только ручку и бумагу, очень элегантно.
Объяснять ваше решение поучительным и легко понятным способом - элегантно.

Использование нескольких или очень дорогих компьютеров не элегантно.

C ++, 44014022/164607120

Он находится в C ++, использует 1 ГБ памяти и занял около 45 секунд, чтобы найти эту первую пару. Я обновлю время, когда он их всех найдет.

Код ниже. Сначала он находит все пары, которые генерируют 4 нуля, а затем сокращает их путем простого испытания (см. checkМетод). Он находит пары, которые генерируют 4 нуля, генерируя два больших массива, один из которых содержит первые 4 младших байта генератора state1, а второй - отрицательный из первых 4 младших байтов генератора state2. Эти массивы затем сортируются и ищутся совпадения, которые соответствуют общему генератору, выводящему 4 нуля для запуска.

Массивы слишком велики, чтобы их можно было хранить в памяти, поэтому они выполняют работу в пакетах, размер которых не помещается в памяти.

Похоже, полный цикл займет ~ 12 часов.

Изменить : Улучшен код, так что требуется всего ~ 1 час, чтобы получить все возможные семена. Теперь он генерирует таблицы в 256 разных файлах, по одному на каждый первый байт вывода. Затем мы можем обрабатывать каждый файл независимо, поэтому нам не нужно восстанавливать данные.

Изменить : Оказывается, вы можете генерировать 256 подтаблиц по отдельности, а не все сразу, поэтому диск не требуется. Время работы до ~ 15 минут с использованием 256 МБ.

#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++;
      }
    }
  }
}