Discussion :

[Sidenn]

Bonjour à tous,

Je cherche à réaliser un générateur cryptographique de nombres pseudo-aléatoires.

Qu'est-ce que c'est qu'un générateur de nombres aléatoires, pseudo-aléatoires ?

C'est une fonction qui donne en sortie des nombres. A chaque appel la fonction donne un nombre différent. On l'appelle aléatoire parce que tous ces nombres semblent indépendants les uns des autres. On dit "semblent" car la machine étant totalement déterministe, les algorithmes sont eux même déterministes. Donc les nombres en sortie du générateur dépendent tout de même les uns des autres, mais il est tellement difficile de faire la relation entre les uns et les autres sans la fonction de base que l'on finit par dire qu'ils sont pseudo-aléatoires.

Qu'est-ce qu'un générateur cryptographique de nombre pseudo-aleatoire ?

C'est un générateur de nombres aléatoires le moins biaisé possible, c'est à dire qu'il favorise une équiprobabilité de chacunes des sorties du générateur. La plus part des générateurs le font, mais pas assez bien pour une utilisation cryptographique. C'est à dire qu'il faut favoriser l'uniformité des sorties dans le domaine de définition de la sortie de la fonction, de l'algorithme. C'est exactement le contraire de la courbe de Gauss qui donne un maximum à une certaine valeure.

Pour quoi faire ?

J'en ai "besoin" afin de pouvoir l'inserer dans un programme de chiffrement à clef symétrique que je développe moi même. J'ai tout de même quelques difficultés à développer un suffisement bon générateur cryptographique de nombres pseudo-aléatoires. J'en ai développé un dont les sorties ont toutes une probabilité de sortie moyenne de 0,1% avec un écart-type de 0,5%, ce qui est bien trop grand pour une utilisation cryptographique.


Si l'un de vous sait comment développer une telle fonction je lui serais reconnaissant de bien vouloir m'aider. Par la même occasion, je sais qu'il existe un certain nombre de fonctions existant, telles que "Blum Blum Shub", "Fortuna", "ISAAC", cependant je n'arrive pas à trouver les codes sources et quand je les trouve, j'avoue ma difficulté à dénicher une once de documentation pour me permettre d'utiliser ces codes.

Dans l'attente d'une réponse de votre part,

phmorin

PS: j'avais posté ce sujet sur le forum du C mais on m'a dit de le mettre ici.

[Matthieu Brucher]

Mersenne-Twister a un bon point à ce niveau.

[Sidenn]

Aurais-tu une idée où je pourrais trouvé l'algorithme et encore mieux un code source en C?

[jobherzt]

si je puis me permettre, Mersenne Twister est recommandé pour l'utilisation en modélisation statistique, notamment pour sa stablité en grande dimension, mais il n'est pas recommandé pour la cryptographie, vu qu'on peut le "casser" assez facilement.

[Matthieu Brucher]

L'autre solution, c'est alors d'utiliser un générateur avec hasard fort, mais ça n'existe pas en algorithmie...

[thewho]

Bonjour,

si je puis me permettre, Mersenne Twister est recommandé pour l'utilisation en modélisation statistique, notamment pour sa stablité en grande dimension, mais il n'est pas recommandé pour la cryptographie, vu qu'on peut le "casser" assez facilement.

Qu'appelles-tu "casser" un générateur pseudo-aléatoire ?

[millie]

Qu'appelles-tu "casser" un générateur pseudo-aléatoire

Une définition simple serait de savoir déterminer le nombre suivant une génération.

En général, on fait passer des tests de validations des générateurs pseudo aléatoires (pour éviter ce genre de phénomène). La majeure partie de ces tests sont statistiques (test de fréquence, test de séries, tests des intervalles, tests du collectionneur de coupons, et tests de permutations).

Ya aussi des méthodes qui permettent de "casser" partiellement le générateur. Par exemple en prouvant que sur certaines périodes, le générateur prend autant de valeur pair qu'impair.

TROLL ON

algorithmie...

Paraitrait-t-il que le terme algorithmie n'existe pas (même si il est parfois employé à tort), ce serait algorithmique.

[Matthieu Brucher]

Paraitrait-t-il que le terme algorithmie n'existe pas (même si il est parfois employé à tort), ce serait algorithmique.

Effectivement, parfois j'emplois l'un, parfois l'autre, ils sont à priori synonymes.

[jobherzt]

"casser" un generateur aleatoire, cela vet dire : en observant une serie de valeur en sortie du generateur, parvenir a retrouver la "graine" et les eventuels parametres, et donc pouvoir predire la suite... de la suite :-) . il existe un algo qui le fait pour le mersenne twister. c'est assez subtile, mais un algo peut generer une suite qui a les propriété d'une suite impredicitble... mais qui est quand meme predictible meme sans connaitre la graine.

donc en fait, on ne peut pas distinguer la sortie de mersenne d'une suite aleatoire... mais en fait on peut.. ces 2 affirmations qui semblent se contredire correspondent a 2 aspects mathmeatique differents ! si par exemple tu developpe un algo probabiliste (Miller Rabin, par exemple), ou que tu veux simuler un deplacement aleatoire dans un espace a plusieurs dimensions, Mersenne twister sera plus recommandé qu'un algo cryptographique, car plus riche en propriété statistique. en revanche, pour un algo de chiffrement, cela s'inverse.

[Graffito]

Bonjour,

Je ne sais pas si le nombre de tirages et la borne supérieure des nombres aléatoires permettent l'implémentation, mais on peut associer à chaque tirage un nombre le nombre pseudo-aléatoire (venant d'un algo quelquonque) :

Code :

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

1
2
3
4
5
1 : N1 (1)
2 -> N2 (2)
3 -> N3 (3)
...
n -> Nn (n)

Trier les éléments Ni (i) en ordre croissant fonction de Ni et i.
Remplacer Ni par la position Px dans le tableau trié modulo la borne des nombres aléatoires.
Retrier en fonction de n : ce qui pemet d'associer à n la valeur Px dont la répartition sera parfaitement equiprobable.

[jobherzt]

graffito, j'avoue que je ne vois pas bien ou tu veux en venir..

[Graffito]

Bonjour,

Je répondais à ce besoin :

C'est à dire qu'il faut favoriser l'uniformité des sorties dans le domaine de définition de la sortie de la fonction, de l'algorithme.

Le traitement proposé permet d'avoir des répartitions équiprobables.
le nombre d'occurence d'un nombre étant soit X , soit X+1.
(X=T div D, avec T=nb de tirages et D=nb de valeurs dans le domaine de définition).