Aller au contenu

Olympiades⚓︎

Première NSI, Académie de Normandie

Signature numérique d'un tableau⚓︎

Il s'agissait de mettre en œuvre une technique de stéganographie pour cacher une image en niveaux de gris (représentant la signature d'un peintre) dans une autre (représentant un tableau du peintre en question).

Le problème est simplifié : on part de deux fichiers images de même dimensions et on crée un troisième fichier qui coincide parfaitement l'image du tableau pour tous les points (pixels) où le fichier signature est noir et dégrade légèrement les pixels où le fichier signature présente un pixel non noir.

La dégradation se fait en remplaçant des bits de points faibles des entiers modélisant la couleur du pixel en rvb par les bits de la représentation binaire du niveau de gris de la signature.

Voici les différentes fonctions que le sujet proposait de coder :

Les conversions binaire \(\leftrightarrow\) décimal
def dec_vers_bin(n):
    """Donne sur 8 bits l'écriture de n donné en décimal"""
    huit_bits = [0] * 8
    i = 7
    while n > 0:
        n, huit_bits[i] = divmod(n, 2)
        i -= 1
    return huit_bits

def bin_vers_dec(bits):
    """À partir de la liste des bits renvoie l'entier n correspondant"""
    puissance_2 = 1
    n = 0
    for i in range(len(bits)-1, -1, -1):
        n += puissance_2 * bits[i]
        puissance_2 = puissance_2 * 2
    return n
Les combinaisons en image

combinaisons

Les fonctions combinaison_1, combinaison_2 et combinaison_3 réalise les 3 transformations (orange, verte et bleu) schématisées ci-dessus.

Les fonctions combinaison
def combinaison_1(n1, n2):
    """renvoie l'entier n3 dont l'écriture binaire sur 8 bits est constituée :
    - des 5 bits de poids forts de l'écriture binaire de n1
    - des 3 bits de poids forts de l'écriture binaire de n2
    """
    bits_de_n1 = dec_vers_bin(n1)
    bits_de_n2 = dec_vers_bin(n2)
    bits_de_n3 = [bits_de_n1[i] if i < 5 else bits_de_n2[i - 5] for i in range(8)]
    return bin_vers_dec(bits_de_n3)

def combinaison_2(n1, n2):
    """renvoie l'entier n3 dont l'écriture binaire sur 8 bits est constituée :
    - des 5 bits de poids forts de l'écriture binaire de n1
    - des 3 bits du "milieu" (3, 4 et 5) de l'écriture binaire de n2
    """
    bits_de_n1 = dec_vers_bin(n1)
    bits_de_n2 = dec_vers_bin(n2)
    bits_de_n3 = [bits_de_n1[i] if i < 5 else bits_de_n2[i - 3] for i in range(8)]
    return bin_vers_dec(bits_de_n3)

def combinaison_3(n1, n2):
    """renvoie l'entier n3 dont l'écriture binaire sur 8 bits est constituée :
    - des 6 premiers bits de poids forts de l'écriture binaire de n1
    - des 2 bits de poids faibles de l'écriture binaire de n2
    """
    bits_de_n1 = dec_vers_bin(n1)
    bits_de_n2 = dec_vers_bin(n2)
    bits_de_n3 = [bits_de_n1[i] if i < 6 else bits_de_n2[i] for i in range(8)]
    return bin_vers_dec(bits_de_n3)

La transformation d'un pixel de couleur \((r, v, b)\) à l'aide d'une nuance de gris \(g\) consiste alors à :

Transformer un pixel
def transforme(r, v, b, g):
    return combinaison_1(r, g), combinaison_2(v, g), combinaison_3(b, g)

Il ne reste plus qu'à réaliser cette transformation sur chacun des pixels concernés :

Signer un tableau
def signer(fichier_sans, fichier_signature):
    racine = fichier_sans[:-4]
    ext = fichier_sans[-3:]
    fichier_avec = f'{racine}_avec_signature.{ext}'

    img_tableau = Image.open(fichier_sans)
    img_signature = Image.open(fichier_signature)
    img_finale = Image.new('RGB', img_tableau.size)

    largeur, hauteur = img_tableau.size
    coordonnees = [(x, y) for y in range(hauteur) for x in range(largeur)]

    for pt in coordonnees:
        gris, _, _ = img_signature.getpixel(pt)
        r, v, b = img_tableau.getpixel(pt)
        if gris == 0:
            img_finale.putpixel(pt, (r, v, b))
        else:
            img_finale.putpixel(pt, transforme(r, v, b, gris))

    img_finale.save(fichier_avec)

Puis la question, un peu plus technique pour évaluer le niveau de compréhension de la méthode précédente : réaliser la fonction qui réalise l'opération inverse. À partir de deux fichier images d'un tableau signé et du même tableau non signé, créer une image de la signature utilisée.

Cette génération repose donc sur une fonction qui à partir d'un triplet rvb produit un entier entre \(0\) et \(255\) :

Récupérer un niveau de gris
def niveau_gris(rvb):
    r, v, b = rvb
    bits_r = dec_vers_bin(r)
    bits_v = dec_vers_bin(v)
    bits_b = dec_vers_bin(b)
    return bin_vers_dec(bits_r[-3:]+bits_v[-3:]+bits_b[-2:])    

Et la génération de signature :

Générer une signature
def signature(fichier_sans, fichier_avec):
    """Révèle la signature présente dans fichier_avec, en comparant
    avec fichier_sans... le fichier signature.png est généré avec cette signature
    """
    img_sans = Image.open(fichier_sans)
    img_avec = Image.open(fichier_avec)
    img_signature = Image.new('RGB', img_sans.size)

    largeur, hauteur = img_sans.size
    coordonnees = [(x, y) for y in range(hauteur) for x in range(largeur)]

    for pt in coordonnees:
        rvb_sans = img_sans.getpixel(pt)
        rvb_avec = img_avec.getpixel(pt)
        if rvb_sans == rvb_avec:
            img_signature.putpixel(pt, (0, 0, 0))
        else:
            gris = niveau_gris(rvb_avec)
            img_signature.putpixel(pt, (gris, gris, gris))

    img_signature.save('signature.png')    

Automates⚓︎

Présentation⚓︎

Le deuxième problème amène les élèves vers de l'informatique plus théorique avec l'exploration des langages rationnels et des automates finis.

Automate de la figure 1

FIG1

En ajoutant un peu de code qui s'appuie sur simple-pygraph on peut créer des automates :

Reconnaissance de \(acaa\)

Nous allons modéliser \(A_1\), l'automate de la figure 1 du sujet, défini par : - \(T_1\) ses transitions - \(S_1 = 0\) sont état de départ - \(E_1 = {2, 3}\), les états finals

>>> T1 = [{'a': 1, 'b': 2}, {'b': 3, 'c': 2}, {'a': 2}, {}]
>>> S1 = 0
>>> E1 = [2, 3]
>>> A1 = Automate(S1, E1, T1)
>>> A1.accept('acaa')
True
lue  : ⭣
mot  : acaa
état : 1

ACAA-1

lue  :  ⭣
mot  : acaa
état : 2

ACAA-2

lue  :   ⭣
mot  : acaa
état : 2

ACAA-2

lue  :    ⭣
mot  : acaa
état : 2

ACAA-2

lue  :   
mot  : acaa
état : 2

Plus de lettre à lire, on est sur un état final, le mot est accepté.

ACAA-2

Les mots a et abca ne sont pas acceptés :

Non reconnus
>>> A1.accept('a')
False

On termine la lecture du mot sur un état non final :

echec_a

>>> A1.accept('abca')
False

On termine est sur un état final, mais il reste des lettres. La prochaine est c hors de l'état \(3\) il n'y a aucune transition.

echec_abca

Les autres exemples du sujet

fig2

fig3

Travail à réaliser⚓︎

Le mot \(babacab\) est-il reconnu par \(A_3\) ?
état courant lettres restant à lire lettre courante état suivant
2 babacab b 2
2 abacab a 1
1 bacab b 2
2 acab a 1
1 cab c 1
1 ab a 1
1 b b 2
2

On termine sur l'état \(2\) qui est final : le mot est reconnu.

Modéliser un automate

Il s'agissait, avec les structures de données connues en 1re, de proposer une modélisation d'un automate. Et de montrer le résultat sur l'automate \(A_1\) du premier exemple.

Réponse

En première on s'appuie sur les dictionnaires, les p-uplets nommés et les tableaux. Un automate est caractérisé par :

  • un nombre d'états
  • un tableau des états finaux
  • un état courant (initialisé à \(0\))
  • une table de transitions (vide au départ) qui est un tableau de dictionnaires : pour chaque état, le dictionnaire indique les transitions à partir de cet état ; les clés sont les caractères reconnus à partir de l'état et les valeurs les états d'arrivée

\(A_1\) pourrait être modélisé par le p-uplet nommé suivant :

>>> A1 = {'nb_etats': 4, 'finaux': [2, 3], 'courant': 0,
            'transitions': [{'a': 1, 'b': 2}, {'b': 3, 'c': 2}, {'a': 2}, {}]}
Implémentation complète

Il faut écrire un programme complet (disons un ensemble de fonctions) permettant :

  1. de créer un automate en ne spécifiant que le nombre d'états et les états finaux, mais avec une table de transitions vide
  2. de rajouter une transition à la table d'un automate, en spécifiant l'état de départ, l'état d'arrivée et le caractère qui provoque cette transition
  3. de reconnaitre un mot par un automate donné
Réponse

On ne fait aucune vérification de cohérence (par exemple si l'utilisateur déclare un automate à 3 états mais spécifie \(5\) comme un état final cela ne sera pas détecté).

def cree_automate(nb_etats, finaux):
    return {'nb_etats': nb_etats, 'finaux': finaux, 'courant': 0,
            'transitions': [{} for _ in range(nb_etats)]}

def ajoute_transition(A, depart, arrivee, caractere):
    """ajoute à l'automate A, la transision entre les etats depart -> arrivee
    etiquete par caractere
    """
    A['transitions'][depart][caractere] = arrivee    

def lit_un_caractere(A, car):
    """cette fonction lit le caractere car à partir de l'état
    courant de l'automate A si c'est possible effectue la transition et renvoie True
    renvoie False si ce n'est pas possible
    """
    depart = A['courant'] 
    if car in A['transitions'][depart]:
        A['courant'] = A['transitions'][depart][car]
        return True
    return False    

def reconnait(A, mot):
    """tente de reconnaitre le mot à partir de l'automate A
    par lecture successive des caractères de A, renvoie True si
    le mot est reconnu et False sinon
    """
    A['courant'] = 0  # on réinitialise le départ
    for car in mot:
        if not lit_un_caractere(A, car):
            return False
    return A['courant'] in A['finaux']

Et on peut tester sur le dernier automate \(A_4\) de la figure 4 du sujet :

\(A_4\)
  • Création de l'automate
>>> A4 = cree_automate(2, [1])
>>> ajoute_transition(A4, 0, 1, 'a')
>>> ajoute_transition(A4, 0, 0, 'b')
>>> ajoute_transition(A4, 1, 0, 'b')
>>> ajoute_transition(A4, 1, 1, 'a')
  • Réconnaissance (ou pas) de quelques mots
>>> reconnait(A4, 'a')
True
>>> reconnait(A4, 'ba')
True
>>> reconnait(A4, 'bbabaabaa')
True
>>> reconnait(A4, 'b')
False
>>> reconnait(A4, 'baaabab')
False