Tests statistiques sur les générateurs physiques de nombres aléatoires (TRNGs)
Institution:
Aix-Marseille 1Disciplines:
Directors:
Abstract EN:
Statistical tests related to the entropy estimation of a random source are widely used in testing of true random number generators (TRNGs,True Random Number Generators) intended for cryptographic applications. Namely, Maurer’s universal statistical test is nowadays viewed as a standard in this domain. Therefore, from a statistical viewpoint, this thesis is focused on further developments of entropy tests. It consists in three main parts : The design of a generic software tool called Genstar, Generic Statistical Test Architecture. Genstar consists in a collection of statistical tests for random number generators. This software is developed with the help of the objet oriented programming, thus providing a common interface enabling easy integration of new statistical tests in Genstar. The second important characteristic of Genstar is related to the problem of comparison of statistical tests. To compute the power of a given statistical test, Genstar is equipped with a family of statistical models of TRNGs. Improvements of Maurer’s test. To improve statistical characteristics of this test, we propose several approaches such as the m-spacing and the p-leave out methods. In the very core of these methods is a new interpretation of the Maurer test related to the maximum likelihood tests for the problem of uniformity testing. It’s well known that the standard Maurer test cannot detect long memory dependencies in the data. In order to overcome this difficulty, we propose two approaches. The first one, called (SD test), computes the distribution of distances between motifs in the data. The second approach called MaurerPP is based on the idea of the equivalence of motifs. This equivalence permits to reduce multiple motifs testing to one generic motif testing and resolves efficiently the problem of large blocks in the Maurer test. Standard normality of m-spacings entropy estimators under weaker assumptions on the probability density. The improvements of the Maurer test proposed in this thesis are essentially based on the m - spacing method in the entropy estimation. In this thesis, we show that under mild conditions on the probability density, i. E. For vanishing densities, the m-spacings entropy estimators have the standard Gaussian limit.
Abstract FR:
L’objectif de cette thèse est de fournir des solutions aux problèmes de tests statistiques appliqués sur les séquences binaires issues des générateurs physiques de nombres aléatoires (TRNGs,True Random Number Generators). Les tests statistiques de l’entropie sont les tests les plus importants pour tester les TRNGs. Plus particulièrement, le test universel de Maurer est considéré aujourd’hui comme étant une référence pour tester l’entropie de ces générateurs. Le travail de la thèse peut se résumer en les trois contributions suivantes. La conception d’un outil logiciel que nous avons nommé Genstar, Generic Statistical Test Architecture formé de tests statistiques sur les générateurs de nombres aléatoires. Les caractéristiques importantes de cet outil sont de munir les tests statistiques qui y figurent de méthodes communes, de pouvoir intégrer tout test statistique programmable que l’on veut implémenter et surtout de fournir des méthodes de comparaison de deux ou plusieurs tests statistiques. L’amélioration du test de Maurer ; nous fournissons plusieurs méthodes pour l’amélioration du test telles que la méthode du m-spacing ou du p-leave out et proposons de nouveaux tests complémentaires remédiant à plusieurs problèmes liés au test de Maurer dans les cas où l’alternative consiste en des chaînes de Markov de longues mémoires (SD test), ou le cas où la longueur de blocs du test est très grande (MaurerPP). On s’appuie sur Genstar pour illustrer numériquement les meilleures performances de ces tests pour des alternatives typiques. Les améliorations que nous proposons au test de Maurer étant en partie basées sur la méthode du m-spacing pour l’estimation de l’entropie, on prouve la convergence de ces estimateurs vers la loi gaussienne sous des hypothèses plus générales sur les propriétés de la fonction de densité.