{
 "metadata": {
  "name": "",
  "signature": "sha256:535e7f351416c3d4b0e1c5675843c67a5da3d9cf6fd8c88c10c10a0456f8b6c5"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# this is the probelm we need to solve\n",
      "import random\n",
      "import select\n",
      "import signal\n",
      "import sympy\n",
      "import sys\n",
      "\n",
      "\n",
      "class Unbuffered(object):\n",
      "    def __init__(self, stream):\n",
      "        self.stream = stream\n",
      "\n",
      "    def write(self, data):\n",
      "        self.stream.write(data)\n",
      "        self.stream.flush()\n",
      "\n",
      "    def __getattr__(self, attr):\n",
      "        return getattr(self.stream, attr)\n",
      "\n",
      "\n",
      "def random_prime(bits):\n",
      "    return sympy.nextprime(2 ** bits + random.randint(0, 2 ** bits))\n",
      "\n",
      "\n",
      "def encrypt(bits, m):\n",
      "    p = random_prime(bits)\n",
      "    q = random_prime(bits)\n",
      "    n = p * q\n",
      "    assert m < n\n",
      "    print n\n",
      "    print m ** 3 % n\n",
      "    print (m + 1) ** 3 % n\n",
      "\n",
      "\n",
      "def main():\n",
      "    signal.alarm(180)\n",
      "    sys.stdout = Unbuffered(sys.stdout)\n",
      "    for i in range(1, 10):\n",
      "        bits = 50 * i\n",
      "        m = random.randint(0, 4 ** bits)\n",
      "        encrypt(bits, m)\n",
      "        rfd, _, _ = select.select([sys.stdin], [], [], 10)\n",
      "        if rfd:\n",
      "            try:\n",
      "                x = int(raw_input())\n",
      "            except ValueError:\n",
      "                print \"\\033[31;1mEnter a number, ok?\\033[0m\"\n",
      "                exit()\n",
      "            if x == m:\n",
      "                print \"\\033[32;1mGreat:)\\033[0m\"\n",
      "                continue\n",
      "            else:\n",
      "                print \"\\033[31;1mso sad :(\\033[0m\"\n",
      "                exit()\n",
      "        else:\n",
      "            print \"\\033[31;1mToo slooooooooooow :(\\033[0m\"\n",
      "            exit()\n",
      "\n",
      "    bits = 512.512\n",
      "    m = int(open('flag').read().encode('hex'), 16)\n",
      "    encrypt(bits, m)\n",
      "    print \"\\033[32;1mGood Luck!\\033[0m\"\n",
      "\n",
      "main()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from gmpy2 import mpz, divm\n",
      "from sympy import *"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# suppose m**3 =c and (m+1) ** 3  =d\n",
      "x, c,d = symbols('x,c,d')\n",
      "f1 = x**3-c\n",
      "f2 =  (x+1)**3-d"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# finding gcd of  f1, f2\n",
      "\n",
      "q,r = div(f1, f2)\n",
      "print r\n",
      "q2, r2=div( (x+1)**3-d, r)\n",
      "# m is the root of linear equation r2\n",
      "r2= Poly(3*r2, x)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Given\n",
      "n = 2346958776283104186640235260573\n",
      "c = 1085431292732484513462488498356\n",
      "d =2179163442056091844263758576965\n",
      "# so, we can compute  m as following\n",
      "# The formulat is simply:  -r2.all_coeffs()[0]/-r2.all_coeffs()[1] mod n\n",
      "m=divm(2*c  + d  - 1, d-c+2, n)\n",
      "pow(m, 3, n) == c and  pow(m+1, 3, n) == d"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# now doing this automatically\n",
      "import telnetlib\n",
      "tel = telnetlib.Telnet(\"54.64.40.172\", 5454)\n",
      "for i in range(1, 10):    \n",
      "    n = mpz(tel.read_until('\\n').strip())\n",
      "    c = mpz(tel.read_until('\\n').strip())\n",
      "    d = mpz(tel.read_until('\\n').strip())\n",
      "    m = divm(2*c  + d  - 1, d-c+2, n)\n",
      "    tel.write('%d\\n'%m)\n",
      "    ans = tel.read_until('\\n')\n",
      "    print i, ans\n",
      "n = mpz(tel.read_until('\\n').strip())\n",
      "c = mpz(tel.read_until('\\n').strip())\n",
      "d = mpz(tel.read_until('\\n').strip())\n",
      "m = divm(2*c  + d  - 1, d-c+2, n)\n",
      "ans = tel.read_until('\\n')\n",
      "print ans, n,c,d\n",
      "print m"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# get our flag\n",
      "print (\"%x\"%m).decode('hex')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}