SecFest SmallRSA

small_rsa.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b6b8e459-f204-467c-9b87-f95aa2c26280",
   "metadata": {},
   "outputs": [],
   "source": [
    "from sage.all import *\n",
    "from binteger import Bin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "dcefa032-5052-4d52-87c7-8e6c8275fffc",
   "metadata": {},
   "outputs": [],
   "source": [
    "B0 = 299089579545315329927831077361748367952\n",
    "B = 89454576592593506198091003676782760426164579104178557226654770323935580674319\n",
    "enc = 20028745085195583678378916660396397538994010666442432435713640627343638544983255393172148533881365971854283869014758186049316988000737550769605639679479180589253955045598774721246899297252406061180515011481963360240256930643234163280545121729316133742144823763601498670419742214338058035882729739026231634052850909950379775962557912899396425158183194713786156167265753101307366270122197291552260459611820717997757267712339753750891161458350673859656475246424157412488302546155825912483333623112241511338503582503574264361642880778925970123483773426929656284901291439896260232211956880277503017106751458194801408711006508735697948503777541874602351630564440747713117941961365774432080957568074493024639496001096643016830901025267139229529531498995611208677992804905291286283800620644472474016518205177496080326978650925595478508487654201440611536444236269249350798132974110183405726386731371083064781799161730272554725154294836754680153505618540394615227117220937285324830238267813179531144987439258005506277060338763635818845237827323991005526601556189238304698762279589753458427889093496877392067155432030319457380945056863466258912867795091887061462273\n",
    "n = 34636826522268200537774154204941407529988822872148894567372441583415254552447302749228340228906546920018188955427366065775864988572478602396106371080685655564033817360335889100181326997156956367867826271804748628399970980872535732627789819667138755054766468613617857322669943746935541793686046017146304058463046888768033823974071280198556883407966869840605294817458160107581025567028344865676401747062383757953634109234225473151412286700057343914024601771084294978143682676406989676297209210216751760067457688993962995389392757065579902776423369572207772618783218733875876004666171649676348837063312375577831738151728184702454332533310164381393954188000484797023852778358325185035355456975120195736428957973841058260571165844580731851332614644310138023335666774129908073810240673290494869672972129721881195738377137440359704474859842375310892200036137555884160008753002740372280734559191112796694291489720084349580961011222521816640149582773655766774142060407687849118888102012006683658983742498222152936133450205031770557715936326829853770866589383519670805541691607883632863177387841208657406032490492781368768715851417369111054048036698365329818004529"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5051f672-224e-4299-96da-17851f10a5a8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2 * 3 * 73 * 83 * 331 * 3767 * 11927 * 2111023 * 4504321 * 104714017 * 117745941129232061 * 78310696142599100678759"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(n % B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5e65039b-589f-4a54-9950-abc8fda9f054",
   "metadata": {},
   "outputs": [],
   "source": [
    "ds = divisors(n % B)"
   ]
  },
  {
   "cell_type": "raw",
   "id": "ebb6421e-6eea-4b1c-85a5-e00500067a49",
   "metadata": {},
   "source": [
    "p0q0 + B * (p0q1 + p1q0) + B**2 * (p0q2 + p1q1 + p2q0) + ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "25c80c00-d134-4630-8124-0a9eb8800f92",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "73"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cands0 = []\n",
    "for p0 in ds:\n",
    "    q0 = (n % B) // p0\n",
    "    if p0 > q0:\n",
    "        continue\n",
    "    if max(p0, q0) >= B0:\n",
    "        continue\n",
    "    cands0.append((p0, q0))\n",
    "len(cands0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b2c4f19c-dc31-463c-8da4-a5fedd29a1d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_lin(p0, q0, c):\n",
    "    a = 1\n",
    "    b = (c - a*p0) * inverse_mod(q0, B) % B\n",
    "    assert (a * p0 + b * q0) % B == c\n",
    "    \n",
    "    l = lcm(p0, q0)\n",
    "    M = B\n",
    "    mat = matrix(ZZ, [\n",
    "        [a, b, M],\n",
    "        [l // p0, -l // q0, 0],\n",
    "        [B, 0, 0],\n",
    "        [0, B, 0],\n",
    "    ]).LLL()\n",
    "\n",
    "    KB = 1 # enumerate a few small sols\n",
    "    for k in range(-KB, KB+1):\n",
    "        for k2 in range(-KB, KB+1):\n",
    "            a, b, t = mat[3] + k*mat[1] + k2 * mat[2]\n",
    "            if abs(t) != M:\n",
    "                continue\n",
    "            if t == -M:\n",
    "                a, b = -a, -b\n",
    "            assert (a * p0 + b * q0) % B == c\n",
    "            if 0 < min(a,b) <= max(a, b) < B0:\n",
    "                assert (a * p0 + b * q0) % B == c\n",
    "                yield a, b\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "b1bc45fb-0f73-4a2c-be8b-08aabcee4f3f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def extend(cands0, e):\n",
    "    for p, q in cands0:\n",
    "        nn = (n - p * q) // B**e\n",
    "        p0 = p % B\n",
    "        q0 = q % B\n",
    "        for qe, pe in solve_lin(p0, q0, nn % B):\n",
    "            qq = q + B**e*qe\n",
    "            pp = p + B**e*pe\n",
    "            assert n % (B**e*B) == (pp * qq) % (B**e*B)\n",
    "            yield pp, qq\n",
    "\n",
    "cands1 = list(extend(cands0, e=1))\n",
    "len(cands1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "4a51d580-864c-40f1-a8fb-ef9b6229c6a9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 25\n",
      "2 23\n",
      "3 23\n",
      "4 20\n",
      "5 20\n",
      "6 20\n",
      "7 21\n"
     ]
    }
   ],
   "source": [
    "cands = cands0\n",
    "for e in range(1, 8):\n",
    "    cands = list(extend(cands, e))\n",
    "    print(e, len(cands))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "31c1459f-e167-4a48-a789-dce2b889f677",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "good\n",
      "b'SECFEST{small_coefficients_equivalent_to_polynomial_multiplication}'\n"
     ]
    }
   ],
   "source": [
    "for p, q in cands:\n",
    "    if p * q == n:\n",
    "        print(\"good\")\n",
    "        d = inverse_mod(0x10001, n - p - q + 1)\n",
    "        print(Bin(pow(enc, d, n)).bytes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3935b981-758f-4094-afb2-d9fd8cff491a",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath",
   "language": "python",
   "name": "sagemath"
  },
  "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.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}