Ajax's Home

Le chaos dans la cryptographie

admin — Wed, 17 Feb 2010 16:58:43 +0000

Après une longue absence, je reviens pour vous parler d’un sujet récent, la cryptographie chaotique.

En effet, la cryptographie actuelle, en particulier RSA et DES souffrent de la monté de la puissance de calculs des ordinateurs, et l’arrivée de l’ordinateur quantique pourrait bien sonner le glas de ces algorithmes. Pour remédier, et surtout trouver un remplacent, 2 pistes intéressent les chercheurs actuellement :

- La cryptographie Quantique ( Que je n’aborderais pas ici )

-La cryptographie Chaotique ( Qui est le sujet principal de cet article )

La cryptographie chaotique repose sur l’utilisation, comme son nom ne l’indique pas, du chaos. Mais on parle ici du chaos au sens physique du terme, décrit par la théorie du chaos, s’intéressant à des systèmes déterministes mais avec une forte sensibilité aux conditions initiales.
Le jeu de billard en est un exemple. En effet, il est aisément concevable que l’on ne pourra pas renvoyer une bille exactement d’où elle vient, il faudrait qu’elle soit renvoyée avec exactement la même force, le même angle. En supposant que ces deux conditions soient remplies, il n’est pas dit que les bandes du billard réagissent de manière identique. Les conditions initiales vont donc jouer un rôle déterminant dans l’évolution de la bille.

L’étude de cette théorie est relativement récente, et a intéressé/intéresse les militaires, ne permettant à la recherche civile de ne s’y intéresser que récemment…

Le principe de la cryptographie chaotique est de noyer le message à transmettre dans un chaos et de l’envoyer à un récepteur qui connait les caractéristiques du générateur de chaos, qui pourra donc soustraire le chaos au signal reçu et ainsi en extraire le message.

Des implémentations physiques sont à l’étude, comme l’explique cet article de tout-pour-la-science et l’illustre le projet OCCULT .

Je vais dans cet article vous présenter la méthode générale ( numérique ), puis les améliorations possible grâce à la méthode de Baptista ( pas le catcheur hein ) et de Wang. Je présenterais ensuite quelques attaques de cryptanalyse et comment le chiffrement chaotique y répond. Il faut être bien conscient que c’est une lutte dans le temps, et que les deux camps font des avancer à des vitesses impressionnantes ( grâce notamment aux avancés récentes de la théorie des nombres ). Les réponses actuelles seront donc peut-être dépassé d’ici à quelques années. Peut-être, voir même très surement.

Prenons la suite défini par la relation de récurrence Xn+1 = Xn * k * (1 – Xn), avec X0 dans [0,1].

Prenons par exemple X0 = 0,2 et k = 2. La suite a cette allure :

Mais si l’on prend k=3.6 :

Et l’on aperçoit ici un comportement chaotique. Nous allons donc prendre cette suite comme base de notre chiffre.

Fixons ses conditions initales : X0 = 0.4362719749372

k = 3.78

Ces conditions initiales vont représenter le secret dont aura besoin la machine qui va décrypter le message.

On va ensuite définir un alphabet qui va faire correspondre nos différentes lettres à des nombres. Je vais pour cela prendre la table ASCII.

On se restreint ensuite à un intervale, ici Xmin = 0.2 et Xmax = 0.8, l’intervalle est [0.2,0.8] .

On subdivise cette intervalle en 256 intervalles différents ( correspondant aux nombre de caractères différents que l’on code ). On appellera ces intervalles S0, S1, … avec Si = [Xmin + E*i,Xmin + E*(i+1)[ et E = (Xmax - Xmin)/256 . On se défini aussi un N0 = 96 arbitraire et un Nmax = 256² = 65536

Le principe est alors le suivant :

On souhaite coder le message "Code". Ce qui correspond à 67 111 100 101 . On fait ensuite correspondre chaque intervalle Si au caractère représenté par le nombre i. Ainsi, S65 représente A.

Maintenant, on itère notre suite au moins N0 fois, et jusqu'à ce qu'on ai Xn qui appartient à S67 . Dans notre cas, on va avoir n = 406 et Xn = 0,358579557009 . On va choisir ce Xn comme étant notre nouveau X0' .

Et on itère notre suite au moins N0 fois avec cette nouvelle condition initiale, jusqu'à ce que l'on ai Xn' qui appartient à 111. On obtient n' = 563. Et on recommence l'opération pour 100 et 101.

On obtient ainsi notre message codé. Pour le décoder, il suffit de faire le travail en sens inverse : On commence par itéré 406 fois pour obtenir l'intervalle, donc le Si, donc le i et donc le caractère correspondant, puis on recommence en prenant le X406 comme X0' et en itérant 563 fois, ...

La méthode est donc simple et avec un grand niveau de sécurité, ne présentant aucun raccourci et ne dépendant que de la clé de départ ( X0 et k ).De plus, les caractères qui se répètent ne sont pas codés de la même manière ( pas d'analyse fréquentielle à priori possible ).

Un de problème est que le message "Code" sera toujours codé de la même façon avec une même clé.

On introduit donc 2 ajouts, la méthode de Baptista et la méthode de Wang. La méthode de Baptista consiste à choisir un l dans [0,1[ et à généré à chaque fois que l'intervalle Si désiré est atteint,un nombre K pseudo aléatoire. Si K > l, on s'arrête, sinon on continue à itérer jusqu'à retomber de nouveau dans l'intervalle Si. On recommence alors l'opération.

Bien entendu, plus l est grand, plus le temps de calcul est important. Il devient déraisonnable à partir de 0.95 environ. Un bon choix est l = 0.8, car la courbe du temps nécéssaire pour coder en fonction de l est linéaire jusqu'à 0.8 . Elle devient ensuite exponentielle.

Un avantage de cette méthode est qu'elle est assez facile à implémenter et que le décrypteur n'a pas à être changé.

La méthode Wang, elle, consiste à choisir à chaque caractère un R pseudo-aléatoire dans [0,Rmax], puis de faire R itérations avant de prendre le nouveau X0′. Donc si il faut 406 itérations pour atteindre S67, on va en faire R2 de plus, et démarré avec X0′ = X(67 + R2) . On transmettra ensuite R1 +406, R2 + 563, …

La méthode reste viable pour Rmax < 60000. Elle présente les mêmes avantages que la méthode Baptista.

Parlons maintenant des attaques sur cet algorithme. La première, la plus connue surement, le Brute Force, c’est à dire tester toutes les possibilités pour la clé, et faire derrière une analyse pour vérifier si le texte est intelligible. Cette méthode à très peu de chance d’aboutir en un temps raisonnable pour la cryptographie chaotique, grâce en particulier à la sensibilité aux conditions initiales ( modifier X0 de 0.00000000000000001 suffit à complètement changé le code en sortie !).

Une deuxième attaque envisageable est une Memory attack, qui va consister à prendre les lettres les plus répandus, et à créer une base de donnée qui va recenser les divers codes possibles, avec leur correspondance pour la clé. Une telle base permet d’obtenir des taux de réussite pouvant aller jusqu’à 60% en considérant les lettres « e », »t », »a », »o », »i », »n », »s », »r » , puisque dépendante (la réussite) de la première lettre.

Une bonne manière de s’en prémunir est de faire en sorte que la base devienne énorme, grâce à une méthode comme celle de Baptista, ou encore de modifier l’alphabet pour coder directement des doublets de lettres au lieu de lettre simple ( alphabet de 256*256 caractères ), ce qui ralenti les calculs mais permet d’augmenter la sécurité.

Une étude de 2007 [SETIT 07] à montré que la méthode de Baptista, même avec un coefficient de 0.99, reste vulnérable à une attaque de texte clair choisi ( décrite dans le document ) si le message est suffisamment long, comme c’est le cas par exemple pour une image. Mais la possibilité réelle de cette attaque reste limité. Néanmoins, l’auteur propose l’amélioration suivante : l’introduction d’une fonction f(X) discrète, qui donnera une valeur pseudo-aléatoire qui pourra être rajouter au code de sortie.

D’autre amélioration sont à l’étude, et paraissent les unes après les autres.Et comme la puissance d’un outil de chiffrement dépend aussi de sa vitesse de d’encryption ou encore de la facilité de son implémentation, beaucoup de domaine sont concernés. On pourra citer par exemple l’idée de passer d’un code de bloc de 8 bits à un bloc de 4 bits, ce qui peut permettre d’aller jusqu’à 12 fois plus rapidement dans l’encryption d’un fichier texte. On pourra aussi citer les différentes tentatives d’implémentations, comme le projet déjà cité OCCULT, et la possible industrialisation du procédé grâce au projet INTOCCULT.

En somme, je pense qu’il va être intéressant de suivre les actualités sur ce sujet, et la bataille que vont se livrer, que se livre déjà même, les cryptanalystes et les cryptologues .

Pour vos tests personnels, je vous mets un bout de code python qui simule le chiffrement et le déchiffrement par la méthode générale ainsi que par la méthode Baptista. Je vous conseille d’observer à quel point le système est sensible aux conditions initiales, c’est édifiant !

#! usr/bin/python
import string,math,random
#Conditions initiales :
X0 = 0.358579557009
k = 3.78
N0,Nmax = 96,256*256
n = 0.8

eps,Xmin,Xmax = 0.6/(256), 0.2, 0.8
Message= "Hello World!"

def crypt(entre,baptista = False):
 global X0,k,N0,Nmax,eps,Xmin,Xmax,n
 sortie,X1 = "",X0

 for j in range(0,len(entre)):
 if(baptista):
 r,i = 0,0
 while(r<=n):
 X1 = k*X1*(1-X1)
 i += 1
 while(((X1< Xmin + ord(entre[j])*eps ) or (X1>= Xmin + (ord(entre[j]) + 1)*eps)) or i= Xmin + (ord(entre[j]) + 1)*eps)) or i
Bibliographie/Webographie : 
http://www.hkstar.com/~hmk409/research/ces/research/200107/project.htm
SETIT2007 : Analyse De Sécurité d’une Nouvelle Méthode De

Cryptage Chaotique

Nada REBHI, Mohamed Amine BEN FARAH, Abdennaceur KACHOURI &

Mounir SAMET
Tout pour la science :  http://www.tout-pour-la-science.com/2284/S%E9curisation+de+l%27information+:+le+cryptage+par+le+chaos.html
Illustrastion Verhlust Henon
Spyworld-actu : http://www.spyworld-actu.com/spip.php?article1214

La bêtise est humaine

admin — Thu, 06 Aug 2009 13:49:36 +0000

Il m’est rare de poster des billets d’humeur, mais là je n’ai pas vraiment pu m’en empêcher.

J’ai eu récemment la très belle et appréciable idée de faire le tour de mon compte chez mon hébergeur, de vérifier qu’il n’y a plus de choses qui sont un peu « outdate » . Alors oui, j’avais une ou deux bases de données qui n’étaient plus du tout utilisé, donc je les ais supprimé. Et de l’art de bien décrire ses bases de données, la vielle description présente ne m’a pas mis la puce à l’oreille. Et c’est mon blog que j’ai supprimé. Aucune backup SQL.

Donc mission récupération des articles grâce au cache google ( et non webarchive :s ), réinstallation de wordpress et de nouvelle base de données, et remises en état des articles. C’est pourquoi il ne sont peut-être pas forcément dans l’ordre, et qu’il risque de manquer certaines images.

Mais bon, on apprend de ses erreurs, et celle là ne m’arrivera plus ! ( du moins je l’espère )

Sur ce, bonne lecture à tous/toutes

Ajax

Introduction à quelques concepts de l’intelligence artificielle

admin — Thu, 06 Aug 2009 13:45:17 +0000

Quel sujet vaste que celui de l’intelligence artificielle !

Il m’en impossible ici d’en aborder toutes les facettes, ne serait-ce que parce que les principes de certaines m’échappent totalement. Non, je vais essayer de vous montrer deux trois choses, des éléments qui pourront vous aider dans votre compréhension de ce vaste monde. Peut-être que d’autres articles suivront…

En tout cas, celui-ci va d’abord vous présentez un jeu, le tic-tac-toe ( ou morpion ), ainsi qu’un possible joueur artificiel à ce jeu. Cela me permettra d’aborder l’algorithme MinMax et son “extension” Alpha-Bêta.

Après avoir vu ces joueurs déterministes, c’est à dire qu’ils joueront la même chose pour une même situation, je vous présenterais différentes méthodes d’apprentissage. Notre joueur évoluera au fil des parties.

Tout d’abord, qu’est-ce que le tic-tac-toe ?

Les règles sont simples : Le terrain de jeu contient 3×3 cases. Les 2 joueurs jouent en tour par tour. A chaque tour, un joueur remplis une case vide avec un signe/couleur qui lui correspond. Le but du jeu est de réussir à aligner 3 fois son signe, que ce soit horizontalement, verticalement ou en diagonale, avant son adversaire. A ce moment là, la partie s’arrête. Si aucun des deux n’arrivent à aligner 3 cases et que les 9 cases sont remplies, il y a match nul.
Bref, c’est un jeu que vous connaissez surement.

Maintenant, notre but va être de construire un adversaire virtuel, artificiel. Une première possibilité serait de lui dire de jouer aléatoirement sur une case libre. On conçoit assez facilement qu’un adversaire de ce type est très facile à battre.

Une deuxième possibilité va être d’utiliser un algorithme, nommé MinMax. Cette algorithme va nous donner des résultats très satisfaisant, mais pour un temps de calcul relativement long ( relativement, parce que pour un jeu de 9 cases, il est en faite très rapide; mais il devient inutilisable pour un jeu comme celui des échecs ).

Considérons l’arbre de possibilité d’une partie. Je m’explique :

Nous allons utiliser la notation suivante, les chiffres représentent les cases ordonnées de cette façon :

1 2 3
4 5 6
7 8 9
et X le signe du Joueur 1(humain), O le signe du Joueur 2(artificiel), V une case vide.

La situation actuelle est :
V X X
O O V
X O X

C’est donc à J2 de jouer. Son arbre de possibilité, avec une profondeur de 1, est

Il joue en 1=>

O X X
O O V
X O X

Il joue en 6 =>

V X X
O O O
X O X

De profondeur 1, car nous nous intéressons seulement au prochain coup.

Maintenant, nous allons nous définir une fonction d’évaluation, que l’on nommera eval() . Cette fonction évalue la partie à un instant donné. C’est en général son écriture qui est la principale difficulté de l’algorithme MinMax. En effet, comment définir une évaluation du jeu ?

Pour nous simplifier les choses, nous diront que la fonction renvoi 1 si J2 gagne, -1 si J1 gagne et 0 si il y a impression d’égalité.

Bien, maintenant, regardons notre précédent jeu, avec une profondeur d’arbre de 2 ( qui suffit à décrire toutes les possibilités restantes ).

A:J2 => 1 – B: J2 => 6

C:J1 => 6

SI J2 joue en 1, on se retrouve dans la situation A, et J1 va jouer en 6, pour se retrouver dans la situation C ( fin de partie ). Si J2 joue en 6, on se retrouve dans la situation B ( fin de partie ).

Maintenant, on a eval(A) = 0, car aucun gagnant; eval(B) = 1, car c’est J2 qui gagne; eval(C) = -1 car c’est J1 qui gagne.

L’algorithme va donc construire l’arbre complet des possibilités, puis il va remonter. Chaque départ de branche est appelé un nœud . Donc à chaque fois que l’on augmente la profondeur, on descend d’un nœud .

Une fois l’arbre complet des possibilités fait, et chaque possibilité évaluée, l’algorithme va progressivement remonter l’arbre. Pour se faire, il va prendre la valeur Minimale de toute les possibilités obtenus au départ d’un nœud .

Par exemple, la valeur en A va devenir -1, car depuis A, on peut atteindre C, qui vaut -1 et qui est la plus petite valeur que l’on obtenir depuis A. En B, la valeur restera 1, car c’est la seule valeur que l’on peut obtenir depuis B ( et donc la plus petite ).

On se retrouve ainsi avec jouer en 1 => -1, joueur en 6 => +1 . A ce moment là, l’algorithme va choisir le Maximum, c’est à dire +1, et donc J2 va jouer en 6 ( et remporter la partie ).

Voici donc le principe de l’algorithme MinMax . On comprend la lenteur de l’algorithme, car il doit explorer et évalué chacune des possibilités à partir d’une situation donnée, ce qui peut vite devenir interminable .

Imaginons maintenant une branche de l’arbre de possibilités suivant, pour un jeu arbitraire :

D - E

B:3 – C:1 F:2 – G:5 – H: 3

Que vaut eval(A) ?

Tout d’abord, trouvons eval(D). max(B,C) = 1. Donc eval(D) = 3. Ensuite, nous allons calculer eval(E). Il faudrait donc calculer max(F,G,H), c’est à dire d’abord évaluer F, puis G, puis H, en espérant par aussi qu’il n’y ai pas encore de nœud . Beaucoup de travail en perspective encore. Mais rappelons nous que A = min(D,E). Or, l’évaluation de G renvoi 5, 5 > 3. Et comme eval(E) = max(F,G,H), eval(E) >= 5 . La valeur de E sera de minimum 5. Et 5 est plus grand que la valeur obtenu en D. Donc pas besoin d’évaluer H, car de toute façon, E > D . Donc A = D = 3 .

On a sauté une étape de calcul, ce n’est peut-être pas flagrant côté temps gagné. Mais imaginé la même chose avec des arbres de profondeur 10 et plus . Le temps d’exécution de l’algorithme peut être aisément divisé par 10 !

Ce nouvel algorithme s’appelle Alpha-Bêta.

Je ne vous présente pas ici de code implémentant ces deux algorithmes pour le jeu du tic-tac-toe, car vous pourrez aisément les trouver sur http://fearyourself.developpez.com/tutoriel/sdl/morpion/ ( part6 et part7 ). Si vous n’avez pas très bien compris mon explication, je vous invite à lire celles présentés à cette adresse, elles sont très bien illustrées.

Ces différents algorithme ont le désavantage d’être déterministe. C’est à dire que pour une situation donnée, ils joueront toujours la même chose. Pour le jeu du tic-tac-toe, ce n’est pas grave, puisqu’il existe une stratégie optimale. Mais pour d’autre jeu, plus complexe, ce n’est plus utilisable.

On peut alors se tourner vers des algorithmes qui vont apprendre au fur et à mesure des parties.

Il faut savoir qu’il y a plusieurs méthodes d’apprentissage :

- Par cœur : Vous apprenez par exemple par cœur les règles. Ce sera toujours pareils. Certains bon joueurs au échecs connaissent dans certaines situation le coup optimal à jouer. Ils connaissent donc ces situations par cœur .

- Supervisé : Un apprentissage supervisé est un apprentissage assisté d’un expert du jeu. Il vous donnera les bonnes stratégies, les erreurs à ne pas commettre, …

- Par imitation : On peut apprendre par imitation en reproduisant une stratégie qu’on l’on à déjà vue.

- Par renforcement : On apprend de nos erreurs.

- Par découverte : Au fur et à mesures des jeux, on trouve de nouvelles possibilités.

Il faut savoir que certaines machines sont très fortes dans des jeux répétés contre des adversaires humains, car elles apprennent au fur et à mesures à la fois de nouvelles stratégies, les renforcent, et arrivent même à prédire ce que l’humain va jouer. Je citerais par exemple le résultat d’une thèse, SAGACE ( dont je ne présenterais pas le fonctionnement ici, car il est plutôt complexe ).

Alors qu’est-ce que nous donnent un adversaire qui va apprendre au fur et à mesure des parties ?

J’ai réalisé un adversaire qui apprend à jouer au tic-tac-toe par imitation ( le code python est disponible tout en bas de l’article ).

C’est à dire qu’il va, au fur et à mesure des différents jeux, voir ce que je joue dans une situation donné. Si il se retrouve dans la même situation, il jouera alors ce que j’ai joué.

Il est clair que les premières parties sont gagnées haut la main par le joueur humain. Mais on sent tout doucement l’IA tendre vers une stratégie optimale ( si on considère que le joueur humain joue de façon optimale ). Au bout d’un moment, il n’est plus possible de gagner, toutes les parties mènent à égalités, si l’on joue de manière optimale.

Pour gagner, à ce moment là, il faut jouer un coup inattendu, voir idiot, pour se retrouver dans une situation que la base de données des coups précédemment joué ne connais pas. Et à ce moment là, vous pourrez facilement gagné.

De même, au bout d’un moment, il n’y a plus possibilité de gagné, même de cette façon.

Je ne présente pas les autres méthodes d’apprentissages, peut-être seront-elles sujets d’un autre article, car celui-ci comment à vraiment devenir long.

Sur ce, je vous souhaite donc une agréable journée, et de belles parties de tic-tac-toe .

Le code présenté ci-dessus ne gère pas les différentes symétries des situations, il reste basique et à des fins de test.

from random import *

terrain = [0,0,0,0,0,0,0,0,0,0]
# 1 2 3
# 4 5 6
# 7 8 9
#Rien : 0, Joueur : 1, IA : 2
gagnant = 0

def check_terrain():
    global terrain,gagnant
    gagnant = 0
    if (terrain[1] == terrain[2]) and (terrain[2] == terrain[3]) :
        gagnant = terrain[2]
    elif (terrain[2] == terrain[5]) and (terrain[5] == terrain[8]) :
        gagnant = terrain[5]
    elif (terrain[4] == terrain[5]) and (terrain[5] == terrain[6]) :
        gagnant = terrain[5]
    elif (terrain[7] == terrain[8]) and (terrain[9] == terrain[8]) :
        gagnant = terrain[7]
    elif (terrain[1] == terrain[4]) and (terrain[4] == terrain[7]) :
        gagnant = terrain[1]
    elif (terrain[3] == terrain[6]) and (terrain[6] == terrain[9]) :
        gagnant = terrain[3]
    elif (terrain[1] == terrain[5]) and (terrain[5] == terrain[9]) :
        gagnant = terrain[5]
    elif (terrain[3] == terrain[5]) and (terrain[5] == terrain[7]) :
        gagnant = terrain[5]
    else :
        eg = 1
        for i in range(1,10):
            if (terrain[i] == 0) :
                eg = 0
        if (eg==1):
            gagnant = 3
    return gagnant

def cherche_strat():
    global terrain
    t = 0
    bdd = open('bdd.txt','r')
    while 1:
        txt = bdd.readline()
        if txt=='':
            t=0
            break
        if ((txt[0] == str(terrain[1]) or txt[0] == '*') and (txt[1] == str(terrain[2]) or txt[1] == '*') and (txt[2] == str(terrain[3]) or txt[2] == '*') and (txt[3] == str(terrain[4]) or txt[3] == '*') and (txt[4] == str(terrain[5]) or txt[4] == '*') and (txt[5] == str(terrain[6]) or txt[5] == '*') and (txt[6] == str(terrain[7]) or txt[6] == '*') and (txt[7] == str(terrain[8]) or txt[7] == '*') and (txt[8] == str(terrain[9]) or txt[8] == '*')):
            t = txt[10]
            break
    bdd.close()
    return t

def play_ia():
    global terrain

    t = cherche_strat()
    print t
    if (t!=0) :
        terrain[int(t)] = 2
    else:   
        #IA Aleatoire
        k = randint(1,9)
        while(terrain[k] != 0):
            k = randint(1,9)
        terrain[k] = 2

    return 0

def affiche_terrain():
    global terrain
    print ""
    print terrain[1],terrain[2],terrain[3]
    print terrain[4],terrain[5],terrain[6]
    print terrain[7],terrain[8],terrain[9]
    return 0

def joueur():
    global terrain
    i = input("Jouer sur la case : ")
    while(terrain[i] != 0):
        i = input("Jouer sur la case : ")

    #Imitation
    if (cherche_strat() == 0):
        bdd = open('bdd.txt','a')
        bdd.write(str(terrain[1]*2 % 3) + str(terrain[2]*2 % 3) + str(terrain[3]*2 % 3) + str(terrain[4]*2 % 3) + str(terrain[5]*2 % 3) + str(terrain[6]*2 % 3) + str(terrain[7]*2 % 3) + str(terrain[8]*2 % 3) + str(terrain[9]*2 % 3) + ' ' + str(i) + '\n')
        bdd.close()

    terrain[i] = 1
    return 0

flag = randint(0,1)
flag = flag * 2 - 1

while(check_terrain() == 0):
    if(flag == 1) :
        affiche_terrain()
        joueur()
        flag = -flag
        if(check_terrain() != 0):
            break
    elif(flag == -1) :
        play_ia()
        flag = -flag

k = check_terrain()
if(k ==1) :
    print "Vous avez gagner !"
elif(k ==2 ):
    print "L'IA gagne !"
else:
    print "Match NUL !"

print check_terrain()

Quelques résultats sur l’arrêt optimale

admin — Thu, 06 Aug 2009 13:44:36 +0000

Un précédent article porte sur la théorie des jeux. Il nous permet d’obtenir des stratégies optimales pour un grand nombre de jeux.

Je vous propose ici d’autres résultats, concernant des jeux dont le gain dépend directement du moment où le joueur s’arrête.

Le premier jeu présenté sera un lancé de dés. Le principe est le suivant : le joueur lance un premier dé, il peut choisir de s’arrêter. Si il s’arrête, il gagne en euros le score du dé. C’est à dire que si il fait un 6 et qu’il choisi de s’arrêter, il gagne 6 €. Il peut aussi choisir de continuer, donc de lancer un deuxième dé, et de nouveau, il a la possibilité de s’arrêter. Si il le fait, il gagne le score du second dé, et ainsi de suite.
Il a le droit à 6 lancés de dé, sachant qu’au bout du 6ème il est obligé de s’arrêter ( et donc de gagner en euros ce qui est indiqué sur le dé ).

Quelle est la stratégie optimale à ce jeu ?

En effet, il est certain que si j’obtiens un 6 à n’importe quel lancé, je m’arrête ( Je ne pourrais pas obtenir mieux que 6€ de gain ). Mais qu’en est-il si j’obtiens un 4 à mon premier lancer ? ou un 3 à l’avant dernier lancer ?

Eh bien, pour ce genre de situation/jeu , un outil va nous permettre de déterminer la stratégie à adopter ( c’est à dire que faire à chaque lancer si on souhaite une espérance mathématique du gain maximale ). J’ai nommé la récurrence à rebours.

Le principe est le suivant : Nous allons partir du dernier lancé, regarder la stratégie optimale, puis revenir à l’avant-dernier lancé, faire de même, etc .. jusqu’au premier lancé. Et donc en tiré la stratégie à adopter sur tout le jeu. Mais appliquons cette méthode à notre problème de lancé de dé, ce sera plus clair.

Tout d’abord, si nous n’avions qu’un seul dé, l’espérance mathématique serait de 3,5 € ( 1/6 * 1 + 1/6 * 2 + 1/6 * 3 + 1/6 * 4 + 1/6 * 5 + 1/6 * 6 = 3,5 ). Donc sur le dernier lancé, nous pouvons espéré gagné 3,5€ .

Ainsi, sur l’avant-dernier lancé, nous savons que nous pouvons gagné 3,5€ avec le dernier lancé. Donc si nous faisons moi que 3,5 ( 1, 2 ou 3 ) nous attendrons le dernier lancé ; mais si nous faisons plus, c’est à dire 4, 5 ou 6, nous nous arrêtons, car nous ne pouvons pas espéré théoriquement mieux . On en déduit alors la stratégie optimale pour l’avant-dernier lancé qui est de s’arrêter si on obtient un 4, 5 ou 6 et de continuer sinon.

L’espérance mathématique de l’avant-dernier lancé vaut alors : (3/6 * 3,5 + 1/6 * 4 + 1/6 * 5 + 1/6 * 6 = ) 4,25 . Avec le même raisonnement que ci-dessus, la stratégie optimale au 4ème lancé est de s’arrêter si on obtient un 5 ou un 6, et de continuer sinon.

En remontant ainsi jusqu’au premier lancé ( d’où le terme “rebours” ), la stratégie optimale ( au regard de l’espérance mathématique à chaque lancé ) est :

1,2,3,4 lancé : s’arrêter si 5,6 ; continuer sinon
5 lancé : s’arrêter si 4,5,6 ; continuer sinon
6 lancé : s’arrêter dans tout les cas

Je vais maintenant vous présentez un deuxième problème d’arrêt optimale.

Le jeu est le suivant : Vous avez devant vous 100 papiers avec chacun un numéro, face caché, placés au hasard .Vous ne connaissez pas l’intervalle dans lesquels ont été choisi les numéros. Vous retournez les billets un par un, en vous arrêtant sur celui que vous estimez contenir le nombre le plus élevé. Si vous ne vous arrêtez pas avant, vous êtes obligé de vous arrêter sur le 100ème.

Un exemple avec 10 billets ( au lieu de 100 ) : Vous retournez le premier billet : 55, le deuxième 130, le troisième 20, le quatrième 150. Vous décidez de vous arrêtez. Pas de chance, le 7ème billet était 562 et le 9ème était 2314. Il fallait s’arrêter sur le 9ème.

Il est clair qu’intuitivement, les chances de gagner à ce jeu sont très faibles. En faite, nous allons montrer que finalement, elle ne sont pas si faibles que ça, elles sont même supérieures à 1/3 !

Montrer n’est pas le terme exacte, puisque nous n’introduirons pas ici de démonstration rigoureuse.
Des recherches universitaires ont montrés que le meilleur pourcentage de victoire est de 1/e ( où e = exp(1) , donc 1/e environ égal à 0,3678 ).

La technique utilisée est la suivante : il faut retourner tout d’abord E(N/e) +1 cartes ( partie entière du nombre de cartes totale quotient de exp(1) , + 1 ). On regarde alors quelle est le plus grand nombre que l’on connais actuellement. On appelle ce nombre un “record”. Puis on retourne une par une les cartes, jusqu’à obtenir un nombre qui dépasse notre précédent record. On s’arrête alors.

Cette technique est la technique optimale, garantissant 1/e chances de gagner .

J’avoue que lorsque j’ai vu ce résultat, je n’y ai pas trop cru. Et en tout bon lecteur non niais que vous êtes, j’espère que c’est un peu la même chose pour vous. J’ai donc écrit un petit programme, pas très long, qui simule à la fois le jeu ainsi que la méthode décrite ci-dessus, comptant le nombre de fois qu’elle est gagnante. L’expérience étant renouvelé 10000 fois, afin d’avoir des résultats assez correct en terme de statistique ( loi des grands nombres ).

On obtient ( pour 5 lancements ) : 0,3684 ; 0,3700 ; 0,3729 ; 0,3605 ; 0,3747

Des résultats donc relativement ( 10 000 lancés, c’est peu ) très proche de ceux annoncés par la théorie.

Un résultat qui est donc intéressant à connaitre. A noter qu’un officier s’est fait beaucoup d’argent en pariant avec ses collègues sur l’issue d’un tel jeux. 1€ pour tout le monde en cas de perte, 10€ dans sa poche de la part de chacun en cas de victoire, donc une espérance mathématique de 3,038 € / partie ( Évidemment, il ne présentait pas le jeu comme ça à ses collègues ! ).

Pour finir, voici le programme en python utilisé pour simulé le dernier jeu :

from random import *

score,n,k = 0,10000.,0

while(k < n):

    #Simulation d'un seul jeu
    tab,amax = [],1

    for i in range(1,101): # Création des billets et détermination du nombre le plus grand
        a = randint(1,50000)
        if a > amax :
            amax = a
        tab.append(a)

    #application de la méthode
    imax = 0
    for i in range(1,38):
        if tab[i] > tab[imax] :
            imax = i

    j,act = 38,tab[38]

    while(act < tab[imax] and j<99):
        j = j+1
        act = tab[j]

    if(amax == act) : #vérification
        score = score + 1

    k=k+1
print score/n #on affiche le résultat pour n( = 10 000 ) parties jouées
input()

Référence : Pour la Science N°381

Deux/trois mots à propos de la théorie des jeux…

admin — Thu, 06 Aug 2009 13:43:54 +0000

Théorie des jeux ? Argh .. encore des maths ?

Bon, des maths oui, mais ça va se résumé à savoir faire une fraction .

Qu’est-ce que la théorie des jeux ?

C’est la traduction mathématique et logique de problèmes qui peuvent être économiques, sociales, diplomatiques, etc. et de leurs solutions possibles, suivant plusieurs critères. Bon, pour être moins vagues, donnont l’exemple le plus connu du dilemne du prisonnier. Soit deux criminels qui vont passer séparemment un intérogatoire. La police n’a aucune preuve contre aucun des deux, elle souhaite donc des aveux. Si aucun des deux n’avouent, ils écoppent de 6 mois de prison. Si un des deux avoue, il est immédiatemment libéré, et l’autre suspect écoppent de 15 ans de prison. Si les deux avouent, ils partent chacun pour 8 ans de prison. Bien evidemment, les deux interrogatoires se déroulent simultanément.

Le suspect est donc confronté à un choix difficile. Dans le doute, il avouera, et l’autre, anticipant sa décision, avouera aussi pour éviter de prendre 15 ans. Ils prendront donc chacun 8 ans. Si ils avaient coopéré, ils n’auraient passé que 6 mois en prison.

La solution la plus probable ( appelée Equilibre de Nash ) n’est donc pas forcément la meilleure des solutions.

Avant de prendre un autre exemple, donnons quelques précisions. Chaque “participants”, précédemment les suspects, sont appelés “joueurs”. Chaque joueur a un éventail de stratégie, supposé connu par lui même et par les autres joueurs. Le jeu est dit à informations complètes. Chaque joueur essaye de jouer de sorte à maximiser ses gains. Chaque joueur peut anticiper les décisions des autres joueurs. Pour l’instant, le jeu n’est pas “dynamique”, c’est à dire que les décisions sont prises simultanément.

Prenons un second exemple. Le problème des marchands de glaces.

Supposons une plage de dimension 1, et deux marchands de glaces. La plage est remplie de touristes, qui vont aller acheter leur glace au marchand le plus proche. Logiquement, les marchands ( Joueur 1 et Joueur 2 ) vont se placer respectivement à 1/4 et 3/4 de la plage ( voir diagramme suivant ).

Cependant, le joueur 1 peut réfléchir et se dire que plus il va se rapprocher du joueur 2, plus il augmentera son nombre de client, et donc ses gains ( les gains sont supposés être une fonction croissante du nombre de client, donc de la zone “desservie” ). Le joueur 2 va également se dire la même chose. Au final, ils vont tout les deux se retrouver au milieu de la plage, comme le montre le diagramme suivant :

Cette solution correspondra l’équilibre de Nash. Je vous passe la démonstration, mais il est démontré que cet équilibre est unique. Pourtant, pour les groupes de touristes situés tout à gauche et tout à droite de la plage, cette solution n’est pas la meilleure, puisqu’ils doivent parcourir une plus grande distance.

L’équilibre de Nash, et donc la solution qui arrivera réellement n’est donc pas forcément la meilleure solution d’un point de vue social.

Dans un troisième exemple, nous allons maintenant considéré un jeu où le joueur 2 prend une décision après le joueur 1.

Le joueur 1 a deux stratégie, A et B. Le joueur 2 a lui aussi deux stratégie, C et D.

La matrice des gains est donnée par
(A,C) = (2,0)
(A,D) = (2,1)
(B,C) = (1,1)
(B,D) = (3,0) où 3 est le gain du joueur 1 et 0 le gain du joueur 2 .

On voit donc que la meilleur issue pour le joueur 1 est (B,D). Cependant, si il joue B, il sera logique pour le joueur 2 de jouer C, pour maximiser ses gains. Le joueur 1 ne remportera alors qu’un gain de 1. Partant de là, il peut se dire que si il joue 1, le joueur 2 va joueur D pour maximiser ses gains. Le joueur 1 aura alors un gain de 2. La combinaison qui sera très certainement jouer est donc (A,D).

Dans l’application au modèle commercial, le duopole de Cournot considère n entreprises qui vendent une quantitée Qi d’un produit à un certain prix p. La décision de la quantitée vendu est prise simultanément. On arrive aux résultats suivants :

Quand n tend vers l’infini, le prix de vente tend vers le prix de fabrication, et donc les gains tendent vers 0.
Toutes les entreprises gagneront autant, tout en vendant la même quantité. Si une entreprise signe un accord avec une autre, elles maximisent leurs profits.

Ensuite, le duopole de Stackelberg considère lui une entreprise qui vend d’abord une certaine quantité, puis une seconde entreprise qui vont une autre quantité, fonction de la première. On appelle alors meneur ( leader ) et suiveur ( follower ) la première et la seconde entreprise respectivement.

Et bien ce duopole montre que les gains de la première et de la seconde entreprise ne seront pas les mêmes.
On peut ainsi voir qu’une prise de décision simultanée et une dynamique n’aboutissent pas au même résultat.

( Je ne développe pas ici ces deux duopoles, mais vous invitent à lire des articles qui s’y rapportent, qui seront surement bien plus clair que mes explications ).

Pour terminer, nous allons aborder la théorie de l’engagement. Les joueurs peuvent s’engager à ne pas modifier certaine variable, pour maximier leurs gains. A priori, cette affirmation peut sembler fausse, mais revenons à notre exemple des marchands de glaces.

Nous allons maintenant considéré que pour s’implanter, un marchand de glace paye son installation C, valeur comprise entre 1/6 et 1/4 . Si les marchands ne font aucun engagement, l’équilibre de Nash sera comme le montre le diagramme suivant, deux marchands à 1/4 et deux autres à 3/4 :

Le gain de chacun sera alors de g = 1/4 – C ( > 0 ).

Maintenant, les marchands se fixent en localisation, c’est à dire qu’une fois qu’ils se sont mis a un endroit, ils ne bougeront plus.

Les deux premiers marchand qui arrivent se mettent chacun à une distance C du bord de la plage, pour s’assurer un gain qui ne sera pas négatif. Un troisième marchand qui arrivent se placera au milieu de la plage pour s’assurer d’avoir un maximum de gain. Un quatrième marchand qui arrivent ne pourra alors trouver d’endroit où s’implanter et espéré avoir un gain positif; en effet, même si il se met au milieu, son gain sera alors de g = 1/4 – 2C ( <0 ). Il ne viendra donc pas. Les gains des trois autres marchand seront donc supérieur à la première situation ( un marchand de plus est un manque-à-gagner pour les autres marchands ).

Cet exemple montre donc qu’il est possible d’augmenter ses profits en “s’engageant” à ne pas modifier certaines variables. En effet, si la localisation était restée variable, on se serait retrouver dans la première situation.

Ce dernier exemple conclu une ( petite ) introduction à la théorie des jeux.

A bientôt, bonne vacances à tous !

Echange de donnée cryptée, sans échange de clé unique ?

admin — Thu, 06 Aug 2009 13:42:13 +0000

Bonjour, c’est Bernard !

J’aimerais bien communiquer avec Alice, malheureusement Eve est dans le coin ….

Ah, je sais ! Je vais crypter mes données ! Pas de problèmes, plein d’algorithmes existent déjà comme DES, ou je peux même faire le mien !

Ah … mais il faut que je donne à Alice une clé… et Eve est très en forme sur les attaques ManInTheMiddle ces temps-ci …

Plus sérieusement, comment pourrait faire Bernard pour crypter ses informations sans que Eve ne puisse les décrypter ?
C’est à dire, comment éviter qu’Eve espionne l’échange de la clé, appelée clé privée ?

Ce fut le grand problème des cryptographes jusqu’à ce début de siècle, et jusqu’a l’idée de Diffie et Hellman. En effet, ils ont tout simplement imaginé qu’il était possible de ne pas utiliser seulement une clé privée dans une fonction cryptographique réversible. A partir de l’idée de la boite à cadenas, qui prouve qu’il est possible de ne pas utiliser seulement ces fonctions, l’idée fut de trouver des ( voir une ) fonction à sens unique.

Tout d’abord, qu’est-ce que la boite à cadenas ?
Bernard peut mettre son message dans une boite, qu’il refermera avec un cadenas A dont il est seul possesseur de la clé. Il envoie sa boite à Alice, qui ne peut l’ouvrir, mais qui rajoute un cadenas B dont elle est seule possesseur de la clé , et qui renvoie cette même boite à Bernard ( avec donc les cadenas A et B dessus ). Bernard enlève son cadenas A puisqu’il a la clé, et renvoi la boite à Alice. Alice peut maintenant enlever son cadenas B, ouvrir la boite, et lire le message de Bernard. Ici, le cadenas représente la fonction de cryptage, et la clé représente la clé utilisé. Dans cette exemple, Bernard n’a pas eu besoin d’échanger sa clé avec Alice, et donc, pas de risque d’interception. Et ça, c’est tout simplement une révolution pour le monde de la cryptographie.

Diffie et Hellman trouverons alors une technique utilisant une fonction à sens unique, j’ai nommé le modulo. Nous reviendrons sur cette technique dans un exemple plus bas.

Malheureusement, ces technique annihile l’instantanéité d’un moyen de communication comme l’email.
Si Bernard veut envoyer un message urgent à Alice, mais que celle ci s’est couché tard et dort encore, il devra attendre qu’elle se réveille, prenne son petit dej’, consulte ses emails, lui renvoi, …

Viens alors une autre idée, dont vous avez surement entendu parlé, qui est celle de la cryptographie à clé publique / privée. Cette cryptographie utilise une fonction très difficilement réversible. Très difficilement, pour éviter tout décryptage malencontreux, mais cependant possible pour permettre un décryptage ( autrement, on a affaire à une fonction de hashage ). Et c’est au trio Rivest Shamir Adleman que l’on doit RSA .

L’algorythme n’est pas très dur à comprendre, ni à mettre en place, et je vous conseille de lire la page de Wikipedia fr qui s’y rapporte : http://fr.wikipedia.org/wiki/Rivest_Shamir_Adleman .

Cependant, à cette époque, si Bernard souhaitait crypté un texte d’une longueur conséquente, les temps de calculs devenaient trop important pour être exécuté par un ordinateur personnel. Exit la cryptographie à clé public pour tous. Exit, sans compter Zimmerman et Pretty Good Privacy. L’idée, qui couta d’ailleurs beaucoup de temps et de procédure judiciaire à Zimmerman, était de réussir à mettre à la porté de tous la cryptographie à clé publique. Son logiciel, PGP, fonctionne de la manière suivante :

Tout d’abord, l’utilisateur génère le nombre N de l’algorithme RSA de manière aléatoire, par ses mouvements de souris. Pour tester si les nombres obtenus sont premiers, il existe des techniques très rapide permettant d’obtenir des nombres dits premiers probable. Sur des très grand nombre, comme ceux utilisé dans RSA, le risque que le nombre obtenu soit le résultat d’une factorisation qui n’est pas celle de deux nombres premiers, mais d’au moins un nombre composé, est moins élevé que celui de gagné au Loto ( enfin “risques”, on se comprend ). Ensuite, lors d’un échange, une clé est générée, puis crypté avec RSA ( en utilisant la clé publique du destinataire ), et cette même clé est ensuite utilisé pour crypter le message avec un algorithme à clé privé bien plus rapide, comme DES. La clé publique de l’expéditeur est envoyée avec le message. A la réception, le message est décrypté grâce à la clé contenu dans le décryptage du code RSA grâce a la clé privée du destinataire, pour être enfin intelligible. Et tout ça, PGP doit le fait sans grande assistance de l’utilisateur, permettant une utilisation grand public.

Pour des raisons de brevet, le logiciel PGP fut recodé par des européens, et est disponible sur http://www.pgpi.org/ .

Avec l’évolution de la puissance des ordinateurs ( loi de Moore vous connaissez ? A intervalles réguliers, la puissance doit être doublée pour deux fois moins de place … techniquement réalisable jusqu’à maintenant, mais atteindra bientôt ses limites ), il est maintenant recommandé d’utiliser des clées de 1024 voir 2048 bits, c’est à dire des nombres assez grand pour ne pas être factorisé dans un temps dit raisonnable.

Revenons à notre problématique. Les solutions qui s’offre à Bernard sont donc :

- Utiliser un algorithme à clé privé, en donnant la clé privée physiquement à Alice.
- Utiliser le système de cadenas, ou de fonction à sens unique.
- Utiliser un système à clé publique, de façon simplifier avec par exemple PGP.

( Si j’étais réellement Bernard, j’opterais pour la troisième solution … )

Maintenant, je vous propose de coder tout d’abord un équivalent du système de cadenas, puis de reproduire le système de Diffie et Hellmann.

Tout d’abord, pour notre équivalent de cadenas, voici ce que doit faire notre fonction ( résumé par ce magnifique schéma ) :

Entrée utilisateurA ( texte, cleA ) ==> réception utilisateurB ( texteA ) et renvoi ( texteA, cleB ) ==> réception utilisateurA ( texteAB ) et renvoi ( texteB ) ==> réception utilisateurB (texte ). Sauf que pour les deux utilisateurs, ça donnera Entré utilisateurA (texte) ==> sortie utilisateurB (texte).

A vos crayons, méninges, claviers, souris, barres chocolatées !

Pour ma part, je l’ai codé en python. Je passe sur les fonctions d’envoi / réception, qui n’apporte pas grand chose au code. J’utiliserais envoi(donnee) qui envoi “donnee” ( par Socket par exemple ), et reception() qui receptionne ce qui à été envoyé.
Une des difficulté de la fonction est de trouvé un algorithme capable de crypter plusieurs fois avec des clés différentes, et de ne pas dépendre du sens de décryptage ( c’est à dire donner le même résultat si on décrypte d’abord avec la clé A puis B, et si on décrypte avec B puis A ).

La fonction est donc décomposé en quatre sous fonctions ( 6 si on compte celles d’envoi/réception ) :

- crypt(texte,cle) qui va crypter texte avec la cle cle
- decrypt(texte,cle) qui inverse la fonction crypt()
- send(texte) qui est la fonction qui gère l’envoi d’un message
- receive(texte) qui est la fonction gérant l’arrivée d’un message

Pour l’algorithme, j’ai choisi de tout simplement utiliser une addition modulo 256 sur la valeur ASCII des caractères. Par exemple, la lettre A(67) crypté avec la lettre B(68) donne chr(67+68). Le protocole utilisera un système de drapeau pour reconnaitre les étapes. Ce drapeau sera en faite un 1,2 ou 3 précédant la suite de caractère. 1 indique que la suite de caractère est seulement codée avec A ( 1ère étape ), 2 indique qu’elle est codée avec AB ( 2ème étape ) et 3 indique qu’elle n’est plus que codée avec B ( dernière étape ).

A présent, le code :

def crypt(clair,cle):
    i,crypter=0,""
    while i < len(clair):
        char = (ord(clair[i]) + ord(cle[i%len(cle)]))%256
        crypter = crypter + chr(char)
        i += 1
    return crypter

def decrypt(crypter,cle):
    i,clair = 0,""
    while i < len(crypter):
        char = (ord(crypter[i]) - ord(cle[i%len(cle)]))%256
        clair = clair + chr(char)
        i += 1
    return clair

A ce niveau là, on peut déja testé si notre fonction de dépend pas de l’ordre du cryptage/décryptage :

Ordre normal :

cleA,cleB = "une","deux"
print decrypt(decrypt(crypt(crypt("Texte temoin",cleA),cleB),cleB),cleA)

Texte temoin
Ordre “anormal” :

cleA,cleB = "une","deux"
print decrypt(decrypt(crypt(crypt("Texte temoin",cleA),cleB),cleA),cleB)

Texte temoin

Bien, on peut donc maintenant implementer notre protocole, et intégrer nos deux fonctions, ce qui donne :

def send(texte,cle):
    envoi(str(1)+crypt(texte,cle))
    retour = reception()
    envoi(str(3)+decrypt(retour[1:],cle))

def receive(cle):
    donnee = reception()
    flag,texte = donnee[0],donnee[1:]
    switch flag:
        case "1":
            envoi(str(2)+crypt(texte,cle))
        case "2":
            envoi(str(3)+decrypt(texte,cle))
        case "3":
            print decrypt(texte,cle)
    else:
        print "Error : flag:",flag

Pourquoi ai-je mis l’argument “cle” dans mes fonctions send() et receive() ?

Parceque un des problème de notre fonction de cryptage, est que en connaissant une clé et le texte en clair, on connait tout de suite la deuxième clé. Et donc, vous pouvez connaitre la clé de votre correspondant dès le premier message. Ca implique donc soit une clé différente pour chaque correspondant, soit une clé générée aléatoirement pour la session . Et l’argument “cle” devient donc nécéssaire.

Et comme promis, voici maintenant le principe de l’échange de clé Diffie-Hellman-Merkle ( Oui parceque Merkle a aussi contribué ). Je préviens tout de suite, il y aura un peu de math, rien de très compliqué .

Ces trois personnes ont donc réussi à trouvé une fonction à sens unique, qui repose sur l’arithmétique du modulo. Tout d’abord, un petit rappel sur l’opération modulo, que je noterai % .

Le modulo représente le reste dans la division euclidiènne d’un nombre par un autre.

Donc 7 % 3 = 1, car 7 = 2*3 + 1. Mais là où cette fonction devient intéressante, c’est que 10 % 3 = 1 aussi !

Et donc, si vous ne connaissez que 3 et 1, vous ne pouvez pas deviner le 7, 10, 13, 4, 1, … il y en a une infinitée. Cette fonction est donc à sens unique.

Celle de DHM s’écrit Y^x % P . Voici comment se déroulerait l’obtention d’une clé :

Tout d’abord, nos amis Alice et Bernard vont se mettre d’accord sur la valeur de Y et P.

Alice choisit un nombre qu’elle garde secret, que l’on appelera A. Bernard fait de même avec un nombre B.

Alice et Bernard appliquent alors leur nombre à la fonction à sens unique.

Pour Alice, on a Y^A % P = @, et pour Bernard Y^B % P = & .

Alice et Bernard se partagent alors leurs résultats @ et &. Pour obtenir la clé, Alice va faire &^A % P, et Bernard @^B % P. Et miraculeusement, ils obtiendront la même clé.

Prenons un exemple concret. Disons que Y = 7, P = 11, A = 3 et B = 6. On a donc @ = 7^3 % 11 = 2, et & = 7^6 % 11 = 4. 3 et 4 sont donc échangé, et la clé sera donc 4^3 % 11 = 2^6 % 11 = 9 !

Comme vous le remarquerez, la clé ne peut dépasser P. Il est donc important de prendre un nombre P très grand ( l’autre opération étant une puissance, il est très probable ( et il est nécéssaire ) que Y^x soit supérieur au moins une fois à P ) .

Maintenant, que sait notre Eve ?

Et bien, elle connait Y = 7, P = 11,@=2 et &=4. Et avec ça, elle ne peut pas deviner la clé ( Ses seules informations sont que la clé est comprise entre 0 et 11, et qu’elle peut prendre toutes les valeurs que peut prendre 7^x % 11 ).

Vous pouvez vous amuser à coder une fonction utilisant ce principe, mais pour ma part je n’en posterais pas une ici, qui serait sans réel intérêt. Je vous donne la fonction pour déterminer @ et &, et celle pour déterminer ensuite la clé :

Determination de A :

def det(Y,P,A):
    return exp(Y,A) % P

Determination de la cle à partir de & :

def gen_cle(&,A,P):
    return exp(&,A) % P

C’est ainsi que se cloture cet article, un peu plus long que les autres, il y avait beaucoup à dire .

Enjoy
Ajax

HTTP Response Splitting ( Séparation de réponse HTTP )

admin — Thu, 06 Aug 2009 13:41:12 +0000

Bien le bonjour

Pour vous présenter cette technique somme toute assez méconnue, je vous propose de vous faire un min-rappel sur le protocole HTTP, ou plutôt sur ce qui se passe lorsque votre naviguateur va sur le site www.exemple.com .

Si vous entrez “http://www.exemple.com” dans votre navigateur préféré ( au hasard Internet Explorer 5 ), la requête envoyée au serveur sera la suivante ( je simplifie ici énormément la requête ):

GET / HTTP/1.1
Host: www.exemple.com

Avec les caractères de retour chariot ( \r ) et de saut de ligne ( \n ), celà donne :

GET / HTTP/1.1\r\n
Host: www.exemple.com\r\n\r\n

Maintenant, regardons une requête un peu plus complète ( demande d’affichage de la page http://localhost/http_splitting.php ) :

GET /http_splitting.php HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; fr; rv:1.9.0.3) Gecko/2008092417 Firefox/3.0.3
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: fr,fr-fr;q=0.8,en-us;q=0.5,en;q=0.3
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Keep-Alive: 300
Connection: keep-alive

Et la réponse du serveur:

HTTP/1.x 200 OK
Date: Sun, 02 Nov 2008 10:55:25 GMT
Server: Apache/2.2.9 (Win32) DAV/2 mod_ssl/2.2.9 OpenSSL/0.9.8h mod_autoindex_color PHP/5.2.6
X-Powered-By: PHP/5.2.6
Content-Length: 0
Keep-Alive: timeout=5, max=100
Connection: Keep-Alive
Content-Type: text/html

Maintenant, intéressons nous à un script de redirection. La page http_splitting.php a pour code source :

Si nous demandons la page http://localhost/http_splitting.php?page=index.php, la requête sera :

GET /http_splitting.php?page=index.php HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; fr; rv:1.9.0.3) Gecko/2008092417 Firefox/3.0.3
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: fr,fr-fr;q=0.8,en-us;q=0.5,en;q=0.3
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Keep-Alive: 300
Connection: keep-alive

Et la réponse serveur :

HTTP/1.x 302 Found
Date: Sun, 02 Nov 2008 10:59:44 GMT
Server: Apache/2.2.9 (Win32) DAV/2 mod_ssl/2.2.9 OpenSSL/0.9.8h mod_autoindex_color PHP/5.2.6
X-Powered-By: PHP/5.2.6
Location: index.php [=> Notre argument page=index.php ]
Content-Length: 0
Keep-Alive: timeout=5, max=100
Connection: Keep-Alive
Content-Type: text/html

Ce retour serveur qui conduit le naviguateur à exécuter la requête suivante :

GET /index.php HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; fr; rv:1.9.0.3) Gecko/2008092417 Firefox/3.0.3
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: fr,fr-fr;q=0.8,en-us;q=0.5,en;q=0.3
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Keep-Alive: 300
Connection: keep-alive

Bon, et maintenant, rentrons dans le vif du sujet .

Il est possible, à l’aide d’une URL “malicieuse”, disons plutôt spécialement formée, d’interféré et de modifier la réponse HTTP du serveur. Je m’explique :

Comme vous l’avez remarqué, lorsque j’appelle http_splitting.php?page=index.php , le retour serveur contient Location: index.php\r\n .

Maintenant, je vais demandé l’URL suivante :
http_splitting.php?page=%0d%0aContent-Type: text/html%0d%0aHTTP/1.1 200 OK%0d%0aContent-Type: text/html%0d%0a%0d%0a%3Chtml%3E%test%3C/html%3E
%0d = \r, %0a = \n
Cette même requête écrite plus clairement :
http_splitting.php?page=

Content-type: text/html
HTTP/1.1 200 OK
Content-Type: text/html
test

Que va-t-il se passé si l’on entre cette URL dans le naviguateur ?

La requête sera donc :

GET /http_splitting.php?page=http_splitting.php?page=%0d%0aContent-Type:%20text/html%0d%0aHTTP/1.1%20200%20OK%0d%0aContent-Type:%20text/html%0d%0a%0d%0a%3Chtml%3E%test%3C/html%3E HTTP/1.1
Host: localhost
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; fr; rv:1.9.0.3) Gecko/2008092417 Firefox/3.0.3
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Accept-Language: fr,fr-fr;q=0.8,en-us;q=0.5,en;q=0.3
Accept-Encoding: gzip,deflate
Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7
Keep-Alive: 300
Connection: keep-alive

Et la réponse serveur, qui contiendra notre retour falsifié :

HTTP/1.x 302 Found
Date: Sun, 02 Nov 2008 10:59:44 GMT
Server: Apache/2.2.9 (Win32) DAV/2 mod_ssl/2.2.9 OpenSSL/0.9.8h mod_autoindex_color PHP/5.2.6
X-Powered-By: PHP/5.2.6
Location:
Content-type: text/html

HTTP/1.1 200 OK
Content-Type: text/html

test
Content-Length: 0
Keep-Alive: timeout=5, max=100
Connection: Keep-Alive
Content-Type: text/html

Et donc, ce que nous verrons : test !

Les applications de ce principe sont multiples, car falsifié une réponse serveur permet par exemple de modifier la date de cache-control, de dernière édition de la page, d’intégré un code Javascript mesquin, …

Je ne peux que donc vous recommander de filtrer les %0d et autres %0a .

En espérant que cet article vous aura permis d’apprendre de nouvelles choses,

Bonne journey :]

(Petite)Introduction au profiling

admin — Thu, 06 Aug 2009 13:39:44 +0000

Profiquoi ? -> Profiling ! ( profilage )

Le profiling est un art permettant d’établir l’ébauche de l’identité d’une personne, à partir par exemple de ses écrits, mais aussi de ses faits et gestes, de ses fréquentations, … ( Dans la suite, nous parlerons de tout ce qui se rapporte au profiling de l’auteur d’un écrit ).

Tout d’abord, le pourquoi du profiling ?

Le profiling est utilisé par certains services comme la criminologie, afin par exemple de dresser un profil psychologique d’un criminel. Ces informations permettent d’orienter une enquête, de “trier” des suspects, de comprendre certaine chose, ou encore d’amener à en découvrir de nouvelle ( un certain profil peut indiquer un certain lieu, .. ) . Dans notre contexte, nous essairons de dresser le profil d’un auteur afin de le comparer à celui d’un autre. Celà nous permettra de savoir si tout d’abord l’auteur est bien une unique personne, son pays natal, son sexe, son niveau d’étude, …. et ensuite, en le comparant à celui d’un autre, déterminer si les deux auteurs ont des chances de n’être qu’un(e) .

“Ont des chances”, car en effet, le profiling est une science inexacte, mais qui repose néanmoins sur des études pertinentes, d’ordre social, psychologique,…

Pour donner des chiffres, les chances d’obtenir un profil completement juste sont d’environ 16% ( ce qui, vous en conviendrez, est très faible ). Néanmoins, les risques de confrontations de deux auteurs ( c’est à dire affirmer que deux textes d’auteurs différents, sont en fait écrit par une entitée unique ) sont de 0.24% ( inférieure à 1%, d’où l’intérêt de l’utilisation de cette méthode ).

Maintenant, comment se passe concrètement l’analyse d’un profil :

Tout d’abord, il faut acquérir le plus de documents de l’auteur, être certains qu’ils sont bien de lui. Ces documents devront aussi être les plus longs possibles ( difficile de mener une analyse pertinente sur un texte de 300 mots … ) . En général, pour un WebUser, on choisira des sources comme les blogs / forums / sites perso en général, lieu de grandes ressources.

Le profiling peut désormais débuter. Il va se dérouler en 5 étapes, qui sont les suivantes :

- Détermination du Sexe

- Analyse du “lexique mental”

- Statistiques vocabulaires, et mots/groupe de mot importants

- Analyse de la ponctuation

- Analyse de la longueur des phrases

Détermination du Sexe : Un homme et une femme utilisent des mots différents, et avec des fréquences différentes. L’analyse de la fréquence de ces mots “cible” conclut sur un genre masculin, féminin, ou un égalitée. La précision de cette méthode est de l’ordre de 60/70% . Cette méthode permet aussi de déterminer le pays d’origine de l’auteur. En effet, pour un texte écrit en anglais, la méthode sera plutôt précise pour un Americain, mais indiquera en général une égalité pour un Européen ( et donc un britannique pure souche ). Ces mêmes “scores” permettent aussi de différencier deux personnes : une personne indiqué pour mâle à 62% sera surement différente d’une indiquée à 88%.
Analyse du “lexique mental” : Le lexique mental représente tous les mots connus par une personne. Un mot qui n’a jamais été entendu ne sera jamais utilisé, et un mot qui n’est pas employé dans son contexte légitime indique une méconnaissance de son sens. Cette méthode permet de comparer une langue maternel d’une langue apprise lors d’études, avec une précision supérieure à 80% . Cela peut aussi entrainer une distinction de niveaux d’études. En français, l’utilisation de mots comme “épars;ecclésiastique;dot;encens;solennité;scélérat;baïonnette;funérailles;précipitamment;…” dans leur contexte exact indiquera que la personne jouit surement d’un niveau d’étude respectable.
- Statistiques vocabulaires, et mots/groupe de mot importants : Certain mots et certaines expressions sont plus répétées que d’autres, suivant généralement le lieu d’origine et le parcours d’étude. Il n’est pas difficile en lisant un texte français de savoir si la personne vient d’un milieu “rural” ou plutôt d’un milieu “urbain”. En Amérique, deux personnes provenant du même état ont des statistiques vocabulaires voisines de l’ordre de 40% .
Analyse de la ponctuation : Il y a tellement de manière d’aérer son texte … L’analyse de la fréquence d’apparition des caractères comme , ; ! ? ( ) ” ‘ et l’écart entre ces derniers ( en particuliers les virgules ) est une approche très distinctive, c’est à dire qu’affirmer que deux résultats d’analyse de ponctuation différents proviennent d’un même auteur est quasiment à coup sur faux. Vous remarquerez, très cher lecteur, que j’ai tendance personnellement à utiliser beaucoup de virgule, sans être excessif ( du moins j’essaye ).
Analyse de la longueur des phrases : En plus de l’analyse de la fréquence des signes de ponctuations, l’analyse de la longueur des phrases est très instructive. Pour me reprendre en exemple, j’ai tendance à écrire des phrases de 20 à 30 mots ( phrases donc assez longues ). Cette analyse permet surtout de déterminer si deux auteurs distincts ont écrits deux articles distincts ( et non l’inverse : deux articles distincts provenant du même auteur => haut niveau de faux positif ).

Le manque de documentation ( surtout francophone ) sur ce sujet m’oblige malheuresement à terminer mon article ici. Je vous invite à lire la comparaison entre n3td3v et Gobbles Security réalisée par Hacker Factor ( english ). L’auteur dresse d’abord le profil de n3td3v, qui s’avère être en faite 3 personnes distinctes, puis dresse celui de Gobbles Security, tout en le comparant à ses premiers résultats.

Même s’il ne conclut pas, et même si le profiling est somme toute une science assez subjective, son risque d’erreur s’il affirmait que Gobbles Security et n3td3v désigne un unique groupe, serait de l’ordre de 1 pour 100 000 000 ( sans commentaire ).

Si vous avez de la documentation sur le sujet, surtout, n’hésitez pas, je suis preneur .

Sur ceux, il se fait tard, et à moins d’avoir envie de comparer un texte écrit par quelqu’un de sobre et réveillé à celui de quelqu’un dans mon état actuel …. eh bien Bonne nuit

Le protocole UpNp, sa presentation et ses problemes

admin — Thu, 06 Aug 2009 13:38:24 +0000

Nous allons nous interesser dans cet article au protocole UpNp .
Je vous propose tout d’abord l’introduction que nous donne Wikipedia :
L’Universal Plug and Play (UPnP) est un protocole réseau promulgué par l’UPnP Forum.
Le but de l’UPnP est de permettre à des périphériques de se connecter aisément et de simplifier l’implémentation de réseaux à la maison (partages de fichiers, communications, divertissements) ou dans les entreprises. UPnP le permet en définissant et en publiant les protocoles de commande UPnP au-dessus des standards de communication de l’Internet.

Plus clairement, lorsque vous connectez une imprimante, votre Box, etc…, ces produits, etant compatible UpNp, vont tenter de s’auto-configurer ( autant dire qu’ils y arrivent la plupart du temps :] ).
Ces produits doivent respecter des spécifications normalisées, mais peuvent contenir d’autres fonctions supplémentaires, relatives au produit ( une Box qui pourra activer son Wifi via UpNp.. ).
L’établissement d’une connection UpNp se déroule en plusieurs étapes :
-L’obtention d’une adresse IP lorsque l’équipement est connecté sur le réseaux
-Le produit va ensuite avertir les autres équipements sur le réseaux de sa présence via une requête NOTIFY. Cette requete contient un champ LOCATION, indiquant le chemin du fichier XML listant les services.
-Envoi de l’adresse du fichier de configuration ( XML )
-Controle du produit

Les équipements ou logiciels présent sur le réseaux peuvent aussi chercher à obtenir l’adresse d’un service, via une requete M-SEARCH.
Malheuresement, ce beau protocole ne contient absolument aucune sécurité…

Je m’explique : Il est possible de completement reconfigurer un service, un équipement du réseaux utilisant UpNp sans AUCUN mot de passe !

Nous allons dans la suite prendre l’exemple d’une NeufBox, version FirmWare : NB4-R1.5.6-MAIN
L’ip de cet équipement est sur le réseaux 192.168.1.1 . Cette même adresse propose une interface d’administration sur le port 80, nécéssitant cependant un couple login/password. ( par défaut : admin / clé WPA ).
Pour obtenir l’adresse de son fichier de configuration, et des services paramétrables, nous allons envoyer une requete M-SEARCH, et écouté la réponse NOTIFY de la NeufBox .
L’envoi de ce paquet peut se faire via NMAP, mais nous préfererons “UpNpScan” qui est un petit logiciel executant très bien son travail :

>UPnPScan.exe -t 192.168.1.1
UPnP Discovery Tool v0.4 by patrik@cqure.net
--------------------------------------------
[192.168.1.1]
HTTP/1.1 200 OK
CACHE-CONTROL: max-age=1800
DATE: Sat, 11 Oct 2008 16:30:02 GMT
EXT:
LOCATION: http://192.168.1.1:49152/gatedesc.xml
SERVER: Linux/2.6.8.1, UPnP/1.0, Portable SDK for UPnP devices/1.4.1
X-User-Agent: redsonic
ST: upnp:rootdevice
USN: uuid:75802409-bccb-40e7-8e6c-fa095ecce13e::upnp:rootdevice

—

Maintenant que nous avons l’adresse du fichier de configuration, analysons-le.
En plus de l’adresse du fabricant, de la version, du site du fabricant et du nom du modele, nous avons trois :


-

urn:schemas-dummy-com:service:Dummy:1
urn:dummy-com:serviceId:dummy1
/dummy
/dummy
/dummy.xml



-

-

urn:schemas-upnp-org:service:WANCommonInterfaceConfig:1

urn:upnp-org:serviceId:WANCommonIFC1
/upnp/control/WANCommonIFC1
/upnp/control/WANCommonIFC1
/gateicfgSCPD.xml



-

urn:schemas-upnp-org:service:WANIPConnection:1
urn:upnp-org:serviceId:WANIPConn1
/upnp/control/WANIPConn1
/upnp/control/WANIPConn1
/gateconnSCPD.xml

Le premier fichier ( dummy.xml ) ne nous donne rien d’interessant.
La lecture du second ( /gateicfgSCPD.xml ) nous indique qu’il permet de configurer tout ce qui est en rapport avec le cablage.
En revanche, lors de la lecture du troisième , l’”action-List” proposé est alléchante :
AddPortMapping , GetExternalIPAddress , …

Oui, vous avez bien vu, notre NeufBox nous offre bien gentiment la possibilité d’ajouter une redirection de port NAT !
Pour un particulier, la redirection des ports 139,435 permettra d’avoir accès à son dossier publique, …
Le fichier livré par la balise permettra ces modifications.
En effet, le paramétrage UpNp se fait par requete HTTP/SOAP . Elle sera de la forme :
POST (url de controle) HTTP/1.0
Un champ Host constitué de l’adresse ip et du service UpNp, un champ Content-type spécifiant l’utilisation de XML, et un champ SOAPACTION qui contient l’action à réalisé sur l’équipement cible.
Le contenu du POST(XML), le tout dans une enveloppe SOAP.

Cette attaque peut bien entendu etre facilement automatisée, et il est aussi aisé de la combiné avec une attaque de type CSRF ( via FLash par exemple ), afin de pouvoir completement reconfigurer les équipements réseaux d’un visiteur lambda par la simple vue d’une page web.
L’exemple montrait ici la possibilité de rajouter des redirections NAT, mais il faut savoir que certains routeurs proposeront par exemple le changement de serveur DNS ( => Pharming ), modification des identifiants réseaux, obtention de la clé Wifi, ajout d’adresse d’autorisation pour l’adresse MAC, activation de service HotSpot, …

Il est donc très clair que pour un particulier, ce protocole se révèle certe pratique, mais surtout dangereux.
Reconfigurer des équipements à l’échelle d’une entreprise de manière automatique est bien plus fastidieux, mais il subsiste un risque.

En espérant que cet article vous aura fait acquérir quelques nouvelles connaissances,
Bonne soirée

PS: Pour plus d’informations, d’exemples, je vous recommande l’article de XMCO Partners ( Actu sécu n°20 ). Je ne propose d’ailleurs qu’un autre exemple que celui proposé par cet article.

Cryptanalyse d’un texte chiffré par l’algorithme de Viginère

admin — Thu, 06 Aug 2009 13:37:09 +0000

Comme la dernière fois, je vous propose une approche par l’exemple. A vous d’essayer de déchiffré ce qui suit :

IYVLS LZKIW KHMMX ZLHHE ONEEX UNBSX JYVPO AHXGV KMXTB KMXRD KAXRO XUEIW KHMWY AMEEP ULFIN AHFSD UOWYX KJAVK YYISE XJHYF UCKGR OZYVO XHHXB KNXBD KUVLK WOXGK XUVXO XYGSE YOMMV OMHRC AHXPO ZNKIN KFTGV KJHYB KZYIM ZOXVV GMNFC ZCMYD OIGIF OXXQW KHMTV AMEEM RYLIB GFHRQ AYXXF GLBIO KNFMO AREID KRMIC KLTGR OZYVO OFYEE ZMTZY OLJYS RSTIE AHXTO XCHHO UOWIC VULWK MYLIX ZCXVC JOOVO YFBXD KLTMB KMXXK OYGXE ZCEMC KMISE XWAMP LLXVV KMIPE YAKEX JMLIM XYMWV KMWIE DWHVB KMISX JUGXC TUOES KHMTV AMJYK GPHMB KHEIE XMFES TMNRO DYFTV GCKIN AGXQO RCOVO VINVC GMLYB KLWIV GVHRX KWHQZ XYAIX YCHRN KMFIC YUZIC

On ne connais bien entendu pas la clé, le but étant de la retrouvé, ainsi que le texte en clair.

Si le mot cle est BAD et que le mot à chiffré est COOL, on a :
DORM
On remarquera que les deux “O” ne sont pas chiffré de la même façon, d’où la force du chiffre de Viginère. C’est ainsi qu’il a été indéchiffrable jusqu’au XIXème siècle.

La méthode de cryptanalyse repose en deux étapes :
Tout d’abord, nous allons essayer de déterminer la taille de la clé.
Pour celà, il est possible d’utiliser deux méthodes : L’indice de coïncidence ( test de Friedman ) ainsi que l’analyse de la distance entre deux chaines semblables. Nous utiliserons cette dernière.
Elle repose sur le principe que même si une lettre est codée différement à chaque fois, elle sera néanmoins répétée plusieurs fois de la même manière.
Par exemple dans notre texte, “BKMX” est répété, et l’écart entre les deux chaines est de 275 caractères.
Ce qui veut dire que soit la chaine fait 1 caractères, soit un multiple de 275. Il y a aussi une infime probabilité pour que le BKMX code pour une autre chaine, et que sa répétition n’est que pure coïncidence. Evidemment, avec une chaine de 4 caractères, cette probabilitée est très faible, pour ne pas dire nulle.
Nous allons donc cherché toutes les chaines de 4 caractères qui se répète, et faire le PGCD de leurs intervalles.
La liste ci-dessous représente les différentes intervalles entre deux même chaines :
50, 50, 190, 140, 145, 145, 145, 145, 275, 245, 45, 195, 195, 195, 195
Le mot clé a donc une taille qui est un multiple de tout ces nombres, c’est à dire 5 ou 1.
Si le mot clé avait pour taille 1, nous aurions eu affaire à un simple Chiffre de César, ce qui n’est pas le cas.
En utilisant l’indice de coïncidence, nous obtenons le même résultat, mais la technique n’est pas détaillée ici.
Maintenant que nous savons que notre clé fait 5 caractères, nous allons pouvoir réunir les caractères chiffrés avec le même alphabet.
En ne prenant que le début du texte, on peut dire que :
I,L,K sont chiffrés avec le premier alphabet décalé
Y,Z,H le sont avec le deuxième, etc..
Ainsi, nous obtenons cinq chaines de caractères, toutes chiffrées avec un alphabet décalé, ou encore un Chiffre de César.
Pour pouvoir trouver chaque décalage, nous allons procédé à une analyse fréquentielle de chacune.
Pour le premier décalage, et donc la première lettre du mot clé, nous allons procédé à une analyse fréquentielle de :
ILKZOUJAKKKXKAUAUKYXUOXKKWXXYOAZKKKZGZOOKARGAGKAKKOOZORAXUVMZJYKKOZKXLKYJXKDKJTKAGKXTDGARVGKGKXYKY
Ce qui nous donne les fréquences suivantes (en %):
A 10.204081632653061
B 0
C 0
D 2.0408163265306123
E 0
F 0
G 7.142857142857143
H 0
I 1.0204081632653061
J 4.081632653061225
K 26.53061224489796
L 2.0408163265306123
M 1.0204081632653061
N 0
O 9.183673469387756
P 0
Q 0
R 3.061224489795918
S 0
T 2.0408163265306123
U 5.1020408163265305
V 2.0408163265306123
W 1.0204081632653061
X 10.204081632653061
Y 6.122448979591836
Z 7.142857142857143
On remarque que la lettre K est la lettre la plus fréquente, que les trois fréquences L,M et N sont très faibles, celle de O forte puis de nouveau deux fréquences très faible. Si l’on décalle la lettre K pour qu’elle devienne E, ces statistiques de fréquence correspondent avec celle de la langue française. On en déduit donc que pour la première lettre, on a affaire a un décalage de E vers K, c’est à dire de A vers G.
La première lettre du mot clé est donc G.
De la même façon, nous pouvons déterminer les 4 autres lettres. Il est important de ne pas seulement prendre la lettre la plus forte comme étant un E, mais de bien regarder la suite de lettre.
Nous obtenons donc la clé GUTEK, et le message en clair :
CECHI FFREM ENTIN TRODU ITLAN OTION DECLE UNECL
ESEPR ESENT EGENE RALEM ENTSO USLAF ORMED UNMOT
OUDUN EPHRA SEPOU RPOUV OIRCH IFFRE RNOTR ETEXT
EACHA QUECA RACTE RENOU SUTIL ISONS UNELE TTRED
ELACL EPOUR EFFEC TUERL ASUBS TITUT IONEV IDEMM
ENTPL USLAC LESER ALONG UEETV ARIEE ETMIE UXLET
EXTES ERACH IFFRE ILFAU TSAVO IRQUI LYAEU UNEPE
RIODE OUDES PASSA GESEN TIERS DUVRE SLITT ERAIR
ESETA IENTU TILIS ESPOU RCHIF FRERL ESPLU SGRAN
DSSEC RETSL ESDEU XCORR ESPON DANTS NAVAI ENTPL
USQUA AVOIR ENLEU RSMAI NSUNE XEMPL AIRED UMEME
LIVRE POURS ASSUR ERDEL ABONN ECOMP REHEN SIOND
ESMES SAGES
Ou encore :
Ce chiffrement introduit la notion de clé. Une clé se présente généralement sous la forme d’un mot ou d’une phrase. Pour pouvoir chiffrer notre texte, à chaque caractère nous utilisons une lettre de la clé pour effectuer la substitution. Évidemment, plus la clé sera longue et variée et mieux le texte sera chiffré. Il faut savoir qu’il y a eu une période où des passages entiers d’œuvres littéraires étaient utilisés pour chiffrer les plus grands secrets. Les deux correspondants n’avaient plus qu’à avoir en leurs mains un exemplaire du même livre pour s’assurer de la bonne compréhension des messages. ( Présentation du chiffre de viginère de Wikipédia )

On peut attribuer cette découverte à Charles Babbage, même s’il ne l’a pas publier.Cette technique porte donc le nom de Friedrich Wilhelm Kasiski, ayant fait cette même découverte un peu plus tard ( et l’ayant publié dans “Ecriture secrète, et art du déchiffrement” ).

Remarque : Une autre méthode peut être employé, appelée “mot probable”. En effet, imaginons que notre texte contient le mot “que”. Nous imaginons alors qu’il ne contient seulement le mot “que”. Ainsi, nous obtenons une clé. Prenons un deuxième texte, chiffré avec la même clé, et appliquons notre clé temporaire. Si nous ne nous sommes pas trompé, il est probable que certaine partie du texte ressortent, nous permettant de deviné une partie de la clé. Voilà pourquoi il est déconseillé de toujours utilisé la même clé, et de préféré un système de clé jetable.

Encore une fois, je vous conseille de vous faire des petits outils qui vous aideront dans votre analyse.

On pourra par exemple utiliser un utilitaire pour essayer de trouver la longueur de la clé ( en cherchant l’espace entre les mêmes chaines, et puis un PGCD de tout ça ) :

inter,i,all,num,texte = input("Intervalle : "),0,{},[],""
def pgcd(a,b):
    while a<>b:
        if a 1 :
        if all.has_key(chaine) :
            num.append(i - all[chaine])
        else :
            all[chaine] = i

    i+=1
print pgcdl(num)

Bonne journée à tous !