{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4ee72c9f-15ad-4c81-8769-937eeee677f6",
   "metadata": {},
   "source": [
    "# Chiffrement symétrique OTP\n",
    "L'objectif de cet exercice est de coder une fonction qui permet de\n",
    "   chiffrer avec le chiffrement parfait :  $$ C = M \\oplus K$$ Cette\n",
    "   fonction prend en entrée une clé et un message, qui sont de\n",
    "   même taille, et tous deux sous forme de chaîne de caractères, et\n",
    "   sa sortie est également une chaîne de caractères. Vous aurez\n",
    "   peut-être l'usage de l'opérateur `^^`, `chr` et `ord`.\n",
    "\n",
    "   1) Codez une fonction qui permet de chiffrer avec le chiffrement parfait ($ C = M \\oplus K$).\n",
    "   2) Codez la fonction de déchiffrement correspondante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fcbb35b4-5fd0-4b03-8864-3acf1d8e5576",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7231ad8e-6ace-4a01-bcbe-8e48fcf5d222",
   "metadata": {},
   "source": [
    "# Protocole à trois passes de Shamir\n",
    "Le chiffrement OTP (exercice ci-dessus) est parfaitement sûr (la connaissance du chiffré ne donne aucune information sur le message). Cependant, il est nécessaire d'avoir un secret partagé (ici $K$) avant de pouvoir communiquer. On suppose donc maintenant qu'Alice et Bob souhaitent communiquer sans avoir de secret partagé. Ils vont utiliser le protocole de trois passes de Shamir pour qu'Alice communique un nombre secret $m$ à Bob. Ils choississent chacun une clé secrète ($K_A$ pour Alice et $K_B$ pour Bob) et échangent les trois messages suivants (en utilisant OTP pour le chiffrement/déchiffrement) :\n",
    "1) Alice chiffre le message $m$ avec sa clé $K_A$ et envoie le résultat à Bob : $\\{m\\}_{K_A}$ qui vaut $51$\n",
    "2) Bob ne peut pas déchiffrer ce message, il chiffre donc le message reçu avec sa clé secrète $K_B$ et envoie le résultat à Alice : $\\{\\{m\\}_{K_A}\\}_{K_B}$ qui vaut $69$\n",
    "4) Alice déchiffre le message reçu avec sa clé $K_A$ et envoie le résultat à Bob : $\\{m\\}_{K_B}$ qui vaut $60$\n",
    "\n",
    "Retrouver le nombre mystère $m$. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41ec2ce4-30fc-4547-aa21-62564a63a5d7",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "6b4a1298-b901-42a3-ad6a-23cb700509e8",
   "metadata": {},
   "source": [
    "# LFSR \n",
    "1) Soit le LSFR avec la graine $s^{(0)}=[0,0,1,0]$ et les coefficients $c=[1,0,1,0]$ (cf MescoursJV). \n",
    "\n",
    "    - Calculez les 10 premiers bits de sortie. Vérifiez ensuite les résultats à la main.\n",
    "\n",
    "2) On considère le LFSR de longueur $\\ell = 3$ avec\n",
    "    $(c_1, c_2, c_3) = (1,0,1)$, initialisé à\n",
    "    $(z_2, z_1, z_0) = (0,0,1)$.\n",
    "\n",
    "   - Représentez l'état $s^{(i)}$ du LFSR pour\n",
    "    $1 \\leq s^{(i)} \\leq 7$. Donnez la sortie de ce LFSR et sa période.\n",
    "   - Pourquoi les sorties du LFSR sont-elles périodiques ? Quelle est la plus longue période possible pour un LFSR de longueur $\\ell$?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d69e7409-a788-4623-9d37-0dee8f00fc2c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "2a6cc005-a391-4340-ad08-d167ccd2029c",
   "metadata": {},
   "source": [
    "# Chiffrer une image\n",
    "L'objectif de cet exercice est de chiffrer une image en ligne de commande (pas en Sage) à l'aide des outils fournis par la librairie openssl (en ligne de commande). Écrivez un script bash en suivant les étapes ci-dessous :\n",
    "- Prenez une image d'un drapeau de votre choix (Royaume-Uni par exemple) et convertissez la dans le format $\\texttt{ppm}$ à l'aide de la commande `convert`.\n",
    "- Mettez les trois premières lignes de votre fichier $\\texttt{ppm}$ dans un fichier intitulé _header.txt_\n",
    "- Mettez tout le fichier $\\texttt{ppm}$ sauf les 3 premières lignes dans un fichier _body.bin_\n",
    "- Chiffrez avec `openssl` en AES-ECB le fichier _body.bin_\n",
    "- Remettez l'en-tête _header.txt_ au début du fichier obtenu à la question précédente pour avoir une image chiffrée, et observez le résultat."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f0016dc4-bd7b-4ec6-af54-581ed785a6de",
   "metadata": {},
   "source": [
    "# Mode chiffrement\n",
    "Voici un mode de chiffrement, avec $IV$ un vecteur initial, $M_i$\n",
    "  les messages en clair et $C_i$ les chiffrés :\n",
    "\n",
    "$$C_i = M_i \\oplus O_i$$\n",
    "$$O_i = \\ E_K (O_{i-1})$$\n",
    "$$O_{0} = \\ \\mbox{IV}$$\n",
    "\n",
    "1) Donner une représentation graphique de ce mode de chiffrement.\n",
    "2) Donner le mode de déchiffrement correspondant."
   ]
  },
  {
   "cell_type": "raw",
   "id": "f60c2be1-788a-4263-a526-3f4b6d608add",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "1a51cd0b-88a7-42fa-a3b5-b0e0b12255b4",
   "metadata": {},
   "source": [
    "# Attaque _Meet in the Middle_\n",
    "Les algorithmes de chiffrement symétrique et de déchiffrement\n",
    "symétrique sont publics, et la sécurité repose sur une clé\n",
    "secrète $K$, qui sert à la fois à chiffrer et à déchiffrer.\n",
    "\n",
    "Pour chiffrer le message $M$ à l'aide de la clé secrète $K$,\n",
    "Alice calcule le chiffré $C = ENC(K, M)$. Pour déchiffrer le\n",
    "message chiffré $C$ à l'aide de la clé $K$, Bob calcule\n",
    "$M = DEC(K, C)$. Un attaquant a découvert $M$ et $C$, mais\n",
    "le chiffrement ne permet pas d’en déduire $K$. Or l’attaquant voudrait\n",
    "connaître la clé $K$ pour pouvoir lire les prochains messages\n",
    "chiffrés d’Alice. Il sait seulement que $K$ est un nombre composé de\n",
    "$n$ bits en binaire.\n",
    "\n",
    "Pour découvrir $K$, l’attaquant décide d’essayer de chiffrer $M$\n",
    "avec toutes les valeurs possibles de la clé pour tenter de retrouver\n",
    "$C$ : c’est une attaque par recherche exhaustive (aussi appelée _bruteforce attack_). \n",
    "Puisqu’il sait que\n",
    "la longueur de la clé qu’il cherche est de $n$ bits, il devra tester,\n",
    "dans le pire des cas, tous les nombres composés de $n$ bits, et il y\n",
    "en a $2^{n}$.\n",
    "\n",
    "Pour avoir une meilleure sécurité, Alice a l’idée de chiffrer deux\n",
    "fois son message avec deux clés différentes $K_1$ et $K_2$ :\n",
    "$C = ENC(K_2, ENC(K_1, M))$. De cette façon, elle se dit que, en\n",
    "supposant que $K_1$ et $K_2$ comportent toutes les deux $n$ bits,\n",
    "l’attaquant devra effectuer dans le pire des cas\n",
    "$2^{n} \\times 2^{n} = 2^{2n}$ tests pour découvrir les deux clés.\n",
    "\n",
    "- Trouver un moyen pour découvrir les deux clés beaucoup plus efficacement que par une attaque par recherche exhaustive."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c38fcfc6-b5bb-4e12-bd14-ba3bd44a5ec0",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7af942d1-846e-46cb-850c-3c8fec427e49",
   "metadata": {},
   "source": [
    "[BONUS] Défi\n",
    "Déchiffrer le message suivant : 21 34 42 44 54-44 52 34: \\ 44 23 15 \\ 11 33 43 52 15 42 \\ 44 34 \\ 31 24 21 15\n",
    "\n",
    "Hint: Jim Moriarty\n",
    "23 24 33 44: \\ 24 24 32 \\ 32 34 42 24 11 42 44 54"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bf288033-738a-4384-8fe6-ba00dd62a6e6",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.7",
   "language": "sage",
   "name": "sagemath-10.7"
  },
  "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.13.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}