Infobahn CTF 2025 - Kyoko

KyokoEigenvalues.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5ea57893-f2c5-447f-9d79-a621c80ec356",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2025-11-09T18:01:32.830829Z",
     "iopub.status.busy": "2025-11-09T18:01:32.830727Z",
     "iopub.status.idle": "2025-11-09T18:01:33.238933Z",
     "shell.execute_reply": "2025-11-09T18:01:33.238623Z",
     "shell.execute_reply.started": "2025-11-09T18:01:32.830820Z"
    }
   },
   "outputs": [],
   "source": [
    "from sage.all import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "2265984e-1bbb-4441-a56b-1c583146e595",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2025-11-09T18:01:33.239294Z",
     "iopub.status.busy": "2025-11-09T18:01:33.239188Z",
     "iopub.status.idle": "2025-11-09T18:01:33.241392Z",
     "shell.execute_reply": "2025-11-09T18:01:33.241124Z",
     "shell.execute_reply.started": "2025-11-09T18:01:33.239286Z"
    }
   },
   "outputs": [],
   "source": [
    "g = [[904340994107770791252911616082749668795132721221296256067487, 726510118527278616560633019284038416782281874181800960719969433033800981241049307591144805, 421266392918500760628726586543246178175685970778705670812080740836468472070182252359521470937273326995730187700156081616], [116961774366146569716655401608202201385160327031449285563126725460822700358892111574266458, 816005185804573384985596285679022410513958432857740941969174191635130755187012903371947532415715430944250522052012786223, 285079655860840715333252980951774426843925526525786952690479760904623635879091686605301191750219944125092836793966960030535995322734385670633319445701], [27914940780753999719113535868297190072825918514073929367714907017225442967111706674668230809342246006641649619296901870, 753100456525956823638930861813097616885298310849957702482402421553175337603882634945790935882440632896536990353857020248813343137035610591681699083467, 397816674767248800830499740353176228866766834468388278599642822015074158624840491089839092179483938852821933963997269771642396527327113866217865766537971752530345783744552918144155]]\n",
    "gsec = [[36754938330320300224378499077458782121822821519572384874116, 666104148012514454219536044712205489404446090527286652344211193883747328915798926610181090, 597093025239040065804028075393970677561135215140518873573643444139640449147223968113514106326951683600458744502547807223], [520115950464630320513161212555343079854016965727709590071167946274347503933231506226079730, 196901465492113772066002290169038711755692761132697323662430846269972215930580155653575880500305437881960130163985417805, 681643523340868644344118278753022550672325071479698731429550569397449625301502630203602053879788465117161604187027699024654684045513102844945565018499], [585514510876281032280636795117147080413524014840319320606139004571388929862053366190907289618449912570446686286612179144, 190200944329900207319425902827674455336623704044299933384113900450583074871858612853022922312519819031588934745308631731938686695285988632133147226700, 674551507113280066684677454440980021697355396600421504381955937736411119056715125555584572960737291244946959899615924811789611770763511406388666639749144855743461050476448822622460]]\n",
    "ct = bytes.fromhex(\"d372d0eb56a5c0c8e58022dd6786a069d9bad720b02139bb70283fa214ebce97d80f5c17ccb1af3eb20429a98a1ad13e07e3368a5444c5fac2846faf75a35000\")"
   ]
  },
  {
   "cell_type": "raw",
   "id": "282e3bdf-176f-4e5d-9ee0-04fb940095d3",
   "metadata": {},
   "source": [
    "1   q   q^2\n",
    "p   1   q\n",
    "p^2 p   1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "582c61ea-19f4-45f0-b0c2-115aa778cd86",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2025-11-09T18:01:33.241876Z",
     "iopub.status.busy": "2025-11-09T18:01:33.241805Z",
     "iopub.status.idle": "2025-11-09T18:01:33.264936Z",
     "shell.execute_reply": "2025-11-09T18:01:33.264386Z",
     "shell.execute_reply.started": "2025-11-09T18:01:33.241869Z"
    }
   },
   "outputs": [],
   "source": [
    "p = gcd([g[1][0], g[2][0], g[2][1], gsec[1][0], gsec[2][0], gsec[2][1]])\n",
    "q = gcd([g[0][1], g[0][2], g[1][2], gsec[0][1], gsec[0][2], gsec[1][2]])\n",
    "assert is_prime(p) and is_prime(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "37ad4442-0348-4ada-8321-421798bcd882",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2025-11-09T18:01:33.265737Z",
     "iopub.status.busy": "2025-11-09T18:01:33.265525Z",
     "iopub.status.idle": "2025-11-09T18:01:53.860581Z",
     "shell.execute_reply": "2025-11-09T18:01:53.860116Z",
     "shell.execute_reply.started": "2025-11-09T18:01:33.265717Z"
    }
   },
   "outputs": [],
   "source": [
    "candsp = []\n",
    "for r1 in matrix(Zmod(p**3), g).charpoly().roots(multiplicities=False):\n",
    "    for r2 in matrix(Zmod(p**3), gsec).charpoly().roots(multiplicities=False):\n",
    "        try:\n",
    "            candsp.append(r2.log(r1))\n",
    "        except:\n",
    "            continue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4c347ab6-f311-419e-a9b4-62e252376340",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2025-11-09T18:01:53.860968Z",
     "iopub.status.busy": "2025-11-09T18:01:53.860885Z",
     "iopub.status.idle": "2025-11-09T18:02:12.597404Z",
     "shell.execute_reply": "2025-11-09T18:02:12.597045Z",
     "shell.execute_reply.started": "2025-11-09T18:01:53.860959Z"
    }
   },
   "outputs": [],
   "source": [
    "candsq = []\n",
    "for r1 in matrix(Zmod(q**3), g).charpoly().roots(multiplicities=False):\n",
    "    for r2 in matrix(Zmod(q**3), gsec).charpoly().roots(multiplicities=False):\n",
    "        try:\n",
    "            candsq.append(r2.log(r1))\n",
    "        except:\n",
    "            continue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "bf2af996-01cc-4f57-b1c1-e0f9acca9f17",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2025-11-09T18:02:12.597726Z",
     "iopub.status.busy": "2025-11-09T18:02:12.597645Z",
     "iopub.status.idle": "2025-11-09T18:02:12.617858Z",
     "shell.execute_reply": "2025-11-09T18:02:12.617639Z",
     "shell.execute_reply.started": "2025-11-09T18:02:12.597719Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "709258524127151201011322770854884023028746478749930539969052022961169390965518002306430876 118413001718874073999980970265197864108279480038422116287293965466915109709300659825713164 2957540193340299912607433868980976999288407598436684600127348065062524622360474220998418065472102255893586602436768054976170845181070584405973364198542182846621810265420294108\n",
      "b'infobahn{N07_f3311ng_b4d_f0r_07h3r5_m34n5_h4v1ng_n0_r3gr375}\\x04\\x04\\x04\\x04'\n"
     ]
    }
   ],
   "source": [
    "from Crypto.Cipher import AES\n",
    "from hashlib import sha256\n",
    "for cp in candsp:\n",
    "    for cq in candsq:\n",
    "        try:\n",
    "            secret = crt([cp, cq], [p**2*(p-1), q**2*(q-1)])\n",
    "        except:\n",
    "            continue\n",
    "        pt = AES.new(sha256(hex(secret).encode()).digest()[:16], AES.MODE_ECB).decrypt(ct)\n",
    "        if b\"info\" in pt:\n",
    "            print(cp, cq, secret)\n",
    "            print(pt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "dfcc773d-8c74-4e3c-8b82-ffc55da92488",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath Python",
   "language": "python",
   "name": "sagemathpy"
  },
  "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.12.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}