hellman/not_so_hard_rsa.ipynb

## not_so_hard_rsa.ipynb
{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# HITCON CTF 2019 Quals - Not So Hard RSA (crypto)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The challenge consists of the following short code:\n",
    "\n",
    "```py\n",
    "from Crypto.Util.number import *\n",
    "from secrets import *\n",
    "\n",
    "T = 10\n",
    "def encrypt(data):\n",
    "    num = bytes_to_long(data)\n",
    "    p = getPrime(512)\n",
    "    q = getPrime(512)\n",
    "    n = p*q\n",
    "    assert num < n\n",
    "    phi = (p-1)*(q-1)\n",
    "    e = inverse(d,phi)\n",
    "    a = pow(num,e,n)\n",
    "    enc = long_to_bytes(a).encode('hex')\n",
    "    return (n,e,enc)\n",
    "\n",
    "flag = open('flag').read()\n",
    "print d.bit_length()\n",
    "for _ in xrange(T):\n",
    "    data = flag + urandom(40)\n",
    "    print encrypt(data)\n",
    "```\n",
    "\n",
    "We are given 10 different RSA moduli and encryptions of the flag under each of them. The only relation between them is the common private exponent $d$. From the output file we can see that it has 465 bits, i.e. it is very short (compared to 1024 bits - size of $n$). Consider the exponents equations of the RSA, with approximate bit size of elements noted (recall that $0 \\le k_i < min(e_i, d)$):\n",
    "\n",
    "$$\n",
    "\\underbrace{e_i}_\\text{1024 bits} \\underbrace{d}_\\text{465 bits} - 1\n",
    "=\n",
    "k_i \\phi(n_i) = \\underbrace{k_i}_\\text{465 bits}(\\underbrace{n_i}_\\text{1024 bits}\\underbrace{-p_i-q_i+1}_\\text{512 bits})\n",
    ".\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\underbrace{k_in_i}_\\text{1489 bits} - \\underbrace{e_i d+1}_\\text{1489 bits} = \\underbrace{k_i(p_i+q_i-1)}_\\text{977 bits}.\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How much freedom do the unknowns have? Let's assume we fix $d$ arbitrarily. Then 465-bit freedom of $k$ would allow to get roughly $1489-465=1024$-bit value on the left. However, we know that it has only 977 bits (we consider it as an error/noise term). Therefore, we obtain a 47-bit costraint on $d$ from each equation. From 10 equations we can expect to recover all 465 bits of $d$!\n",
    "\n",
    "This is just an intuition behind the sizes of the numbers, we also have to efficiently satisfy the constraints. Luckily, LLL works great with such linear equations.\n",
    "\n",
    "Consider the following lattice (spanned by rows):\n",
    "\n",
    "$$\n",
    "\\Lambda =\n",
    "\\begin{array}{c c}\n",
    "    \\begin{array}{c}\n",
    "      d \\\\ k_1 \\\\ \\vdots \\\\ k_{10}\n",
    "    \\end{array}\\hspace{-1em}\n",
    "    &\n",
    "    \\left(\n",
    "      \\begin{array}{@{} c c c c c c c @{}}\n",
    "        -e_1 & \\cdots & -e_{10} & 1   & 0 & \\cdots & 0 \\\\\n",
    "        1 & \\cdots & 0 & 0          & 1 & \\cdots & 0 \\\\\n",
    "        \\vdots & \\ddots  & \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
    "        0 & \\cdots & 1 & 0          & 0 & \\cdots & 1 \\\\\n",
    "      \\end{array}\n",
    "    \\right) \\\\\n",
    "     & \\begin{array} {@{} c c c c c c c @{}}\n",
    "        \\hspace{0.7cm}v_1 & \\cdots & v_{10} & \\hspace{0.35cm}d & k_1 & \\cdots & k_{10} \n",
    "      \\end{array} \\\\\n",
    "\\end{array}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that all $e_i$ are in the same row since they correspond to terms with $e_id$ and $d$ is the same for all equations. Whereas all $k_i$ are different and each has its own row.\n",
    "\n",
    "Consider the correct $k_i$ and $d$ and consider the linear combination descibed at the left side of the matrix. The corresponding vector in the lattice is equal to\n",
    "$$\n",
    "(v_1, \\dots, v_{10}, d, k_1, \\dots, k_{10}),\n",
    "$$\n",
    "where $v_i = k_in_i-e_id$ is the small (\"noise\") 977-bit value. As a result, we obtain that the solution we look for correspond to the short vector in the lattice: all $v_i$, $d$ and all $k_i$ must be small. Note that $d$ and $k$ should be 465-bit values, while $v$ can be much larger: 977 bits. To encode this information, we scale the '$d$' and '$k_i$' columns by $2^{512}$ before applying LLL and scale back afterwards."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "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": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# chall\n",
    "data = [\n",
    "(61608417975397048843788515638593839325111098880518441270527767841153782846066445099077365303960932518098100778959123136871039627996767023258612684873083420234538156646585282154245553305607644427220207313162116929585370583379703086997585339296145409828300576290109728682441066135201997295424597733433471586151L, 60032368056605168202792776655067640210910930719068898740685488293392455428589220656480049668823171895161714617099267690524276842795335016835073541061601545456195765907623303970146386500563913899580929779870429659650425339185233299118860275385880359287380867251468679962048998842668813298548390941601249105855L, '1e4433543ad3eab1d5a5490e33ee98c34785945c7b69dd0fd0a371c28e5ff45f6627ad0559d9837fd6439367543ff5670f4df4fd36cbee75950db62e51811f98e3f34db66b07196a5dfbd9867952d8e6d67c43becf086087181e5f78582e98945e5c8c08d754b998ef01e836729f9620cdcd2cc8aae9cb4bf3d8e4beec3ca8fd'),\n",
    "(52084595054768217522676979342755393306305099169414947960508049057119329537162079071100773540172780699842974838973453517862170568297372572652378982794735495836797191260523386985555538123219596180065060457770169661533302156160201909218943628670173938802399175928847179180982290051008255643478089280887936398779L, 15937444970326662770243305998311639639802081677519521519037892156989918335411343952028567001158781869582357356721336548356177945486289103616332672857562241745733313956089488246637981047367689313876169403573606972534488436195086998111247112950511965259280728899941655052549135516189815880662766290132607874671L, '15dbeced76ab710b84982e67a839846cfe38cfccce4dacc585df0e38d695e1c84eac7281d8c83b3c6eebfae7c27d91496b19de120374d08cbccc251a464c2f7bb10fb9d1c1f13b78f1fbfe0ce37d01350978dcb192c92db43560a9cd81481aa2e2d41a8c5b3c67d3e3ae4be50ddf37a5a0193da6f4befe71d5348bd7820f1b0a'),\n",
    "(121675354261226402523384817752122501670754379029920951567545832861118347020889141951034949457467042630795199347469665294677977729959566390358589470405088739543312116123816666440234661644847943610733959265939955886506334607329368744886743083353218982597246897307234102346047327550059519916639261619453107169923L, 1958149621008109700386193021020256359555810444022322757777842537494487439895477039590251808463946583928481366538370998263830913239177109491659797444270949612728937519312683847609162235917948298810271512469482956117395111528004250206351805086758526770795159863075378020975086922955262230095667701740508170151L, '5b445089b4578b115b0293cc1922f5fdb784701fd533eec7ec9bd7fdad995baefb051b9793ff3dadc24ff8d5b52c89f9565f65409c58506c7e79dd787f8e388f019497461fa3db0eac5284d398f9e6a1b81c59ba74677cc01c38ddd6461df029e1179f3ee63ccce20f3090835b7bd7b4de25c38ccddf2ec622cd41fafb49d68f'),\n",
    "(70820434096887624688036248070441718528107270792728727307197623356369639890276828895683705436125317302252834211775910545775001651922925694194466935425170969939539346172633115232030274859268960310846965871663926227518137713901150141826470260092611613639370170779217268337906342955347156686598981918675591938393L, 6264211827826908864953215815104077572906230669747226774603059704547415338199956437981145121700015020477626176620200121575740530313039227764537541481272011717745292622796843631960318813842515397395192806936521180850750841260559451018598913158548097304919304754876270597286947644956943158352022152801127867879L, '4f56516d8e197a8fd6ed76433a836635dd5ad1247be9ccbb5a88ea940f5746221b4bb5b60ef925019a11d36fbe8f1d948e9afb4305937d7e017148b8ba324682d60ed6fb7f3de80031432023bbef81a96d0c1bd26c3a728bc6fdebbd48bf86b93325584c1a1386e26374c9747754b858a01b73996cea8fe4edd2a8130504e63e'),\n",
    "(82396665631738285668995082087133930047188890932442133336046256534530991902128696466596278088102928917626464109384091264437455382690583003229076491363732222934817133536320704449557698925700841043105303694696203472531025908797520768019280257689521302427077849286757365739653728248123114986191011560571298134089L, 77541341309162852568860774868359137598587882474829780783306540898574011860779494674673722444562346968736216806881154962981695851598965376893425170303668270087989094501452417979429678869102952038600630142304872749698942475289176861137563927160985001506014089253274664444041660282426708388957971134224538326179L, '6b35dffadd327c0999efc909a3c1d1482c6a286808801095eec5ea88224467881b4081c1aef02c273cc5dc4d3505dc50fcf4ce60052b6a5a9dc005faad4709fbcca254c6fc1c552d51c8e15fbd8fc404b0136758e1ba57f6c04b1049e303a43ae60c1eb0b671289f6689d1cd104c407549c1bcfc081a28a3f3324a1611e81555'),\n",
    "(64885222129962661919689742957615146346855998523264787345799887210230045803423356080820154546050540728264000944692170729880161760807788699983366314269171423680987673788784023826885067996007133127166699735414920427997399513922777341273346196540175237091469555617281522541592407225697228219483666768990986901207L, 47625666889348051674457306461777570860477708163951567694477110559722255361844497439523737482859577232793119885759760321686098657292699849459852343686370029321619072315457562131610624443702007471950020751311592439673932509558946203816066868221203483167079506399876187240483994566182748627389022243608934595071L, '0f79419a86361d668ced50fbcfa521c5117f7b2f72c3cc248dba4b2b1c9e7dc3a32fa500f5167a0360aeefcb8daa973bc67b0537d641617c2d96d98ee27179de1644b480c120b2d14054db032b42af33b23f8182f72cc8e752d6f89d556800f637bc492bd8eb2fb294eee61bc3c55677066b6962c4d2a1f1896703d446d903f3'),\n",
    "(130307595686638523389042871138355252466828093625912424932382409748014813151912412889866698513547588105179569464359905871041351306187955332098310075195714887141180801001191398677311128761953690562878908997464309620384635922453765468745206262477334243233099872249671186622159533482223573972729351847574480258349L, 15517881429792452627724339825487038872077384939873021432131971858090290889497162855962736652640866521963165312583164013911162455865793567436833813352448640307756786561236246631146444590597902995591016928432988304077340670079503467394770901559567924809126517090243024890436892801283564005789256977822007581731L, '69a8e0bb49427f3465c9f3a41a22e047bd348c886cdb07264a321f8b890bb48cd7a878e43c1eb4b2f496dafb50677b3eea032c8f7f2ee59695398c56cc3b183bb6e2f1ab2d5d633461a6592ca0c98c0f2dae4100d6aaaf0d1166bdd46beb68b07d9c9cf6c5a92ef7db019dc065b3a8300ca25b50cba51a3294d954c178bf3770'),\n",
    "(65386448419573832864151040666988491321490532636782967162806795276671017479566436411594017000387653366263378617189553041765586083217125727980734225153709370447270596363822524978426540069479632490507360491377612488876553715272119578498102854909764339676652952568021321118127618560269626549257296451954041925283L, 62417639911670877600600895776941278119707067464948560335387709799367122896567813566638216057171867961437006927011778910808189676129022776796728833211435603542364704330783289218396426543693678813151580911213239650850603907199690825764030369692366216968117035006819175280930722880390482701178418013436415892711L, '2231e71788fe0fec78ada4f24a58bbaa5b1a0fb48dc94b18bf7409637dbcfd8e2755d80b5e4b309e20a69474a6e2eb245e40c1b3f81c6151dbf7e6871e90a9616a32f4a8443d30bfaaff5d711be39bc8f38c13234af9fd867f508b8a6b097a49fb07a1392ec08c38f0939620cf644ec6631f7566b6bc7a1f1d01a9c736eceda4'),\n",
    "(131618812326147470215836136712095159211663684841466199972335887950664101678748935713203393931245541362772506324940879455504378545672259298894346211770983161798960234145317156224604949365110464634198678301644727985645228605590810190481288852412139519629077007437022950591320600450976104529132138396249413028099L, 14318453997383587408499979509282945054981178882287936277795320451723285671391694914929520724692059461777785480850364952738183846512279857119933447174333240691522012746191524101263192457454032837995702952840654708026147079321112397181981380295129696518148352311994008219805602114421675331461920408832158576071L, '71a370974f020d338071e2b0480f38f2d5b488252f5eb206636d6dcd3c93ea586a507c29d2e611a9a8d5d0f849b913116b37e69345d6eae71cf87cdb6b74e75bccdb374c372562777a727f07e4272a5ff17b451d582074b565879453d028c5e9b91cb67ae923f0f09492e508422e65c1daada0564d91a9feec094af77ab190fa'),\n",
    "(99041226655569332839951771030354960649881033648844611842019981984694036670092050113949713459076512100815903654289240773362239468428010238444408944822516190193861719380849620966232652503444079295871086550223067647300451354087943235559953597249075277760677450645744584993036921709483731953822197438848939991653L, 45917328654051873455626365238806652384056265616606200025887647202756379007355041189714541493038574645714670682101129613041399879280497291675656671383417575172090283625761438606371062142083212903854592596935358334738253893062615061401134834123551055465985828525720791523020773994634134135284036947641526947783L, '336e810e66eeac255f1714b290187773de92ec044b654a4cc0eef2070e9d8d86fa37d424b2e4b71fd135e634034e06dbc31e77bd13d470aa5d3e5dcc5e689b565178a4a445d4560f5569967315a0bbe163ef83063429ec8d1fbba1a8dbd9e30a2a67e17793f8b19e7b184c3b989dadc85b7f060e3daefb66ff803c98bda8862f'),\n",
    "]\n",
    "T = len(data)        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that $v_i$ are typically a bit smaller, and we can reduce them by approximating $p+q$ by $2\\sqrt{n}$. Therefore, we should scale the $d$ and $k_i$ columns by a bit smaller numbers. This is important, since the information amount that we obtain is quite tight. In fact, when scaling by $2^{512}$, the resulting basis does not contain the desired result. However, it should still be available in small linear combinations of short vectors, or e.g., by guessing a few bits of $d$ first.\n",
    "\n",
    "Luckily, scaling by $2^{505}$ works well and we find the correct $d$ in 10-th element of the smallest basis vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bit sizes:\n",
      "[968, 966, 962, 967, 970, 971, 964, 970, 961, 970]\n",
      "[465]\n",
      "[465, 463, 459, 461, 465, 464, 462, 465, 461, 464]\n",
      "found d row 0 : d = 52734116413990333859776618028885273976613159615407987318262228643225868562829470128730568170502025104920857931843837285163945541735508099991\n",
      "\"hitcon{recover_everything_by_amazing_LLL_algorithm!!}\\n\\x1c}w\\x16\\x1b\\xbbHv\\x85\\x98X\\xae\\x83xH\\xbeZ'\\x83\\x98o\\xf3\\xfe\\xbcW\\x16\\x15\\xb6\\xd9\\x1f\\xcbG\\xa0\\x84\\xbe\\xbd\\x1b\\xba\\xb6\\xed\"\n"
     ]
    }
   ],
   "source": [
    "m = matrix(ZZ, T+1, 2*T+1)\n",
    "\n",
    "i = 0\n",
    "m[0,T] = 1\n",
    "for ni, ei, ci in data:\n",
    "    m[0,i] = -ei\n",
    "    # approximate p+q as 2sqrt(n), reduce a bit size of the noise\n",
    "    m[1+i,i] = (ni - 2*int(sqrt(ni)))\n",
    "    m[1+i,T+1+i] = 1\n",
    "    i += 1\n",
    "    \n",
    "Cd = 2**505\n",
    "Ck = 2**506\n",
    "for i in range(T):\n",
    "    m.set_column(i, m.column(i))\n",
    "    m.set_column(T+1+i, m.column(T+1+i) * Cd)\n",
    "m.set_column(T, m.column(T) * Ck)\n",
    "\n",
    "ml = m.LLL()\n",
    "\n",
    "for i in range(T):\n",
    "    ml.set_column(i, ml.column(i))\n",
    "    ml.set_column(T+1+i, ml.column(T+1+i) / Cd)\n",
    "ml.set_column(T, ml.column(T) / Ck)    \n",
    "\n",
    "print(\"Bit sizes:\")\n",
    "print([len(ZZ(v).bits()) for v in ml[0][:T]])\n",
    "print([len(ZZ(v).bits()) for v in ml[0][T:T+1]])\n",
    "print([len(ZZ(v).bits()) for v in ml[0][T+1:]])\n",
    "\n",
    "n, e, ct = data[0]\n",
    "\n",
    "for irow, row in enumerate(ml):\n",
    "    d = int(abs(row[T]))\n",
    "    if pow(2, e*d, n) == 2:\n",
    "        print(\"found d\", \"row\", irow, \":\", \"d =\", d)\n",
    "        ct = int(ct, 16)\n",
    "        flag = pow(ct, d, n)\n",
    "        print(`long_to_bytes(flag)`)\n",
    "        break"
   ]
  }
 ],
 "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
}
	{
	"cells": [
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"# HITCON CTF 2019 Quals - Not So Hard RSA (crypto)"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"The challenge consists of the following short code:\n",
	"\n",
	"```py\n",
	"from Crypto.Util.number import *\n",
	"from secrets import *\n",
	"\n",
	"T = 10\n",
	"def encrypt(data):\n",
	" num = bytes_to_long(data)\n",
	" p = getPrime(512)\n",
	" q = getPrime(512)\n",
	" n = p*q\n",
	" assert num < n\n",
	" phi = (p-1)*(q-1)\n",
	" e = inverse(d,phi)\n",
	" a = pow(num,e,n)\n",
	" enc = long_to_bytes(a).encode('hex')\n",
	" return (n,e,enc)\n",
	"\n",
	"flag = open('flag').read()\n",
	"print d.bit_length()\n",
	"for _ in xrange(T):\n",
	" data = flag + urandom(40)\n",
	" print encrypt(data)\n",
	"```\n",
	"\n",
	"We are given 10 different RSA moduli and encryptions of the flag under each of them. The only relation between them is the common private exponent $d$. From the output file we can see that it has 465 bits, i.e. it is very short (compared to 1024 bits - size of $n$). Consider the exponents equations of the RSA, with approximate bit size of elements noted (recall that $0 \\le k_i < min(e_i, d)$):\n",
	"\n",
	"$$\n",
	"\\underbrace{e_i}_\\text{1024 bits} \\underbrace{d}_\\text{465 bits} - 1\n",
	"=\n",
	"k_i \\phi(n_i) = \\underbrace{k_i}_\\text{465 bits}(\\underbrace{n_i}_\\text{1024 bits}\\underbrace{-p_i-q_i+1}_\\text{512 bits})\n",
	".\n",
	"$$\n",
	"\n",
	"$$\n",
	"\\underbrace{k_in_i}_\\text{1489 bits} - \\underbrace{e_i d+1}_\\text{1489 bits} = \\underbrace{k_i(p_i+q_i-1)}_\\text{977 bits}.\n",
	"$$\n"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"How much freedom do the unknowns have? Let's assume we fix $d$ arbitrarily. Then 465-bit freedom of $k$ would allow to get roughly $1489-465=1024$-bit value on the left. However, we know that it has only 977 bits (we consider it as an error/noise term). Therefore, we obtain a 47-bit costraint on $d$ from each equation. From 10 equations we can expect to recover all 465 bits of $d$!\n",
	"\n",
	"This is just an intuition behind the sizes of the numbers, we also have to efficiently satisfy the constraints. Luckily, LLL works great with such linear equations.\n",
	"\n",
	"Consider the following lattice (spanned by rows):\n",
	"\n",
	"$$\n",
	"\\Lambda =\n",
	"\\begin{array}{c c}\n",
	" \\begin{array}{c}\n",
	" d \\\\ k_1 \\\\ \\vdots \\\\ k_{10}\n",
	" \\end{array}\\hspace{-1em}\n",
	" &\n",
	" \\left(\n",
	" \\begin{array}{@{} c c c c c c c @{}}\n",
	" -e_1 & \\cdots & -e_{10} & 1 & 0 & \\cdots & 0 \\\\\n",
	" 1 & \\cdots & 0 & 0 & 1 & \\cdots & 0 \\\\\n",
	" \\vdots & \\ddots & \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
	" 0 & \\cdots & 1 & 0 & 0 & \\cdots & 1 \\\\\n",
	" \\end{array}\n",
	" \\right) \\\\\n",
	" & \\begin{array} {@{} c c c c c c c @{}}\n",
	" \\hspace{0.7cm}v_1 & \\cdots & v_{10} & \\hspace{0.35cm}d & k_1 & \\cdots & k_{10} \n",
	" \\end{array} \\\\\n",
	"\\end{array}.\n",
	"$$"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Note that all $e_i$ are in the same row since they correspond to terms with $e_id$ and $d$ is the same for all equations. Whereas all $k_i$ are different and each has its own row.\n",
	"\n",
	"Consider the correct $k_i$ and $d$ and consider the linear combination descibed at the left side of the matrix. The corresponding vector in the lattice is equal to\n",
	"$$\n",
	"(v_1, \\dots, v_{10}, d, k_1, \\dots, k_{10}),\n",
	"$$\n",
	"where $v_i = k_in_i-e_id$ is the small (\"noise\") 977-bit value. As a result, we obtain that the solution we look for correspond to the short vector in the lattice: all $v_i$, $d$ and all $k_i$ must be small. Note that $d$ and $k$ should be 465-bit values, while $v$ can be much larger: 977 bits. To encode this information, we scale the '$d$' and '$k_i$' columns by $2^{512}$ before applying LLL and scale back afterwards."
	]
	},
	{
	"cell_type": "code",
	"execution_count": 34,
	"metadata": {},
	"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": 35,
	"metadata": {},
	"outputs": [],
	"source": [
	"# chall\n",
	"data = [\n",
	"(61608417975397048843788515638593839325111098880518441270527767841153782846066445099077365303960932518098100778959123136871039627996767023258612684873083420234538156646585282154245553305607644427220207313162116929585370583379703086997585339296145409828300576290109728682441066135201997295424597733433471586151L, 60032368056605168202792776655067640210910930719068898740685488293392455428589220656480049668823171895161714617099267690524276842795335016835073541061601545456195765907623303970146386500563913899580929779870429659650425339185233299118860275385880359287380867251468679962048998842668813298548390941601249105855L, '1e4433543ad3eab1d5a5490e33ee98c34785945c7b69dd0fd0a371c28e5ff45f6627ad0559d9837fd6439367543ff5670f4df4fd36cbee75950db62e51811f98e3f34db66b07196a5dfbd9867952d8e6d67c43becf086087181e5f78582e98945e5c8c08d754b998ef01e836729f9620cdcd2cc8aae9cb4bf3d8e4beec3ca8fd'),\n",
	"(52084595054768217522676979342755393306305099169414947960508049057119329537162079071100773540172780699842974838973453517862170568297372572652378982794735495836797191260523386985555538123219596180065060457770169661533302156160201909218943628670173938802399175928847179180982290051008255643478089280887936398779L, 15937444970326662770243305998311639639802081677519521519037892156989918335411343952028567001158781869582357356721336548356177945486289103616332672857562241745733313956089488246637981047367689313876169403573606972534488436195086998111247112950511965259280728899941655052549135516189815880662766290132607874671L, '15dbeced76ab710b84982e67a839846cfe38cfccce4dacc585df0e38d695e1c84eac7281d8c83b3c6eebfae7c27d91496b19de120374d08cbccc251a464c2f7bb10fb9d1c1f13b78f1fbfe0ce37d01350978dcb192c92db43560a9cd81481aa2e2d41a8c5b3c67d3e3ae4be50ddf37a5a0193da6f4befe71d5348bd7820f1b0a'),\n",
	"(121675354261226402523384817752122501670754379029920951567545832861118347020889141951034949457467042630795199347469665294677977729959566390358589470405088739543312116123816666440234661644847943610733959265939955886506334607329368744886743083353218982597246897307234102346047327550059519916639261619453107169923L, 1958149621008109700386193021020256359555810444022322757777842537494487439895477039590251808463946583928481366538370998263830913239177109491659797444270949612728937519312683847609162235917948298810271512469482956117395111528004250206351805086758526770795159863075378020975086922955262230095667701740508170151L, '5b445089b4578b115b0293cc1922f5fdb784701fd533eec7ec9bd7fdad995baefb051b9793ff3dadc24ff8d5b52c89f9565f65409c58506c7e79dd787f8e388f019497461fa3db0eac5284d398f9e6a1b81c59ba74677cc01c38ddd6461df029e1179f3ee63ccce20f3090835b7bd7b4de25c38ccddf2ec622cd41fafb49d68f'),\n",
	"(70820434096887624688036248070441718528107270792728727307197623356369639890276828895683705436125317302252834211775910545775001651922925694194466935425170969939539346172633115232030274859268960310846965871663926227518137713901150141826470260092611613639370170779217268337906342955347156686598981918675591938393L, 6264211827826908864953215815104077572906230669747226774603059704547415338199956437981145121700015020477626176620200121575740530313039227764537541481272011717745292622796843631960318813842515397395192806936521180850750841260559451018598913158548097304919304754876270597286947644956943158352022152801127867879L, '4f56516d8e197a8fd6ed76433a836635dd5ad1247be9ccbb5a88ea940f5746221b4bb5b60ef925019a11d36fbe8f1d948e9afb4305937d7e017148b8ba324682d60ed6fb7f3de80031432023bbef81a96d0c1bd26c3a728bc6fdebbd48bf86b93325584c1a1386e26374c9747754b858a01b73996cea8fe4edd2a8130504e63e'),\n",
	"(82396665631738285668995082087133930047188890932442133336046256534530991902128696466596278088102928917626464109384091264437455382690583003229076491363732222934817133536320704449557698925700841043105303694696203472531025908797520768019280257689521302427077849286757365739653728248123114986191011560571298134089L, 77541341309162852568860774868359137598587882474829780783306540898574011860779494674673722444562346968736216806881154962981695851598965376893425170303668270087989094501452417979429678869102952038600630142304872749698942475289176861137563927160985001506014089253274664444041660282426708388957971134224538326179L, '6b35dffadd327c0999efc909a3c1d1482c6a286808801095eec5ea88224467881b4081c1aef02c273cc5dc4d3505dc50fcf4ce60052b6a5a9dc005faad4709fbcca254c6fc1c552d51c8e15fbd8fc404b0136758e1ba57f6c04b1049e303a43ae60c1eb0b671289f6689d1cd104c407549c1bcfc081a28a3f3324a1611e81555'),\n",
	"(64885222129962661919689742957615146346855998523264787345799887210230045803423356080820154546050540728264000944692170729880161760807788699983366314269171423680987673788784023826885067996007133127166699735414920427997399513922777341273346196540175237091469555617281522541592407225697228219483666768990986901207L, 47625666889348051674457306461777570860477708163951567694477110559722255361844497439523737482859577232793119885759760321686098657292699849459852343686370029321619072315457562131610624443702007471950020751311592439673932509558946203816066868221203483167079506399876187240483994566182748627389022243608934595071L, '0f79419a86361d668ced50fbcfa521c5117f7b2f72c3cc248dba4b2b1c9e7dc3a32fa500f5167a0360aeefcb8daa973bc67b0537d641617c2d96d98ee27179de1644b480c120b2d14054db032b42af33b23f8182f72cc8e752d6f89d556800f637bc492bd8eb2fb294eee61bc3c55677066b6962c4d2a1f1896703d446d903f3'),\n",
	"(130307595686638523389042871138355252466828093625912424932382409748014813151912412889866698513547588105179569464359905871041351306187955332098310075195714887141180801001191398677311128761953690562878908997464309620384635922453765468745206262477334243233099872249671186622159533482223573972729351847574480258349L, 15517881429792452627724339825487038872077384939873021432131971858090290889497162855962736652640866521963165312583164013911162455865793567436833813352448640307756786561236246631146444590597902995591016928432988304077340670079503467394770901559567924809126517090243024890436892801283564005789256977822007581731L, '69a8e0bb49427f3465c9f3a41a22e047bd348c886cdb07264a321f8b890bb48cd7a878e43c1eb4b2f496dafb50677b3eea032c8f7f2ee59695398c56cc3b183bb6e2f1ab2d5d633461a6592ca0c98c0f2dae4100d6aaaf0d1166bdd46beb68b07d9c9cf6c5a92ef7db019dc065b3a8300ca25b50cba51a3294d954c178bf3770'),\n",
	"(65386448419573832864151040666988491321490532636782967162806795276671017479566436411594017000387653366263378617189553041765586083217125727980734225153709370447270596363822524978426540069479632490507360491377612488876553715272119578498102854909764339676652952568021321118127618560269626549257296451954041925283L, 62417639911670877600600895776941278119707067464948560335387709799367122896567813566638216057171867961437006927011778910808189676129022776796728833211435603542364704330783289218396426543693678813151580911213239650850603907199690825764030369692366216968117035006819175280930722880390482701178418013436415892711L, '2231e71788fe0fec78ada4f24a58bbaa5b1a0fb48dc94b18bf7409637dbcfd8e2755d80b5e4b309e20a69474a6e2eb245e40c1b3f81c6151dbf7e6871e90a9616a32f4a8443d30bfaaff5d711be39bc8f38c13234af9fd867f508b8a6b097a49fb07a1392ec08c38f0939620cf644ec6631f7566b6bc7a1f1d01a9c736eceda4'),\n",
	"(131618812326147470215836136712095159211663684841466199972335887950664101678748935713203393931245541362772506324940879455504378545672259298894346211770983161798960234145317156224604949365110464634198678301644727985645228605590810190481288852412139519629077007437022950591320600450976104529132138396249413028099L, 14318453997383587408499979509282945054981178882287936277795320451723285671391694914929520724692059461777785480850364952738183846512279857119933447174333240691522012746191524101263192457454032837995702952840654708026147079321112397181981380295129696518148352311994008219805602114421675331461920408832158576071L, '71a370974f020d338071e2b0480f38f2d5b488252f5eb206636d6dcd3c93ea586a507c29d2e611a9a8d5d0f849b913116b37e69345d6eae71cf87cdb6b74e75bccdb374c372562777a727f07e4272a5ff17b451d582074b565879453d028c5e9b91cb67ae923f0f09492e508422e65c1daada0564d91a9feec094af77ab190fa'),\n",
	"(99041226655569332839951771030354960649881033648844611842019981984694036670092050113949713459076512100815903654289240773362239468428010238444408944822516190193861719380849620966232652503444079295871086550223067647300451354087943235559953597249075277760677450645744584993036921709483731953822197438848939991653L, 45917328654051873455626365238806652384056265616606200025887647202756379007355041189714541493038574645714670682101129613041399879280497291675656671383417575172090283625761438606371062142083212903854592596935358334738253893062615061401134834123551055465985828525720791523020773994634134135284036947641526947783L, '336e810e66eeac255f1714b290187773de92ec044b654a4cc0eef2070e9d8d86fa37d424b2e4b71fd135e634034e06dbc31e77bd13d470aa5d3e5dcc5e689b565178a4a445d4560f5569967315a0bbe163ef83063429ec8d1fbba1a8dbd9e30a2a67e17793f8b19e7b184c3b989dadc85b7f060e3daefb66ff803c98bda8862f'),\n",
	"]\n",
	"T = len(data) "
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Note that $v_i$ are typically a bit smaller, and we can reduce them by approximating $p+q$ by $2\\sqrt{n}$. Therefore, we should scale the $d$ and $k_i$ columns by a bit smaller numbers. This is important, since the information amount that we obtain is quite tight. In fact, when scaling by $2^{512}$, the resulting basis does not contain the desired result. However, it should still be available in small linear combinations of short vectors, or e.g., by guessing a few bits of $d$ first.\n",
	"\n",
	"Luckily, scaling by $2^{505}$ works well and we find the correct $d$ in 10-th element of the smallest basis vector."
	]
	},
	{
	"cell_type": "code",
	"execution_count": 37,
	"metadata": {},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"Bit sizes:\n",
	"[968, 966, 962, 967, 970, 971, 964, 970, 961, 970]\n",
	"[465]\n",
	"[465, 463, 459, 461, 465, 464, 462, 465, 461, 464]\n",
	"found d row 0 : d = 52734116413990333859776618028885273976613159615407987318262228643225868562829470128730568170502025104920857931843837285163945541735508099991\n",
	"\"hitcon{recover_everything_by_amazing_LLL_algorithm!!}\\n\\x1c}w\\x16\\x1b\\xbbHv\\x85\\x98X\\xae\\x83xH\\xbeZ'\\x83\\x98o\\xf3\\xfe\\xbcW\\x16\\x15\\xb6\\xd9\\x1f\\xcbG\\xa0\\x84\\xbe\\xbd\\x1b\\xba\\xb6\\xed\"\n"
	]
	}
	],
	"source": [
	"m = matrix(ZZ, T+1, 2*T+1)\n",
	"\n",
	"i = 0\n",
	"m[0,T] = 1\n",
	"for ni, ei, ci in data:\n",
	" m[0,i] = -ei\n",
	" # approximate p+q as 2sqrt(n), reduce a bit size of the noise\n",
	" m[1+i,i] = (ni - 2*int(sqrt(ni)))\n",
	" m[1+i,T+1+i] = 1\n",
	" i += 1\n",
	" \n",
	"Cd = 2**505\n",
	"Ck = 2**506\n",
	"for i in range(T):\n",
	" m.set_column(i, m.column(i))\n",
	" m.set_column(T+1+i, m.column(T+1+i) * Cd)\n",
	"m.set_column(T, m.column(T) * Ck)\n",
	"\n",
	"ml = m.LLL()\n",
	"\n",
	"for i in range(T):\n",
	" ml.set_column(i, ml.column(i))\n",
	" ml.set_column(T+1+i, ml.column(T+1+i) / Cd)\n",
	"ml.set_column(T, ml.column(T) / Ck) \n",
	"\n",
	"print(\"Bit sizes:\")\n",
	"print([len(ZZ(v).bits()) for v in ml[0][:T]])\n",
	"print([len(ZZ(v).bits()) for v in ml[0][T:T+1]])\n",
	"print([len(ZZ(v).bits()) for v in ml[0][T+1:]])\n",
	"\n",
	"n, e, ct = data[0]\n",
	"\n",
	"for irow, row in enumerate(ml):\n",
	" d = int(abs(row[T]))\n",
	" if pow(2, e*d, n) == 2:\n",
	" print(\"found d\", \"row\", irow, \":\", \"d =\", d)\n",
	" ct = int(ct, 16)\n",
	" flag = pow(ct, d, n)\n",
	" print(`long_to_bytes(flag)`)\n",
	" break"
	]
	}
	],
	"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
	}