{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# TD 5 - RSA\n", "\n", "## Exercice 1\n", "\n", "On demandait de chiffrer le message représenté par l'entier $v$, il n'y avait donc qu'à calculer $v^e\\mod n$ ..." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "p = 1113954325148827987925490175477024844070922844843\n", "q = 1917481702524504439375786268230862180696934189293\n", "e = 3" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "n = p*q\n", "v = 1808808319415691415062465989446183136395423154715795462152356725976667671981921260211627443446049" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'0x10a000004972030440233370fff100006020600010a000004972030440233370fff1000060206'" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# On l'affiche en hexadécimal ...\n", "c = pow(v,e,n)\n", "hex(c)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et on voit bien quelque chose de louche :\n", "\n", "
\n",
    "10a00000 4972 0304 4023 3370 fff 10 0006 0206\n",
    "000\n",
    "10a00000 4972 0304 4023 3370 fff 10 0006 0206\n",
    "
\n", " (Et si on ne voit rien, la suite de l'énoncé explique ce qu'on aurait dû voir).\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "# On écrit un petite classe dont on aura besoin ensuite\n", "\n", "from ent3 import * # contient inversemod \n", "class RSA:\n", " def __init__(self,p,q,e):\n", " assert miller_rabin(p)\n", " assert miller_rabin(q)\n", " n = p*q\n", " m = (p-1)*(q-1)\n", " d = inversemod(e,m)\n", " self.n = n; self.e = e\n", " self.p = p; self.q = q; self.d =d\n", "\n", " def crypt(self,x):\n", " assert x.0.3.Ie5...6b..\n", "31 50 2a ab 33 b9 df 5e 37 fb 0d b7 3d 15 61 21 | 1P*.3..^7...=.a!\n", " (SW1,SW2) = (90, 0)\n", "# On supprime les 3 de redondance tous les 4 octets\n", "\n", "0 00 0d 8c 9 8e 8f b2 1 d8 43 c7 8 06 cd 6d\n", "e aa 30 d7 3 ab 49 65 5 15 ce af 6 62 ca 1c\n", "1 50 2a ab 3 b9 df 5e 7 fb 0d b7 d 15 61 21\n", "\n", "# Et on obtient la valeur d'authentification en hexadécimal:\n", "v=0x0000d8c98e8fb21d843c7806cd6deaa30d73ab4965515ceaf662ca1c1502aab3b9df5e7fb0db7d156121\n", "```\n", "On vérifie au passage que c'est bien le même $v$ que dans l'exercice 1 :" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1808808319415691415062465989446183136395423154715795462152356725976667671981921260211627443446049" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "0x0000d8c98e8fb21d843c7806cd6deaa30d73ab4965515ceaf662ca1c1502aab3b9df5e7fb0db7d156121" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On recopie les données situées après le code \"2E 02 38 F1\", on doit lire" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "56" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "0x38" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "56 octets, donc ..." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ " s='''30 04 97 20 33 04 40 23 | =#a!..8ñ0.— 3.@#\n", "33 37 0F FF 31 01 00 06 32 50 02 06 32 50 34 97 | 37.ÿ1...2P..2P4—\n", "35 44 84 94 32 4F 4E 2F 34 D4 F4 E4 39 51 55 45 | 5D„”2ON/4Ôôä9QUE\n", "32 02 02 02 30 20 20 20 32 02 02 02 30 20'''" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['30 04 97 20 33 04 40 23 ',\n", " '|',\n", " ' =#a!..8ñ0.\\x97 3.@#',\n", " '\\n',\n", " '33 37 0F FF 31 01 00 06 32 50 02 06 32 50 34 97 ',\n", " '|',\n", " ' 37.ÿ1...2P..2P4\\x97',\n", " '\\n',\n", " '35 44 84 94 32 4F 4E 2F 34 D4 F4 E4 39 51 55 45 ',\n", " '|',\n", " ' 5D\\x84\\x942ON/4Ôôä9QUE',\n", " '\\n',\n", " '32 02 02 02 30 20 20 20 32 02 02 02 30 20']" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# On peut nettoyer cette chaîne avec une expression régulière\n", "# (ou à la main)\n", "import re\n", "pat=r'(\\||\\n)'\n", "ll=re.split(pat,s)\n", "ll" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "['30 04 97 20 33 04 40 23 ',\n", " '33 37 0F FF 31 01 00 06 32 50 02 06 32 50 34 97 ',\n", " '35 44 84 94 32 4F 4E 2F 34 D4 F4 E4 39 51 55 45 ',\n", " '32 02 02 02 30 20 20 20 32 02 02 02 30 20']" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "mm=[ll[4*i] for i in range(len(ll)//4+1)]\n", "mm" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'30 04 97 20 33 04 40 23 33 37 0F FF 31 01 00 06 32 50 02 06 32 50 34 97 35 44 84 94 32 4F 4E 2F 34 D4 F4 E4 39 51 55 45 32 02 02 02 30 20 20 20 32 02 02 02 30 20'" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from functools import reduce\n", "t=reduce(lambda x,y:x+y,mm)\n", "t" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'300497203304402333370FFF31010006325002063250349735448494324F4E2F34D4F4E4395155453202020230202020320202023020'" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "t=t.replace(' ','')\n", "t" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "108" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(t) " ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "# On élimine les 3 de contrôle\n", "x = ''\n", "for i in range(len(t)//2):\n", " if i%4: x+=t[2*i:2*i+2]\n", " else: x+=t[2*i+1]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et on obtient enfin les données de la carte\n", "C'est un encodage bizarre oà les chiffres hexadécimaux 0-9 sont utilisés\n", "pour représenter le numéro de la carte, des dates ou d'autres codes, et où les caractères alphabétiques sont représentés par leurs codes ascii ..." ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'004972030440233370FFF101000625002062503497544849424F4E2F4D4F4E49515545202020202020202020202020'" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "b'\\x00Ir\\x03\\x04@#3p\\xff\\xf1\\x01\\x00\\x06%\\x00 bP4\\x97THIBON/MONIQUE '" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from codecs import *\n", "decode(x,'hex')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il faut donc couper après l'octet 0x97 et interpréter la suite en ASCII. Voilà la structure des données\n", "\n", "
\n",
    "00\n",
    "4972030440233370\n",
    "FFF\n",
    "101\n",
    "0006\n",
    "250\n",
    "0206\n",
    "250\n",
    "3\n",
    "497\n",
    "THIBON/MONIQUE\n",
    "(espaces)\n",
    "\n",
    "
\n", "
\n",
    "00                      # Identique sur toutes les cartes\n",
    "49**************        # Numéro de la carte\n",
    "FFF                     # Réservé futurs numéros\n",
    "101                     # Code usage (ou code service)\n",
    "aamm                    # Début de validité\n",
    "250                     # Code langue (250=français)\n",
    "aamm                    # Fin de validité\n",
    "250                     # Code devise (Franc)\n",
    "3                       # Exposant (5=unité, 3=centimes)\n",
    "497                     # ?? (identique sur toutes le cartes)\n",
    "*****************       # Nom du titulaire, en ASCII, sur 26 caractères\n",
    "202020202020202020202020# (des espaces)\n",
    "
\n", "\n", "\n", "Pour la fausse carte, il suffit donc de remplacer le nom, le numéro et les dates, puis de chiffrer les nouvelles données d'authentification avec la cléf privéee $d$.\n", "\n" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "42" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x = b'004972030440233370FFF101000625002062503497544849424F4E2F4D4F4E49515545202020202020202020202020'\n", "y = b'003141592653589793FFF101000025013132303497'\n", "len(y)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "28" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z = encode(b'MANSOIF/GERARD','hex')\n", "len(z)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "b'4d414e534f49462f474552415244'" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "z" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "b'003141592653589793FFF1010000250131323034974d414e534f49462f474552415244'" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "y+z" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "70" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(y+z)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "y=y+z+b'20'*12" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "94" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "len(y)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "b'003141592653589793FFF1010000250131323034974d414e534f49462f474552415244202020202020202020202020'" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "y" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "b'004972030440233370FFF101000625002062503497544849424F4E2F4D4F4E49515545202020202020202020202020'" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "b'300314153926535839793FFF31010000325013133230349734d414e5334f494632f47455324152443202020230202020320202023020'" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Il ne reste plus qu'à réinsérer les 3\n", "\n", "yy = b''.join([b'3'+y[7*i:7*i+7] for i in range(len(y)//7+1)])\n", "\n", "yy" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "108" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\n", "len(yy) #petit contrôle" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "## On fabrique la nouvelle valeur d'authentification en substitiuant \n", "## le nouveau numéro et les nouvelles dates (00/00 et 13/13)\n", "\n", "uu =int('''\n", "10a00000 3141 5926 5358 9793 fff 10 0000 1313\n", "000\n", "10a00000 3141 5926 5358 9793 fff 10 0000 1313\n", "'''.replace(' ','').replace('\\n',''),16)\n", "\n" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "33865723129921835612249160218012612201774316382006172730732123289398593691299921292272079635" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "uu" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [], "source": [ "rsa = RSA(p,q,e)" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "93737746716878564284840231240552282287015996007177936369954585285163900606293377642619339275449" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "vv = rsa.uncrypt(uu)\n", "vv" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'B3C0BC69935C2FB00E6A91054D4645971C50E0A8CBF69081F7D007207DB12912F49CFEEB1F7FCB9'" ] }, "execution_count": 31, "metadata": {}, "output_type": "execute_result" } ], "source": [ "w = '%X' %vv\n", "w" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'3B3C0BC639935C2F3B00E6A931054D46345971C530E0A8CB3F69081F37D0072037DB129132F49CFE3EB1F7FC3B9'" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "ww = ''.join(['3'+w[7*i:7*i+7] for i in range(len(w)//7+1)])\n", "ww" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et voilà ! Il n'y a plus qu'à écrire $ww$ et $yy$ aux adresses indiquées, et à programmer la carte pour qu'elle\n", "réponde `(0x90,0x00)` quelque soit la question posée ..." ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "850 18491463140934317381 36982926281868634763\n", "1869 5724817658511806303 11449635317023612607\n" ] } ], "source": [ "## Exercice 2\n", "\n", "from decimal import * # Multiprécision sur les flottants\n", "from ent3 import *\n", "\n", "getcontext().prec = 5000 # On trouve ça dans la doc\n", "e = Decimal(\"1.\").exp() # e = exp(1), et il connaît exp\n", "e = str(e)\n", "\n", "def s(i): # tranches de 20 chiffres consécutifs\n", " try:\n", " return int(e[2+i:2+i+20])\n", " except: return None\n", "\n", "\n", "def test_slice(n): # On teste q et p=2q+1 si q est impair\n", " if n%2 ==0: return False\n", " q = 2*n+1\n", " if miller_rabin(n):\n", " if miller_rabin(q): return True\n", " return False\n", "\n", "for i in range(len(e)-22):\n", " if test_slice(s(i)):\n", " print (i+2, s(i), 2*s(i)+1)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le premier est donc $q=18491463140934317381$, à la position 850 après la virgule." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Exercice 3\n", "\n", "On peut retrouver $y=x^3\\mod n_an_bn_c$ par le théorème des restes chinois. Comme $x<\\min(n_a,n_b,n_c)$ on peut le trouver en calculant la racine cubique de $y=x^3$ dans les réels.\n", "Pour utiliser `Decimal`, on calcule $y^{1/3} = \\exp(\\ln(y)/3).$" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "182604505278011806364889160347210631562705250523819775263426937816401785613989069256884639013849511605042503493462711546751975744\n", "5673318464228055404789402258300850215739763.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999920\n" ] } ], "source": [ "from codecs import encode, decode\n", "def s2i(s):\n", " return int(encode(s,'hex'),16)\n", "\n", "def i2s(m):\n", " t = '%x' % m \n", " if len(t)%2: t='0'+t\n", " return decode(t,'hex')\n", "\n", "from ent3 import *\n", "from functools import reduce\n", "def solve_chinese(yy,mm):\n", " assert len(yy) == len(mm), \"Arguments must have same length.\"\n", " k = len(yy); m = reduce(lambda x,y:x*y, mm); x=0\n", " for i in range(k):\n", " u = reduce(lambda x,y:x*y, [mm[j] for j in range(k) if j!=i])\n", " v = inversemod(u,mm[i])\n", " x = (x + yy[i]*v*u) % m\n", " return x\n", "\n", "\n", "e = 3\n", "\n", "na = 2135987035920910082395022704999628797051095341826417406442524165008583957746445088405009430865999\n", "nb = 2135987035920910082395022704999628797162490781344963051155377956280967195101981889839850702671619\n", "nc = 2135987035920910082395022704999628896193030374617175691844152549530769669304774519830221356585511\n", "\n", "ya = 1704530022978544318071261282029959269089776023381678967531907665026466268332863367550402288250742\n", "yb = 1704520499835949615592131996885727697345627882180875786884636832758759452639025264678208940201982\n", "yc = 1696054426594054895613006544606777272432734244621789015588464666648043681903785330811909500673766\n", "\n", "\n", "res = solve_chinese([ya,yb,yc],[na,nb,nc])\n", " \n", "from decimal import *\n", "getcontext().prec = 500\n", "z = Decimal(res)\n", "a = z.ln()/3\n", "b = a.exp()\n", "\n", "print (res)\n", "print (b)\n", "\n" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5673318464228055404789402258300850215739764" ] }, "execution_count": 35, "metadata": {}, "output_type": "execute_result" } ], "source": [ "int(str(b.to_integral_exact()))" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "b'A bon chat bon rat'" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "i2s(_)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "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.8.10" } }, "nbformat": 4, "nbformat_minor": 1 }