Décomposition de nombres clés contre certains codes
2011/11/01 Alberdi Celaya, Elisabete - Matematikan lizentziatua eta doktoregaia Iturria: Elhuyar aldizkaria
Si vous avez déjà accédé à une page web "sécurisée" -- parce que vous avez acheté un voyage d'avion sur Internet, vous avez accédé à voir les dernières opérations du compte courant -, la communication a été effectuée via une plate-forme sécurisée, appelée SSL, qui est dans un protocole https (secure). Dans ce cas, vous avez pu vérifier qu'un cadenas apparaît dans la barre des tâches du navigateur. Il indique que pour accéder à cette page il faut clé ou clé, que personne qui n'a pas de clé ne peut pas accéder. Autrement dit, la communication est sûre dans la mesure où le destinataire est le seul qui décode le message. Donc, lorsque vous achetez un billet sur Iberia, Iberia chiffre ou codez votre numéro de visa. Le message chiffré voyage sur le réseau et lorsque vous arrivez à Iberia décrypte ou décode le message chiffré. La communication est sûre dans la mesure où le seul qui sait déchiffrer le message est le destinataire.
La cryptographie est un technicien qui utilise différentes méthodes pour protéger un message. Bien que initialement situé dans le domaine des mathématiques, il a également étendu l'informatique et la télématique. Cependant, l'utilisation des techniques de cryptographie est très ancienne. Les premières civilisations ont développé des techniques pour envoyer des messages dans des campagnes militaires. Bien que le messager tombe entre les mains de l'ennemi, ils ont obtenu que l'ennemi ne s'approprie pas le message, car ils envoyaient le message chiffré avec des techniques de cryptographie. Le destinataire du message en le recevant déchiffrait le message codé avec l'opération inverse. Au cinquième siècle avant JC, l'outil utilisé pour chiffrer les messages était le soi-disant “Scytal”. Sur un bâton est enroulé un ruban de cuir dans lequel le message a été écrit. Une fois la bande enlevée, les lettres du message étaient mélangées et seul celui qui avait le bâton du même diamètre du scandale pouvait déchiffrer le message. À cette époque, ces bâtons étaient la force des peuples, et depuis lors vient le bâton qui se livre aujourd'hui aux maires des peuples.
Méthodes de cryptage classiques
Les méthodes de chiffrement des messages sont divisées en deux grands blocs : classiques et modernes. Certaines des méthodes classiques sont basées sur le remplacement. Ces méthodes remplacent chaque lettre du message par une autre lettre ou numéro. Un exemple de ce type de méthodes a. C. C'est le crypteur utilisé par Jules César au premier siècle, dans lequel chaque lettre était remplacée par une lettre qui dans l'alphabet est trois espaces plus à droite qu'elle. Ainsi, la lettre A était remplacée par D, la lettre B par E, etc. Celui qui recevait un message codé avec la technique de César, remplaçant chaque lettre par laquelle il était alphabétiquement 3 espaces plus à gauche, obtenait le message initial. Cette méthode n'était rien sûr.
Le chiffreur de César peut être généralisé en remplaçant chaque lettre par une lettre b espace plus droite qu'elle. Dans un alphabet de vingt-sept lettres, il y a 26 façons de remplacer une lettre par une autre. Tester les vingt-six formes vous obtenez le message. Par conséquent, cette méthode généralisée est également très faible. En outre, le test avec toutes les façons de remplacer une lettre lorsque vous utilisez cette méthode n'est pas la seule façon de clarifier le message codé. Vous pouvez également clarifier le message codé en connaissant la langue dans laquelle le message est écrit et la fréquence des lettres dans cette langue. Pour cela, il suffit de remplacer la lettre qui apparaît le plus dans le message codé par la plus fréquente dans cette langue, et la distance entre les deux lettres est celle qui nous indique la position dans laquelle nous devons déplacer chaque lettre. Une fois la valeur de b connue, en déplaçant chaque lettre de message chiffrée à gauche l'espace b, nous obtiendrons le message complet. Il est évident que cette méthode n'est pas sûre.
Un cryptage plus sophistiqué est un cryptage affine; Ki = a . L'opération Mi + b (mod27) permet de coder chaque lettre Mi du message. Ce résultat est obtenu en assignant un nombre à chaque lettre et en remplaçant le nombre correspondant à la lettre par cette formule. Puis à . La valeur Mi + b est divisée par 27, le résidu résultant étant la valeur de Ki. Pour terminer, entrez la lettre correspondant à ce numéro. Par exemple, H correspond au nombre 7 et a = 5, b = 7, Ki = 5 . Da 7 + 7 = 42 = 15 (mod27). La lettre O correspond au numéro 15. Cela signifie qu'en utilisant ce chiffrement, la lettre H devient O. Bien que cette méthode semble plus complexe que la précédente, lorsque le message codé est long, en utilisant les fréquences des lettres d'une langue, il est facile de détecter le message.
Méthodes de cryptage modernes
Les méthodes de cryptage modernes peuvent utiliser clé privée ou clé publique. Les utilisateurs de clé privée peuvent être de bloc ou de flux. Les chiffreurs de bloc appliquent l'algorithme plusieurs fois dans un ensemble de caractères d'information en utilisant la même clé. Des exemples de crypteurs en bloc sont DES (Data Encryption Standard) et AES (Advanced Encryption Standard). Dans les deux méthodes, l'algorithme est connu et la clé, inconnu (privé). Dans les flux, chaque caractère est chiffré par une longue clé aléatoire dans lequel il est également inconnu.
Mais la modernité n'a pas non plus libéré ces méthodes des doigts de l'insécurité. Le principal inconvénient du crypteur DES est la petite taille de la clé (56 bits). Cela signifie qu'il ya 256 = 72.057.594.037.927.936 options pour choisir la clé, et dans le monde des ordinateurs ce nombre est petit. Un exemple de ceci est que dans un challenge DES organisé en janvier 1998 on a réussi à casser la clé en 56 heures, puisque des ordinateurs évaluant 90.000 clés par seconde ont été utilisés. Avec une clé plus longue de 112 bits, le triple DES est actuellement utilisé car il offre 2112 options pour la clé. La clé de la méthode AES est également plus longue : 128, 129 et 256 bits. L'inconvénient des flux est que le chiffrement individuel des caractères rend la relation entre les caractères du message codé faible.
Parmi les méthodes qui utilisent la clé publique se trouve celle connue sous le nom de RSA (Rivest, Shamir, Adleman). C'est une méthode jusqu'ici sûre, mais comment pouvez-vous obtenir la certitude avec une clé connue de tous? La clé est dans la difficile opération de décryptage.
Décomposition des nombres
Les êtres humains ont commencé à décomposer les nombres depuis très enfant. Un des concepts que nous apprenons d'abord est celui du nombre premier: Le nombre a est le premier, seulement s'il peut être divisé par ±a et ±1. Ainsi, les nombres 2, 3, 5, 7... sont les premiers. Quand on veut décomposer un nombre, on commence à diviser par des nombres premiers mineurs. Par exemple, le nombre 15 est décomposé comme le produit des nombres premiers 3 et 5. Quand un nombre n'est pas divisé par des nombres premiers mineurs, il est dit être le premier. Par conséquent, nous ajoutons à la liste des nombres premiers que nous avons indiqué ci-dessus le rapport des premiers numéros suivants: 11, 13, 17, 19, 23,...131, 137,... Ou : 244497-1, 213466917-1,... Oui, il n'y a pas de chiffres mineurs qui peuvent les diviser.
Bien que les petits nombres donnent du travail, nous pouvons dire assez facilement s'ils sont les premiers ou pas. Mais que pouvons-nous dire du numéro 94550!-1? Est-ce la première ? En mathématiques, il existe plusieurs outils pour dire si un numéro est le premier ou non. Et si un numéro n'est pas le premier, comment est-il décomposé?
Bien qu'il existe des algorithmes efficaces pour décomposer certains nombres, la décomposition de n'importe quel nombre reste un mystère mathématique et le système RSA exploite ce mystère pour construire son codage. En utilisant la RSA, le destinataire du message rend public deux numéros : e et n Le premier numéro, e, est celui que l'expéditeur utilisera pour encoder le message. Si x est un message, l'expéditeur effectuera l'opération suivante : x - e ; et ce sera le message codé qui ira sur le réseau. Le destinataire, pour déchiffrer le message codé qu'il a reçu, utilisera le nombre e ', qui calculera en reconnaissant le nombre n et qu'il remplit ( x - e ) e' = x -. Ainsi, le destinataire récupérera le message initial. Dans le système RSA, le nombre n est choisi comme le produit de deux nombres premiers, et le mystère entourant la décomposition des nombres rend le nombre n pratiquement inséparable. En conséquence, le nombre e ' nécessaire pour l'opération à effectuer pour clarifier le message peut être obtenu par celui qui sait presque exclusivement décomposer n, c'est-à-dire par celui qui a créé le numéro.
Conclusions
Comme dans leur journée, les méthodes de remplacement ont été laissées derrière, à mesure que les vitesses des ordinateurs augmentaient, les techniques de cryptographie qui utilisent les clés courtes sont restées derrière et iront, car la clé longue actuelle peut être courte demain. Bien que le système RSA n'ait pas de tels inconvénients, il dépend de la décomposition des nombres; si un algorithme efficace de décomposition des nombres était trouvé, ce serait la fin du système RSA que nous avons jusqu'ici eu comme sûr. Si cela se produisait, nous aurions besoin d'un nouveau système de codage. Qui donnera l'algorithme efficace pour la décomposition des nombres? Et qui va créer un système de cryptage sécurisé qui ne peut pas maîtriser la vitesse des ordinateurs?
Bibliographie Bibliographie
