Gambling with Secrets: Part 7/8 (Diffie-Hellman Key Exchange)
Summary
TLDRAprès la Seconde Guerre mondiale, les tensions entre l'Union soviétique et les États-Unis ont conduit à la création du NORAD en 1958, un système de défense contre les missiles balistiques intercontinentaux. Ce système a favorisé le développement des réseaux informatiques et de la communication machine-à-machine. Avec l'expansion d'Internet, la sécurité des transactions en ligne a nécessité l'encryption. En 1976, Diffie et Hellman ont inventé un moyen de partager une clé secrète en utilisant une fonction unidirectionnelle basée sur l'arithmétique modulée, qui est facile à effectuer mais difficile à inverser, offrant ainsi une sécurité cryptographique robuste.
Takeaways
- 🌐 Après la Seconde Guerre mondiale, la tension entre l'Union soviétique et les États-Unis a conduit à la création du NORAD pour défendre contre les attaques nucléaires.
- 🛡️ Le système SAGE (Semi-Automatic Ground Environment) était un réseau de radars automatisés pour suivre les missiles intercontinentaux.
- 🏰 Le Centre d'alerte primaire du NORAD était situé dans la montagne Cheyenne au Colorado, protégé et connecté à travers des lignes téléphoniques et des ondes radio.
- 💡 L'idée de la communication en ligne a été adoptée et améliorée par les universités, qui ont compris son potentiel pour le travail collaboratif.
- 🔐 Avec l'expansion d'Internet, la sécurité des transactions en ligne a nécessité le développement de l'encryptage pour protéger les données.
- 🔑 Diffie et Hellman ont inventé en 1976 un moyen de partager des clés secrètes entre deux parties sans que des écouteurs non autorisés ne puissent les obtenir.
- 🎨 La métaphore des couleurs est utilisée pour expliquer comment deux personnes peuvent déterminer une couleur secrète commune sans la divulguer.
- 🔄 La fonction unidirectionnelle, qui est facile à effectuer dans un sens mais difficile dans l'autre, est au cœur de la méthode de partage de clés secrètes.
- 🔢 L'arithmétique modulée, aussi connue que l'arithmétique du compteur, est utilisée pour créer des fonctions unidirectionnelles avec des nombres.
- 🔒 Le problème du logarithme discret est utilisé pour rendre la détermination de la clé secrète difficile, même avec des ressources de calcul immenses.
- 🌐 La force de l'encryptage repose sur la difficulté et le temps nécessaire pour inverser la fonction unidirectionnelle, rendant pratiquement impossible la violation de la sécurité.
Q & A
Quelle était la principale préoccupation des États-Unis et de l'Union soviétique après la Seconde Guerre mondiale?
-La principale préoccupation était de pouvoir lancer et défendre avec succès des attaques nucléaires intercontinentales.
Pourquoi NORAD a-t-il été créé en 1958?
-NORAD a été créé pour fournir une défense contre les attaques potentielles de missiles balistiques intercontinentaux, en particulier par-dessus le Pôle Nord.
Quel rôle jouait le SAGE (Semi-Automatic Ground Environment) dans le système de défense de NORAD?
-Le SAGE était un système automatisé de plus de 100 radars à longue distance connectés à des systèmes informatiques pour suivre et transmettre des données de suivi.
Où se trouvait le Centre d'alerte principal de NORAD?
-Le Centre d'alerte principal était situé à l'intérieur de la montagne Cheyenne, au Colorado.
Comment les universités ont-elles adapté l'idée d'être en ligne après la Seconde Guerre mondiale?
-Les universités ont compris le potentiel des réseaux informatiques pour connecter des travailleurs et des équipes géographiquement dispersés, et pour accéder à des bases de données.
Quel problème est apparu avec la croissance d'Internet et l'encodage des transactions sécurisées?
-Un problème était que l'encodage nécessitait que deux parties partagent un secret, un nombre aléatoire appelé clé, et il était difficile de le faire sans que des écouteurs non autorisés ne l'obtiennent.
Qui a inventé la méthode pour permettre à deux personnes de partager une clé secrète sans la divulguer à un écoutant?
-Whitfield Diffie et Martin Hellman ont inventé une méthode en 1976 pour permettre cela.
Comment fonctionne la 'trick' de Diffie-Hellman pour partager une couleur secrète?
-Alice et Bob choisissent une couleur de départ commune, mélangent chacun une couleur privée à cette couleur, et échangent leurs mélanges. Ensuite, ils ajoutent leur couleur privée au mélange de l'autre personne pour obtenir une couleur secrète partagée.
Quel est le concept mathématique derrière la 'trick' de Diffie-Hellman?
-Le concept est basé sur une fonction à sens unique, où il est facile de mélanger deux couleurs pour en faire une troisième, mais difficile de retrouver les couleurs originales à partir de la couleur mélangée.
Quelle est la méthode utilisée pour implémenter la 'trick' de Diffie-Hellman avec des nombres?
-La méthode utilise l'arithmétique modulée, aussi connue que l'arithmétique du 'horloge', avec un modulo premier et une racine primitive pour calculer des exposants qui sont difficiles à inverser, ce qui fournit une fonction à sens unique.
Outlines
🌐 L'origine du réseau informatique et la sécurité
Après la Seconde Guerre mondiale, les tensions entre l'Union soviétique et les États-Unis ont conduit à la création du NORAD en 1958, une initiative conjointe entre les États-Unis et le Canada pour défendre contre les attaques nucléaires. Le système Semi-Automatic Ground Environment (SAGE) utilisait un réseau de radars connectés à des systèmes informatiques pour suivre les missiles intercontinentaux. Ce concept a été adapté par les universités pour le réseautage informatique, permettant une communication et une prise de décision rapide. Avec l'expansion d'Internet, la sécurité des transactions en ligne a nécessité l'encryption, ce qui a conduit à l'invention de la cryptographie à clé publique pour permettre aux utilisateurs de partager des secrets numériques sans être interceptés par des écouteurs.
🔐 La cryptographie à clé publique et les fonctions à sens unique
Pour s'assurer que la communication numérique reste sécurisée, les chercheurs ont dû trouver une méthode pour que deux personnes puissent partager un secret, comme un chiffre, sans le partager avec un éventuel écouteur. Whitfield Diffie et Martin Hellman ont inventé une méthode basée sur la propriété de mélanger des couleurs pour créer un code secret partagé. Cette méthode a été traduite en termes numériques en utilisant l'arithmétique modulo, où un grand nombre premier comme 17 sert de base et un générateur comme 3 est utilisé pour créer des nombres qui sont faciles à calculer dans une direction mais difficiles à inverser, ce qui est essentiel pour la sécurité de la cryptographie à clé publique. Les utilisateurs Alice et Bob peuvent ainsi partager un secret numérique en utilisant des calculs publics et privés qui, même si interceptés, sont pratiquement impossibles à déchiffrer sans connaître le nombre privé.
Mindmap
Keywords
💡Guerre froide
💡NORAD
💡Système semi-automatique au sol
💡Modularité arithmétique
💡Chiffrement
💡Problème du logarithme discret
💡Clé secrète
💡Générateur
💡Algorithme Diffie-Hellman
💡Fonction à sens unique
Highlights
After World War II, tensions between the Soviet Union and the United States led to the need for advanced defense systems against nuclear attacks.
The United States and Canada established NORAD in 1958 to protect against attacks over the North Pole.
SAGE, the Semi-Automatic Ground Environment, was a network of radars and computer systems that provided early warning for missile attacks.
The primary warning center for SAGE was located deep inside Cheyenne Mountain in Colorado.
Machine-to-machine communication allowed for rapid decision-making in defense operations.
Universities recognized the potential of computer networking for connecting geographically distributed workers and information.
The concept of being 'online' evolved to include electronic handling of various applications, including secure money transfers.
Encryption became crucial as the internet expanded, requiring secure communication between parties.
Whitfield Diffie and Martin Hellman developed a method in 1976 for secure key exchange without prior shared secrets.
The 'Diffie-Hellman key exchange' uses a one-way function to allow parties to agree on a secret key without an eavesdropper's knowledge.
The key exchange is based on the concept of mixing colors, where it's easy to mix but hard to reverse the process to find original colors.
Modular arithmetic, or clock arithmetic, provides a framework for the numerical procedure used in the key exchange.
A prime modulus and a generator are used to ensure the one-way function is easy to compute but hard to reverse.
The discrete logarithm problem is the challenge of reversing the one-way function, which is computationally difficult.
The strength of encryption lies in the time it takes to reverse the one-way function, making it impractical for an attacker to decrypt.
Alice and Bob can publicly agree on a prime modulus and a generator, then privately select numbers to compute a shared secret.
The shared secret is computed without revealing the private numbers, ensuring the security of the key exchange.
The Diffie-Hellman key exchange is a foundational protocol for secure communication over the internet.
Transcripts
[Music]
after World War II with most of Europe
and ruins tensions grew between the
Soviet Union and the United States it
was clear that the next Global
superpower required the ability to both
launch and successfully defend nuclear
attacks from intercontinental ballistic
missiles the United States most
vulnerable point of attack was over the
North Pole so in 1958 a joint effort
between United States and Canada was
established NORAD the North American
Aerospace Defense command an important
line of defense was the semi-automatic
ground environment it was an automated
system of over 100 longdistance Radars
scattered across North America they were
connected to computerized radar systems
that transmitted tracking data using
telephone lines or radio waves all this
information was fed into the primary
warning Center buried deep inside
Cheyenne Mountain in Colorado this
application of machine to machine
communication allowed operators to make
split-second decisions using the
information transmitted and processed
automatically by
computers this idea of being online was
quickly adapted and advanced by
universities in the following years as
they understood the potential of
computer networking the thing that makes
the computer communication Network
special is that it puts the workers the
the team members who are geographically
distributed in touch not only with one
another but with the information base
with which they work all the time and
this is obviously going to make a
tremendous difference in how we plan
organize and execute almost everything
of any intellectual consequence if we
get into a mode in which everything is
handled electronically and your only
identification is some little plastic
thing you stick into the Machinery then
I can imagine that they want to get that
settled up with your bank account just
right now and put it through all the
checks and that would require Network
money transfers were just one of a
growing number of applications which
require encryption to remain
secure as the internet grew to Encompass
Millions around the world a new problem
emerged at the time encryption required
two parties to First share a secret
random number known as a key how could
two people who have never met agree on a
key without letting Eve who is always
listening also obtain a
copy in
1976 Whitfield Diffy and Martin Helman
devised an amazing trick to do this
first let's explore how this trick is
done using colors how could Alice and
Bob agree on a secret color without Eve
finding it out the trick is based on two
facts one it's easy to mix two colors
together to make a third color and two
given a mixed color it's hard to reverse
it in order to find the exact original
colors this is the basis for a
lock easy in One Direction hard in the
reverse
Direction This is known as a one-way
function now the solution works as
follows first they agree publicly on a
starting color let's say yellow
next Alice and Bob both randomly select
private colors and mix them into public
yellow in order to disguise their
private
color now Alice keeps her private color
and sends her mixture to
Bob and Bob keeps his private color and
sends his mixture to
Alice now the heart of the
trick Alice and Bob add their private
colors to the other person person's
mixture and arrive at a shared secret
color notice how Eve is unable to
determine this
color since she needs one of the private
colors to do
[Music]
so and that's the
trick now to do this with numbers we
need a numerical procedure which is easy
in one dire C and hard in the other this
brings us to modular arithmetic which is
also known as clock arithmetic for
example to find 46 mod 12 we take a rope
of length 46
units and wrap it around a clock of 12
units which is called the
modulus and where the Rope ends is the
solution so we say 46 mod 12 is
congruent to 10 easy now to make this
work we need a prime modulus such as 17
instead of
12 then we find a primitive root of 17
in this case three which has this
important property that when raised to
different exponents the solution
distributes uniformly Around the
Clock three is known as the
generator so if we raise three to any
exponent x the solution is equally
likely to be any integer between 0 and
17 now the reverse procedure is
hard given 12 find the exponent three
needs to be raised to this is called the
discrete logarithm problem and now we
have our one-way function easy to
perform but hard to reverse given 12 we
would have to resort to trial and error
to find the matching
exponent how hard is this with small
numbers it's easy easy but if we use a
prime modulus which is hundreds of
digits long it gets seriously hard even
if you had access to all computational
power on Earth it could take thousands
of years to go through all possibilities
so the strength of a one-way function is
based on time needed to reverse
it now this is our
solution first Alice and Bob agree
publicly on a prime modulus and a
generator in this case 3 and 17 then
Alice selects a private random number
say 15 and calculates 3 to the^ of 15
mod 17 and sends the result publicly to
Bob then Bob selects his private random
number
13 and calculates 3 to the^ of 13 mod 17
and sends the result publicly to
Alice and now the heart of the trick
Alice takes Bob's public result and
raises it to the power of her private
number to obtain the shared secret which
in this case is
10 Bob takes Alice's public result and
raises it to the power of his private
number resulting in the same shared
secret now notice they did the same
calculation though it may not look like
it at first first look at Alice the 12
she received from
was calculated as 3 to ^ 13 mod 17 so
her calculation was the same as 3 to the
power of 13 to the power of 15 mod
17 now look at Bob the six he received
from Alice was calculated as 3 to ^ 15
mod
17 so his calculation was the same as 3
to the power of 15 to the power of 13
mod 17 notice they did the same
calculation with the exponents in a
different
order they both end up with three raised
to the power of their private numbers
without one of these private numbers 15
or 13 Eve will not be able to find the
solution this is how it's
done while Eve is stuck grinding away at
the discrete logarithm problem and with
large enough numbers we can say it's
practically impossible for her to break
the
encryption
5.0 / 5 (0 votes)