SekaiCTF Zeroday crypto polynomials using Grobner basis

sekai_sbg_groebner.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "caa9b4b5-f1a6-4903-abb3-85fc83c1e72f",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-27T08:57:27.479313Z",
     "iopub.status.busy": "2024-08-27T08:57:27.479008Z",
     "iopub.status.idle": "2024-08-27T08:57:27.486778Z",
     "shell.execute_reply": "2024-08-27T08:57:27.486328Z",
     "shell.execute_reply.started": "2024-08-27T08:57:27.479293Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(k, [x1, x2, x3, x4, x5, x6, x7, x8, x9, x10])"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N = 10\n",
    "p = next_prime(2**32)\n",
    "R = PolynomialRing(QQ, names=[\"k\"] + [\"x%d\" % i for i in range(1, N+1)], order=\"degrevlex\")\n",
    "k, *xs = R.gens()\n",
    "k, xs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ff9bd29-a9e3-49fe-9810-90ed82eed821",
   "metadata": {},
   "source": [
    "Switching to QQ for experiments (support is worse for GF(p))."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ca776c07-49cc-448b-a152-1f01eeeb5858",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-27T08:57:27.487493Z",
     "iopub.status.busy": "2024-08-27T08:57:27.487342Z",
     "iopub.status.idle": "2024-08-27T08:57:27.499144Z",
     "shell.execute_reply": "2024-08-27T08:57:27.498771Z",
     "shell.execute_reply.started": "2024-08-27T08:57:27.487482Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[k*x1 + 3302349220*k + x1 + 3302349219,\n",
       " k*x2 + 491992704*k + 2*x2 + 983985407,\n",
       " k*x3 + 502719671*k + 3*x3 + 1508159012,\n",
       " k*x4 + 366922857*k + 4*x4 + 1467691427,\n",
       " k*x5 + 2697476265*k + 5*x5 + 13487381324,\n",
       " k*x6 + 503190041*k + 6*x6 + 3019140245,\n",
       " k*x7 + 4116397481*k + 7*x7 + 28814782366,\n",
       " k*x8 + 1998266983*k + 8*x8 + 15986135863,\n",
       " k*x9 + 1496342497*k + 9*x9 + 13467082472,\n",
       " k*x10 + 1380928961*k + 10*x10 + 13809289609]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "As = [QQ(GF(p).random_element()) for _ in range(N)]\n",
    "\n",
    "eqs = [(k+i) * (xs[i-1] + As[i-1]) - 1 for i in range(1,N+1)]\n",
    "eqs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "874fe018-27a8-44d1-9df4-e2604d85c104",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-27T08:09:31.499791Z",
     "iopub.status.busy": "2024-08-27T08:09:31.499328Z",
     "iopub.status.idle": "2024-08-27T08:09:31.502925Z",
     "shell.execute_reply": "2024-08-27T08:09:31.502304Z",
     "shell.execute_reply.started": "2024-08-27T08:09:31.499777Z"
    }
   },
   "source": [
    "Ideal with eliminated k seems to be generated by all pairwise resultants."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "f48cc310-968c-4e94-9b92-d34b4dcd7dfd",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-27T08:57:27.499958Z",
     "iopub.status.busy": "2024-08-27T08:57:27.499638Z",
     "iopub.status.idle": "2024-08-27T08:57:27.510276Z",
     "shell.execute_reply": "2024-08-27T08:57:27.509940Z",
     "shell.execute_reply.started": "2024-08-27T08:57:27.499934Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x1*x2 + 491992703*x1 + 3302349221*x2 + 1624731719489734364\n",
      "x1*x3 + 1005439341/2*x1 + 6604698441/2*x3 + 3320311824011383691/2\n",
      "x2*x3 + 502719670*x2 + 491992705*x3 + 247334410300007351\n",
      "x1*x4 + 1100768570/3*x1 + 9907047661/3*x4 + 3635122228906938257/3\n",
      "x2*x4 + 733845713/2*x2 + 983985409/2*x4 + 361046737024600809/2\n",
      "x3*x4 + 366922856*x3 + 502719672*x4 + 184459337817623233\n",
      "x1*x5 + 10789905059/4*x1 + 13209396881/4*x5 + 35632034558160180245/4\n",
      "x2*x5 + 8092428794/3*x2 + 1475978113/3*x5 + 1327138642328331747\n",
      "x3*x5 + 5394952529/2*x3 + 1005439343/2*x5 + 1356074381568487112\n",
      "x4*x5 + 2697476264*x4 + 366922858*x5 + 989765700174042513\n",
      "x1*x6 + 2515950204/5*x1 + 16511746101/5*x6 + 8308546194241430921/5\n",
      "x2*x6 + 2012760163/4*x2 + 1967970817/4*x6 + 990263315601040793/4\n",
      "x3*x6 + 1509570122/3*x3 + 1508159014/3*x6 + 252963531862153301\n",
      "x4*x6 + 1006380081/2*x4 + 733845715/2*x6 + 184631927525800729\n",
      "x5*x6 + 503190040*x5 + 2697476266*x6 + 1357343190187590641\n",
      "x1*x7 + 24698384885/6*x1 + 19814095321/6*x7 + 81562692064355937181/6\n",
      "x2*x7 + 20581987404/5*x2 + 2459963521/5*x7 + 10126187640704297897/5\n",
      "x3*x7 + 16465589923/4*x3 + 2010878685/4*x7 + 4138787976513936407/2\n",
      "x4*x7 + 12349192442/3*x4 + 1100768572/3*x7 + 4531200976577844275/3\n",
      "x5*x7 + 8232794961/2*x5 + 5394952531/2*x7 + 11103884503012749073\n",
      "x6*x7 + 4116397480*x6 + 503190042*x7 + 2071330220849894161\n",
      "x1*x8 + 13987868880/7*x1 + 23116444541/7*x8 + 46192827887328540583/7\n",
      "x2*x8 + 11989601897/6*x2 + 2951956225/6*x8 + 5898796659186826471/6\n",
      "x3*x8 + 9991334914/5*x3 + 2513598356/5*x8 + 5022840602815160277/5\n",
      "x4*x8 + 7993067931/4*x4 + 1467691429/4*x8 + 1466419661717932925/2\n",
      "x5*x8 + 5994800948/3*x5 + 8092428796/3*x8 + 16170833272627766203/3\n",
      "x6*x8 + 3996533965/2*x6 + 1006380083/2*x8 + 1005508045852254774\n",
      "x7*x8 + 1998266982*x7 + 4116397482*x8 + 8225661173068539325\n",
      "x1*x9 + 11970739975/8*x1 + 26418793761/8*x9 + 39531563820760411997/8\n",
      "x2*x9 + 10474397478/7*x2 + 3443948929/7*x9 + 5153327139468343009/7\n",
      "x3*x9 + 8978054981/6*x3 + 3016318027/6*x9 + 2256722423882286874/3\n",
      "x4*x9 + 7481712484/5*x4 + 1834614286/5*x9 + 549042264275637857\n",
      "x5*x9 + 5985369987/4*x5 + 10789905061/4*x9 + 4036348369668050263\n",
      "x6*x9 + 4489027490/3*x6 + 1509570124/3*x9 + 2258833928239569587/3\n",
      "x7*x9 + 2992684993/2*x7 + 8232794963/2*x9 + 6159540484054022565\n",
      "x8*x9 + 1496342496*x8 + 1998266984*x9 + 2990091806512952065\n",
      "x1*x10 + 12428360648/9*x1 + 29721142981/9*x10 + 41042787093182423521/9\n",
      "x2*x10 + 11047431687/8*x2 + 3935941633/8*x10 + 5435255789323340609/8\n",
      "x3*x10 + 9666502726/7*x3 + 3519037698/7*x10 + 694220153073750301\n",
      "x4*x10 + 8285573765/6*x4 + 2201537143/6*x10 + 1520083199559487783/3\n",
      "x5*x10 + 6904644804/5*x5 + 13487381326/5*x10 + 18625115478426506021/5\n",
      "x6*x10 + 5523715843/4*x6 + 2012760165/4*x10 + 694869700723112131\n",
      "x7*x10 + 4142786882/3*x7 + 12349192444/3*x10 + 5684452495588524401\n",
      "x8*x10 + 2761857921/2*x8 + 3996533967/2*x10 + 2759464748326125652\n",
      "x9*x10 + 1380928960*x9 + 1496342498*x10 + 2066342689566942081\n"
     ]
    }
   ],
   "source": [
    "I = Ideal(eqs).elimination_ideal([k])\n",
    "gb = I.groebner_basis()\n",
    "for g in gb:\n",
    "    print(g)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "beb35607-3ad0-48c7-84ed-df07f1d69bf3",
   "metadata": {},
   "source": [
    "We will start with these equations (call them level-1), which evaluate to 0 mod $p^1$. Then we'll multiply each current level-d equation with a level-1 equation (have zero mod $p^{d+1}$), and compute the Groebner basis of it, in graded order (we care about the total degree). Then we'll keep only the degree-(d+2) equations from the basis and use them as level-(d+1) equations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5031eaa1-bb57-442e-bd87-603d36461b63",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-08-27T08:57:27.510935Z",
     "iopub.status.busy": "2024-08-27T08:57:27.510747Z",
     "iopub.status.idle": "2024-08-27T08:58:30.801359Z",
     "shell.execute_reply": "2024-08-27T08:58:30.800870Z",
     "shell.execute_reply.started": "2024-08-27T08:57:27.510924Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "level 1 (degree 2): 45\n",
      "level 2 (degree 3 ): 84 / 237\n",
      "level 3 (degree 4 ): 70 / 910\n",
      "level 4 (degree 5 ): 21 / 1386\n",
      "level 5 (degree 6 ): 1 / 661\n"
     ]
    }
   ],
   "source": [
    "gbcur = gb\n",
    "print(\"level\", 1, \"(degree 2):\", len(gb))\n",
    "for d in range(1, 5):\n",
    "    eqs = set()\n",
    "    for eq1 in gbcur:\n",
    "        for eq2 in gb:\n",
    "            eqs.add(eq1 * eq2)\n",
    "    gbnew = Ideal(list(eqs)).groebner_basis()\n",
    "    \n",
    "    good = [g for g in gbnew if g.degree() <= d + 2]\n",
    "    \n",
    "    print(\"level\", d+1, \"(degree\", d+2, \"):\", len(good), \"/\", len(gbnew))\n",
    "    gbcur = good"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7a40d501-a83d-43d2-a61a-1f45a56068f1",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageConda",
   "language": "python",
   "name": "sageconda"
  },
  "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.10.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}