2nd Crypto CTF 2020 - GenGol

gengol.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2nd Crypto CTF 2020 - GenGol\n",
    "\n",
    "This is again an RSA-like challenge, where few weaknesses are interestingly mixed together."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import *\n",
    "import random\n",
    "\n",
    "def genkey(k=512, nbit=1024):\n",
    "    assert 2*k <= nbit\n",
    "    while True:\n",
    "        p = random.randint(1, 2**(nbit - k)) * 2**k + 1\n",
    "        if not isPrime(p): continue\n",
    "        q = getPrime(nbit)\n",
    "        n = p * q\n",
    "        while True:\n",
    "            y = random.randint(1, n)\n",
    "            jp, jq = pow(y, (p-1)//2, p), pow(y, (q-1)//2, q)\n",
    "            if (jp + jq == p + q - 2):\n",
    "                d = random.randint(int(exp(0.272 * log(n))), int(exp(0.292 * log(n)))) | 1\n",
    "                e = inverse(d, (p - 1)*(n/p - 1))\n",
    "                if e * d % ((p - 1)*(n/p - 1)) == 1:\n",
    "                    return (n, y, k, e), (p, d)\n",
    "\n",
    "def encrypt(msg, pkey):\n",
    "    n, y, k, _ = pkey\n",
    "    m = bytes_to_long(msg)\n",
    "    assert m <= 2**k - 1\n",
    "    x = random.randint(1, n)\n",
    "    c = pow(y, m, n) * pow(x, 4**k, n) % n\n",
    "    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-16T21:12:52.348331Z",
     "iopub.status.busy": "2020-08-16T21:12:52.347909Z",
     "iopub.status.idle": "2020-08-16T21:12:52.353010Z",
     "shell.execute_reply": "2020-08-16T21:12:52.351998Z",
     "shell.execute_reply.started": "2020-08-16T21:12:52.348283Z"
    }
   },
   "outputs": [],
   "source": [
    "n, y, k, e = pkey = (19545764749038418707423482688339375172570014947642431940684456209199133662612924782350873526870144698958332746564347962129710266450724719417969337820667041471024794991519152124184751777703438755127996141556369377531644132238147658246849302588050812207568092111336823914414716415415043221612879571114226453349014538716642991132002013001057172880188860648420935958930680331305269004539955338202912788402527881753117747941781017257550506692901575263952247810144252350279803242123415203612038326448039955185283198645290497751691434792586616961955028752759257565821926239920507512570745243565662182775774062057791614340059L, 6713416021011621860292095135170808229197691401808786379005956958972631575685722516254902506420897257390134389751222750071612382145080088914855339805564824600399571590429098132306344208575084295212754746022537647167518867331249618141656172215473281056990729825123342876791069716652238530101906241012957925858050801973297467776915931059263433002394778083519034230621723649147245051859246240595459023971754395781480309164911053126130864589542140823684068414351622554117077387498819889441373973156596663742549798997739739818594080622027379880314278201881341695601412534917197345991836322646172268609850323157309277449839L, 512, 6430470634703752752410865118713512102273240450186720678582719773307245425439795018835094838171454393910107856337743886319396544382771488797495287565431789565914797925117124451292370339814770378298130765557283040202149138450222342144790542310174532627018946820721116849808896185555115650699502252019810137138661202289232657347537636031798052620838832324602613187586907293646530610877952048890046729989059412110648213600146045233277015646822494474807562255270052325042929699002216633761536108800580880403467146230213318196826190179231978188794163889939327438074942415151273248971589462645532957964702863891474130785207L)\n",
    "enc = 3454085346574987225897831843027819308224167386932731290492223099682362777177850503131523581825210489935713468476347858275690317267310391889881249451570639374942758474027300505459731033746919130301261750148953120742881314068224134546119933825907008577335596198633834951391140360579708607628376848859139717083973348586284471677027943816798571794184743064521079266501342213050814388151710070528752227349444352969848344075816569840832978948650595425435333679490829143988877536836692298581315990015291505643844132256649193564238372544816803818259019432171003583987935610027762164808999385479216326262990988010754441786843"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First weakness: the prime $p$ has the form $p=2^{512}h+1$ for some random 512-bit number $h$. Immediately we can recall that knowing half of the bits of a prime leads to factorization via the Coppersmith attack. However, the attack complexity grows rather fast as the number of known bits approaches the half. And in this challenge, we have exactly half, so it's rather tough.\n",
    "\n",
    "Second weakness: the private exponent $d$ is small, which again would lead to factorization via the Boneh-Durfee attack, as long we have $d \\le n^{0.292}$. Unfortunately, similarly to the first weakness, we have $d$ very close to the bound. Applying this attack would be difficult again.\n",
    "\n",
    "Can we combine the two weaknesses? Let's see! The following equation links together the exponents and the primes:\n",
    "$$\n",
    "    ed = 1 + k\\phi(n) = 1 + k(n-p-q+1),\n",
    "$$\n",
    "with another unknown $k \\le d$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that from the least significant half of $p$ we can always derive the least significant half of $q$:\n",
    "$$\n",
    "q \\equiv n/p \\equiv n/1 \\pmod{2^{512}}.\n",
    "$$\n",
    "Funnily, it matches the 512 least significant bits of $n$!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is typical to reduce the main equation modulo $e$ when it's large (as in the Boneh-Durfee attack). Let also\n",
    "$$\n",
    "q=2^{512}q_1 + q_0,~~ c=n-q_0,~~ s=h+q_1.\n",
    "$$\n",
    "Then\n",
    "$$\n",
    "1 + ck - 2^{512}ks \\equiv 0 \\pmod{e}.\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we've got rid of $d$... Let's go back to $\\mathbb{Z}$! Let's multiply the congruence by a magic constant such that all overflows go away. (By the way, this simplified Coppersmith-like technique was actually described by Håstad in 1988).\n",
    "\n",
    "Does such a constant exist? There is a simple rule of thumb: sum up the unknown bits in each monomial, it should be less than size of the modulus. We know that $k \\le d < N^{0.292} \\approx 2^{600}$, and $k(h+q_1) \\le 2^{513 + 600}$, totaling in 1713 bits, while $e$ is close to $n$, that is 2048 bits. All is well!\n",
    "\n",
    "We build the lattice spanned by the rows of the following matrix:\n",
    "$$\n",
    "M = \\begin{pmatrix}\n",
    "1 & c & -2^{512} \\\\\n",
    "0 & e & 0 \\\\\n",
    "0 & 0 & e\n",
    "\\end{pmatrix},\n",
    "$$\n",
    "and we scale the coordinates (columns of $M$) according to the maximum values of respective unknowns: $1$ for the monomial $1$, $2^{600}$ for the monomial $ck=k(n-q_0)$ and $2^{600+513}$ for the monomial $ks=k(h+q_1)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-16T21:12:52.354817Z",
     "iopub.status.busy": "2020-08-16T21:12:52.354394Z",
     "iopub.status.idle": "2020-08-16T21:12:52.502759Z",
     "shell.execute_reply": "2020-08-16T21:12:52.501592Z",
     "shell.execute_reply.started": "2020-08-16T21:12:52.354767Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "logs 1873.48 1275.86 765.42\n"
     ]
    }
   ],
   "source": [
    "q0 = n % 2**512\n",
    "c = n - q0\n",
    "\n",
    "m = matrix(ZZ, 3, 3)\n",
    "m.set_row(0, [1, n-q0, -2**512])\n",
    "m[1,1] = m[2,2] = e\n",
    "\n",
    "# scale\n",
    "ws = [1, 2**600, 2**(600+513)]\n",
    "for i, w in enumerate(ws):\n",
    "    m.set_column(i, m.column(i) * w)\n",
    "\n",
    "# reduce\n",
    "m = m.LLL()\n",
    "\n",
    "# unscale\n",
    "for i, w in enumerate(ws):\n",
    "    m.set_column(i, [a // w for a in m.column(i)])\n",
    "\n",
    "v1, v2, v3 = m[0]\n",
    "print(\"logs\", *[\"%.2f\" % math.log(abs(int(v)), 2) for v in m[0]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now have an equation\n",
    "$$\n",
    "v_1 + v_2k + v_3ks = 0\n",
    "$$\n",
    "with known $v_1,v_2,v_3$. Let's reduce it modulo $v_3$ to get rid of $s$ and recover $k$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-16T21:12:52.509211Z",
     "iopub.status.busy": "2020-08-16T21:12:52.504970Z",
     "iopub.status.idle": "2020-08-16T21:12:52.519115Z",
     "shell.execute_reply": "2020-08-16T21:12:52.517101Z",
     "shell.execute_reply.started": "2020-08-16T21:12:52.508956Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "k 216044433968486211309048459396103283041730279225632068616903982472942572502334736404159307637404900676003426000595797121702299425713710848996850411476714168260771030918399955451677\n"
     ]
    }
   ],
   "source": [
    "mod = abs(v3) # can be negative, no problem\n",
    "k = (-v1 * inverse_mod(v2, mod)) % mod\n",
    "assert 0 <= k <= 2**600\n",
    "print(\"k\", k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can recover $d$ by inverting $e$ modulo $k$, except that $k$ is a bit smaller than $d$ so we would need to add a small multiple of $k$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-16T21:12:52.522077Z",
     "iopub.status.busy": "2020-08-16T21:12:52.521260Z",
     "iopub.status.idle": "2020-08-16T21:12:52.586477Z",
     "shell.execute_reply": "2020-08-16T21:12:52.585138Z",
     "shell.execute_reply.started": "2020-08-16T21:12:52.521967Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "d 656678790957846493325522295512552964642389087863533147035026289582702006575160547700839896514211327495319861876561572664042587635691012861464469207125743152896724283300906291591687\n"
     ]
    }
   ],
   "source": [
    "for i in range(100):\n",
    "    d = inverse_mod(e, k) + i*k\n",
    "    if pow(2, e * d, n) == 2:\n",
    "        break\n",
    "else:\n",
    "    raise\n",
    "print(\"d\", d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we can factorize $n$ using knowledge of $e,d$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-16T21:12:52.589448Z",
     "iopub.status.busy": "2020-08-16T21:12:52.588445Z",
     "iopub.status.idle": "2020-08-16T21:12:52.652448Z",
     "shell.execute_reply": "2020-08-16T21:12:52.650481Z",
     "shell.execute_reply.started": "2020-08-16T21:12:52.589330Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "p 172526663954288094402684831904894709672893572566091967600912295188703612481353322028634215632716054996456966521811183881911243075756946478351847294224868653426239553732224998655197250350521485873159799384081746532388926378144538953342220772420070151311687280144185404913564138987585944163712571082540021959643\n",
      "q 113291269309056938092068497035577523945787720114947464982138940595000056469162234376505618425566254410753094291703374184880373819234307147701908263467938592313201528637552669061051638788295404349743246277302794476046653862387813290948923123537614303866508465481425893261054183642634492637353626231145771302913\n"
     ]
    }
   ],
   "source": [
    "for i in range(100):\n",
    "    p = gcd(n, int(pow(2, (e * d - 1)//2**i, n)) - 1)\n",
    "    if 1 < p < n:\n",
    "        break\n",
    "else:\n",
    "    raise\n",
    "q = n // p\n",
    "print(\"p\", p)\n",
    "print(\"q\", q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, I lied to you: this is not an RSA challenge, because the flag is not encrypted by $e$-exponentiation! Instead, it turns out to be a generalized Goldwasser-Micali cryptosystem. Anyway, the message is easy to recover by doing discrete log in the subgroup of order $2^{512}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-08-16T21:12:52.655216Z",
     "iopub.status.busy": "2020-08-16T21:12:52.654175Z",
     "iopub.status.idle": "2020-08-16T21:12:53.074411Z",
     "shell.execute_reply": "2020-08-16T21:12:53.073110Z",
     "shell.execute_reply.started": "2020-08-16T21:12:52.655111Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CCTF{9en3r4liZed_adDi7iv3lY_h0mOmorphiC_Goldwa5ser_Mic4Li}\n"
     ]
    }
   ],
   "source": [
    "msg = 0\n",
    "if (p-1) % 2**512 != 0:\n",
    "    p, q = q, p\n",
    "h = (p-1) >> 512\n",
    "target = pow(enc, h, p)\n",
    "gen = pow(y, h, p)\n",
    "for i in range(512):\n",
    "    targeti = pow(target, 2**(511-i), p)\n",
    "    geni = pow(gen, 2**(511-i), p)\n",
    "    if pow(geni, msg, p) != targeti:\n",
    "        msg += 1 << i       \n",
    "print(long_to_bytes(msg).decode())"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.1",
   "language": "sage",
   "name": "sagemath3"
  },
  "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}

https://nbviewer.jupyter.org/gist/hellman/2e2e74bec0e002c904883661b427a72d