Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 26-10-2007 22:41:18
- 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.
#2 04-11-2007 21:13:30
- 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+
Hors ligne
#3 07-11-2007 04:37:06
- 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
#4 07-11-2007 04:39:27
- 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.
Pages : 1