day 52 - RSA.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def secure_prime_generator():\n",
    "    yield from [\n",
    "        251352642263889039868309043894037481379002996715589396370854987834622532561522720403074015628816522584866374785754812790090831773387112312703220610291993961566100333483106513061700679351674883108504663868999773335993131871433147375498526830250690800432950741107471775936506033522777378528889986463928680062779,\n",
    "        234601306906702217804957533486106543816960131695391266497422573355527800260716665381597389816091857137372406177664905766000014102540204528163683625043444669386812465309478832002368041295429725611772236019022712629169757194963880836723186721316763532024657471001347998077008043814690024358601642733925216784203,\n",
    "    ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def modinv(x, y):\n",
    "    r, s = 1, 0\n",
    "    while y:\n",
    "        r, s = s, r - x // y * s\n",
    "        x, y = y, x % y\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rsa_generate_keys():\n",
    "    p, q = secure_prime_generator()\n",
    "    n = p * q\n",
    "    t = n - p - q + 1\n",
    "    e = 65537\n",
    "    d = modinv(e, t) % t\n",
    "    assert (d * e) % t == 1\n",
    "    return (e, n), (d, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def rsa(plaintext, public_key):\n",
    "    return pow(plaintext, *public_key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## keys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "public_key, secret_key = rsa_generate_keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(65537,\n",
       " 58967658369561163583995664151705537612631456941226585145001736155445085885436956133402962616775555500479429922140321605063456075222335023020218578571558003435174909963319619244821157746252197885628802071763470174413201522569356053296685834595362968800778468737693074613267684084217204017873750446802044584084498581219849973790017343888256411013653688556278788070745635045095995056877259642839730825907965544973672656542601570609068817838234644958846427643088478240335082249677864789882511592486797239674160452077169411971273434857626735582274817190984442183721945999865859466422472845277588368259261760233826535480137)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "public_key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(32639742054323523661031580828650534544392003478949839063736255562124081596351847364013089886417596950354636310108218358259943735367279937975211699593540109138569129405212055903155962561652878992005591100527818545966603574053221236696683939389678915058929150433015761702105657992264877747720954135956649973789334911071168428227464085150820871588160770978551544646965210798269197906675922224772713666123225990305644372957419486169245295190574189157389340237417783311258488777336686103120891002317113842264416737708675921812070527474901946450952078789439410581693777829144977217172397092723130874770379072485175449578961,\n",
       " 58967658369561163583995664151705537612631456941226585145001736155445085885436956133402962616775555500479429922140321605063456075222335023020218578571558003435174909963319619244821157746252197885628802071763470174413201522569356053296685834595362968800778468737693074613267684084217204017873750446802044584084498581219849973790017343888256411013653688556278788070745635045095995056877259642839730825907965544973672656542601570609068817838234644958846427643088478240335082249677864789882511592486797239674160452077169411971273434857626735582274817190984442183721945999865859466422472845277588368259261760233826535480137)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "secret_key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## encryption"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "37930332066974779164345751815395228520383070918149654734779452314315201401578073995623676191126275180229634519536130536469650873769044314422167044966349923400485329143076986636753828936028839818231151694765870620828795561931693647118671097571595175457792224986081168799650305451662018565631898905521228230362451756374795462396041777695041246353088986331124068828091083876264418231632281088387993565061643784457276421962040835851861587580705505405821148340529587678730109599751672134343435130195273271395130139199246695649453457192908607858557747694289049617690930150092441884659797085102908069133974365162807747676330"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ciphertext = rsa(0xfacade17, public_key)\n",
    "ciphertext"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0xfacade17'"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plaintext = rsa(ciphertext, secret_key)\n",
    "hex(plaintext)"
   ]
  },
  {
   "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}