Cryptage probabiliste

Le chiffrement probabiliste est l'utilisation du caractère aléatoire dans un algorithme de chiffrement , de sorte que lorsque le même message est chiffré plusieurs fois, il produira en général des textes chiffrés différents . Le terme « chiffrement probabiliste » est généralement utilisé en référence aux algorithmes de chiffrement à clé publique ; cependant, divers algorithmes de chiffrement à clé symétrique atteignent une propriété similaire (par exemple, les chiffrements par blocs lorsqu'ils sont utilisés dans un mode de chaînage tel que CBC ) et les chiffrements par flux tels que Freestyle qui sont intrinsèquement aléatoires. Pour être sémantiquement sécurisé , c'est-à-dire pour cacher même des informations partielles sur le texte en clair , un algorithme de chiffrement doit être probabiliste .

Le premier système de chiffrement à clé publique probabiliste dont la sécurité est prouvée a été proposé par Shafi Goldwasser et Silvio Micali , basé sur la difficulté du problème de résiduosité quadratique et avait un facteur d'expansion de message égal à la taille de la clé publique. Les algorithmes de chiffrement probabiliste les plus efficaces incluent Elgamal , Paillier et diverses constructions sous le modèle d'oracle aléatoire , y compris OAEP.

Le chiffrement probabiliste est particulièrement important lors de l'utilisation de la cryptographie à clé publique . Supposons que l' adversaire observe un texte chiffré et soupçonne que le texte en clair est soit « OUI » soit « NON », ou qu'il ait l'impression que le texte en clair pourrait être « ATTAQUE À CALAIS ». Lorsqu'un algorithme de chiffrement déterministe est utilisé, l'adversaire peut simplement essayer de chiffrer chacune de ses suppositions sous la clé publique du destinataire et comparer chaque résultat au texte chiffré cible. Pour lutter contre cette attaque, les systèmes de chiffrement à clé publique doivent incorporer un élément aléatoire, garantissant que chaque texte en clair correspond à l'un des nombreux textes chiffrés possibles.

Une approche intuitive pour convertir un schéma de chiffrement déterministe en schéma probabiliste consiste simplement à compléter le texte en clair avec une chaîne aléatoire avant de le chiffrer avec l' algorithme déterministe . Inversement, le déchiffrement implique l'application d'un algorithme déterministe et l'ignorance du remplissage aléatoire. Cependant, les premiers schémas qui appliquaient cette approche naïve ont été brisés en raison des limitations de certains schémas de chiffrement déterministes. Des techniques telles que le remplissage de chiffrement asymétrique optimal (OAEP) intègrent le remplissage aléatoire d'une manière sécurisée en utilisant n'importe quelle permutation de trappe .

Exemple de chiffrement probabiliste utilisant n’importe quelle permutation de trappe :

• x - texte en clair sur un seul bit
• f - permutation à trappe (algorithme de chiffrement déterministe)
• b - prédicat du noyau dur de f
• r - chaîne aléatoire

Cette méthode est inefficace car un seul bit est chiffré. En d'autres termes, le facteur d'expansion du message est égal à la taille de la clé publique.

Exemple de cryptage probabiliste dans le modèle d'oracle aléatoire :

• x - texte en clair
• f - permutation à trappe (algorithme de chiffrement déterministe)
• h - oracle aléatoire (généralement implémenté à l'aide d'une fonction de hachage spécifiée publiquement )
• r - chaîne aléatoire