Comment le chiffrement peut-il impliquer un caractère aléatoire?

8

Si un algorithme de chiffrement est destiné à convertir une chaîne en une autre chaîne qui peut ensuite être déchiffrée de nouveau à l'original, comment ce processus pourrait-il impliquer un quelconque caractère aléatoire?

Elle doit certainement être déterministe, sinon comment la fonction de déchiffrement pourrait-elle savoir quels facteurs ont été impliqués dans la création de la chaîne chiffrée?

CJ7
la source
3
Veuillez ne pas poser de questions identiques sur plusieurs sites Stack Exchange, comme celui-ci sur Crypto.SE .
Paŭlo Ebermann

Réponses:

5

Il peut y avoir plus d'un texte chiffré qui correspond au même texte en clair. En termes mathématiques, l'algorithme de chiffrement doit être injectif afin que vous puissiez récupérer le texte en clair pour le texte chiffré, mais cela n'empêche pas le texte chiffré d'encoder plus d'informations que le texte en clair.

À titre d'exemple concret, considérons les modes de fonctionnement du chiffrement par blocs tels que CBC , CTR ou OFB . Tous ces modes impliquent un IV (vecteur d'initialisation) en plus du texte en clair, de l'algorithme de chiffrement par blocs et de sa clé. (Pour le CTR, le IV est appelé un nonce, mais il joue un rôle similaire.) La fonction de cryptage est déterministe pour un IV donné. Le IV, en revanche, peut être choisi au hasard (pour le CTR, il doit être choisi au hasard). Ainsi, à moins que le protocole ne spécifie une méthode déterministe de choix de l'IV (telle qu'une constante convenue), l'IV est envoyé avec le texte chiffré. En fait, la sortie du logiciel de cryptage se compose souvent du IV suivi du texte chiffré stricto sensu. Le IV lui-même est envoyé en clair; il ne contient (ne doit pas) contenir d'informations confidentielles.

Comme autre exemple, considérons le mode PKCS1.5 («schéma de remplissage») de RSA (défini dans PKCS # 1 version 1.5 - voir p.22-25 de PKCS # 1 v2.1 ). Simplifiant un peu, ce mode consiste à concaténer une chaîne aléatoire avec le message, puis à appliquer l'opération d'exponentiation. Le texte chiffré est où est la concaténation, est le message et est une chaîne de remplissage dont la plupart des bits sont aléatoires. Pour récupérer le message à partir du texte chiffré , appliquez l'opération de déchiffrement brute et divisez en remplissage (qui est supprimé) et message.(PM)emodnMPCCmodnC

Gilles 'SO- arrête d'être méchant'
la source
4

Non seulement les schémas de cryptage peuvent être aléatoires, mais dans certains cas (par exemple, le cryptage à clé publique ), ils doivent être randomisés. Ce n'est pas un problème car nous avons besoin d'un schéma de chiffrement pour être correct , c'est-à-dire que pour tout message et toute clé il contient sur le caractère aléatoire .mk

Pr[ DEC( ENC(k,m,R) )=m]=1
R

La raison pour laquelle les schémas de clés publiques doivent être aléatoires provient de la façon dont nous définissons la sécurité: nous ne souhaitons pas que le texte chiffré laisse fuir des informations sur le message chiffré. L'exemple classique est le suivant. Supposons que soit la clé publique et la clé secrète, respectivement, et que l'adversaire intercepte un message chiffré envoyé à une unité sur le terrain. L'adversaire sait que le message est "ATTACK" ou "RETREAT", mais ne sait pas lequel. Une chose que l'adversaire peut faire est de crypter les deux messages en utilisant le public . laissez et . Si(pk,sk)cpkcA=ENCpk("ATTACK ")cR=ENCpk("RETREAT")ENCest déterministe, l'adversaire peut découvrir le message avec certitude en comparant à et .ccAcR

La façon dont cette notion est formellement définie est connue sous le nom de sécurité sémantique :

Un schéma de chiffrement est sémantiquement sécurisé si un adversaire ne peut pas gagner le jeu suivant avec une probabilité sensiblement supérieure à :A1/2

  1. Un challenger génère des clés et envoie la clé publique à l'adversaire.C(pk,sk)pk
  2. A choisit deux messages de longueur égale et et les donne tous les deux à .m0m1C
  3. C sélectionne uniformément un bit et renvoie .b{0,1}ENC(mb)
  4. A doit dire quel message a été chiffré: ou , c'est-à-dire qu'il doit sortir le bit .m0m1b

(J'omets le paramètre de sécurité , qui est essentiel pour définir "négligeable" ou "perceptible"; nous devons supposer que la génération des clés dépend de , et que l'avantage est supérieur à est négligeable dans , c'est-à-dire moins que ) κκA1/2κκω(1)

A sonné.
la source
nous pouvons ajouter une chaîne aléatoire à la fin de l'entrée avant d'effectuer le cryptage pour éviter le problème et toujours avoir , c'est-à-dire que la condition peut être plus forte que celle que vous avez indiquée en haut . EC(ENC(k,m,R))=m
Kaveh
3

Vous n'avez pas indiqué de quel type de chiffrement nous parlons, mais permettez-moi de souligner ce qui est vraiment nécessaire pour la sécurité des protocoles cartographiques (en plus ce qui est indiqué dans d'autres réponses).

Ce dont nous avons vraiment besoin, c'est ceci: les clés doivent être générées de manière aléatoire (cela peut être fait en collaboration comme dans la cryptographie à clé publique comme RSA ou par une entité comme dans la cryptographie à clé privée). Le caractère aléatoire de la clé garantit qu'un adversaire ne peut pas prédire les clés (et les utiliser pour briser le protocole). Tant que les clés semblent aléatoires à l'adversaire, le protocole sera sécurisé. Souvent, les clés sont générées par un algorithme randomisé puis remises aux parties, tandis que les algorithmes de chiffrement et de déchiffrement ne sont pas aléatoires mais déterministes.

N'oubliez pas non plus qu'être randomisé ne signifie pas que le processus n'est pas inversible. Un exemple simple est le suivant: étant donné , générer aléatoirement , sortie . Pour inverser, nous pouvons sortir la première partie de la paire.xrx,r

Kaveh
la source
votre exemple est important: sans remplissage aléatoire, vanilla RSA n'est pas sécurisé. avec un rembourrage aléatoire, RSA peut se révéler avoir de belles propriétés de sécurité dans le modèle d'oracle aléatoire
Sasho Nikolov
1

Les algorithmes de chiffrement et de déchiffrement peuvent être randomisés tant que vous pouvez prouver un théorème selon lequel le chiffrement suivi du déchiffrement vous donnera le message original la plupart du temps .

Pourquoi voudrait-on un tel schéma de cryptage? Parce que: 1) il existe des situations où nous ne voulons pas avoir raison tout le temps mais seulement 99999999 fois sur chaque 100000000 et 2) autoriser de si petites erreurs améliore souvent autre chose (comme l'efficacité) par une quantité disproportionnée.

Vinayak Pathak
la source
3
Bien que le cryptage probabiliste existe, il est plutôt du côté exotique. De nombreux algorithmes de chiffrement quotidiens impliquent un caractère aléatoire sans être probabiliste.
Gilles 'SO- arrête d'être méchant'
@Gilles: Une distinction importante à faire.
Raphael
0

Pour citer un exemple, dans le cryptage RSA , vous devez générer deux nombres premiers et et un entier qui seront utilisés pour créer vos clés publiques et privées.pqe

Si vous générez l'une de ces valeurs de manière déterministe, leur génération peut être reproduite, ce qui pourrait compromettre votre cryptage. Si ces nombres sont générés de manière aléatoire, ce n'est pas un problème.

Mise à jour

Comme exemple plus spécifique de la réponse de Ran G. , vous pouvez jeter un œil à la cryptographie à courbe elliptique , où l'algorithme nécessite un paramètre aléatoire (généralement appelé , ou ) pour crypter et décrypter les messages. Si le même paramètre "aléatoire" est utilisé plusieurs fois, leur clé peut être calculée à partir de deux messages chiffrés. C'était le problème / la prémisse du hack PlayStation 3 de l'année dernière .kr

Pedro
la source
1
C'est le hasard dans la génération de clés, dont je doute que la question soit: toute génération de clés doit impliquer le hasard, sinon la clé est prévisible (ou dérivée et non générée).
Gilles 'SO- arrête d'être méchant'
Je ne pense pas que ce soit le lieu de randomisation que le PO ait en tête. Les clés sont données et statiques pour la cryption (en | de). La façon dont vous choisissez votre clé est indépendante de cela.
Raphael
@ Gilles: Je ne le considérerais pas aussi clairement. Les valeurs , et sont généralement stockées sous forme cryptée, avec un mot de passe choisi par l'utilisateur. A proprement parler, ils sont la clé, mais d'un utilisateur de la perspective « , ils ne sont que des valeurs aléatoires générées en tapant charabia sur le clavier et n'a rien à voir avec leur mot de passe soigneusement choisi. pqe
Pedro
@Pedro Je ne comprends pas comment votre dernier commentaire se rapporte à la question. Même du point de vue des fichiers de clés (que je ne vois pas dans la question), la clé n'est évidemment pas générée de manière aléatoire, elle est dérivée du fichier de clé et du mot de passe.
Gilles 'SO- arrête d'être méchant'