On distingue deux approches fondamentales dans l'étude
de la sécurité d'un cryptosystème : la
sécurité parfaite de Shannon et la sécurité
calculatoire.
II.3.1. Notions
élémentaires de probabilité
Définition classique de
probabilité
Considérons une expérience aléatoire possédant la symétrie mutuelle et un événement quelconque relatif à La probabilité de l'événement est le nombre , où est le nombre de cas favorables à et le nombre total des éventualités rattaché à
l'épreuve.
Définition axiomatique de
probabilité
Une mesure de définie sur un espace probabilisable , l'application qui vérifie les 3 axiomes suivants :
1.
2. Si pour
alors ;
3.
Le triplet est appelé espace probabilisé.
Probabilité conditionnelle
Soient et deux événement telque
On appelle probabilité conditionnelle de
l'événement par rapport à l'événement , ou encore la probabilité de A étant donné
B :
La probabilité conditionnelle nous permet de calculer
la probabilité de l'intersection :
Indépendance stochastique des
événements
Deux événements et sont indépendant si
si et et que les événement et sont indépendants alors
Les événements sont indépendants si
Théorème de Bayes
Si est un système complet d'événements et est un événement quelconque.
Supposons que puisse se produire qu'en combinaison avec l'un des
événements de , c'est-à-dire .
, alors on a la formule de Bayes
Preuve. Voir [12]
II.3.2. La
sécurité calculatoire
La sécurité calculatoire est basée sur la
mesure de la quantité de calcul nécessaire pour casser un
système. On dit qu'un procédé est sûr au sens de la
théorie de la complexité si le meilleur algorithme pour le casser
nécessite opérations où est un nombre beaucoup trop grand pour que cet algorithme soit
applicable en pratique. Dans la pratique, on dit souvent qu'un système
est sûr si la meilleure attaque connue ne peut se faire avec une
quantité raisonnable de temps de calcul. Le problème de cette
approche c'est qu'un cryptosystème peut être sûr pendant un
moment puis ne plus l'être lorsque l'on découvre un algorithme
plus efficace.
II.3.3 La
sécurité parfaite de Shannon
Claude Shannon en 1949 dans son article
intitulé « Communication Theory of Secrecy
System » introduit la notion des systèmes cryptographiquement
sûrs, qui eut une influence considérable sur l'étude de la
cryptographie.
Considérons l'ensemble fini de textes clairs, l'ensemble fini de textes chiffrés, l'ensemble fini de clés.
Supposons qu'une clé est utilisée une et une seule fois.
Notons que l'ensemble des textes clairs est muni d'une probabilité ainsi que l'ensemble des clés muni d'une probabilité
Supposons que les clés sont choisies
indépendamment des textes clairs.
Ainsi les deux probabilités et induisent une probabilité sur l'ensemble des textes
chiffrés Nous pouvons calculer la probabilité que le texte chiffré soit transmis.
Pour une clé , notons que représente l'ensemble des textes chiffrés avec la
clé nous définissons
, qui est l'ensemble de toutes les clés possibles qui permettent
d'obtenir le chiffré
Nous avons alors la probabilité de donnée par :
L'événement « le texte chiffré
est » n'est possible que si ou .
La probabilité d'avoir le « texte
chiffré » est la somme de toutes les probabilités mutuelles
les événements « le texte clair est » et « la clé est » sont supposés indépendants, alors cette
probabilité est égale à .
et ,nous pouvons calculer la probabilité conditionnelle (la probabilité que soit le texte chiffré en sachant que est la texte clair) par où .
possédant la symétrie mutuelle et 
un événement quelconque relatif à 
La probabilité de l'événement 
est le nombre 
, où 
est le nombre de cas favorables à 
et 
le nombre total des éventualités rattaché à
l'épreuve.
définie sur un espace probabilisable 
, l'application 
qui vérifie les 3 axiomes suivants :
1. 
pour 
;
3. 
est appelé espace probabilisé.
et 
deux événement telque 
par rapport à l'événement 
, ou encore la probabilité de A étant donné
B :
et 
sont indépendant si 
et 
et que les événement 
et 
sont indépendants alors 
sont indépendants si 
est un système complet d'événements et 
est un événement quelconque.
puisse se produire qu'en combinaison avec l'un des
événements de 
, c'est-à-dire 
.
, alors on a la formule de Bayes
opérations où 
est un nombre beaucoup trop grand pour que cet algorithme soit
applicable en pratique. Dans la pratique, on dit souvent qu'un système
est sûr si la meilleure attaque connue ne peut se faire avec une
quantité raisonnable de temps de calcul. Le problème de cette
approche c'est qu'un cryptosystème peut être sûr pendant un
moment puis ne plus l'être lorsque l'on découvre un algorithme
plus efficace.
de textes clairs, l'ensemble fini 
de textes chiffrés, l'ensemble fini 
de clés.
est utilisée une et une seule fois.
est muni d'une probabilité 
ainsi que l'ensemble des clés 
muni d'une probabilité 
et 
induisent une probabilité sur l'ensemble des textes
chiffrés 
Nous pouvons calculer la probabilité 
que le texte chiffré 
soit transmis.
, notons que 
représente l'ensemble des textes chiffrés avec la
clé 
nous définissons
, qui est l'ensemble de toutes les clés possibles qui permettent
d'obtenir le chiffré 
donnée par :
» n'est possible que si 
ou 
. 
» est la somme de toutes les probabilités mutuelles
les événements « le texte clair est 
» et « la clé est 
» sont supposés indépendants, alors cette
probabilité est égale à 
.
et 
,nous pouvons calculer la probabilité conditionnelle 
(la probabilité que
soit le texte chiffré en sachant que 
est la texte clair) par 
où 
.