{ "cells": [ { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import datetime as dt" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#
TP4 - Génération d'une clef aléatoire
Registres à décalage à rétroaction linéaire (LFSR)
\n", "
2025/2026 - L. Naert, S. Bouchelaghem, T. Godin
\n", "\n", "_Certains exemples et textes de ce TP sont tirés de Exercices et Problèmes de cryptographie de Damien Vergnaud, 3ème édition ainsi que de Codes et Cryptologie de Christine Bachoc._\n", "\n", "__Usage de l'IA générative : interdit__\n", "\n", "\n", "Ce TP traite d'un des aspects de la cryptographie symétrique moderne (post 1950) : la génération d'une clef binaire \"aléatoire\" pour le chiffrement d'un message, lui aussi binaire, selon le principe du _masque jetable_.\n", "\n", "_Note_ : à tout moment, vous pouvez utiliser des fonctions définies dans les TPs précédents." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1 - Messages en binaire et masque jetable\n", "\n", "Avec l'arrivée des ordinateurs et du binaire, les messages sont d'abord convertis en suites de $0$ et de $1$ avant d'être transmis. Nous travaillerons donc maintenant non plus sur l'ensemble $\\mathbb{Z}/26\\mathbb{Z}$ mais sur $\\mathbb{Z}/2\\mathbb{Z}$ qui est un ensemble composé de deux valeurs $0$ et $1$.\n", "\n", "\n", "Voici deux fonctions qui vous seront (certainement) utiles dans la suite du TP :\n", "\n", "- `stringToBinary` convertit une chaine de caractère en une suite binaire.\n", "- `binaryToString` permet de changer une suite binaire en chaine de caractère." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "En binaire : 01101101011001010111001101110011011000010110011101100101001000000110010101101110001000000110001101101100011000010110100101110010\n", "En ascii : message en clair\n" ] } ], "source": [ "def stringToBinary(msg):\n", " msg_bin = \"\"\n", " for i in bytearray(msg, encoding ='ascii') :\n", " msg_bin = msg_bin + format(i, '08b')\n", " return msg_bin\n", "\n", "def binaryToString(binary):\n", " msg = \"\"\n", " for i in range(0, len(binary), 8):\n", " byte_int = int(binary[i:i+8], 2)\n", " byte_char = chr(byte_int)\n", " msg = msg + byte_char\n", " \n", " return msg\n", "\n", " \n", "print(\"En binaire :\", stringToBinary(\"message en clair\"))\n", "print(\"En ascii :\",binaryToString(stringToBinary(\"message en clair\")))\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le masque jetable, aussi appelé \"chiffrement de Vernam\", repose sur le principe du \"ou exclusif\" (_xor_, noté $\\oplus$, opérateur ^ en python) bit à bit entre le message binaire à chiffrer et la clef de chiffrement (de même longueur). \n", "\n", "Voici la table de vérité du \"ou exclusif\" :\n", "$$ 0 \\oplus 0 = 0 $$ \n", "$$ 1 \\oplus 1 = 0 $$\n", "$$ 1 \\oplus 0 = 1 $$\n", "$$ 0 \\oplus 1 = 1 $$\n", "\n", "Ainsi, étant donné une clef _k_ de longueur _n_ (donc $k \\in (\\mathbb{Z}/2\\mathbb{Z})^n$)\n", "\n", "\\begin{align*}\n", " E_k \\colon (\\mathbb{Z}/2\\mathbb{Z})^n &\\to (\\mathbb{Z}/2\\mathbb{Z})^n\\\\\n", " m &\\mapsto c = m \\oplus k\n", "\\end{align*}\n", "\n", "Par exemple, avec $m = 1100 1100$ et $k = 1010 1011$, on aura $c = 0110 0111$ (Vérifiez par vous même !)\n", "\n", "Le masque jetable garantit la sécurité des messages à condition qu'une clef ne serve qu'au chiffrement d'un seul message (d'où le \"jetable\" du nom) sinon, la cryptanalyse devient possible.\n", "\n", "\n", "> __Question 1 (masque jetable/Chiffrement de Vernam)__ : Définir une fonction `chiffrementVernam(msgBinaire, clef)` qui étant donné un message en clair binaire `msgBinaire`, et une suite binaire `clef` de même longueur que le message retourne le message chiffré correspondant.\n", "\n", "Note : En python, le \"ou exclusif\" est l'opérateur `^`" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "chiffrementVernam : OK\n" ] } ], "source": [ "def chiffrementVernam(msgBinaire, clef):\n", " res = \"\"\n", " for i in range (len(msgBinaire)) :\n", " res += str(int(msgBinaire[i])^int(clef[i]))\n", " return res\n", "\n", "try:\n", " assert chiffrementVernam(stringToBinary(\"vernam\"),\"110011001100110011001100110011001100110011001100\") == \"101110101010100110111110101000101010110110100001\"\n", " print(\"chiffrementVernam : OK\")\n", "except:\n", " print(\"chiffrementVernam : ERREUR\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le déchiffrement s'opère en executant la même opération : $m = c \\oplus k$\n", "\n", "> __Question 2 (déchiffrement)__ : Le démontrer." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour démontrer : $$ m = c \\oplus k $$\n", "On sait : $$ 0 = x \\oplus x $$\n", "On a $$ c \\oplus k = ( c \\oplus k ) \\oplus k = m \\oplus ( k \\oplus k ) = m \\oplus 0 = m $$\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Question 3 (déchiffrement)__ : Quel clair (en ascii) représente le chiffré \"1010001010101101101010011011111010111000\" codé avec la clef \"1100110011001100110011001100110011001100\" ? Ecrire le bout de code permettant de le déchiffrer." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'naert'" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c = \"1010001010101101101010011011111010111000\"\n", "k = \"1100110011001100110011001100110011001100\"\n", "binaryToString(chiffrementVernam(c,k))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2 - Registre à décalage à rétroaction linéaire\n", "\n", "En pratique, il existe deux inconvénients majeurs au principe du chiffrement par masque jetable : \n", "1. Les clefs doivent faire la même longueur que le message à chiffrer. Transmettre des clefs aussi longues est un problème en soi. \n", "2. Pour assurer la sécurité des messages, il faut que la clef soit choisie aléatoirement. Or, nous ne savons pas comment produire du vrai aléa. \n", "\n", "\n", "Les __registres à décalage à rétroaction linéaire__ ou __LFSR__ (pour _linear feedback shift register_) permettent de pallier partiellement ces deux inconvénients en générant une suite binaire proche de l'aléatoire véritable à partir de quelques bits appelés _graine_. Il suffit donc de transmettre la graine ainsi que la fonction interne du LFSR, et non plus la suite entière, au destinataire du message pour qu'il puisse déchiffrer le message.\n", "\n", "Un LFSR binaire de longueur $L$ est composé :\n", "- d'un registre à décalage contenant une suite de $L$ bits ($s_i$, $s_{i+1}$, ..., $s_{i+L−1}$) décrivant l'état interne du registre.\n", "- d'une fonction de rétroaction linéaire permettant de calculer la valeur du bit suivant à insérer dans le registre.\n", "\n", "A chaque top d'horloge, le bit $s_i$ constitue la sortie du registre, et les autres sont décalés ; le nouveau bit $s_{i+L}$, placé dans la cellule rendue libre du registre, est donné par une fonction :\n", "$s_{i+L} = c_0s_{i} \\oplus c_1s_{i+1} \\oplus ... \\oplus c_{L−1}s_{i+L-1}$\n", "où les coefficients $c_i$ sont binaires.\n", "\n", "On appelle __suite chiffrante__ la concaténation des sorties du registre. C'est cette suite qui servira ensuite de clef de chiffrement.\n", "\n", "On peut représenter ce LFSR de la manière suivante :\n", "\n", "\n", "\n", "\n", "Ci-dessous un exemple de LFSR de longueur $L = 4$ initialisé avec la graine $1001$ à $t_0$: \n", "\n", "\n", "\n", "\n", "Les coefficients de la fonction de rétroaction sont : $c_0 = 1, c_1 = 0, c_2 = 1, c_3 = 1$. \n", "\n", "Le bit inséré à droite est donc calculé grace à la formule : $s_{i+4} = s_{i} \\oplus s_{i+2} \\oplus s_{i+3}$.\n", "\n", "Nous avons déroulé les 2 premières itérations ($t_1$ et $t_2$) du registre. A l'étape $t_1$, la sortie est le bit situé le plus à gauche du registre (de valeur $1$). A l'étape $t_2$, c'est le bit $0$ qui sort permettant de créer la suite chiffrante $10$ en considérant la sortie de l'étape précédente.\n", "\n", "\n", "\n", "\n", "> __Question 4 (suite chiffrante)__ : Quelle sera la suite chiffrante à $t_{14}$ ? Que remarquez vous ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Question 5 (registre à décalage)__ : Ecrire une fonction `etatSuivant(etat,coeff)` qui prend une liste binaire correspondant à l'état interne du registre ainsi qu'une liste des coefficients de rétroaction non nuls (i.e. indices des cases sur lesquelles faire le xor) et renvoie l'état suivant du registre et le bit de sortie." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "etatSuivant : OK\n" ] } ], "source": [ "def etatSuivant(etat,coeff):\n", " n = len(etat)\n", " nouvelleValeur = 0\n", " for i in coeff:\n", " nouvelleValeur ^= etat[i]\n", " nouvelEtat = etat[1:] + [nouvelleValeur]\n", " return (nouvelEtat, etat[0])\n", " \n", "\n", "try:\n", " assert etatSuivant([1,0,0,1],[0,2,3]) == ([0, 0, 1, 0],1) #Exemple précédent t1\n", " assert etatSuivant(etatSuivant([1,0,0,1],[0,2,3])[0],[0,2,3]) == ([0, 1, 0, 1],0) #Exemple précédent t2\n", " print(\"etatSuivant : OK\")\n", "except:\n", " print(\"etatSuivant : ERREUR\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Question 6 (suite chiffrante)__ : Ecrire une fonction `suite_LSFR(graine,coeff,n)` qui prend en entrée une liste binaire correspondant à la graine du registre, une liste des coefficients de rétroaction non nuls et la longueur souhaitée de la suite chiffrante et qui renvoie la suite chiffrante binaire sous forme d'une chaine de caractère." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "suite_LFSR : OK\n", "1100100011\n", "1011100101\n" ] } ], "source": [ "def suite_LFSR(graine,coeff,n):\n", " etat = graine\n", " res = \"\"\n", " for _ in range(n):\n", " etat, bit_sortie = etatSuivant(etat, coeff)\n", " res += str(bit_sortie)\n", " return res\n", "\n", "try:\n", " assert suite_LFSR([1,0,0,1],[0,2,3],14) == \"10010111001011\"\n", " print(\"suite_LFSR : OK\")\n", "except:\n", " print(\"suite_LFSR : ERREUR\")\n", "\n", "print(suite_LFSR([1,1,0,0],[0,3],10))\n", "print(suite_LFSR([1,0,1],[0,1],10))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction suivante permet de générer une graine d'une taille précisée en paramètre. N'hésitez pas à l'utiliser pour tester vos méthodes." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "La graine est égale à : [1, 1, 1, 0, 1, 1, 0, 1] \n", "\n" ] } ], "source": [ "def generation_reg_graine(taille):\n", " \"\"\"\n", " Génération d'une graine de taille \"taille\" basée sur l'heure\n", " \"\"\" \n", "\n", " ### Transformation de la date en une chaine de caractères\n", " date = str(dt.datetime.now())\n", " #print(date)\n", " ### Transformation de la fin de la chaine en un entier compris entre 0 et 255 pour pouvoir le représenter avec 8 bits\n", " init_entier = int(date[-4:]) % 2**taille # j'ai choisi de prendre les 4 derniers caractères arbitrairement\n", "\n", " ### Représentation de l'entier sur un octet\n", " init_bin = bin(init_entier)[2:] # on retire le 0b qui permet de préciser qu'il s'agit d'un nombre binaire\n", " while len(init_bin) < taille : \n", " init_bin = '0' + init_bin # on rajoute des 0 pour que le nombre produit soit composé de taille bits. (padding)\n", " #print(init_bin)\n", " ### Transformation de la chaine des bits en une liste\n", " init_reg = [int(x) for x in init_bin]\n", " return init_reg\n", "\n", "init_reg = generation_reg_graine(8)\n", "print('La graine est égale à :', init_reg,'\\n')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Question 7 (Chiffrement par LFSR)__ : Ecrire une fonction `chiffrementLFSR(msgAscii, graine,coeff)` qui déroule l'ensemble du processus de chiffrement par masque jetable généré par LSFR et retourne la version binaire du message chiffré." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1011111111000010001000111111111101101110\n", "chiffrementLFSR : OK\n" ] } ], "source": [ "def chiffrementLFSR(msgAscii, graine,coeff):\n", " msgBinaire = stringToBinary(msgAscii)\n", " n = len(msgBinaire)\n", " keystream = suite_LFSR(graine, coeff, n)\n", " res = \"\"\n", " for i in range(n):\n", " res += str(int(msgBinaire[i]) ^ int(keystream[i]))\n", " return res\n", "\n", "print(chiffrementLFSR(\"naert\",[1,1,0,1],[0,2,3]))\n", "\n", "\n", "try:\n", " assert chiffrementLFSR(\"naert\",[1,0,0,1],[0,2,3]) == \"1111100101001111001110011100101100000110\"\n", " print(\"chiffrementLFSR : OK\")\n", "except:\n", " print(\"chiffrementLFSR : ERREUR\")\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Question 8 (Déchiffrement par LFSR)__ : Ecrire une fonction `dechiffrementLFSR(msgChiffBinary, graine,coeff)` qui déroule l'ensemble du processus de déchiffrement et retourne la version ascii du message en clair." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "dechiffrementLFSR : OK\n" ] } ], "source": [ "def dechiffrementLFSR(msgChiffBinary, graine,coeff):\n", " n = len(msgChiffBinary)\n", " keystream = suite_LFSR(graine, coeff, n)\n", " res = \"\"\n", " for i in range(n):\n", " res += str(int(msgChiffBinary[i]) ^ int(keystream[i]))\n", " return binaryToString(res)\n", "\n", "try:\n", " assert dechiffrementLFSR(\"1111100101001111001110011100101100000110\",[1,0,0,1],[0,2,3]) == \"naert\"\n", " print(\"dechiffrementLFSR : OK\")\n", "except:\n", " print(\"dechiffrementLFSR : ERREUR\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Activité 1__ : Chiffrer un message à l'aide d'une clef générée par un LFSR de taille 8 et envoyez le message chiffré, la graine et les coefficients de votre LFSR à votre voisin(e) pour qu'il/elle le déchiffre." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "__Ouverture cryptanalyse__ : Les LFSR sont susceptibles d'être cryptanalysés en utilisant un pivot de Gauss. Vous pouvez vous référer à \"_Exercices et Problèmes de cryptographie_\" de Damien Vergnaud pour plus d'informations." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3 - Périodicité (bonus)\n", "\n", "\n", "En pratique, la suite chiffrante produite par un unique LFSR n'est pas assez complexe pour servir de clef de chiffrement. Nous avons vu notamment à la question 4 que les LFSR pouvait produire des suites chiffrantes périodiques donc loin d'une suite réellement aléatoire. En réalité, toute suite chiffrante produite par un unique LSFR est ultimement périodique.\n", "\n", "\n", "_Définitions_ : \n", "\n", "Soit une suite $s = (s_0,s_1,s_2...)$ avec pour tout $i \\in \\mathbb{N}$, $s_i \\in \\mathbb{Z}/2\\mathbb{Z}$\n", "\n", "On dit que $s$ est __périodique__ de période T si $s_i = s_{i+T}$ pour tout $i \\ge 0$\n", "\n", "On dit qu'une suite $s$ est __ultimement périodique__ de période T si $s_i = s_{i+T}$ pour tout $i$ supérieur ou égal à un certain rang appelé $i_0$. Ainsi, une suite périodique est ultimement périodique ($i_0 = 0$) mais la réciproque est fausse.\n", "\n", "> __Question 9 (Période)__ : Ecrire une fonction `periode(graine,coeff)` qui donne la plus petite période de la suite générée par le générateur défini par `graine` et `coeff` ainsi que `True` s'il s'agit d'une suite périodique et `False` si elle est ultimement périodique avec $i_0 \\gt 0$ ." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Suite périodique : 10010111001011\n", "Suite ultimement périodique (mais non périodique) : 10110011001100\n", "periode : OK\n" ] } ], "source": [ "def periode(graine,coeff):\n", " return \"todo\"\n", "\n", "\n", "print(\"Suite périodique : \", suite_LFSR([1,0,0,1],[0,2,3],14))\n", "print(\"Suite ultimement périodique (mais non périodique) : \",suite_LFSR([1,0,1,1],[1,2,3],14))\n", "\n", "try:\n", " assert periode([1,0,0,1],[0,2,3]) == (7,True)\n", " assert periode([1,0,1,1],[1,2,3]) == (4,False)\n", " print(\"periode : OK\")\n", "except:\n", " print(\"periode : ERREUR\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour générer des suites chiffrantes utilisables dans un système cryptographique, les LFSR sont utilisés comme briques de base de système plus complexes : plusieurs LFSR peuvent être combinés pour atteindre la complexité souhaitée." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.6" } }, "nbformat": 4, "nbformat_minor": 4 }