Tél 01 53 01 98 30 - Fax 01 42 72 78 18 - Snap charlemagne4eme

Thèmes :

Algorithmique

Cryptographie

Programmation

Probabilités

Option : Interface graphique

Option : réseau

Description :

Ce projet est une introduction aux techniques cryptographiques. Il s'agit de décrire ici un protocole de cryptographie parfaite, c'est-à-dire sans possibilité de décodage sans l'image complémentaire.

Principe :

On donne en entrée une image de taille n x m codée sous la forme d'un tableau A de n chaînes de m caractères ” ” ou ”%%*”. La procédure produit en sortie deux images complémentaires de taille 2n x 2m codées sous la forme de deux tableaux B et C de 2n chaînes de 2m caractères ” ” ou “*” de la façon suivante:

à chaque case de A, correspond un bloc de 2×2 case dans B et C

Pour chaque case [i,j] de A, on tire un bit aléatoire Rij uniforme indépendamment

Si A[i,j] = ” ”, alors on donne aux blocs [ [2i,2j],[2i,2j+1] ],[ [2i+1,2j],[2i+1,2j+1] ] de B et C les mêmes valeurs [ ,#], [#, ] ou [ [#, ], [ ,#]] suivant si Rij = 0 ou 1

Si A[i,j] = “*”, alors on donne aux blocs [2i,2j],[2i,2j+1],[2i+1,2j],[2i+1,2j+1] de B et C les valeurs opposées [ ,#], [#, ] et [ [#, ], [ ,#]], ou l'inverse [ [#, ], [ ,#]] et [ ,#], [#, ], suivant si Rij = 0 ou 1.

Voici un exemple :

A = [ "## ",

      "  #",

      " # ",

      "###"]

      

R =

011

010

100

100

      

B = 

 ## #

#  # #

 ##  #

#  ##

#  # #

 ## #

#  # #

 ## #

 

C = 

#  ##

 ##  #

 ## #

#  # #

# #  #

 # ##

 ## #

#  # #

Par construction, un pixel noir de A est remplacé par deux pixels en diagonale opposés dans B et C; et un pixel blanc de B est remplacé par deux pixels en diagonale identiques dans B et C. Ainsi, si on superpose les deux images B et C on retrouve l'image A, car à tout pixel noir de A correspond un bloc tout noir dans la superposition B+C et à tout pixel blanc de A correspond un bloc à moitié rempli dans la superposition B+C.

Cependant, comme le choix de la diagonale de pixel est fait de façon aléatoire et indépendante dans chaque case de B (idem pour C), la matrice B ou la matrice ne contiennent aucune information sur A si on les prend séparément ! C'est donc un procédé cryptographique parfait

Réalisations demandées :

Écrire un programme qui calcule les images complémentaires B et C à partir du tableau A

Démontrer que si on a B seulement, on n'a strictement aucune information sur A (c'est-à-dire que tous les tableaux A engendrent cette matrice B de façon équiprobable)

Option : utiliser les librairies Tkinter et ImageMagick (par exemple) pour lire, écrire et afficher des images en noir et blanc de l'entrée et des résultats.

Proposer une extension de ce protocole cryptographique à 3 personnes ou plus, où l'image est “éclatée” en 3 ou plus images telles qu'il les faut toutes pour reconstruire l'image originale.