RCTF2020 Crypto solution

infantECC.ipynb

MultipleMultiply.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import bytes_to_long\n",
    "import hashlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#flag = \"flag{M4th_0f_MuLLLtiplication}\"\n",
    "flag = open(\"flag.txt\",\"rb\").read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "while True:\n",
    "    F = GF(random_prime(2^120))\n",
    "    p = int(F.modulus()[0])+1\n",
    "    fac = factor(p-1)[-1][0]\n",
    "    if fac < 2^50 and fac > 2^45:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2^2 * 3 * 11 * 151 * 313 * 5801 * 15192183847 * 49629872653873"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factor(p-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "num = [F.random_element() for i in range(90)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "secret = randint(0, 2^90)\n",
    "r = 1\n",
    "for i in range(90):\n",
    "    if (secret >> i) & 1:\n",
    "        r *= num[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "h = hashlib.sha256(str(secret).encode('utf-8')).digest()\n",
    "hflag = bytes_to_long(h)^^bytes_to_long(flag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finite Field of size 27287355548326904718205455026067397\n",
      "[9964502217119710756123434680636957, 12006301066058420883591007289545346, 26050130178034149597997179198370216, 17414866814143316245455051738424417, 24464873110921046769516355747688490, 19811544596826103041301882775985205, 21896224272490793260249021925804048, 18225894058014786665444640185867746, 16773487061813483982970825548460724, 7379326194051214768004260221561189, 20386765349024857548576736574363892, 26132591830281988369489315897505589, 21791567508929224431169892900954454, 19046611842722730963029461260859665, 19693881535389973702263181872188746, 12299747535049943121140946453388830, 3299704473768068947444138346653054, 8928037515724141299906599257419809, 21613928194690998047752806293083970, 26380594900282858293157555873150100, 14662836377492325044866443794572455, 9275343676286710659876608223972210, 26943453939014220580971949630472256, 13350600668960685904813706078625362, 24572107885690644055598306247438785, 25088087837459127814715058608301640, 13472690930713580044224019576614491, 18631181143621927207911199072119222, 7314873357341570099254453657828184, 21682704576401323048786876116378985, 12342797490387432160525297654004589, 24813093343399642560504323714158717, 24894575199223105785984336103600316, 25643309803136210180869227150540190, 544420881920487708966501825745624, 22882689232362054168646625774957943, 6608219398535905522470612715813957, 11277265668276511771780169087201491, 10413349341514336450780809020205240, 10144920823485222966031354928090046, 14976283684851314409763647865734195, 19776510618133146288471364233231584, 23916572157666044382274529392640436, 13859551791065715774629492704303964, 7526929807978778538528417231455458, 21706644761819851793610762137194108, 15921813678330828817028007571220291, 845951138269363333425945388704895, 3130680138164227228090104297956125, 21191926372635381436791234008810114, 8400644437289548189901797542395379, 5067103436700261749441836593129391, 9767294194593269424809851266920534, 21727725340567270196945077701874035, 1182429994197864219408572276687837, 13291983453328207884285729937714004, 1847043276856328627247949241226613, 24642287245051656812801835996687824, 6115070757414994291505654213959258, 14770642483078897646007192364754982, 6114311983079540724595133700825108, 10543831808826531389965939984666531, 27184823477350449262209006993903105, 21289717115339131124839791047196774, 10815592463382675337537642911028076, 10145224471759745566914587211809976, 18359318850052353553507234413985125, 10281524325153215331652947485075999, 17871748637559442821162457394607722, 4973801612742646075519962618997756, 17927551999842528923488748443903957, 20992445315043895937315681613818098, 21539143564808845675663689824038689, 9389547937910221888936913728144227, 27264202296805994002591871934281662, 11149524620064909768637245752203562, 22091517753147745970661731722385872, 16678577455485714699856153789535403, 5252804852707530454469291604437206, 5816583599300094147112975601549764, 13916331621796462059913443827871072, 22574806267425266391132192709650270, 24642104548938134381852473098817161, 3303235795146860137551164964749731, 4061884435280521104388190830345001, 25723042412913339156150657329561196, 19646489944513594879731256865487179, 3645292247129894792642524671282311, 11288361405384374233423402780984291, 19954556818916459663078210728274157]\n",
      "23575065654670029596063945889146406\n",
      "88594819989105948089396706477456112087088489833478063334411300493140260645660\n"
     ]
    }
   ],
   "source": [
    "print(F)\n",
    "print(num)\n",
    "print(r)\n",
    "print(bytes_to_long(h)^^bytes_to_long(flag))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = F.multiplicative_generator()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "dlpr = r.log(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "dlp = [x.log(g) for x in num]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = Matrix(ZZ, 92, 92)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(90):\n",
    "    M[i,i+1] = 2\n",
    "    M[i,0] = int(dlp[i])*2*5\n",
    "    M[-1,i+1] = 1\n",
    "M[-1,0] = (int(dlpr))*2*5\n",
    "M[-2,0] = int(F.modulus()[0])*2*5\n",
    "M[-1,-1] = 1\n",
    "lm=M.BKZ(block_size=30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, -1, 1, 1, 1, 1, 1, -1, -1, -1, -1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, -1, 1, -1, -1, 1, -1, -1, 1, -1, -1, 1, 1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, 1, 1, -1, -1, -1, -1, 1)\n",
      "1167068617183251246832890817\n"
     ]
    }
   ],
   "source": [
    "print(lm[0])\n",
    "guess = 0\n",
    "if lm[0][0] == 0:\n",
    "    for x in range(90):\n",
    "        if lm[0][x+1] == -lm[0][-1]:\n",
    "            guess += 1<<x\n",
    "        elif lm[0][x+1] != lm[0][-1]:\n",
    "            guess = 0\n",
    "            break\n",
    "if guess:\n",
    "    print(guess)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import long_to_bytes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'flag{M4th_0f_MuLLLtiplication}'"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "long_to_bytes(bytes_to_long(hashlib.sha256(str(guess).encode('utf-8')).digest())^^hflag)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.0",
   "language": "sage",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}