Discussion :

[floatNone]

Bonjour à toutes et tous,

Je suis actuellement à la recherche d'une fonction capable de me générer un nombre pseudo-aléatoire mais avec quelques règles supplémentaires.

Cette fonction prendrait un argument (un entier) et retournerait un entier aléatoire associé.
L'argument sera la seed du nombre aléatoire retourné par la fonction.

Il faut aussi que la fonction soit bijective, c'est-à-dire que tous les entiers sont "générables" par la fonction.


Il ne faut pas qu'on puisse voir de motif dans la génération des nombres donc on peut exclure les fonctions affines ou exponentielles et logarithmiques.
Enfin, il faudrait que je puisse retrouver la seed depuis un nombre généré.

Voilà un exemple de ce que je voudrais obtenir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
fonction(45) ==> 878526
fonction(46) ==> 245
fonction(47) ==> 787654
fonction(48) ==> 7883111
 
noitcnof(245) ==> 46  // "noitcnof" = "fonction" à l'envers
noitcnof(7883111) ==> 48

J'ai cherché un peu sur internet avant de poser ma question ici et je suis tombé sur des articles (en anglais) qui parlaient de "bijective mapping" mais je n'ai rien trouvé de concluant en approfondissant sur cette piste.

Merci en tout cas pour vos futures réponses, floatNone.

[tbc92]

Tu veux une Bijection d'un ensemble E vers lui-même .... Et l'ensemble E, c'est ? C'est l'ensemble des entiers inférieurs à un certain nombre qu'on va choisir N.

En tant que bricoleur en chef, on va bricoler un truc :

Si je me souviens bien de mes cours de maths, si P1 et P2 sont 2 nombres premiers, la fonction suivante convient :
f(x) = Modulo( P1*x, P2)

Il faut prendre P2 très grand, plus grand que le nombre N du début.

Et pour trouver la fonction réciproque g, il y a un nombre unique Q1 tel que P1*Q1 = 1 [modulo P2]
La fonction réciproque serait donc g(x) = Modulo(Q1*x,P2)


Cette fonction n'est pas totalement affine, mais elle est affine par morceaux ... c'est gênant.
En combinant 3 ou 4 fois cette fonction, on va arriver à une fonction assez difficile à reconstituer :
y = Modulo(P1*x, P2)
z = Modulo(P3*y, P4)
t = Modulo(P5*z, P6)
f(x) = t

Et la fonction réciproque peut-être trouvée comme dans le premier cas.

La ""confidentialité"" est probablement faible.

Tu peux combiner cela avec une autre fonction :
x = 123456
Autrement dit , x = 0000000000123456 : je complète à gauche par des 0 , pour avoir nc = 16 chiffres.
et j'inverse : f(x) = 6543210000000000
En combinant cette technique avec la technique précédente, tu as une fonction qui devient plus difficile à reconstituer.

Reste à choisir les bonnes valeurs de P1 P2 P3 P4 P5 P6 et nc pour que les intervalles des fonctions soient compatibles.

De toutes façons, quand on parle de nombres aléatoires et de cryptologie, on tourne autour des nombres premiers.

[yahiko]

Je ne sais pas vraiment ce que tu souhaites faire au final, mais j'ai plutôt l'impression que tu souhaites une fonction dite de hachage plutôt qu'un générateur de nombre pseudo-aléatoire. Ce n'est pas tout à fait la même chose.

La fonction de hachage prend une donnée en entrée et la transforme de façon aléatoire, en apparence, en une autre donnée, de telle sorte que f(n) et f(n+epsilon) --- autrement dit deux données similaires en entrée --- donnent des résultats totalement différents.

Le générateur de nombres pseudo-aléatoire, c'est différent. C'est un objet qu'on initialise au tout départ à l'aide d'une graine (seed), puis qu'on appelle ensuite, sans argument pour ce qui est de la fonction de base, et qui génère une suite de nombres en apparence aléatoires.

[pseudocode]

Je ne sais pas vraiment ce que tu souhaites faire au final, mais j'ai plutôt l'impression que tu souhaites une fonction dite de hachage plutôt qu'un générateur de nombre pseudo-aléatoire.

D'après sa description et son exemple, il veut plutôt un "block cipher" = un bijective mapping d'un champ de bits.

Puisqu'il s'agit de transformer un entier en un autre entier aléatoire, le plus simple c'est de prendre l'algo RC5 sur 32bits (ou 64 bits, suivant la taille de l'entier).

[pseudocode]

Puisqu'il s'agit de transformer un entier en un autre entier aléatoire, le plus simple c'est de prendre l'algo RC5 sur 32bits (ou 64 bits, suivant la taille de l'entier).

S'il n'est pas nécessaire d'avoir un haut niveau de résistance à la cryptanalyse, on peut se limiter à permuter les 32 bits de l'entier.
C'est à dire créer une bijection de (0,1,...,31) vers (0,1,..,31).

encode(45)=2162832  /  decode(2162832)=45
encode(46)=66704    /  decode(66704)=46
encode(47)=2163856  /  decode(2163856)=47
encode(48)=130      /  decode(130)=48

On peut aussi travailler par groupe de 8 bits et créer une bijection de (0,...,256) vers (0,...,256).
On applique alors la permutation sur chacun des 4 octets qui forment l'entier.

Tout cela nécessite simplement de créer une table de conversion, c'est à dire créer un tableau (1...N) et de la mélanger de manière pseudo-aléatoire en fixant la seed du générateur (afin de pouvoir reconstruire la table de conversion à partir de la même seed).

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Simple 32bit swapping
int[] cipher = createCipher(314159265359L); // our seed
int encoded  = encode(45, cipher);
int decoded  = decode(2162832, cipher);
 
int[] createCipher(long seed) {
	int[] cipher = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31};
	Random randomizer = new Random(seed);
	for (int i = 0; i < 32; i++) {
		int k = randomizer.nextInt(32);
		int swap = cipher[i]; cipher[i] = cipher[k]; cipher[k] = swap;
	}
	return cipher;
}
 
int encode(int input, int[] cipher) {
	int output = 0;
	for (int bit = 0; bit < 32; bit++)
		if ((input & (1L << bit)) != 0)
			output |= 1L << cipher[bit];
	return output;
}
 
int decode(int input, int[] cipher) {
	int output = 0;
	for (int bit = 0; bit < 32; bit++)
		if ((input & (1L << bit)) != 0)
			output |= 1L << indexOf(cipher, bit);
	return output;
}
 
public static int indexOf(int[] array, int value) {
	for (int i = 0; i < array.length; i++) if (value == array[i]) return i;
	return -1;
}

[wiwaxia]

Bonjour,

Je viens de trouver fortuitement une collection de générateurs congruenciels linéaires, programmés dans 67 langages ... Si cela peut en intéresser quelques uns: c'est sur le site Rosetta.org

[Maschmalow]

Ce que tu cherche est une permutation aléatoire (sur ton ensemble d'entier). Grosso modo une permutation ca décrit une table de correspondances entre les différents éléments de ton ensemble. Une permutation aléatoire c'est une permutation prise au hasard dans l'ensemble des permutations qui existe.

A partir de là tu a deux manières de procéder:
Tu génère un permutation aléatoire, ce qui revient bêtement à génerer ta table de correspondances. Tu peux le faire par exemple avec leMélange de Fisher-Yates, mais ca veut dire que tu dois stocker toute la table en mémoire (donc si tu veux faire tous les nombres sur 32 bits par exemple ca va être chaud).

Sinon tu peux génerer ta table au fur et a mesure. C'est à dire que tu commence avec ta table vide, et tu la remplis avec un nombre aléatoire à chaque fois qu'il y a une requète pour un nombre qui n'a pas encore été demandé. Mais la encore si tu as plein de requètes sur plein de nombres différents, ça consome de la mémoire.

Dans tous les cas la table de correspondance se fera avec une Bidirectional map, pour garantir la bijection et pour pouvoir récupérer les clés à partir des valeurs. Il y a rien de magique la-dedans, c'est essentiellement deux tables de hachages dont les clés de l'une sont les valeurs de l'autre, et inversement.

Après avoir lu ton message, j'ai plus l'impression que ton but c'est de mettre en relation deux nombres (peu importe lesquels) de façon à ce que personne ne puisse prédire les prochaines associations, même connaissant les associations actuelles. Dans ce cas tu as une solution simple: tu génère une clé privée (et qui le reste !), et tu chiffre/déchiffre ton nombre avec un algo de chiffrement à flot (au hasard, ChaCha20) pour avoir les correspondances.

Génerer un tableau est peut être plus simple a implémenter (pas besoin de lib, le tout se fait en quelques lignes de code max), mais demande un espace de stockage proportionnel au nombre d'associations que tu fais. La technique du chiffrement se fait grosso modo en temps et mémoire constant, mais ça demande un poil plus de réflexion et de recherche.