des nombres aléatoires plus savoureux si un peu de poivreNous combinerons théorie et pratique - nous montrerons qu'il est possible d'améliorer l'entropie de séquences aléatoires, après quoi nous examinerons les codes sources qui le font.
Je voulais vraiment écrire sur le fait que la génération de nombres aléatoires de haute qualité, c'est-à-dire très entropiques, est essentielle pour résoudre un grand nombre de problèmes, mais cela est probablement superflu. J'espère que tout le monde le sait très bien.
À la recherche de nombres aléatoires de qualité, les gens inventent des appareils très spirituels (voir, par exemple,
ici et
ici ). En principe, de très bonnes sources d'aléatoire sont intégrées dans l'API des systèmes d'exploitation, mais c'est un problème grave, et un ver de doute nous mange toujours un peu: le RNG que j'utilise est-il assez bon et est-il gâché ... disons, par des tiers?
Un peu de théorie
Pour commencer, nous montrons qu'avec la bonne approche, la qualité du RNG existant ne peut pas être dégradée. L'approche correcte la plus simple consiste à superposer toute autre séquence via l'opération XOR sur la séquence
principale .
La séquence
principale peut être, par exemple, un RNG systémique, que nous considérons déjà comme bon, mais il y a encore des doutes, et nous avions envie de le jouer en toute sécurité.
Une séquence
supplémentaire peut être, par exemple, un générateur de nombres pseudo-aléatoires dont la sortie semble bonne, mais nous savons que son entropie réelle est très faible.
La séquence
résultante sera le résultat de l'application de l'opération XOR aux bits des séquences primaire et secondaire.
Une nuance importante: les séquences primaires et secondaires doivent être indépendantes l'une de l'autre. Autrement dit, leur entropie doit provenir de sources fondamentalement différentes, dont l'interdépendance ne peut être calculée.
Notons
x le bit suivant de la séquence principale et
y - le bit correspondant de la séquence supplémentaire. Le bit de la séquence résultante est noté
r :
r = x⊕y
La première tentative de prouver. Essayons de passer par l'entropie informationnelle de
x ,
y et
r . Nous désignons la probabilité de zéro
x comme
p x0 et la probabilité de zéro
y comme
p y0 . Les entropies d'informations
x et
y sont calculées selon la formule de Shannon:
H
x = - (p
x0 log
2 p
x0 + (1 - p
x0 ) log
2 (1 - p
x0 ))
H
y = - (p
y0 log
2 p
y0 + (1 - p
y0 ) log
2 (1 - p
y0 ))
Zéro dans la séquence résultante apparaît quand il y a deux zéros ou deux unités à l'entrée. Probabilité de zéro r:
p
r0 = p
x0 p
y0 + (1 - p
x0 ) (1 - p
y0 )
H
r = - (p
r0 log
2 p
r0 + (1 - p
r0 ) log
2 (1 - p
r0 ))
Afin de prouver l'invariabilité de la séquence principale, il est nécessaire de prouver que
Hr - Hx ≥ 0 pour toutes les valeurs de
p x0 et
p y0 . Je ne pouvais pas le prouver analytiquement, mais le calcul visualisé montre que l'augmentation de l'entropie forme une surface lisse, qui n'ira nulle part ailleurs:
Par exemple, si nous ajoutons un signal supplémentaire très asymétrique avec
p y0 = 0,1 au signal principal asymétrique c
p x0 = 0,3 (entropie 0,881), nous obtenons le résultat
p r0 = 0,66 avec entropie 0,925.
L'entropie ne peut donc pas être gâchée, mais ce n'est pas encore exact. Par conséquent, une deuxième tentative est nécessaire. Cependant, grâce à l'entropie, on peut également le prouver. Schéma (toutes les étapes sont assez simples, vous pouvez le faire vous-même):
- Nous prouvons que l'entropie a un maximum au point p 0 = 1/2.
- Nous prouvons que pour tout p x0 et p y0, la valeur de p r0 ne peut pas être plus éloignée de 1/2 que p x0 .
La deuxième tentative de prouver. Grâce à la capacité de deviner. Supposons qu'un attaquant ait a priori quelques informations sur les séquences primaire et secondaire. La possession d'informations s'exprime dans la capacité avec une certaine probabilité de deviner à l'avance les valeurs de
x ,
y et, par conséquent,
r . Les probabilités de deviner
x et
y sont respectivement notées
g x et
g y (d'après le mot guess). Le bit de la séquence résultante est deviné soit lorsque les deux valeurs sont devinées correctement, soit lorsque les deux sont incorrectes, donc la probabilité de deviner est la suivante:
g
r = g
x g
y + (1 - g
x ) (1 - g
y ) = 2 g
x g
y - g
x - g
y + 1
Lorsque nous avons le devineur parfait, nous avons
g = 1. Si nous ne savons rien,
g est ... non, pas zéro, mais 1/2. C'est exactement la probabilité de deviner si nous prenons une décision en lançant une pièce. Un cas très intéressant est lorsque
g <1/2. D'une part, un tel devineur quelque part en lui-même possède des données sur la valeur prédite, mais pour une raison quelconque, inverse sa sortie, et donc la
pièce devient
pire . N'oubliez pas l'expression «pire qu'une pièce», elle nous sera utile ci-dessous. Du point de vue de la théorie mathématique de la communication (et, par conséquent, de la théorie quantitative de l'information qui nous est familière), cette situation est absurde, car ce ne sera pas une théorie de l'information, mais une théorie de la désinformation, mais dans la vie nous avons cette situation beaucoup plus souvent que nous le souhaiterions .
Considérez les cas limites:
- g x = 1 , c'est-à-dire que la séquence x est complètement prévisible:
g r = g x g y + (1 - g x ) (1 - g y ) = 1 g y + (1−1) (1 - g y ) = g y
Autrement dit, la probabilité de deviner le résultat est égale à la probabilité de deviner la séquence supplémentaire. - g y = 1 : similaire à la précédente. La probabilité de deviner le résultat est égale à la probabilité de deviner la séquence principale.
- g x = 1/2 , c'est-à-dire que la séquence x est complètement imprévisible:
g r = 2 g x g y - g x - g y + 1 = 2/2 g y - 1/2 - g y +1 = g y - g y + 1/2 = 1/2
C'est-à-dire que l'ajout de toute séquence supplémentaire ne nuit pas à l'imprévisibilité complète de la séquence principale. - g y = 1/2 : similaire à la précédente. L'ajout d'une séquence supplémentaire complètement imprévisible rend le résultat complètement imprévisible.
Afin de prouver que l'ajout d'une séquence supplémentaire à la séquence principale n'aidera pas l'attaquant, nous devons déterminer dans quelles conditions
g r peut être supérieur à
g x , c'est-à-dire
2 g
x g
y - g
x - g
y + 1> g
xDéplacez g
x du côté droit vers la gauche, et g
y et 1 vers la droite:
2 g
x g
y - g
x - g
x > g
y - 1
2 g
x g
y - 2 g
x > g
y - 1
On sort sur le coté gauche 2g
x hors crochets:
2 g
x (g
y - 1)> g
y - 1
Puisque nous avons g
y inférieur à un (le cas limite lorsque g
y = 1, nous l'avons déjà considéré), nous transformons g
y -1 en 1 - g
y , sans oublier de changer «plus» en «moins»:
2 g
x (1 - g
y ) <1 - g
yRéduisez «1 - g
y » et obtenez la condition dans laquelle l'ajout d'une séquence supplémentaire améliorera la situation pour que l'attaquant devine:
2 g
x <1
g
x <1/2
Autrement dit,
g r peut être supérieur à
g x uniquement lorsque l'on suppose que la séquence principale est
pire qu'une pièce . Ensuite, lorsque notre prédicteur est engagé dans un sabotage conscient.
Quelques considérations supplémentaires sur l'entropie.- L'entropie est un concept extrêmement mythologique. Informations - y compris. C'est très inquiétant. Souvent, l'entropie informationnelle est représentée comme une sorte de matière subtile qui est objectivement présente dans les données ou non. En fait, l'entropie informationnelle n'est pas quelque chose qui est présent dans le signal lui-même, mais une évaluation quantitative de la conscience a priori du destinataire du message concernant le message lui-même. Autrement dit, il ne s'agit pas seulement du signal, mais aussi du destinataire. Si le destinataire ne sait rien du tout sur le signal à l'avance, l'entropie informationnelle de l'unité binaire transmise est exactement de 1 bit, indépendamment de la façon dont le signal a été reçu et de ce qu'il est.
- Nous avons un théorème d'addition d'entropie selon lequel l'entropie totale des sources indépendantes est égale à la somme des entropies de ces sources. Si nous combinions la séquence principale avec la séquence supplémentaire par concaténation, nous aurions conservé les entropies des sources, mais nous aurions obtenu un mauvais résultat, car dans notre tâche, nous devons évaluer non pas l'entropie totale, mais la spécifique, en termes d'un bit séparé. La concaténation des sources nous donne l'entropie spécifique du résultat égale à la moyenne arithmétique de l'entropie des sources, et la faible séquence additionnelle d'entropie aggrave naturellement le résultat. L'application de l'opération XOR conduit au fait que nous perdons une partie de l'entropie, mais nous sommes garantis que l'entropie résultante n'est pas pire que l'entropie maximale des termes.
- Les cryptographes ont un dogme: utiliser des générateurs de nombres pseudo-aléatoires est une arrogance impardonnable. Parce que ces générateurs ont une petite entropie spécifique. Mais nous venons de découvrir que si tout est bien fait, l'entropie devient un baril de miel qui ne peut être gâché par aucune quantité de goudron.
- Si nous n'avons que 10 octets d'entropie réelle, répartis sur un kilo-octet de données, d'un point de vue formel nous n'avons que 1% d'entropie spécifique, ce qui est très mauvais. Mais si ces 10 octets sont étalés qualitativement, et à part la force brute, il n'y a aucun moyen de calculer ces 10 octets, tout ne semble pas si mal. 10 octets, c'est 2 80 , et si notre force brute par seconde recherche parmi un billion d'options, il nous faudra en moyenne 19 mille ans pour apprendre à deviner le prochain personnage.
Comme mentionné ci-dessus, l'entropie informationnelle est une valeur relative. Lorsque, pour un sujet, l'entropie spécifique est 1, pour un autre, elle peut bien être 0. De plus, celui qui a 1 peut ne pas avoir de moyen de connaître l'état réel des choses. Le système RNG produit pour nous un flux indiscernable de vraiment aléatoire, mais nous ne pouvons qu'espérer qu'il est vraiment aléatoire
pour tout le monde . Et croyez. Si la paranoïa suggère que la qualité du RNG principal peut soudainement être insatisfaisante, il est logique de se couvrir à l'aide d'un autre.
Implémentation d'un sommateur RNG en Python
from random import Random, SystemRandom from random import BPF as _BPF, RECIP_BPF as _RECIP_BPF from functools import reduce as _reduce from operator import xor as _xor class CompoundRandom(SystemRandom): def __new__(cls, *sources): """Positional arguments must be descendants of Random""" if not all(isinstance(src, Random) for src in sources): raise TypeError("all the sources must be descendants of Random") return super().__new__(cls) def __init__(self, *sources): """Positional arguments must be descendants of Random""" self.sources = sources super().__init__() def getrandbits(self, k): """getrandbits(k) -> x. Generates an int with k random bits."""
Exemple d'utilisation:
>>> import random_xe
SystemRandom, qui est considéré comme correct, est considéré comme le flux principal et comme un flux secondaire - le PRNG Random standard. Bien entendu, le point n'est pas grand-chose. Le PRNG standard n'est certainement pas le type de supplément pour lequel il valait la peine de commencer. Au lieu de cela, vous pouvez marier deux RNG systémiques ensemble:
>>> myrandom2 = random_xe.CompoundRandom(SystemRandom(), SystemRandom())
Le sens, la vérité en est encore moins (bien que ce soit pour une raison que Bruce Schneier recommande dans Applied Cryptography pour une raison quelconque), car les calculs ci-dessus ne sont valables que pour des sources indépendantes. Si le RNG du système est compromis, le résultat sera également compromis. En principe, le vol de fantaisie dans la recherche d'une source d'entropie supplémentaire n'est limité par rien (dans notre monde, le désordre est beaucoup plus courant que l'ordre), mais comme solution simple, je proposerai le HashRandom PRSP, également implémenté dans la bibliothèque random_xe.
DSRP basés sur le hachage circulaire en streaming
Dans le cas le plus simple, vous pouvez prendre une quantité relativement faible de données initiales (par exemple, demander à l'utilisateur de jouer sur le clavier), calculer leur hachage, puis ajouter cycliquement le hachage à l'entrée de l'algorithme de hachage et prendre les hachages suivants. Schématiquement, cela peut être représenté comme suit:
La force cryptographique de ce processus repose sur deux hypothèses:
- La tâche de restauration des données d'origine à partir de la valeur de hachage est insupportablement compliquée.
- En utilisant la valeur de hachage, il est impossible de restaurer l'état interne de l'algorithme de hachage.
Après avoir consulté un paranoïaque interne, il a reconnu la deuxième hypothèse comme inutile, et donc, dans la mise en œuvre finale du PRNG, le schéma est légèrement compliqué:
Maintenant, si un attaquant parvient à obtenir une valeur "Hash 1r", il ne pourra pas calculer la valeur "Hash 2r" qui le suit, car il n'a pas de valeur "Hash 2h" qu'il ne peut pas reconnaître sans calculer la fonction de hachage "contre laine". Ainsi, la force cryptographique de ce schéma correspond à la force cryptographique de l'algorithme de hachage utilisé.
Exemple d'utilisation:
>>>
Par défaut, l'algorithme SHA-256 est utilisé. Si vous voulez autre chose, vous pouvez transférer le type d'algorithme de hachage souhaité au constructeur avec le deuxième paramètre. Par exemple, faisons un RNG composite, résumant les éléments suivants dans un tas:
1. RNG systémique (c'est sacré).
2. Entrée utilisateur traitée par l'algorithme SHA3-512.
3. Le temps passé sur cette entrée traitée par SHA-256.
>>> from getpass import getpass >>> from time import perf_counter >>> from hashlib import sha3_512
Conclusions:- Si nous ne sommes pas sûrs de notre générateur de nombres aléatoires, nous pouvons résoudre ce problème facilement et à moindre coût.
- Pour résoudre ce problème, nous ne pouvons pas faire pire. Encore mieux. Et c'est mathématiquement prouvé.
- Il ne faut pas oublier d'essayer de s'assurer que les sources d'entropie utilisées sont indépendantes.
Les sources de la bibliothèque sont sur
GitHub .