Zaprojektowałem prosty generator losowy, który cyklicznie zamienia dwie liczby za pomocą metody mnożenia i modułu. Działa to doskonale.

Gdybym użył go jako generatora szyfrów, byłby jednak podatny na znany atak w postaci tekstu jawnego, biorąc pod uwagę, że osoba atakująca może odwrócić inżynierowanie ziarna od szeregu liczb losowych w sposób efektywny obliczeniowo.

Aby udowodnić, że złamano szyfr, znajdź legalną parę wartości początkowych, które generują 7 zer w rzędzie w zakresie [0; 255], zużywając jak najmniej energii, czasu procesora itp., Jak to możliwe.

Oto losowy generator napisany w 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>")
}

Stworzyłem narzędzie do testowania par numerów kandydatów, można je znaleźć tutaj .

Przez następne 3 dni spoilery nie są dozwolone , odpowiedź musi zawierać tylko zestaw liczb, i oczywiście powinien być inny zestaw niż te publikowane przez poprzednie solwery. Następnie zachęcamy do pisania kodu i wyjaśnienia swojego podejścia.

Edycja, kwarantanna się zakończyła:
odpowiedzi powinny zawierać zarówno unikalny zestaw liczb, jak i objaśnienie oraz kod dokumentujący metodę rozwiązywania.

Najbardziej eleganckie rozwiązanie wygrywa.

Dla przypomnienia: napisanie
programu, który szybko znajdzie rozwiązanie, jest eleganckie.
Tworzenie programu, który efektywnie wykorzystuje funkcje GPU, aby zrobić to jeszcze szybciej, jest eleganckie.
Wykonanie pracy na „muzealnym sprzęcie” jest eleganckie.
Znalezienie metody rozwiązania, która może być wykorzystana tylko za pomocą długopisu i papieru, jest bardzo eleganckie.
Wyjaśnienie rozwiązania w pouczający i łatwo zrozumiały sposób jest eleganckie.

Korzystanie z wielu lub bardzo drogich komputerów jest nieeleganckie.

C ++, 44014022/164607120

Jest w C ++, zużywa 1 GB pamięci i znalezienie pierwszej pary zajęło około 45 sekund. Zaktualizuję czas, gdy znajdzie je wszystkie.

Kod poniżej. Najpierw znajduje wszystkie pary, które generują 4 zera, a następnie zmniejsza je za pomocą prostej próby (patrz checkmetoda). Znajduje pary, które generują 4 zera, generując dwie duże tablice, z których jedna zawiera pierwsze 4 bajty niskiego rzędu generatora state1, a druga zawiera ujemną liczbę pierwszych 4 bajtów niskiego rzędu generatora state2. Te tablice są następnie sortowane i wyszukiwane w celu znalezienia dopasowania, które odpowiada ogólnemu generatorowi wysyłającemu 4 zera na start.

Tablice są zbyt duże, aby zapisać je w pamięci, więc działa w partiach o rozmiarze dopasowanym do pamięci.

Wygląda na to, że pełny przebieg zajmie ~ 12 godzin.

Edycja : Poprawiony kod, więc uzyskanie wszystkich możliwych nasion zajmuje tylko ~ 1 godzinę. Teraz generuje tabele w 256 różnych plikach, po jednym dla każdego pierwszego bajtu wyniku. Następnie możemy przetwarzać każdy plik niezależnie, więc nie musimy ponownie generować danych.

Edycja : Okazuje się, że możesz wygenerować 256 podtabel indywidualnie zamiast wszystkich naraz, więc nie potrzebujesz dysku. Czas pracy do ~ 15 minut przy 256 MB.

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