Cryptographie_Exercices_corrigés.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Cryptographie - Exercices corrigés.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "history_visible": true,
      "authorship_tag": "ABX9TyPKtD76dLi6c9Gs1V9WUfb/",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/GeoLabUniLaSalle/Python/blob/main/Cryptographie_Exercices_corrig%C3%A9s.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5-CCoKXFZT3Q"
      },
      "source": [
        "## **Exercice 1 : Temps de calcul**\n",
        "\n",
        "**Objectif**\n",
        "\n",
        "Connaissant le texte d'origine, le même texte chiffré, et l'algorithme de cryptographie utilisé, déterminer le temps nécessaire pour découvrir la clé par force brute.\n",
        "Voici les paramètres utiles :\n",
        "\n",
        "*   La clé à déterminer pèse 128 bits\n",
        "*   On estime le nombre d'opérations élémentaires pour chiffrer à 1000\n",
        "*   Nous disposons d'un PC équipé d'un processeur capable d'effectuer 110 000 millions d'instructions par seconde (Intel Core i7-8086K, 2018)\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RMZlzjlxZP20",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "d34cef94-9acd-4670-e6f9-bfcf7a86167f"
      },
      "source": [
        "operations = 2**128*1000\n",
        "print(operations)\n",
        "secondes = operations / 110_000_000_000\n",
        "print(secondes)\n",
        "annees = secondes / 60 / 60 / 24 / 365\n",
        "print(annees)"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "340282366920938463463374607431768211456000\n",
            "3.0934760629176224e+30\n",
            "9.809348246187286e+22\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "t59zVdvCdC-K"
      },
      "source": [
        "Vous devez trouver 9.8 x 10^22 années.\n",
        "\n",
        "Pour donner un idée, le Big Bang date de 13,7 milliards d'années.\n",
        "\n",
        "Le calcul peut être réparti sur plusieurs ordinateurs mais ça ne suffirait pas...\n",
        "\n",
        "Quelle est la durée du calcul pour une clé codée sur 56 bits ? Et si on réparti le calcul sur 1000 PC ?"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Nn2X7I4IcXw7",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ee6ef0de-c246-4fc4-fb31-6419250e3b9a"
      },
      "source": [
        "operations = 2**56*1000\n",
        "secondes = operations / 110_000_000_000\n",
        "annees = secondes / 60 / 60 / 24 / 365\n",
        "print(annees)\n",
        "\n",
        "jours = annees * 365 / 1000\n",
        "print(jours)"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "20.772102889029547\n",
            "7.581817554495784\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PZ7GHOJSeKDB"
      },
      "source": [
        "Un peu moins de 20 ans, et cela descent à 7.5 jours si on fait travailler 1000 processeurs en parallèle sur la tâche. \n",
        "\n",
        "## **Exercice 2 : Chiffrement faible**\n",
        "\n",
        "**Objectif**\n",
        "\n",
        "Un système de cryptage consiste à faire une rotation du texte d'un certain nombre de caractères (vers la droite), puis à ajouter une valeur (avec modulo) à chacun des caractères.\n",
        "\n",
        "Par exemple, si on prend la chaîne \"abcz\", on peut faire une rotation d'un caractère vers la droite, et obtenir \"zabc\", puis ajouter 1 à chaque caractère, et obtenir la chaîne cryptée \"abcd\". \n",
        "\n",
        "Vous devez écrire un programme qui, à partir d'un texte original *a* (donné sous la forme d'une liste ne contenant que des lettres minuscules non accentuées) et d'un texte cryptée *b* (donné sous la même forme, et ayant la même taille), permette de retrouver les deux valeurs utilisées pour le cryptage (on garantit l'unicité de la solution).\n",
        "\n",
        "Voici un exemple :"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9NG2L4swc3P_"
      },
      "source": [
        "a = ['a','b','c','d']\n",
        "b = ['h','e','f','g']"
      ],
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "BwghduV0iOa8",
        "outputId": "89131f47-01ff-4897-f8c2-153001199037"
      },
      "source": [
        "def ajout(x):\n",
        "    '''\n",
        "    Retourne le message x en ajoutant 1 à chaque lettre du message\n",
        "    '''\n",
        "    code=[]\n",
        "    for i in x:\n",
        "        if i=='z':\n",
        "            code.append('a')\n",
        "        else:\n",
        "            code.append(chr(ord(i)+1))\n",
        "    return code\n",
        "\n",
        "print(ajout(['a','b','c','a']))"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['b', 'c', 'd', 'b']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "LDPjcUuliRDb",
        "outputId": "c001ebac-57e4-454f-ff76-895c29e9becc"
      },
      "source": [
        "def rotation(x):\n",
        "    '''\n",
        "    Retourne le message x en appliquant une rotation de 1\n",
        "    '''\n",
        "    return x[-1:] + x[:-1]\n",
        "\n",
        "print(rotation(['a','b','c','d']))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['d', 'a', 'b', 'c']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "r-S0XKiKiSMM",
        "outputId": "c3c4ba76-82ed-43b4-add7-8c3a78bc1b3f"
      },
      "source": [
        "def crypt(x, y):\n",
        "    '''\n",
        "    Retourne les valeurs de rotation et ajout à appliquer au message x pour obtenir le message codé y\n",
        "    '''\n",
        "    for i in range(len(x)):\n",
        "        x = rotation(x)\n",
        "        for j in range(26):\n",
        "            x = ajout(x)\n",
        "            if x==y:\n",
        "                return(i+1,j+1)\n",
        "    return 'pas de solution'\n",
        "\n",
        "print(crypt(['a','b','c','d'],['h','e','f','g']))"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "(1, 4)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UKXbgTSK87uC"
      },
      "source": [
        "Dans cet exemple, nous devons trouver :"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ps32SQJ988Cu",
        "outputId": "43c8214e-3cfd-42dd-8501-e84b030ac290"
      },
      "source": [
        "print('1 4')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 4\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7MtSJGew9wYX"
      },
      "source": [
        "En effet, en appliquant une rotation de 1 et une permutation de 4, nous obtenons le texte crypté :"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "C7hzSFA296q9",
        "outputId": "9eaa9ed8-f573-4864-f43c-e352f292ebd0"
      },
      "source": [
        "a = ['a','b','c','d']\n",
        "a = a[-1:] + a[:-1]\n",
        "print(a)\n",
        "\n",
        "for i in range(len(a)):\n",
        "  a[i]=str(chr(ord(a[i])+4))\n",
        "print(a)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "['d', 'a', 'b', 'c']\n",
            "['h', 'e', 'f', 'g']\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DoA4RTKD7vdT"
      },
      "source": [
        "## **Exercice 3 : Permutation alphabétique**\n",
        "\n",
        "**Objectif**\n",
        "\n",
        "Chiffrez le texte 'vive la cryptographie' avec la clé suivante : 'yruhfwlkdxeajitsvznmcpbgqo' et un chiffrement en permutation alphabétique (a remplacé par y, b remplacé par r, etc.)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AjDUGq8G7yCG",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "f49a5cb4-6050-44b4-c75e-85335b4918f0"
      },
      "source": [
        "from string import ascii_lowercase, ascii_uppercase\n",
        "import random as rd\n",
        "\n",
        "lower = ascii_lowercase\n",
        "upper = ascii_uppercase\n",
        "\n",
        "cle = 'yruhfwlkdxeajitsvznmcpbgqo'\n",
        "\n",
        "table = dict()\n",
        "for i in range(26):\n",
        "  table[lower[i]] = cle[i]\n",
        "  table[upper[i]] = cle[i].upper()\n",
        "print(table)"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "{'a': 'y', 'A': 'Y', 'b': 'r', 'B': 'R', 'c': 'u', 'C': 'U', 'd': 'h', 'D': 'H', 'e': 'f', 'E': 'F', 'f': 'w', 'F': 'W', 'g': 'l', 'G': 'L', 'h': 'k', 'H': 'K', 'i': 'd', 'I': 'D', 'j': 'x', 'J': 'X', 'k': 'e', 'K': 'E', 'l': 'a', 'L': 'A', 'm': 'j', 'M': 'J', 'n': 'i', 'N': 'I', 'o': 't', 'O': 'T', 'p': 's', 'P': 'S', 'q': 'v', 'Q': 'V', 'r': 'z', 'R': 'Z', 's': 'n', 'S': 'N', 't': 'm', 'T': 'M', 'u': 'c', 'U': 'C', 'v': 'p', 'V': 'P', 'w': 'b', 'W': 'B', 'x': 'g', 'X': 'G', 'y': 'q', 'Y': 'Q', 'z': 'o', 'Z': 'O'}\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "S_AFHm5FiZSb",
        "outputId": "2bf76696-c74e-4434-91ff-b62879e29b10"
      },
      "source": [
        "def code(x, table):\n",
        "  \"\"\"\n",
        "  Retourne x chiffré par la table de correspondance table\n",
        "  \"\"\"\n",
        "  code=\"\"\n",
        "  for i in x:\n",
        "    if i in lower+upper:\n",
        "      code+=table[i]\n",
        "    else:\n",
        "      code+=i\n",
        "  return code\n",
        "\n",
        "print(code('vive la cryptographie',table))"
      ],
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "pdpf ay uzqsmtlzyskdf\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "w-0NRLONgls9"
      },
      "source": [
        "Vous devez obtenir : 'pdpf ay uzqsmtlzyskdf'\n",
        "\n",
        "## **Exercice 4 : Le chiffre de Vigenère**\n",
        "\n",
        "**Objectif**\n",
        "\n",
        "Chiffrez le texte 'vive la cryptographie' avec la clé 'python'."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XlCUROW5fpHl"
      },
      "source": [
        "def vigenere(x,cle):\n",
        "  \"\"\"\n",
        "  Retourne x chiffré avec le chiffre de Vigenère et le texte cle\n",
        "  \"\"\"\n",
        "  code=\"\"\n",
        "  for i in range(len(x)):\n",
        "    if x[i] in lower:\n",
        "      code += lower[(lower.index(x[i])+lower.index(cle[i%len(cle)]))%26]\n",
        "    elif x[i] in upper:\n",
        "      code += upper[(upper.index(x[i])+lower.index(cle[i%len(cle)]))%26]\n",
        "    else:\n",
        "      code+=x[i]\n",
        "  return code"
      ],
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HsreVslXigwd",
        "outputId": "f7391194-1b7e-4b64-8b41-d91f0665f9f3"
      },
      "source": [
        "print(vigenere('vive la cryptographie','python'))"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "kgol yp vymcimzyocwgx\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tY_4VK56hS40"
      },
      "source": [
        "Vous devez obtenir 'kgol yp vymcimzyocwgx'.\n",
        "\n",
        "Retrouvez maintenant le texte en clair associé au texte 'vn jsbgx puov zvjflirwhv' qui a été chiffré avec la clé 'baguette'."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xvEvxo48gM_D"
      },
      "source": [
        "def decode_vigenere(x,cle):\n",
        "  \"\"\"\n",
        "  Retourne x chiffré avec le chiffre de Vigenère et le texte cle\n",
        "  \"\"\"\n",
        "  code=\"\"\n",
        "  for i in range(len(x)):\n",
        "    if x[i] in lower:\n",
        "      code += lower[(lower.index(x[i])-lower.index(cle[i%len(cle)]))%26]\n",
        "    elif x[i] in upper:\n",
        "      code += upper[(upper.index(x[i])-lower.index(cle[i%len(cle)]))%26]\n",
        "    else:\n",
        "      code+=x[i]\n",
        "  return code"
      ],
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "EIMsZl85isnM",
        "outputId": "9e1d50d2-ebe6-4b7a-c048-286f0399ce38"
      },
      "source": [
        "print(decode_vigenere('vn jsbgx puov zvjflirwhv','baguette'))"
      ],
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "un point pour griffondor\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UCHyk8w6hrVb"
      },
      "source": [
        "Vous devez obtenir 'un point pour griffondor !'.\n",
        "\n",
        "Retrouvez enfin la clé associée au texte 'un point pour griffondor' dont la version chiffrée est 'kh srqgv ficu okkmvivgrz !'."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9AFK8T6XgV8R"
      },
      "source": [
        "def cle_vigenere(x,y):\n",
        "  \"\"\"\n",
        "  Retourne la clé utilisée pour chiffrer x avec le chiffre de Vigenère donnant y\n",
        "  \"\"\"\n",
        "  cle=\"\"\n",
        "  for i in range(len(x)):\n",
        "    if x[i] in lower:\n",
        "      cle += lower[(lower.index(y[i])-lower.index(x[i]))%26]\n",
        "    elif x[i] in upper:\n",
        "      cle += upper[(upper.index(y[i])-upper.index(x[i]))%26]\n",
        "    else:\n",
        "      cle+=x[i]\n",
        "  return cle"
      ],
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eYtduXuxiqBU",
        "outputId": "2df254e2-331b-43c6-a6cc-a5d95998d3b8"
      },
      "source": [
        "print(cle_vigenere('un point pour griffondor','kh srqgv ficu okkmvivgrz'))"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "qu dditc quid itchquiddi\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ynPpI4iIiUAM"
      },
      "source": [
        "La réponse est 'quidditch'.\n",
        "\n",
        "\n",
        "## **Conclusion**\n",
        "\n",
        "Les algorithmes vus dans ce chapitre sont dits **symétriques** parce qu'ils utilisent une seule et même clé pour **chiffer** et pour **déchiffrer**.\n",
        "\n",
        "Le défaut de cette technique est que la clé doit rester **confidentielle**. Si une autre personne que le correspondant a accès à la clé, il sera capable de lire de texte en clair, et de produire de faux textes chiffrés à destination du correspondant initial.\n",
        "\n",
        "En pratique, on crée une **clé unique** pour chaque correspondant différent.\n",
        "\n",
        "Les algorithmes vus ici sont les plus simples, il en existe de beaucoup plus élaborés.\n",
        "\n",
        "Par exemple, l'algorithme du **masque jetable** qui reprend le principe du chiffre de Vigenère, mais pour lequel la clé est générée aléatoirement, est forcément d'une taille au moins égale à celle du texte à chiffrer, et n'est pas réutilisable (on génère une nouvelle clé pour chaque texte à chiffrer, même pour un même correspondant).\n",
        "\n",
        "D'autres algorithmes de chiffrement symétrique sont actuellement utilisés en pratique, comme AES qui est le **standard actuel**. AES (Advanced Encryption Standard) fonctionne avec une clé codée sur 128, 192 ou 256 bits stockée dans une matrice sur laquelle on opère des opérations (rotation, multiplication, opérations logiques) pour chiffrer les messages.\n",
        "\n"
      ]
    }
  ]
}