HITCON CTF 2019 Quals - Lost Key Again (crypto)

lost_key_again.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HITCON CTF 2019 Quals - Lost Key Again (crypto)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The challenge has the following code:\n",
    "\n",
    "```py\n",
    "def read_key():\n",
    "    key_file = open(\"key\")\n",
    "    n,e,d = map(int,key_file.readlines()[:3])\n",
    "    return n,e,d\n",
    "\n",
    "def calc(n,p,input):\n",
    "    data = \"X: \"+input\n",
    "    num = bytes_to_long(data)\n",
    "    res = pow(num,p,n)\n",
    "    return long_to_bytes(res).encode('hex')\n",
    "\n",
    "def read_flag():\n",
    "    flag = open('flag').read()\n",
    "    assert len(flag) >= 50\n",
    "    assert len(flag) <= 60\n",
    "    prefix = os.urandom(68)\n",
    "    return prefix+flag\n",
    "\n",
    "n,e,d = read_key()\n",
    "flag =  calc(n,e,read_flag())\n",
    "print 'Here is the flag!', flag\n",
    "for i in xrange(100):\n",
    "    m = raw_input('give me your X value: ')\n",
    "    try:\n",
    "        m = m.decode('hex')[:15]\n",
    "        print calc(n,e,m)\n",
    "    except:\n",
    "        print 'no'\n",
    "        exit(0)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can encrypt messages of length up to 15 bytes, prepended by $T=$ \"X: \"=0x583a20.\n",
    "The challenge only provides encryption oracle, therefore knowing $e$ and $n$ should allow to decrypt, i.e. they must be weak in some way. This already hints about some guessing, but first we need to recover $n$ and/or $e$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Typically, to recover the modulus, when $e$ is unknown, we use multiplicativity of RSA:\n",
    "\n",
    "$$ a^e \\times b^e \\equiv (a \\times b)^e \\pmod{n}.$$\n",
    "\n",
    "If we compute the values on the left and on the right, they will differ by a multiple of $n$. After collecting a few of them, we recover $n$ using the GCD.\n",
    "\n",
    "Here, due to restrictions (3-byte padding and small size), we can not find values $a,b$ such that $a,b,ab$ all have correct padding \"X: \".\n",
    "\n",
    "However, the key is to notice that we are not required to obtain **one** enc() on the righthand side: we can use any nontrivial relations. Let's find some!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let $pad_t(x) := 256^tT + x$. We want to find relations of the form\n",
    "\n",
    "$$\n",
    "pad_{t_1}(x_1)^{e_1} pad_{t_2}(x_2)^{e_2} \\ldots = pad_{t_1'}(x_1')^{e_1'} pad_{t_2'}(x_2')^{e_2'} \\ldots,\n",
    "$$\n",
    "\n",
    "where all $t_i$ should be at most 15, all $x_i \\le 256^{t_i}$, and all $e_i$ must be small (since we will compute the expressions on both sides in integers). How can we find them? Let's map the problem to a linear one!\n",
    "\n",
    "One approach is to consider *logarithms*: taking logarithm of the equation leads to a linear equation. However, logarithms in real numbers have precision issues, which are hard to tackle with. Instead, we can make logarithms base each prime to produce a vector of integers. Equivalently, we obtain multiple linear equations. \n",
    "\n",
    "This approach is similar to the index calculus method and some sieving methods. First, we choose a factor base $B$ made of small primes up to a chosen limit and look for values that split completely in $B$ and have correct padding $pad_t$. Note that this is doable only because we can choose *small* numbers $pad_t(x)$, which have high chance to split in a small factor base."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-12T13:43:30.558144Z",
     "start_time": "2019-10-12T13:43:30.547188Z"
    }
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function, division\n",
    "from sage.all import *\n",
    "from Crypto.Util.number import *\n",
    "from sock import Sock\n",
    "class Stop(Exception): _render_traceback_ = lambda self: None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-10-12T13:43:30.558144Z",
     "start_time": "2019-10-12T13:43:30.547188Z"
    }
   },
   "outputs": [],
   "source": [
    "T = 0x583a20 # \"X: \""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Experimentally, we can find that all 53 primes below 250 make a good factorbase. Our goal is to find $53 + \\epsilon$ messages that split in $B$, where $\\epsilon$ is the minimum kernel dimension that we would like. The larger the kernel is, the more relations will be there, and higher chance to find small ones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# factorbase\n",
    "B = set(primes(250))\n",
    "# number of required relations\n",
    "# more extra -> larger kernel -> smaller relations!\n",
    "N = len(B) + 50\n",
    "\n",
    "def facb(v):\n",
    "    res = []\n",
    "    for p in B:\n",
    "        e = 0\n",
    "        while v % p == 0:\n",
    "            e += 1\n",
    "            v //= p\n",
    "        res.append((p, e))\n",
    "    if v == 1: return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  1-th/103 B-smooth number: t= 1 x=     16 factors: 2^4 * 41 * 109 * 127 * 163\n",
      "  2-th/103 B-smooth number: t= 1 x=     60 factors: 2^2 * 7^2 * 17 * 19 * 103 * 227\n",
      "  3-th/103 B-smooth number: t= 1 x=    179 factors: 3^2 * 7 * 17 * 61 * 139 * 163\n",
      "  4-th/103 B-smooth number: t= 2 x=   2128 factors: 2^4 * 11 * 31 * 41 * 67 * 131 * 193\n",
      "  5-th/103 B-smooth number: t= 2 x=   3551 factors: 3^4 * 7^2 * 61 * 83 * 109 * 173\n",
      "  6-th/103 B-smooth number: t= 2 x=   4096 factors: 2^12 * 41 * 109 * 127 * 163\n",
      "  7-th/103 B-smooth number: t= 2 x=   5216 factors: 2^5 * 3^2 * 13^3 * 29 * 107 * 193\n",
      "  8-th/103 B-smooth number: t= 2 x=   7738 factors: 2 * 11^2 * 13 * 47 * 103 * 139 * 179\n",
      "  9-th/103 B-smooth number: t= 2 x=   8222 factors: 2 * 3^3 * 5^2 * 11^3 * 23 * 53 * 173\n",
      " 10-th/103 B-smooth number: t= 2 x=   9522 factors: 2 * 5^3 * 7 * 71 * 113 * 137 * 197\n",
      " 11-th/103 B-smooth number: t= 2 x=  14342 factors: 2 * 3^2 * 5 * 13^2 * 31 * 73 * 101 * 109\n",
      " 12-th/103 B-smooth number: t= 2 x=  15059 factors: 3 * 7 * 53 * 67 * 113 * 193 * 233\n",
      " 13-th/103 B-smooth number: t= 2 x=  15360 factors: 2^10 * 7^2 * 17 * 19 * 103 * 227\n",
      " 14-th/103 B-smooth number: t= 2 x=  18496 factors: 2^6 * 7^2 * 11 * 31 * 37 * 61 * 157\n",
      " 15-th/103 B-smooth number: t= 2 x=  19112 factors: 2^3 * 3^2 * 5 * 7 * 11^2 * 47 * 137 * 193\n",
      " 16-th/103 B-smooth number: t= 2 x=  19882 factors: 2 * 5 * 7 * 11 * 17^2 * 19^2 * 53 * 89\n",
      " 17-th/103 B-smooth number: t= 2 x=  23195 factors: 3 * 13 * 23^3 * 37 * 113 * 191\n",
      " 18-th/103 B-smooth number: t= 2 x=  24212 factors: 2^2 * 3 * 5 * 43^2 * 113 * 167 * 181\n",
      " 19-th/103 B-smooth number: t= 2 x=  26060 factors: 2^2 * 3^2 * 31 * 61 * 151 * 191 * 193\n",
      " 20-th/103 B-smooth number: t= 2 x=  29687 factors: 3^3 * 5 * 31 * 47 * 53 * 163 * 223\n",
      " 21-th/103 B-smooth number: t= 2 x=  29888 factors: 2^6 * 3 * 23 * 43 * 59 * 149 * 227\n",
      " 22-th/103 B-smooth number: t= 2 x=  30256 factors: 2^4 * 7^2 * 19 * 23 * 73 * 109 * 139\n",
      " 23-th/103 B-smooth number: t= 2 x=  31187 factors: 3 * 5 * 7^2 * 17 * 19 * 37 * 179 * 241\n",
      " 24-th/103 B-smooth number: t= 2 x=  35766 factors: 2 * 11 * 13 * 19^2 * 97 * 157 * 241\n",
      " 25-th/103 B-smooth number: t= 2 x=  36032 factors: 2^6 * 3^6 * 5 * 17 * 19 * 47 * 107\n",
      " 26-th/103 B-smooth number: t= 2 x=  42800 factors: 2^4 * 3^2 * 7^2 * 29 * 31^2 * 41 * 47\n",
      " 27-th/103 B-smooth number: t= 2 x=  44753 factors: 3^3 * 7 * 11 * 17 * 19 * 31 * 109 * 167\n",
      " 28-th/103 B-smooth number: t= 2 x=  45824 factors: 2^8 * 3^2 * 7 * 17 * 61 * 139 * 163\n",
      " 29-th/103 B-smooth number: t= 2 x=  46048 factors: 2^5 * 7 * 29^2 * 89 * 97 * 233\n",
      " 30-th/103 B-smooth number: t= 2 x=  49637 factors: 3 * 5 * 11 * 13 * 71 * 97 * 113 * 227\n",
      " 31-th/103 B-smooth number: t= 2 x=  50612 factors: 2^2 * 3^7 * 5 * 7 * 13 * 31 * 37 * 83\n",
      " 32-th/103 B-smooth number: t= 2 x=  51536 factors: 2^4 * 3 * 7 * 17 * 19 * 79 * 193 * 229\n",
      " 33-th/103 B-smooth number: t= 2 x=  51947 factors: 3 * 5^2 * 11 * 43^3 * 53 * 109\n",
      " 34-th/103 B-smooth number: t= 2 x=  52106 factors: 2 * 3^2 * 19 * 23 * 47 * 53 * 83 * 233\n",
      " 35-th/103 B-smooth number: t= 2 x=  55393 factors: 7^5 * 19 * 67 * 89 * 199\n",
      " 36-th/103 B-smooth number: t= 2 x=  56039 factors: 3^4 * 11 * 19 * 23 * 79 * 97 * 127\n",
      " 37-th/103 B-smooth number: t= 2 x=  60284 factors: 2^2 * 3 * 13 * 31 * 47 * 67 * 149 * 167\n",
      " 38-th/103 B-smooth number: t= 2 x=  62519 factors: 3^5 * 7 * 101 * 113 * 131 * 149\n",
      " 39-th/103 B-smooth number: t= 2 x=  62897 factors: 3^3 * 5^4 * 7 * 13 * 29 * 67 * 127\n",
      " 40-th/103 B-smooth number: t= 2 x=  65144 factors: 2^3 * 3 * 7^2 * 53 * 137 * 199 * 223\n",
      " 41-th/103 B-smooth number: t= 3 x=   3732 factors: 2^2 * 5^2 * 7^3 * 13 * 17 * 29 * 41 * 47 * 229\n",
      " 42-th/103 B-smooth number: t= 3 x=  12062 factors: 2 * 3^5 * 5 * 7^2 * 17^2 * 23^2 * 73^2\n",
      " 43-th/103 B-smooth number: t= 3 x=  47230 factors: 2 * 7 * 13 * 19 * 89 * 107 * 113 * 131 * 199\n",
      " 44-th/103 B-smooth number: t= 3 x=  92327 factors: 3 * 5 * 11 * 13 * 29 * 37 * 47 * 61^2 * 241\n",
      " 45-th/103 B-smooth number: t= 3 x= 118496 factors: 2^5 * 3^5 * 11^2 * 13^2 * 61 * 73 * 137\n",
      " 46-th/103 B-smooth number: t= 3 x= 135227 factors: 3^2 * 5 * 7 * 11 * 13^2 * 17 * 23 * 31 * 79 * 173\n",
      " 47-th/103 B-smooth number: t= 3 x= 148773 factors: 13 * 97 * 101 * 107 * 137 * 223 * 233\n",
      " 48-th/103 B-smooth number: t= 3 x= 167357 factors: 3^2 * 5^2 * 7 * 17 * 61 * 67^2 * 101 * 131\n",
      " 49-th/103 B-smooth number: t= 3 x= 226307 factors: 3^4 * 5^2 * 11^2 * 23^2 * 29 * 131 * 197\n",
      " 50-th/103 B-smooth number: t= 3 x= 247850 factors: 2 * 3 * 7^2 * 31 * 47 * 71 * 103 * 173 * 179\n",
      " 51-th/103 B-smooth number: t= 3 x= 253436 factors: 2^2 * 3 * 7^3 * 13 * 43 * 53 * 59 * 97 * 139\n",
      " 52-th/103 B-smooth number: t= 3 x= 289264 factors: 2^4 * 13 * 17 * 53 * 101 * 107 * 211 * 227\n",
      " 53-th/103 B-smooth number: t= 3 x= 296982 factors: 2 * 5^2 * 11 * 17 * 61^2 * 71 * 173 * 227\n",
      " 54-th/103 B-smooth number: t= 3 x= 334844 factors: 2^2 * 3 * 11^2 * 23 * 53^3 * 109 * 179\n",
      " 55-th/103 B-smooth number: t= 3 x= 348687 factors: 5 * 13 * 29 * 103^2 * 109 * 191 * 233\n",
      " 56-th/103 B-smooth number: t= 3 x= 405532 factors: 2^2 * 5^2 * 7^2 * 19 * 37 * 41 * 73 * 97^2\n",
      " 57-th/103 B-smooth number: t= 3 x= 500696 factors: 2^3 * 3 * 13 * 37^2 * 83 * 107^2 * 239\n",
      " 58-th/103 B-smooth number: t= 3 x= 502308 factors: 2^2 * 11^3 * 13 * 17 * 47 * 61 * 149 * 193\n",
      " 59-th/103 B-smooth number: t= 3 x= 529907 factors: 3 * 5^2 * 11 * 13 * 23 * 107 * 137 * 139 * 193\n",
      " 60-th/103 B-smooth number: t= 3 x= 530856 factors: 2^3 * 13^2 * 19 * 61 * 71 * 89 * 97 * 101\n",
      " 61-th/103 B-smooth number: t= 3 x= 544768 factors: 2^12 * 11 * 31 * 41 * 67 * 131 * 193\n",
      " 62-th/103 B-smooth number: t= 3 x= 578000 factors: 2^4 * 3^2 * 23 * 31^2 * 43 * 67 * 71 * 149\n",
      " 63-th/103 B-smooth number: t= 3 x= 630007 factors: 5^3 * 11 * 13 * 41 * 47 * 73 * 173 * 223\n",
      " 64-th/103 B-smooth number: t= 3 x= 642184 factors: 2^3 * 11^2 * 17 * 37 * 41 * 71 * 229 * 239\n",
      " 65-th/103 B-smooth number: t= 3 x= 662930 factors: 2 * 3 * 11 * 41 * 73 * 131 * 139 * 149 * 181\n",
      " 66-th/103 B-smooth number: t= 3 x= 674328 factors: 2^3 * 29 * 41 * 47 * 61 * 139 * 157 * 163\n",
      " 67-th/103 B-smooth number: t= 3 x= 674876 factors: 2^2 * 3^2 * 11 * 19 * 23 * 79 * 181 * 197 * 199\n",
      " 68-th/103 B-smooth number: t= 3 x= 720337 factors: 5 * 89 * 137 * 139 * 211 * 227 * 239\n",
      " 69-th/103 B-smooth number: t= 3 x= 736417 factors: 5 * 19 * 29 * 79 * 107 * 113 * 191 * 193\n",
      " 70-th/103 B-smooth number: t= 3 x= 793144 factors: 2^3 * 13^2 * 17 * 37 * 47 * 97 * 131 * 191\n",
      " 71-th/103 B-smooth number: t= 3 x= 841240 factors: 2^3 * 7^2 * 11 * 19 * 163 * 173 * 199 * 211\n",
      " 72-th/103 B-smooth number: t= 3 x= 844166 factors: 2 * 3^2 * 7 * 11 * 19 * 31 * 97 * 107^3\n",
      " 73-th/103 B-smooth number: t= 3 x= 909056 factors: 2^8 * 3^4 * 7^2 * 61 * 83 * 109 * 173\n",
      " 74-th/103 B-smooth number: t= 3 x=1004870 factors: 2 * 3^2 * 29 * 31 * 41 * 53 * 89 * 139 * 223\n",
      " 75-th/103 B-smooth number: t= 3 x=1033607 factors: 3^3 * 5^2 * 7 * 23 * 31 * 37 * 71 * 97 * 113\n",
      " 76-th/103 B-smooth number: t= 3 x=1048576 factors: 2^20 * 41 * 109 * 127 * 163\n",
      " 77-th/103 B-smooth number: t= 3 x=1081632 factors: 2^5 * 5^5 * 113 * 179 * 199 * 241\n",
      " 78-th/103 B-smooth number: t= 3 x=1081991 factors: 3^6 * 7 * 13 * 17 * 41 * 61 * 163 * 211\n",
      " 79-th/103 B-smooth number: t= 3 x=1108199 factors: 3^2 * 7 * 11 * 13 * 37 * 89 * 109 * 131 * 229\n",
      " 80-th/103 B-smooth number: t= 3 x=1111880 factors: 2^3 * 3^8 * 29 * 41 * 73 * 107 * 199\n",
      " 81-th/103 B-smooth number: t= 3 x=1190435 factors: 3 * 7 * 11^3 * 47^2 * 89 * 127 * 139\n",
      " 82-th/103 B-smooth number: t= 3 x=1262921 factors: 3 * 157 * 163 * 167 * 193 * 197 * 199\n",
      " 83-th/103 B-smooth number: t= 3 x=1280964 factors: 2^2 * 41 * 43 * 67 * 79 * 109 * 113 * 211\n",
      " 84-th/103 B-smooth number: t= 3 x=1335296 factors: 2^13 * 3^2 * 13^3 * 29 * 107 * 193\n",
      " 85-th/103 B-smooth number: t= 3 x=1341632 factors: 2^6 * 3^2 * 5^4 * 17 * 37 * 53 * 59 * 137\n",
      " 86-th/103 B-smooth number: t= 3 x=1352359 factors: 7^2 * 17 * 19^2 * 83 * 109 * 181 * 197\n",
      " 87-th/103 B-smooth number: t= 3 x=1366210 factors: 2 * 13 * 19 * 23 * 29 * 89 * 149^3\n",
      " 88-th/103 B-smooth number: t= 3 x=1407564 factors: 2^2 * 11 * 23^2 * 29 * 53 * 71 * 181 * 211\n",
      " 89-th/103 B-smooth number: t= 3 x=1412228 factors: 2^2 * 3^6 * 11^2 * 19 * 37 * 47 * 53 * 157\n",
      " 90-th/103 B-smooth number: t= 3 x=1424320 factors: 2^6 * 13 * 17 * 71 * 73 * 83 * 107 * 149\n",
      " 91-th/103 B-smooth number: t= 3 x=1431275 factors: 3 * 13 * 31 * 107 * 109 * 181 * 191 * 199\n",
      " 92-th/103 B-smooth number: t= 3 x=1468832 factors: 2^5 * 3 * 5^2 * 7^2 * 13 * 53 * 67 * 107 * 167\n",
      " 93-th/103 B-smooth number: t= 3 x=1518636 factors: 2^2 * 17 * 47 * 73 * 101 * 137 * 151 * 199\n",
      " 94-th/103 B-smooth number: t= 3 x=1530920 factors: 2^3 * 3^3 * 13 * 79 * 113 * 157^3\n",
      " 95-th/103 B-smooth number: t= 3 x=1629907 factors: 5^2 * 11^2 * 29 * 79 * 241^3\n",
      " 96-th/103 B-smooth number: t= 3 x=1646382 factors: 2 * 5^3 * 47 * 53 * 67 * 89 * 151 * 173\n",
      " 97-th/103 B-smooth number: t= 3 x=1684132 factors: 2^2 * 5^4 * 43 * 137 * 151 * 181 * 241\n",
      " 98-th/103 B-smooth number: t= 3 x=1728280 factors: 2^3 * 7 * 11^2 * 17 * 127 * 149 * 191 * 233\n",
      " 99-th/103 B-smooth number: t= 3 x=1771841 factors: 3^3 * 7 * 19^3 * 31 * 83 * 127 * 229\n",
      "100-th/103 B-smooth number: t= 3 x=1817859 factors: 7^4 * 19 * 37 * 41^2 * 179 * 191\n",
      "101-th/103 B-smooth number: t= 3 x=1837964 factors: 2^2 * 3^7 * 17^2 * 31 * 61 * 103 * 197\n",
      "102-th/103 B-smooth number: t= 3 x=1897317 factors: 5 * 11^2 * 19 * 41 * 61 * 127 * 163^2\n",
      "103-th/103 B-smooth number: t= 3 x=1942904 factors: 2^3 * 3^2 * 29 * 71 * 83 * 173 * 199 * 229\n",
      "Done 103\n"
     ]
    }
   ],
   "source": [
    "sources = []\n",
    "vecs = []\n",
    "for t in range(1, 100):\n",
    "    if len(sources) >= N: break\n",
    "    for x in range(0, 256**t-1):\n",
    "        if len(sources) >= N: break\n",
    "        v = 256**t * T + x\n",
    "        fac = facb(v)\n",
    "        if fac:\n",
    "            ps = {p for p, e in fac}\n",
    "            vecs.append([e for p, e in fac])\n",
    "            sources.append((t, x))\n",
    "            print(\"%3d-th/%d B-smooth number: t=%2d x=%7d factors: %r\" % (len(sources), N, t, x, factor(v)))\n",
    "print(\"Done\", len(sources))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In a few seconds we have found 103 $B$-smooth messages! We are looking for *relations* between them, let's look at the kernel. Furthermore, we are interested in *small* relations, since we will compute the corresponding values in integers. Let's apply LLL to the kernel first:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ml = matrix(ZZ, vecs).left_kernel().matrix().LLL()\n",
    "ml[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wow, a very small relation indeed! What does it correspond to?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pad(t=2,x=2128)^-1 *\n",
      "pad(t=2,x=3551)^1 *\n",
      "pad(t=3,x=544768)^1 *\n",
      "pad(t=3,x=909056)^-1 *\n",
      "= 1\n"
     ]
    }
   ],
   "source": [
    "p = 1\n",
    "for i, c in enumerate(ml[0]):\n",
    "    if c:\n",
    "        t, x = sources[i]\n",
    "        p *= (256**t*T + x)**c\n",
    "        print(\"pad(t=%d,x=%d)^%d *\" % (t, x, c))\n",
    "print(\"= %d\" % p)        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ouch, fractions? We can not invert since we don't know $n$... But we don't need to! We simply move the negative power to the righthand side and get the relation that we want:\n",
    "\n",
    "$$\n",
    "pad_2(3551)pad_3(544768) = pad_2(2128)pad_3(909056).\n",
    "$$\n",
    "\n",
    "Let's now collect a few smallest relations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pad(t=2,x=3551)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=909056)^1\n",
      "'X: \\r\\xdf'^1 * 'X: \\x08P\\x00'^1 = 'X: \\x08P'^1 * 'X: \\r\\xdf\\x00'^1\n",
      "\n",
      "pad(t=2,x=4096)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=1048576)^1\n",
      "'X: \\x10\\x00'^1 * 'X: \\x08P\\x00'^1 = 'X: \\x08P'^1 * 'X: \\x10\\x00\\x00'^1\n",
      "\n",
      "pad(t=2,x=5216)^1 * pad(t=3,x=544768)^1 = pad(t=2,x=2128)^1 * pad(t=3,x=1335296)^1\n",
      "'X: \\x14`'^1 * 'X: \\x08P\\x00'^1 = 'X: \\x08P'^1 * 'X: \\x14`\\x00'^1\n",
      "\n",
      "pad(t=2,x=2128)^1 * pad(t=2,x=15360)^1 = pad(t=1,x=60)^1 * pad(t=3,x=544768)^1\n",
      "'X: \\x08P'^1 * 'X: <\\x00'^1 = 'X: <'^1 * 'X: \\x08P\\x00'^1\n",
      "\n",
      "pad(t=2,x=3551)^1 * pad(t=2,x=4096)^1 = pad(t=1,x=16)^1 * pad(t=3,x=909056)^1\n",
      "'X: \\r\\xdf'^1 * 'X: \\x10\\x00'^1 = 'X: \\x10'^1 * 'X: \\r\\xdf\\x00'^1\n",
      "\n",
      "pad(t=2,x=3551)^1 * pad(t=2,x=45824)^1 = pad(t=1,x=179)^1 * pad(t=3,x=909056)^1\n",
      "'X: \\r\\xdf'^1 * 'X: \\xb3\\x00'^1 = 'X: \\xb3'^1 * 'X: \\r\\xdf\\x00'^1\n",
      "\n",
      "pad(t=2,x=14342)^1 * pad(t=2,x=15360)^1 * pad(t=2,x=19112)^1 * pad(t=2,x=19882)^1 * pad(t=2,x=49637)^1 * pad(t=2,x=60284)^1 * pad(t=3,x=334844)^1 * pad(t=3,x=500696)^1 * pad(t=3,x=544768)^1 * pad(t=3,x=674328)^1 * pad(t=3,x=841240)^1 * pad(t=3,x=1081991)^1 * pad(t=3,x=1190435)^1 * pad(t=3,x=1728280)^1 = pad(t=2,x=7738)^1 * pad(t=2,x=8222)^1 * pad(t=2,x=15059)^1 * pad(t=2,x=42800)^1 * pad(t=2,x=44753)^1 * pad(t=2,x=55393)^1 * pad(t=3,x=289264)^1 * pad(t=3,x=502308)^1 * pad(t=3,x=720337)^1 * pad(t=3,x=793144)^1 * pad(t=3,x=1048576)^1 * pad(t=3,x=1412228)^1 * pad(t=3,x=1424320)^1 * pad(t=3,x=1897317)^1\n",
      "'X: 8\\x06'^1 * 'X: <\\x00'^1 * 'X: J\\xa8'^1 * 'X: M\\xaa'^1 * 'X: \\xc1\\xe5'^1 * 'X: \\xeb|'^1 * 'X: \\x05\\x1b\\xfc'^1 * 'X: \\x07\\xa3\\xd8'^1 * 'X: \\x08P\\x00'^1 * 'X: \\nJ\\x18'^1 * 'X: \\x0c\\xd6\\x18'^1 * 'X: \\x10\\x82\\x87'^1 * 'X: \\x12*#'^1 * 'X: \\x1a_\\x18'^1 = 'X: \\x1e:'^1 * 'X:  \\x1e'^1 * 'X: :\\xd3'^1 * 'X: \\xa70'^1 * 'X: \\xae\\xd1'^1 * 'X: \\xd8a'^1 * 'X: \\x04i\\xf0'^1 * 'X: \\x07\\xaa$'^1 * 'X: \\n\\xfd\\xd1'^1 * 'X: \\x0c\\x1a8'^1 * 'X: \\x10\\x00\\x00'^1 * 'X: \\x15\\x8c\\x84'^1 * 'X: \\x15\\xbb\\xc0'^1 * 'X: \\x1c\\xf3e'^1\n",
      "\n"
     ]
    }
   ],
   "source": [
    "rels = []\n",
    "for row in ml[:7]:\n",
    "    rel = []\n",
    "    for i, c in enumerate(row):\n",
    "        t, x = sources[i]\n",
    "        v = 256**t*T + x\n",
    "        v = v**abs(c)\n",
    "        if c:\n",
    "            rel.append((c, t, x))\n",
    "    print(\n",
    "        \" * \".join(\"pad(t=%d,x=%d)^%d\" % (r[1], r[2], r[0]) for r in rel if r[0] > 0),\n",
    "        \"=\",\n",
    "        \" * \".join(\"pad(t=%d,x=%d)^%d\" % (r[1], r[2], -r[0]) for r in rel if r[0] < 0),\n",
    "    )\n",
    "    print(\n",
    "        \" * \".join(repr(long_to_bytes(256**r[1]*T+r[2])) + \"^%d\" % r[0] for r in rel if r[0] > 0),\n",
    "        \"=\",\n",
    "        \" * \".join(repr(long_to_bytes(256**r[1]*T+r[2])) + \"^%d\" % (-r[0]) for r in rel if r[0] < 0),\n",
    "    )\n",
    "    print()\n",
    "    rels.append(rel)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first 6 relations are very short and should be enough to recover $n$! The others are of course still usable if needed: they have a reasonable amount of terms and small powers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "cache = {}\n",
    "def query(x, t):\n",
    "    if (x, t) not in cache:\n",
    "        f.read_until(b\"X value:\")\n",
    "        assert x < 256**t\n",
    "        assert x < 256**15\n",
    "        bx = long_to_bytes(x) if x else \"\"\n",
    "        bx = \"\\x00\" * (t - len(bx)) + bx\n",
    "        f.send_line(bx.encode(\"hex\"))\n",
    "        cache[x, t] = int(f.read_line().strip(), 16)\n",
    "    return cache[x, t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rel [(-1, 2, 2128), (1, 2, 3551), (1, 3, 544768), (-1, 3, 909056)]\n",
      "rel [(-1, 2, 2128), (1, 2, 4096), (1, 3, 544768), (-1, 3, 1048576)]\n",
      "rel [(-1, 2, 2128), (1, 2, 5216), (1, 3, 544768), (-1, 3, 1335296)]\n",
      "rel [(-1, 1, 60), (1, 2, 2128), (1, 2, 15360), (-1, 3, 544768)]\n",
      "rel [(-1, 1, 16), (1, 2, 3551), (1, 2, 4096), (-1, 3, 909056)]\n",
      "rel [(-1, 1, 179), (1, 2, 3551), (1, 2, 45824), (-1, 3, 909056)]\n",
      "\n",
      "n = 28152737628466294873353447700677616804377761540447615032304834412268931104665382061141878570495440888771518997616518312198719994551237036466480942443879131169765243306374805214525362072592889691405243268672638788064054189918713974963485194898322382615752287071631796323864338560758158133372985410715951157\n"
     ]
    }
   ],
   "source": [
    "f = Sock(\"3.115.26.78 31337\")\n",
    "f.read_until(\"flag! \")\n",
    "encflag = bytes_to_long(f.read_line().strip().decode(\"hex\"))\n",
    "n = 0\n",
    "for rel in rels[:6]:\n",
    "    print(\"rel\", rel)\n",
    "    vl = vr = 1\n",
    "    for c, t, x in rel:\n",
    "        v = query(x, t)\n",
    "        if c < 0:\n",
    "            vr *= v**(-c)\n",
    "        else:\n",
    "            vl *= v**c\n",
    "    n = gcd(n, vl - vr)\n",
    "f.close()\n",
    "print()\n",
    "print(\"n =\", n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now comes the guessing part: we recovered $n$, so what? Even if we recover $e$ (may be it's small?) we only have the encryption oracle...\n",
    "\n",
    "After trying basic factorization attacks on $n$, we can find that Pollard's $p-1$ works: $p-1$ is smooth for at some prime factor of $n$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 * 269 * 1013 * 1997 * 2293 * 5477 * 6521 * 8521 * 9029 * 13729 * 15511 * 16333 * 18119 * 19963 * 24329 * 25589 * 26561 * 37889 * 38231 * 38557 * 38851 * 47881 * 49477 * 49547 * 49549 * 59009 * 63149 * 64067 * 66733 * 67807 * 70139 * 76543 * 78277 * 85621 * 85991 * 88289\n"
     ]
    }
   ],
   "source": [
    "p = 531268630871904928125236420930762796930566248599562838123179520115291463168597060453850582450268863522872788705521479922595212649079603574353380342938159\n",
    "q = 52991530070696473563320564293242344753975698734819856541454993888990555556689500359127445576561403828332510518908254263289997022658687697289264351266523\n",
    "assert n == p * q\n",
    "print(factor(p-1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This allows us to recover the public exponent too, since we can apply Pohlig-Hellman's discrete logarithm method. Sage can do it for us transparently:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "375469807216214245"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f = Sock(\"3.115.26.78 31337\")\n",
    "msg0 = T\n",
    "enc0 = query(0, 0)\n",
    "f.close()\n",
    "F = GF(p)\n",
    "e = F(enc0).log(F(msg0))\n",
    "assert pow(msg0, e, n) == enc0\n",
    "e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'X: \\xb2J\\xb4\\x82\\xb6\\x042!\\x15\\xce$\\xf83\\xd6\\xd6nF?\\x1an\\xd6\\xd0\\xbc\\xed<O>\\xee\\x97*\"g\\x14\\xa6\\xf0k%\\xd6\\xfa\\xf4`\\x8a{\\x05\\x12\\x86\\xfe\\x1f!\\xb2\\xb3\\x16\\xbfa\\x04:^~\\x1bjc4\\xb2\\x04\\xeb\\xfe\\x9ayhitcon{@@@_5m00thneSS_CAN_give_y0u_everything_@@@}\\n'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d = inverse_mod(e, n - p - q + 1)\n",
    "long_to_bytes(pow(encflag, d, n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Aftermath\n",
    "\n",
    "After the CTF my colleague told me a very simple way to find $n$. In fact, it is basically the same as the 6 relations that I used, but I didn't realize their trivial structure, for example:\n",
    "\n",
    "```py\n",
    "'X: \\r\\xdf'^1 * 'X: \\x08P\\x00'^1 = 'X: \\x08P'^1 * 'X: \\r\\xdf\\x00'^1\n",
    "```\n",
    "\n",
    "Clearly, there are arbitrary two messages and their copies padded by a null bytes!\n",
    "\n",
    "Since we can append a null byte to any message, we obtain encryptions of $m$ and $256m$, and if we repeat for another message $m'$, we get:\n",
    "\n",
    "$$m^e \\times (256m')^e = (m')^e \\times (256m)^e.\n",
    "$$\n",
    "\n",
    "Since we obtain reduced modulo $n$ encryptions, the products are likely to be separated by a nonzero multiple of $n$, and $n$ can thus be recovered using a couple of $gcd$.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 8.8",
   "language": "sage",
   "name": "sagemath"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

Github viewer crashes, please use
https://nbviewer.jupyter.org/gist/hellman/6f3cf1dafc72564038346dfc7c496bc4