Tout d'abord, comme mentionné dans le message de cryptage du système RSA est un chiffrement à clé publique et tire parti des propriétés des nombres premiers. Par ailleurs, l'arithmétique utilisée (dans les calculs) n'est pas l'ordinaire, mais le fini que l'on appelle ou artirmetica modulaire. Commençons tout de ce dernier à procéder étape par étape dans la mise en œuvre de cryptage RSA.
L'arithmétique sur, comme son nom l'indique, des ensembles de nombres est fini. Un exemple illustratif qui va tout faire très clair, c'est l'ordinateur pour regarder. Prenez une montre classique avec les mains que nous sommes tous habitués. Il s'agit d'un système fini les heures indiquées sur le cadran sont 12. The Lancet, en fait, à chaque tour sera de retour - tôt ou tard - la même position. Il se trouve que 3 12 = 3 dans notre ordinateur pour regarder. Plus précisément, les opérations arithmétiques d'addition et de multiplication ont lieu au cours de la même manière dell'aritmentica ordinaire, sauf que le résultat final que vous faites pour le module (mod souvent désigné et présent dans tous les langages de programmation , C, Javascript ou PHP est le symbole%). Dans le cas de notre horloge 12 heures, en fait, l'opération d'addition est à seulement 3 12 = 15 mod 12, qui se traduira par 3 - visuellement comme nous sommes habitués.
Dans la pratique - par rapport à l'horloge - nous faire exactement cela, mais pas consciemment. Le fonctionnement du module 12, pour comprendre, pour correspondre à diviser un nombre par 12 et prendre le reste de la division:
Par exemple 15 mod 12 = 15/12 = (repos 15-12) = 3
Par exemple, 24 mod 12 = 24/12 = (reste 0) = 0
Par exemple 26 mod 12 = 26/12 = (repos 14-12) = 2
Le nombre d'heures sur qudrante peut être n'importe quel nombre, 12, 24, 5, 128, ...
Cependant on a découvert que le choix d'un nombre premier, comme le nombre d'heures, nous avions une fonctionnalité puissante. Tout d'abord lorsque vous choisissez un nombre premier, nous ne trouverez jamais un résultat nul. En outre, un nombre quelconque d'un quadrilatère formé par un grand nombre premier choisi comme le premier nombre renvoie toujours le nombre d'heures donné. Par exemple, si nous prenons une horloge avec 5 heures sur le cadran et nous élevons nous obtenons, par exemple 2 5 2 encore, le nombre de départ:
2 5 = 32 mod 5 = 2
Qui se traduit par:
x p = x (mod p)
Pierre de Fermat , le mathématicien qui a pris conscience de ce comportement, il a remarqué que l'aiguille de l'horloge semblait dessiner un motif répétitif. En pratique, dans notre cas, après cinq étapes le pointeur à la position de départ.
| Puissances de 2 | 1 2 | 2 2 | 2 3 | 2 4 | 2 5 | 2 6 | 2 7 | 2 8 | 2 9 | 2 10 |
| Fonctionnement normal | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 |
| Module 5 | 2 | 4 | 3 | 1 | 2 | 4 | 3 | 1 | 2 | 4 |
Avec une horloge à 13 heures (jusqu'à essayer 3 13) nous obtenons:
3, 9, 1, 3, 9, 1, 3, 9, 1, 3, 9, 1, 3
Contrairement à notre première main ne s'arrêtera pas sur tous les nombres possibles, mais la tendance semble trop répétitif, et, dans ce cas, la main sera de retour à l'étape 3 après 3 a été multipliée par elle-même 13 fois!
En 1736, Leonhard Euler était en mesure d'étendre cette fonctionnalité, ainsi que de donner une explication. Il a montré que, étant donné une heure d'horloge sur le cadran avec N, où N = p * q est le produit de deux nombres premiers p et q, la performance serait de commencer à se répéter après (p -1) * (q -1) 1 étapes.
Cette fonctionnalité est la base de cryptage RSA. Il était entendu que cette tendance cyclique pourrait - en fait - à disparaître par magie et ensuite apporter des informations à la lumière. Nous voyons que N est le produit de deux nombres premiers p et q, cet artifice sera en mesure de publier et maintenir N p et q secret.
En pratique, donc, ce que vous vous rappelez est de faire un tour de cartes. Imaginez que nous avons un tas constitué d'un grand nombre de cartes, si grand que nous aurions besoin d'écrire au moins une centaine chiffres. Le code que nous voulons pour crypter est une de ces cartes, après avoir été au sommet du pont, il est mélangé de manière à perdre - apparemment - la localisation de notre papier (le message). Avec l'arithmétique d'horloge, en pratique, il est très facile de se débarrasser du papier, mais il n'est pas aussi facile à réapparaître, sauf si vous savez le nombre exact de coups à faire sur le pont de telle manière à rétablir le papier dessus d'elle.
Nous avons ensuite exemple complet, de sorte que vous pouvez voir toutes les formules nécessaires pour créer ce genre de magie.
Dans notre exemple nous allons utiliser un petit nombre seulement de comprendre le mécanisme et d'imaginer d'avoir à envoyer notre numéro de carte de crédit pour un site Web
ETAPE 1
Le site communique - à nos navigateurs - la première clé publique, calculé comme N = q p * (le site Web sera jalousement si les nombres p et q, seul le produit est rendu public), il représente le nombre d'heures d'utilisation sur notre montre. Considérons que, en réalité, le nombre p et q sont au moins 60 chiffres! Nous allons utiliser des numéros de plus humain:
N = p * q = 5 * 11 = 55
Cinquante-cinq est notre clé publique, grâce à la sécurité du code, le site Web peuvent être distribuées facilement et également à tous ses clients. Bien qu'il ait été rendu public le nombre N, les facteurs principaux qui composent p et q sont secrètes, ils décodent le numéro de notre carte de crédit!
ETAPE 2
À ce stade, et de recevoir un second numéro, appelé codage numérique. Ce nombre est le même pour tous publics et aussi, au même titre que N. Grâce à notre navigateur, nous permet de coder le nombre de nos C carte de crédit, en pratique, battre les cartes, et représente le nombre de battre les cartes:
C E (modulo N)
Et le nombre est généralement faible et est calculé à partir de la formule que nous avons rencontré quand nous avons vu que sur une montre avec un nombre d'heures composée d'un nombre premier, il y avait une séquence qui a été répétée plus tard (p -1) * ( q -1) 1 étapes (pour plus de détails cliquez ici )!
Tout d'abord vous calculez un nombre b:
b = (p -1) * (q -1) = (5-1) * (11-1) = (4) * (10) = 40
Et le nombre doit être un nombre premier qui ne dispose pas de diviseurs avec b, pgcd (E, B) = 1
Pour simplifier nous allons tentatives - esistone différentes techniques pour cela:
Si E = 2, alors pgcd (2, 40) = 2 n'est pas bon
Si E = 3 alors pgcd (3, 40) = 1 est une bonne
A ce stade, nous pouvons chiffrer le nombre de nos cartes de crédit C. Si C est de 32 et a, par exemple:
Mod N et C = 32 3 mod 55 = 43 C = CF
Cool, 43 est notre numéro de carte de crédit cryptées! Nous pouvons l'envoyer!
ETAPE 3
Le site Web reçoit notre numéro de carte de crédit C cf crypté, ou 43. A ce point utilise la propriété suivante :
Cf. C = C d mod N
Le nombre d est l'inverse de l'arithmétique et le nombre fini de b commande, notre arithmétique d'horloge. Il est calculé pour la simplicité afin que d * e mod b = 1
Aller à tenter de découvrir que:
Pour d = 1 doit être 1 * 3 = 3 mod 40 mod 40 = 3 - pas bon
Pour d = 2 et a 2 * 3 = 6 mod 40 mod 40 = 6 - pas bon
Pour d = 3 et a 3 * 3 = 9 mod 40 mod 40 = 9 - pas bon
....
Pour d = 27 est une 27 * 3 = 81 mod 40 mod 40 = 1 - trouvé!
Maintenant le site est capable de battre les cartes, afin de réapparaître sur notre numéro de carte de crédit:
Cf. C = C d mod N = 43 27 mod 55 = 32
En résumé
| Variable | Tapez | Formule | Valeur |
N | Publique | p * q | 5 * 11 = 55 |
b | Privé | (P -1) * (q -1) | (5-1) * (11-1) = (4) * (10) = 40 |
Il | Publique | Pgcd (E, B) = 1 | Pgcd (3, 40) = 1 alors 40 |
d | Privé | Et b * d = 1 mod | 3 27 * 27 mod 40 = 1, puis |
C | Numéro de carte de crédit | - | 32 |
Cf. C | Crypté | Mod N C E | 32 3 mod 55 = 43 |
C | Déchiffré | Cf. C = C d mod N | 43 27 55 mod = 32 |
Si vous voulez expérimenter avec des numéros choisis au hasard, cliquez ici .
Par ailleurs, comme expliqué sur le site même du RSA:
Supposons qu'Alice souhaite envoyer un message m à Bob. Alice au c chiffré par exponentiation Crée c = m e mod n, et où et n sont la clé publique de Bob. Elle envoie c à Bob. Pour déchiffrer, Bob exponentiates aussi: m = c d mod n, et D, et la relation entre la Veille à ce que Bob récupère correctement m. Depuis que Bob sait d, seul Bob peut déchiffrer ce message.
Les pirates et la sécurité
Notre numéro de carte de crédit, chiffré, il se déplace sur le réseau et n'importe quel pirate peut le lire. Ce qui est nécessaire pour un pirate pour casser notre code est un nombre qui, multiplié par lui-même et parfois à l'ordinateur de regarder des heures de N, donne le nombre de cartes de crédit cryptées (cf C = C e mod n). En plus d'un ordinateur ordinaire le résultat de la multiplication d'une série de autmenta progressivement, ce qui n'arrive pas sur un ordinateur pour regarder, où le point de départ de vue se perd très vite, puisque la taille du résultat n'ont rien à voir avec la position de l'endroit où vous avez commencé. Par ailleurs, dans des cas réels, le nombre N a plus d'une centaine de personnalités, il ya plus d'heures sur le visage de l'ordinateur pour regarder des atomes dans l'univers. C'est seulement à cause du nombre de décodage de ce site Web peut récupérer le numéro de carte de crédit, mais ce nombre d est récupérable seulement si vous savez p et q. Malgré le nombre N = p * q est public, la difficulté de factorisation N rend pratiquement impossible de déchiffrer le code.
Cependant, personne n'a jamais prouvé qu'il existe un algorithme mathématique qui peut rendre de très grands nombres sont décomposés rapidement en utilisant un ordinateur. Si cela se produisait, ce serait ruiner l'économie du monde développé en un rien de temps.
Bibliographie
- Colin Bruce, Lapins de Schrodinger - qunatistica physique et des univers parallèles , Raffaello Cortina Editore
- Marcus du Sautoy, La Musique des Primes. L'hypothèse de Riemann, le plus grand mystère de mathématiques , BUR
- Simon Singh, le dernier théorème de Fermat. L'aventure d'un génie, un problème mathématique et l'homme qui a résolu , Rizzoli
- Liceo Foscarini - Venise http://www.liceofoscarini.it/studenti/crittografia/
- RSA: http://www.rsasecurity.com/
[...] 13) Le cryptage RSA - 808 [...]
bonjour .. Je voudrais faire un programme en C (un pour un Bob et Alice) ... qui est un RSA qui décrypter et déchiffrer un message que l'on .. vous avez des idées?
@ Daniel: Si vous voulez dire l'algorithme est expliqué dans le message. Voir aussi les liens connexes qui contiennent des pages avec la démo en ligne, si elle peut vous aider. Sinon vous avez fait allusion à quelque chose en particulier?
[...] Dire que le fonctionnement du module est un sujet très vaste, dont j'ai discuté dans le cryptage RSA! Cette fois, cependant, ne parle pas des codes ou des chiffres, mais les choses beaucoup plus utiles et [...]
La meilleure explication que j'ai lu. J'ai enfin compris quelque chose d'arithmétique modulaire ... Merci!
Bonjour les gars,
Eh bien le cryptage RSA devrait avoir la vie très longue ... une nouvelle torsion peut provenir de l'ordinateur quantique capable de factorisation de grands nombres rapidement. Pratiquement parlant le lien pour voir les systèmes Dwave .
Que pensez-vous? Nous devrions passer à d'autres systèmes à clé publique bientôt? RSA, cependant, n'est pas «le seul algorithme à clé publique ...
Salutations
Maximilien Monittola