Arithmétique modulaire

Discussion dans 'Bibliothèque Wladbladi' créé par titegazelle, 4 Janvier 2013.

  1. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113


    Arithmétique modulaire


    En mathématiques et plus précisément en théorie algébrique des nombres, l’arithmétique modulaire est un ensemble de méthodes permettant la résolution de problèmes sur les nombres entiers. Ces méthodes dérivent de l’étude du reste obtenu par une division euclidienne.

    L'idée de base de l'arithmétique modulaire est de travailler non sur les nombres eux-mêmes, mais sur les restes de leur division par quelque chose. Quand on fait par exemple une preuve par neuf à l'école primaire, on effectue un peu d'arithmétique modulaire sans le savoir : le diviseur est alors la valeur 9.


    Si ses origines remontent à l’Antiquité, les historiens associent généralement sa naissance à l’année 1801, date de la publication du livre Disquisitiones arithmeticae de Carl Friedrich Gauss. Sa nouvelle approche permet d’élucider de célèbres conjectures et simplifie les démonstrations d’importants résultats par une plus grande abstraction. Si le domaine naturel de ces méthodes est la théorie des nombres, les conséquences des idées de Gauss se retrouvent dans d’autres champs des mathématiques, comme l’algèbre ou la géométrie.


    Le XX[SUP]e[/SUP] siècle modifie le statut de l’arithmétique modulaire. D’une part, d’autres méthodes sont nécessaires pour progresser en théorie des nombres. D’autre part, le développement de nombreuses applications industrielles impose la mise au point d’algorithmes issus des techniques modulaires. Ils résolvent essentiellement des questions soulevées par la théorie de l’information, une branche maintenant surtout considérée comme appartenant aux mathématiques appliquées.


    Usages

    En mathématiques pures, ce terme est très peu utilisé. Le vocable proche le plus fréquent est théorie algébrique des nombres, qui désigne un domaine plus large, contenant par exemple les notions d'entiers algébriques et de théorie de Galois.

    En mathématiques appliquées, cette expression est d'un usage fréquent pour décrire les bases mathématiques de différents domaines de la théorie de l'information : cryptologie, théorie des codes et informatique. De nombreux outils et algorithmes entrent dans ce champ d'étude. On y trouve les tests de primalités, la décomposition en produit de facteurs premiers, l'utilisation des caractères d'un groupe par exemple pour la transformée de Fourier discrète ou encore l'étude d'autres quotients que ceux des entiers, comme celui des polynômes.


    Selon les différents auteurs et le domaine d'application, ces extensions sont considérées, soit comme une partie intégrante de l'arithmétique modulaire, soit comme des applications, voire ne sont pas citées du tout. Sous sa forme simple, elle prend parfois le nom d'arithmétique de l'horloge. Le terme de système modulaire est utilisé pour désigner une arithmétique modulaire sur d'autres ensembles que les entiers.

    Histoire

    Au III[SUP]e[/SUP] siècle av. J.-C., Euclide formalise, dans son livre les Éléments, les fondements de l'arithmétique. On y trouve le lemme portant son nom, une version datée du théorème fondamental de l'arithmétique et une étude sur les nombres parfaits dans la proposition 36 de son livre IX. Diophante d'Alexandrie (env. 250) écrit Arithmetica contenant 130 équations. Il traite essentiellement de problèmes ayant une unique solution numérique et à valeur fractionnaire ou entière. On y trouve le fait que les nombres sommes de deux carrés parfaits ne sont jamais de la forme 4n + 3. Les équations, à coefficients entiers et dont les solutions recherchées sont entières prennent aujourd'hui le nom d'équations diophantiennes.

    La Chine développe parallèlement une arithmétique modulaire. Sun Zi écrit vers l'an 300 un traité de mathématiques dont le problème 26 du chapitre 3 est le suivant : «Soient des objets dont on ignore le nombre. En les comptant 3 par 3 il en reste 2, en les comptant 5 par 5, il en reste 3 et en les comptant 7 par 7, il en reste 2. Combien y a-t-il d'objets ?».
    Qin Jiushao (1202 - 1261) développe le théorème des restes chinois. Son traité est remarquablement avancé, il traite d'un système d'équations linéaires de congruences dans le cas où les moduli ne sont pas premiers entre eux deux à deux. Ses travaux sur les systèmes de congruences dépassent en sophistication ceux de Leonhard Euler. On peut citer George Sarton pour qui : «Qin Jiushao était l'un des plus grands mathématiciens de race chinoise, de son temps et à vrai dire de tous les temps».


    Le XIV[SUP]e[/SUP] siècle voit un déclin progressif puis un oubli de ces résultats, le savoir de Qin Jiushao ne dépasse pas les frontières chinoises avant le XX[SUP]e[/SUP] siècle. Il est redécouvert par les travaux de l'historien des sciences Joseph Needham. En revanche, de nombreuses similarités entre les notations arabes et chinoises laissent penser à des contacts durant les périodes précédentes.

    L'Inde possède aussi une tradition forte en arithmétique. Âryabhata (476 - 550) recherche de manière systématique les solutions entières de l'équation linéaire à deux inconnues à coefficients entiers. Il utilise pour cela un algorithme appelé «Kuttaka» publié dans son livre appelé Âryabhatîya. Les équations diophantiennes de degré deux sont étudiées par Brahmagupta (598 - 668) à l'aide de la méthode chakravala.

    La civilisation islamique joue un double rôle en arithmétique : elle véhicule le savoir acquis par les Grecs, Indiens, Chinois et Européens, et elle apporte des connaissances nouvelles notamment sur l'étude des propriétés de certains ensembles d'entiers, comme les nombres premiers, parfaits, amicaux ou figurés. Dans ce contexte, Qusta ibn Lûqâ réalise une traduction partielle de l'Arithmetica de Diophante d'Alexandrie à la fin du IX[SUP]e[/SUP] siècle et Al-Hajjaj traduit à la même époque les Éléments d'Euclide ; son collègue al-Khuwārizmī (env. 783 - env. 850) écrit un livre sur la numération indienne. Si le livre est perdu, il reste connu par une traduction latine Algoritmi de numero Indorum. Thābit ibn Qurra (836 - 901) étudie les nombres amicaux et les nombres parfaits. Alhazen (965 - 1039) continue ses travaux sur les nombres parfaits et découvre le théorème de Wilson.

    - Apparition en Europe

    En 1621, Claude-Gaspard Bachet de Méziriac traduit le livre de Diophante en latin. Les questions soulevées intéressent les mathématiciens de l'époque. Pierre de Fermat propose un grand nombre d'énoncés, les trois plus célèbres étant probablement son grand théorème, son théorème des deux carrés et son petit théorème. La communauté scientifique se lance des défis sur ce sujet, ainsi Fermat demande : un nombre carré qui, ajouté à la somme de ses parties aliquotes (i.e. ses diviseurs), fasse un cube.» Il conclut par : «j'attends la solution de ces questions ; si elle n'est fournie ni par l'Angleterre, ni par la Gaule Belgique ou Celtique, elle le sera par la Narbonnaise». Marin Mersenne recherche des nombres premiers particuliers. Fermat lui écrit : «Si je puis une fois tenir la raison fondamentale que 3, 5, 7, 17, 257, 65537, …, sont nombres premiers, il me semble que je trouverai de très belles choses en cette matière, car j'ai déjà trouvé des choses merveilleuses dont je vous ferai part». Ces nombres sont maintenant appelés nombres de Fermat et sa phrase s'avère être l'unique conjecture fausse proposée par l'auteur. René Descartes recherche sans y parvenir, à démontrer que si la division par huit d'un nombre premier donne pour reste un ou trois, il s'écrit de la forme x[SUP]2[/SUP] + 2y[SUP]2.
    [/SUP]
    Sur ce type de problèmes, deux éléments sont remarquables :
    Les équations diophantiennes fascinent, le titre d'un des livres de Bachet de Méziriac est évocateur : Problèmes plaisants et délectables qui se font par les nombres, on peut citer encore la remarque de Fermat à propos de son grand théorème : «J'ai trouvé une solution merveilleuse … »

    Les problèmes posés sont difficiles. Malgré quelques succès comme l'identité de Bézout probablement due à Bachet de Méziriac, l'essentiel des questions restent sans réponse, comme le théorème des deux carrés de Fermat, ou avec des réponses pour le moins peu convaincantes, comme celle de Fermat pour son grand théorème : « … mais la place me manque ici pour la développer» (la première preuve reconnue apparaîtra en 1995). Bien souvent, Fermat termine ses théorèmes par des commentaires avouant son échec : «Je vous avoue tout net (car par avance je vous avertis que je ne suis pas capable de m'attribuer plus que je ne sais, je dis avec la même franchise ce que je ne sais pas) que je n'ai pu encore démontrer … cette belle proposition que je vous ai envoyée … »

    - Méthodes utilisées

    Le siècle suivant voit la résolution de certaines de ces questions, souvent par Leonhard Euler : il contredit Fermat en démontrant que ses nombres ne sont pas toujours premiers, et prouve le théorème des deux carrés. Il commet aussi des erreurs, sa tentative de démonstration du grand théorème de Fermat pour n égal à trois est un échec, sa première démonstration s'avère fausse. Il soulève d'autres questions comme la loi de réciprocité quadratique en 1782. Là encore, et malgré une tentative d'Adrien-Marie Legendre, la solution reste hors de portée.

    Jusqu'à l'aube du XIX[SUP]e[/SUP] siècle les méthodes utilisées, si elles dénotent une grande astuce chez les mathématiciens, sont finalement peu nombreuses et de principes simples. L'exemple suivant, tiré du problème des deux carrés, en illustre trois : existe-t-il un nombre dont la division par quatre donne pour reste 3 et qui est somme de deux carrés ? Soit a[SUP]2[/SUP] et b[SUP]2[/SUP] ces deux carrés. Seul l'un est pair car sinon leur somme serait paire et sa division par 4 aurait 0 comme reste. Supposons a pair et b impair. a est pair donc son carré est un multiple de 4. L'entier b est impair donc s'écrit 2c + 1, son carré est égal à 4c[SUP]2[/SUP] + 4c + 1, la division de b[SUP]2[/SUP] par quatre donne pour reste un et la somme des deux carrés donne aussi pour reste un.

    • Le premier outil utilisé est celui des nombres premiers, ce raisonnement est exact car 2 est un nombre premier.
    • Le deuxième est la transformation algébrique, b est transformé en 2c + 1. Utilisé avec virtuosité, il permet aux mathématiciens de l'époque de résoudre certaines équations diophantiennes. Toute l'astuce réside à choisir avec habileté les bonnes transformations.
    • Le troisième est la division euclidienne, les carrés et leur somme sont systématiquement divisés par 4.
    • Le quatrième n'est pas illustré dans l'exemple, il correspond à la descente infinie utilisée dans la démonstration d'Euler du théorème des deux carrés. Elle consiste à trouver à partir d'une solution entière positive une autre solution entière positive et plus petite. La suite des solutions descend de manière infinie dans l'ensemble des entiers positifs, ce qui n'est pas possible. Cette méthode fut déjà utilisée par Fermat pour démontrer son grand théorème dans le cas où n est égal à 4.
    Le caractère rustique des outils se traduit par des démonstrations longues et techniques, comme par exemple la preuve d'Euler pour le théorème des deux carrés. De plus, et malgré plus d'un siècle d'efforts, l'essentiel des équations diophantiennes résistent à une telle approche.

    - L'apport de Carl Friedrich Gauss

    À l'âge de 17 ans, Gauss démontre la loi de réciprocité quadratique. Un an plus tard, le 30 mars 1796, il prend conscience que ses calculs arithmétiques permettent de construire à la règle et au compas l'heptadécagone, c'est-à-dire le polygone régulier à dix-sept côtés, problème resté ouvert depuis l'Antiquité. Enfin en 1801, il publie Disquisitiones arithmeticae (Recherches arithmétiques) et est surnommé le prince des mathématiciens.

    Ces deux grandes découvertes procèdent d'une même démarche, la mise au point d'outils plus sophistiqués que ceux dont disposaient Fermat ou Euler, simplifiant les démonstrations au prix d'une abstraction plus grande. Sa démarche fonde l'arithmétique modulaire.

    Elle est appliquée d'abord aux entiers puis aux polynômes puis à un nouvel ensemble d'entiers, maintenant appelés entiers de Gauss. Johann Peter Gustav Lejeune Dirichlet découvre un ensemble analogue, celui des entiers de Dirichlet. Il lui permet d'initier la preuve du théorème de Fermat pour n = 5 qu'il envoie à l'Académie des sciences en 1825. Elle est analysée par Legendre qui met quelques mois pour la mener à bonne fin.

    Toutes les équations diophantiennes de Fermat sont maintenant résolues à l'exception de son grand théorème. De nouvelles conjectures apparaissent. Par exemple, si a et b sont premiers entre eux, la suite arithmétique de valeur initiale a et de raison b contient-elle des nombres premiers, si oui combien ? Gauss et d'autres mathématiciens comme Legendre ont bien imaginé qu'il en existe une infinité mais ne parviennent pas à le démontrer. De même la loi de réciprocité quadratique doit posséder des équivalents pour les ordres supérieurs.

    L'arithmétique modulaire est enrichie. Dirichlet, un élève de Gauss trouve une démonstration du théorème de la progression arithmétique en développant le concept des caractères et en formalisant les bases de la théorie analytique des nombres. Son raisonnement est un joyau de l'arithmétique modulaire, Charles Gustave Jacob Jacobi écrit, dans une lettre à son frère : «En appliquant les séries de Fourier à la théorie des nombres, Dirichlet a récemment trouvé des résultats atteignant les sommets de la perspicacité humaine.» Dirichlet n'est pas le premier à utiliser des outils qui sont maintenant qualifiés de conséquence de l'analyse harmonique sur un groupe abélien fini. Legendre pour tenter de démontrer la loi de réciprocité quadratique développa des calculs similaires sur les réels, formalisant ce qui est maintenant appelé le symbole de Legendre. Gauss enfin généralise cette approche aux nombres complexes dans son livre de 1801. Ses calculs portent le nom de somme de Gauss et période de Gauss.

    Au XIX[SUP]e[/SUP] siècle, ces mathématiques sont dénommées arithmétique transcendante. Si le terme d'arithmétique reste largement usité, Legendre considère, en 1830, cette branche comme suffisamment développée pour mériter le terme de théorie des nombres. L'apparition de nouvelles techniques, différentes de celles de Gauss, introduit une subdivision avec la théorie algébrique des nombres et la théorie analytique des nombres. Le terme d'arithmétique transcendante tombe ensuite en désuétude avec l'apparition des nombres transcendants.

    - XX
    [SUP]e[/SUP] siècle

    . Cryptologie
    Ce domaine quitte celui des mathématiques pures. En revanche, une application industrielle fait, au cours du temps, de plus en plus appel aux notions mathématiques développées par Gauss : la science des codes secrets appelée cryptologie. En 1883, Auguste Kerckhoffs énonce que : «la sécurité d'un système de cryptographie ne doit pas reposer sur le secret de l'algorithme. La sécurité ne repose que sur le secret de la clé». Cette approche est à l'origine d'une modification profonde de cette science. Au milieu du XX[SUP]e[/SUP] siècle, elle devient une branche des mathématiques appliquées.

    Au début des années 1930, le bureau du chiffre polonais fait appel au mathématicien Marian Rejewski pour percer le code du système Enigma, utilisé par les Allemands. Les anciens codes, comme le chiffre de César, sont réinterprétés comme une transformation mathématique dans l'ensemble des moduli de Gauss sur les nombres entiers. Le terme d'«arithmétique modulaire» est utilisé pour décrire ces techniques. Durant les années 1970, Horst Feistel développe un système à clé privée, le Data Encryption Standard ou DES, qui devient le standard des applications non classifiées. Les cryptanalystes du DES, et plus généralement des chiffrements symétriques, utiliseront des mathématiques issues des travaux de Dirichlet sur les caractères, dans le cadre d'un espace vectoriel sur un corps fini à deux éléments.


    [​IMG]
    Enigma, une machine de chiffrement utilisée durant la Seconde Guerre mondiale,
    décrypté par un mathématicien : Marian Rejewski.

    This article or image contains materials that originally
    came from a National Security Agency (NSA) website or publication.
    It is believed that this information is not classified, and is in the public domain
    Ce fichier et sa description proviennent de Wikimedia Commons
    _________________________________________________________

    En 1976 une nouvelle famille de codes est découverte, fondée sur une clé publique. Des solutions industrielles sont rapidement développées, la plus célèbre est dénommée R.S.A.. Elle se fonde sur les travaux de Fermat et d'Euler. Le terme «arithmétique modulaire» est, dans ce contexte, utilisé pour décrire non seulement la structure des moduli sur les entiers, mais aussi les théorèmes traitant des nombres premiers comme la décomposition en produit de facteurs premiers, le théorème chinois, le petit théorème de Fermat et sa généralisation par Euler.

    L'arithmétique modulaire est un domaine de recherche actif au début du XXI[SUP]e[/SUP] siècle. Une mise en œuvre efficace nécessite l'utilisation d'opérations sur des grands ensembles de moduli. L'approche de Gauss est utilisée sur des polynômes à coefficients dans un corps fini. L'arithmétique modulaire se généralise à d'autres ensembles que les quotients d'entiers, par exemple pour la cryptanalyse.

    .
    Théorie de l'information

    La cryptographie n'est pas l'unique domaine utilisant le vocable «arithmétique modulaire». La fin de la Seconde Guerre mondiale voit l'apparition d'une nouvelle science : la théorie de l'information. En 1948, sous l'impulsion de Claude Shannon, elle devient une branche des mathématiques appliquées.

    Si la confidentialité est l'un des sujets abordés, la fiabilité est aussi un thème majeur. Richard Hamming propose un premier algorithme dès 1950. Une fois encore, les moduli sur les entiers sont utilisés pour une des plus simples techniques de code : les sommes de contrôle. En 1960, de nouveaux codes plus puissants sont développés, sur la base de polynômes à coefficients dans un corps fini. L'arithmétique utilisée prend souvent le nom de «modulaire».

    Un Processeur Pentium contenant une unité arithmétique et logique
    fondée sur l'arithmétique modulaire.


    [​IMG]
    Description : Pentium P-MMX
    Date : 01/09/2007
    Source : Sergei Frolov, Soviet Calculators Collection, http://www.leningrad.su/museum/main.php?lang=0
    Auteur : Sergei Frolov imported from Wikipedia english by Jean-Luc W 19:39, 1 September 2007 (UTC)
    "Moi, propriétaire du copyright de cette œuvre, la place dans le domaine public.
    Ceci s'applique dans le monde entier. Dans certains pays, ceci peut ne pas être possible ;
    dans ce cas : J'accorde à toute personne le droit d'utiliser cette œuvre dans n'importe quel but,
    sans aucune condition, sauf celles requises par la loi."

    Ce fichier et sa description proviennent de Wikimedia Commons.

    _________________________


    L'informatique devient un sujet universitaire au début des années 1960. Les contraintes inhérentes à la structure des processeurs imposent la représentation des nombres sous forme d'une suite finie d'informations, justifiant l'utilisation des moduli. Le terme d'«arithmétique modulaire» apparaît souvent, on y trouve même les entiers de Gauss ou les polynômes, par exemple, pour des calculs sur des grands entiers.

    Les techniques développées pour la cryptographie, la théorie des codes et l'arithmétique informatique reposent sur les mêmes concepts, offrant une relative unité aux mathématiques de la théorie de l'information.
     
  2. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113
    Arithmétique modulaire
    ______________________________________________________________



    Outils de l'arithmétique modulaire

    - Congruences sur les entiers

    L'exemple historique de l'«arithmétique modulaire» repose sur les nombres entiers. Un entier n étant fixé, le calcul modulo n consiste à identifier tous les entiers à leur reste dans la division euclidienne par n ; ceci peut être illustré par l'exemple de l'« arithmétique de l'horloge », qui correspond à n=12 : la petite aiguille se trouve dans la même position à deux moments éloignés de douze heures, on identifie par exemple 13 h à 1 h. Pour obtenir un calcul sur un tel ensemble, on vérifie que l'addition et la multiplication sont compatibles avec les identifications. Cette formalisation est l'œuvre de Legendre, qui donne le nom de résidu aux différents éléments.

    L'apport de Gauss consiste à analyser la structure de cet ensemble, maintenant qualifié du nom d'anneau de congruences et noté Z/nZ. Elle se divise en premier lieu en l'étude de l'addition, qui définit un groupe cyclique de générateur 1 ; puis de la multiplication, qui dépend des propriétés du modulo. Si celui-ci est premier, on obtient un corps. Cette approche simplifie les démonstrations arithmétiques. Les deux exemples historiques du livre Disquisitiones arithmeticae sont le théorème de Wilson et le petit théorème de Fermat.

    Le calcul modulaire, dans le cas où le modulo n'est pas premier, est plus complexe, mais le théorème des restes chinois permet d'en élucider la structure. L'anneau n'est alors pas intègre et il existe des diviseurs de zéro, ce sont des nombres qui, multipliés par un certain autre nombre non nul, donnent zéro. Le nombre d'éléments inversibles est donné par la fonction indicatrice d'Euler. Elle permet, par exemple, de généraliser le petit théorème de Fermat.

    - Résidus et polynômes

    Gauss remarque que l'ensemble des polynômes à coefficients rationnels peut se voir appliquer la logique du calcul modulaire, puisqu'il dispose d'une addition, d'une multiplication, et d'une division euclidienne. Les congruences sont les restes de la division euclidienne des polynômes par un polynôme donné.

    Il applique cette approche au polynôme X[SUP]n[/SUP] - 1 et trouve sa décomposition en produit de facteurs irréductibles, qui prennent le nom de polynôme cyclotomique. Gauss utilise ces résultats pour trouver une construction à la règle et au compas de l'heptadécagone, polygone régulier à 17 côtés.


    Il hésite à considérer ces travaux comme de l'arithmétique ; il écrit : «La théorie de la division du cercle, ou des polygones réguliers, …, n'appartient pas par elle même à l'Arithmétique, mais ses principes ne peuvent être puisés que dans l'Arithmétique transcendante». Le terme d'arithmétique « transcendante » de Gauss est maintenant remplacé par celui d'arithmétique «modulaire».La logique de cet argument est toujours d'actualité.

    - Entiers algébriques

    Le cas des polynômes à coefficients entiers diffère : la propriété de division ne fonctionne que pour des polynômes dont le plus grand coefficient est égal à plus ou moins un. Le cas des moduli du polynôme X[SUP]2[/SUP] + 1 est envisagé : la structure modulaire obtenue est encore celle d'un anneau, s'identifiant à l'ensemble des nombres de la forme α + i.β où α et β sont des entiers et i désigne le nombre imaginaire, correspondant au monôme X. Cet ensemble est celui des entiers de Gauss.

    Il peut être muni d'une norme. À l'entier de Gauss a = α + i.β est associée la norme α[SUP]2[/SUP] + β[SUP]2[/SUP], qui provient du module des nombres complexes. Cette norme permet de définir une division euclidienne, comme l'illustre la figure de droite. Les entiers sont représentés par les intersections du quadrillage. La valeur a/b existe si b est différent de zéro, cependant cette valeur n'est pas nécessairement un entier de Gauss. Elle est représentée par le point noir de la figure. Dire qu'une division euclidienne existe, revient à dire qu'il existe un entier de Gauss à une norme strictement inférieure à un de ce point noir. L'illustration montre que, dans le cas présent, il existe au moins trois candidats. Dans le cas général, il en existe entre un et quatre et dans ce contexte seule l'existence compte.

    Ce résultat de division euclidienne implique des propriétés sur cet anneau d'entiers : l'identité de Bézout, l'existence de nombres premiers de Gauss et un analogue du théorème fondamental de l'arithmétique. Ces nombres premiers permettent à Richard Dedekind de proposer une résolution simple du théorème des deux carrés. L'illustration géométrique est donnée sur la figure de gauche. Un nombre premier p s'exprime comme somme de deux carrés si le cercle de rayon la racine de p croise au moins un entier Gauss.

    Gotthold Eisenstein, qui rencontre Gauss en 1844, découvre un nouvel anneau d'entiers ; l'arithmétique sur cet anneau offre une démonstration rigoureuse du grand théorème de Fermat pour n égal à trois, justifiant, encore une fois, la nécessité théorique d'une telle généralisation de l'arithmétique modulaire.

    - Caractères de Dirichlet

    Dirichlet s'intéresse aux nombres premiers de la forme n + λ.mn et m sont deux entiers premiers entre eux et λ une variable qui décrit l'ensemble des entiers positifs. Il souhaite en effet démontrer qu'il existe une infinité de nombres premiers de cette nature.
    L'arithmétique modulaire est un bon outil pour cette problématique, qui est équivalente à trouver le cardinal de l'ensemble des nombres premiers dans une classe de modulo.

    Dirichlet considère le groupe des éléments inversibles modulo m, et étudie l'ensemble des fonctions du groupe dans les nombres complexes non nuls qui vérifient, si a et b sont deux résidus : f(a.b) = f(a).f(b). De telles fonctions sont appelées caractères de Dirichlet. Il en existe φ(n), le produit de deux caractères est encore un caractère, et leur table de multiplication est exactement la même que celle du groupe des unités étudié.

    Les calculs sur ces fonctions sont formellement analogues à ceux réalisés précédemment par Joseph Fourier. Il faut néanmoins atteindre le XX[SUP]e[/SUP] siècle pour voir apparaître une théorie unifiant les deux approches. Elle prend le nom d'analyse harmonique.


    Développements théoriques


    Il est fréquent que des concepts mathématiques, développés dans un contexte, soient réutilisés dans d'autres domaines. Ainsi la théorie des groupes s'applique à l'arithmétique et à la géométrie. Il en est de même pour les outils de l'arithmétique modulaire, dont les outils alimentent de vastes champs des mathématiques pures, comme l'algèbre générale ou la théorie de Galois. Ces théories ne sont néanmoins pas considérées comme des cas particuliers d'arithmétique modulaire car elles font aussi appel à de nombreux autres concepts.

    - Structures quotient

    En langage moderne, l'arithmétique modulaire se formalise par la notion de quotient d'anneaux euclidiens. Le concept de relation d'équivalence permet de généraliser ce concept aux principales structures algébriques. Par exemple, le quotient d'un groupe par un sous-groupe normal est, à travers le théorème de Jordan-Hölder, un outil de base de la classification des groupes finis. Les groupes quotients sont aussi utilisés en topologie algébrique pour classifier les variétés. Dans la théorie des anneaux, la notion d'idéal joue un rôle analogue à celui de la notion de sous-groupe normal en théorie des groupes. Elle permet de construire des anneaux quotients dans un contexte plus général que celui de l'arithmétique modulaire. Le théorème des zéros de Hilbert, base du lien entre l'algèbre commutative et la géométrie algébrique, s'exprime en termes d'idéal.

    Les termes de congruence et de modulo sont néanmoins réservés aux quotients sur un anneau euclidien.
    - Résidus de polynômes et théorie de Galois
    L'arithmétique modulaire s'applique à l'anneau des polynômes à coefficients dans un corps commutatif, car cette structure dispose d'une division. Elle est le point de départ de la théorie d'Évariste Galois et consiste en l'étude systématique des ensembles de congruence de polynômes modulo un polynôme irréductible, l'équivalent des nombres premiers. Ces ensembles sont maintenant appelés extensions algébriques.

    Ces extensions permettent l'analyse de la résolubilité des équations algébriques, c'est-à-dire des équations s'écrivant sous forme polynomiale. Si le polynôme est irréductible, son ensemble de congruences est le plus petit corps contenant au moins une racine. Il est appelé corps de rupture. En réitérant ce processus, un corps contenant toutes les racines, le corps de décomposition, est construit. La logique modulaire du quotient fournit la structure algébrique adaptée à cette problématique.

    La théorie de Galois fait appel à bien d'autres notions. L'étude de la résolubilité de l'équation est possible via l'étude du groupe des automorphismes du corps, appelé groupe de Galois, grâce à la correspondance de Galois entre sous-corps et sous-groupes. Au-delà de l'étude de la résolubilité des équations algébriques, la théorie de Galois est devenue un cadre naturel de résolution de nombreux problèmes en arithmétique, géométrie arithmétique ou géométrie algébrique, et permet surtout de formuler de nouveaux problèmes plus généraux dans ces divers domaines.

    Si cette théorie utilise le concept de quotient d'un anneau euclidien, la variété d'outils spécifiques à ce domaine en fait un champ propre, bien distinct du sujet de cet article. L'un des fruits de cette théorie, les corps finis, encore appelés corps de Galois, fournissent un cadre naturel à de nombreuses applications en arithmétique modulaire.

    - Entiers algébriques et théorie algébrique des nombres
    L'arithmétique modulaire offre un bon cadre conceptuel pour la résolution du grand théorème de Fermat. Cependant, si n est plus grand que dix, les anneaux d'entiers algébriques, construits selon la méthode de Gauss, présentent ce que Dirichlet appelle une obstruction. Il montre que le groupe des unités de cet anneau, c'est-à-dire des éléments ayant un inverse pour la multiplication, n'est plus un groupe cyclique ou abélien fini comme celui qu'étudiait Gauss. Il contient aussi des copies de l'anneau des entiers et est donc infini. Ce résultat prend le nom de théorème des unités de Dirichlet. L'obstruction provient de cette nouvelle configuration. Elle empêche l'application des techniques modulaires utilisées pour les entiers de Gauss car l'anneau associé n'est plus euclidien.

    Ernst Kummer utilise un outil lié à la généralisation du quotient maintenant formalisé par les idéaux. Ils remplacent les nombres premiers absents. La théorie algébrique des nombres prend alors le relais, avec des techniques différentes. L'outil de base est un anneau dont les éléments sont appelés entiers algébriques et qui possède une structure dite d'anneau de Dedekind. Kummer parvient ainsi à démontrer le grand théorème pour certaines valeurs de n premier, c'est-à-dire pour les nombres premiers réguliers. Les seules valeurs inférieures à 100 non traitées sont 37, 59 et 67.

    D'autres outils et objets d'étude apparaissent, comme l'anneau adélique, ceux de la théorie de Galois, les courbes elliptiques, les séries L de Dirichlet ou les formes modulaires. Certains proviennent de conséquences presque directes de l'arithmétique modulaire, comme les corps finis, utilisés de manière intensive au XX[SUP]e[/SUP] siècle. La théorie algébrique des nombres est largement plus vaste que le cadre de l'arithmétique modulaire, tout en reposant in fine sur des techniques parfois similaires.


    - Caractères de Dirichlet et théorie analytique des nombres
    La découverte par Euler d'un produit infini, construit à l'aide de nombres premiers et égal au sixième du carré de la surface d'un cercle de rayon un, ouvre la voie à une approche différente pour la compréhension des nombres. Dirichlet l'utilise pour démontrer que chacun des moduli d'entiers du groupe des unités contient une infinité de nombres premiers. Ce résultat porte maintenant le nom de théorème de la progression arithmétique.

    Pour mener à bien sa démonstration, Dirichlet développe un outil spécifique, les séries L de Dirichlet. L'une de ses séries correspond à une célèbre fonction qui prendra le nom de ζ (zêta) de Riemann. Sa plus grande difficulté consiste à prouver que ses fonctions n'ont pas de racine au point un. Pour y parvenir, il utilise l'analyse harmonique sur le groupe des unités d'une classe de modulo.

    Néanmoins, une fois encore, l'arithmétique modulaire est insuffisante pour venir à bout du théorème. Dirichlet utilise de nombreuses techniques analytiques, comme les séries entières et l'analyse complexe. Le fruit de ces travaux donne naissance à une nouvelle branche des mathématiques : la théorie analytique des nombres. L'un des points cruciaux de cette théorie provient de l'unique article de Bernhard Riemann en théorie des nombres : Sur le nombre de nombres premiers inférieurs à une taille donnée. Il conjecture une localisation des racines de sa fonction ζ. La recherche de la position des racines, initiée par Dirichlet, devient une préoccupation centrale et reste l'une des conjectures pressenties comme les plus difficiles des mathématiques de notre époque.

     
  3. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113
    Arithmétique modulaire
    ______________________________________________________________




    Cryptographie


    L'objet de la cryptographie est d'assurer sécurité dans la transmission des messages. La confidentialité ainsi que l'authentification de ceux-ci sont deux exemples du sens donné au terme sécurité. On peut citer deux exemples : la protection des messages qu'utilise une armée pour empêcher une anticipation de l'ennemi, ou la carte bleue proposée par le système bancaire, offrant à un usager une bonne sécurité.

    En termes plus mathématiques, l'opération de chiffrement se traduit par un algorithme, c'est-à-dire une fonction f qui, à un message en clair m et une clé k, associe un message chiffré f (k, m). La connaissance du message chiffré et de l'algorithme doit être insuffisante pour reconstituer le message en clair sans une clé de déchiffrement. Dans le cas de la cryptographie traditionnelle, dite cryptographie symétrique, la clé de déchiffrement est identique à la clé de chiffrement ou s'en déduit aisément. Cette clé doit alors rester secrète.

    La cryptographie asymétrique s'appuie sur le constat que seule la clé de déchiffrement doit rester secrète, et connue du seul récepteur du message. Elle n'a pas besoin d'être communiquée à ses correspondants. Alice utilise la clé de chiffrement de Bob, que celui-ci a rendu publique, pour lui envoyer un message. Seul Bob peut le déchiffrer, même Alice, si jamais elle avait perdu le message en clair, en serait incapable. Bob doit répondre en utilisant la clé de chiffrement d'Alice.

    L'objectif est donc de définir une fonction simple à évaluer mais difficile à inverser sans la connaissance d'un secret. L'arithmétique modulaire a été la première à offrir des solutions, et elle est toujours à la base de beaucoup de solutions commerciales. Par exemple l'échange de clés Diffie-Hellman, premier exemple historique, exploite la difficulté pratique à inverser l'exponentiation modulaire. Cette dernière, ou ses généralisations à d'autres groupes, reste fondamentale dans le domaine.

    La cryptographie asymétrique résout en particulier le délicat problème de la distribution des clés en cryptographie symétrique. Si plusieurs correspondants communiquent, en cryptographie symétrique, une clé différente s'avère nécessaire pour chaque couple d'intervenants, alors qu'en cryptographie asymétrique chaque correspondant dispose d'une clef qu'il garde secrète, et d'une clef qu'il rend publique. Cependant elle n'a pas fait disparaître les codes symétriques, qui offrent des algorithmes beaucoup plus efficaces. Pour une sécurité équivalente, les codes symétriques présentent l'avantage de nécessiter des clés nettement plus petites, 128 bits pour la version courante de AES, contre plus d'un millier pour le RSA, mais surtout le chiffrement comme le déchiffrement sont de cent à mille fois plus rapide. Les systèmes cryptographiques modernes, comme ceux utilisés par les cartes bancaires, ou le protocole de communication cryptée SSL/TLS très utilisé sur Internet, n'utilisent qu'en début de communication la cryptographie asymétrique, pour échanger les clés d'un chiffrement symétrique qui prendra ensuite le relais.

    - Cryptographie asymétrique

    Le code RSA est un exemple largement répandu de cryptographie asymétrique. Le chiffrement utilise deux clés, une clé publique pour le chiffrement, et une clé privée, pour le déchiffrement. La force d'un tel système réside dans le fait que la connaissance de la clé publique ne permet pas le décryptage. Il se décrit de la manière suivante :

    Alice (le choix des prénoms est traditionnel) souhaite pouvoir recevoir des messages de Bob sans qu'Ève puisse les déchiffrer. Alice choisit deux grands nombres premiers p et q, dont elle calcule le produit n=pq, et un entier e, premier avec φ(n) = (p - 1)(q - 1), et strictement inférieur à ce nombre ; la fonction indicatrice d'Euler φ, donne l'ordre du groupe des éléments inversibles de Z/nZ. Le couple (n,e) constitue alors la clef publique d'Alice, c'est-à-dire qu'elle peut être librement accessible, en particulier à Bob qui doit tout de même pouvoir s'assurer que cette clef est bien celle d'Alice.


    Parallèlement Alice calcule l'inverse de e modulo n, soit un entier d strictement inférieur à n vérifiant

    [​IMG]

    ce qui se fait de façon efficace par l'|algorithme d'Euclide étendu connaissant p et q, donc φ(n). L'entier d constitue la clef privée d'Alice. On montre que la connaissance de d permet de retrouver la factorisation de n de façon efficace, le calcul de d et la factorisation de n sont donc calculatoirement équivalents.

    Les messages sont des entiers strictement inférieurs à n, que l'on voit comme des éléments de l'anneau Z/nZ. Si Bob souhaite transmettre le message m à Alice, il transmet la valeur de m[SUP]e[/SUP] modulo n. Alice a rendu au préalable publiques les valeurs de n = pq, e et donc la fonction f de chiffrement, qui est ici égale à :

    [​IMG]

    Ève peut connaître e, n et donc f, ces informations sont en effet publiques. En revanche, elle ne peut intercepter les valeurs de p et q qui n'ont jamais été communiquées.

    Pour Bob, la fonction de codage est aisée : il s'agit d'une exponentiation modulaire qui se calcule de façon efficace. Pour Alice la lecture l'est aussi pour les mêmes raisons. En effet le théorème d'Euler montre que :
    [​IMG]

    En revanche Ève ne connaît pas a priori les entiers p et q. Si n est grand (et si les entiers p et q sont bien choisis) il n'existe pas, à ce jour, d'algorithme assez efficace pour la factorisation de n. Plus généralement on ne connait pas de façon efficace de résoudre le problème RSA, qui est celui d'inverser la fonction de chiffrement (dont on ne sait pas s'il est ou non plus facile à résoudre que le problème de la factorisation de n).

    - Cryptographie symétrique
    La cryptographie asymétrique n'existerait pas sans les méthodes issues de l'arithmétique modulaire. Celle-ci ne joue pas le même rôle fondateur en cryptographie symétrique, mais n'en est pas absente pour autant. Les chiffrements symétriques se divisent en deux grandes familles dont l'une, les chiffrements par flot, utilise souvent comme composant de base les suites récurrentes linéaires sur un corps fini ; l'autre, celle des chiffrements par bloc, comprend entre autres le DES et son successeur, le standard de chiffrement avancé, appelé couramment AES (pour Advanced Encryption Standard). Ces derniers opèrent sur des blocs de données d'une taille fixe comptée en octets, huit pour le DES par exemple. Une suite d'opérations primitives assez simples est appliquée de façon répétée pour coder un bloc. Un octet, ou plus généralement un bloc de n bits, peut être vu comme les coefficients d'un polynôme sur les entiers modulos deux, de degré maximal n-1. Cela a conduit les cryptologues à s'intéresser à certaines opérations sur les corps finis de caractéristique 2. Ainsi il s'avère que l'opération d'inversion sur le corps fini F[SUB]2[/SUB][SUP]n[/SUP], composée avec une transformation affine, a de bonnes propriétés cryptographiques pour en faire l'une des primitives des chiffrements par bloc. Ceci a été exploité par les auteurs du chiffrement Rijndael, qui est devenu l'AES. La publication officielle de ce dernier par le NIST (agence fédérale américaine) contient d'ailleurs quelques préliminaires mathématiques sur le sujet. Cependant il n'est nul besoin d'algorithmique sur l'arithmétique ou les corps finis pour l'implémentation : ces opérations sont représentées par des tables, comme les opérations analogues du DES obtenues elles de façon beaucoup plus heuristique. Certains cryptologues ont vu une faiblesse potentielle dans la caractérisation trop algébrique de Rijndael, qui le rendrait plus accessible à l'imagination des mathématiciens, ce qui n'a pas empêché son adoption pour l'AES.

    - Tests de primalité
    Les codes RSA utilisent comme clés les nombres premiers p et q du paragraphe précédent. L'usage, pour les trouver, consiste à choisir un nombre presque au hasard, de tester s'il est premier ou non et de recommencer s'il ne l'est pas.

    Le crible d'Ératosthène est une méthode rapide pour les petits nombres. Utilisé habilement, 46 tests suffisent pour vérifier la primalité d'un nombre inférieur à 39000. En revanche, il est inefficace pour une application industrielle employant des nombres qui s'écrivent avec plusieurs centaines de chiffres.

    La majorité des tests de l'industrie se fondent sur des variantes du petit théorème de Fermat. Si un nombre p est premier, alors pour tout entier a, a[SUP]p[/SUP] est congru à a modulo p. La réciproque est fausse : il existe des nombres non premiers, appelés nombres de Carmichaël (par exemple 561 = 3 · 11 · 17), pour lesquels la congruence est vraie pour toute valeur de a. Toutefois, si p n'est ni un nombre de Carmichaël, ni un nombre premier, la congruence est fausse pour au moins la moitié des valeurs de a comprises entre un et p. Que la congruence soit vérifiée pour un grand nombre de valeurs de a indique une très forte probabilité de primalité pour p, s'il n'est pas un nombre de Carmichaël.

    Le test de primalité de Solovay-Strassen et surtout le test de primalité de Miller-Rabin sont deux exemples largement utilisés. Ils se fondent sur une analyse plus poussée du petit théorème de Fermat et n'admettent pas d'analogues aux nombres de Carmichaël, ce qui lève l'un des problèmes du test de Fermat. Pour ces deux méthodes, un test de primalité déterministe consiste à vérifier la propriété pour un nombre de valeurs de a garantissant une preuve irréfutable. Le nombre de calculs à effectuer étant rédhibitoire, on se contente d'un test probabiliste. Il consiste à vérifier la congruence sur un ensemble de valeurs de a, choisi pour assurer une probabilité de primalité supérieure à une valeur donnée, souvent égale à 1 - (1/2)[SUP]100[/SUP].

    - Décomposition en produit de facteurs premiers
    La sécurité par l'obscurité n'est pas de mise pour les codes RSA. Il est important de connaître précisément l'état de l'art de la décomposition des entiers en termes de facteurs premiers. Un concours appelé compétition de factorisation RSA fut ouvert jusqu'en mai 2007, proposant un prix pour quiconque capable de factoriser un nombre choisi dans une liste rendue publique.

    Le crible d'Ératosthène est un test de primalité qui offre une méthode de décomposition. Mais une fois encore, il n'est pas applicable pour de grands nombres car trop lent.
    Les différentes méthodes actuellement utilisées reposent souvent sur les résidus quadratiques. Un diviseur de zéro est un résidu quadratique contenant comme représentants au moins deux carrés parfaits. L'objectif est de trouver ces deux carrés. Cette approche est celle du crible quadratique et de l'algorithme de factorisation par crible sur les corps de nombres généralisé, le plus rapide connu en 2007. On peut encore citer l'algorithme ρ de Pollard qui utilise le paradoxe des anniversaires.

    - Corps finis
    La construction par quotient des corps premiers Z/pZ se généralisent à d'autres structures. En informatique, les nombres sont codés sur n bits, c'est-à-dire qu'un nombre correspond à une suite de longueur n composée de 0 et de 1. Une telle suite peut être considérée comme un vecteur d'un espace vectoriel de dimension n sur le corps fini F[SUB]2[/SUB] à deux éléments.

    Cette structure est souvent considérée comme l'espace des polynômes à coefficients dans F[SUB]2[/SUB] de degré strictement inférieur à n. Pour garantir la stabilité de la multiplication, cet espace est quotienté par un polynôme de degré n. Quand ce polynôme est irréductible (équivalent de nombre premier), la structure obtenue est le corps fini de cardinal 2[SUP]n[/SUP]. Un nombre a modulo 2[SUP]n[/SUP] et un polynôme P modulo un polynôme de degré n sont très semblables, ils s'écrivent en effet :

    [​IMG]

    Un exemple d'utilisation est la création d'un générateur de nombres pseudo-aléatoires dans F[SUB]2[/SUB]. De tels générateurs sont utilisés par exemple, dans le contexte d'une communication orale par téléphone portable, par le chiffrement de flux A5/1. Celui-ci a pour composants des registres à décalage à rétroaction linéaire, ou LFSR (acronyme de linear feedback shift register). Étant données deux suites finies d'éléments de F[SUB]2[/SUB] de longueur n, une suite de coefficients et une séquence d'initialisation, soient :


    [​IMG] et [​IMG]

    Un LFSR fournit une suite pseudo-aléatoire (u[SUB]j[/SUB]), obtenue par récurrence linéaire :

    [​IMG]

    La suite des coefficients est souvent fixe. La clé fournit alors la séquence d'initialisation, qui peut être
    représentée par un entier a modulo 2[SUP]n[/SUP] :

    [​IMG]

    La suite obtenue est périodique, cependant si la suite des coefficients est bien choisie, la période est très longue : 2[SUP]n[/SUP] - 1. Cette situation se produit si le polynôme de rétroaction R, donnée par la formule suivante, est le polynôme minimal d'un élément primitif du groupe cyclique F[SUB]2[/SUB][SUP]n*[/SUP].
    [​IMG]

    - Analyse harmonique sur un groupe abélien fini
    Les idées de Dirichlet s'appliquent sur le système modulaire du paragraphe précédent. Pour l'addition, l'espace vectoriel V précédent est un groupe abélien fini. Les caractères de ce groupe forment une base orthonormale de l'ensemble des fonctions de V dans celui des nombres complexes. Il est à noter que l'ensemble d'arrivée choisi n'est pas toujours celui des complexes mais parfois le corps F[SUB]2[/SUB]. Les résultats sont strictement identiques. Une telle structure dispose d'une analyse harmonique. Si l'ensemble d'arrivée est choisi égal à F[SUB]2[/SUB] la transformée de Fourier prend le nom de transformée de Walsh. Cette approche est utilisée à la fois pour les systèmes DES, RSA et certains chiffrements de flux.

    Un registre à décalage à rétroaction linéaire est trop aisément déchiffrable. Pour un registre de longueur n, même si la suite engendrée est de période 2[SUP]n[/SUP] - 1, l'algorithme de Berlekamp-Massey permet de déterminer celle-ci grâce la connaissance de 2n valeurs consécutives, avec une complexité quadratique. Ainsi, si la clé est composée de 128 bits, il suffit de 128 × 128 · k = 16 384 · k étapes pour le décrypter, où k est suffisamment «petit» pour que cela représente une sécurité insuffisante. La solution adoptée consiste à utiliser plusieurs registres à décalage. Les différents résultats sont vus comme un élément d'un nouvel espace vectoriel sur F[SUB]2[/SUB]. Une fonction booléenne associe à chaque élément de cet espace la valeur un ou zéro. Si une telle fonction est bien choisie, le meilleur algorithme de déchiffrement connu demande de l'ordre de 2[SUP]n[/SUP] étapes pour trouver le signal apportant la confusion. La détermination de cette fonction est obtenue à l'aide des outils de l'analyse harmonique.

    Pour un code RSA et à la fin du XX[SUP]e[/SUP] siècle, la clé est souvent un nombre dépassant 10[SUP]308[/SUP]. Il est important de disposer d'une multiplication rapide sur les grands moduli. La technique consiste à identifier les moduli aux polynômes sur un corps fini. La multiplication de deux polynômes de degré n est une opération qui, si elle est réalisée de manière naïve, impose une complexité quadratique. Les caractères du groupe additif associés étant orthogonaux, la complexité devient linéaire si une telle base est utilisée. Un calcul plus rapide consiste à réaliser une transformée de Fourier rapide, à multiplier les deux résultats et à opérer la transformée de Fourier inverse. La complexité totale est alors en n log(n) où log désigne ici le logarithme de base deux.



     
  4. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113
    Arithmétique modulaire
    ______________________________________________________________




    Codes correcteurs


    Un code correcteur n'a pas la vocation d'assurer la sécurité, mais la fiabilité de la transmission d'un message. Il permet de restituer le texte original même si une perturbation aléatoire et modérée se produit durant la transmission. Le message encodé est transmis sous une forme appelée mot du code. Il contient non seulement les informations du message initial mais aussi les redondances permettant la validation d'une bonne communication et parfois la correction automatique d'éventuelles erreurs.

    Un mot du code est composée d'une famille de n lettres choisies dans un alphabet, en général binaire. Le cas industriel le plus fréquent est celui du code linéaire, la valeur n est constante pour chaque mot du code et est appelée dimension du code. L'ensemble des mots du code est muni d'une structure d'espace vectoriel de dimension n.

    Les codes linéaires utilisent essentiellement l'arithmétique modulaire comme base mathématique. Beaucoup enrichissent la structure d'espace vectoriel par celle d'un anneau de polynômes sur un corps fini. Ce corps est parfois le corps binaire, souvent un corps de cardinal une puissance de deux. On parle alors de code cyclique.

    Les codes linéaires sont largement présents dans l'industrie. La télécommunication les utilise pour le téléphone portable ou internet, l'informatique pour notamment la communication entre la mémoire et de processeur, l'audio-visuel pour les disques compacts ou d'autres formats de même nature comme les DVD.


    - Somme de contrôle
    Une somme de contrôle est un code linéaire particulièrement utilisé. Il correspond à un code correcteur dont seule la détection est automatisable, la correction est obtenue par une demande de répétition du message.

    Au message initial est ajoutée une information codée sur une lettre. La lettre est choisie de telle manière à ce que la congruence de la somme des lettres du mot du code soit égale à une valeur donnée, souvent zéro. Dans l'exemple illustré sur la figure de droite, le message initial est composé de deux lettres, un mot du code en contient trois, si le message initial est 00, le mot du code transmis est 000, si le message est 01, le mot du code devient 011. Les quatre mots possibles du code sont illustrés par les points verts de la figure.

    Si une unique erreur se produit, sur n'importe laquelle des trois lettres du mot du code, le message reçu correspond à un point noir. Le récepteur sait qu'il doit demander le renouvellement de la transmission. Cette configuration est analogue quelle que soit la longueur du mot du code. Une longueur égale à huit est souvent choisie, elle permet la transmission d'un message de sept lettres. Le résultat est identique, chaque mot licite du code ne possède pour voisin que des mots hors du code, une unique erreur durant la transmission est ainsi détectée. En revanche une double anomalie est systématiquement passée sous silence.


    - Codes cycliques
    Il existe certaines situations où la demande de répétition n'est pas possible, par exemple pour un DVD, lorsqu'une poussière masque une information. Il est nécessaire d'imaginer des codes correcteurs qui, non seulement détectent, mais corrigent automatiquement les erreurs.

    La méthode utilisée consiste à éloigner les mots du code à une distance suffisante pour repérer le bon message d'origine. La distance entre deux points correspond au nombre de lettres à modifier pour passer de l'un à l'autre. Le graphique de gauche illustre cette situation. Les points verts correspondent aux mots du code, par définition sans erreur. Les bleus sont ceux obtenus lorsqu'une unique lettre est altérée dans la transmission et les rouges quand deux lettres sont modifiées. Dans le schéma, on remarque que chaque point bleu contient un unique point vert à une distance de un et à chaque point rouge correspond un unique point vert situé à une distance de deux. Si une ou deux erreurs se sont produites, l'unique point vert le plus proche correspond nécessairement au message initial. Un tel code est capable de protéger jusqu'à deux erreurs.

    L'arithmétique modulaire fournit des solutions optimales pour construire la géométrie d'un code linéaire correcteur. Comme un espace vectoriel ne constitue pas une structure suffisante pour définir des moduli, il est enrichi d'une structure d'anneau de polynômes quotienté par X[SUP]n[/SUP] - 1, où n désigne la dimension de l'espace vectoriel. Dans cet espace de modulo, le monôme X[SUP]n[/SUP] est identifié au polynôme constant un. Si la chaîne (a[SUB]0[/SUB], a[SUB]1[/SUB], …, a[SUB]n[/SUB]) est un mot du code, alors il en est de même de la suivante : (a[SUB]n[/SUB], a[SUB]0[/SUB], a[SUB]1[/SUB], …, a[SUB]n-1[/SUB]). On parle pour cette raison de code cyclique. La logique est la même que celle d'un code correcteur, à la différence près que la congruence est définie non pas sur un entier mais sur un polynôme cyclotomique à coefficients dans un corps fini.

    L'exemple le plus simple correspond au code de Hamming dont les messages à transmettre comportent quatre lettres et trois lettres supplémentaires décrivent les redondances.


    Le contexte d'un code linéaire est analogue à celui de la cryptographie, on y trouve aussi des espaces vectoriels de dimension n sur un corps fini et un système de modulo de polynômes, le polynôme choisi étant souvent : X[SUP]n[/SUP] + 1. Les caractères du groupe sont utilisés, ainsi que l'analyse harmonique associée.
    L'identité de MacWilliams est un exemple archétypal. Elle permet la détermination du polynôme énumérateur des poids du code dual ou encore l'étude des caractéristiques du code de Hamming. Elle est obtenue grâce à l'analyse harmonique, à l'aide d'un produit de convolution.


    _______________________

    Nom de la page : Arithmétique modulaire
    Contenu soumis à la licence CC-BY-SA 3.0.
    Source : Article Arithmétique modulaire de Wikipédia en français (auteurs)

    sous licence Creative Commons paternité partage à l’identique
    [​IMG] Cet article est reconnu comme «article de qualité»
    depuis sa version du 20 octobre 2007 (comparer avec la version actuelle).
    Pour toute information complémentaire,
    consulter sa page de discussion et le vote l’ayant promu.

    _______________________



     
  5. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113
    Arithmétique modulaire
    _________________________________________________________________________


    Théorie de l'information

    La théorie de l'information, sans précision, est le nom usuel désignant la théorie de l'information de Shannon, qui est une théorie probabiliste permettant de quantifier le contenu moyen en information d'un ensemble de messages, dont le codage informatique satisfait une distribution statistique précise. Ce domaine trouve son origine scientifique avec Claude Shannon qui en est le père fondateur avec son article A Mathematical Theory of Communications publié en 1948.

    Parmi les branches importantes de la théorie de l'information de Shannon, on peut citer :


    Dans un sens plus général, une théorie de l'information est une théorie visant à quantifier et qualifier la notion de contenu en information présent dans un ensemble de données. À ce titre, il existe une autre théorie de l'information : la théorie algorithmique de l'information, créée par Kolmogorov, Solomonov et Chaitin au début des années 1960.

    L'information selon Shannon, un concept de la physique mathématique


    L'information est un concept physique nouveau qui a surgi dans un champ technologique. Le concept théorique d'information a été introduit à partir de recherches théoriques sur les systèmes de télécommunication. L'origine de ces recherches remonte aux études entreprises dès la fin du XIX[SUP]e[/SUP] siècle, en physique et en mathématique par Boltzmann et Markov sur la notion de probabilité d'un événement et les possibilités de mesure de cette probabilité. Plus récemment, avant la Seconde Guerre mondiale, les contributions les plus importantes sont dues à la collaboration des mathématiciens et des ingénieurs des télécommunications, qui ont été amenés à envisager les propriétés théoriques de tout système de signaux utilisé par les êtres, vivants ou techniques, à des fins de communication.

    À la suite des travaux de Hartley (1928), Shannon détermine l'information comme grandeur observable et mesurable (1948), et celle-ci devient la poutre maîtresse de la théorie de la communication qu'il élabore avec Warren Weaver.

    Cette théorie est née de préoccupations techniques pratiques. La société Bell cherche à transmettre les messages de la façon à la fois la plus économique et la plus fiable. Aussi le cadre originel de la théorie est celui d'un système de communications où un émetteur transmet un message à un récepteur à travers un canal matériel/énergétique donné. Émetteur et récepteur ont par hypothèse un répertoire commun, un code qui contient les catégories de signaux utilisables. Ainsi le message codé est transmis, de l'émetteur au récepteur à travers le canal, sous forme de signes ou signaux portés par de la matière/énergie.

    Ainsi, le concept d'information a été l'objet d'une théorie, appelée « théorie de l'information ». C'était une théorie mathématique appliquée aux techniques de la télécommunication. Elle a été élaborée plus spécialement par Claude Shannon, ingénieur à la Compagnie des Téléphones Bell et reste jusqu'à nos jours la base du concept dit scientifique d'information.

    Cependant cette définition mathématique de l'information ne pourrait s'appuyer ni sur la forme matérielle/énergétique, ni sur le contenu cognitif des messages émis : leur contenu sémantique est laissé de côté, de même que leur contenant physique, pour ne s'intéresser qu'aux aspects mathématiques.

    Dans sa conception originale, la théorie de l'information de Shannon s'est limitée à analyser les moyens à mettre en œuvre dans les techniques de télécommunication pour transmettre l'information le plus rapidement possible et avec le maximum de sécurité. Elle s'est donc efforcée de développer des méthodes susceptibles de minimiser la probabilité d'erreur dans la reconnaissance du message. Une notion fondamentale sera nécessaire pour développer ces méthodes : la mesure de l'information, au sens mathématique du terme.

    Pour Shannon, l'information présente un caractère essentiellement aléatoire. Un événement aléatoire est par définition incertain. Cette incertitude est prise comme mesure de l'information. Une information sera donc uniquement définie par sa probabilité (I = - log p). Donc l'information est la mesure de l'incertitude calculée à partir de la probabilité de l'événement. Shannon a donc confondu la notion d'information et de mesure d'incertitude. Il faut remarquer que dans cette définition l'information est bien synonyme de mesure d'incertitude. Dans cet ordre d'idée, plus une information est incertaine, plus elle est intéressante, et un événement certain ne contient aucune information. En théorie de l'information de Shannon, il s'agit donc de raisonner en probabilité et non en logique pure.

    L'information se mesure en unités d'information dites bits. Le bit peut être défini comme un événement qui dénoue l'incertitude d'un récepteur placé devant une alternative dont les deux issues sont pour lui équiprobables. Plus les éventualités que peut envisager ce récepteur sont nombreuses, plus le message comporte d'événements informatifs, plus s'accroît la quantité de bits transmis. Il est clair que nul récepteur ne mesure en bits l'information obtenue dans un message. C'est seulement le constructeur d'un canal de télécommunication qui a besoin de la théorie, et mesure l'information en bit pour rendre la transmission de message la plus économique et la plus fiable.

    La notion d'information d'après Shannon est nécessairement associée à la notion de « redondance » et à celle de « bruit ». Par exemple, en linguistique l'information n'est ni dans le mot, ni dans la syllabe, ni dans la lettre. Il y a des lettres voire des syllabes qui sont inutiles à la transmission de l'information que contient le mot : il y a dans une phrase, des mots inutiles à la transmission de l'information. La théorie de Shannon appelle redondance tout ce qui dans le message apparaît comme en surplus. Aussi est-il économique de ne pas transmettre la redondance.

    L'information chemine à travers un canal matériel/énergétique : fil téléphonique, onde radio, etc. Or, dans son cheminement, l'information rencontre du bruit. Le bruit est constitué par les perturbations aléatoires de toutes sortes qui surgissent dans le canal de transmission et tendent à brouiller le message. Le problème de la dégradation de l'information par le bruit est donc un problème inhérent à sa communication. Ici, l'idée de redondance présente une face nouvelle ; alors qu'elle apparaît comme un surplus inutile sous l'angle économique, elle devient, sous l'angle de la fiabilité de la transmission un fortifiant contre le bruit, un préventif contre les risques d'ambiguïté et d'erreur à la réception.

    Le statut physique de la théorie de l’information


    Très vite de multiples applications de la théorie de l'information de Shannon sont apparues dans le domaine des sciences humaines : les modèles mathématiques élaborés ont permis de préciser certains concepts utilisés couramment dans les analyses linguistiques structurales, en même temps qu'ils faisaient apparaître les limites inhérentes à ce type d'analyse et provoquaient des recherches nouvelles (en traduction automatique et en psycho-linguistique). Tandis que se développait un champ scientifique nouveau : la cybernétique.

    Cependant, une caractéristique majeure de la théorie shannonienne est de donner à la notion d'information (telle que définie par cette théorie) un statut physique à part entière. Effectivement, l'information acquiert les caractères fondamentaux de toute réalité physique organisée : abandonnée à elle-même, elle ne peut évoluer que dans le sens de sa désorganisation, c'est-à-dire l'accroissement d'entropie ; de fait, l'information subit, dans ses transformations (codage, transmission, décodage, etc..), l'effet irréversible et croissant de la dégradation. Par conséquent Shannon définit comme entropie d'information la mesure H ( H = - K log p). De façon étonnante, l'équation par laquelle Shannon définit l'entropie de l'information coïncide, mais de signe inverse, avec l'équation de Boltzmann-Gibbs définissant l'entropie S en thermodynamique (S = K log p).

    Certains, comme Couffignal, ont soutenu avec raison que la coïncidence est sans signification : l'application de la fonction de Shannon à la thermodynamique et à l'information est un hasard de rencontre de l'application d'une même formule mathématique, sans plus. Certes, il peut y avoir rencontre de deux équations de probabilité provenant d'univers différents. Toutefois Brillouin prétendait établir une relation logique entre le H de Shannon et le S de Boltzmann.

    Selon ce point de vue, il est possible d'inscrire l'information shannonienne dans la physique. En effet, il existe une dualité dans le concept d'information reliant l'information à la matière/énergie véhiculant cette information. L'information shannonienne s'enracine dans la physique et les mathématiques, mais sans qu'on puisse la réduire aux maîtres-concepts de la physique classique, masse et énergie. Comme le dit Wiener : «l'information n'est ni la masse, ni l'énergie, l'information est l'information.»


    Développement de la théorie mathématique de l'information


    La théorie mathématique de l'Information résulte initialement des travaux de Ronald Aylmer Fisher. Celui-ci, statisticien, définit formellement l'information comme égale à la valeur moyenne du carré de la dérivée du logarithme de la loi de probabilité étudiée.


    [​IMG]

    À partir de l'inégalité de Cramer, on déduit que la valeur d'une telle information est proportionnelle à la faible variabilité des conclusions résultantes. En termes simples, moins une observation est probable, plus son observation est porteuse d'information. Par exemple, lorsque le journaliste commence le journal télévisé par la phrase « Bonsoir », ce mot, qui présente une forte probabilité, n'apporte que peu d'information. En revanche, si la première phrase est, par exemple « La France a peur », sa faible probabilité fera que l'auditeur apprendra qu'il s'est passé quelque chose, et, partant, sera plus à l'écoute.

    D'autres modèles mathématiques ont complété et étendu de façon formelle la définition de l'information.

    Claude Shannon et Warren Weaver renforcent le paradigme. Ils sont ingénieurs en télécommunication et se préoccupent de mesurer l'information pour en déduire les fondamentaux de la Communication (et non une théorie de l'information). Dans Théorie Mathématique de la Communication en 1948, ils modélisent l'information pour étudier les lois correspondantes : bruit, entropie et chaos, par analogie générale aux lois d'énergétique et de thermodynamique. Leurs travaux complétant ceux d'Alan Turing, de Norbert Wiener et de John von Neumann (pour ne citer que les principaux) constituent le socle initial de la théorie du signal et des «Sciences de l'Information».

    Pour une source [​IMG] comportant [​IMG] symboles, un symbole [​IMG] ayant une probabilité [​IMG] d'apparaître, l'entropie [​IMG] de la source [​IMG] est définie comme :

    [​IMG]

    C'est au départ le logarithme naturel qui est utilisé. On le remplacera pour commodité par le logarithme à base 2, correspondant à une information qui est le bit. Les considérations d'entropie maximale (MAXENT) permettront à l'inférence bayésienne de définir de façon rationnelle ses distributions a priori.

    L'informatique constituera une déclinaison technique automatisant les traitements (dont la transmission et le transport) d'information. L'appellation « Technologies de l'Information et de la Communication » recouvre les différents aspects (systèmes de traitements, réseaux, etc.) de l'informatique au sens large.


    Les sciences de l'information dégagent du sens depuis des données en s'appuyant sur des questions de corrélation, d'entropie et d'apprentissage (voir Data mining). Les technologies de l'information, quant à elles, s'occupent de la façon de concevoir, implémenter et déployer des solutions pour répondre à des besoins identifiés.

    Adrian Mc Donough dans Information economics définit l'information comme la rencontre d'une donnée (data) et d'un problème. La connaissance (knowledge) est une information potentielle. Le rendement informationnel d'un système de traitement de l'information est le quotient entre le nombre de bits du réservoir de données et celui de l'information extraite. Les data sont le cost side du système, l'information, le value side. Il en résulte que lorsqu'un informaticien calcule la productivité de son système par le rapport entre la quantité de données produites et le coût financier, il commet une erreur, car les deux termes de l'équation négligent la quantité d'information réellement produite. Cette remarque prend tout son sens à la lumière du grand principe de Russel Ackoff qui postule qu'au-delà d'une certaine masse de données, la quantité d'information baisse et qu'à la limite elle devient nulle. Ceci correspond à l'adage « trop d'information détruit l'information ». Ce constat est aggravé lorsque le récepteur du système est un processeur humain, et pis encore, le conscient d'un agent humain. En effet, l'information est tributaire de la sélection opérée par l'attention, et par l'intervention de données affectives, émotionnelles, et structurelles absentes de l'ordinateur. L'information se transforme alors en sens, puis en motivation. Une information qui ne produit aucun sens est nulle et non avenue pour le récepteur humain, même si elle est acceptable pour un robot. Une information chargée de sens mais non irriguée par une énergie psychologique (drive, cathexis, libido, ep, etc.) est morte. On constate donc que dans la chaîne qui mène de la donnée à l'action (données → information → connaissance → sens → motivation), seules les deux premières transformations sont prises en compte par la théorie de l'information classique et par la sémiologie. Kevin Bronstein remarque que l'automate ne définit l'information que par deux valeurs : le nombre de bits, la structure et l'organisation des sèmes, alors que le psychisme fait intervenir des facteurs dynamiques tels que passion, motivation, désir, répulsion, etc. qui donnent vie à l'information psychologique.

    Exemples d'information


    Une information désigne, parmi un ensemble d'événements, un ou plusieurs événements possibles.

    En théorie, l'information diminue l'incertitude. En théorie de la décision, on considère même qu'il ne faut appeler « information » que ce qui est « susceptible d'avoir un effet sur nos décisions » (peu de choses dans un journal sont à ce compte des informations…)

    En pratique, l'excès d'information, tel qu'il se présente dans les systèmes de messagerie électronique, peut aboutir à une saturation, et empêcher la prise de décision.


    - Premier exemple
    Soit une source pouvant produire des tensions entières de 1 à 10 volts et un récepteur qui va mesurer cette tension. Avant l'envoi du courant électrique par la source, le récepteur n'a aucune idée de la tension qui sera délivrée par la source. En revanche, une fois le courant émis et reçu, l'incertitude sur le courant émis diminue. La théorie de l'information considère que le récepteur possède une incertitude de 10 états.

    - Second exemple
    Une bibliothèque possède un grand nombre d'ouvrages, des revues, des livres et des dictionnaires. Nous cherchons un cours complet sur la théorie de l'information. Tout d'abord, il est logique que nous ne trouverons pas ce dossier dans des ouvrages d'arts ou de littérature ; nous venons donc d'obtenir une information qui diminuera notre temps de recherche. Nous avions précisé que nous voulions aussi un cours complet, nous ne le trouverons donc ni dans une revue, ni dans un dictionnaire. nous avons obtenu une information supplémentaire (nous cherchons un livre), qui réduira encore le temps de notre recherche.

    - Information imparfaite
    Soit un réalisateur dont j'aime deux films sur trois. Un critique que je connais bien éreinte son dernier film et je sais que je partage en moyenne les analyses de ce critique quatre fois sur cinq. Cette critique me dissuadera-t-elle d'aller voir le film ? C'est là la question centrale de l'inférence bayésienne, qui se quantifie aussi en bits.

    Contenu d'information et contexte


    Il faut moins de bits pour écrire « chien » que « mammifère ». Pourtant l'indication « Médor est un chien » contient bien plus d'information que l'indication « Médor est un mammifère » : le contenu d'information sémantique d'un message dépend du contexte. En fait, c'est le couple message + contexte qui constitue le véritable porteur d'information, et jamais le message seul (voir paradoxe du compresseur).

    Mesure de la quantité d'information

    - Quantité d'information : cas élémentaire

    Considérons [​IMG] boîtes numérotées de 1 à [​IMG]. Un individu A a caché au hasard un objet dans une de ces boîtes. Un individu B doit trouver le numéro de la boîte où est caché l'objet. Pour cela, il a le droit de poser des questions à l'individu A auxquelles celui-ci doit répondre sans mentir par OUI ou NON. Mais chaque question posée représente un coût à payer par l'individu B (par exemple un euro). Un individu C sait dans quelle boîte est caché l'objet. Il a la possibilité de vendre cette information à l'individu B. B n'acceptera ce marché que si le prix de C est inférieur ou égal au coût moyen que B devrait dépenser pour trouver la boîte en posant des questions à A. L'information détenue par C a donc un certain prix. Ce prix représente la quantité d'information représentée par la connaissance de la bonne boîte : c'est le nombre moyen de questions à poser pour identifier cette boîte. Nous la noterons I.

    EXEMPLE :

    Si [​IMG], [​IMG]. Il n'y a qu'une seule boîte. Aucune question n'est nécessaire.

    Si [​IMG], [​IMG]. On demande si la bonne boîte est la boîte n°1. La réponse OUI ou NON détermine alors sans ambiguïté quelle est la boîte cherchée.

    Si [​IMG], [​IMG]. On demande si la boîte porte le n°1 ou 2. La réponse permet alors d'éliminer deux des boîtes et il suffit d'une dernière question pour trouver quelle est la bonne boîte parmi les deux restantes.

    Si [​IMG], [​IMG]. On écrit les numéros des boîtes en base 2. Les numéros ont au plus [​IMG] chiffres binaires, et pour chacun des rangs de ces chiffres, on demande si la boîte cherchée possède le chiffre 0 ou le chiffre 1. En [​IMG] questions, on a déterminé tous les chiffres binaires de la bonne boîte. Cela revient également à poser [​IMG] questions, chaque question ayant pour but de diviser successivement le nombre de boîtes considérées par 2 (méthode de dichotomie).

    On est donc amené à poser [​IMG], mais cette configuration ne se produit que dans le cas de [​IMG] événements équiprobables.

    - Quantité d'information relative à un événement

    Supposons maintenant que les boîtes soient colorées, et qu'il y ait [​IMG] boîtes rouges. Supposons également que C sache que la boîte où est caché l'objet est rouge. Quel est le prix de cette information ? Sans cette information, le prix à payer est [​IMG]. Muni de cette information, le prix à payer n'est plus que [​IMG]. Le prix de l'information « la boîte cherchée est rouge » est donc [​IMG].

    On définit ainsi la quantité d'information comme une fonction croissante de [​IMG] avec :

    • [​IMG] le nombre d'évènements possibles
    • [​IMG] le nombre d'éléments du sous-ensemble délimité par l'information

    Afin de mesurer cette quantité d'information, on pose : [​IMG]

    Il est exprimé en bit (ou « logon », unité introduite par Shannon, de laquelle, dans les faits, bit est devenu un synonyme), ou bien en « nat » si on utilise le logarithme naturel à la place du logarithme de base 2.


    Cette définition se justifie, car l'on veut les propriétés suivantes :

    1. l'information est comprise entre 0 et ;
    2. un évènement avec peu de probabilité représente beaucoup d'information (exemple : « Il neige en janvier » contient beaucoup moins d'information que « Il neige en août » pour peu que l'on soit dans l'hémisphère nord) ;
    3. l'information doit être additive.

    Remarque : lorsqu'on dispose de plusieurs informations, la quantité d'information globale n'est pas la somme des quantités d'information. Ceci est dû à la présence du logarithme. Voir aussi : information mutuelle, information commune à deux messages, qui, dans l'idée, explique cette « sous-additivité » de l'information.

    - Entropie, formule de Shannon
    Supposons maintenant que les boîtes soient de diverses couleurs : n[SUB]1[/SUB] boîtes de couleur C[SUB]1[/SUB], n[SUB]2[/SUB] boîtes de couleur C[SUB]2[/SUB], …, n[SUB]k[/SUB] boîtes de couleurs C[SUB]k[/SUB], avec n[SUB]1[/SUB] + n[SUB]2[/SUB] + … + n[SUB]k[/SUB] = N. La personne C sait de quelle couleur est la boîte recherchée. Quel est le prix de cette information ?

    L'information «la boîte est de couleur C[SUB]1[/SUB]» vaut log N/n[SUB]1[/SUB], et cette éventualité a une probabilité n[SUB]1[/SUB]/N. L'information « la boîte est de couleur C2 » vaut log N/n[SUB]2[/SUB], et cette éventualité a une probabilité n[SUB]2[/SUB]/N…
    Le prix moyen de l'information est donc n[SUB]1[/SUB]/N log N/n[SUB]1[/SUB] + n[SUB]2[/SUB]/N log N/n[SUB]2[/SUB] + … + n[SUB]k[/SUB]/N log N/n[SUB]k[/SUB]. Plus généralement, si on considère k évènements disjoints de probabilités respectives p[SUB]1[/SUB], p[SUB]2[/SUB], …, p[SUB]k[/SUB] avec p[SUB]1[/SUB] + p[SUB]2[/SUB] + … + p[SUB]k[/SUB] = 1, alors la quantité d'information correspondant à cette distribution de probabilité est p[SUB]1[/SUB] log 1/p[SUB]1[/SUB] + … + p[SUB]k[/SUB] log 1/p[SUB]k[/SUB]. Cette quantité s'appelle entropie de la distribution de probabilité.


    L'entropie permet donc de mesurer la quantité d'information moyenne d'un ensemble d'évènements (en particulier de messages) et de mesurer son incertitude.

    On la note [​IMG] :
    [​IMG] avec [​IMG] la probabilité associée à l'apparition de l'événement [​IMG].

    - Codage de l'information
    On considère une suite de symboles. Chaque symbole peut prendre deux valeurs s[SUB]1[/SUB] et s[SUB]2[/SUB] avec des probabilités respectivement p[SUB]1[/SUB] = 0,8 et p[SUB]2[/SUB] = 0,2. La quantité d'information contenue dans un symbole est :
    [​IMG]

    Si chaque symbole est indépendant du suivant, alors un message de N symboles contient en moyenne une quantité d'information égale à 0,72N. Si le symbole s[SUB]1[/SUB] est codé 0 et le symbole s[SUB]2[/SUB] est codé 1, alors le message a une longueur de N, ce qui est une perte par rapport à la quantité d'information qu'il porte. Les théorèmes de Shannon énoncent qu'il est impossible de trouver un code dont la longueur moyenne soit inférieure à 0,72N, mais qu'il est possible de coder le message de façon à ce que le message codé ait en moyenne une longueur aussi proche que l'on veut de 0,72N lorsque N augmente.

    Par exemple, on regroupe les symboles trois par trois et on les code comme suit :

    [TABLE="class: MsoNormalTable"]
    [TR]
    [TD]
    symboles à coder
    [/TD]
    [TD]
    probabilité du triplet
    [/TD]
    [TD]
    codage du triplet
    [/TD]
    [TD]
    longueur du code
    [/TD]
    [/TR]
    [TR]
    [TD="align: center"] s[SUB]1[/SUB]s[SUB]1[/SUB]s[SUB]1[/SUB][/TD]
    [TD="align: center"] 0.8³ = 0.512[/TD]
    [TD="align: center"] 0[/TD]
    [TD="align: center"] 1[/TD]
    [/TR]
    [TR]
    [TD="align: center"] s[SUB]1[/SUB]s[SUB]1[/SUB]s[SUB]2[/SUB][/TD]
    [TD="align: center"] 0.8² × 0.2 = 0.128[/TD]
    [TD="align: center"] 100[/TD]
    [TD="align: center"] 3[/TD]
    [/TR]
    [TR]
    [TD="align: center"] s[SUB]1[/SUB]s[SUB]2[/SUB]s[SUB]1[/SUB][/TD]
    [TD="align: center"] 0.8² × 0.2 = 0.128[/TD]
    [TD="align: center"] 101[/TD]
    [TD="align: center"] 3[/TD]
    [/TR]
    [TR]
    [TD="align: center"] s[SUB]2[/SUB]s[SUB]1[/SUB]s[SUB]1[/SUB][/TD]
    [TD="align: center"] 0.8² × 0.2 = 0.128[/TD]
    [TD="align: center"] 110[/TD]
    [TD="align: center"] 3[/TD]
    [/TR]
    [TR]
    [TD="align: center"] s[SUB]1[/SUB]s[SUB]2[/SUB]s[SUB]2[/SUB][/TD]
    [TD="align: center"] 0.2² × 0.8 = 0.032[/TD]
    [TD="align: center"] 11100[/TD]
    [TD="align: center"] 5[/TD]
    [/TR]
    [TR]
    [TD="align: center"] s[SUB]2[/SUB]s[SUB]1[/SUB]s[SUB]2[/SUB][/TD]
    [TD="align: center"] 0.2² × 0.8 = 0.032[/TD]
    [TD="align: center"] 11101[/TD]
    [TD="align: center"] 5[/TD]
    [/TR]
    [TR]
    [TD="align: center"] s[SUB]2[/SUB]s[SUB]2[/SUB]s[SUB]1[/SUB][/TD]
    [TD="align: center"] 0.2² × 0.8 = 0.032[/TD]
    [TD="align: center"] 11110[/TD]
    [TD="align: center"] 5[/TD]
    [/TR]
    [TR]
    [TD="align: center"] s[SUB]2[/SUB]s[SUB]2[/SUB]s[SUB]2[/SUB][/TD]
    [TD="align: center"] 0.2³ = 0.008[/TD]
    [TD="align: center"] 11111[/TD]
    [TD="align: center"] 5[/TD]
    [/TR]
    [/TABLE]

    Le message s[SUB]1[/SUB]s[SUB]1[/SUB]s[SUB]1[/SUB]s[SUB]1[/SUB]s[SUB]1[/SUB]s[SUB]2[/SUB]s[SUB]2[/SUB]s[SUB]2[/SUB]s[SUB]1[/SUB] sera codé 010011110.
    La longueur moyenne du code d'un message de N symboles est


    [​IMG]


    Limites de cette théorie


    L'une des caractéristiques fondamentales de cette théorie est l'exclusion de la sémantique. La théorie de l'information est indifférente à la signification des messages. Le sens d'un message peut pourtant être considéré comme essentiel dans la caractérisation de l'information. Mais le point de vue de la théorie de l'information se limite à celui d'un messager dont la fonction est de transférer un objet.

    La théorie de l'information de Shannon est toujours relative à un ensemble de données, une famille de chaines de caractères, caractérisée par une loi de distribution bien précise. Elle donne donc un contenu en information en moyenne, ce qui en fait une théorie probabiliste, particulièrement bien adaptée au contexte de la transmission de donnée, et dans ce cadre cette théorie a produit des résultats importants. En revanche, elle n'est pas en mesure de quantifier le contenu en information d'une chaine prise isolément, un brin d'ADN par exemple, alors que la théorie algorithmique de l'information en est capable jusqu'à un certain point. Mais cette dernière théorie possède également ses propres limitations. C'est pourquoi il ne faut pas considérer que la notion d'information est entièrement cernée par la théorie de l'information de Shannon, ou la théorie algorithmique de l'information, mais que cette notion a besoin d'une variété de modélisations formelles pour s'exprimer.

    L'information de Fisher semble ainsi parfois avantageusement remplacer l'information de Shannon dans la mesure où elle est une quantification locale et non globale de l'information contenue dans une distribution. Cela dit, les deux notions sont liées et peuvent dans diverses applications mener aux mêmes résultats.


    _______________________________
    Nom de la page : Théorie de l'information
    Contenu soumis à la licence CC-BY-SA 3.0.
    Sous licence Creative Commons paternité partage à l’identique
    Source : Article Théorie de l'information de Wikipédia en français (auteurs)



    ... SUITE /
    Codage de l'information

     
  6. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113
    Arithmétique modulaire
    _________________________________________________________________________



    Codage de l'information


    On s'intéresse ici aux moyens de formaliser l'information afin de pouvoir la manipuler (principalement pour la transmettre). On ne s'intéressera donc pas au contenu mais seulement à la forme.

    Alphabet, mot, langages

    - Définitions

    On définit un alphabet comme un ensemble non vide de symboles, par exemple :



    On nomme lettre un élément d'un alphabet.
    On nomme mot une suite finie de lettres.
    La suite de 0 lettre est nommée le mot vide, notée ε.

    On nomme langage un ensemble de mots associé à certaines règles d'interprétation (sans cette dernière restriction, n'importe quelle table de valeurs aléatoires pourrait être nommée langage).
    Dans le cas de l'ADN, ces règles sont contenues dans le ribosome, dans les langues naturelles, elles sont contenues dans leur lexique, sur un ordinateur, elles sont présentes dans les circuits de l'unité centrale.

    - Opérations

    Soit un alphabet [​IMG] et un entier naturel [​IMG].
    On note [​IMG] l'ensemble de tous les mots de longueur [​IMG] sur [​IMG] et [​IMG] l'ensemble de tous les mots de [​IMG].

    On dispose de : [​IMG](fermeture de Kleene).

    On définit l'opération de concaténation [​IMG] qui à [​IMG] associe un mot [​IMG] qui est constitué de la suite de lettres de [​IMG] puis celle de [​IMG].

    Exemple :
    «marc» [​IMG] «et sophie» = «marc et sophie» (les guillemets servent à délimiter les symboles, ce ne sont pas des éléments de
    [​IMG]).

    Propriétés
    :


    • .est associatif : [​IMG]
    • .admet ε comme élément neutre [​IMG]
    • .n'est pas commutative.

    Codages et codes

    - Codage

    Soit L et M deux langages.
    Un codage c de L dans M est un morphisme (pour l'opération [​IMG]) injectif. En d'autres termes, c'est une correspondance entre les mots de L et ceux de M, où à tout mot de L est associé un unique mot de M et tel que le codage de la concaténée soit égale à la concaténée des codages.

    ([​IMG]).

    - Code

    Un langage L sur un alphabet A est un code si et seulement s'il n'existe pas deux factorisations différentes des mots [​IMG] avec des mots de L.

    Applications, exemples



    ___________________

    Nom de la page :
    Codage de l'information
    Contenu soumis à la licence CC-BY-SA 3.0.
    sous licence Creative Commons paternité partage à l’identique
    Source : Article Codage de l'information de Wikipédia en français (auteurs)

    ___________________


    SUITE....

    Cryptologie
     
  7. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113
    Théorie de l'information
    ___________________________________________________________________________________


    Cryptologie


    La cryptologie, étymologiquement la science du secret, ne peut être vraiment considérée comme une science que depuis peu de temps. Cette science englobe la cryptographie — l'écriture secrète — et la cryptanalyse — l'analyse de cette dernière.
    La cryptologie est un art ancien et une science nouvelle : un art ancien car Jules César l'utilisait déjà ; une science nouvelle parce que ce n'est un thème de recherche scientifique académique (comprendre universitaire) que depuis les années 1970. Cette discipline est liée à beaucoup d'autres, par exemple l'arithmétique modulaire, l'algèbre, la complexité, la théorie de l'information, ou encore les codes correcteurs d'erreurs.

    Cryptographie


    La cryptographie se scinde en deux parties nettement différenciées :

    La première est la plus ancienne, on peut la faire remonter à l'Égypte de l'an 2000 av. J.-C. en passant par Jules César ; la seconde remonte à l'article de W. Diffie et M. Hellman, New directions in cryptography daté de 1976.

    Toutes deux visent à assurer la confidentialité de l'information, mais la cryptographie à clef secrète nécessite au préalable la mise en commun entre les destinataires d'une certaine information : la clef (symétrique), nécessaire au chiffrement ainsi qu'au déchiffrement des messages. Dans le cadre de la cryptographie à clef publique, ce n'est plus nécessaire. En effet, les clefs sont alors différentes, ne peuvent se déduire l'une de l'autre, et servent à faire des opérations opposées, d'où l'asymétrie entre les opérations de chiffrement et de déchiffrement.

    Bien que beaucoup plus récente et malgré d'énormes avantages — signature numérique, échange de clefs... — la cryptographie à clef publique ne remplace pas totalement celle à clef secrète, qui pour des raisons de vitesse de chiffrement et parfois de simplicité reste présente. À ce titre, signalons la date du dernier standard américain en la matière, l'AES : décembre 2001, ce qui prouve la vitalité encore actuelle de la cryptographie symétrique.
    Dans le bestiaire des algorithmes de chiffrement, on peut citer :


    Cryptanalyse


    Le pendant de cette confidentialité se trouve dans la cryptanalyse. Évidemment, depuis l'existence de ces codes secrets, on a cherché à les casser, à comprendre les messages chiffrés bien que l'on n'en soit pas le destinataire légitime, autrement dit décrypter. Si la cryptanalyse du système de César est aisée (un indice : les propriétés statistiques de la langue, en français, le e est la lettre la plus fréquente), des systèmes beaucoup plus résistants ont vu le jour. Certains ont résisté longtemps, celui de Vigenère (Le traité des secrètes manières d'écrire 1586) par exemple, n'ayant été cassé par Babbage qu'au milieu du XIX[SUP]e[/SUP] siècle. D'autres, bien que n'ayant pas de faille exploitable, ne sont plus utilisés car ils sont à la portée des puissances de calcul modernes. C'est le cas du DES avec sa clef de 56 bits jugée trop courte car elle peut être trouvée par recherche exhaustive (force brute).

    Dans un bestiaire de la cryptanalyse, il faudrait presque passer chaque système en revue — non seulement chaque système, mais aussi chaque mise en œuvre : à quoi sert la meilleure porte blindée si le mur qui la soutient est en contreplaqué ? Cela dit, si l'on veut vraiment citer quelques techniques, on a :

    • la cryptanalyse différentielle, Biham et Shamir (le S de RSA), 1991, systèmes symétriques ;
    • la cryptanalyse linéaire, Matsui, 1994, systèmes symétriques ;
    • la factorisation, seul vrai moyen de déchiffrer RSA à l'heure actuelle ;
    • la force brute, c'est-à-dire l'essai systématique de toutes les clefs possibles ;
    • et d'autres encore.

    Autres facettes de la cryptologie


    La confidentialité n'est que l'une des facettes de la cryptologie. Elle permet également :

    Pour l'essentiel, c'est la cryptographie à clef publique qui fournit les bases nécessaires à ces aspects de la cryptologie.

    Une arme de guerre


    La cryptologie a très longtemps été considérée comme une arme de guerre. Au IV[SUP]e[/SUP] siècle av. J.-C., Énée le Tacticien, un général grec, y consacre un chapitre dans Commentaires sur la défense des places fortes. On peut citer le siège de la Rochelle, où Antoine Rossignol (1600 - 1682) décrypte les messages que les Huguenots assiégés tentent de faire sortir. Richelieu y apprend ainsi que les Huguenots sont affamés et attendent la flotte anglaise. Celle-ci trouvera à son arrivée la flotte française, prête au combat, ainsi qu'une digue bloquant l'accès au port.

    Autre exemple, la Première Guerre mondiale, où le Room 40 — service du chiffre britannique — s'illustre tout particulièrement en décryptant un télégramme envoyé en janvier 1917 de Berlin à l'ambassadeur allemand à Washington, qui devait le retransmettre au Mexique. Ils apprennent ainsi que l'Allemagne va se lancer dans une guerre sous-marine totale et demande une alliance militaire, devant permettre au Mexique de récupérer le Nouveau-Mexique, le Texas et l'Arizona. Les Britanniques pourraient transmettre directement ces renseignements aux États-Unis, mais ils révéleraient ainsi aux Allemands l'interception et la mise à jour de leur code. Ils préfèrent donc envoyer un espion récupérer le message destiné aux Mexicains, faisant ainsi croire à une fuite côté Mexique. Le télégramme en clair se retrouve publié dans les journaux américains le 1[SUP]er[/SUP] mars 1917. Suite à cela, le président Wilson n'a pas de mal à obtenir l'accord du congrès, les États-Unis entrent en guerre.

    Ces exemples illustrent bien pourquoi les gouvernements sont prudents quant à l'utilisation de moyen cryptographique. Philip Zimmermann en a fait l'expérience lorsqu'il a mis à disposition son logiciel de messagerie sécurisée, Pretty Good Privacy (PGP), en 1991. Violant les restrictions à l'exportation pour les produits cryptographiques, PGP a été très mal accueilli par le gouvernement américain qui a ouvert une enquête en 1993 — abandonnée en 1996, peu avant que le gouvernement Clinton ne libéralise grandement, à l'aube de l'ère du commerce électronique, l'usage de la cryptographie.

    Aspects juridiques


    En France, depuis la loi pour la confiance dans l'économie numérique, l'usage de la cryptologie est libre. Néanmoins, l'article 132-79 du code pénal prévoit que lorsqu'un moyen de cryptologie a été utilisé pour préparer ou commettre un crime ou un délit, ou pour en faciliter la préparation ou la commission, le maximum de la peine privative de liberté encourue est relevé.

    Les dispositions pénales ne sont toutefois pas applicables à l'auteur ou au complice de l'infraction qui, à la demande des autorités judiciaires ou administratives, leur a remis la version en clair des messages chiffrés ainsi que les conventions secrètes nécessaires au déchiffrement.

    Des logiciels de chiffrement avec une fonction de déni plausible permettent d'échapper à l'aggravation des peines (ex: FreeOTFE et TrueCrypt).


    Différents aspects de la cryptologie




    ________________________________
    Nom de la page : Cryptologie
    Contenu soumis à la licence CC-BY-SA 3.0.
    Source : Article Cryptologie de Wikipédia en français (auteurs)
    Sous licence Creative Commons paternité partage à l’identique

    ________________________________


    Langage de la cryptologie

    Comme toute science, la cryptologie possède son propre langage. Étant donnée la relative jeunesse de cette science, et le fait qu'une très grande partie des publications dans ce domaine sont en langue anglaise, le problème de la terminologie francophone se pose, parfois par manque de traduction, parfois par manque de traduction univoque ou élégante.

    Chiffrement ou cryptage


    Heureusement, certains termes, de par l'utilisation systématique dont ils font l'objet, ne souffrent pas de discussion. Ainsi, on parle de chiffrement et non de cryptage. Ici, la raison est simple : décryptage a une signification et elle est totalement différente de déchiffrement. Le déchiffrement est une opération effectuée par le destinataire légitime, pour retrouver le message qu'on lui a envoyé — que l'on appelle le texte clair, le message chiffré étant parfois appelé cryptogramme. Cette opération nécessite une donnée secrète que l'on appelle la clé. Le décryptage consiste également à essayer de retrouver le texte clair, mais sans connaître cette clé : c'est donc l'opération d'un adversaire cherchant à prendre connaissance de la communication sans y avoir droit.

    Algorithmes, protocoles et autres schémas


    Mis à part les problèmes de terminologie, il y a des définitions qui peuvent sembler plus ou moins précises. Par exemple, on parle de l'algorithme de chiffrement RSA mais du protocole d'échange de clés Diffie-Hellman ou encore de schéma de signature. La différence entre un algorithme et un protocole est une question d'interactivité : pour un algorithme, une seule personne est impliquée, celle qui fait les calculs ; pour un protocole, plusieurs entités interviennent, il y a échange d'informations. La notion de schéma est quant à elle moins précise, ce terme est généralement utilisé lorsque l'on souhaite mettre en évidence le fait que l'algorithme ou le protocole repose sur un algorithme plus élémentaire. Autrement dit on essaie de faire ressortir le caractère composé.

    Alice, Bob et Ève


    Le folklore des cryptologues veut que l'on utilise fréquemment les mêmes prénoms dans les explications des protocoles ou des attaques. Généralement, Alice et Bob (on trouve également Bernard en français) sont les deux personnes cherchant à communiquer de manière sûre (quand Carole ne se joint pas à eux) alors que Ève est l'espionne. Voir l'article Alice Oscar Bob Eve.

    Définitions multiples


    Pour finir, on se trouve parfois face à des définitions portant plusieurs noms mais recouvrant le même concept. Ainsi les preuves sans divulgation sont aussi désignées par les expressions à apport de connaissance nulle ou sans apport de connaissance, la cryptographie à clé publique est également appelée asymétrique, de par l'asymétrie existant entre la possibilité de chiffrer -- accessible à tout le monde -- et de déchiffrer -- restreinte au seul destinaitaire. Sur le même principe, la cryptographie à clé secrète est dite symétrique.

    ________________________________
    Nom de la page : Langage de la cryptologie
    Contenu soumis à la licence CC-BY-SA 3.0.
    Source : Article Langage de la cryptologie de Wikipédia en français (auteurs)

    ________________________________


    Alice et Bob

    Les personnages Alice et Bob sont des figures classiques en cryptologie. Ces noms sont utilisés au lieu de « personne A » et « personne B » ; Alice et Bob cherchent dans la plupart des cas à communiquer de manière sécurisée.

    Ces noms ont été inventés par Ron Rivest pour son article de 1978 dans le Communications of the ACM qui présentait le cryptosystème RSA. (Le rapport technique de 1977 sur RSA n'utilisait pas encore ces noms.) Rivest nie tout lien avec le film de 1969 intitulé Bob et Carole et Ted et Alice.

    D'autres prénoms sont utilisés pour décrire d'autres rôles, comme Oscar (l'adversaire, opponent en anglais) ou Eve (une « écouteuse » ou eavesdropper) ou Robert (le responsable, Roberto en Espagnol). Ces personnages font souvent partie des démonstrations d'attaques et d'explications sur les protocoles. Selon la langue, on peut trouver d'autres prénoms (Bernard ou Carole en français, par exemple).


    Utilisateurs légitimes



    • Alice et Bob (parfois Bernard en français). En général, Alice veut envoyer un message à Bob.
    • Carol (ou Carole en français), est une troisième participante aux échanges. Puis, on a souvent Dave, un quatrième participant. Pour aller au-delà, il faudrait utiliser un prénom en « E », mais un risque de confusion existe car cette lettre est celle de l'attaquant le plus courant (voir plus bas).

    Adversaires



    • Eve, un écouteur externe (de l'anglais eavesdropper), est un attaquant passif. Tandis qu'elle peut écouter les échanges d'Alice et de Bob, elle ne peut pas les modifier.
    • Mallory, (ou Mallet, pour malicieux), est un attaquant actif. Au contraire d'Eve, Mallory peut modifier les messages, substituer les siens, remettre en jeu d'anciens messages, etc. Rendre un système sûr vis-à-vis de Mallory s'avère un problème plus difficile que pour Eve.
    • Oscar, un opposant, est habituellement défini comme équivalent à Mallory.
    • Trudy, une intruse, est plus dangereuse qu'Eve parce que celle-là peut modifier des messages en transit. Bob et Alice devraient idéalement être aptes à détecter de telles modifications, puis soit les ignorer, soit récupérer le message original. Sinon, Trudy peut causer beaucoup de dommages.

    Tierces parties



    • Isaac, un fournisseur d'accès à Internet ("i" de l'anglais Internet Service Provider, ISP).
    • Ivan, un émetteur ("i" de l'anglais issuer), pour la cryptographie financière, par exemple.
    • Justin, du système de justice, plus spécifiquement, un avocat.
    • Matilda, une marchande, pour la cryptographie financière ou le commerce électronique, par exemple.
    • Nestor, un tiers de confiance neutre, est une version francophone de Trent.
    • Plod, est un officier de police, de douanes ou de service de renseignements.
    • Trent, est un arbitre de confiance ("tr" de l'anglais trusted arbitrator), est en quelque sorte un tiers parti neutre dont le rôle exact varie avec le protocole dont il est question.
    • Vanna, voir Peggy.
    • Victor, voir Peggy.
    • Walter, un gardien de prison ("w" de l'anglais warden), peut surveiller Alice et Bob d'une façon qui dépend du protocole en question.

    Preuve à divulgation nulle de connaissance



    • Peggy (ou Pat), une prouveur et Victor, un vérifieur, doivent interagir d'une façon donnée afin de prouver que la transaction voulue a bien eu lieu. On les retrouve souvent dans les preuves à divulgation nulle de connaissance (zero-knowledge). Une autre paire de noms pour ceci est Pat et Vanna (à cause des hôtes de l'émission de télévision américaine Wheel of Fortune).

    Systèmes de preuve interactive


    Bien que les systèmes de preuve interactive ne soient pas tout à fait des protocoles cryptographiques, ils sont suffisamment reliés pour qu'on mentionne la liste des personnages de sa terminologie.

    • Arthur et Merlin : dans les preuves interactives, le prouveur a une capacité calculatoire illimitée et est donc associé à Merlin, le puissant magicien. Il émet un énoncé comme véritable et Arthur, le sage roi, lui pose des questions pour vérifier cet énoncé. Ces deux personnages sont aussi éponymes de deux classes de complexité, soit MA et AM.

    ________________________________
     
  8. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113


    Cryptographie

    La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés. Elle se distingue de la stéganographie qui fait passer inaperçu un message dans un autre message alors que la cryptographie rend un message inintelligible à autre que qui-de-droit.

    Elle est utilisée depuis l'Antiquité, mais certaines de ses méthodes les plus importantes, comme la cryptographie asymétrique, datent de la fin du XX[SUP]e[/SUP] siècle.


    Étymologie et vocabulaire


    Le mot cryptographie vient des mots en grec ancien kruptos («caché») et graphein («écrire»).
    À cause de l'utilisation d'anglicismes puis de la création des chaînes de télévision dites «cryptées», une grande confusion règne concernant les différents termes de la cryptographie :



    • chiffrement : transformation à l'aide d'une clé d'un message en clair (dit texte clair) en un message incompréhensible (dit texte chiffré) pour celui qui ne dispose pas de la clé de déchiffrement (en anglais encryption key ou private key pour la cryptographie asymétrique) ;
    • chiffre : utilisation de la substitution au niveau des lettres pour coder ;
    • code : utilisation de la substitution au niveau des mots ou des phrases pour coder ;
    • coder : action réalisée sur un texte lorsqu'on remplace un mot ou une phrase par un autre mot, un nombre ou un symbole;
    • cryptogramme : message chiffré ;
    • crypto système : algorithme de chiffrement;
    • décrypter : retrouver le message clair correspondant à un message chiffré sans posséder la clé de déchiffrement (terme que ne possèdent pas les anglophones, qui eux « cassent » des codes secrets);
    • cryptographie : étymologiquement «écriture secrète», devenue par extension l'étude de cet art (donc aujourd'hui la science visant à créer des cryptogrammes, c'est-à-dire à chiffrer) ;
    • cryptanalyse : science analysant les cryptogrammes en vue de les décrypter ;
    • cryptologie : science regroupant la cryptographie et la cryptanalyse.
    • cryptolecte : jargon réservé à un groupe restreint de personnes désirant dissimuler leur communication.

    Il apparaît donc que mis au regard du couple chiffrer/déchiffrer et du sens du mot «décrypter», le terme «crypter» n'a pas de raison d'être (l'Académie française précise que le mot est à bannir), en tout cas pas dans le sens où on le trouve en général utilisé. Dans sa dernière édition (entamée en 1992) le Dictionnaire de l'Académie française n'intègre pas «crypter» et «cryptage», mais ce dernier terme apparait dans le Grand Robert (qui date son apparition de 1980). L'Office québécois de la langue française intègre «crypter» au sens de «chiffrer», et «cryptage» au sens de déchiffrement dans son grand dictionnaire terminologique.

    Histoire


    Utilisé depuis l'antiquité, l'une des utilisations les plus célèbres pour cette époque est le chiffre de César, nommé en référence à Jules César qui l'utilisait pour ses communications secrètes. Mais la cryptographie est bien antérieure à cela : le plus ancien document chiffré est une recette secrète de poterie qui date du XVI[SUP]e[/SUP] siècle av. J.-C., qui a été découverte dans l'actuelle Irak.

    Bien qu'éminemment stratégique, la cryptographie est restée pendant très longtemps un art, pour ne devenir une science qu'au XXI[SUP]e[/SUP] siècle. Avec l'apparition de l'informatique, son utilisation se démocratise de plus en plus.

    Utilisations


    Les domaines d'utilisations de la cryptographie sont très vastes et vont du domaine militaire, au commercial, en passant par la protection de la vie privée.

    Algorithmes et protocoles

    - Algorithmes de chiffrement faibles (facilement cassables)

    Les premiers algorithmes utilisés pour le chiffrement d'une information étaient assez rudimentaires dans leur ensemble. Ils consistaient notamment au remplacement de caractères par d'autres. La confidentialité de l'algorithme de chiffrement était donc la pierre angulaire de ce système pour éviter un décryptage rapide.

    Exemples d'algorithmes de chiffrement faibles :


    - Algorithmes de cryptographie symétrique (à clé secrète)
    Les algorithmes de chiffrement symétrique se fondent sur une même clé pour chiffrer et déchiffrer un message. L'un des problèmes de cette technique est que la clé, qui doit rester totalement confidentielle, doit être transmise au correspondant de façon sûre. La mise en œuvre peut s'avèrer difficile, surtout avec un grand nombre de correspondants car il faut autant de clés que de correspondants.

    Quelques algorithmes de chiffrement symétrique très utilisés :

    • Chiffre de Vernam (le seul offrant une sécurité théorique absolue, à condition que la clé ait au moins la même longueur que le message, qu'elle ne soit utilisée qu'une seule fois à chiffrer et qu'elle soit totalement aléatoire)
    • DES
    • 3DES
    • AES
    • RC4
    • RC5
    • MISTY1
    • Et d’autres…

    - Algorithmes de cryptographie asymétrique (à clé publique et privée)
    Pour résoudre le problème de l'échange de clés, la cryptographie asymétrique a été mise au point dans les années 1970. Elle se base sur le principe de deux clés :

    • une publique, permettant le chiffrement ;
    • une privée, permettant le déchiffrement.

    Comme son nom l'indique, la clé publique est mise à la disposition de quiconque désire chiffrer un message. Ce dernier ne pourra être déchiffré qu'avec la clé privée, qui doit rester confidentielle.

    Quelques algorithmes de cryptographie asymétrique très utilisés :


    Le principal inconvénient de RSA et des autres algorithmes à clés publiques est leur grande lenteur par rapport aux algorithmes à clés secrètes. RSA est par exemple 1000 fois plus lent que DES. En pratique, dans le cadre de la confidentialité, on s'en sert pour chiffrer un nombre aléatoire qui sert ensuite de clé secrète pour un algorithme de chiffrement symétrique. C'est le principe qu'utilisent des logiciels comme PGP par exemple.

    La cryptographie asymétrique est également utilisée pour assurer l'authenticité d'un message. L'empreinte du message est chiffrée à l'aide de la clé privée et est jointe au message. Les destinataires déchiffrent ensuite le cryptogramme à l'aide de la clé publique et retrouvent normalement l'empreinte. Cela leur assure que l'émetteur est bien l'auteur du message. On parle alors de signature ou encore de scellement.


    - Fonctions de hachage
    Une fonction de hachage est une fonction qui convertit un grand ensemble en un plus petit ensemble, l'empreinte. Il est impossible de la déchiffrer pour revenir à l'ensemble d'origine, ce n'est donc pas une technique de chiffrement.
    Quelques fonctions de hachage très utilisées :


    L'empreinte d'un message ne dépasse généralement pas 256 bits (maximum 512 bits pour SHA-512) et permet de vérifier son intégrité.

    Communauté


    Projet NESSIE
    Advanced Encryption Standard process
    Les cryptologues sont des experts en cryptologie : ils conçoivent, analysent et cassent les algorithmes.


    _____________________________
     
  9. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113



    Histoire de la cryptographie


    Cet article résume l'histoire de la cryptographie de l'Antiquité à aujourd'hui. La cryptographie est la science du codage des messages à l'aide de codes secrets ou de clés. Le codage des messages vise à en assurer la confidentialité, l'authenticité et l'intégrité.

    Dans l'Antiquité


    - Les premières méthodes de chiffrement
    Le plus vieux document chiffré
    Le premier «document» chiffré connu remonte à l'Antiquité. Il s'agit d'une tablette d'argile, retrouvée en Irak, et datant du XVI[SUP]e[/SUP] siècle av. J.-C. Un potier y avait gravé sa recette secrète en supprimant des consonnes et en modifiant l'orthographe des mots.
    Bien qu'éminemment stratégique, la cryptographie est restée pendant très longtemps un art, pour ne devenir une science qu'au XXI[SUP]e[/SUP] siècle. Avec l'apparition de l'informatique, son utilisation se démocratise de plus en plus.

    La technique grecque
    La première grande compilation des procédés cryptographiques et stéganographique pratiqués durant l'Antiquité est celle du chapitre 31 de la Poliorcétique d'Énée le Tacticien, datant du IV[SUP]e[/SUP] siècle av. J.-C.
    Entre le X[SUP]e[/SUP] et le VII[SUP]e[/SUP] siècle av. J.-C. semble attestée une technique de chiffrement par transposition, c'est-à-dire reposant sur le changement de position des lettres dans le message, en utilisant un bâton de diamètre déterminé appelée scytale. On enroulait en hélice une bande de cuir autour de la scytale avant d'y inscrire un message. Une fois déroulé, le message était envoyé au destinataire qui possédait un bâton identique, nécessaire au déchiffrement. Cependant, l'utilisation de la scytale lacédémonienne comme procédé cryptographique n'est explicitement affirmée que par Plutarque et Aulu-Gelle, auteurs de la fin de l'Antiquité, et n'est pas mentionnée par Énée le Tacticien : dès lors, la scytale a-t-elle véritablement été un procédé cryptographique ?

    La technique des Hébreux
    À partir du V[SUP]e[/SUP] siècle av. J.-C., l'une des premières techniques de chiffrement est utilisée dans les textes religieux par les Hébreux qui connaissent plusieurs procédés.
    Le plus connu appelé Atbash est une méthode de substitution alphabétique inversée. Son nom est formé par les initiales des premières et dernières lettres de l'alphabet hébreux aleph, tav, beth, shin.
    Elle consiste à remplacer chaque lettre du texte en clair par une autre lettre de l'alphabet choisie de la manière suivante : A devient Z, B devient Y, etc.

    Nabuchodonosor
    Aux alentours de -600, Nabuchodonosor, roi de Babylone, employait une méthode originale : il écrivait sur le crâne rasé de ses esclaves, attendait que leurs cheveux aient repoussé, et il les envoyait à ses généraux. Il suffisait ensuite de raser à nouveau le messager pour lire le texte. Il s'agit toutefois de stéganographie à proprement parler et non pas de cryptographie : l'information est cachée et non pas codée.
    On remarque dans ce procédé une certaine fiabilité : en effet l'interception du message par un tiers est tout de suite remarquée.


    Les premiers «vrais» systèmes de cryptographie
    Il faut attendre -200 pour voir apparaître les premiers «vrais» systèmes de cryptographie. Ce sont essentiellement des chiffrements par substitution.
    Il existe 3 types de substitutions :
    - mono-alphabétique : remplace chaque lettre du message par une autre lettre de l'alphabet

    - poly-alphabétique : utilise une suite de chiffres mono-alphabétiques (la clé) réutilisée périodiquement
    - poly-grammes : substitue un groupe de caractères dans le message par un autre groupe de caractères

    Le code de César

    Le code de César est la méthode cryptographique, par substitution mono-alphabétique, la plus ancienne (I[SUP]er[/SUP] siècle av. J.-C.).
    Cette méthode est utilisée dans l'armée romaine et bien qu'elle soit beaucoup moins robuste que la technique Atbash, la faible alphabétisation de la population la rend suffisamment efficace.

    Méthode de chiffrement
    Son système est simple, il consiste à décaler les lettres de l'alphabet d'un nombre n. Par exemple, si on remplace A par D (n=3), on remplace B par E, C par F...
    Le texte que nous souhaitons coder étant le suivant : «décaler les lettres de l'alphabet»
    Le texte codé est alors : « ghfdohu ohv ohwwuhv gh o'doskdehw »

    Limites du procédé

    Malheureusement, on comprendra que ce système est très peu sûr, puisqu'il n'y a que 26 lettres dans l'alphabet donc seulement 25 façons de chiffrer un message avec le code de César (on ne peut substituer une lettre par elle-même). Pourtant sa simplicité conduisit les officiers sudistes à le réemployer durant la guerre de Sécession. L'armée russe en fit de même en 1915.

    Un système connu et pourtant

    Le code de César a été utilisé sur des forums internet sous le nom de ROT13 (rotation de 13 lettres ou A→N...). Le ROT13 n'a pas pour but de rendre du texte confidentiel, mais plutôt d'empêcher la lecture involontaire (d'une réponse à une devinette, ou de l'intrigue d'un film, etc.). Son utilisation est simple : il suffit de re-chiffrer un texte, codé en ROT13, une deuxième fois pour obtenir le texte en clair.L'historien grec Polybe est à l'origine du premier procédé de chiffrement par substitution homophonique.
    Méthode de chiffrement
    C'est un système de transmission basé sur un carré de 25 cases (on peut agrandir ce carré à 36 cases, afin de pouvoir ajouter les chiffres ou pour chiffrer des alphabets comportant davantage de lettres, comme l'alphabet cyrillique).
    En français, on supprime le W, qui sera remplacé par V. Il existe une variante où ce sont I et J qui se partagent la même case. Chaque lettre peut être ainsi représentée par un groupe de deux chiffres : celui de sa ligne et celui de sa colonne. Ainsi e=(1;5), u=(5;1), n=(3;4)...
    Un moyen de transmission original
    Polybe proposait de transmettre ces nombres au moyen de torches. Une torche à droite et cinq à gauche pour transmettre la lettre e par exemple. Ce procédé permettait donc de transmettre des messages sur de longues distances.

    Son originalité

    Les cryptologues modernes ont vu dans le « carré de 25 » plusieurs caractéristiques extrêmement intéressantes :

    • la conversion de lettres en chiffres,
    • la réduction de nombres, de symboles,
    • la représentation de chaque lettre par deux éléments séparés.

    Ce système de chiffrement peut être compliqué avec un mot de passe. Par exemple, si le mot de passe est «DIFFICILE», on commencera à remplir le carré avec les lettres de ce mot, après avoir supprimé les lettres identiques, puis on complétera le tableau avec les lettres inutilisées.

    De l'Antiquité à la guerre





    Ce dictionnaire permet de chiffrer des mots ou des syllabes courants et sera utilisé pendant plusieurs siècles par les diplomates européens et américains.



    • 1412 : Les connaissances de la civilisation arabe dans le domaine de la cryptologie sont exposées dans Subh al-a sha, une encyclopédie en 14 volumes écrite par l'Égyptien al-Qalqashandi.

    • 1467 : Le savant italien Leone Battista Alberti expose pour la première fois le chiffrement par substitution polyalphabétique qu'il applique à l'aide d'un disque à chiffrer.
      Ce procédé consiste à remplacer chaque lettre du texte en clair par une lettre d'un autre alphabet et à changer plusieurs fois d'alphabet de substitution au cours du chiffrement, rendant la cryptanalyse par analyse de fréquence inefficace.
      Le principe du disque à chiffrer sera repris et amélioré par le colonel Wadsworth en 1817, puis par Charles Wheatstone en 1867.
      Alberti présente aussi pour la première fois le surchiffrement codique, c'est-à-dire le chiffrement du texte déjà chiffré une première fois, technique qui ne sera réellement utilisée que plusieurs siècles plus tard.


    • 1518 : Le moine bénédictin Jean Trithème écrit Polygraphiæ, le premier livre imprimé traitant de cryptologie, dans lequel il expose un procédé stéganographique consistant à remplacer chaque lettre du texte en clair par un groupe de mots, le texte chiffré ressemblant alors à un poème.
      Trithème expose aussi une technique de chiffrement par substitution polyalphabétique à l'origine de la technique connue sous le nom de chiffre de Vigenère.

    • 1553 : Giovan Battista Bellaso publie le livre La Cifra, un recueil de clés littérales utilisées dans les chiffrements par substitution polyalphabétique, faciles à retenir et à utiliser, qu'il appelle mots de passe.

    • 1563 : L'Italien Giambattista della Porta expose dans son livre De Furtivis Literarum Notis, vulgo de ziferis les connaissances en cryptologie connues jusqu'à cette époque.
      Il expose une technique de substitution diagrammatique consistant à remplacer chaque couple de lettres du texte en clair par un symbole et présente un procédé de chiffrement par substitution polyalphabétique utilisant 11 alphabets différents qui restera efficace pendant 3 siècles.

    En 1586, le diplomate français Blaise de Vigenère présente dans son livre Traicté des chiffres ou secrètes manières d'escrire (Bibliothèque Nationale de France) une technique de chiffrement par substitution polyalphabétique inspirée de celle de Trithème. Le chiffrement de Vigenère ne sera cassé qu'en 1854.

    Méthode de chiffrement
    Le chiffrement utilise une clé littérale ou mot de passe, dont chaque lettre indique le décalage alphabétique à appliquer sur le texte en clair.
    On reporte les lettres de l'alphabet sur une grille de 26 x 26 cases ; la première rangée contenant A, B, ..., les colonnes suivantes sont chacune décalée d'une position par rapport à la précédente. Le texte chiffré s'obtient en prenant l'intersection, de la ligne qui commence par la lettre à coder, avec la colonne qui commence par la première lettre du mot de passe, et ainsi de suite. Dès que l'on atteint la fin du mot de passe, on recommence à la première lettre. Pour décoder, il suffit de faire la même chose dans l'autre sens.


    Les points forts de cette méthode
    Cet algorithme de cryptographie comporte beaucoup de points forts. Il est très facile d'utilisation, et le déchiffrement est tout aussi facile si on connaît la clé. La grande caractéristique du chiffre de Vigenère est qu'il est impossible par une analyse statistique simple de retrouver où sont certaines lettres. Un autre avantage réside dans le fait que l'on peut produire une infinité de clés. Il fallut attendre près de trois siècles pour qu'il soit cryptanalysé au milieu du XIX[SUP]e[/SUP] siècle. Voir Cryptanalyse du chiffre de Vigenère.



    • 1623 : Dans son livre De dignitate et augmentis scientiarum, Francis Bacon expose une technique stéganographique qui consiste à représenter chaque lettre du texte en clair par un groupe de 5 lettres A ou B. Le texte chiffré résultant est ainsi constitué d'une succession de ces deux lettres.
      Ce procédé est équivalent à un codage binaire des lettres de l'alphabet sur 5 bits (de type Code Baudot), préfigurant le codage numérique des lettres sur 8 bits utilisé actuellement en informatique (code ASCII).


    • Les moyens de transmissions sont utilisés avec un moyen de codage dès le XIXe siècle — et même depuis 1794 pour le télégraphe optique de Chappe, qu'entre 1834 et 1835, deux banquiers, les célèbres frères jumeaux Joseph et François Blanc, détourneront, de connivence avec deux employés du télégraphe entre Bordeaux et Tours, pour transmettre avec leur propre code des informations avant qu'elles n'arrivent par les voies officielles.

    • 1854 : Un pionnier du télégraphe, Charles Wheatstone, apporte sa contribution à la cryptologie en inventant le chiffrement de Playfair, du nom de celui qui l'a fait connaître.
      Cette technique est basée sur une méthode de substitution diagrammatique consistant à remplacer un couple de lettres adjacentes par un autre couple choisi dans une grille qui constitue la clé.

    • 1883 : Le hollandais Auguste Kerckhoffs publie un livre sur la cryptologie La cryptographie militaire.
      Il y expose notamment quelques règles à respecter pour concevoir un bon système cryptographique, toujours valables actuellement, dont la principale est la suivante : la sécurité d'un système ne doit pas reposer sur le secret de la méthode de chiffrement ("Sécurité par l'obscurité").

    L'inventeur de ce système est Félix-Marie Delastelle. Il utilise une grille de chiffrement/déchiffrement analogue à celle du chiffre de Polybe.

    Méthode de chiffrement

    Tout d'abord, il faut regrouper les lettres du message clair par groupes de 5 par (au besoin, on rajoute des nulles pour arriver à un multiple de 5).
    Pour déchiffrer, on effectue l'opération dans le sens inverse.

    Une simple adaptation

    Ce chiffre diffère peu de celui de Polybe. Il est présenté ici pour montrer la diversité des méthodes de chiffrement : la plupart de ces méthodes sont de simples adaptations de méthodes déjà existantes.

    Grand chiffre du roi Louis XIV
    Les historiens disposent de quelques documents qui ont été chiffrés par ce qu'on nomme le Grand Chiffre du roi Louis XIV, et qui n'était en principe utilisé que pour des communications d'une importance extrême. C'est dire l'intérêt pour les historiens de connaître le contenu de ces documents, ou même simplement le sujet dont ils parlaient. Hélas, faute d'information même statistique sur la nature des textes, et de connaissance ne serait-ce que de quelques mots de leur contenu, ils durent attendre longtemps la solution de ce mystère. Vers 1893, Étienne Bazeries les en délivra finalement après presque deux siècles de perplexité.

    Lors de la
    Première Guerre mondiale


    Pendant la guerre de 14-18, la cryptographie prit un essor considérable. La maîtrise cryptographique des Français les aident considérablement à déchiffrer les messages ennemis, leur procurant un avantage très important sur l'ennemi. Un lieutenant aurait quasiment réussi à lui seul à changer le cours de l'histoire. Évoquant ce lieutenant, Clemenceau aurait prétendu qu'à lui tout seul il valait un corps d'armée. La rapidité des transmissions a bénéficié des progrès du XIXe siècle, et est désormais instantanée, mais le déchiffrage des messages codés, réalisé à la main, reste très lent, souvent plusieurs heures.

    Lors de la
    Seconde Guerre mondiale


    La cryptologie a joué un rôle décisif pendant la Seconde Guerre mondiale. Les exploits des alliés en matière de cryptologie auraient permis d'écourter la guerre (de un à deux ans, selon certains spécialistes). Churchill citait la cryptographie comme l'un des facteurs clefs de la victoire.

    La machine Enigma

    Inventée pour les civils

    L'histoire de la machine Enigma commence en 1919, quand un ingénieur hollandais, Hugo Alexander, dépose un brevet de machine à chiffrer électromécanique. Ses idées sont reprises par le Dr Arthur Scherbius, qui crée à Berlin une société destinée à fabriquer et à commercialiser une machine à chiffrer civile : l'Enigma. Cette société fait un fiasco, mais la machine Enigma a attiré l'attention des militaires.

    Le fonctionnement d'Enigma
    Le codage effectué par la machine Enigma est à la fois simple et astucieux. Chaque lettre est remplacée par une autre, l'astuce est que la substitution change d'une lettre à l'autre. La machine est alimentée par une pile électrique. Quand on appuie sur une touche du clavier, un circuit électrique est fermé, et une lampe s'allume qui indique quelle lettre codée l'on substitue. Concrètement, le circuit électrique est constitué de plusieurs éléments en chaîne :

    • le tableau de connexions : il permet d'échanger des paires de l'alphabet, deux à deux, au moyen de fiches. Il y a 6 fiches qui permettent donc d'échanger 12 lettres. Un tableau de connexions est donc une permutation très particulière où on a échangé au plus 6 paires. Par exemple, dans le tableau suivant (avec simplement 6 lettres), on a échangé A et C, D et F, tandis que B et E restent invariants.

    • les rotors : un rotor est également une permutation, mais cette fois quelconque. À chaque lettre en entrée correspond une autre lettre.

    On peut composer les rotors, c'est-à-dire les mettre les uns à la suite des autres. La machine Enigma disposera, au gré de ses évolutions successives, de 3 à 6 rotors. Parmi ces rotors, seuls 3 sont utilisés pour le codage, et on a le choix de les placer dans l'ordre que l'on souhaite (ce qui constituera une partie de la clé). Surtout, les rotors sont cylindriques, et ils peuvent tourner autour de leur axe. Ainsi, à chaque fois qu'on a tapé une lettre, le premier rotor tourne d'un cran, et la permutation qu'il engendre est changée. Observons ce changement sur la figure suivante : le rotor transforme initialement D en B. Lorsqu'il tourne d'un cran, cette liaison électrique DB se retrouve remontée en CA.

    Chaque rotor possède donc 26 positions. À chaque fois qu'une lettre est tapée, le premier rotor tourne d'un cran. Après 26 lettres, il est revenu à sa position initiale, et le second rotor tourne alors d'un cran. On recommence à tourner le premier rotor, et ainsi de suite... Quand le second rotor a retrouvé sa position initiale, c'est le troisième rotor qui tourne d'un cran.

    • Le réflecteur : Au bout des 3 rotors se situe une dernière permutation qui permet de revenir en arrière. On permute une dernière fois les lettres 2 par 2, et on les fait retraverser les rotors, et le tableau de connexion.

    Résumons sur la machine simplifiée suivante (6 lettres, 2 rotors) comment est codée la lettre A :

    • on traverse le tableau de connexions : on obtient C
    • on traverse les 2 rotors : on obtient successivement A et F
    • on traverse le réflecteur où on obtient E, puis on renvoie dans les rotors pour obtenir F, A et finalement C après le tableau de connexions.

    Remarquons que si on avait tapé C, le courant aurait circulé dans l'autre sens et on aurait obtenu A.


    Nombre de clés possibles
    Il y a trois éléments à connaître pour pouvoir coder un message avec la machine Enigma :

    1. la position des 6 fiches du tableau de connexion : d'abord, il faut choisir 12 lettres parmi 26. C'est donc le nombre de combinaisons de 12 parmi 26, soit 26! /(12!14!) = 9 657 700. Maintenant, il faut choisir 6 paires de lettres parmi 12, soit 12 !/6 !, et comme la paire (A, B) donne la même connexion que la paire (B, A), il faut encore diviser par 2[SUP]6[/SUP]. On trouve finalement 100 391 791 500.
    2. l'ordre des rotors : il y a autant d'ordres que de façons d'ordonner 3 éléments : 3 !=6.
    3. la position initiale des rotors : chaque rotor ayant 26 éléments, il y a 26*26*26=17 576 choix.
    On multiplie tout cela, et on obtient plus de 10[SUP]16[/SUP] possibilités, ce qui est énorme pour l'époque !

    Il est important de remarquer que les permutations employées dans les rotors et les réflecteurs ne peuvent pas être considérées comme faisant partie du secret. En effet, toutes les machines utilisent les mêmes, et il suffit donc d'en avoir une à disposition. Les Britanniques, par exemple, en ont récupéré une pendant la guerre dans un sous-marin coulé. Ceci est une illustration d'un principe général en cryptographie, dit principe de Kerckhoffs, qui veut que tout le secret doit résider dans la clé secrète de chiffrement et de déchiffrement, et pas dans une quelconque confidentialité de l'algorithme (ici de la machine) qui ne peut être raisonnablement garantie.


    Points forts et faiblesses
    Nous avons déjà décrit les points forts de la machine Enigma. Pour l'essentiel, c'est le nombre de clés énorme, et la réversibilité : si, avec la même clé secrète initiale, on tape le message clair, on obtient le message codé, et avec le message codé, on obtient le message clair.

    L'une des failles de la machine Enigma est que jamais la lettre A ne sera codée par un A. Cela élimine un certain nombre de cas à inspecter. Une des autres faiblesses dépend plutôt du protocole utilisé par les Allemands : certains opérateurs - par exemple, ceux qui informaient de la météo - prenaient peu de précautions et commençaient toujours leurs messages par les mêmes mots (typiquement «Mon général…»). Les Britanniques connaissaient ainsi pour une partie du message à la fois le texte clair et le texte codé, ce qui aide à retrouver la clé. Et comme c'est la même clé qui sert pour toutes les machines Enigma de l'armée allemande pour un jour donné, une erreur de protocole dans un message peut compromettre la sécurité de tous les autres !

    Le déchiffrement des messages Enigma
    Le service de renseignements polonais fut, semble-t-il, le premier à réellement travailler à «casser» le code allemand dans les années 1930. Ils travaillèrent ensuite en collaboration avec le service cryptographique du 2[SUP]e[/SUP] bureau français, dirigé par le colonel Gustave Bertrand, aidés dans cette tâche par les informations fournies par la taupe française Hans Thilo Schmidt («Asche» pour les services français). Finalement, une collaboration s'instaure avec les services britanniques, qui rassemblèrent leurs spécialistes (en particulier Alan Turing) cryptographes à Bletchley Park.

    La Kriegsmarine ayant mis au point une Enigma modifiée, ce n'est que vers 1942, après la capture d'une machine modifiée sur un U-boot, que les alliés purent connaître la teneur des messages codés de la marine allemande. La machine utilisée pour décoder les messages chiffrés avec la machine Enigma était appelée «la Bombe». Les auxiliaires de la marine s'occupaient tout d'abord de régler « la Bombe », ce qui prenait environ une demi-heure. Puis le décodage lui-même du message prenait encore environ 11 minutes. Trois à quatre mille messages étaient déchiffrés chaque jour par les 9 000 personnes travaillant à Bletchley Park.


    Enigma et UNIX
    Un étudiant s'amusa un jour à programmer en langage C la simulation du fonctionnement d'une machine Enigma. Ce programme fut inclus dans les distributions UNIX sous le nom de crypt (utilisable comme une commande UNIX). Jusqu'à la déclassification des travaux du groupe de Bletchley Park, les bureaux d'études d'engineering croyaient ce codage très sûr et l'utilisaient pour échanger leurs informations confidentielles. Pour la plus grande joie de la National Security Agency qui voyait son travail considérablement facilité.

    Le code Lorenz
    Le code des hauts dirigeants allemands
    Si la machine Enigma est la plus connue, le code Lorenz a conduit à des retombées encore plus importantes aujourd'hui. Ce code était utilisé par la haute hiérarchie allemande pour sécuriser les communications des dirigeants.

    Inverser le code
    Strictement, le chiffrement d'Enigma n'a pas été «cracké». Les Allemands l'utilisaient mal, parfois très mal, suffisamment pour que la recherche de la clef unique parmi toutes les clefs devienne possible. Cette attaque, la force brute, vaincra tous les chiffrements. Un chiffrement n'est «cracké» que lorsqu'il existe mieux que la force brute pour l'inverser.
    Au contraire, le code Lorenz a bel et bien été «cracké». Ainsi, sans retrouver la clef de chiffrement, le texte clair était recalculé depuis le texte chiffré.

    L'analyse du code Lorenz
    Le code Lorenz pratiquait le chiffrement par flot (stream cipher). Ce type de chiffrement a une faiblesse mortelle : il devient trivial à inverser lorsque deux messages sont chiffrés avec la même clef.

    En considérant que A est le texte clair, B est la clef, le message chiffré A' = A + B Si deux messages sont chiffrés avec la même clef, A' = A + B et C' = C + B, il suffit de faire l'addition des deux textes chiffrés pour éliminer la clef.
    A' + C' = ( A + B )+ ( C + B ) = ( A + C ) + ( B + B ) = A + C puisque B + B = 0.

    Puisque tous les effets de la clef sont maintenant retirés, il ne reste qu'à faire une analyse statistique pour «séparer» les deux textes A et C et retrouver ainsi chacun d'eux. La clef devient aussi triviale à calculer (elle est égale à A' + A).

    C'est cette seule et unique faiblesse qui a détruit tout le code.

    Un opérateur a transmis un long message pour recevoir en réponse un NACK (message non reçu). Plutôt que de respecter les règles et produire une nouvelle clef, il a repris la même clef et a renvoyé son message. S'il avait renvoyé exactement le même texte lettre par lettre, l'attaque n'aurait pas été possible. Par contre, en utilisant un diminutif ici et un synonyme là, il a techniquement envoyé ce second message chiffré avec la même clef.

    Après avoir retrouvé les deux messages et la clef unique, celle-ci a révélé ses secrets. La technique utilisée codait les lettres sur cinq bits où chaque bit traversait un canal de chiffrement différent. La clef a montré certaines répétitions. De celles-ci a été déduit tout le principe de la génération de la clef et celui de la machine Lorenz. Une autre distinction entre Enigma et Lorenz est que les alliés avaient été en possession d'une machine Enigma avant la guerre et en avaient obtenu d'autres pendant. Au contraire, les alliés ne virent une authentique machine Lorenz qu'après la fin de la guerre.

    La faiblesse du code Lorenz
    Si le mécanisme de génération de clef de Lorenz était maintenant connu, il ne suffisait pas à inverser les autres messages chiffrés. De plus, l'analyse statistique de la clef montrait que celle-ci resterait aléatoire sur chaque canal même si elle était contrôlée par des paramètres non aléatoires comme la prépondérance de certaines lettres dans une langue.

    Une faiblesse dans le code Lorenz a malgré tout été trouvée. Deux lettres consécutives identiques produisaient un résultat constant sur chacun des 5 canaux dans le texte chiffré. Un exemple est le doublon «SS», en plus de ceux imposés par la langue.

    La conséquence du code Lorenz
    Si une faiblesse était trouvée, l'exploiter était autre chose. En effet, l'analyse statistique nécessaire pour retrouver ces doublons demandait une puissance inexistante pour l'époque. C'est à ce moment que fut développée l'arme ultime pour le chiffrement, l'ordinateur. Colossus, le premier ordinateur, a ainsi été construit.

    C'est donc avec Colossus que le code Lorenz a pu être inversé. Les détails de ses algorithmes débordent toutefois les objectifs de cette section.

    En plus de léguer l'ordinateur, l'attaque du code Lorenz, tout comme celle d'Enigma, a fait une énorme différence dans la guerre. Dire qu'elle a raccourci la guerre de un an ou même fait la différence entre victoire et défaite n'est pas que spéculation. La meilleure formulation a été faite par un Allemand après qu'il apprit l'existence du programme de déchiffrement des alliés. Il affirma que la différence apportée par le déchiffrement est que la bombe nucléaire a explosé au Japon plutôt qu'en Allemagne.

    Les
    Navajos


    Bien que les moyens de chiffrements électromécaniques, tels que la machine Enigma, aient prouvé leur efficacité en termes de sécurité, ils n'en restent pas moins encombrants et lents car nécessitant une double saisie des messages. Ces deux inconvénients majeurs rendant ce procédé quasiment inexploitable en milieu hostile, ils poussèrent les Américains à chercher un moyen de chiffrement assurant une communication efficace sur le terrain lors de la guerre qui les opposa aux Japonais.

    Ce procédé fut imaginé par l'ingénieur américain Philip Johnston. Ce dernier ayant grandi dans les réserves navajos, il eut l'idée d'utiliser leur langue comme procédé cryptographique. La méconnaissance quasi totale de cette langue ainsi que sa construction grammaticale très particulière, la rendant impénétrable aux étrangers, décidèrent de son utilisation.

    Cependant un problème majeur demeurait : les mots usuels employés par l'armée n'existaient pas dans la langue navajo. Il fut donc décidé de trouver une correspondance entre des mots navajos et le dialecte militaire. Cette table de correspondance fut établie par association d'idées afin de la rendre plus facilement mémorisable. Le terme «bombardier» fut par exemple traduit par «buse» alors que les «bombes» larguées par ces engins devenaient des «œufs» dans la langue navajo.

    Voilà comment les Parleurs-de-code (Windtalkers) navajos prirent part à la guerre du Pacifique. Leur bravoure au combat fut reconnue de manière officielle par le gouvernement américain lorsqu'il leur dédia, en 1982, la journée du 14 août.

    __________________________________________
     
  10. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113

    Le chiffre de César



    [​IMG]


    Principe du chiffre de César
    Description : English: Caesar cipher with a shift of 3.
    Date : 2006.10.01
    Source : Travail personnel
    Auteur : Cepheus
    Moi, propriétaire du copyright de cette œuvre, la place dans le domaine public.
    Ceci s'applique dans le monde entier.
    Dans certains pays, ceci peut ne pas être possible ; dans ce cas :
    J'accorde à toute personne le droit d'utiliser cette œuvre dans n'importe quel but,
    sans aucune condition, sauf celles requises par la loi.

    _____________________________


    Chiffrement par décalage


    En cryptographie, le chiffrement par décalage, aussi connu comme le chiffre de César, est une méthode de chiffrement très simple utilisée par Jules César dans ses correspondances secrètes (ce qui explique le nom «chiffre de César»).

    Le texte chiffré s'obtient en remplaçant chaque lettre du texte clair original par une lettre à distance fixe, toujours du même côté, dans l'ordre de l'alphabet. Pour les dernières lettres (dans le cas d'un décalage à droite), on reprend au début. Par exemple avec un décalage de 3 vers la droite, A est remplacé par D, B devient E, et ainsi jusqu'à W qui devient Z, puis X devient A etc. Il s'agit d'une permutation circulaire de l'alphabet. La longueur du décalage, 3 dans l'exemple évoqué, constitue la clé du chiffrement qu'il suffit de transmettre au destinataire — s'il sait déjà qu'il s'agit d'un chiffrement de César — pour que celui-ci puisse déchiffrer le message. Dans le cas de l'alphabet latin, le chiffre de César n'a que 26 clés possibles (y compris la clé nulle, qui ne modifie pas le texte).

    Il s'agit d'un cas particulier de chiffrement par substitution monoalphabétique : ces substitutions reposent sur un principe analogue, mais sont obtenues par des permutations quelconques des lettres de l'alphabet. Dans le cas général, la clé est donnée par la permutation, et le nombre de clés possibles est alors sans commune mesure avec celui des chiffrements de César.

    Le chiffrement de César a pu être utilisé comme élément d'une méthode plus complexe, comme le chiffre de Vigenère. Seul, il n'offre aucune sécurité de communication, à cause du très faible nombre de clés, ce qui permet d'essayer systématiquement celles-ci quand la méthode de chiffrement est connue, mais aussi parce que, comme tout encodage par substitution monoalphabétique, il peut être très rapidement «cassé» par analyse de fréquences (certaines lettres apparaissent beaucoup plus souvent que les autres dans une langue naturelle).

    Exemple


    Le chiffrement peut être représenté par la superposition de deux alphabets, l'alphabet clair présenté dans l'ordre normal et l'alphabet chiffré décalé, à gauche ou à droite, du nombre de lettres voulu. Nous avons ci-dessous l'exemple d'un encodage de 3 lettres vers la droite. Le paramètre de décalage (ici 3) est la clé de chiffrement :


    [​IMG]

    Pour encoder un message, il suffit de regarder chaque lettre du message clair, et d'écrire la lettre encodée correspondante. Pour déchiffrer, on fait tout simplement l'inverse.

    [​IMG]

    Le chiffrement peut aussi être représenté en utilisant les congruences sur les entiers. En commençant par transformer chaque lettre en un nombre (A = 0, B = 1,..., Z = 25), pour encoder une lettre avec une clé n il suffit d'appliquer la formule :

    [​IMG]Le déchiffrement consiste à utiliser la clé opposée ([​IMG] à la place de [​IMG]) :
    [​IMG]On peut s'arranger pour que le résultat soit toujours représenté par un entier de 0 à 25 : si [​IMG] (respectivement [​IMG]) n'est pas dans l'intervalle [​IMG], il suffit de soustraire (respectivement ajouter) 26.

    Le décalage demeurant toujours le même pour un même message, cette méthode est une substitution monoalphabétique, contrairement au chiffre de Vigenère qui constitue une substitution polyalphabétique.

    Dénominations


    Le chiffrement par décalage possède plusieurs synonymes :

    • le chiffre de César. César utilisait pour ses correspondances un chiffrement par décalage de 3 vers la droite. Selon David Kahn, ce n'est que récemment que l'expression « chiffre de César » désigne les chiffrements par décalage ayant un décalage différent de 3[SUP]3[/SUP] ;
    • la substitution de César ;
    • le terme code de César est un abus de langage : en cryptologie, le chiffre est un procédé systématique, alors qu'un code utilise le symbolisme des mots. À ce sujet, se reporter au chapitre Différence entre chiffre et code de l'article «Chiffre».

    Historique

    César

    Postérieur et plus simple que la scytale, le chiffre de César doit son nom à Jules César qui, selon Suétone l'utilisait avec un décalage de trois sur la droite pour certaines de ses correspondances secrètes, notamment militaires :
    «Il y employait, pour les choses tout à fait secrètes, une espèce de chiffre qui en rendait le sens inintelligible (les lettres étant disposées de manière à ne pouvoir jamais former un mot), et qui consistait, je le dis pour ceux qui voudront les déchiffrer, à changer le rang des lettres dans l'alphabet, en écrivant la quatrième pour la première, c'est-à-dire le d pour le a, et ainsi de suite.»
    Aulu-Gelle confirme l'usage par Jules César de méthodes de chiffrement par substitution :
    «Nous avons un recueil des lettres de J. César à C. Oppius et Balbus Cornelius, chargés du soin de ses affaires en son absence. Dans ces lettres, on trouve, en certains endroits, des fragments de syllabes sans liaison, caractères isolés, qu'on croirait jetés au hasard : il est impossible d'en former aucun mot. C'était un stratagème dont ils étaient convenus entre eux : sur le papier une lettre prenait la place et le nom d'une autre ; mais le lecteur restituait à chacune son nom et sa signification»
    Aulu-Gelle, Nuits attiques, livre XVII, 9

    Bien que César soit le premier personnage connu à utiliser cette technique, on sait que d'autres chiffres par substitution, éventuellement plus complexes, ont été utilisés avant lui, et il n'est donc pas certain qu'il soit le premier à l'avoir conçu, même s'il a pu le réinventer.
    Auguste, son neveu, utilisait aussi un chiffre, consistant en un décalage de un sans boucler à la fin de l'alphabet :

    «Lorsqu'il écrivait en chiffres, il employait le b pour a, le c pour le b, et ainsi de suite pour les autres lettres. Au lieu du z il mettait deux a.»
    Toujours suivant les écrits d'Aulu-Gelle, on peut penser que Jules César utilisait d'autres clés, et même d'autres techniques de chiffrement plus complexes. En particulier Aulu-Gelle fait référence à un traité (aujourd’hui perdu) consacré aux chiffres utilisés par César.
    On ignore quelle était l'efficacité du chiffre de César à son époque. La première trace de techniques de cryptanalyse date du IX[SUP]e[/SUP] siècle avec le développement dans le monde arabe de l'analyse fréquentielle.


    Utilisations


    Un chiffre de César, avec un décalage de un, apparaît au dos du Mezuzah.
    AuXIX[SUP]e[/SUP] siècle, les pages d'annonces personnelles des journaux étaient parfois utilisées pour la transmission de messages cryptés à l'aide de codes simples. David Kahn donne des exemples d'amants communiquant de manière confidentielle en chiffrant leurs messages à l'aide du chiffre de César dans le quotidien britannique The Times. Le chiffre de César fut encore employé en 1915 : l'armée russe le préférait à d'autres codes plus élaborés mais qui s'étaient révélés trop difficiles d'utilisation pour leurs troupes ; les analystes allemands et autrichiens eurent peu de mal à déchiffrer leurs messages. Le codage utilisé par Enigma se base aussi sur la substitution des lettres, mais en suivant une méthode beaucoup plus complexe.


    Utilisations modernes

    Aujourd'hui, on peut trouver le chiffre de César dans des jouets promotionnels pour enfants. Les livres-jeu emploient souvent cette méthode, avec un décalage de un ou deux dans un sens ou dans l'autre, pour donner des indications sans rendre le jeu trop facile.
    Plusieurs cas particuliers ont été nommés par jeux de mots : «avocat» (A vaut K), «cassis» (K 6) et «cassette» (K 7). Typiquement, un jeu pour enfant peut impliquer de décoder un message, en donnant un indice contenant le mot «avocat».
    Un tel code avec un décalage de13 caractères est aussi employé dans l'algorithme ROT13 : cette méthode très simple est utilisée dans certains forums sur Internet pour brouiller tout ou partie d'un texte (comme la chute d'une blague, ou un spoiler), mais pas comme méthode de chiffrement en tant que tel.

    En avril 2006, le chef en fuite de la mafia Bernardo Provenzano a été capturé en Sicile grâce notamment au déchiffrement d'une partie de sa correspondance qui utilisait une variante du chiffrement de César basée sur les nombres : A s'écrivait 4, B 5, etc.


    Décryptage


    Le chiffre de César peut être cassé très facilement, même à l'aide du seul texte chiffré. On peut distinguer deux cas :

    • le cryptanalyste a connaissance du fait qu'un simple chiffrement par substitution a été employé, mais ignore qu'il s'agit du chiffre de César en particulier ;
    • le cryptanalyste sait que le chiffre de César a été utilisé, mais ignore la valeur du décalage.

    Par recherche de la méthode de chiffrement
    Dans le premier cas, il est possible de casser le chiffre de César à l'aide des mêmes techniques que dans le cas général d'un chiffrement par substitution, à savoir l'analyse fréquentielle ou la recherche de mots probables. Lors de la résolution, le cryptanalyste ne sera pas sans remarquer une certaine régularité dans les décalages, et en déduira que l'algorithme employé est le chiffre de César.

    Par recherche de la valeur du décalage

    [​IMG]

    Dans le deuxième cas, comme il n'y a qu'un nombre limité de décalages (vingt six dont un inutile), il suffit de tester tous les chiffrements possibles jusqu'à trouver le bon. C'est ce qu'on appelle une attaque par force brute, technique de test de toutes les combinaisons possibles. Une méthode simple pour mener l'attaque est de prendre un fragment du texte crypté et d'écrire dans un tableau tous les décalages possibles (voir le tableau ci-dessus). Dans ce tableau, on a pris le fragmentGVCTX SKVEQ QI ; le texte en clair apparaît ainsi facilement à la quatrième ligne. Une autre façon de procéder serait d'écrire toutes les lettres de l'alphabet, en dessous de chaque lettre du fragment, et en commençant par celle-ci. Ce genre d'attaque peut être accélérée en utilisant des bandes avec l'alphabet écrit dessus ; les bandes étant placées en colonne sur le texte chiffré (lettre sur lettre : par exemple, le «E» de la bande doit être placé au-dessus du «E » du texte chiffré), la phrase en clair doit apparaître sur une des lignes.

    Analyse fréquentielle

    [​IMG]


    Une autre attaque possible est de faire une analyse de fréquence d'apparition des lettres : on génère un graphique sur la fréquence d'apparition de chaque lettre dans le texte crypté et un autre avec un texte de référence, dans la langue du message d'origine, et on explore par décalages successifs toutes les possibilités. En les comparant, un humain peut facilement voir la valeur du décalage entre ces deux graphiques, et trouver la clé de chiffrement. Cette technique s'appelle l'analyse fréquentielle. Par exemple, en anglais, les lettres E et T sont les plus fréquentes et les lettres Q et Z, les moins fréquentes. Des ordinateurs peuvent aussi faire ce travail de reconnaissance en évaluant la concordance de distribution des deux textes (le texte chiffré et celui de référence) en utilisant, par exemple, une fonction test du χ² de Pearson.

    Avec des textes longs, il est très probable qu'il n'y ait qu'une seule possibilité de déchiffrement. Mais pour de courts textes, il peut y avoir plusieurs possibilités de déchiffrement. Par exemple, «NYHCL» peut être déchiffré en «grave» (par un décalage de 19) ou en «tenir» (6) (pour un texte en français) ; ou alors «DQODG» peut donner «bombe» (24) ou « recru » (14) (voir aussi : distance d'unicité).

    Composition de chiffrements

    Enchaîner les chiffrements (et les déchiffrements) ne donne pas de protection supplémentaire car chiffrer un texte avec un décalage de trois sur la gauche, puis le chiffrer de nouveau avec un décalage de sept sur la droite revient exactement au même que de coder le texte de départ avec un décalage de quatre sur la droite ([​IMG]). En termes mathématiques, l'ensemble des vingt-six opérations de chiffrement (en comprenant le décalage nul c'est-à-dire le texte chiffré identique au texte clair) est stable par composition. Il forme même un groupe, puisque, de plus, une opération de déchiffrement est identique à une opération de chiffrement.

    __________________________________

    Le chiffre de Vigenère

    Le chiffre de Vigenère est un système de chiffrement polyalphabétique, c'est un chiffrement par substitution, mais une même lettre du message clair peut, suivant sa position dans celui-ci, être remplacée par des lettres différentes, contrairement à un système de chiffrement monoalphabétique comme le chiffre de César (qu'il utilise cependant comme composant). Cette méthode résiste ainsi à l'analyse de fréquences, ce qui est un avantage décisif sur les chiffrements monoalphabétiques. Cependant le chiffre de Vigenère a été cassé par le major prussien Friedrich Kasiski qui a publié sa méthode en 1863. Il n'offre plus depuis cette époque aucune sécurité.

    Il est nommé ainsi au XIX[SUP]e[/SUP] siècle en référence au diplomate du XVI[SUP]e[/SUP] siècle Blaise de Vigenère, qui le décrit (intégré à un chiffrement plus complexe) dans son traité des chiffres paru en 1586. On trouve en fait déjà une méthode de chiffrement analogue dans un court traité de Giovan Battista Bellaso paru en 1533.


    Le chiffre de Vigenère utilise le chiffre de César mais avec un décalage différent suivant la position de la lettre décalée dans le texte ; la valeur de ce décalage est définie à l'aide d'un mot-clé, chaque lettre du mot-clé désigne le décalage correspondant à sa position dans l'alphabet (0 pour A, 1 pour B etc.). Si la longueur du mot clé est n, toutes les lettres du texte clair en position un multiple de n sont décalées suivant le même entier, de même pour celles en position un multiple de n plus 1, etc. L'utilisation de plusieurs décalages différents rend inopérante l'analyse fréquentielle classique, du moins directement. Des méthodes statistiques plus avancées, utilisant l'indice de coïncidence, permettent cependant de casser le code (voir aussi cryptanalyse du chiffre de Vigenère) .
    On peut voir le chiffrement de Vernam (ou «masque jetable») comme un chiffre de Vigenère où le mot-clé est de même longueur que le texte à chiffrer, choisi de façon complètement aléatoire, et utilisé une seule fois. Il est alors théoriquement incassable, mais difficile à utiliser en pratique.

    Principe du chiffrement


    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.

    - La table de Vigenère

    L'outil indispensable du chiffrement de Vigenère est la «table de Vigenère»
    Table de Vigenère
    Table en clair​
    [​IMG]


    - Chiffrement

    Pour chaque lettre en clair, on sélectionne la colonne correspondante et pour une lettre de la clé on sélectionne la ligne adéquate, puis au croisement de la ligne et de la colonne on trouve la lettre chiffrée. La lettre de la clé est à prendre dans l'ordre dans laquelle elle se présente et on répète la clé en boucle autant que nécessaire.
    clé : MUSIQUE
    texte : j'adore ecouter la radio toute la journee

    [​IMG]

    Le texte chiffré est alors :
    V'UVWHY IOIMBUL PM LSLYI XAOLM BU NAOJVUY.


    Si on veut déchiffrer ce texte, on regarde pour chaque lettre de la clé répétée la ligne correspondante et on y cherche la lettre chiffrée. La première lettre de la colonne que l'on trouve ainsi est la lettre déchiffrée.
    [​IMG]


    - Principe mathématique

    Mathématiquement, on identifie les lettres de l'alphabet aux nombres de de 0 à 25 (A=0, B=1 ...). Les opérations de chiffrement et de déchiffrement sont, pour chaque lettre, celles du chiffre de César. En désignant la i-ème lettre du texte clair par Texte, la i-ème du chiffré par Chiffré, et la i-ème lettre de la clé, répétée suffisamment de fois, par Clés, elle se formalise par :

    • Chiffré = (Texte + Clés) modulo 26
      [*]Texte = (Chiffré - Clés) modulo 26

    où x modulo 26 désigne le reste de la division entière de x par 26. Pour le chiffrement il suffit d'effectuer l'addition des deux lettres puis de soustraire 26 si le résultat dépasse 26. Pour le déchiffrement il suffit d'effectuer la soustraction et d'additionner 26 si le résultat est négatif. Le déchiffrement est aussi une opération identique à celle du chiffrement pour la clé obtenue par Clé' = 26 - Clé. Un disque à chiffrer (en), qui utilise une représentation circulaire de l'alphabet (après Z on a A), permet de réaliser directement cette opération.
    Le chiffré d'un texte suffisamment long constitué uniquement de A donne la clé ( 0 + x = x, soit A + Clés = Clés ).

    Cryptanalyse


    Si l'on connait le nombre de symboles que comporte la clé, il devient possible de procéder par analyse de fréquences sur chacun des sous-textes déterminés en sélectionnant des lettres du message clair à intervalle la longueur de la clef (autant de sous-textes que la longueur de la clef). C'est l'attaque bien connue sur les chiffrements mono-alphabétiques.

    Friedrich Kasiski publie en 1863 une méthode efficace pour déterminer la taille de la clef, le test de Kasiski, en repérant la répétition de certains motifs dans le message chiffré. Charles Babbage s'est intéressé au chiffrement de Vigenère une dizaine d'année auparavant. Il avait décrypté dans des cas particuliers des messages chiffrés par la méthode de Vigenère. Il n'a rien publié à ce sujet, mais on dispose de ses notes. On ne sait pas quelle méthode il a utilisé, il a pu exploiter des faiblesses de l'utilisation du chiffrement. Certains historiens pensent qu'il a pu découvrir la méthode de Kasiski, bien qu'il n'en ait pas laissé de trace écrite.

    Des techniques statistiques fondées sur l'indice de coïncidence, découvertes au XX[SUP]e[/SUP] siècle, s'avèrent encore plus efficaces pour casser le chiffre.


    Variantes


    Le chiffre de Vigenère a été réinventé de nombreuse fois au cours de siècles et il a existé plusieurs variantes. Il n'est pas indispensable d'utiliser un décalage comme substitution alphabétique, n'importe quelle permutation des lettres de l'alphabet convient. L'avantage du chiffre de César est d'être entièrement déterminé par la lettre qui donne le décalage. Mais, avant Vigenère, Giovan Battista Bellaso avait proposé un tel système (repris par le physicien Giambattista della Porta qui s'en inspire sans citer Beloso), où chacun des correspondants dispose d'une même grille qui donne une suite de permutations de l'alphabet chacune associée à une ou plusieurs lettres. Chiffrement et déchiffrement demandent la grille et un mot clef. Les lettres du mot clef sont utilisées de la même façon que pour le chiffrement de Vigenère, mais indiquent l'une des permutations de la grille et non un décalage. A priori, la connaissance de la grille ne permet pas à elle seule de déchiffrer le message, puisqu'il faut le mot clef. Cependant le chiffrement est susceptible des mêmes attaques que celui de Vigenère.
    Le système a connu d'autres variantes comme le chiffre de Beaufort.


    Le chiffre de Vigenère en littérature




    _______________________________________
    Nom de la page : Chiffrement par décalage
    Contenu soumis à la licence CC-BY-SA 3.0.
    Source : Article Chiffrement par décalage de Wikipédia en français (auteurs)

    _______________________________________

    Voir aussi :
    Cryptanalyse du chiffre de Vigenère.

     
  11. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113



    Cryptographie symétrique



    La cryptographie symétrique, également dite à clé secrète (par opposition à la cryptographie à clé publique), est la plus ancienne forme de chiffrement. On a des traces de son utilisation par les Égyptiens vers 2000 av. J.-C. Plus proche de nous, on peut citer le chiffre de Jules César, dont le ROT13 est une variante.


    Clé et sécurité

    L'un des concepts fondamentaux de la cryptographie symétrique est la clé. Une clé est une donnée qui (traitée par un algorithme) permet de chiffrer et de déchiffrer un message. Toutes les méthodes de cryptage n'utilisent pas de clé. Le ROT13, par exemple, n'a pas de clé. Quiconque découvre qu'un message a été codé avec cet algorithme peut le déchiffrer sans autre information. Une fois l'algorithme découvert, tous les messages chiffrés par lui deviennent lisibles.

    Si l'on modifiait le ROT13 en rendant le décalage variable, alors la valeur de ce décalage deviendrait une clé, car il ne serait plus possible de chiffrer et déchiffer sans elle. L'ensemble des clés possibles comporterait alors 26 décalages.

    Cet exemple montre le rôle et l'importance de la clé dans un algorithme de chiffrement ; et les restrictions qu'elle implique. Auguste Kerckhoffs (La cryptographie militaire, 1883) énonce le principe de Kerckhoffs : pour être sûr, l'algorithme doit pouvoir être divulgué. En outre, il faut aussi que la clé puisse prendre suffisamment de valeurs pour qu'une attaque exhaustive — essai systématique de toutes les clés — soit beaucoup trop longue pour être menée à bien. Cela s'appelle la sécurité calculatoire.


    Cette sécurité calculatoire s'altère avec le progrès technique, et la puissance croissante des moyens de calcul la fait reculer constamment. Exemple : le DES, devenu obsolète à cause du trop petit nombre de clés qu'il peut utiliser (pourtant 2[SUP]56[/SUP]). Actuellement, 2[SUP]80[/SUP] est un strict minimum. À titre indicatif, l'algorithme AES, dernier standard d'algorithme symétrique choisi par l'institut de standardisation américain NIST en décembre 2001, utilise des clés dont la taille est au moins de 128 bits soit 16 octets, autrement dit il y en a 2[SUP]128[/SUP]. Pour donner un ordre de grandeur sur ce nombre, cela fait environ 3,4×10[SUP]38[/SUP] clés possibles ; l'âge de l'univers étant de 10[SUP]10[/SUP] années, si on suppose qu'il est possible de tester 1 000 milliards de clés par seconde (soit 3,2×10[SUP]19[/SUP] clés par an), il faudra encore plus d'un milliard de fois l'âge de l'univers. Dans un tel cas, on pourrait raisonnablement penser que notre algorithme est sûr. Toutefois, l'utilisation en parallèle de très nombreux ordinateurs, synchronisés par internet, fragilise la sécurité calculatoire.

    Cette notion de sécurité calculatoire pose la question de la sécurité absolue. On sait depuis Claude Shannon et son article Communication theory of secrecy system (1949) que le chiffrement de Gilbert Vernam qui consiste à ajouter au message en clair une clé de la même longueurest parfaitement sûr. C'est le seul pour lequel nous soyons capables de prouver une telle chose. L'inconvénient est que pour chiffrer un message de n bits, il faut au préalable avoir échangé une clé de n bits avec le destinataire du message, et cela par une voie absolument sûre, sinon chiffrer devient inutile. Très peu de cas nécessitent un tel système, mais c'était toutefois le système utilisé pour le Téléphone rouge entre le Kremlin et la Maison-Blanche.

    Petite taxinomie du chiffrement symétrique classique


    Jusqu'aux communications numériques, les systèmes utilisaient l'alphabet et combinaient substitutions — les symboles sont changés mais restent à leur place — et transpositions — les symboles ne sont pas modifiés mais changent de place.

    La substitution est dite monoalphabétique quand l'algorithme de codage n'utilise aucun autre paramètre que la lettre à coder, de sorte qu'une lettre est toujours remplacée par la même lettre (relation 1→1). C'est le cas d'un algorithme à décalage simple. Quand l'algorithme de codage utilise un (ou plusieurs) autre(s) paramètre(s) (ex: sa position dans le message), chaque lettre à coder peut alors être remplacée par plusieurs lettres différentes selon les cas (relation 1→n). On parle alors de substitution polyalphabétique — e.g. le chiffre de Vigenère, Enigma.


    La substitution peut utiliser la méthode du décalage, où chaque lettre est transformée en la lettre n positions plus loin dans l'alphabet, en rebouclant, i.e. la lettre suivant 'z' est 'a'. On parle de décalage simple — est également connu sous le nom de chiffre de Jules César - quand le décalage est identique pour toutes les lettres du message. Avec le chiffre de Blaise de Vigenère, on applique un nombre quelconque n de décalages, le premier décalage est utilisé pour chiffrer la lettre numéro 1, puis la 1+n, 1+2n, … le second décalage pour la lettre numéro 2, 2+n, 2+2n, … Usuellement, la valeur de ces décalages est donnée par un mot de longueur n dont la i[SUP]e[/SUP] lettre donne la valeur du i[SUP]e[/SUP] décalage. Clarifions par un exemple.

    [​IMG]

    Un 'a' dans le mot clé correspond à un décalage de 0, un 'b' à un décalage de 1, etc. Dans notre exemple, la clé a 6 lettres, donc les lettres 1 ('w') et 7 ('d') sont chiffrées par le même décalage, à savoir 2.

    La machine Enigma utilisée par les Allemands durant la Seconde Guerre mondiale est également basée sur les substitutions, mais avec un mécanisme beaucoup plus sophistiqué.

    Une autre forme de la substitution est le dictionnaire : au lieu de changer les symboles du message un a un, ce sont des mots entiers que l'on remplace.

    Pour les transpositions on modifie l'ordre des symboles du texte clair. Une technique consiste à se donner un mot clé, à écrire le message sous ce mot clé et à lire le texte en colonne, par ordre alphabétique.


    [​IMG]

    Les astérisques sont ajoutés pour le déchiffrement et les espaces dans le message chiffré uniquement pour la lisibilité. Le message, s'il était par exemple envoyé à un destinataire qui connaît le mot clé, serait le suivant :

    [​IMG]

    Techniques modernes


    Depuis l'avènement du numérique, les paradigmes du chiffrement symétrique ont bien changé. D'une part, la discipline s'est formalisée, même si la conception de système de chiffrement garde inévitablement un aspect artisanal. En effet dans ce domaine, la seule chose que l'on sache prouver est la résistance face à des types d'attaques connues, pour les autres… D'autre part, la forme du texte chiffré ayant changé, les méthodes ont suivi. Les algorithmes modernes chiffrent des suites de bits.

    On distingue deux types d'algorithmes, les algorithmes en blocs, qui prennent [​IMG] bits en entrée et en ressortent [​IMG], et les algorithmes à flots, qui chiffrent bit par bit sur le modèle du chiffre de Vernam. Dans ce dernier cas, l'algorithme engendre une suite de bits qui est ajouté (cf. XOR) à la suite binaire à chiffrer. Les techniques utilisées pour générer la suite que l'on ajoute -- appelée la suite chiffrante -- sont diverses. Elles peuvent utiliser des registres à décalage à rétroaction linéaire, composés de façon non linéaire (par exemple A5/1 ou E0, mais pas RC4 qui est ou a été très répandu) ... ou utiliser un chiffrement par bloc en mode avec un mode opératoire adapté.

    La seconde famille d'algorithmes, ceux en blocs, est en général construite sur un modèle itératif. Ce modèle utilise une fonction [​IMG] qui prend une clé [​IMG] et un message [​IMG] de [​IMG] bits. C'est cette fonction [​IMG] qui est itérée un certain nombre de fois, on parle de nombre de tours. À chaque tour, la clé [​IMG] utilisée est changée et le message que l'on chiffre est le résultat de l'itération précédente.

    [​IMG] ;
    [​IMG] ;
    ...
    [​IMG] ;
    Les clés [​IMG] utilisées sont déduites d'une clé maître [​IMG] qui est la quantité secrète que doivent partager émetteur et destinataire. L'algorithme générant ces clés à partir de [​IMG] est appelé l'algorithme de cadencement de clés.

    Pour qu'un tel système puisse fonctionner, la fonction [​IMG] utilisée doit être une permutation, c'est-à-dire qu'il faut pour toute clé [​IMG] et message [​IMG] pouvoir recalculer [​IMG] à partir de [​IMG], autrement le déchiffrement n'est pas possible et par conséquent on ne dispose pas d'un algorithme utilisable. Formellement, cela signifie qu'il existe une fonction [​IMG] vérifiant
    [​IMG].

    La sécurité d'un tel système repose essentiellement sur deux points, l'algorithme de cadencement de clé et la robustesse de la fonction [​IMG]. Si l'algorithme de cadencement est mal conçu, les [​IMG] peuvent être déductibles les unes des autres, ou mal réparties, … Dire de la fonction [​IMG] qu'elle est robuste signifie qu'on la suppose difficile à inverser sans connaître la clé [​IMG] ayant servi dans le calcul de [​IMG]. En d'autres termes, connaissant seulement [​IMG], [​IMG] et [​IMG], on ne doit pas pouvoir retrouver le message [​IMG], si ce n'est en effectuant une recherche exhaustive de la clé [​IMG], c'est-à-dire en calculant

    1) [​IMG]) ;
    2) [​IMG] ;

    et cela pour toutes les clés [​IMG] jusqu'à ce que l'on en trouve une pour laquelle [​IMG] est égal à [​IMG]. On est alors assuré d'avoir le message [​IMG] qui n'est autre que [​IMG]. Le problème étant que si [​IMG] est constitué de [​IMG] bits, il faut en moyenne [​IMG] essais. En prenant [​IMG] assez grand, on peut être sur que cela n'est pas réalisable en pratique : supposons que l'on puisse essayer 10[SUP]9[/SUP] (un milliard) clés par seconde, soit environ 2[SUP]30[/SUP], il y a 31 557 600 secondes par an, soit 2[SUP]25[/SUP], en conséquence on peut tester 2[SUP]55[/SUP] clés par an. Si on prend pour [​IMG] une valeur de 80 bits, il faudrait 2[SUP]24[/SUP] ans, plus de 1 million d'années.

    Une technique très répandue pour fabriquer des fonctions [​IMG] est celle du schéma de Feistel. Dans ce schéma, le message à chiffrer est découpé en 2 blocs de [SUP]n[/SUP]⁄[SUB]2[/SUB] bits, [​IMG] et le message chiffré est

    [​IMG]
    où le '+' est le XOR est [​IMG] est une fonction quelconque, on n'a plus à supposer que c'est une permutation. En effet, on peut retrouver [​IMG] à partir de la clé [​IMG]

    1) connaissant [​IMG], on connaît [​IMG] qui est sa partie gauche,
    2) on calcule [​IMG],
    3) on ajoute le résultat du calcul précédent à la partie droite de [​IMG], et on retrouve [​IMG],
    cela sans restriction sur [​IMG]. Clairement, dans ce schéma, la robustesse de [​IMG] repose sur la fonction [​IMG].



    _____________________________

    Nom de la page : Cryptographie symétrique
    Contenu soumis à la licence CC-BY-SA 3.0
    .
    sous licence Creative Commons paternité partage à l’identique
    Source : Article Cryptographie symétrique de Wikipédia en français (auteurs)
    _____________________________





     
  12. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113



    Cryptographie asymétrique



    La cryptographie asymétrique, ou cryptographie à clé publique, est une méthode de chiffrement qui s'oppose à la cryptographie symétrique. Elle repose sur l'utilisation d'une clé publique (qui est diffusée) et d'une clé privée (gardée secrète), l'une permettant de coder le message et l'autre de le décoder. Ainsi, l'expéditeur peut utiliser la clé publique du destinataire pour coder un message que seul le destinataire (en possession de la clé privée) peut décoder, garantissant la confidentialité du contenu. Inversement, l'expéditeur peut utiliser sa propre clé privée pour coder un message que le destinataire peut décoder avec la clé publique ; c'est le mécanisme utilisé par la signature numérique pour authentifier l'auteur d'un message.

    Principe

    La cryptographie asymétrique, ou cryptographie à clé publique est fondée sur l'existence de fonctions à sens unique — une fois la fonction appliquée à un message, il est extrêmement difficile de retrouver le message original.

    En réalité, on utilise en cryptographie asymétrique des fonctions à sens unique et à brèche secrète. Une telle fonction est difficile à inverser, à moins de posséder une information particulière, tenue secrète, nommée clé privée.

    À partir d'une telle fonction, voici comment se déroulent les choses : Alice souhaite pouvoir recevoir des messages chiffrés de n'importe qui. Elle génère alors une valeur à partir d'une fonction à sens unique et à brèche secrète à l'aide d'un algorithme de chiffrement asymétrique (liste ici), par exemple RSA.

    Alice diffuse à tout le monde la fonction pour coder les messages (notée clé publique) mais garde secrète la fonction de décodage (notée clé privée).


    [​IMG]

    1[SUP]re[/SUP] étape : Alice génère deux clés.
    La clé publique (verte) qu'elle envoie à Bob et la clé privée (rouge)
    qu'elle conserve précieusement sans la divulguer à quiconque.

    Description: Asymetric cryptography. Step 1 – Alice sends public key to Bob.
    Date: 20 mars 2007
    Source: own work, based on png version originally uploaded to the Commons by Dake.
    Auteur : odder
    Ce fichier est disponible selon les termes de la licence
    Creative Commons paternité – partage à l’identique 3.0 (non transposée)
    Ce fichier et sa description proviennent de Wikimedia Commons.

    ________________________________________________



    [​IMG]


    2[SUP]e[/SUP] et 3[SUP]e[/SUP] étapes :
    Bob chiffre le message avec la clé publique d'Alice et envoie le texte chiffré.
    Alice déchiffre le message grâce à sa clé privée.

    Description: Asymetric cryptography. Steps 2 & 3 :
    Bob ciphers the message with Alice's public key.
    Alice gets the ciphertext and uses her private key to recover the text.
    Date: 20 mars 2007
    Source: own work, based on png version originally uploaded to the Commons by Dake.
    Auteur : odder
    Ce fichier est disponible selon les termes de la licence
    Creative Commons paternité – partage à l’identique 3.0 (non transposée)
    Ce fichier et sa description proviennent de Wikimedia Commons.

    ________________________________________________


    - Chiffrement

    Un des rôles de la clé publique est de permettre le chiffrement ; c'est donc cette clé qu'utilisera Bob pour envoyer des messages chiffrés à Alice. L'autre clé — l'information secrète — sert à chiffrer. Ainsi, Alice, et elle seule, peut prendre connaissance des messages de Bob. La connaissance d'une clé ne permet pas de déduire l'autre.

    - Authentification de l'origine
    D'autre part, l'utilisation par Alice de sa clé privée sur le condensat d'un message, permettra à Bob de vérifier que le message provient bien d'Alice : il appliquera la clé publique d'Alice au condensat fourni (condensat chiffré avec la clé privée d'Alice) et retrouve donc le condensat original du message. Il lui suffira de comparer le condensat ainsi obtenu et le condensat réel du message pour savoir si Alice est bien l'expéditeur. C'est donc ainsi que Bob sera rassuré sur l'origine du message reçu : il appartient bien à Alice. C'est sur ce mécanisme notamment que fonctionne la signature numérique.

    - Faiblesses
    Comme dans le cadre de la cryptographie symétrique, les faiblesses peuvent tout d'abord venir des faiblesses de l'algorithme de chiffrement (voir Cryptanalyse).
    Le risque principal dans l'utilisation des clés asymétriques est celui de l'attaque de l'homme du milieu, c'est-à-dire la possibilité qu'une partie adverse intercepte les clés publiques échangées pour les remplacer par les siennes. Il pourrait alors déchiffrer et signer tous les messages échangés. La résolution de cette faiblesse nécessite une infrastructure à clés publiques afin de certifier que les clés publiques appartiennent bien aux parties.

    - Analogies
    * Le coffre-fort
    Le chiffrement : Alice a choisi un coffre-fort. Elle l'envoie ouvert à Bob, et en garde la clé. Lorsque Bob veut écrire à Alice, il y dépose son message, ferme le coffre, il n'a pas besoin de la clef pour cela, et le renvoie à Alice. À sa réception, seule Alice peut ouvrir le coffre, puisqu'elle seule en possède la clé, à supposer le coffre inviolable, et que personne ne puisse refaire la clé.
    L'authentification ou la signature : Alice place un message dans le coffre-fort qu'elle ferme avec sa clé privée avant de l'envoyer à Bob. Si Bob parvient, à l'aide de la clé publique d'Alice (dont il dispose), à lire la lettre c'est que c'est bien celui d'Alice et donc que c'est bien elle qui y a placé le message.

    * La boîte à deux serrures
    Une autre analogie envisageable serait d'imaginer une boîte avec deux serrures différentes. Lorsque l'on ferme la boîte d'un côté, seule la clé correspondant à l'autre serrure permet l'ouverture de la boîte et vice-versa. Une des clés est privée et conservée secrète, l'autre est dite publique et un exemplaire peut-être obtenu par quiconque souhaite utiliser la boîte.
    Pour chiffrer un message Bob prend la boîte, y place son message, et la ferme à l'aide de la clé publique. Seul le détenteur de la clé privée permettant d'accéder à l'autre serrure, Alice en l'occurrence, sera en mesure de rouvrir la boîte.
    Pour signer un message, Alice le place dans la boîte et ferme celle-ci à l'aide de sa clé privée. Ainsi n'importe qui ayant récupéré la clé publique pourra ouvrir la boîte. Mais comme la boîte a été fermée par la clé privée, cette personne sera assurée que c'est bien Alice, seule détentrice de cette clé, qui aura placé le message dans la boîte et fermé ladite boîte.


    Applications
    Transmission sécurisée de la clé symétrique
    La cryptographie asymétrique répond à un besoin majeur de la cryptographie symétrique : le partage sécurisé d'une clé entre deux correspondants, afin de prévenir l'interception de cette clé par une personne tierce non autorisée, et donc la lecture des données chiffrées sans autorisation.
    Les mécanismes de chiffrement symétrique étant moins coûteux en temps de calcul, ceux-ci sont préférés aux mécanismes de chiffrement asymétrique. Cependant toute utilisation de clé de chiffrement symétrique nécessite que les deux correspondants se partagent cette clé, c'est-à-dire la connaissent avant l'échange. Ceci peut être un problème si la communication de cette clé s'effectue par l'intermédiaire d'un medium non sécurisé, «en clair». Afin de pallier cet inconvénient, on utilise un mécanisme de chiffrement asymétrique pour la seule phase d'échange de la clé symétrique, et l'on utilise cette dernière pour tout le reste de l'échange.


    Mécanismes d'authentification
    Un inconvénient majeur de l'utilisation des mécanismes de chiffrement asymétriques est le fait que la clé publique est distribuée à toutes les personnes : Bob, Carole, … souhaitant échanger des données de façon confidentielle. De ce fait, lorsque la personne possédant la clé privée, Alice, déchiffre les données chiffrées, elle n'a aucun moyen de vérifier avec certitude la provenance de ces données (Bob, ou Carole …) : on parle de problèmes d'authentification. Afin de résoudre ce problème, on utilise des mécanismes d'authentification permettant de garantir la provenance des informations chiffrées. Ces mécanismes sont eux aussi fondés sur le chiffrement asymétrique.
    Principe d'authentification par chiffrement asymétrique :


    Objectif : Bob souhaite envoyer des données chiffrées à Alice en lui garantissant qu'il en est l'expéditeur.

    1
    . Bob crée une paire de clés asymétriques : il conserve la clé privée et diffuse librement la clé publique (notamment à Alice)
    2. Alice crée une paire de clés asymétriques : clé privée (qu'elle conserve), clé publique (qu'elle diffuse librement, notamment à Bob)
    3. Bob effectue un condensat de son message «en clair» puis chiffre ce condensat avec sa propre clé privée
    4. Bob chiffre son message avec la clé publique d'Alice.
    5. Bob envoie le message chiffré accompagné du condensat chiffré.
    6. Alice reçoit le message chiffré de Bob, accompagné du condensat.
    7. Alice déchiffre le message avec sa propre clé privée. À ce stade le message est lisible mais elle ne peut pas être sûre que Bob en soit l'expéditeur.
    8. Alice déchiffre le condensat avec la clé publique de Bob. Alice utilise la même fonction de hachage sur le texte en clair et compare avec le condensat déchiffré de Bob. Si les deux condensats correspondent, alors Alice peut avoir la certitude que Bob est l'expéditeur. Dans le cas contraire, on peut présumer qu'une personne malveillante a tenté d'envoyer un message à Alice en se faisant passer pour Bob !

    Cette méthode d'authentification utilise la spécificité des paires de clés asymétriques : si l'on chiffre un message en utilisant la clé publique, alors on peut déchiffrer le message en utilisant la clé privée ; l'inverse est aussi possible : si l'on chiffre en utilisant la clé privée alors on peut déchiffrer en utilisant la clé publique.

    Certificats
    La cryptographie asymétrique est également utilisée avec les certificats numériques, celui-ci contenant la clé publique de l'entité associée au certificat. La clé privée est quant à elle stockée au niveau de cette dernière entité. Une application des certificats est par exemple la mise en œuvre d'une infrastructure à clés publiques (PKI) pour gérer l'authentification et la signature numérique d'une entité, par exemple un serveur web (Apache avec le module SSL par exemple), ou simplement un client souhaitant signer et chiffrer des informations à l'aide de son certificat de la façon décrite dans les sections précédentes.

    Une clé privée inviolable ?


    Un chiffrement symétrique au moyen d'une clé de 128 bits propose 2[SUP]128[/SUP] ( ~ 3,4 10[SUP]38[/SUP] ) façons de chiffrer un message. Un pirate qui essaierait de déchiffrer le message par la force brute devrait les essayer une par une.

    Pour les systèmes à clé publique, il en va autrement. Tout d'abord les clés sont plus longues (par exemple 1 024 bits minimum pour RSA) ; en effet, elles possèdent une structure mathématique très particulière (on ne peut pas choisir une suite de bits aléatoire comme clé secrète, car, dans le cas du RSA, seuls les nombres premiers sont utilisés). Certains algorithmes exploitant cette structure sont plus efficaces qu'une recherche exhaustive sur, par exemple, 1 024 bits. Ainsi, dans le cas de RSA, le crible général de corps de nombres est une méthode plus efficace que la recherche exhaustive pour la factorisation.

    Il faut noter le développement actuel de la cryptographie utilisant les courbes elliptiques, qui permettent (au prix d'une théorie et d'implémentations plus complexes) l'utilisation de clés nettement plus petites que celles des algorithmes classiques (une taille de 160 bits étant considérée comme très sûre actuellement), pour un niveau de sécurité équivalent.

    Historique


    Le concept de cryptographie à clé publique — autre nom de la cryptographie asymétrique — est dû à Whitfield Diffie et à Martin Hellman. Il fut présenté pour la première fois à la National Computer Conference en 1976[SUP]2[/SUP], puis publié quelques mois plus tard dans New Directions in Cryptography. On considère que Ralph Merkle a découvert indépendamment la cryptographie à clef publique, même si ses articles furent publiés plus tard.

    En réalité, James Ellis, qui travaillait au service du chiffre britannique (GCHQ, Government Communications Headquarters), avait eu cette idée peu avant. En 1973, C.C. Cocks décrivit (pour le même service du chiffre) ce qu'on a appelé l'algorithme RSA. Enfin, en 1974, M. J. Williamson invente un protocole d'échange de clé très proche de celui de Diffie et de Hellman. Ces découvertes n'ont été rendues publiques qu'en 1997 par le GCHQ.

    Dans leur article de 1976, W. Diffie et M. Hellman n'avaient pas pu donner l'exemple d'un système à clé publique, n'en ayant pas trouvé. Il fallut attendre 1978 pour avoir un exemple donné par Ronald Rivest, Adi Shamir et Leonard Adleman, le RSA, abréviation tirée des trois noms de ses auteurs. Les trois hommes fondèrent par la suite la société RSA Security. On considère cependant que la première réalisation pratique d'un système de chiffrement à clef publique est le système Merkle-Hellman. Le système Merkle-Hellman fut cependant prouvé comme non-sûr par Shamir en 1982.


    ________________________________________________

    · Nom de la page : Cryptographie asymétrique
    Contenu soumis à la licence CC-BY-SA 3.0.
    Sous licence Creative Commons paternité partage à l’identique
    Source : Article Cryptographie asymétrique de Wikipédia en français (auteurs)
    ________________________________________________


    A SUIVRE/
    Cryptographie hybride

     
  13. titegazelle

    titegazelle سُبحَانَ اللّهِ وَ بِحَمْدِهِ Membre du personnel

    J'aime reçus:
    4181
    Points:
    113


    Cryptographie hybride



    La
    cryptographie hybride
    est un système de cryptographie faisant appel aux deux grandes familles de systèmes cryptographiques : la cryptographie asymétrique et la cryptographie symétrique. Les logiciels comme PGP et GnuPG reposent sur ce concept qui permet de combiner les avantages des deux systèmes.

    Principe

    La cryptographie asymétrique est intrinsèquement lente à cause des calculs complexes qui y sont associés, alors que la cryptographie symétrique brille par sa rapidité. Toutefois, cette dernière souffre d'une grave lacune, on doit transmettre les clés de manière sécurisée (sur un canal authentifié). Pour pallier ce défaut, on recourt à la cryptographie asymétrique qui travaille avec une paire de clés : la clé privée et la clé publique. La cryptographie hybride combine les deux systèmes afin de bénéficier des avantages (rapidité de la cryptographie symétrique pour le contenu du message) et utilisation de la cryptographie "lente" uniquement pour la clé.

    Chiffrement


    La plupart des systèmes hybrides procèdent de la manière suivante. Une clé aléatoire est générée pour l'algorithme symétrique (3DES, IDEA, AES et bien d'autres encore), cette clé fait généralement entre 128 et 512 bits selon les algorithmes. L'algorithme de chiffrement symétrique est ensuite utilisé pour chiffrer le message. Dans le cas d'un chiffrement par blocs, on doit utiliser un mode d'opération comme par exemple CBC, cela permet de chiffrer un message de taille supérieure à celle d'un bloc. La clé aléatoire quant à elle, se voit chiffrée grâce à la clé publique du destinataire, c'est ici qu'intervient la cryptographie asymétrique (RSA ou Diffie-Hellman). Comme la clé est courte, ce chiffrage prend peu de temps. Chiffrer l'ensemble du message avec un algorithme asymétrique serait bien plus lourd, c'est pourquoi on préfère passer par un algorithme symétrique. Il suffit ensuite d'envoyer le message chiffré avec l'algorithme symétrique et accompagné de la clé chiffrée correspondante. Le destinataire déchiffre la clé symétrique avec sa clé privée et via un déchiffrement symétrique, retrouve le message.

    Authentification


    Il est très courant d'ajouter des authentifications et des signatures aux messages envoyés. On utilise pour cela des fonctions de hachage (MD5, SHA-1 ou des codes authentificateurs comme HMAC).

    ·
    ______________________________________
    Nom de la page : Cryptographie hybride
    Contenu soumis à la licence CC-BY-SA 3.0.
    Source : Article Cryptographie hybride de Wikipédia en français (auteurs)
    ______________________________________



     

Partager cette page