Gambling with Secrets: Part 7/8 (Diffie-Hellman Key Exchange)

Summary

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, 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

00:00

🌐 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.

05:02

🔐 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é.

Keywords

💡Guerre froide

La Guerre froide fait référence à la période de tensions politiques et militaires entre les États-Unis et l'Union soviétique après la Seconde Guerre mondiale. Dans la vidéo, elle est mentionnée comme le contexte historique qui a poussé les deux superpuissances à développer des systèmes de défense nucléaire, comme NORAD, pour prévenir les attaques potentielles.

💡NORAD

NORAD (Commandement de la défense aérospatiale de l'Amérique du Nord) est une organisation militaire conjointe entre les États-Unis et le Canada, créée en 1958. Elle joue un rôle clé dans la surveillance et la défense aérienne de l'Amérique du Nord, particulièrement contre les attaques de missiles nucléaires à longue portée. Ce concept est central dans la vidéo car il illustre la réponse technologique face à la menace d'attaques intercontinentales pendant la Guerre froide.

💡Système semi-automatique au sol

Le système semi-automatique au sol (SAGE) était un réseau de radars automatisés qui surveillait l'espace aérien nord-américain. Ce système, composé de plus de 100 radars à longue portée, permettait de transmettre des données via des lignes téléphoniques ou des ondes radio. La vidéo le mentionne pour souligner l'importance des technologies de communication automatique dans la défense aérienne.

💡Modularité arithmétique

La modularité arithmétique, également appelée arithmétique des horloges, est un concept mathématique dans lequel les nombres « tournent » autour d'un certain mod (modulus). Par exemple, 46 mod 12 équivaut à 10. Ce concept est essentiel pour comprendre le chiffrement moderne expliqué dans la vidéo, notamment dans la façon dont les nombres sont transformés pour sécuriser les communications.

💡Chiffrement

Le chiffrement est une méthode de sécurisation de l'information en la transformant de manière à ce qu'elle ne puisse être lue que par des parties autorisées. Dans la vidéo, il est crucial pour protéger les communications sur des réseaux numériques. L'exemple donné est la méthode développée par Diffie et Hellman pour échanger des clés de manière sécurisée, sans que des tiers puissent intercepter les informations.

💡Problème du logarithme discret

Le problème du logarithme discret est un défi mathématique qui consiste à inverser certaines opérations arithmétiques, ce qui est très difficile avec des grands nombres. Dans la vidéo, ce problème est à la base des fonctions à sens unique, rendant le chiffrement sûr et difficile à casser par des attaquants comme 'Eve'.

💡Clé secrète

La clé secrète est un élément central du chiffrement. Dans la vidéo, elle est décrite comme un nombre que deux parties (Alice et Bob) doivent partager pour sécuriser leur communication. Cependant, l'échange de cette clé sans qu'un tiers (comme Eve) ne l'intercepte est un des grands défis résolus par l'algorithme de Diffie-Hellman.

💡Générateur

Un générateur, dans le contexte du chiffrement, est un nombre utilisé pour générer une série de valeurs en exponentiation dans un cadre modulaire. Dans la vidéo, le chiffre 3 est choisi comme générateur, car il possède la propriété de distribuer uniformément les résultats lorsqu'il est élevé à différentes puissances dans un système modulaire. Cela est essentiel pour créer des résultats aléatoires et sécurisés dans le cadre du chiffrement.

💡Algorithme Diffie-Hellman

L'algorithme Diffie-Hellman est une méthode de cryptographie qui permet à deux parties d'échanger une clé secrète de manière sécurisée, même si un tiers écoute la communication. La vidéo l'explique en utilisant des couleurs comme métaphore et montre comment les deux parties peuvent partager un secret sans que l'espion, Eve, ne puisse le déchiffrer.

💡Fonction à sens unique

Une fonction à sens unique est une opération facile à effectuer dans un sens, mais très difficile à inverser sans certaines informations. Dans la vidéo, ce concept est illustré par l'idée de mélanger des couleurs ou de réaliser des calculs modulaires, ce qui est simple à faire mais difficile à défaire sans connaître des détails cruciaux comme les couleurs ou les clés privées.

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