Hitcon CTF 2019 Quals - Lost Modulus Again

lost_modulus_again.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HITCON CTF 2019 Quals - Lost Modulus Again (crypto)\n",
    "\n",
    "The challenge is a typical RSA challenge with partial information about the private key given:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```py\n",
    "from Crypto.Util.number import *\n",
    "\n",
    "class Key:\n",
    "    def __init__(self, bits):\n",
    "        assert bits >= 512\n",
    "        self.p = getPrime(bits)\n",
    "        self.q = getPrime(bits)\n",
    "        self.n = self.p * self.q\n",
    "        self.e = 0x100007\n",
    "        self.d = inverse(self.e, (self.p-1)*(self.q-1))\n",
    "        self.dmp1 = self.d%(self.p-1)\n",
    "        self.dmq1 = self.d%(self.q-1)\n",
    "        self.iqmp = inverse(self.q, self.p)\n",
    "        self.ipmq = inverse(self.p, self.q)\n",
    "\n",
    "    def encrypt(self, data):\n",
    "        num = bytes_to_long(data)\n",
    "        result = pow(num, self.e, self.n)\n",
    "        return long_to_bytes(result)\n",
    "\n",
    "    def decrypt(self, data):\n",
    "        num = bytes_to_long(data)\n",
    "        v1 = pow(num, self.dmp1, self.p)\n",
    "        v2 = pow(num, self.dmq1, self.q)\n",
    "        result = (v2*self.p*self.ipmq+v1*self.q*self.iqmp) % self.n\n",
    "        return long_to_bytes(result)\n",
    "\n",
    "    def __str__(self):\n",
    "        return \"Key([e = {0}, n = {1}, x = {2}, y = {3}])\".format(self.e, self.d, self.iqmp, self.ipmq)\n",
    "\n",
    "def main():\n",
    "    key = Key(1024)\n",
    "    flag = open('flag').read()\n",
    "    encrypt_flag = key.encrypt(flag)\n",
    "    assert key.decrypt(encrypt_flag) == flag\n",
    "    print key\n",
    "    print encrypt_flag.encode('hex')\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are given $e,n,(p^{-1}\\mod q),(q^{-1}\\mod p)$... Oops! We are not given $n$, we are given the **private exponent** $d$ instead! Are we done already? Not so fast!\n",
    "\n",
    "Without $n$, we can not reduce modulo, and exponentiations are somewhat useless.. We have to use the primes' inverses. These are numbers used in the Chinese Remainder Theorem.\n",
    "\n",
    "Let $i_p = (p^{-1}\\mod q), i_q = (q^{-1}\\mod p)$. Then, by CRT, we have\n",
    "\n",
    "$$\n",
    "i_pp + i_qq \\equiv 1 \\pmod{n}.\n",
    "$$\n",
    "\n",
    "Note that since $i_p,p,i_q,q$ are all roughly of size $\\sqrt{n}$, we can deduce that actually\n",
    "\n",
    "$$\n",
    "i_pp + i_qq = 1 + n.\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also have the standard equation\n",
    "\n",
    "$$\n",
    "ed = 1 + k\\phi(n) = 1 + k(pq - p - q + 1),\n",
    "$$\n",
    "\n",
    "where $0 \\le k < min(e,d)$. Since $e = 1048583$, we can try all possible values for $k$. The two last equations then become equations with only $p,q$ unknown and thus can be solved by standard methods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function, division\n",
    "from sage.all import *\n",
    "from Crypto.Util.number import *\n",
    "class Stop(Exception): _render_traceback_ = lambda self: None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "e = 1048583\n",
    "d = 20899585599499852848600179189763086698516108548228367107221738096450499101070075492197700491683249172909869748620431162381087017866603003080844372390109407618883775889949113518883655204495367156356586733638609604914325927159037673858380872827051492954190012228501796895529660404878822550757780926433386946425164501187561418082866346427628551763297010068329425460680225523270632454412376673863754258135691783420342075219153761633410012733450586771838248239221434791288928709490210661095249658730871114233033907339401132548352479119599592161475582267434069666373923164546185334225821332964035123667137917080001159691927\n",
    "\n",
    "ip = 22886390627173202444468626406642274959028635116543626995297684671305848436910064602418012808595951325519844918478912090039470530649857775854959462500919029371215000179065185673136642143061689849338228110909931445119687113803523924040922470616407096745128917352037282612768345609735657018628096338779732460743\n",
    "iq = 138356012157150927033117814862941924437637775040379746970778376921933744927520585574595823734209547857047013402623714044512594300691782086053475259157899010363944831564630625623351267412232071416191142966170634950729938561841853176635423819365023039470901382901261884795304947251115006930995163847675576699331\n",
    "\n",
    "ct = 0x32074de818f2feeb788e36d7d3ee09f0000381584a72b2fba0dcc9a2ebe5fd79cf2d6fd40c4dbfea27d3489704f2c1a30b17a783baa67229d02043c5bc9bdb995ae984d80a96bd79370ea2c356f39f85a12d16983598c1fb772f9183441fea5dfeb5b26455df75de18ce70a6a9e9dbc0a4ca434ba94cf4d1e5347395cf7aafa756c8a5bd6fd166bc30245a4bded28f5baac38d024042a166369f7515e8b0c479a1965b5988b350064648738f6585c0a0d1463bd536d11a105bb926b44236593b5c6c71ef5b132cd9c211e8ad9131aa53ffde88f5b0df18e7c45bcdb6244edcaa8d386196d25297c259fca3be37f0f2015f40cb5423a918c51383390dfd5a8703"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "k = 973605\n",
      "p = 166564961597106229342966450443567005929416288372170308009700499465281616388542030734600089639466922805142577582894052957547174764252067983124558747593344882775630971023610755334859287415681252266825395627416912206349590353878868107848653100299011246746851490276537231636534462821659050996145878589643016881929\n",
      "q = 135136928230019073146158752709151576119155564982754768027494878210491711363872928718225319693774548227271767324623087432404412585662574641211148315864508708036871556964386141364368797168619283425834644924573664613109609076319077176698754203574237779054129492453503018443013301394555677417140681949745410143477\n",
      "'hitcon{1t_is_50_easy_t0_find_th3_modulus_back@@!!@!@!@@!}\\n'\n"
     ]
    }
   ],
   "source": [
    "vp = PolynomialRing(QQ, names='p').gen()\n",
    "\n",
    "for k in reversed(range(e)):    \n",
    "    vq = (e * d - 1 - k * (ip - 1) * vp) / QQ(k * (iq - 1))\n",
    "    poly = iq * vq + ip * vp - vp * vq - 1\n",
    "    for zp, _ in poly.roots():\n",
    "        if zp != int(zp): continue\n",
    "        zp = abs(int(zp))\n",
    "        if pow(2, e * d % (zp - 1), zp) != 2: continue\n",
    "            \n",
    "        print(\"k =\", k)\n",
    "        print(\"p =\", zp)\n",
    "        zq = vq.subs(p=zp)\n",
    "        print(\"q =\", zq)\n",
    "        n = int(zp * zq)\n",
    "        m = int(pow(ct, d, n))\n",
    "        assert pow(m, e, n) == ct\n",
    "        print(repr(long_to_bytes(int(m))))\n",
    "        raise Stop"
   ]
  }
 ],
 "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"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

https://nbviewer.jupyter.org/gist/hellman/8e1793771cf240740b731c2b082b1ba2