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 R_ij 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 R_ij = 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 R_ij = 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.