Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Répondre
Résumé de la discussion (messages les plus récents en premier)
- thadrien
- 20-03-2012 12:10:07
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.
- Fred
- 20-03-2012 09:53:09
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.
- joutye
- 20-03-2012 01:42:37
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