J'ai un tableau d'éléments A . Il est calculé en XORing un autre tableau X avec une valeur constante P suivant cette formule:
A[i] = X[i] xor P
A est connu, X est inconnu et P est inconnu mais constant dans tous les éléments. Est-il possible de trouver P avec seulement ces contraintes?
3 Réponses :
Non, puisque P peut être n'importe quoi. L'opération xor est commutative, distributive et associative, donc les équations suivantes sont équivalentes:
A[i] = X[i] xor P X[i] = A[i] xor P P = A[i] xor X[i] etc...
Tout cela est vrai indépendamment de P si X est inconnu. Bien sûr, vous pouvez calculer P si vous connaissez une paire de A [i] et X [i].
Ouais, je sais que nous ne pouvons pas le calculer directement. Mais, je me demande si nous pouvons utiliser le fait que nous avons plusieurs éléments connus A [i] s avec plusieurs éléments inconnus X [i] s XORed avec la même constante valeur P .
Comme l'a indiqué l'autre réponse, à moins que vous n'ayez d'autres connaissances sur A ou X.
Si vous avez un a priori probabiliste sur le tableau d'origine, vous pouvez trouver le P le plus probable qui a été utilisé. Il suffit de xor le tableau donné avec tous les P possibles, et de trouver celui qui maximise Prob (A).
Par exemple, si vous savez que le tableau d'origine était quelque chose comme du texte anglais, alors vous pourriez juger "HELLO" comme étant plus probable que "IDMMN" puisque HELLO est un mot, mais IDMMN ne l'est pas.
Si vous n'avez aucun moyen de juger quels tableaux d'entrée étaient plus ou moins probables les uns que les autres, alors vous êtes bloqué, puisque chaque P possible est également probable.
Ouais, j'ai des mesures probabilistes sur les tableaux d'entrée. Merci pour ces conseils.
Un exemple simple où vous ne trouvez pas P est
X = [ 0, 1, 1] P = 1 => A = [ 1, 0, 0 ] X = [ 2, 3, 3] P = 3 => A = [ 1, 0, 0 ]
(Je pense que la réponse est triviale - et la question utile. Pensez aux réponses dé-spoiling (
>!).)en.wikipedia.org/wiki/XOR_cipher