12 Avril 2021
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
Code de Shannon-Fano
Pour toute variable aléatoire
Entropie d'un symbole :
Entropie par symbole :
Il est important de rappeler les termes corrects à utiliser lorsque l'on parle de cryptographie.
Pour plus d'informations, voir ce site
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 déchiffrer 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
| Nom | Type de chiffrement |
|---|---|
| Cartes et systèmes bancaires | RSA |
| Fichiers "secret défense" de la NSA | AES |
| Commerce électronique | SSL ou TLS |
| Réseau Wifi | WEP, WPA ou WPA2 |
| Accès client/serveur | SSH (utilise le RSA ou DSA) |
| PGP (RSA ou DSA) |
Catégorisation de certains systèmes de chiffrement
| Chiffrement symétrique | Chiffrement asymétrique |
|---|---|
| AES | RSA |
| DES | McEliece |
| IDEA | DSS/DSA |
| Menezes-Vanstonne | ElGamal |
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 historiques :
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 :
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.
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.
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.
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
Ainsi, Bob récupère correctement le message d’Alice.