Practica 4 - RSA.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Codificación con llave pública RSA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from TANMLP import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sympy import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Los servicios de inteligencia han interceptado el siguiente WhatsApp, que ha sido enviado por el cabecilla de un grupo al que están investigando.\n",
    "\n",
    "<span style=\"color:blue\">\n",
    "Hola a todos,\n",
    "entrar en:\n",
    "$$963165702406078610933268087093959165865367524389470937341450164058799873046090241902268240522430399039842519010966073984353131388865535909155540264424417892621L$$\n",
    "</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sabemos, gracias a un infiltrado, al que llamaremos Pepe, para proteger su identidad, que ese número corresponde a la codificación (usando el protocolo RSA) de la dirección de una web. \n",
    "\n",
    "De las llaves públicas e y n que se han usado para codificar la dirección de la web. Pepe nos ha dicho que el módulo $n$ es \n",
    "$$\n",
    "10000000000000000000000000000000000000000000000000000000000000000000033000000000000000002890000000000000000000000000000000000000000000000000000000000000000009537L\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Del que además sabemos que es el producto de dos primos uno de ellos muy cercano a $10^{90}$. \n",
    "\n",
    "Acerca del exponente $e$, que se ha usado, solo sabemos que está entre $12334$ y $12345$. \n",
    "\n",
    "En esa web se habla de un famoso detective cuyo apellido ha sido usado como llave para codificar, siguiendo el procedimiento de Vigenère, una clave. La matriz de Vigenère que se ha usado se obtiene mediante una traslación de 6 lugares de las 26 letras del alfabeto (sin Ñ), de manera que en el lugar 1,1 aparece la letra G.\n",
    "\n",
    "Afortunadamente tenemos pinchado el WhatsApp del cabecilla e interceptamos este otro mensaje:\n",
    "\n",
    "<span style=\"color:blue\">\n",
    "Lo vamos a petar compañer@s\n",
    "os dejo las instrucciones donde siempre\n",
    "la clave para entrar es: SQNHYQQ\n",
    "</span>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pepe dice que esta banda ha pirateado la web de la asignatura TAN y Criptografía de cuarto curso de matemáticas de la UGR y que es en esta web donde dejan las instrucciones para cometer sus fechorías. Solo hay que introducir la clave correcta cuando se pulsa el botón etiquetado como \"este botón\" que aparece en esa web.\n",
    "\n",
    "Puede ser una cuestión de seguridad nacional saber que está tramando este peligroso grupo. ¿Podrías ayudar a nuestro servicio de inteligencia averiguando que traman?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cod_afin(mensaje,a,b,n):\n",
    "    hexalista=str_to_hexalist(mensaje)\n",
    "    declista=hexalist_to_dec(hexalista)\n",
    "    for i in range(0,len(declista)):\n",
    "        declista[i]=((declista[i]*a)+b)%n\n",
    "    return declista"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def deco_rsa(declista,e,p,q):\n",
    "    n=p*q\n",
    "    phi=(p-1)*(q-1)\n",
    "    u=gcdex(e,phi)[0]\n",
    "    u=u%phi\n",
    "    declista2=[]\n",
    "    for i in range(0,len(declista)):\n",
    "        declista[i]=pow(declista[i],int(u),n)\n",
    "    hexlista=declist_to_hex(declista)\n",
    "    mensaje=hexalist_to_str(hexlista)\n",
    "    return mensaje"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Con las pistas que tenemos vamos a intentar conseguir factorizar n para poder romper el cifrado, para ello usaremos la pista de que n es el producto de dos primos y que uno de ellos está próximo a $10^{90}$  Usaremos la función de python nextprime($10^{90}$). Y nos daremos cuenta de que ese primo divide a n y que el otro factor es también primo por lo que habremos factorizado n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "n=n=10000000000000000000000000000000000000000000000000000000000000000000033000000000000000002890000000000000000000000000000000000000000000000000000000000000000009537\n",
    "#Llamamos a al siguiente primo después del número 10^90\n",
    "a=nextprime(10**90)\n",
    "#Comprobamos que a divide a n\n",
    "print n%a\n",
    "#Calculamos b como el otro factor de n y comprobamos que es primo también\n",
    "b=n/a\n",
    "print isprime(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lo único que nos queda es saber el exponente $e$, pero como tenemos un rango de valores para este números, probaremos cada uno para ver cuáles dan errores y cuáles no. Y obtenemos que para $e=12337$ obtenemos la dirección web que mencionaba Pepe."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "https://es.wikipedia.org/wiki/Andrea_Camilleri\n"
     ]
    }
   ],
   "source": [
    "web=[963165702406078610933268087093959165865367524389470937341450164058799873046090241902268240522430399039842519010966073984353131388865535909155540264424417892621L]\n",
    "mensaje=deco_rsa(web,12337,a,b)\n",
    "print(mensaje)        \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En la página de wikipedia del escritor italiano encontramos que el famoso detective es el comisario Montalbano. Para ello hallaremos la clave decodificando 'SQNHYQQ' usando la codificación de Vigenere y obtenemos la clave: 'MIGUELV'.\n",
    "Vamos a la página de TAN y Criptografía y obtenemos una codificación con RSA."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Amig@s,\n",
    "Averiguar quien es el autor del siguiente pasaje y comunicarlo al profesor, él os dará las siguientes instrucciones.\n",
    "\n",
    "He codificado el texto usando RSA con exponente e=1211 y módulo n=100000000190000000000000130000000247L\n",
    "\n",
    "[62718023028666516652217553286447580L,7498947686663464945219055124624672L,5097532352808044988339897796965481L, 91589262635941722393701864307290432L,32253663039631038701991850668453454L,53773066331614972385019608760594210L, 44872556814103066346332116543585947L,927595488059769026187019360488764L,49395339185930770640825500218907604L, 82765863643386211968916760020252865L,25190253146559911376083367250316299L,81516543968865406348490251727544031L, 46973933837819443668504149601583430L,77960341753470006710619206199970261L,49395339185930770640825500218907604L, 79254408903157759140039430389457364L,32253663039631038701991850668453454L,69780185215451483837569951955699571L, 29181696113870199493001011506819598L,90746575521726863772619585452064895L,53321108584650112172697208811566958L, 89581607855380843846698601631339583L,4708233782086952953447867649890291L,81432953437104554702397572297116064L, 36748330705811761693354226961591564L,1738593413407962465957970386712872L,32253663039631038701991850668453454L, 6750255873197567500580868078789613L,3974641490716322416716012898882504L,69986814838734158265662071880367929L, 33080062031670887360059604610536909L,40912383938472947746699773999940668L,4708233782086952953447867649890291L, 60483336929846569313797889446933915L,50667049569681047447267330219362885L,16290171361242663103615946233640411L, 47438932232141836314849694319021353L,39517692056423301078064249847281553L,5059085049209552086870359812535240L, 62718023028666516652217553286447580L,34826601305744909271655808230506457L,32253663039631038701991850668453454L, 91586940261787857401151443814477655L,61306029703084185462695712502140576L,83961571813158583840345582468490739L, 53321108584650112172697208811566958L,16290171361242663103615946233640411L,33080062031670887360059604610536909L, 33769266318800097853303530008277240L,32253663039631038701991850668453454L,59548761183455377590539187724065107L, 40242014248379983165075976953067146L,39517692056423301078064249847281553L,29181696113870199493001011506819598L, 32435388911346208285687326957122563L,53321108584650112172697208811566958L,49395339185930770640825500218907604L, 20984102453995705653556910024287620L,23099420478417425445521464902274289L,32601348700812862397811686988230384L, 38217714717707056935821519501830833L,58757499046435065954253182867578106L,927595488059769026187019360488764L, 97463369160658535386970147458030133L,596227106103230803334107174826800L,81516543968865406348490251727544031L, 33080062031670887360059604610536909L,94139569715939059099802866251926914L,52678403584758883400564489432746954L, 32253663039631038701991850668453454L,44476434974326501460048387026732L,55680754582162596062709617863536289L, 62718023028666516652217553286447580L,3789955926090140936068306445042312L,32253663039631038701991850668453454L,66686506397057715816262021262989728L] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "e2=1211\n",
    "n2=100000000190000000000000130000000247\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "10000000019 10000000000000000000000013\n"
     ]
    }
   ],
   "source": [
    "print n2%nextprime(10**10)==0\n",
    "#El siguiente primo a 10^10 divide a nuestro n\n",
    "p=nextprime(10**10)\n",
    "q=n2/p\n",
    "#Hemos factorizado n como el producto de dos primos\n",
    "print isprime(q)\n",
    "print p,q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hemos conseguido factorizar el n2 en dos primos por lo que ya tenemos las llaves privadas y sólo nos queda decodificar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "To be, or not to be: that is the question: Whether ‘tis nobler in the mind to suffer The slings and arrows of outrageous fortune, Or to take arms against a sea of troubles, And by opposing end them? To die: to sleep; No more; and by a sleep to say we end The heart-ache and the thousand natural shocks That flesh is heir to, ‘tis a consummation Devoutly to be wish’d. To die, to sleep.\n"
     ]
    }
   ],
   "source": [
    "mensaje=mensaje=[62718023028666516652217553286447580L,7498947686663464945219055124624672L,5097532352808044988339897796965481L, 91589262635941722393701864307290432L,32253663039631038701991850668453454L,53773066331614972385019608760594210L, 44872556814103066346332116543585947L,927595488059769026187019360488764L,49395339185930770640825500218907604L, 82765863643386211968916760020252865L,25190253146559911376083367250316299L,81516543968865406348490251727544031L, 46973933837819443668504149601583430L,77960341753470006710619206199970261L,49395339185930770640825500218907604L, 79254408903157759140039430389457364L,32253663039631038701991850668453454L,69780185215451483837569951955699571L, 29181696113870199493001011506819598L,90746575521726863772619585452064895L,53321108584650112172697208811566958L, 89581607855380843846698601631339583L,4708233782086952953447867649890291L,81432953437104554702397572297116064L, 36748330705811761693354226961591564L,1738593413407962465957970386712872L,32253663039631038701991850668453454L, 6750255873197567500580868078789613L,3974641490716322416716012898882504L,69986814838734158265662071880367929L, 33080062031670887360059604610536909L,40912383938472947746699773999940668L,4708233782086952953447867649890291L, 60483336929846569313797889446933915L,50667049569681047447267330219362885L,16290171361242663103615946233640411L, 47438932232141836314849694319021353L,39517692056423301078064249847281553L,5059085049209552086870359812535240L, 62718023028666516652217553286447580L,34826601305744909271655808230506457L,32253663039631038701991850668453454L, 91586940261787857401151443814477655L,61306029703084185462695712502140576L,83961571813158583840345582468490739L, 53321108584650112172697208811566958L,16290171361242663103615946233640411L,33080062031670887360059604610536909L, 33769266318800097853303530008277240L,32253663039631038701991850668453454L,59548761183455377590539187724065107L, 40242014248379983165075976953067146L,39517692056423301078064249847281553L,29181696113870199493001011506819598L, 32435388911346208285687326957122563L,53321108584650112172697208811566958L,49395339185930770640825500218907604L, 20984102453995705653556910024287620L,23099420478417425445521464902274289L,32601348700812862397811686988230384L, 38217714717707056935821519501830833L,58757499046435065954253182867578106L,927595488059769026187019360488764L, 97463369160658535386970147458030133L,596227106103230803334107174826800L,81516543968865406348490251727544031L, 33080062031670887360059604610536909L,94139569715939059099802866251926914L,52678403584758883400564489432746954L, 32253663039631038701991850668453454L,44476434974326501460048387026732L,55680754582162596062709617863536289L, 62718023028666516652217553286447580L,3789955926090140936068306445042312L,32253663039631038701991850668453454L,66686506397057715816262021262989728L] \n",
    "mensaje_decodificado=deco_rsa(mensaje,e2,p,q)\n",
    "print mensaje_decodificado"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El autor de este fragmento es William Shakespeare de su célebre obra 'Hamlet'."
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}