Category ArchivePython

Chiffrement de Hill en Python

Nous allons encore une fois parler cryptographie dans cet article. Dans l’article précédent, je vous parlais du chiffrement affine, le chiffrement le plus nul après le chiffrement de César, mais cette fois-ci, on va lever le niveau…

Les prérequis

Pour chiffrer un message avec cette méthode, il nous faudra connaître les matrices ainsi que les opérations de base qui s’y rapportent, mais aussi la notion de modulo…

Nous allons nous basé sur un alphabet (un ensemble constitué d’un certain nombre de caractères). Pour ma part, j’ai pris :

alphabet=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z",'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',"'","ù","é","è","à","ç","-","ê"," ","."]

De plus, comme il y a pas mal de calculs d’algèbre linéaires, j’utilise le module numpy.

Condition nécessaire et suffisante

La clé de chiffrement est une matrice. Pour pouvoir chiffrer, et surtout déchiffrer, il faut que le déterminant de cette matrice ait un inverse modulo le nombre de caractères de notre alphabet. Il faut donc, après saisie de la matrice, tester cette condition. Rappelons que le déterminant (que je vais noter d) est inversible modulo n s’il existe un entier x compris entre 0 et n-1 tel que dx = 1 mod n.

De plus, le message à chiffrer doit comporter un nombre de caractères multiple de la dimension de la matrice (qui doit être carrée). Donc ici, deux possibilités :

  • soit on demande à l’utilisateur un message ayant un nombre convenable de caractères, ce qui n’est pas très pratique,
  • soit on complète le message par des espaces vides afin que le nombre de caractères soit au final un multiple de la dimension de la matrice.

C’est la seconde solution que j’utilise.

Principe du chiffrement

Pour faire simple, je vais prendre une matrice \(2\times2\), par exemple : $$A=\begin{pmatrix}3&7\\2&13\end{pmatrix}$$et un mot de deux lettres, par exemple “MA”.

Première étape

J’attribue à chaque lettre de mon mot un nombre (le rang de la lettre dans l’alphabet). Donc ici, “M” correspond à 12 et “A”, à “0”. Je créé ainsi un vecteur:$$V=\begin{pmatrix}12\\0\end{pmatrix}.$$

Deuxième étape

Je multiplie la matrice-clé par le vecteur ainsi obtenu:$$\begin{pmatrix}3&7\\2&13\end{pmatrix}\begin{pmatrix}12\\0\end{pmatrix}=\begin{pmatrix}36\\24\end{pmatrix}.$$

Troisième étape

Je prend les coefficients du résultat modulo le nombre de caractères dans l’alphabet. Comme ici c’est 62, ça ne change rien aux nombres obtenus.

Quatrième étape

Je convertis les nombres en caractères en prenant les lettres qui correspondent aux rangs obtenus. Ici, 36 correspond au caractère “k”, et 24 à la lettre “Y”.

Le message chiffré est alors : “kY”.

Principe du déchiffrement

Il est le même que celui du chiffrement, en prenant comme matrice l’inverse modulo n de la matrice de chiffrement.

Première étape

On calcule le déterminant de la matrice de chiffrement A. Pour mon exemple, on trouve :$$\det A=25.$$

Ensuite, on exprime la matrice inverse sous la forme :$$A^{-1}=\frac{1}{\det A}B$$où \(B\) doit être trouvée. Pour nous,$$A^{-1}=\frac{1}{25}\begin{pmatrix}13&-7\\-2&3\end{pmatrix}.$$

Deuxième étape

On cherche l’inverse du déterminant modulo le nombre de caractères dans l’alphabet. On cherche donc ici l’inverse de 25 modulo 62. On trouve 5 car \(25\times5=125=1\mod 62\).

Donc on peut écrire:$$A^{-1}=5\begin{pmatrix}13&-7\\-2&3\end{pmatrix}.$$

Troisième étape

On calcule modulo le nombre de caractères dans l’alphabet les coefficients de la matrice inverse. Ici, on obtiens :$$A^{-1}=\begin{pmatrix}65&-35\\-10&15\end{pmatrix}\equiv\begin{pmatrix}3&27\\52&15\end{pmatrix}\mod62.$$

Quatrième étape

On chiffre le message chiffré à l’aide de la matrice inverse. Donc ici, si on part du message “kY”, qui correspond au vecteur \(\binom{36}{24}\), on a :$$\begin{pmatrix}3&27\\52&15\end{pmatrix}\begin{pmatrix}36\\24\end{pmatrix}=\begin{pmatrix}756\\2232\end{pmatrix}\equiv\begin{pmatrix}12\\0\end{pmatrix}\mod62.$$On retrouve bien le rang des lettres “M” et “A”.

Résultat en Python

J’ai ici converti en fichier exécutable le programme Python, et voici les captures d’écran:

Téléchargement des fichiers

Pour les abonné.e.s de mathweb.fr, j’ai mis tous les fichiers dans un ZIP sur cette page. Pour exécuter directement le programme, double-cliquez sur le fichier Hill.py.

Créer un exécutable sous Windows à partir d’un programme Python

Si vous êtes comme moi, vous êtes sûrement frustrés d’avoir créé un beau programme Python et de ne pas l’avoir en exécutable sous Windows.

Dans cet article, je vais vous montrer comment transformer votre fichier .py en fichier .exe.

Installation du module cx_Freeze

Allez en ligne de commande. Pour cela, allez dans la recherche Windows et tapez “cmd”.

Ensuite, tapez la commande suivante :

python -m pip install cx_Freeze --upgrade

Si tout se passe bien, un message positif apparaîtra. Sinon… ben dommage ! 🙂

Création d’un programme Python

Je vais partir d’un programme que j’avais déjà exposé, celui d’un chiffrement/déchiffrement affine, en l’améliorant un peu :

 alphabet=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z",'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',"'","ù","é","è","à","ç","-","ê"," "]

# Calcul du pgcd de a et b

def pgcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

# fonction de chiffrement affine

def chiffrementAffine(a,b,L):
        x=alphabet.index(L)
        y=(a*x+b)%len(alphabet)
        return alphabet[y]

# Calcul de l'inverse d'un nombre modulo 26

def inverse(a):
        x=0
        while (a*x%len(alphabet)!=1):
                x=x+1
        return x

# Fonction de déchiffrement

def dechiffrementAffine(a,b,L):
    x=alphabet.index(L)
    y=(inverse(a)*(x-b))%len(alphabet)
    return alphabet[y]
                

# Affichage du mot chiffré

def crypt(M,a,b):
    if (pgcd(a,len(alphabet))==1):
        mot = [chiffrementAffine(a,b,i) for i in M]
        return "".join(mot)
    else:
        return "Chiffrement impossible. Veuillez choisir un nombre a premier avec"+str(len(alphabet))+"."

# Affichage du mot déchiffré

def decrypt(M,a,b):
    if (pgcd(a,len(alphabet))==1):
        mot = [dechiffrementAffine(a,b,i) for i in M]
        return "".join(mot)
    else:
        return "Déchiffrement impossible. Le nombre a n'est pas premier avec"+str(len(alphabet))+"."

# Menu

def menu():
    print('Menu du jour...\n----------------')
    print('1. Chiffrer un message')
    print('2. Déchiffrer un message\n-----------------------\n')
    choix = int(input('Quel est votre choix ? '))
    if choix == 1:
        chiffrer()
    elif choix == 2:
        dechiffrer()
    else:
        print('Can you be serious please... ?\n')
        menu()

# Retour au menu ?

def return_menu():
    rep = input('\nSouhaitez-vous revenir au menu (O/N) ? ')
    if rep.upper() == 'N':
        the_end()
    elif rep.upper() == 'O':
        menu()
    else:
        print('Can you be serious please... ?\n')
        return_menu()
# the_end()

def the_end():
    print("Ok. C'est vous qui voyez... See you soon !")
    
# chiffrer

def chiffrer():
    msg = input('Entrez le message à chiffrer : ')
    a = int(input('Entrez la première clé : '))
    b = int(input('Entrez la seconde clé : '))
    print('Le chiffrement donne : ',crypt(msg,a,b))
    return_menu()

def dechiffrer():
    msg = input('Entrez le message à déchiffrer : ')
    a = int(input('Entrez la première clé : '))
    b = int(input('Entrez la seconde clé : '))
    print('Le chiffrement donne : ',decrypt(msg,a,b))
    return_menu()

menu()

Ce programme, je vais le sauvegarder sous le nom chiffrement.py.

Création d’un programme de transformation

Je vais créer maintenant un autre programme Python:

from cx_Freeze import setup, Executable

setup(
    name = "ChiffrementAffine",
    version = "0.1",
    description = "Chiffre et déchiffre un message",
    executables = [Executable("chiffrement.py")]
)

Je vais sauvegarder ce programme sous le nom setup.py dans le même répertoire que chiffrement.py.

Construction de l’exécutable

En ligne de commande, je vais dans le répertoire où se trouvent mes deux fichiers Python, puis je tape :

python setup.py build

Cela peut prendre quelques secondes si c’est la première fois que vous entrez cette ligne de commande. À la fin, on doit obtenir un écran comme celui-ci:

Capture d’écran : terminal Windows

Dans le répertoire où se trouvent les fichiers Python, un répertoire nommé build s’est créé, dans lequel se trouve un répertoire dont le nom ressemble à exe.win32-3.6 , dans lequel se trouve le fichier exécutable, ainsi que plein de fichiers dll.

Et voilà ! Votre fichier exécutable est prêt !

Pour les abonné.e.s de ce site, je mets le ZIP correspondant sur cette page.

Voir le numéros des pages où sont vos images

Introduction

Il y a quelques temps, dans le cadre de mon activité professionnelle du côté de l’édition, j’ai dû me pencher sur une question plutôt épineuse (pour moi), à savoir de construire une liste dans laquelle il y a les images d’un document créé avec \(\LaTeX\), ainsi que le numéro de la page de chaque image.

Par exemple, si mon document affiche l’image toto.eps à la page 7, je voudrais que cela figure dans ma liste.

Nous allons voir une façon (qui n’est peut-être pas la meilleure, mais toute suggestion est bonne) de procéder avec Python.

Code source \(\LaTeX\)

\documentclass[12pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{lipsum}
\usepackage{graphicx}
	\graphicspath{{img/}}
\begin{document}
\lipsum
\begin{center}
\includegraphics{avatar.eps}
\end{center}
\lipsum
\begin{center}
\includegraphics{nsi.eps}
\end{center}
\lipsum
\begin{center}
\includegraphics{sept.eps}
\end{center}
\lipsum
\begin{center}
\includegraphics[width=0.75\linewidth]{tangente.eps}
\end{center}
\end{document}

Je compile ce code via la chaîne Latex+dvips+ps2pdf et l’obtiens alors un document PS ainsi qu’un DVI.

On passe en ligne de commande

Maintenant, on va dans le répertoire qui contient les fichiers, puis on entre le code suivant (sous Windows) :

dvips -o Essai.ps Essai > logdvi

Sous Linux, le code est le suivant :

dvips -o Essai.ps Essai &> logdvi

Ce code aura pour effet de créer un fichier logdvi dans lequel il y aura :

This is dvips(k) 5.998 Copyright 2018 Radical Eye Software (www.radicaleye.com)
' TeX output 2019.01.19:1350' -> Essai.ps
<C:/Users/mathweb/AppData/Local/Programs/MiKTeX/dvips/base/tex.pro>
<C:/Users/mathweb/AppData/Local/Programs/MiKTeX/dvips/base/texps.pro>
<C:/Users/mathweb/AppData/Local/Programs/MiKTeX/dvips/base/special.pro>.
<C:/Users/mathweb/AppData/Local/Programs/MiKTeX/fonts/type1/public/amsfonts/cm/cmr12.pfb>
[1] [2<./img/avatar.eps>] [3] [4<./img/nsi.eps>] [5] [6<./img/sept.eps>] [7]
[8<./img/tangente.eps>]

Remarquez alors qu’à la fin de ce fichier, la liste des images est présente… avec le numéro des pages juste avant les images ! Le problème est le format…

Du côté de Python

Etape 1 : on lit le fichier dvilog

fichier = open("logdvi", "r")
all_lines = fichier.readlines()
fic = ""
for i in range(len(all_lines)):
    line = all_lines[i].replace('\n','')
    fic += line
fichier.close()

Ce code ouvre d’abord le fichier logdvi puis convertit toutes ses lignes en entrées de liste. La liste ainsi construite est nommée all_lines.

Ensuite, je souhaite créer une chaîne de caractères contenant toutes les lignes à la suite; je vais donc enlever les “\n” (les retours à la ligne) à chacune des lignes (dans la boucle for) et je concatène les lignes avec l’instruction “fic += line”. À la fin de ma boucle, la chaîne de caractères fic contient toute les lignes du fichier logdvi à la suite.

Etape 2 : on créé la liste

crochetOuvrant = False
imgList = []

for c in fic:
    if c == "[":
        crochetOuvrant = True
        container = ""
    else:
        if c == "]":
            crochetOuvrant = False
            imgList.append(container)
            
        else:
            if crochetOuvrant == True:
                container += c

Ici, on parcourt la chaîne de caractères fic (avec la boucle for c in fic) caractère par caractère. Si on rencontre un crochet ouvrant, alors on commence le stockage dans la liste : pour chaque crochet ouvrant, on créé une entrée.

Cette entrée est de la forme “[xx]” ou “[xx<./img/xxx.eps>]”.

Etape 3 : on créé un dictionnaire des images

imgDicoList = []
page = ''

for i in imgList:
    if '<' in i: # si au moins une illus. est présente
        imgDico = {}
        for x in i.split('<'):
            if len(x)<4:
                pageCount = True
                if len(x) == 1:
                    page = '00'+x
                elif len(x) == 2:
                    page = '0'+x
                else:
                    page = x
            else:
                pageCount = False
                name = x[6:]
                name = name[:-5]
            if pageCount == False:
                imgDico['page'] = page
                imgDico['name'] = name
                imgDicoList.append(imgDico)

Je souhaite que ma liste soit composée d’entrées sous la forme d’un dictionnaire qui comporte deux clés, que je vais nommer page et name. Je vais donc parcourir ma liste précédente et je vais avant tout tester la présence d’une image. Si l’entrée de la liste est de la forme “[xx]”, c’est-à-dire s’il n’y a pas de symbole “<“, alors on peut passer à l’entrée suivante.

Si “>” est au contraire présent alors je créé un dictionnaire vide, imgDico. Il faut penser à une chose : 2 images peuvent être sur une même page, donc dans une entrée, il se peut qu’il y ait plusieurs “<“, donc pour chaque entrée, je vais couper selon les caractères “<” (avec la méthode split, qui construit une liste composée de chaque portion comprise entre deux “<“); c’est le principe de la boucle “for x in i.split(‘<‘):” qui fait que l’on parcourt la liste construite par split.

Bon, je passe les détails mais ce dernier code construit des entrées sous la forme de dictionnaires, où le numéro des pages est formaté sur 3 caractères.

Le final

Python nous renvoie :

print(imgDicoList)
[{'page': '002', 'name': 'avatar'}, {'page': '004', 'name': 'nsi'}, {'page': '006', 'name': 'sept'}, {'page': '008', 'name': 'tangente'}]

On a donc ainsi une liste de toutes les illustrations ainsi que leur page.

Alternative

Le début du code peut être simplifié à l’aide du module re. De plus, plutôt que de passer en ligne de commande avant d’exécuter le programme Python, on peut faire appel au module os pour exécuter la ligne “dvips…” directement.

import re
import os

instruction = "dvips -o Essai.ps Essai > logdvi.txt"
os.system(instruction)

regex = re.compile(r'[\n]')
fichier = open("logdvi.txt", "r")
fic = fichier.read()
fic = regex.sub(" ",fic)

fichier.close()

crochetOuvrant = False
imgList = []

for c in fic: 
    if c == "[":
        crochetOuvrant = True
        container = ""
    else:
        if c == "]":
            crochetOuvrant = False
            imgList.append(container)
            
        else:
            if crochetOuvrant == True:
                container += c

imgDicoList = [] 
page = ''

for i in imgList:
    if '<' in i:
        imgDico = {}
        for x in i.split('<'):
            if len(x)<4:
                pageCount = True
                if len(x) == 1:
                    page = '00'+x
                elif len(x) == 2:
                    page = '0'+x
                else:
                    page = x
            else:
                pageCount = False
                name = x[6:]
                name = name[:-5]
            if pageCount == False:
                imgDico['page'] = page
                imgDico['name'] = name
                imgDicoList.append(imgDico)

for i in imgDicoList:
    for key, value in i.items():
        print (key, value)

Les abonnés à ce site pourront télécharger le ZIP contenant le fichier source LaTeX, le code Python et les images EPS sur cette page.

Engendrer une feuille d’exercices aléatoires avec Python en \(\LaTeX\)

Combien de fois ai-je voulu générer automatiquement des exercices similaires (par exemple, de développement) ? Vous ne le savez pas, mais moi, je le sais : beaucoup trop !

Encore aujourd’hui, j’ai voulu générer une série de multiplications pour faire réviser ses tables une de mes élèves.

Comme je me suis mis à Python il n’y a pas longtemps, et comme dans la foulée je me suis aussi mis à PythonTeX, j’ai forcément pensé à tout ça pour faire ma feuille d’exercices (plutôt que d’inventer et de taper plus de 90 opérations).

Nous allons voir comment.

Créer et insérer directement des graphiques 3D avec Pythontex sous LaTeX

La prise en main et l’installation de Pythontex peut s’avérer assez fastidieuse quand on s’y met. Par expérience, je peux vous dire que la tâche est encore plus difficile sous Ubuntu quand on est novice (et je le suis !). C’est une des raisons pour lesquelles je n’ai pas souhaité resté sous Ubuntu pour me remettre à Windows.

Une fois Pythontex installé, je pense qu’il est légitime de vouloir l’exploiter à fond, y compris pour faire des choses qu’avec \(\LaTeX\) seul il est difficile de faire. Parmi ces choses,il y a les graphiques, et plus particulièrement les graphiques 3D (car les courbes 2D, PGF sait le faire facilement).

La méthode de Hörner

Considérons un polynôme P, dont une racine est égale à a.

La méthode de Hörner va nous permettre de trouver les coefficients du polynôme Q tel que : \[P(x)=(x-a)Q(x).\]

Bien entendu, il existe d’autres méthodes, comme la division euclidienne de polynômes ou encore la méthode des coefficients indéterminés, mais nous allons voir que la méthode de Hörner a deux avantages sur les autres : sa rapidité et le fait que l’on puisse la programmer aisément.

Chiffrement affine en Python

Le chiffrement affine est une méthode de chiffrement basée sur les fonctions affines… Mouais !

En d’autres termes, si x est le code d’une lettre sur un alphabet déterminé alors cette dernière sera transformée en une autre lettre dont le code est égal à ax+b mod n (où n est le nombre de caractères de l’alphabet choisi et où a et b sont deux entiers strictement inférieurs à n).