La situation est la suivante: il y a Deux alliés qui sont en guerre contre un ennemi avec des espions très désarticulés: comment ils peuvent faire pour échanger des messages secrètes Sans ceux-ci tombent entre les mains de l’ennemi? Les grands protagonistes de la réponse à cette question sont les nombres premiers, c’est-à-dire ces nombres internes positifs qui n’ont pas d’autres séparateurs sinon 1 et eux-mêmes. Mais qu’est-ce que les nombres premiers ont à faire avec deux rois qui veulent communiquer entre eux en toute sécurité? En résolvant ce problème, nous découvrirons l’idée clé derrière beaucoup Protocoles de communication sûrsbasé sur le fait que le Multiplication de très grands nombres premiers C’est une opération facile qui peut être utilisée pour faire un message illisible, tandis que Décomposer un nombre en premiers facteursAutrement dit, essayer de récupérer le message initial peut prendre beaucoup de temps.
Mais comment? Nous le voyons dans cet article.
Le problème des deux rois qui veulent communiquer en secret
Pour comprendre ce que cela signifie crypter (ou croiser) un message pour Rendez-le illisible À toute personne inconnue qui le trouve entre ses mains, nous considérons cette situation d’imagination.
Le roi Gino doit envoyer au roi Pino, sans être intercepté par les espions ennemis qualifiés, un message vital pour le sort des deux royaumes. Les forgerons des deux rois savent créer des bauli et des paquets indestructibles, impossible à ouvrir sans clé. Re Gino met le message dans un coffre, le ferme avec un cadenas et l’envoie au King Pino. Si pendant le voyage, le coffre était intercepté par un espion ne pouvait pas être ouvert, mais même le roi Pino pourrait l’ouvrir sans clé. Le roi Gino pourrait alors envoyer la clé au roi la clé séparément du coffre, mais un espion pourrait intercepter à la fois la clé et le tronc et l’ouvrir ainsi: la clé ne peut pas voyager, c’est trop dangereux! Alors, comment faire le coffre qui ne peut pas être ouvert pour les espions, mais qui peut être ouvert par le roi Pino?
Pour trouver une réponse à cette question, nous devons penser à une clé particulière, c’est-à-dire je Nombres premiers.
Le long voyage du message: comment le rendre secret pour tout le monde mais pas pour les deux rois?
Les deux rois se rendent compte que l’envoi d’une clé physique est risqué et conçoit ainsi le stratagème de Deux cadenas:
- Re Gino met le message dans le coffre, le ferme avec un cadenas bleu dont il a seulement la clé et envoie le coffre si serré au roi Pino
- Le roi Pino reçoit le coffre et renforce sa fermeture avec un Deuxième cadenas rouge dont il seul a la clé et le réfère au roi Gino très fermé avec les deux cadenas
- King Gino à ce stade enlever Le cadenas rouge Du tronc en utilisant sa clé et le reporter à Pino. À ce stade, le coffre est toujours fermé avec le cadenas bleu, dont le roi Pino a la clé!
- Le roi Pino reçoit le coffre et, ayant la bonne clé, enlever Le cadenas bleu, gérant ainsi à ouvrir le tronc E Lisez le message secret.
Le message part du roi Gino et arrive et le roi Pino bien caché à l’intérieur du coffre sans aucun espion peut le lire, car les deux clés nécessaires à la lecture du coffre sont toujours restées en sécurité entre les mains des deux rois!
On peut dire que le message C’était en fait chiffrercomme ceux qui traitent cryptagela discipline qui étudie comment transformer un message clair – c’est-à-dire clairement lisible – Dans un autre message chiffrer – c’est-à-dire contrefait – afin qu’il soit incompréhensible pour ceux qui ne connaissent pas les détails de la technique utilisée pour la transformation.
À ce stade, se demande: Mais qu’est-ce que les nombres premiers ont à voir avec cela?
Les nombres premiers sont une excellente clé secrète pour cacher un message
Ce que nous venons de voir était, bien sûr, un exemple de fantaisie dans lequel «resserrer» un message que nous avons utilisé des cadenas. Dans la pratique, comment allumatons-nous un message, étant donné que les canaux que nous utilisons pour communiquer sont numériques et non physiques? Un coffre et deux cadenas ne suffisent pas.
L’échange de messages numériques – comme SMS ou WhatsApp – se déroule considérablement sous la forme de Séquences de nombres. Par exemple le mot « SALUT » pourrait voyager comme « 39115 »où chaque lettre a été remplacée par sa position dans l’alphabet. Il est clair, cependant, qu’un tel cryptage est très facile à déchiffrer: en combinant la lettre de l’alphabet correspondant avec chaque nombre de la séquence, nous avons trois hypothèses possibles: 3-9-1-1-5 qui correspond à ciaae, 3-9-15 qui correspond à SALUT, ou 3-9-11-5 qui est Cike. Il n’est pas difficile de deviner que le mot envoyé est la deuxième hypothèse, c’est-à-dire SALUT.
Quelque chose de plus complexe doit donc être pensé: non seulement pour combiner des nombres en lettres, mais assurez-vous opérations sur ces chiffres. Nous essayons de le comprendre avec un exemple.
Supposons le nôtre message secret Le nombre et la lettre F à laquelle nous combinons le numéro 6. Pour déguiser le message, nous pouvons le multiplier par un numéro secret que nous décidons – dit clé – Afin d’obtenir un numéro supplémentaire. Par exemple, nous choisissons le numéro 5, qui multiplié par notre message 6 donne le numéro 30 tel qu’il sera, qui sera le nôtre CYPHRUS. Si une lumière interceptait le numéro 30, ne connaissant pas la clé, il aurait du mal à reconnaître le message secret parce qu’il ne sait pas qu’il doit diviser pour 5 en obtenant ainsi 6 et enfin la lettre F. Cependant, il pourrait imaginer que nous avons obtenu le Numéro à travers une opération simple et après une tentative, il en viendrait probablement à deviner qu’il s’agit d’une multiplication et, écrivant tous les produits qui en donnent 30, obtiendraient: 6 × 5, 2 × 15, 3 × 10, 2x3x5, 30 × 1. À ce stade, la lumière ne saurait pas exactement ce qu’est le message, mais cela aurait certainement restreint les possibilités: il sait que c’est un nombre entre 1, 2, 3, 5, 6, 10, 15, 30. En bref, Multiply par 5 semble ne pas être une tactique alors si impénétrable. Alors comment le faire?
C’est là que je Nombres premiers: rompre Un nombre en tant que produit des nombres est d’autant plus difficile Plus les premiers nombres qui le font. Si au lieu du numéro 5, nous avons utilisé un énorme premier numéro comme clé, pour notre avertissement de décomposer le nombre, il pourrait devenir une tâche si ardue et longue qu’elle le rend.
Du coffre aux nombres premiers: ce que les rois numériques auraient fait
Revenons à l’histoire de Deux rois Et nous essayons de mieux comprendre comment les nombres peuvent remplacer les deux Cadlocks avec deux Clés numériques secrètes, Chacune des deux notes uniquement au roi qui le possède. Imaginons que King Gino et King Pino vivent aujourd’hui, puis utilisent le numérique. Que pourraient-ils faire pour tromper les espions? Par exemple, ils pourraient le faire:
- King Gino chiffre le message 6 le multiplier par le Première clé numériquepar exemple 5 (nous utilisons un petit premier numéro pour la commodité, mais comme nous l’avons mentionné ci-dessus, le meilleur choix est d’utiliser un énorme premier numéro!); Une fois crypté, envoyez 6 × 5 =30 au roi pino;
- King Pino Multiply 30 pour Deuxième clé personnellepar exemple 7, et envoyer 30 × 7 =210 au roi Gino;
- Le roi Gino prend son « cadenas » dividende 210 pour première cléSignifiant quoi 5, et envoyer 42 au roi pino;
- À ce stade, le roi Pino peut complètement déchiffrer le message avec le deuxième clédividende 42 Pour 7 Et obtenez le message de départ: 6.
Dans l’image ci-dessus, vous pouvez voir comment le message 6 commence du roi Gino et arrive au roi Pino sans jamais être visible car il voyage toujours caché, d’abord à l’intérieur du numéro 30alors dans 210 et enfin dans 42.
Beaucoup protocoles de communication – c’est-à-dire que les processus utilisés pour faire des messages que nous utilisons aussi sûrs que possible – sont basés sur des solutions similaires à celles adoptées par les deux rois numériques et, même s’ils cryptent des messages avec des opérations plus compliquées qu’une simple multiplication, utilisent toujours le produit de très grands nombres premiers. L’un des plus populaires s’appelle RSA Et il a été rendu public en 1977 grâce à un défi qui a prévu la décomposition en premiers facteurs d’un certain nombre de 129 chiffres: ce n’est qu’en 1994 qu’une équipe de 600 volontaires a réussi à relever le défi, après 17 ans, une fois que cela aurait fait une lumière désistation!