Party Ticket.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getSafePrime(bits):\n",
    "    while True:\n",
    "        p = random_prime(2^bits)\n",
    "        q = 2*p + 1\n",
    "        if is_prime(q):\n",
    "            return q\n",
    "\n",
    "p1, q1, p2, q2 = [getSafePrime(512) for _ in range(4)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "metadata": {},
   "outputs": [],
   "source": [
    "#n1 = p1 * q1\n",
    "#n2 = p2 * q2\n",
    "\n",
    "min_n = min(n1, n2)\n",
    "m = randint(2, 2 ^ (512 + 40 * 8))\n",
    "#b1 = randint(2, n1 - 1)\n",
    "#b2 = randint(2, n2 - 1)\n",
    "\n",
    "#c1 = (m * (m + b1)) % n1\n",
    "#c2 = (m * (m + b2)) % n2\n",
    "\n",
    "c1, n1, b1 = (39795129165179782072948669478321161038899681479625871173358302171683237835893840832234290438594216818679179705997157281783088604033668784734122669285858548434085304860234391595875496651283661871404229929931914526131264445207417648044425803563540967051469010787678249371332908670932659894542284165107881074924, 68660909070969737297724508988762852362244900989155650221801858809739761710736551570690881564899840391495223451995828852734931447471673160591368686788574452119089378643644806717315577499800198973149266893774763827678504269587808830214845193664196824803341291352363645741122863749136102317353277712778211746921, 67178092889486032966910239547294187275937064814538687370261392801988475286892301409412576388719256715674626198440678559254835210118951299316974691924547702661863023685159440234566417895869627139518545768653628797985530216197348765809818845561978683799881440977147882485209500531050870266487696442421879139684)\n",
    "c2, n2, b2 = (36129665029719417090875571200754697953719279663088594567085283528953872388969769307850818115587391335775050603174937738300553500364215284033587524409615295754037689856216651222399084259820740358670434163638881570227399889906282981752001884272665493024728725562843386437393437830876306729318240313971929190505, 126991469439266064182253640334143646787359600249751079940543800712902350262198976007776974846490305764455811952233960442940522062124810837879374503257253974693717431704743426838043079713490230725414862073192582640938262060331106418061373056529919988728695827648357260941906124164026078519494251443409651992021, 126361241889724771204194948532709880824648737216913346245821320121024754608436799993819209968301950594061546010811840952941646399799787914278677074393432618677546231281655894048478786406241444001324129430720968342426822797458373897535424257744221083876893507563751916046235091732419653547738101160488559383290)\n",
    "N = n1 * n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "metadata": {},
   "outputs": [],
   "source": [
    "P.<x> = PolynomialRing(Zmod(N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 231,
   "metadata": {},
   "outputs": [],
   "source": [
    "coef1 = crt([1, 0], [n1, n2])\n",
    "coef2 = crt([0, 1], [n1, n2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 233,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4206037578318332575658329651734650178005312063375076513492646422671019785611184012432059187668801186403426916486999247372548083961053867933480434984588457639307729143043774447491833097904051745248863198266481804918105019510291012428326672465339911420088400260061051897801723603990716064569614691748737472632730332284931705506861768730564420608888381220873705215209011683272713432952565036332827519830617790878090468436374529591377291061015881477299137991821153656274937556770812608219369139390852857408107091189118438476817891605685551425842788640982006484088533501017404322243479105832100472341543055990746276093574"
      ]
     },
     "execution_count": 233,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(coef1 * (m^2 + m*b1 - c1) + coef2 * (m^2 + m*b2 - c2)) % N"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 234,
   "metadata": {},
   "outputs": [],
   "source": [
    "pol = coef1 * (x^2 + x*b1 - c1) + coef2 * (x^2 + x*b2 - c2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 235,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x^2 + 7762308240846775144296698047579357257464726588443527417187872156955097695182206519537865041117084020329643087768522937256571450192166784510896920953082530219748132422316077097680382406025512173793183999466958291002265921212400035894369757246914011237107874921260362932580606734475934529351294385515229912973948536923951376728587088960168080828434992508344672880594133484233200421813530405169097590233779892603140609663858364009949998079116575114866920680061371304881837318790613546750428664638190769966972999760228799215606384727745296708502682304975295307334131114908755191546431894952900195410165089175778519893921*x + 4882384166295036387238907507673870929455665069959332106919901825734412366467863322644120413909504392901301662606897760165846107475045674732573455368082512611103710328693050134730406274604816383451358274882873938515958679149719888350105172990061878859465267801198504727402068964213357234935599313765613007236374680953616052943586810204674772628743263546927694662684907555333925874661449625300602832998889846922026637220136247402915378626495824151233949439763441645774999997402821515089233021136647178619054632708377908559041538616496791037073278749500606076986044957556675054434812236362122494338959704461297163637378"
      ]
     },
     "execution_count": 235,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [],
   "source": [
    "debug = True\n",
    "\n",
    "# display matrix picture with 0 and X\n",
    "def matrix_overview(BB, bound):\n",
    "    pass\n",
    "\n",
    "def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):\n",
    "    \"\"\"\n",
    "    Coppersmith revisited by Howgrave-Graham\n",
    "    \n",
    "    finds a solution if:\n",
    "    * b|modulus, b >= modulus^beta , 0 < beta <= 1\n",
    "    * |x| < XX\n",
    "    \"\"\"\n",
    "    #\n",
    "    # init\n",
    "    #\n",
    "    dd = pol.degree()\n",
    "    nn = dd * mm + tt\n",
    "\n",
    "    #\n",
    "    # checks\n",
    "    #\n",
    "    if not 0 < beta <= 1:\n",
    "        raise ValueError(\"beta should belongs in (0, 1]\")\n",
    "\n",
    "    if not pol.is_monic():\n",
    "        raise ArithmeticError(\"Polynomial must be monic.\")\n",
    "\n",
    "    #\n",
    "    # calculate bounds and display them\n",
    "    #\n",
    "    \"\"\"\n",
    "    * we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)\n",
    "    * we know LLL will give us a short vector v such that:\n",
    "    ||v|| <= 2^((n - 1)/4) * det(L)^(1/n)\n",
    "    * we will use that vector as a coefficient vector for our g(x)\n",
    "    \n",
    "    * so we want to satisfy:\n",
    "    2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)\n",
    "    \n",
    "    so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)\n",
    "    (it's important to use N because we might not know b)\n",
    "    \"\"\"\n",
    "    if debug:\n",
    "        # t optimized?\n",
    "        print(\"\\n# Optimized t?\\n\")\n",
    "        print(\"we want X^(n-1) < N^(beta*m) so that each vector is helpful\")\n",
    "        cond1 = RR(XX^(nn-1))\n",
    "        print(\"* X^(n-1) = \", cond1)\n",
    "        cond2 = pow(modulus, beta*mm)\n",
    "        print(\"* N^(beta*m) = \", cond2)\n",
    "        print(\"* X^(n-1) < N^(beta*m) \\n-> GOOD\" if cond1 < cond2 else \"* X^(n-1) >= N^(beta*m) \\n-> NOT GOOD\")\n",
    "        \n",
    "        # bound for X\n",
    "        print(\"\\n# X bound respected?\\n\")\n",
    "        print(\"we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M\")\n",
    "        print(\"* X =\", XX)\n",
    "        cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)\n",
    "        print(\"* M =\", cond2)\n",
    "        print(\"* X <= M \\n-> GOOD\" if XX <= cond2 else \"* X > M \\n-> NOT GOOD\")\n",
    "\n",
    "        # solution possible?\n",
    "        print(\"\\n# Solutions possible?\\n\")\n",
    "        detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))\n",
    "        print(\"we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)\")\n",
    "        cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))\n",
    "        print(\"* 2^((n - 1)/4) * det(L)^(1/n) = \", cond1)\n",
    "        cond2 = RR(modulus^(beta*mm) / sqrt(nn))\n",
    "        print(\"* N^(beta*m) / sqrt(n) = \", cond2)\n",
    "        print(\"* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \\n-> SOLUTION WILL BE FOUND\" if cond1 < cond2 else \"* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \\n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)\")\n",
    "\n",
    "        # warning about X\n",
    "        print(\"\\n# Note that no solutions will be found _for sure_ if you don't respect:\\n* |root| < X \\n* b >= modulus^beta\\n\")\n",
    "    \n",
    "    #\n",
    "    # Coppersmith revisited algo for univariate\n",
    "    #\n",
    "\n",
    "    # change ring of pol and x\n",
    "    polZ = pol.change_ring(ZZ)\n",
    "    x = polZ.parent().gen()\n",
    "\n",
    "    # compute polynomials\n",
    "    gg = []\n",
    "    for ii in range(mm):\n",
    "        print('Appending', ii)\n",
    "        for jj in range(dd):\n",
    "            gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)\n",
    "    for ii in range(tt):\n",
    "        gg.append((x * XX)**ii * polZ(x * XX)**mm)\n",
    "    \n",
    "    # construct lattice B\n",
    "    BB = Matrix(ZZ, nn)\n",
    "\n",
    "    for ii in range(nn):\n",
    "        for jj in range(ii+1):\n",
    "            BB[ii, jj] = gg[ii][jj]\n",
    "\n",
    "    # display basis matrix\n",
    "    if debug:\n",
    "        matrix_overview(BB, modulus^mm)\n",
    "\n",
    "    # LLL\n",
    "    BB = BB.LLL()\n",
    "\n",
    "    # transform shortest vector in polynomial    \n",
    "    new_pol = 0\n",
    "    for ii in range(nn):\n",
    "        new_pol += x**ii * BB[0, ii] / XX**ii\n",
    "\n",
    "    # factor polynomial\n",
    "    potential_roots = new_pol.roots()\n",
    "    print(\"potential roots:\", potential_roots)\n",
    "\n",
    "    # test roots\n",
    "    roots = []\n",
    "    for root in potential_roots:\n",
    "        if root[0].is_integer():\n",
    "            result = polZ(ZZ(root[0]))\n",
    "            if gcd(modulus, result) >= modulus^beta:\n",
    "                roots.append(ZZ(root[0]))\n",
    "\n",
    "    # \n",
    "    return roots"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 236,
   "metadata": {},
   "outputs": [],
   "source": [
    "dd = pol.degree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "metadata": {},
   "outputs": [],
   "source": [
    "beta = 1\n",
    "epsilon = 5e-2\n",
    "mm = ceil(beta**2 / (dd * epsilon))\n",
    "tt = floor(dd * mm * ((1/beta) - 1))\n",
    "XX = ceil(N**((beta**2/dd) - epsilon))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 244,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "# Optimized t?\n",
      "\n",
      "we want X^(n-1) < N^(beta*m) so that each vector is helpful\n",
      "* X^(n-1) =  1.95496521975057e5266\n",
      "* N^(beta*m) =  2540042463520916738411275294239349544900471575409188239176195214125655226888387397840869771740657778083760163176768201611028316531894337687097279404189477452767274476540153091906112154225721184621538967114904315356486923241106306344362740642795046772791789227851275204648862738465335058483674158974087310883675582121660845354521001857232681027534726484353339527545750622950224876361170458045659565756682782169854154749020362555581444428162201233546936801668903066257532904688028708914520970935168850394715075078212122667257117497487018841698812653539367697660207524483174245736122331101608176626880093533829575389337490016354736475647298691185384793141506921510416297468530416261143171964608196381093330870446309434085876691792482927326539633738497480356205638451316012393783418500788946928744305720510176896820955247452523932695458364797081676227055700887084950519092868371416014574553760983502627054700066631775497905414617664284793157122454070832248752653288259286912286937727339694132994190665606039093006869326910363421518832044710558522298351278355115865279732377884841522953618078686398432637676608386659794552765139985444313826792222448209550204572716344855325555535317375797418525445495414304060570245061520677221991324508605344494624031784107975414247314610721449482577586989008465595982910371436014114127088843247036091872878202455280922916662180073131034780373089958090532960097251737023402215323334341245783435823156622873596411952789051983936855558955954949701470757870316536339214488338310939665702285021794276433144032764487349595874658640395742778266310855268219317142367063535224122529351921383797059325876380138384811554841596953049073600664012587702184436072781111830749978903086981401670453899242688731839934578430026293297284779202105420700404196191176675686754011892426921440744345490483049898826953591899555898295112023104291362610148186869295317005844470148084388320640666737352683184742841389148994047536275066244772144362376580009774852867767181622613393300783263721476280811651705241769150982938600706585166072526449191143654218571844841313217867115587872161521775553147323815968609175633523704573028393737660479253757101758998683028540664203476656066073453705299380959834288254916361567975319456080977094100463697298709490344408113532651442372324684436323451847000591352851861632178066056764497734816438073965236132668487594198833154956147320535310124099134815592463306635673500047640773271174876672058120957609150592036131783479565878338004263269343524777210786839349822684215596124990367293389910707182115173073781799948179104803454224708746206557027868648660432806552889481797908178816416510819354381412482321442238347772038095713281648589032384717932288661077193706525011365111322982713452743389456573602254070248802277215675406396145831188944499727538961450180846039101883940338667484278137644868324063108301530409122159079471048496458037448751970500353366476571519862858659989491047157932668519568057278257524725652159741848766490643113987443971519374155713401051569820375185693951060378015741848516983372377645682343492315956007244465003036644895160440348946104105358859596021434195342935489656517454801343480228317298322770489015465734375324835247694652339072344628862794277442427170625261534722826820890935133824208128651967935687523367438568291886804347696411940535101373203577576080033697091157909930817863982421318159976799317388133827358733030186985721978636485124078222103933875156726194617726539444182240589357194298291596844311628550871475918579666725593584201872181174289339523512446500790627178358638823010765590332343314747489092344418723654523132581373501395238475425906581695253209567736909117760040196885374245609152617495001113182050006091461645295824294696596969513091466112184991465683753618461552935913730193426185113851561106070458665132891692093358910929337848510038619456569376531177030090880926244020452536554687735123834660224139420733229280473785418329201726907395956190119693671999585541659227899576428915130897302038880160091137711127336409005294901987577779570833512564284106235484394729857026522486027938678889664296707917122386490507390918700574055494236730855391494867709649428668642847228810316348408883388005484874042105056236484939042474814397154504656640955720276129176850247184976332123909038997399497589553535543562875500923994779135602710232932455714079683290694085350531159592646266396415129640055759531480934660143443228208709522335497427284106933942493998690484775544143631315472732851221555675521669242532873920299772243490786994558953449007262647524010775641585998534869627764863743576648444659275730239539335223686415324689371948057750804362743389770549301254517983342279920424858544597594887494164931773471940433911217502253256217242101408409633562795575141429090779225070819014705591324155630377610638294197611113815446489786358950360283604388682852830127138784540514450001267552491221907824506725684175688535762506159422770969908199680822535569505138651451362028478826651680622262439088572911829221282263968345401369484565637031387834212639461085658063096312538085775310560477553547432419245052988427314428670836998781314761704198616515163240101172843362850369264894057806290606979682495211401850674540363548008811849849203995815177524972818092065860562409357443267218009802719581817181747376645169198072933278837951718227295308190644652979784799993770738676653807299134014208156488223590299189031684517352490504594660168336500905091667353878017004848882979397690277322506373119982995800325454881364840917954087980431813966895520927998149807866935376001748432290573354390900373081119000361006800926568441328748295887252616060839180678586491679915998015572974764934541112410353353557404671594679145731753045287285793410210712565905672332157872164915580099903609423600895570214000735537698581473608754770178268049649213621937188249824018314768052858855677374417400855711122503025765669134084620074675386079092871170716249182996577884453860114473771415538163767518866190163071644539005933183672974264610052394409353599987031765690526049092436694368589221374247393710370540183745866575004456487502947895843989374470277426856575901307276422843682105057278458724940735147011202455401\n",
      "* X^(n-1) < N^(beta*m) \n",
      "-> GOOD\n",
      "\n",
      "# X bound respected?\n",
      "\n",
      "we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M\n",
      "* X = 14901083349891084070697565462646396735811158083086452272953284984073213124872572874378522954883992548348680098320775142438797637885609035600013149094152784218273630007175409758431644953949341308112531106083605854995035730709079182271139452763647716675637156970235681080854183936\n",
      "* M = 2.88570508908242e291\n",
      "* X <= M \n",
      "-> GOOD\n",
      "\n",
      "# Solutions possible?\n",
      "\n",
      "we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)\n",
      "* 2^((n - 1)/4) * det(L)^(1/n) =  1.77061661203620e6022\n",
      "* N^(beta*m) / sqrt(n) =  5.67970761416880e6158\n",
      "* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n",
      "-> SOLUTION WILL BE FOUND\n",
      "\n",
      "# Note that no solutions will be found _for sure_ if you don't respect:\n",
      "* |root| < X \n",
      "* b >= modulus^beta\n",
      "\n",
      "Appending 0\n",
      "Appending 1\n",
      "Appending 2\n",
      "Appending 3\n",
      "Appending 4\n",
      "Appending 5\n",
      "Appending 6\n",
      "Appending 7\n",
      "Appending 8\n",
      "Appending 9\n",
      "potential roots: [(8288019666414250297759292171687475421492232818737821326621996108402380171721836673645567042633149756411614430575568279199859305892583735709780527038824655329947112470481701438783511180691576641391543556967743369328894120863038015520008430190710859664128765078745, 1)]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[8288019666414250297759292171687475421492232818737821326621996108402380171721836673645567042633149756411614430575568279199859305892583735709780527038824655329947112470481701438783511180691576641391543556967743369328894120863038015520008430190710859664128765078745]"
      ]
     },
     "execution_count": 244,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 211,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N ^ (0.5 - epsilon) > m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.100000000000000"
      ]
     },
     "execution_count": 212,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "epsilon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2429804041576502372244773002217952078172000400164677635979873377598062952057401111602518244858493481867025067499733193979540043745700461077865982976978277646701337182638526623831074915868030902862158426156722102477183469498963936753931281527472128"
      ]
     },
     "execution_count": 213,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "XX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4672549724921393839971609512330373952774319131308857924989720434536302585186906007871617621959407882195346101097668854594064228742258693493846629805212013865451291710128270678518174442155245122304452515357547278575512627432746336594034318703900841240"
      ]
     },
     "execution_count": 214,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.4",
   "language": "sage",
   "name": "sagemath-9.4"
  },
  "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": 4
}