Théorie de Shannon

2024-2025 Cryptographie - Asmae EL KASSIRI 41

Théorie de Shannon
• Claude Shannon, mathématicien et ingénieur américain considéré comme le « père de l’âge
de l’information ».
• Shannon créa la théorie de l’information en 1948, dans un seul article — A Mathematical
Theory of Communication — le résultat de plusieurs années de recherche.
• La théorie de l'information, sans précision, est le nom usuel désignant la théorie de
l'information de Shannon, qui est une théorie utilisant les probabilités pour quantifier le
contenu moyen en information d'un ensemble de messages, dont le codage informatique
satisfait une distribution statistique que l'on pense connaître.
• Parmi les branches importantes de la théorie de l'information de Shannon, on peut citer :
• le codage de l'information,
• la mesure quantitative de redondance d'un texte,
• la compression de données,
• la correction d'erreurs,
• la cryptographie.

2024-2025 Cryptographie - Asmae EL KASSIRI 42

Théorie de Shannon
• Le paradigme de Shannon
• Un message émis par une source d’information est transmis dans un canal bruité puis reçu par le
destinataire.
• On y distingue clairement les rôles de la source, du canal et du destinataire; de l’émetteur et du récepteur;
et du signal et du bruit.
• La théorie mathématique de la communication vise à étudier de façon mathématique dans
quelles conditions on peut transmettre des données, en particulier à quelle vitesse, et avec
quelle fiabilité

Réseaux informatiques

2024-2025 Cryptographie - Asmae EL KASSIRI 43

Théorie de Shannon
• La source est l’entité qui possède une information, un message, à transmettre à son
destinataire:
• La source peut-être une station de radio ou de télévision, un journal, un site web, deux personnes désirant
annoncer une mauvaise nouvelle au téléphone ou par courrier électronique, une sonde spatiale prenant
des photos des planètes qu’elle survole, etc.
• Le message peut-être un texte, une photographie, un morceau de musique, une combinaison de ceux-ci.
• L’émetteur est l’appareil physique par lequel nous allons diffuser ce message, c’est par
exemple un émetteur de radio ou de télévision.
• À l’époque de Shannon, la transmission était souvent analogique. Dans le cas du téléphone ou de la radio,
le son est représenté par l’amplitude de la pression sur le micro que ce dernier transforme en un signal
électrique proportionnel.
• Il s’agit donc de transmettre cette amplitude, représentée par une fonction du temps, ou par deux telles
fonctions pour un signal stéréo.

2024-2025 Cryptographie - Asmae EL KASSIRI 44

Théorie de Shannon
• Le récepteur est l’appareil par lequel le destinataire reçoit ce message
• C’est un poste de radio ou de télévision, éventuellement associé à un «décodeur» dans le cas de la
télévision numérique terrestre ou de la télévision par Internet, un téléphone, un ordinateur relié au réseau
Internet, etc.
• Le canal est le medium physique par lequel l’information est transmise de l’émetteur au
récepteur :
• L’air pour la transmission de la radio/télévision par voie hertzienne, la fibre optique du fournisseur
Internet, les câbles en cuivre du réseau de téléphone, etc.
• Comme tout objet physique, ce canal est sujet à des perturbations (du bruit) par lesquelles le signal qui
parvient au récepteur diffère de celui envoyé par l’émetteur, de sorte que le message reçu par le
destinataire diffère de celui envoyé par la source.

2024-2025 Cryptographie - Asmae EL KASSIRI 45

Théorie de Shannon
• Shannon propose une mesure de la « quantité d’information » contenue dans un message,
qu’il appelle entropie.
• L'entropie est une mesure du désordre ou de l'aléa dans un système.
• L’entropie conditionnelle: la quantité d'information nécessaire pour connaitre le comportement d'une
variable aléatoire Y, lorsque l'on connait exactement une variable aléatoire X
• L’entropie conjointe: mesure la quantité d'information contenue dans un système de deux variables
aléatoires (ou plus de deux)
• L’entropie de Shannon: est une fonction mathématique qui, intuitivement, correspond à la
quantité d'information contenue ou fournie par une source d'information.
• Théorie de Shannon:
• Définit comment l'information peut être codée, compressée et transmise avec une efficacité maximale.
• Inclut des concepts comme le débit maximal d'un canal de communication, le bruit qui peut altérer le
signal et la capacité du canal, c’est-à-dire le débit maximum d’information transmissible sans erreur.
•  Shannon a aussi introduit des notions de redondance et de correction d'erreurs.

2024-2025 Cryptographie - Asmae EL KASSIRI 46

Théorie de Shannon
• Domaines d’application:
• Réseaux: La théorie de Shannon n'est pas directement implémentée dans le modèle OSI, mais ses
principes influencent la façon dont certaines couches du modèle OSI gèrent le codage, le débit et la
correction d'erreurs, contribuant ainsi à optimiser la transmission de données
• Couche Physique (couche 1) : La couche physique concerne le support de transmission, et les principes de
Shannon y sont fondamentaux pour évaluer la capacité de transmission, en fonction de la largeur de bande et du
bruit du canal. La théorie de Shannon aide à déterminer le débit maximal réalisable pour éviter la perte de
données.
• Couche Liaison de Données (couche 2) : Les techniques de détection et de correction d'erreurs, comme les codes
de redondance cycliques (CRC), permettent de corriger des erreurs causées par le bruit. Shannon a montré
comment des codes bien conçus peuvent réduire le taux d’erreur, ce qui est crucial pour les protocoles de la
couche liaison.
• Couche Réseau (couche 3) et Transport (couche 4) : Ces couches utilisent des techniques de segmentation, de
contrôle de flux, et de correction d'erreurs, des concepts qui découlent des travaux de Shannon sur la gestion et
la correction des erreurs pour des canaux bruyants.
• Apprentissage automatique : La mesure de l’entropie de Shannon aide à quantifier l’incertitude et à
améliorer les algorithmes d’apprentissage.
• Analyse des données : Elle permet de mesurer la redondance et de compresser les données, ce qui est
crucial pour le stockage et le traitement des grandes quantités de données.
2024-2025 Cryptographie - Asmae EL KASSIRI 47
Théorie de Shannon
• Domaines d’application:
• Cryptographie: (1)
• La théorie de Shannon offre des outils pour évaluer, renforcer et théoriser la sécurité des systèmes
cryptographiques, posant des bases mathématiques qui continuent d’inspirer le développement de
nouvelles techniques et algorithmes de cryptographie.
• Entropie et incertitude:
• Un système cryptographique sûr doit avoir une entropie élevée, ce qui signifie que les messages sont
difficiles à prédire ou à deviner.
• En pratique, cela se traduit par la création de clés suffisamment aléatoires et complexes pour garantir la
sécurité.
• Confusion et diffusion:
• La confusion implique que la relation entre le texte en clair (le message non chiffré) et le texte chiffré doit
être aussi complexe que possible pour masquer l'information.
• La diffusion consiste à répartir les informations du texte clair sur l'ensemble du texte chiffré pour rendre les
schémas d'attaque plus difficiles.
• Capacité des canaux et théorie des codes:
• L’objectif est de concevoir des protocoles cryptographiques pour la transmission de données de manière
sécurisée même dans des canaux bruyants ou à risque d'interception.

2024-2025 Cryptographie - Asmae EL KASSIRI 48

Théorie de Shannon
• Domaines d’application:
• Cryptographie: (2)
• Sécurité parfaite:
• Le chiffrement doit reposer sur une clé aléatoire à utiliser une seule fois.
• Analyse d'entropie et génération de clés:
• Plus la clé est complexe et aléatoire, plus elle est difficile à deviner ou à casser.
• En pratique, des générateurs de nombres aléatoires (RNG) sont utilisés pour créer des clés avec un
maximum d'entropie, afin d'empêcher les attaques basées sur des modèles ou des répétitions.
• Compression d'information et obfuscation:
• L’objectif est de cacher des informations dans un support numérique (comme une image ou un son).
• En réduisant la redondance et en optimisant la compression, on peut dissimuler les informations de manière
plus efficace, rendant la détection plus difficile.
• Évaluation de la robustesse des algorithmes cryptographiques:
• La théorie de l'information permet de calculer la quantité d’information qui fuit lorsque des textes chiffrés
sont interceptés.
• En analysant les relations statistiques entre les messages et les clés, on peut estimer la résistance d'un
algorithme face aux attaques, notamment pour les attaques par analyse différentielle et linéaire.

2024-2025 Cryptographie - Asmae EL KASSIRI 49

Théorie de Shannon
• Théorème du secret parfait de Shannon
• Principes de Shannon: Un chiffre doit apporter de la confusion et de la diffusion
• Confusion: Il n’y a pas de relation algébrique simple entre le clair et le chiffré
• En particulier, connaître un certain nombre de couples clair-chiffré ne permet pas d’interpoler la fonction de
chiffrement pour les autres messages
• Tout le contraire d’un chiffre affine.
• Diffusion: La modification d’une lettre du clair doit modifier l’ensemble du chiffré
• On ne peut pas casser le chiffre morceau par morceau
• Tout le contraire d’un chiffre mono-alphabétique
• Soit un crypto-système.
• On suppose que , et que pour tout clair .
• Alors ce crypto-système à secret parfait si et seulement si
• la distribution des clefs suit une loi uniforme ;
• pour tout message clair ,
𝐾→𝐶
ϕ : est une bijection
k ↦ e(m,k)
2024-2025 Cryptographie - Asmae EL KASSIRI 50
Théorie de Shannon
• Théorème du secret parfait de Shannon
• Un chiffrement possède un secret parfait si :
• La clé est aléatoire et aussi longue que le message.
• La clé est utilisée une seule fois (d'où le nom One-Time Pad).
• La clé est secrète et connue seulement de l'expéditeur et du destinataire.
• Exemples:
• Chiffrement de Vigenère:
• Il convient à condition que la clef soit tirée uniformément parmi les chaînes de même longueur que le message.
• Et pour ne pas divulguer cette longueur, il faut même se placer dans un espace de messages de longueur fixée suffisante,
au moyen de Padding.
• Chiffrement de Vernam:
• Le masque jetable, également appelé chiffre de Vernam (du nom de son inventeur en 1917 : Gilbert Vernam) ou OTP (pour
one-time pad en anglais), est un algorithme de cryptographie.
• Il s'agit essentiellement d'un chiffrement par substitution basique, comme le chiffre de Vigenère ou le code de César, avec
une clé aléatoire au moins aussi grande que le message à transmettre et qui n'est utilisée qu'une fois.
• Il n’est autre que le xor du message et de la clef  la clef ne doit être utilisée qu’une fois, puisque m⊕k⊕m=k (attaque à
clair connu sur la clef).

2024-2025 Cryptographie - Asmae EL KASSIRI 51

 Théorie de Shannon
• Principes de la cryptographie moderne
• Principe de Kerchkoffs: La sécurité d’un chiffre ne doit pas reposer sur le secret de la
méthode, mais sur le secret de la clef utilisée.
• Le premier à avoir formalisé ce principe est le hollandais Auguste Kerckhoffs, qui écrit en 1883 dans le
Journal des sciences militaires un article intitulé La cryptographie militaire.
• On peut résumer ces conditions sous les éléments suivants :
• 1. La clé doit pouvoir être communiquée et retenue sans le secours de notes écrites, et être changée ou
Les points 1 et 3 modifiée au gré des correspondants;
sont les axiomes
• 2. Le système doit être matériellement, sinon mathématiquement indéchiffrable;
fondamentaux de
la cryptographie • 3. Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi;
moderne • 4. La clé doit pouvoir être communiquée et retenue sans le secours de notes écrites, et être changée ou
modifiée au gré des correspondants;
• 5. Il faut qu’il soit applicable à la correspondance télégraphique;
• 6. Il faut qu’il soit portatif, et que son maniement ou son fonctionnement n’exige pas le concours de
plusieurs personnes;
• 7. Enfin, il est nécessaire, vu les circonstances qui en commandent l’application, que le système soit d’un
usage facile, ne demandant ni tension d’esprit, ni la connaissance d’une longue série de règles à observer.

2024-2025 Cryptographie - Asmae EL KASSIRI 52

Théorie de Shannon
• Principes de la cryptographie moderne
• Principe de Kerchkoffs:
• La sécurité d’un chiffre ne doit pas reposer sur le secret de la méthode, mais sur le
secret de la clef utilisée.
• Ce principe repose sur les arguments suivants :
• La transparence : Un cryptosystème sera d’autant plus résistant et sûr qu’il aura été conçu, choisi
et implémenté avec la plus grande transparence
• Soumis ainsi à l’analyse de l’ensemble de la communauté cryptographique
• La portabilité : Si un algorithme est supposé être secret, il se trouvera toujours quelqu’un soit
pour vendre l’algorithme, soit pour le percer à jour, soit pour en découvrir une faiblesse ignorée
de ses concepteurs.
• A ce moment là c’est tout le cryptosystème qui est à changer et pas seulement la clé.

2024-2025 Cryptographie - Asmae EL KASSIRI 53

Atelier
• Exercice 2: secret parfait de shannon
• 1. Illustration du secret parfait avec un cryptage de Vernam (XOR)
• Génération d’une clé aléatoire de même longueur que le message.
• Chiffrement avec XOR entre chaque caractère du message et la clé.
• Déchiffrement avec XOR en utilisant la même clé.
• Vérification qu’une clé incorrecte ne permet pas de retrouver le message original.
• 2. Implémenter une transposition avec la clé: [8, 4, 7, 6, 1, 2, 5, 3]
• Principe: Réarrangement selon une clé d'ordre
• Le texte est découpé en blocs de même taille que la clé.
• Chaque caractère est réorganisé selon l’ordre des indices dans la clé de permutation
• Exemple: message clair= « messages » et cle = [4, 2, 1, 3]  la 1ère lettre du bloc chiffré sera la 4ᵉ lettre du bloc clair, etc.
• Objectif:
Clé 1 2 3 4 1 2 3 4
• Définir les fonctions Transposer et DeTransposer
Message Clair m e s s a g e s
• Initialiser un texte à chiffrer
• Utiliser la fonction de chiffrement et afficher le résultat Message Crypté s e m s s g a e

• Utiliser la fonction de déchiffrement avec une clé correcte et une clé erronée et afficher les résultats

2024-2025 Cryptographie - Asmae EL KASSIRI 54

Atelier
• Exercice 2: secret parfait de shannon
• 3. Implémenter la permutation de César
• Principe: Le chiffre de César décale chaque lettre de l’alphabet d’un certain nombre de positions.
Exemple avec un décalage de 3
• A→D
• B→E
• X→A
• Objectif:
• Définir les fonctions chiffrerCesar et DechiffrerCesar
• Initialiser un texte à chiffrer
• Utiliser la fonction de chiffrement et afficher le résultat
• Utiliser la fonction de déchiffrement avec la permutation correcte et une permutation erronée et afficher les résultats

2024-2025 Cryptographie - Asmae EL KASSIRI 55