Sécurité multimédia : proposition de techniques de dissimulation d’informations numériques basées sur les codes polaires

Le décodage des codes en bloc linéaires 

 Détection des erreurs 

Soit 7(&, .) un code en bloc linéaire et Hd la transposée de sa matrice de contrôle de parité. Soit U un mot quelconque, la quantité s(U) = UHd est appelée syndrome de U. Soit r = c + e le mot reçu lorsque le mot de code c ∈ 7 est transmis ; e étant la configuration d’erreurs survenues lors de la transmission. Nous avons, d’après (1.1), s c = cHd = 0 ⟺ c ∈ 7. Quand on calcule le syndrome du mot reçu r, on obtient : s r = rHd = cHd + eHd = eHd = s(e). (1.23) D’après cette expression, le mot reçu et l’erreur ont le même syndrome. Nous pouvons donc dire que le syndrome ne dépend pas du mot reçu (« patient ») mais dépend de l’erreur (« maladie »). Deux cas de figure peuvent se présenter :  » le syndrome est nul ; on conclut qu’il n’y a pas d’erreurs ou du moins pas d’erreurs détectables. Notons qu’un syndrome nul ne permet pas d’affirmer qu’il n’y a aucune erreur. En effet, une combinaison particulière d’erreurs peut aboutir à un syndrome nul.  » le syndrome est non nul ; il existe au moins une erreur. Les symboles non nuls de e représentent les positions des erreurs. Dans le cas où e n’admet qu’un seul symbole non nul, soit ïW ≠ 0, le syndrome est égal à la colonne  de la matrice de contrôle de parité. Sinon s s’écrit comme combinaison de plusieurs colonnes de H. On appelle coset ou classe latérale d’un syndrome s l’ensemble définit par : ≥ s = U ∈ 0, 1 T UHd = s} (1.24) Le leader du coset est le vecteur de poids minimal appartenant à ce coset.

 Correction des erreurs de transmission 

o Décodage à maximum de vraisemblance a posteriori Le décodage Maximum Likelihood (ML) sélectionne le mot de code c le plus probable (ayant la plus petite distance de Hamming avec le mot reçu r) parmi tous les mots de code possibles de manière à maximiser la probabilité Pr(r|c). Si on considère que la probabilité d’erreur 1µ < _ m , on aura [33] : a = U ⟺ dI r, U ≤ dI r, b , ∀ b ∈ 7 &, . . (1.25) Cette procédure de décodage devient difficile à mettre en œuvre si le nombre de mots de code est important ; ce qui est souvent le cas pour les codes en blocs les plus utilisés. o Décodage à partir du syndrome Comme son nom l’indique, ce type de décodage utilise le calcul de syndrome pour corriger les erreurs. Nous savons, d’après la relation (1.23), que le mot reçu r = c + e et la séquence d’erreurs e ont même syndrome. Le problème de décodage peut donc se résumer à trouver le vecteur e de poids minimal dans la classe latérale de r. Pour ce faire, on peut utiliser, soit une table de correspondance entre les syndromes et les configurations d’erreurs associées, soit calculer le vecteur d’erreurs. La table est composée de deux colonnes et sur chaque ligne se trouve un syndrome et le vecteur d’erreurs correspondant. Le calcul de la séquence d’erreurs peut se faire par évaluation de la position des erreurs et de la valeur de leurs amplitudes. Autrement dit, on cherche les positions y pour lesquelles la composante ïS de la séquence d’erreurs e est non nul et, dans ce cas, on détermine la valeur de ïS. Ce type de décodage est utilisé avec les codes RS et les codes BCH binaires en utilisant une approche polynômiale. Après avoir trouvé e, il suffit de poser c = e + r pour avoir le mot de code qui a été émis. Le décodage est réussi si HI(e) ≤ ô. o Décodage par propagation de croyances L’algorithme de décodage par propagation de croyances BP (Belief Propagation) est un algorithme itératif basé sur un échange d’informations probabilistes entre les différents nœuds (de variable et de contrôle) d’un graphe représentant le code considéré. L’information échangée entre les nœuds est sauvegardée et réutilisée lors des itérations suivantes. 

Codes convolutifs 

Les codes convolutifs peuvent être systématiques ou non [32]. Ils s’appliquent sur une suite infinie de données et génèrent des séquences de mots codés infinies. Pour ces codes, chaque bloc de & éléments binaires en sortie dépend non seulement des . éléments binaires présents en entrée mais aussi des Ä blocs de . éléments binaires précédents, souvent . vaut 1. Ä + 1 s’appelle la longueur de contrainte. Ainsi, le taux de codage ç est égal à ./&. 

Encodage des codes convolutifs

L’opération d’encodage utilisent des polynômes générateurs et est réalisé à l’aide de registres à décalage et de OU exclusifs (XOR). Considérons par exemple un codeur constitué de trois étages et deux sorties â_ = K` ⊕ K`c_ ⊕ K`cm et âm = K` ⊕ K`cm, où K` est le bit d’entrée et ⊕ le XOR. Figure 1.1 : Codeur convolutif, à gauche symbolique et à droite implémentation. Le bit d’entrée K` peut prendre 0 ou 1 pour le même état des registres K`c_ et K`cm, les différents états possibles (K`, K`c_, K`cm) sont donc (000, 100, 001, 101, 010, 110, 011, 111) et les sorties respectives (â_, âm) sont (00, 11, 11, 00, 10, 01, 01, 10). Ainsi le treillis est formé de nœuds reliés par des branches : les nœuds et les branches représentent respectivement les différents états possibles du codeur et les différentes transitions possibles d’un nœud à un autre lors de l’arrivée d’un bit d’entrée. Le treillis du code sera représenté comme suit : Figure 1.2 : Représentation en treillis d’un code convolutif. Partant, par exemple de l’état 00, l’arrivée d’un 0 mène le codeur à l’état 00 et l’arrivée d’un 1 mène le codeur à l’état 10. A chaque branche, nous pouvons associer le mot codé (sortie), soit les 2 bits de code ici.

Décodage des codes convolutifs : décodage de Viterbi

 Le décodage le plus courant des codes convolutifs est basé sur l’algorithme de Viterbi [37] qui décode un flot de données encodées à l’aide d’un encodeur convolutif. L’algorithme de Viterbi peut se faire avec des entrées fermes (on reçoit uniquement les bits codés) ou souples (on les reçoit avec des bits de fiabilité). L’algorithme de Viterbi utilise une représentation en treillis. Il consiste à rechercher dans l’arbre le chemin qui correspond à la séquence la plus probable, c’est-à-dire celle qui est à la distance minimale de la séquence reçue. Avec le codeur de la Figure 1.2, supposons que l’on envoie la séquence binaire 00 1J 10 11 00 et qu’on reçoive 00 1M 10 11 00. La représentation en treillis de l’ensemble des chemins possibles est la suivante : pour K` = 0 et pour K` = 1 Figure 1.3 : Représentation en treillis du décodeur convolutif. Partant de l’état initial 00, on ne peut atteindre que deux états : 00 ou 10 (voir Figure 1.2). L’état 00 est atteint si le bit entrant est 0. Dans ce cas, la séquence de sortie est 00. Une sortie à 00 est en accord avec la séquence reçue 00 : il n’y a donc pas d’erreur (0). En revanche, l’état 10 est atteint si le bit entrant est 1. La séquence de sortie est 11, ce qui diffère de 2 bits par rapport à la séquence reçue. Donc les deux états au temps ô_ sont atteints en faisant 0 ou 2 erreurs (Figure 1.4). Le même raisonnement est fait au temps ôm à partir des deux nœuds résultants de ô_. Les métriques (en vert) correspondent au cumul des erreurs depuis la racine (état 00). Notons que lorsque deux chemins différents aboutissent à un même nœud, celui qui a une métrique plus élevée est abandonné (supprimé). Cela continue jusqu’au temps ô∫. Comme nous pouvons le constater sur la Figure 1.4, la métrique minimale est 1. Figure 1.4 : Décodage de Viterbi sous forme de treillis. Finalement, le chemin le plus vraisemblable est celui ayant le moins d’erreur, c’est-à-dire celui produisant la sortie la plus proche de la séquence reçue. Ici, c’est le chemin représenté en trait gras qui sera la séquence décodée (Figure 1.4). Ainsi, l’algorithme de Viterbi fournit en sortie 00 11 10 11 00 qui correspond à la séquence décodée 0 1 0 0 0. Les codes convolutifs sont utilisés dans les systèmes de communications sans fil, la télévision numérique par satellite DVB-S et la téléphonie mobile. Conclusion Nous venons de passer en revue des notions très importantes en théorie des codes correcteurs d’erreurs et quelques exemples de ces codes en donnant leurs différentes caractéristiques. Les codes de Hamming, les codes BCH, les codes de Reed-Solomon et les codes convolutifs sont des codes correcteurs d’erreurs qui s’appliquent dans plusieurs domaines de la technologie. Ils sont aussi utilisés en stéganographie. Les techniques de dissimulation d’informations telles que la stéganographie sont anciennes et attirent de plus en plus l’intérêt de bon nombre de scientifiques. Le but de ce chapitre est d’introduire la stéganographie, la stéganalyse, ainsi que les différentes techniques et méthodes utilisées. Nous commençons par définir la stéganographie et les caractéristiques des schémas de stéganographie. Les différentes techniques de stéganographie, à savoir les méthodes de remplacement et de correspondance de LSB, le matrix embedding et la technique du papier mouillé, sont ensuite décrites. Nous allons également expliquer la minimisation de l’impact d’insertion, les différents scénarios de stéganalyse et les méthodes permettant de définir les fonctions de distorsion pour la stéganographie adaptative. Nous terminons ce chapitre en présentant les principaux schémas de stéganographie utilisant les codes correcteurs d’erreurs tels que Hamming.

Généralités sur la stéganographie 

Nous allons noter par x = q_, … , qT ∈ º = {Ω}T l’image de couverture et qS son yèRµ pixel. Le message secret m = Ä_, … , ÄR ∈ ℳ = {0, 1}R est inséré en modifiant légèrement l’image de couverture. Cela donne une image stégo y = r_, … , rT ∈ ¡ = Ω_× …×ΩT, où ΩS ⊂ Ω tel que qS ∈ ΩS. Pour les images en niveaux de gris sur 8-bits, utilisées dans cette thèse, Ω = {0, … , 255}. Pour des soucis de simplification, nous allons indifféremment désigner par les mêmes notations les images et les portions qui en découlent. Par exemple, l’image de couverture sera appelé x et un segment de l’image de couverture sera aussi désigné par x. 

Définitions de la stéganographie

 La sécurisation de l’information réunit plusieurs techniques comme la cryptographie qui assure la sécurité de la communication. Cependant, souvent même l’existence de la communication nécessite d’être secrète. Le message d’une telle communication secrète peut être incorporé dans d’autres communications insoupçonnées en utilisant la stéganographie. Cette technique permet de dissimuler une information secrète dans des médiums de couverture numériques tels que l’image, le son ou la vidéo de sorte qu’elle soit indétectable. Ainsi, contrairement à la cryptographie qui a pour seul objet la robustesse, la stéganographie vise d’abord la confidentialité de l’existence de la communication (message) avant la robustesse. La tâche de l’expéditeur (ou stéganographe) [38] est de dissimuler son message secret (ou payload) dans le médium de couverture de telle sorte que seul le destinataire soit au courant de l’existence du message. Dans la stéganographie moderne ou numérique, il existe deux manières de définir de bons algorithmes stéganographiques pour les images numériques. La première méthode repose sur la définition d’un bon modèle de couverture. La seconde et plus moderne approche est basée sur la dissimulation du message secret tout en minimisant une certaine fonction de distorsion. Cette dernière approche est plus flexible et est à la base de la majorité des méthodes de stéganographie actuelles. La stéganographie moderne a véritablement débuté vers 1996. Son développement est favorisé par celui de l’internet qui permet un partage intense de données multimédias à longueur de journée. La stéganographie moderne utilise donc ces médiums pour la dissimulation d’informations secrètes. Les utilisations peuvent être à des fins de protection et de sécurisation d’informations personnelles secrètes ou à des fins malveillantes. Selon certains médias, les attentats du 11 septembre 2001, perpétrés aux EtatsUnis, auraient été planifiés en utilisant des messages secrets cachés au sein d’images numériques échangées à travers internet. Dans le cadre de cette thèse, nous utiliserons les images numériques et l’insertion se fera dans le domaine spatial. 

Les différents types et formats d’images

 Les algorithmes de stéganographie dépendent de la structure des données dans lesquelles se fait l’insertion. Les modifications devant être imperceptibles, il faut donc altérer le support dans les endroits les plus discrets, ce qui dépend fortement du type de données (image, audio, vidéo, …) et de leur format de représentation (JPEG, GIF, MP3, …). 

 La notion de pixel

 Une image est constituée d’un ensemble de points appelés pixels (picture element). Le pixel représente le plus petit élément constitutif d’une image numérique. L’ensemble des pixels est contenu dans un tableau à deux dimensions constituant l’image. 

Les différents types d’images 

La propriété de base d’une image est son mode. Il en existe de quatre types : $ les images binaires (noir et blanc) Une image binaire est représentée par une matrice dont les éléments (pixels) sont des valeurs binaires (0 pour le noir et 1 pour le blanc). les images en teintes ou en densités ou en niveaux de gris Dans une image en niveaux de gris de taille (√, ƒ), chaque pixel est représenté par son intensité lumineuse, de 0 (noir) à 255 (blanc) pour les types entiers sur un octet. Entre les deux valeurs nous avons les nuances de gris. $ les images RGB (Red Green Blue) ou RVB (Rouge Vert Bleu) La nomination RGB indique que chaque pixel de l’image est représenté par un niveau de rouge, un niveau de vert et un niveau de bleu. Un pixel utilise donc 3 octets (24 bits) pour coder un triplé d’entiers. Une image RGB est donc de taille (√, ƒ, 3). $ les images indexées ou images palettisées La couleur de chaque pixel est codée sur un seul octet dans une table de couleurs. Cette table de couleurs de taille (ƒ, 3), la palette de couleurs (color map), définit jusqu’à 256 couleurs utilisables dans l’image en donnant la décomposition RGB de chaque couleur sur 3 octets. 

 Les différents formats d’images 

Les formats d’image sont nombreux et variés. Nous avons, par exemple, PNG (Portable Network Graphics), GIF (Graphics Interchange Format), JPEG (Joint Photographic Experts Group), etc. Le domaine spatial concerne les images fixes non compressées pouvant être représentées par différents formats BMP, RAW, TIFF, PGM … etc. Dans le domaine JPEG, les images sont compressées et représentées en blocs de 8 × 8 pixels avec des coefficients DCT (Discret Cosinus Transform) quantifiés. Notons que pour nos tests dans ce manuscrit, nous utiliserons des images numériques contenues dans la base BOSS [39] d’images en niveaux de gris de même taille 512×512 et de même format PGM.

Le problème ou modèle des prisonniers 

Bien que la communauté des stéganographes se soit constituée dans les années 90, G. J. Simmons pose en 1983 le socle de la stéganographie moderne en définissant la notion de canal subliminal [2]. Pour illustrer son propos, il reprend le problème des prisonniers. Dans ce contexte, Alice et Bob sont deux prisonniers enfermés dans deux cellules séparées l’une de l’autre. Ils sont autorisés à communiquer par l’intermédiaire d’une gardienne Eve, comme indiqué sur la Figure 2.1. Si celle-ci soupçonne qu’ils élaborent un plan pour s’échapper, elle s’autorise à mettre fin à la communication entre les deux détenus et de lourdes sanctions leur seront infligées. De plus, Eve a la possibilité de modifier les messages. Dans une telle situation l’utilisation de messages chiffrés éveillerait des soupçons. Ainsi, la seule alternative d’Alice et Bob est de s’envoyer des messages innocents et de dissimuler l’information secrète dans ceuxci. Pour ce faire, ils mettent en place un canal de transmission (par l’intermédiaire des messages) qui n’est pas visible pour Eve ; ce canal est appelé canal subliminal. Nous supposons tout d’abord qu’Alice et Bob se sont échangés au préalable une clé secrète stéganographique que la gardienne ignore. Leur plan est réussi s’ils arrivent à communiquer sans éveiller le moindre soupçon de la part d’Eve.