Page non complète

Théorie de l'information

Mesure et encodage de l'information

Formule de l'entropie de Shannon 1

Par convention, lorsque la base b n'est pas précisé, on utilise la base 2 (système binaire) : b = 2.

Information Theory (IT) inequality :

pour tout .

La longueur moyenne des codewords :

Nous avons la propriété suivante :
Soit une fonction d'encodage d'un D-ary code pour une distribution (variable aléatoire) . Si le code est uniquely decodable, alors :

Code de Shannon-Fano
Pour toute variable aléatoire and tout entier , il existe un code D-ary sans préfixe pour S, tel que ,

Entropie d'un symbole :

Entropie par symbole :

Cryptographie

Vocabulaire

Il est important de rappeler les termes corrects à utiliser lorsque l'on parle de cryptographie.

  • Chiffrer : action de transformer un texte dit "en clair" en un autre dit "secret" (ciphertext en anglais) à l'aide d'une clé de chiffrement
  • Déchiffrer : action de retrouver le texte dit "en clair" à l'aide d'une clé de déchiffrement
  • Décrypter : action de retrouver le texte dit "en clair" sans clé de déchiffrement (peut être fait pour certains messages par analyse statistique ou par force brute)
  • Crypter : ce verbe n'existe pas

Pour plus d'informations, voir ce site

Introduction

Premièrement il y a ce qu'on appelle les systèmes de cryptographie symétriques. Ici nous utilisons une seule clé de chiffrement. Prenons deux interlocuteurs A et B. Si A veut envoyer un message chiffré à B il va utiliser une fonction de chiffrement avec les données de la clé de chiffrement. Lorsque B va recevoir le message de A, il va devoir utiliser une fonction de déchiffrement (la fonction "inverse" de la fonction de chiffrement) avec la même clé que A.

Ici, les fonctions de chiffrement et de déchiffrement sont très rapides mais un problème se pose : pour que A et B utilise la même clé, il va falloir l'échanger. Et pendant ce cours échange de clé entre A et B, une personne malveillante risque d'intercepter la clé en toute discrétion et de la renvoyer à B. Cette personne sera alors capable de dechiffrer les informations, ce qui brise la confidentialité établie entre A et B.

Ceci est à l'origine de l'attaque du type "Homme du milieu" (Man in the Middle en anglais).

Le deuxième système est le chiffrement asymétrique. Dans celui-ci, si A veut envoyer un message chiffré à B, il va devoir utiliser deux clés : une clé publique et une clé privée. La clé publique est accessible à tous. C'est en utilisant la clé publique de A que B sera en mesure de déchiffrer le message de A qu'il aura chiffré à l'aide de sa clé privée.

Avec ce système, il n'y a pas d'échange de clé, en revanche les fonctions de chiffrement et de déchiffrement sont plus lentes que celle du chiffrement symétrique. De plus, la sécurité de ce genre de système repose sur le fait qu'avec les ordinateurs actuels, il serait extrêmement long de retrouver la clé privée d'un individu à partir de sa clé publique (accessible à tous). Ce qu'il faut comprendre est qu'il est techniquement possible de déchiffrer toute conversation utilisant du chiffrement assymétrique, mais tout cela dans un temps déraisonné.

Différentes applications de la cryptographie

NomType de chiffrement
Cartes et systèmes bancairesRSA
Fichiers "secret défense" de la NSAAES
Commerce électroniqueSSL ou TLS
Réseau WifiWEP, WPA ou WPA2
Accès client/serveurSSH (utilise le RSA ou DSA)
EmailPGP (RSA ou DSA)

Catégorisation de certains systèmes de chiffrement

Chiffrement symétriqueChiffrement asymétrique
AESRSA
DESMcEliece
IDEADSS/DSA
Menezes-VanstonneElGamal

Non discuté ici, il peut être intéressant de se renseigner sur le chiffrement homomorphe et son potentiel d'utilisation pour le cloud.

En cryptographie, les prénoms Alice et Bob sont généralement utilisés pour nommer deux interlocuteurs. Le prénom Eve est utilisé pour désigner une personne tiers qui écoute secrètement la conversation.

Pour découvrir une liste d'autres prénoms utilisés : page Wikipédia.

Systèmes de chiffrement symétriques

Systèmes de chiffrement historiques :

  • chiffrement de César
  • chiffre de Vigenère

Définition (Perfect Secrecy)
Un cryptosystème est à secret parfait si son text clair (plaintext) T et le text chiffré correspondant (cyphertext) C sont statistiquement indépendant.

Résultat important :
Soit un système de chiffrement symétrique de clé K. Pour que ce système soit à secret parfait, il faut qu'il vérifie pour tout text clair T :

Systèmes de chiffrement asymétriques

Pour comprendre davantage le fonctionnement de tels systèmes, il est obligatoire d'avoir des notions de théorie des nombres et d'arithmétique modulaire.

Chiffrement RSA

RSA, pour Rivest Shamir Adleman est un chiffrement apparu en 1977. Il a été créé par Ronald Rivest, Adi Shamir, et Leonard Adleman.

Décrivons le fonctionnement de ce système lorsqu’Alice veut envoyer un message à Bob. Pour se faire, Bob va avoir besoin de créer ses deux clés : une clé privée et une clé publique.

Étapes à suivre pour Bob :
  • Il choisit deux nombres premiers distincts p et q. Afin de garantir la sécurité du chiffrement, ces deux nombres doivent être suffisamment grands. On peut imaginer deux nombres premiers de 1024 bits, ce qu’il est d’usage de faire.

  • Notons m = pq, qui va nous servir de module : toutes les opérations suivantes vont être effectuées dans .

  • Ensuite, Bob choisit un entier k, multiple de (p-1) et (q-1).

    p et q étant distincts, il est alors tout a fait approprié de choisir l’indicatrice d’Euler en pq :

  • Il choisit un entier e premier avec k, autrement dit : gcd(e, k) = 1.

  • D’après l’identité de Bézout, il existe des entiers d et l tels que :

    On a ainsi : .

    On retient d, qui est donc l’inverse de e modulo k.

Création des clés :
  • (m, e) devient la clé publique de Bob
  • (m, d) devient sa clé privée
Transmission du message :

Alice va envoyer à Bob le message c (chiffré) correspondant à cette transformation effectuée sur son message en clair t suivant :

Alice a donc utilisé les éléments de la clé publique de Bob.

Bob reçoit ainsi et déchiffre ce message grâce à la relation suivante :

Ainsi, Bob récupère correctement le message d’Alice


  1. Claude Elwood Shannon (30 avril 1916 à Petoskey, Michigan - 24 février 2001 à Medford, Massachusetts) est un ingénieur en génie électrique et mathématicien américain. Il est l'un des pères, si ce n'est le père fondateur, de la théorie de l'information.