Cryptanalyse de HashMask

Usenet (fr.misc.cryptologie) a proposé à nouveau un nouvel algorithme de chiffrement, issu du même auteur que précédemment. L'algorithme étudié s'appuye largement sur le chiffre de Vernam. Il est aussi inutilisable en pratique que Vernam, la faiblesse en plus, car il ne faut pas réutiliser la clé.

09/05/2012 à 00:29:56 - 7 commentaires

Le chiffre de Vernam est démontré incassable, mais difficilement utilisable en pratique car il faut, entre autres, ne pas réutiliser la clé. L'algorithme HashMask est équivalent à un Vernam affaibli, où il ne faut pas réutiliser la clé mais qui est bien plus courte.

Analyse

La clé sert de générateur à une suite périodique et pseudo-aléatoire constituant le masque. Le masque est ensuite appliqué via un ou-exclusif.

chiffré = clair XOR masque(clé)

Comme nous le verrons plus bas, le masque est plutôt robuste. C'est sûrement très difficile d'entrer par cette porte blindée. Alors on entre par la fenêtre. À une clé donnée correspond un masque et un seul. Si on chiffre deux messages avec cette clé, nous obtenons ceci :

C1 = m1 XOR masque
C2 = m2 XOR masque

C'est la faiblesse fatale typique du Vernam, le masque jetable, dont il ne faut pas réutiliser la clé sous peine d'être vulnérable à l'attaque par mot probable. Pas la peine de chercher la clé, puisqu'il suffit d'extraire le masque. Cet algorithme est inutilisable en pratique, puisqu'il faut refaire une clé à chaque fois.

Cependant, poursuivons l'étude du masque. Le vrai chiffrement invulnérable, Vernam, est contraignant du fait de la taille de la clé, qui doit être au moins égale à celle du clair. Est-il possible de sacrifier un peu la sécurité au profit de plus de fonctionnalité, c'est-à-dire avec un simple mot de passe à transmettre ?

Dans la suite, nous supposerons que le mot de passe n'est pas vulnérable à une attaque par force brute.

Le masque

L'algorithme opère un ou-exclusif entre le clair et le masque. Chaque bit du masque est extrait du flot du masque. Il s'agit d'un chiffrement par flot.

Description

Le flot est composé de segments de 256 bits, générés au moyen de l'algorithme suivant :

SI vide(segment) ALORS segment = hash(clé)
segment = hash(segment+clé) // concaténation, "a"+"b"="ab"
ENVOI segment

Qui fournit les sorties suivantes, toutes de 256 bits :
1: hash(hash(clé)+clé)
2: hash(hash(hash(clé)+clé)+clé)
3: hash(hash(hash(hash(clé)+clé)+clé)+clé)
4: (...)

Ne pas utiliser hash(clé) comme premier segment généré permet de ne pas être vulnérable à une attaque par dictionnaire. La fonction de hachage (à sens unique) est SHA-256. La salage avec la clé empêche l'utilisation de tables arc-en-ciel. Cela correspond au mode d'opération Output Feedback, hash(clé) étant le vecteur d'initialisation.

Dès lors que le flot rencontre à nouveau le même segment, on a trouvé un cycle puisque chaque segment est toujours fonction du segment précédent, à clé fixée. Comme il y a un nombre limité de segments possibles (2^256 =~ 10^77), on tombe forcément sur un cycle. Un masque est donc composé d'une séquence de segment suivie d'un cycle de séquence de segment. Compte tenu de la méthode utilisée, je conjecture que la longueur des cycles est très grande et très probablement toujours plus grande que le clair. Si ce n'était pas suffisant, on pourrait utiliser d'autres algorithme de hachage tels que SHA-512...

Cela veut dire qu'en pratique, on extrait une suite imprévisible, qui pourrait faire l'affaire en tant que masque jetable mais seulement parmi un sous-ensemble des masques possibles, déterminés par l'espace des clés. Évidemment, il n'y a pas toutes les possibilités de masque comme pour le Vernam, et c'est pour ça que cet algorithme n'est pas inconditionnellement invulnérable, même si on n'utilise qu'une seule fois la clé. À supposer que la suite pseudo-aléatoire est robuste, et que la clé est choisie judicieusement, la sécurité semble intéressante. Une attaque classique nécessiterait un clair grand par rapport à un masque doté d'une période hypothétiquement très grande.

Attaques sur le masque

En fait, l'implémentation de référence stocke le nom de fichier à la fin du chiffré. Cela ouvre l'accès aux derniers bits du masque, ce mot probable permet de débuter la cryptanalyse. Cela a pour but, visiblement, de transmettre un fichier au nom générique, le vrai nom de fichier n'étant connu que lors du déchiffrement. On ignorera cette faille de sécurité car la fonctionnalité qu'elle apporterait est faible par rapport au risque pris.

Lors d'un chiffrement à clair connu, on retrouve facilement les segments. la connaissance d'un segment permet de caractériser très probablement la clé et de deviner si deux chiffrés utilisent la même clé. La connaissance de deux segments (consécutifs serait le mieux) ouvre une attaque par force brute sur la clé car l'un est toujours fonction de l'autre et de la clé. La connaissance de tous les segments utilisées pour un chiffré donné ne permet pas de déduire les segments suivants, du fait du salage avec la clé.

La période du masque est la plus courte distance entre deux segments identiques. La connaître est équivalent à connaître la clé. Et réciproquement.

Cryptanalyse

Problème posé

Soient C1, C2, C3 les trois chiffrés d'un clair c avec les clés k1, k2, et k3. De même, soient D1, D2, D3 les trois chiffrés d'un clair d avec les clés k1, k2 et k3. On sait que le texte de c est inclus dans d. Le texte original du problème est ici.

Étant connus c, C1, C2, C3, D1, D2, D3, trouver d. On ne connaît pas les clés k1, k2 et k3.

Preuve formelle de la résolution

On suppose que tous les fichiers font la même taille, et on a :

C1 = H(k1,c) et C2 = H(k2,c) et C3 = H(k3,c) avec H notre fonction de chiffrement.
D1 = H(k1,d) et D2 = H(k2,d) et D3 = H(k3,d)

On a vu précédemment qu'en général : X = H(clé,Y) = Y ⊕ masque(clé)

Avec M1, M2 et M3 les masques correspondants aux clés k1, k2 et k3 :

C1 = c ⊕ M1 et C2 = c ⊕ M2 et C3 = c ⊕ M3
D1 = d ⊕ M1 et D2 = d ⊕ M2 et D3 = d ⊕ M3.

Il vient que :
d = D1 ⊕ M1 ainsi que M1 = C1 ⊕ c
d = D2 ⊕ M2 ainsi que M2 = C2 ⊕ c
d = D3 ⊕ M3 ainsi que M3 = C3 ⊕ c

Et donc :
d = D1 ⊕ C1 ⊕ c
d = D2 ⊕ C2 ⊕ c
d = D3 ⊕ C3 ⊕ c

C1, C2, C3, D1, D2, D3 et c étant connus, on dispose de trois façons de retrouver le clair d.

Cette méthode ne peut pas décrypter au-delà de la longueur du clair c connu. Les informations concernant le clair d, situées au-delà de la longueur de c sont inaccessibles parce qu'on ne sait pas calculer le masque au-delà du clair.

Question ouvertes

Cet algorithme n'a rien inventé, RC4 est basé sur un principe similaire. Il a été cassé, mais en contexte de réutilisation de la clé.

Quelle est en moyenne la longueur du masque ?

Peut-on prédire les segments suivants à partir d'un segment connu ? De deux ? De trois ? etc.

Peut-on retrouver la clé à partir d'un segment ? De deux ? etc.

Quelle est la probabilité que deux clés soient dépendantes ? C'est-à-dire que l'une génère une séquence incluse dans l'autre.

Encore une fois, merci à Dimitri MESTDAGH, le développeur de l'implémentation de référence et à Philippe LHEUREUX, le concepteur de l'algorithme.

Cryptanalyse de l'algorithme CENAv03

Le forum Usenet francophone de cryptographie a proposé un système de chiffrement à casser, avec une implémentation fournie. j'ai cryptanalysé cet algorithme au moyen d'une attaque à clair choisi. Si vous cherchez la révolution de techniques de cryptanalyse actuelles, ce n'est pas ici qu'il faut regarder. En revanche, si le savoir-faire d'il y a plus de 50 ans vous intrigue, cet article peut faire figure de ravissante introduction...

22/04/2012 à 23:46:21 - 3 commentaires

J'ai cassé l'algorithme CENA en m'aidant de l'implémentation de référence. Le langage de programmation utilisé est Php. le code source en licence libre GPLv3+ est téléchargeable ici.

Je me suis contenté d'attaquer assez souvent un seul caractère. La technique est donc basique ici.

Dans la suite, il ne sera jamais question d'octet, mais toujours de caractère. Et pour conserver une relative simplicité, il sera fait mention de lettres clair et de lettres chiffrées. On ne considère que les lettres de l'alphabet. L'implémentation n'utilise jamais de dispositif aléatoire, mais simplement pseudo-aléatoire, mais cela n'a pas de conséquence pour la suite.

Descriptif de l'algorithme de chiffrement

Chaque caractère est chiffré isolément en fonction d'une clé. La variante de chiffrement de chaque caractère est entièrement déterminé par sa position dans le clair. Chaque caractère clair aboutit à 17 caractères (de '0' à '9') chiffrés. Voici la succession de traitement que subit une lettre :

Vigenère fixé

Le caractère subit d'abord l'algorithme de Vigenère utilisant une clé fixée une fois pour toute. Le caractère de rang 0 (première position) n'est pas modifié, le deuxième est décalé de 1, le troisième de deux, etc.

Expansion

À chaque caractère, on associe un nombre de 6 chiffres pris dans un intervalle déterminé dans la clé. Tous les nombres de l'intervalle ramènent au même clair. Par exemple, A est transformé en un nombre entre 305126 et 308475. L'intervalle est fonction de la clé, et reste fixe pendant le chiffrement.
Le chiffré est passé de 1 caractères à 6 caractères.

Brouillage

Les 6 chiffres précédents sont mélangés dans 11 chiffres aléatoires. L'implémentation utilise une phase ajoutant 10 chiffres et une phase ajoutant 1 chiffre. Cela donne l'illusion que ça ajoute de la complexité parce que la clé est plus difficile à générer et à utiliser, mais en fait c'est tout à fait inutile. Le chiffré est passé maintenant de 6 caractères à 17 caractères.

Analyse de l'algorithme

Il est a clé de taille fixe, déterminer la longueur de la clé est donc utile. En fait, il suffirait de tester les longueurs de clé de 32 à 64 caractères, ce qui donne 33 possibilités. En fait, on peut faire plus simple !

L'algorithme chiffre caractère par caractère, on peut donc ne se focaliser que sur le premier caractère. Cette approche permet de s'affranchir du Vigenère fixé, car le Vigenère au rang zéro (première position) retourne exactement le caractère en entrée. Donc le Vigenère peut être ignoré.

L'expansion est le point faible de l'algorithme. Par construction, pour une position donnée (mais nous restons toujours au premier caractère) l'ensemble des valeurs attribuables à un caractère commence toujours par les mêmes deux premiers chiffres, le troisième variant assez peu. En reprenant l'exemple de la lettre 'A', les nombres qui lui sont associés vont de 305126 à 308475. Les trois premiers chiffres sont donc 305, 306, 307 et 308.

Le brouillage ajoute 7 chiffres aléatoires. C'est la partie la plus utile de l'algorithme et noye l'information dans un brouillard aléatoire.

Cryptanalyse

Sans connaître l'algorithme, on analyse les rapports clairs/chiffrés. On constate que la taille des chiffrés est toujours égale à 17 fois celle du clair. En ne chiffrant qu'un seul caractère de façon répétitive, on s'aperçoit vite que 2 des dix-sept caractères ne varient pas, certains variant un peu plus et d'autres sont quasiment aléatoires. En chiffrant deux caractères identiques, on s'aperçoit que les chiffres non-aléatoires restent les mêmes mais que leur position à changé. À cette étape, on sait déjà que (à une clé donnée) la substitution ne dépend que du caractère et que la transposition ne dépend que de la position du caractère. La cryptanalyse ici consiste à retrouver une clé en soumettant à volonté des clairs. En fait, la vraie clé n'est retrouvée mais seulement une clé inverse. En poussant plus loin l'analyse, il serait possible de créer une clé et de chiffrer des messages.

Rangs utiles

Première étape, on détermine les rangs utiles. À une position donnée correspond une répartition donnée des caractères expansés. Par exemple, les rangs 11, 16 et 1 portent de l'information pour le première caractère chiffré. Les rangs 7, 1 et 13 correspondent au deuxième caractère chiffré. Je demande de très nombreuses fois le chiffrement de certains caractères, un à la fois. Cela fournit le spectre associé à la position : pour chaque rang (de 0 à 16) on détermine la probabilité d'occurrence des chiffres. Dans la pratique, on ne conserve que les 3 meilleurs rangs. Dans un caractère chiffré, on est donc capable de connaître les bons caractères parmis les 17.

Dictionnaire

Deuxième étape, on demande un grand nombre de fois le chiffrement de tous les caractères, toujours un à la fois. Les 17 chiffres sont filtrés grâce aux rangs utiles collectés à la première étape, dans la pratique, 3. Grâce au grand nombre d'essais, j'en arrive à déterminer toutes les combinaisons possibles de 3 chiffres. Concrètement, cela revient à déterminer les trois premiers chiffres correspondant à chaque lettre. Par exemple l'expansion de la lettre 'A' est l'ensemble des nombres entre 305126 et 308475 inclus. Le "3" et le "0" apparaissent toujours à la même position dans les chiffrés tandis qu'une position ne contient que "5,"6","7" ou "8". Ce faisant, on récolte pour chaque lettre en clair ces trois nombres caractérisant son expansion. En fait, il existe des cas où il y a ambiguïté. Ces cas ouvrent la voie à l'analyse fréquentielle pour les éliminer, mais qui ne sera pas traitée ici.

Clé inverse

Troisième étape, calcul de la clé inverse. Elle porte toujours sur un seul et premier caractère, ce qui élimine le vigenère du début. En combinant les deux étapes précédentes, on détermine quels 3 chiffres on doit lire parmi les 17 et quelle est la (parfois les) lettre en clair liée à ces 3 chiffres.

Le déchiffrement au moyen de la clé inverse se déroule comme suit :

• On ne conserve que les trois chiffres utiles.
• On regarde à quel caractère correspond ces trois chiffres utiles.

Comment améliorer la cryptanalyse ?

Elle ne porte que sur un caractère, ce qui oblige à faire des milliers de requêtes de chiffrement de un caractère. On peut chiffrer un seul gros fichier contenant toutes les lettres par paquets de quelques milliers. Le débrouillage est réalisé en testant les 33 hypothèses de longueur de la clé. Avec la bonne longueur du clé, la prééminence des 3 chiffres apparaît.

L'analyse fréquentielle peut, sous réserve d'avoir un clair et un chiffré de longueur suffisante, lever les dernières ambiguïtés et permettre de reconstituer la clé d'origine.

Et la longueur de la clé ?

La phase de cryptanalyse n'a pas vraiment besoin de la longueur de la clé. En fait, il faut la déterminer seulement s'il faudra déchiffrer des messages de longueur supérieure et pour généraliser le déchiffrement. La longueur de la clé est tout de même calculée pendant la cryptanalyse. Pendant le débrouillage, on reboucle sur la clé lorsqu'on retrouve les mêmes positions caractéristiques.

Comment améliorer l'algorithme ?

Injection de l'intru : la phase d'injection de l'intru est inutile car elle est équivalente à rajouter un caractère de brouillage. À supprimer.

Brouillage : le brouillage lui-même peut être contourné par une analyse fréquentielle. En effet, le brouillage est aléatoire, contrairement aux informations entrées en clair.

Expansion : elle a grandement permis de casser l'algorithme. En fait, on peut l'améliorer comme suit. L'algorithme partitionne un intervalle de nombres en associant à chaque intervalle une lettre. Par exemple, si on sait que 305126 et 308475 désigne la lettre 'A', alors on sait que tous les nombres entre les deux désignent aussi 'A'.
Pour faire mieux, on pourrait associer à chaque nombre de l'intervalle une lettre de sorte à ce que chaque lettre soit associée à la même quantité de nombre, mais qu'il n'est pas possible de prévoir à quelle lettre est associée un nombre. Par contre, il faudra utiliser une clé de 899999 caractères pour l'expansion... Cela éviterait de pouvoir extraire les 3 chiffres caractéristiques d'une lettre.

Comment faire mieux que l'algorithme ?

Utiliser un vigenère a clé fixée n'est d'aucune utilité et n'a pas freiné la cryptanalyse, autant l'abandonner. Le brouillage ralentit la cryptanalyse, mais n'est pas efficace, donc autant l'abandonner aussi. L'expansion est une fausse bonne idée, et il serait plus efficace de faire un simple vigenère. Par exemple, on pourrait générer une clé infinie au moyen d'un tirage aléatoire provenant d'une suite déterminée par la clé. Par exemple, fixer le sel de la clé (srand() en Php) permet de faire autant de tirages pseudo-aléatoires que voulu... Évidemment, mais si c'est plus efficace, cela reste faible.

En gros, il serait plus efficace de faire du Vigenère au moyen d'une clé pseudo-aléatoire. Mais même comme ça, ce n'est pas gagné contre les techniques d'aujourd'hui.

Merci à Dimitri MESTDAGH, le développeur de l'implémentation de référence et à Philippe LHEUREUX, le concepteur de l'algorithme.

Références

• Algorithme, http://dimooz.free.fr/void/cena/principe.php
• Implémentation de référence, http://dimooz.free.fr/void/cena/index.php
• fr.wikipedia.org/wiki/Cryptanalyse
• fr.wikipedia.org/wiki/Chiffre_de_Vigenère

L'archive contenant les codes sources est disponible ici.

Plena Ilustrita Vortaro de Esperanto, serĉilo

La Plena Ilustrita Vortaro de Esperanto (PIV) rete uzeblas, serĉile.

10/04/2012 à 20:38:23 - 1 commentaire

Jen teksto de la retejo:

la reta versio de unu el la plej famaj E-verkoj de lastaj jardekoj "Plena Ilustrita Vortaro de Esperanto" (PIV). Jam multajn jarojn PIV estas la plej ampleksa difin-vortaro en Esperanto, kiu unuan fojon aperis en la jaro 1970. Al la enhavo de la vortaro kontribuis multaj personoj. La liston de tiuj personoj vi povas trovi ĉe tiu ĉi paĝo.
Ekde aprilo 2012 PIV estas uzebla ankaŭ en la reto.

http://vortaro.net/

Pro faciligi la serĉadon, mi faris serĉilon por Firefox, vortaro.net.xml

Scolnet: éducation à la délation nationale

Les écoles reçoivent des courriels les invitant à créer un espace numérique pour leur écoles. Ils pourront partager des fichiers, photos et y planifier la vie de leur établissement. Il est aussi possible aux enseignants, parents et enfants de s'y inscrire. Scolnet est un réseau social.

18/03/2012 à 09:57:00 - Aucun commentaire

Faits

Chaque site web possède son modèle économique, qui se résume à combien je gagne d'argent par rapport à ce que je dépense pour le site. Par exemple, mon site est 100% déficitaire sur ce point. Mais il me sert à publier des articles et partager des fichiers, un service que je paye. Scolnet ne renseigne pas sur son modèle économique, mais insiste sur la gratuité. Gratuit, mais pas sans contrepartie. Facebook à ses débuts était similaire, avant de vendre la vie privée de ses "clients". Lorsque vous ne payez pas pour un service, c'est que vous n'êtes pas le client, mais le produit.

Les espace numériques sont cloisonnées école par école. Elles sont toutes connues du site, qui les propose à la création d'un espace. Le chef d'établissement doit se déclarer comme tel. Ensuite suivent les enseignants, les parents d'élèves, les parents, les élèves. Toute la hiérarchie est connue de Scolnet. Les messages échangés entre chacun compléteront les renseignements offerts au site. Scolnet exige que chacun contribue sous son prénom et nom, chacun validera donc implicitement l'identité des autres.

Avis

Ce site veut suivre le même chemin que Facebook, mais en forçant une clientèle captive piégée, involontairement ou non, par les chefs d'établissement. De proche en proche, chacun dénoncera ses voisins (identités, relations, enfants, etc.) jusqu'à ce que le site

• ajoute de la publicité,
• partage vos informations avec ses "partenaires" (déjà Google et Facebook),
• se lie avec les fichiers Base Élèves, Affelnet, et... Sconet !

Si vous l'utilisez de votre propre chef, vos échanges contribueront à dénoncer indirectement ceux qui ne souhaitent pas y figurer. Des informations concernant les objecteurs (et leurs familles) pourront être déduites de vos échanges. Facebook en est déjà à ce stade.
Lisez toutes les informations concernant Facebook et la vie privée : elles sont ou seront valables pour Scolnet.

Voici l'avis rendu par la circonscription de La Flèche :
Votre école a peut-être reçu un courriel publicitaire sur l'ouverture du site scolnet, premier réseau social scolaire qui permet à l'équipe enseignante de communiquer et de partager du contenu numérique avec parents et élèves....
Le caractère publicitaire de ce produit, n'a fait l'objet d'aucune validation académique.
Il est précisé, de plus, qu'en l'absence de garantie sur la destination et les conditions d'hébergement des données, pour certaines sensibles, qui y seront traitées, l'utilisation d'un tel produit est fortement déconseillée.

Technique

En France

Le nom de domaine scolnet.fr ainsi que le serveur sont tous les deux hébergés en France, à Roubaix. L'hébergeur est OVH, un hébergeur grand public français.

Une recherche whois indique que le domaine est géré par OVH, un grand hébergeur français. L'hébergement est un Kimsufi (www.kimsufi.com). Une requête sur le nom de domaine scolnet.fr (centralops.net/co/NsLookup.aspx) indique que l'hébergement est aussi assuré par OVH. L'adresse IP est 87.98.156.150. Une requête inverse sur l'adresse IP du serveur confirme que l'hébergement est chez OVH. Un traceroute, vers le domaine, confirme OVH comme hébergeur. La connexion réseau reste en France.

Google & Facebook

Le site partage ses statistiques de fréquentation avec Google. Il est également connecté au réseau social Facebook en ce qui concerne la gestion des comptes utilisateurs.

Les pages comportent le traceur de Google. Le site permet de se connecter avec Facebook mais aucune interaction avec Facebook ne se trouve côté client. L'intégration est faite côté serveur, silencieusement.

Identité réelle

Dans son règlement, le site exige de ses utilisateurs (n'importe qui peut s'inscrire) qu'il fournisse ses vrais noms et prénoms.

Il faut :

• donner sa vraie identité,
  
• il faut envoyer un courriel pour supprimer un compte,
  
• accepter la modification du règlement à tout moment, sans avertissement.
  

Par contre, les directeurs d'écoles sont des utilisateurs particuliers puisque le site a recensé les écoles de France et qu'il faut s'affilier à une école. Le site fait la différence entre chef d'établissement, enseignant, parent d'élève, parent, élève.

Sans contrôle

Le site se présente comme indépendant. Scolnet.fr est un site indépendant créé en 2011, peut-on lire dans la page À propos.

Donc sans liaison ni contrôle par le Ministère de l'Éducation Nationale.

Règlement précaire

Le réseau social Scolnet se réserve le droit de changer à tout moment, sans préavis, les conditions d'utilisation. Il faut envoyer un courriel pour supprimer un compte. La suppression des données n'est pas immédiate. Le site affirme être déclaré à la CNIL, mais ne délivre pas de numéro d'agrément. Il se réservent le droit de diffuser des données agrégées. Aucune possibilité d'exporter ses données.

Confidentialité :

• pas de numéro de déclaration à la CNIL
• ils diffusent des données agrégées (pour de la pub ciblée ?)
• pas de précision sur la propriété des données postées

Aucune précision n'est apportée sur la propriété des données...

Piège du stockage

Le site n'offre que 50Mo de stockage, probablement un piège pour proposer ensuite des forfaits payants.

Il est classique de fournir un service qui semble convenable au début, et gratuitement, pour imposer ensuite ses conditions à qui se rendrait compte qu'au début ce n'était pas assez. On peut imaginer que ce serait assez dramatique pour une école et tous ceux qui gravitent autour.

Pas de HTTPS

Les pages utilisent HTTP et pas HTTPS et la confidentialité qu'il apporte.

Les identifiants et mots de passe circulent en clair entre le navigateur et le site web.

En résumé...

Scolnet est un réseau social avec les mêmes motivations que Facebook. Il ne dispose d'aucun financement (par ses utilisateurs) pour ses activités, il va donc vivre de la publicité et de vos données personnelles. Par ailleurs, mais je ne suis pas juriste, si l'éducation nationale pourrait être poursuivie au civil si l'un de ses agents entrait dans la délation, les directeurs d'établissement seraient personnellement et pénalement responsables puisque ce réseau social repose sur leur participation active.

Permutation sans variable intermédiaire

Soient 3 variables a, b, c. Pour réaliser une permutation circulaire sans variable intermédiaire, on fait ceci : a = - a - b - c ; b = - a - b - c ; c = - a - b - c ; a = - a - b - c.

09/10/2011 à 21:32:21 - Aucun commentaire

Dans de nombreux environnements, on ne dispose pas toujours de variables intermédiaires. Il est donc nécessaire de recourir à des subterfuges.

Avec une variable intermédiaire

Soient deux variables a et b qu'il faut permuter. L'opération est classique si on dispose d'une variable intermédiaire X :

En déroulant l'exécution à la main, cela donne :

action	a	b	X
initialisation	4	7
X = a	4	7	4
a = b	7	7	4
b = X	7	4	4

Ce qui requiert 3 étapes.

Sans variable intermédiaire

Il y a un problème avec

qui ne marche pas car la valeur de b est simplement copiée dans a.
Alors, peut faire ceci :

Ça marche, mais il y a deux formules différentes : a + b et a - b.
On peut faire plus simple :

Ce qui donne l'exécution suivante :

action	a	b
initialisation	4	7
a = - a - b	-11	7
a = - a - b	-11	4
a = - a - b	7	4

Il y a le même nombre d'opérations que précédemment, mais l'action est identique pour tous.

Généralisation

Aux entiers

La permutation circulaire se généralise avec un nombre arbitraire de variables. Soit x1, x2, ..., xn les variables sur lesquelles on veut effectuer une permutation circulaire. Pour mettre la valeur de x1 and x2, x2 dans x3, ..., xn dans x1, on applique l'algorithme suivant :

L'algorithme exploite le fait que le calcul se répète à l'identique pour tous.

Aux booléens

Le symbole ⊻ (XOR) a la même principe que le ∑ car l'opérateur ⊻ possède les propriétés d'associativité et de commutativité.

Le fait qu'en informatique les booléens sont utilisés pour stocker les données permet de généraliser la permutation à n'importe quel type de données.