J'ai conçu un générateur aléatoire simple qui fait tourner deux nombres de manière chaotique en utilisant une méthode de multiplication et de module. Cela fonctionne très bien pour cela.

Si je devais l'utiliser comme générateur de chiffrement, il serait cependant vulnérable à une attaque connue en texte brut, étant donné qu'un attaquant peut inverser la graine à partir d'une série de nombres aléatoires de manière efficace sur le plan des calculs.

Pour prouver que le chiffrement est rompu, trouvez une paire légale de valeurs de départ qui génèrent 7 zéros de suite dans la plage [0; 255], en utilisant le moins d'énergie, de temps CPU, etc. possible.

Voici le générateur aléatoire écrit en 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>")
}

J'ai fait un outil pour tester les paires de nombres candidats, il peut être trouvé ici .

Pour les 3 prochains jours, aucun spoilers n'est autorisé , une réponse ne doit contenir qu'un ensemble de chiffres, et il doit bien sûr être différent de ceux publiés par les solveurs précédents. Par la suite, nous vous encourageons à publier du code et à expliquer votre approche.

Modifier, la quarantaine est terminée: les
réponses doivent contenir à la fois un ensemble unique de chiffres et d'explications et de code pour documenter la méthode de résolution.

La solution la plus élégante gagne.

Pour mémoire:
écrire un programme qui peut trouver une solution rapidement est élégant.
Il est élégant de créer un programme qui utilise efficacement les fonctionnalités d'un GPU pour le faire encore plus rapidement.
Faire le travail sur un "matériel de musée" est élégant.
Trouver une méthode de solution qui peut être utilisée en utilisant uniquement un stylo et du papier est très élégant.
Expliquer votre solution d'une manière instructive et facilement compréhensible est élégant.

L'utilisation d'ordinateurs multiples ou très coûteux n'est pas élégante.

C ++, 44014022/164607120

Il est en C ++, utilise 1 Go de mémoire et a mis environ 45 secondes pour trouver cette première paire. Je mettrai à jour l'heure une fois qu'il les aura tous trouvés.

Code ci-dessous. Il trouve d'abord toutes les paires qui génèrent 4 zéros, puis les réduit par simple essai (voir la checkméthode). Il trouve des paires qui génèrent 4 zéros en générant deux grands tableaux, l'un qui contient les 4 premiers octets de poids faible du générateur state1, et le second qui contient le négatif des 4 premiers octets de poids faible du générateur state2. Ces tableaux sont ensuite triés et recherchés pour une correspondance, ce qui correspond au générateur global produisant 4 zéros pour démarrer.

Les tableaux sont trop gros pour être stockés en mémoire, donc il fait le travail par lots dimensionnés pour tenir juste en mémoire.

Il semble que l'exécution complète prenne environ 12 heures.

Edit : Amélioration du code, il ne faut que ~ 1 heure pour obtenir toutes les graines possibles. Maintenant, il génère les tables dans 256 fichiers différents, un pour chaque premier octet de sortie. Nous pouvons ensuite traiter chaque fichier indépendamment afin de ne pas avoir à régénérer les données.

Modifier : il s'avère que vous pouvez générer les 256 sous-tables individuellement au lieu de toutes en même temps, donc aucun disque n'est nécessaire. Durée de fonctionnement jusqu'à ~ 15 minutes en utilisant 256 Mo.

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