Forum de mathématiques - Bibm@th.net

Arhentest

Invité

Propriétés conservatrice de l'aléatoire

Salutations,

Je souhaiterais être éclairé sur un point préci concernant le caractères aléatoire de nombres, en vue d'une application cryptographique.

Le fait d'effectuer l'opération XOR sur cinq nombres binaires de même taille (l'un après l'autre) conserve t-il le caractère aléatoire du plus aléatoire de ces nombres, si aucun ne possèdent de lien entre eux ?

Dit autrement, est ce que le caractère non aléatoire d'un ou de plusieurs de ces nombres risque d'affectuer la qualité aléatoire du nombre de sortie ? Est ce que le nombre de sorti peut posséder un caractère aléatoire plus faible (autrement que "par hasard" bien sûr) que le plus fort des nombres d'entrées ?

Si les nombres ont des lien entre eux, la réponse est bien sûr évidente. Mais dans le cas où ils sont tous indépendants, intuitivement je serais tenté de dire non... mais mes connaissances sur le sujet sont relativement faibles.

Quelqu'un aurait-il une idée de réponse ?

Arhentest.

john

Membre actif

Inscription : 10-02-2007

Messages : 543

Re : Propriétés conservatrice de l'aléatoire

Salut,
La crypto. n'est pas ma tasse de thé mais je viens de découvrir ton message resté sans réponse alors je me lance...
Il me semble qu'une table de vérité du XOR suffit pour montrer que le caractère aléatoire est conservé.
Exemple avec E1 et E2 à 2 digits.
La sortie S du XOR a aussi 2 digits qui prennent les valeurs 11 01 00 et 10 sans qu'aucune d'elles ne soit privilégiée. Si c'est vrai pour 2 digits, on doit pouvoir montrer simplement que c'est également vrai pour n. SI c'est vrai pour 2 nombres aléatoires en entrée, c'est vrai aussi pour m.
A+

Barbichu

Invité

Re : Propriétés conservatrice de l'aléatoire

Hello,

Soient X et Y deux variables aléatoires :
[tex]X,Y : \Omega \to \{0,\ldots,2^{n-1}\}[/tex]

Etudions la loi de [tex]X \oplus Y[/tex] :

[tex]\forall k \in \{0,\ldots,2^{n-1}\} , P(X\oplus Y = k) = P(\bigsqcup_{i=0}^{2^{n-1}} (X=i)\cap(Y=i\oplus k))[/tex] (réunion disjointe)
       [tex]= \sum_{i=0}^{2^{n-1}} P((X=i)\cap(Y=i\oplus k))[/tex]

Puis s'il on suppose les variables aléatoires X et Y indépendantes, on a :
[tex]\forall k \in \{0,\ldots,2^{n-1}\} , P(X\oplus Y = k) = \sum_{i=0}^{2^{n-1}} P(X=i)P(Y=i\oplus k)[/tex]

Puis si X (par ex) suis une loi uniforme ([tex]\forall k \in \{0,\ldots,2^{n-1}\} , P(X=k)=\frac{1}{2^n}[/tex])
Alors [tex]\forall k \in \{0,\ldots,2^{n-1}\}, P(X\oplus Y = k) = \sum_{i=0}^{2^{n-1}} \frac{1}{2^n} P(Y=i\oplus k)[/tex]
      [tex]= \frac{1}{2^n} \sum_{i=0}^{2^{n-1}} P(Y=i\oplus k)[/tex]
      [tex]= \frac{1}{2^n} \sum_{i=0}^{2^{n-1}} P(Y=i)[/tex]
      [tex]= \frac{1}{2^n} \cdot 1[/tex]

Et  [tex]X \oplus Y[/tex] suis donc une loi uniforme, quelque soit la loi de Y.

Cela répond donc à ta question dans le cas particulier ou "plus aléatoire" signifie "de loi uniforme".
L'aléatoire se mesure (en général) en terme d'entropie : http://fr.wikipedia.org/wiki/Entropie_de_Shannon (le cas le plus aléatoire correspondant à l'entropie maximum, i.e. à la loi uniforme). ll y a peut-être moyen de trouver une minoration de l'entropie de [tex]X \oplus Y[/tex] en fonction de celles de X et Y.

bye

Barbichu

Invité

Re : Propriétés conservatrice de l'aléatoire

PS: Il faut lire [tex]2^n - 1[/tex] et non [tex]2^{n - 1}[/tex] dans le post précédent.