Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#1 20-03-2012 01:42:37
- joutye
- Invité
Décrypter des textes en connaissant les xor entre eux
Bonjour,
Disons que j'ai 10 textes, t0..t9, et je connais pour tout i,j, le texte ti xor tj (xor caractère par caractère). Y'a-t-il un algorithme pour trouver tous les textes ti ?
A part du brute-force je vois pas trop...
Merci d'avance
#2 20-03-2012 09:53:09
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 348
Re : Décrypter des textes en connaissant les xor entre eux
Salut,
Ca ne peut pas te permettre de récupérer toute l'information.
Si par exemple tous tes textes sont égaux à 000....000, alors les xor seront aussi 000...000
Si tous les textes sont égaux à 111...111, alors tous les xor seront aussi égaux à 000...000.
Fred.
Hors ligne
#3 20-03-2012 12:10:07
Re : Décrypter des textes en connaissant les xor entre eux
Salut,
Je vais compléter la réponse de Fred :
Si tu fais un xor de tous les messages avec une même clef, alors tu ne changes pas les ti xor tj. Sans autre information, tu ne peux donc pas récupérer le contenu des messages.
Par contre, dans une situation réelle, les messages ne seront jamais quelconques. Si tu connais un bout d'un message, tu peux en déduire tous les bits de même position des autres messages. Par exemple, si un message commence par, disons "%PDF" (je n'invente rien, voir ici : http://www.opensource.apple.com/source/ … agic.mime), tu peux en déduire les 4 premiers caractères de tous les autres messages
Ensuite, si tu trouve des débuts de mots clefs dans les autres messages, tu peux en déduire la suite. Si par exemple, tu vois dans un fichier un "<HTM" , la suite aura de grandes chances d'être "L>" ce qui te donnera "<HTML>". La encore, je n'invente rien.
Dans le cas d'un texte "pur", tu peux souvent déduire la fin d'un mot du début. Ou, du moins, les possibilités sont assez limitées. C'est la technique du mot probable.
C'est d'ailleurs une des raisons pour lesquelles le célèbre programme PGP, puis ensuite tous ses imitateurs, compriment le fichier avant toute autre opération de chiffrement, afin d'éliminer ces redondances. Même si le chiffrement utilisé par PGP est bien plus robuste par ailleurs.
A noter que ce système de xor entre messages est utilisé par un client de P2P peu connu (tellement peu connu que je ne suis plus arrivé à retrouver son nom en cherchant sur Google), mais essentiellement dans un objectif de "camouflage", et surtout pour poser des problèmes juridiques aux ayants droits, que dans un objectif de chiffrement.
A noter également que ton information est redondante ! En effet, les ti xor t(i+1) suffisent pour reconstituer l'ensemble des ti xor tj de proche en proche car, pour tous i < j, ti xort tj = [ti xor t(i+1)] xor [t(i+1) xor t(i+2)] xor ... xor [t(j-1] xor tj].
A noter enfin que tu n'as pas besoin de reconstituer exactement les messages pour en tirer de l'information. Par exemple, le xor de deux images non comprimées est assez visuel. (Plus de détails ici : http://www.apprendre-en-ligne.net/crypt … ndex.html)
Enfin, dans toutes les étapes, il existe des astuces algorithmiques permettant d'accélérer le processus (tables arc en ciel, etc...).
En conclusion, si il n'est pas possible dans tous les cas de reconstituer les messages, on peut néanmoins en faire quelque chose, en particulier dans le cas qui t’intéresse d'un texte simple sans formatage.
Hors ligne