RCTF2020 Crypto solution

infantECC.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Util.number import getStrongPrime, bytes_to_long, long_to_bytes\n",
    "from hashlib import sha256"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#flag=b\"flag{Copper5mith_M3thod_f0r_ECC}\"\n",
    "flag = open(\"flag.txt\",\"rb\").read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "p=q=1\n",
    "while p % 3 == 1 or q % 3 == 1:\n",
    "    p=getStrongPrime(512)\n",
    "    q=getStrongPrime(512)\n",
    "R=Zmod(p*q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "Mx=R.random_element()\n",
    "My=R.random_element()\n",
    "b=My^2-Mx^3\n",
    "\n",
    "E=EllipticCurve(R, [0,b])\n",
    "Ep=EllipticCurve(GF(p), [0,b])\n",
    "Eq=EllipticCurve(GF(q), [0,b])\n",
    "Ecard=Ep.cardinality()*Eq.cardinality()\n",
    "\n",
    "r=random_prime((p^^q)>>100)\n",
    "s=inverse_mod(r, Ecard)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(75955160398499284582365252139080970001650760916103485139764772804872919753584583266880450168691594499273667135971973410322196200867273228602818191337500001985277231136312528247776522365265305999130251922539242906774436240079513662278472385074144007520670892131774622475195904194782409160126720307889422458493, 77177027104677568205407604834674529531364563093957497500999166982602504419069856531944277180657371948259751584070052558297024329254421478902909314105677601829946763003101714995414429721253749752004489966994416785386578232345759601687283799109121167811119474655723555777958644927956223836954912245628550110978)\n",
      "(4711224273331373977910490238834352060115767875175802159547226065477305442089160927662447689173899921650511329325780640723114337409594286878782729078200642107740290701060578228869140368026890517666438024038857959369890859620213582632492536372064331054738057670135220299550225569372043397171859053270019068355 : 115211308552251170712289808928148740860983837650102588683377623008544267391191924126068218015231728978324393682388525139729336358075647796250226401077991544249724163243218998831603715346875233148667954133219290967210863389487046525121955885958355116923414097756577255364622079931898528134115452256600708038726 : 1)\n",
      "(62241391058840568910776980601486746103312381301373763888005396103132307981408297903504158004027159105570481208389946426882339887604238467177668004592692619137112167401951410360701661999103688500118599007972700256808636078714986354753253210433854996992178601473176978091605053110132146252044190523249304613683 : 13793163824370740918757250634119183853694404762927846616819837629056037858973994028329934876698304788763251957232693510519616156534548152844103039796946124038883381327999652864009559777925995016374384309773683277835618673551989983219612427436029030053080913000651662100624554430136504060233058702814784921823 : 1)\n",
      "1682763377329999876088266320718040612037901309690939971774155809417306970613019643384970947520167566392039523522115794946769307950140283710314194591002069\n"
     ]
    }
   ],
   "source": [
    "print((s,b))\n",
    "print(s*E(Mx,My))\n",
    "print(randint(0,Ecard)*E(Mx,My))\n",
    "print(r^^(bytes_to_long(sha256(long_to_bytes(Mx)).digest())^^bytes_to_long(flag))<<256)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n"
     ]
    }
   ],
   "source": [
    "e=s\n",
    "b=b\n",
    "Cx,Cy,_=s*E(Mx,My)\n",
    "Tx,Ty,_=randint(0,Ecard)*E(Mx,My)\n",
    "secret=r^^(bytes_to_long(sha256(long_to_bytes(Mx)).digest())^^bytes_to_long(flag))<<256\n",
    "d0=secret%2^256\n",
    "N=gcd(int(Cy)^2-int(Cx)^3-int(b),int(Ty)^2-int(Tx)^3-int(b))\n",
    "print(N/p/q)\n",
    "from sage.rings.factorint import factor_trial_division\n",
    "N=factor_trial_division(N, 1000)[-1][0]\n",
    "assert N == p*q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "77 415\n"
     ]
    }
   ],
   "source": [
    "ab=412\n",
    "beta=256\n",
    "R=e*d0-1\n",
    "\n",
    "m=4\n",
    "t=1\n",
    "X=2^(ab-beta)+1\n",
    "while gcd(R,X) != 1:\n",
    "    X+=2\n",
    "Y=2^ab+1\n",
    "while gcd(R,Y) != 1:\n",
    "    Y+=2\n",
    "Z=2^512+1\n",
    "while gcd(R,Z) != 1:\n",
    "    Z+=2\n",
    "W=(2^1024+1)*Y\n",
    "n=(X*Y)^m*Z^(m+t)*W\n",
    "\n",
    "P.<x,y,z>=PolynomialRing(ZZ)\n",
    "PP.<xx,yy,zz>=PolynomialRing(Zmod(n))\n",
    "PR.<qr>=PolynomialRing(ZZ)\n",
    "\n",
    "detB=0\n",
    "w=0\n",
    "for i in range(m+1):\n",
    "    for j in range(m-i+1):\n",
    "        for k in range(j+t+1):\n",
    "            detB += x*m+y*m+z*(m+t)\n",
    "            w+=1\n",
    "for i in range(m+2):\n",
    "    j=m+1-i\n",
    "    for k in range(j+t+1):\n",
    "        detB += x*(m+i)+y*(m+j)+z*(m+t+k)+1024+y\n",
    "        w+=1\n",
    "detB -= (x*m+y*m+z*(m+t)+1024+y)*w\n",
    "print(w, int(PolynomialRing(RR, 'rx')(detB(qr-beta,qr,512)).roots()[0][0]))\n",
    "assert ab <= PolynomialRing(RR, 'rx')(detB(qr-beta,qr,512)).roots()[0][0]\n",
    "\n",
    "\n",
    "M=e*2^beta\n",
    "R=e*d0-1\n",
    "A=int((N+1)/2)\n",
    "pol=M*x-A*y-y*z+R\n",
    "#assert pol(d//2^beta,2*int((e*d-1)/((p+1)*(q+1))),(p+q)/2) == 0\n",
    "pol=P(PP(pol)/R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "gg=[]\n",
    "monomials = []\n",
    "for i in range(m+1):\n",
    "    for j in range(m-i+1):\n",
    "        for k in range(j+t+1):\n",
    "            xshift = x^i*y^j*z^k*pol*X^(m-i)*Y^(m-j)*Z^(m+t-k)\n",
    "            gg.append(xshift)\n",
    "gg.sort()\n",
    "\n",
    "for i in range(m+2):\n",
    "    j=m+1-i\n",
    "    for k in range(j+t+1):\n",
    "        yshift = n*x^i*y^j*z^k\n",
    "        gg.append(yshift)\n",
    "        monomials.append(x^i*y^j*z^k)\n",
    "\n",
    "for polynomial in gg:\n",
    "    for monomial in polynomial.monomials():\n",
    "        if monomial not in monomials:\n",
    "            monomials.append(monomial)\n",
    "monomials.sort()\n",
    "\n",
    "nn = len(monomials)\n",
    "BB = Matrix(ZZ, nn)\n",
    "for ii in range(nn):\n",
    "    BB[ii, 0] = gg[ii](0, 0, 0)\n",
    "    for jj in range(1, nn):\n",
    "        if monomials[jj] in gg[ii].monomials():\n",
    "            BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](X,Y,Z)\n",
    "\n",
    "#assert abs(BB.det()) < n^(nn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2min 55s, sys: 250 ms, total: 2min 55s\n",
      "Wall time: 2min 55s\n"
     ]
    }
   ],
   "source": [
    "%time BB=BB.LLL()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "found them, using vectors 0 and 1\n"
     ]
    }
   ],
   "source": [
    "pol=M*x-A*y-y*z+R\n",
    "found_polynomials = False\n",
    "for pol1_idx in range(nn - 1):\n",
    "    pol1 = 0\n",
    "    for jj in range(nn):\n",
    "        pol1 += P(monomials[jj] * BB[pol1_idx, jj] / monomials[jj](X,Y,Z))\n",
    "    r1=pol.resultant(pol1,y)\n",
    "    if r1.is_zero() or r1.monomials() == [1]:\n",
    "        continue\n",
    "    for pol2_idx in range(pol1_idx + 1, nn):\n",
    "        pol2 = 0\n",
    "        for jj in range(nn):\n",
    "            pol2 += P(monomials[jj] * BB[pol2_idx, jj] / monomials[jj](X,Y,Z))\n",
    "        r2=pol.resultant(pol2,y)\n",
    "        if r2.is_zero() or r2.monomials() == [1]:\n",
    "            continue\n",
    "        else:\n",
    "            print(\"found them, using vectors\", pol1_idx, \"and\", pol2_idx)\n",
    "            found_polynomials = True\n",
    "            break\n",
    "    if found_polynomials:\n",
    "        break\n",
    "if not found_polynomials:\n",
    "    print(\"no independant vectors could be found. This should very rarely happen...\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "rr=r1.resultant(r2)\n",
    "rr=rr(qr,qr,qr)\n",
    "pq=rr.roots()[0][0]*2\n",
    "assert pq != -(N+1)\n",
    "(pp,_),(qq,_)=(qr^2-pq*qr+N).roots()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'flag{Copper5mith_M3thod_f0r_ECC}'\n"
     ]
    }
   ],
   "source": [
    "EE=EllipticCurve(Zmod(N),[0,Cy^2-Cx^3])\n",
    "dd=inverse_mod(e,(pp+1)*(qq+1))\n",
    "M=dd*EE(Cx,Cy)\n",
    "print(long_to_bytes((bytes_to_long(sha256(long_to_bytes(M[0])).digest())<<256^^secret^^dd)>>256))"
   ]
  },
  {
   "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
}

MultipleMultiply.ipynb