Christophe HENRY

Ce site ne comporte aucune information d’intérêt, sauf pour celui qui la cherche — Ĉi-retejo ne enhavas informon interesan, krom por iu kiu ĝin serĉas — This website doesn’t have any information of interest, except for who looks for it

Un cookie n'est ni un fichier, ni un programme !

20/12/2013 - Aucun commentaire

Les cookies ne sont pas des fichiers, ni des programmes. Ce sont des données placées par les sites web, qui peuvent se matérialiser sous la forme de fichiers, mais pas seulement. C'est une des choses qui rendent la navigation distinguable d'une autre lorsqu'on est connecté. Internet Explorer stocke un cookie par fichier, mais Firefox les stocke dans une seule base de données nommée cookies.sqlite. Les cookies de session eux, ne sont conservés qu'en mémoire il me semble. Nous sommes bien loin du fichier.

Concernant les cookies revenant après leur suppression, c'est principalement dû à Flash. Il utilise son propre lieu de stockage de données locales. Les publicitaires ont donc mis au point une application Flash, invisible, dont le seul travail consiste à télécharger les données déjà connues et reconstituer les cookies correspondants. C'est d'ailleurs le principal intérêt du "rich media" que de fournir un moyen de contourner la volonté de l'utilisateur en s'écartant des normes habituelles des pages web telles HTTP ou Javascript.

La politique demandant à l'utilisateur s'il souhaite autoriser les cookies est une absurdité. Si l'utilisateur refuse, comment ce choix est-il retenu ? Avec un cookie ? En cas de refus, il faudra lui poser la question à chaque fois ? Quand c'est un message surgissant, c'est systématiquement dérangeant. Quand c'est relativement discret dans la page, l'utilisateur risque de passer à côté. De fait, bloquer les cookies n'est pas la garantie que le site ne trace pas. Il reste possible de personnaliser la page web servie au visiteur pour y inclure un identifiant. Bien sûr, c'est moins efficace que les cookies puisque cet identifiant disparaît à la fermeture de l'application. Il existe aussi d'autres techniques plus délicates pour tracer les gens, comme le décrit Evercookie.

Que faire ?


Installer Flashblock sous Firefox pour interdire Flash par défaut, exiger qu'on clique pour exécuter ces programmes. À ma connaissance, sauf Youtube et autres, il n'est presque jamais nécessaire d'autoriser Flash a s'exécuter systématiquement. On devrait aussi installer une extension comme Self destructing cookies qui permet de détruire les données locale dès qu'on quitte le site les utilisant.

Il y a bien d'autres choses encore à faire.

Tags de l'article :

"Journalistes"

21/02/2013 - Aucun commentaire

Au cours d'une manifestation d'agriculteurs, deux journalistes ont été pris à parti par des manifestants. Leur caméra a été détruite. Faut-il s'étonner que les journalistes ne soient pas les bienvenus ? Source, http://www.arretsurimages.net/contenu.php?id=5633 (payant).

Sans préjudice sur le pourquoi du comment, et même à supposer que des méchants manifestants ont tapé sur les gentils journalistes, cette histoire ne m'étonne pas. Depuis des années, des abrutis de "journalistes" arrivent avec leurs idées préconçues et la conclusion de leur article, commandé, déjà en tête. Alors quand ont les voit débarquer, ce n'est guère étonnant de voir le résultat. Si ça pouvait apprendre leur métier à cette profession largement orientée, ce serait super. Et sinon, il faut recommencer à repousser la désinformation. Encore.

Il a des exceptions. Par exemple ArrêtSurImage, MediaPart et le Canard enchaîné, pour citer les principaux. Sans publicité, il me semble, et (donc) sans donneur d'ordre. Les autres, financés aussi par la publicité, s'accrochent à nos impôts pour subsister. Qu'il crêvent. Et que leurs salariés retournent à l'école. Et que Google les dé-référence, mais bon, ils ont trouvé le moyen d'arnaquer l'État français, consentant, et ses "journalistes" sur commande pour recevoir un peu de lumière depuis Internet.

Je propose donc qu'ArrêtSurImage dépêche une équipe sur place pour voir comment ça se passe. Ce n'est pas son objectif, je sais, mais ce serait instructif.

Tags de l'article :

Cryptanalyse de l'algorithme CENAv03

22/04/2012 - 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

descriptif
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

énigma
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

descriptif

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 ?

descriptif
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



Le code source est disponible ici.

Tags de l'article :

Plena Ilustrita Vortaro de Esperanto, serĉilo

10/04/2012 - Commentaires fermés

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

Tags de l'article :

For how many states, there's more than one Googolplex of turing machines?

27/09/2011 - Commentaires fermés

This is a great way to enter the world of great numbers, with a bit of theory and practical sort of innovation...

Main terms

What is a Turing Machine?

A Turing Machine is a very simple computer which was designed by Alain Turing in 1936. A Turing Machine is described by states, each states pointing to other states according to some conditions. You may read a bit more about Turing machines in order to fell all the taste of this article.

What are Googol and Googolplex ?

A Googol is a number represented by 1 followed by 100 zeroes. That is, 10^100. A Googolplex is 10 power Googol - that is, a number represented by 1 followed by a Googol of zeroes : 10^(10^100). Somewhat huge.

What is the Log function ?

The Log function approximatively gives the number of digits of a number. It's the reciprocal function of y = 10^x. So, x = Log(y). This function is important here because of one of its main properties. It turns multiplications into additions. So, the calculations will involve far less huge numbers.

So what?

A resolution

The question is: how many states do I need to be able to build one Googolplex Turing Machines? Winter's cold, brain's hot.

The Turing Machine considered here is the more simple one: two different values and two different directions. Two values and two directions make 4 possibilities. To this, let's add the number of possible jumps: k+1 if there's k states. The +1 is due to the terminal state. So, we've got 4*(k+1) possibilities for a given value. A state having two values (0 or 1), it's (4*(k+1))^2 each state. As there is k different states, we get: (4*(k+1))^(2*k).

The problem is that this expression is obviously over k^k and that the question becomes:

k | (4*(k+1))^(2*k) >= 10^(10^100)

I must admit that I didn't have any clue on how to cleanly solve this. Trying as many values of k as possible is hopeless. Here comes the Log. As a strickly growing function the order between the left part and right part is unchanged by the Log:

k | Log( (4*(k+1))^(2*k) ) >= Log ( 10^(10^100) )
So, k | 2*k * Log( 4*(k+1) ) >= 10^100
So, k | 2*k * (Log(4) + Log(k+1)) >= 10^100

Let's Log again:
k | Log(2) + Log(k) + Log(Log(4) + Log(k+1)) >= 100

Now, it's just about using Log(k) and Log(k+1) against 100. I'm sure that it's feasible, but let's do it by a program.

The program

The program, in the Python language, browse the values using an exponential scale. Once it gets over, then it turns back a try a 10th less scale. And so on until the Log of the Log of the number of possible Turing Machines reaches 100. The formatting disappears there, I replaced tabs by underscores.

# Python
# -*- coding: utf-8 -*-

# For how many states, there's more than one gogolplex of turing machines?

from math import log

def logLogNbTuring(k): return log(2.0*k,10)+log(log(4.0,10)+log(k+1.0,10),10)

# A value of 100 means that we're searching for a number of machines greater than 10^(10^100), more than a gogolplex.
nbTenPowerTen = 100

step = 1
while logLogNbTuring(step) step /= 10
print "log(step,10) set to %i" % log(step,10)

i = 1
belowValue = i
while (step>=1):
_if logLogNbTuring(i)>=nbTenPowerTen:
__i = belowValue
__step /= 10
_belowValue = i
_i+=step

# belowValue contains the last value before the limit, so add 1 to get over the limit
i = belowValue + 1
print "nbTenPowerTen=%i, solution=%i" % (nbTenPowerTen, i)
print "log(solution,10)=%f" % log(i,10)

The result

answer = 50 860 333 466 396 650 825 817 657 241 650 242 602 634 644 785 968 021 580 236 147 821 863 292 723 816 479 721 264 913 714 249 728
I think that because of rounds that this number is not strictly the exact solution. But that's not the point: Log(answer) = 97.70 means that answer almost equals 10^100, a Googol.

A Turing machine with almost one Googol states means one Googolplex possibility of Turing machines.

Tags de l'article :

Un cookie n'est ni un fichier, ni un programme !

20/12/2013 - Aucun commentaire

Les cookies ne sont pas des fichiers, ni des programmes. Ce sont des données placées par les sites web, qui peuvent se matérialiser sous la forme de fichiers, mais pas seulement. C'est une des choses qui rendent la navigation distinguable d'une autre lorsqu'on est connecté. Internet Explorer stocke un cookie par fichier, mais Firefox les stocke dans une seule base de données nommée cookies.sqlite. Les cookies de session eux, ne sont conservés qu'en mémoire il me semble. Nous sommes bien loin du fichier.

Concernant les cookies revenant après leur suppression, c'est principalement dû à Flash. Il utilise son propre lieu de stockage de données locales. Les publicitaires ont donc mis au point une application Flash, invisible, dont le seul travail consiste à télécharger les données déjà connues et reconstituer les cookies correspondants. C'est d'ailleurs le principal intérêt du "rich media" que de fournir un moyen de contourner la volonté de l'utilisateur en s'écartant des normes habituelles des pages web telles HTTP ou Javascript.

La politique demandant à l'utilisateur s'il souhaite autoriser les cookies est une absurdité. Si l'utilisateur refuse, comment ce choix est-il retenu ? Avec un cookie ? En cas de refus, il faudra lui poser la question à chaque fois ? Quand c'est un message surgissant, c'est systématiquement dérangeant. Quand c'est relativement discret dans la page, l'utilisateur risque de passer à côté. De fait, bloquer les cookies n'est pas la garantie que le site ne trace pas. Il reste possible de personnaliser la page web servie au visiteur pour y inclure un identifiant. Bien sûr, c'est moins efficace que les cookies puisque cet identifiant disparaît à la fermeture de l'application. Il existe aussi d'autres techniques plus délicates pour tracer les gens, comme le décrit Evercookie.

Que faire ?


Installer Flashblock sous Firefox pour interdire Flash par défaut, exiger qu'on clique pour exécuter ces programmes. À ma connaissance, sauf Youtube et autres, il n'est presque jamais nécessaire d'autoriser Flash a s'exécuter systématiquement. On devrait aussi installer une extension comme Self destructing cookies qui permet de détruire les données locale dès qu'on quitte le site les utilisant.

Il y a bien d'autres choses encore à faire.

Tags de l'article :

"Journalistes"

21/02/2013 - Aucun commentaire

Au cours d'une manifestation d'agriculteurs, deux journalistes ont été pris à parti par des manifestants. Leur caméra a été détruite. Faut-il s'étonner que les journalistes ne soient pas les bienvenus ? Source, http://www.arretsurimages.net/contenu.php?id=5633 (payant).

Sans préjudice sur le pourquoi du comment, et même à supposer que des méchants manifestants ont tapé sur les gentils journalistes, cette histoire ne m'étonne pas. Depuis des années, des abrutis de "journalistes" arrivent avec leurs idées préconçues et la conclusion de leur article, commandé, déjà en tête. Alors quand ont les voit débarquer, ce n'est guère étonnant de voir le résultat. Si ça pouvait apprendre leur métier à cette profession largement orientée, ce serait super. Et sinon, il faut recommencer à repousser la désinformation. Encore.

Il a des exceptions. Par exemple ArrêtSurImage, MediaPart et le Canard enchaîné, pour citer les principaux. Sans publicité, il me semble, et (donc) sans donneur d'ordre. Les autres, financés aussi par la publicité, s'accrochent à nos impôts pour subsister. Qu'il crêvent. Et que leurs salariés retournent à l'école. Et que Google les dé-référence, mais bon, ils ont trouvé le moyen d'arnaquer l'État français, consentant, et ses "journalistes" sur commande pour recevoir un peu de lumière depuis Internet.

Je propose donc qu'ArrêtSurImage dépêche une équipe sur place pour voir comment ça se passe. Ce n'est pas son objectif, je sais, mais ce serait instructif.

Tags de l'article :

Cryptanalyse de l'algorithme CENAv03

22/04/2012 - 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

descriptif
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

énigma
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

descriptif

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 ?

descriptif
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



Le code source est disponible ici.

Tags de l'article :

Plena Ilustrita Vortaro de Esperanto, serĉilo

10/04/2012 - Commentaires fermés

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

Tags de l'article :

For how many states, there's more than one Googolplex of turing machines?

27/09/2011 - Commentaires fermés

This is a great way to enter the world of great numbers, with a bit of theory and practical sort of innovation...

Main terms

What is a Turing Machine?

A Turing Machine is a very simple computer which was designed by Alain Turing in 1936. A Turing Machine is described by states, each states pointing to other states according to some conditions. You may read a bit more about Turing machines in order to fell all the taste of this article.

What are Googol and Googolplex ?

A Googol is a number represented by 1 followed by 100 zeroes. That is, 10^100. A Googolplex is 10 power Googol - that is, a number represented by 1 followed by a Googol of zeroes : 10^(10^100). Somewhat huge.

What is the Log function ?

The Log function approximatively gives the number of digits of a number. It's the reciprocal function of y = 10^x. So, x = Log(y). This function is important here because of one of its main properties. It turns multiplications into additions. So, the calculations will involve far less huge numbers.

So what?

A resolution

The question is: how many states do I need to be able to build one Googolplex Turing Machines? Winter's cold, brain's hot.

The Turing Machine considered here is the more simple one: two different values and two different directions. Two values and two directions make 4 possibilities. To this, let's add the number of possible jumps: k+1 if there's k states. The +1 is due to the terminal state. So, we've got 4*(k+1) possibilities for a given value. A state having two values (0 or 1), it's (4*(k+1))^2 each state. As there is k different states, we get: (4*(k+1))^(2*k).

The problem is that this expression is obviously over k^k and that the question becomes:

k | (4*(k+1))^(2*k) >= 10^(10^100)

I must admit that I didn't have any clue on how to cleanly solve this. Trying as many values of k as possible is hopeless. Here comes the Log. As a strickly growing function the order between the left part and right part is unchanged by the Log:

k | Log( (4*(k+1))^(2*k) ) >= Log ( 10^(10^100) )
So, k | 2*k * Log( 4*(k+1) ) >= 10^100
So, k | 2*k * (Log(4) + Log(k+1)) >= 10^100

Let's Log again:
k | Log(2) + Log(k) + Log(Log(4) + Log(k+1)) >= 100

Now, it's just about using Log(k) and Log(k+1) against 100. I'm sure that it's feasible, but let's do it by a program.

The program

The program, in the Python language, browse the values using an exponential scale. Once it gets over, then it turns back a try a 10th less scale. And so on until the Log of the Log of the number of possible Turing Machines reaches 100. The formatting disappears there, I replaced tabs by underscores.

# Python
# -*- coding: utf-8 -*-

# For how many states, there's more than one gogolplex of turing machines?

from math import log

def logLogNbTuring(k): return log(2.0*k,10)+log(log(4.0,10)+log(k+1.0,10),10)

# A value of 100 means that we're searching for a number of machines greater than 10^(10^100), more than a gogolplex.
nbTenPowerTen = 100

step = 1
while logLogNbTuring(step) step /= 10
print "log(step,10) set to %i" % log(step,10)

i = 1
belowValue = i
while (step>=1):
_if logLogNbTuring(i)>=nbTenPowerTen:
__i = belowValue
__step /= 10
_belowValue = i
_i+=step

# belowValue contains the last value before the limit, so add 1 to get over the limit
i = belowValue + 1
print "nbTenPowerTen=%i, solution=%i" % (nbTenPowerTen, i)
print "log(solution,10)=%f" % log(i,10)

The result

answer = 50 860 333 466 396 650 825 817 657 241 650 242 602 634 644 785 968 021 580 236 147 821 863 292 723 816 479 721 264 913 714 249 728
I think that because of rounds that this number is not strictly the exact solution. But that's not the point: Log(answer) = 97.70 means that answer almost equals 10^100, a Googol.

A Turing machine with almost one Googol states means one Googolplex possibility of Turing machines.

Tags de l'article :