Générateur de nombres pseudo-aléatoires (pseudo random number generator - lfsr)

Soyez le premier à donner votre avis sur cette source.

Vue 29 897 fois - Téléchargée 830 fois

Description

Voici un générateur de nombres pseudo-aléatoires basé sur la description faite par Bruce Schneier d'une "cascade de Gollmann" (Cryptographie appliquée, page 411 de l'édition française).
J'ai choisi de l'implémenter avec 20 registres à décalage (lfsr) : un de 128 bit, 3 de 64 bit et 16 de 32 bit. L'implé est assez algorithmique et certainement pas optilmisée (voir les appels direct au CPU pour la rotation des mots de 32 bits).
Les polynômes primitifs pour les opérations sur ces registres sont choisis en fonction de la graine (992 bit). Ils sont tous denses et calculés avec le logiciel de calcul formel MUPAD. La graine est stocké dans un fichier ("/bin/seed.txt" pour l'exemple), elle doit être changée après chaque utilisation dans la pratique (on peut utiliser les 992 derniers bits générés ...).
J'ai implémenté une version graphique des tests simples du FIPS 140-1. Ca fonctionne sous linux + X11 et c'est opensource.

Source / Exemple :


/* just a sample, see the zip  file for more */

/*

  • Copyright (c) 2004-2005, contax. All rights reserved.
  • LICENSE TERMS
  • The free distribution and use of this software in both source and
  • binary form is allowed (with or without changes) provided that:
  • 1. distributions of this source code include the above copyright
  • notice, this list of conditions and the following disclaimer;
  • 2. distributions in binary form include the above copyright notice,
  • this list of conditions and the following disclaimer in the
  • documentation and/or other associated materials;
*
  • DISCLAIMER
  • This software is provided 'as is' with no explicit or implied
  • warranties in respect of its properties, including, but not limited to,
  • correctness and fitness for purpose.
  • /
#include <unistd.h> #include <sys/mman.h> #include <stdio.h> #include <errno.h> #include "destroy.h" #include "./lfsr/lfsr.h" #define _RANDOM_LOCAL #include "random.h" #undef _RANDOM_LOCAL LFSR_CTX * rand_init(int fd) { LFSR_CTX *ctx; uint32_t *sd; if (NULL == lfsr_alloc(ctx)) { perror("lfsr_alloc"); return NULL; } if ((void *) -1 == (sd = (uint32_t *) mmap(0, 31 * sizeof(uint32_t), PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0))) { perror("projection"); lfsr_ctx_free(ctx); return NULL; } (void) lfsr_init(ctx, sd); munmap(sd, 31 * sizeof(uint32_t)); return ctx; }

Conclusion :


Si vous avez un message d'erreur concernant X11 à l'issue de l'édition de liens, c'est que vos fichier d'en-tête et votre librairie X11 ne se trouvent pas dans le répertoire /usr/X11R6/ : changez les références dans le fichier /rand/bin/subdir.mk.

mode d'emploi :
unzip *****.zip && cd /rand/bin && make && Xtest nom_du_fichier_de_graine [nb_de_points_dessinés]
le nombre de point dessinés est optionnel (65000 par défaut).

les tests dépendent des 20000 premiers bits générés. Il ne changent donc pas en fonction du nombre de points dessinés mais en fonction de la graine !

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

malik7934
Messages postés
1162
Date d'inscription
mardi 9 septembre 2003
Statut
Membre
Dernière intervention
15 août 2009
1 -
Hello,

Ca m'a l'air pas mal tout ça, faudra que je le teste ;o)

Une question tout de même: est ce que ta référence dit si c'est un PRNG cryptographiquement sûr ou algorithmiquement sûr? Car même si un PRNG est proche de l'aléatoire, même si la graine est cryptographiquement sûr, il faut que les fonctions soient impossibles à retrouver à partir de samples...

En tous cas bravo ;o)
contax
Messages postés
20
Date d'inscription
lundi 17 janvier 2005
Statut
Membre
Dernière intervention
13 mars 2005
-
Cryptographiquement sûr en 1996 (date de la parution du livre) ... depuis je ne sais pas.
ihms
Messages postés
1
Date d'inscription
mercredi 22 février 2012
Statut
Membre
Dernière intervention
22 février 2012
-
Bonjour,

J'ai l'erreur suivante :
Fichier de compilation : ../Xtest.c
gcc -I/usr/X11R6/include -O3 -Wall -c -fmessage-length=0 -oXtest.o ../Xtest.c
../Xtest.c:38:22: fatal error: X11/Xlib.h: No such file or directory
compilation terminated.
make: *** [Xtest.o] Error 1

Que dois-je faire pour la régler?

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.