hellman/FibHash.ipynb

## FibHash.ipynb
{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CONFidence 2020 CTF Finals - FibHash (Crypto 421)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T11:48:45.012344Z",
     "iopub.status.busy": "2020-09-06T11:48:45.011996Z",
     "iopub.status.idle": "2020-09-06T11:48:45.016374Z",
     "shell.execute_reply": "2020-09-06T11:48:45.015529Z",
     "shell.execute_reply.started": "2020-09-06T11:48:45.012303Z"
    }
   },
   "source": [
    "In this challenge, we are given four linear recurrences (modulo a large prime $p$):\n",
    "$$\n",
    "\\begin{align}\n",
    "(a, b) &\\mapsto (6 a - 9 b, a),\\\\\n",
    "(a, b) &\\mapsto (8 a - 15 b, a),\\\\\n",
    "(a, b) &\\mapsto (10 a - 21 b, a),\\\\\n",
    "(a, b) &\\mapsto (12 a - 35 b, a).\n",
    "\\end{align}\n",
    "$$\n",
    "Each recurrence is applied $n$ times to some known starting values, where $n$ is the flag's integer value. We are given the first element of each output. The goal is as usual to recover the flag, i.e. find $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import gensafeprime\n",
    "from Crypto.Util.number import bytes_to_long\n",
    "\n",
    "flag = b\"flag{local test flag}\"\n",
    "n = ZZ(bytes_to_long(flag))\n",
    "\n",
    "# p = gensafeprime.generate(n.nbits() + 1)\n",
    "# use challenge prime \n",
    "p = 3825410404746255934165193857151892506649946388303502923742559459860756754338954959067709726395434244171362767397769981378523965557840655385143008725493705117779476208930333229713993176785249759\n",
    "assert n < p\n",
    "print('p =', p)\n",
    "\n",
    "K = Zmod(p)\n",
    "\n",
    "def hash_with_params(g, h, a1, a0):\n",
    "    def step(prev1, prev2):\n",
    "        return vector([g * prev1 - h * prev2, prev1])\n",
    "    def steps(n):\n",
    "        Kx.<prev1, prev2> = K[]\n",
    "        if n == 0: return vector([prev1, prev2])\n",
    "        half = steps(n // 2)\n",
    "        full = half(*half)\n",
    "        if n % 2 == 0: return full\n",
    "        else: return step(*full)\n",
    "    return steps(n)[0](a1, a0)\n",
    "\n",
    "starts = [\n",
    "    (3141592653589793, 2384626433832795),\n",
    "    (288419716939937, 5105820974944592),\n",
    "    (3078164062862089, 9862803482534211),\n",
    "    (7067982148086513, 2823066470938446),\n",
    "]\n",
    "\n",
    "# local test with sample flag\n",
    "debug = 1\n",
    "ys = [\n",
    "    hash_with_params(6, 9,   3141592653589793, 2384626433832795),\n",
    "    hash_with_params(8, 15,   288419716939937, 5105820974944592),\n",
    "    hash_with_params(10, 21, 3078164062862089, 9862803482534211),\n",
    "    hash_with_params(12, 35, 7067982148086513, 2823066470938446),\n",
    "]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's study the matrices $M_i$ of the steps of each linear recurrence. Jordan normal form is particularly useful in this case, as it will reveal a diagonalization if it exists. The hope is to find a basis change matrix $A_i$ such that $J_i = A_i^{-1} \\times M_i \\times A_i$ is diagonal matrix. Diagonal matrices are interesting because their $n$-th power is the diagonal matrix with each diagonal element raise to $n$'th power."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:54.012411Z",
     "iopub.status.busy": "2020-09-06T15:36:54.012106Z",
     "iopub.status.idle": "2020-09-06T15:36:54.133249Z",
     "shell.execute_reply": "2020-09-06T15:36:54.132598Z",
     "shell.execute_reply.started": "2020-09-06T15:36:54.012380Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3 1]\n",
      "[0 3] \n",
      "\n",
      "[5 0]\n",
      "[0 3] \n",
      "\n",
      "[7 0]\n",
      "[0 3] \n",
      "\n",
      "[7 0]\n",
      "[0 5] \n",
      "\n"
     ]
    }
   ],
   "source": [
    "Ms = []\n",
    "Js = []\n",
    "As = []\n",
    "for g, h in [(6, 9), (8, 15), (10, 21), (12, 35)]:\n",
    "    # decomposes over Z\n",
    "    # otherwise, have to look in GF(p)\n",
    "    M = matrix(ZZ, 2, 2, [\n",
    "        g, -h,\n",
    "        1, 0,\n",
    "    ])\n",
    "    J, A = M.jordan_form(subdivide=False, transformation=True)\n",
    "    assert (~A) * M * A == J\n",
    "    print(J, \"\\n\")\n",
    "    Ms.append(M.change_ring(K))\n",
    "    Js.append(J.change_ring(K))\n",
    "    As.append(A.change_ring(K))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interesting! We can see that the 2nd, 3rd and 4th matrices compute powers of 3, 5 and 7. For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:54.134734Z",
     "iopub.status.busy": "2020-09-06T15:36:54.134385Z",
     "iopub.status.idle": "2020-09-06T15:36:54.165030Z",
     "shell.execute_reply": "2020-09-06T15:36:54.161948Z",
     "shell.execute_reply.started": "2020-09-06T15:36:54.134695Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ys[1] == (As[1] * Js[1]**n * (~As[1]) * vector(starts[1]))[0] \\\n",
    "      == (As[1] * diagonal_matrix([K(5)**n, K(3)**n]) * (~As[1]) * vector(starts[1]))[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also immediately notice that one side of the basis change simply modifies the starting points. However, we can not \"remove\" the other one, because we are given only one output of a pair. As a result, we obtain linear combinations of the diagonal powers:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:54.170233Z",
     "iopub.status.busy": "2020-09-06T15:36:54.168391Z",
     "iopub.status.idle": "2020-09-06T15:36:54.186377Z",
     "shell.execute_reply": "2020-09-06T15:36:54.185336Z",
     "shell.execute_reply.started": "2020-09-06T15:36:54.170021Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a0p, a1p = (~As[1]) * vector(starts[1])\n",
    "a, b = As[1][0]\n",
    "ys[1] == a * a0p * pow(5, n, p) + b * a1p * pow(3, n, p)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is likely that they are linearly independent and we can obtain values of $3^n,5^n,7^n$ separately. Let's try:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:54.188741Z",
     "iopub.status.busy": "2020-09-06T15:36:54.187976Z",
     "iopub.status.idle": "2020-09-06T15:36:55.186483Z",
     "shell.execute_reply": "2020-09-06T15:36:55.185759Z",
     "shell.execute_reply.started": "2020-09-06T15:36:54.188641Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "coefs = []\n",
    "for i in range(1, 4):\n",
    "    a0p, a1p = (~As[i]) * vector(starts[i])\n",
    "    a, b = As[i][0]\n",
    "    coefs.append((a * a0p, b * a1p))\n",
    "    \n",
    "a, b = coefs[0]\n",
    "c, d = coefs[1]\n",
    "e, f = coefs[2]\n",
    "\n",
    "# matrix mapping\n",
    "# 3^n, 5^n, 7^n\n",
    "# to outputs y1, y2, y3\n",
    "m = matrix(GF(p), 3, 3, [\n",
    "    b, a, 0,\n",
    "    d, 0, c,\n",
    "    0, f, e\n",
    "])\n",
    "m.rank()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! We can obtain the powers now:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:55.188202Z",
     "iopub.status.busy": "2020-09-06T15:36:55.187715Z",
     "iopub.status.idle": "2020-09-06T15:36:56.150276Z",
     "shell.execute_reply": "2020-09-06T15:36:56.149662Z",
     "shell.execute_reply.started": "2020-09-06T15:36:55.188140Z"
    }
   },
   "outputs": [],
   "source": [
    "assert (~m)[0] * vector(ys[1:4]) == pow(3, n, p)\n",
    "assert (~m)[1] * vector(ys[1:4]) == pow(5, n, p)\n",
    "assert (~m)[2] * vector(ys[1:4]) == pow(7, n, p)\n",
    "select3 = (~m)[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But what now? We have reduced the problem to standard discrete logarithm modulo $p$, which has 640 bits. This is rather infeasible for a CTF-level challenge.\n",
    "\n",
    "But wait, we haven't used one of the outputs! Recall its Jordan form:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.151740Z",
     "iopub.status.busy": "2020-09-06T15:36:56.151324Z",
     "iopub.status.idle": "2020-09-06T15:36:56.170374Z",
     "shell.execute_reply": "2020-09-06T15:36:56.169606Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.151686Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3 1]\n",
       "[0 3]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Js[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How do it's powers look like? Let's compute symbolically:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.173079Z",
     "iopub.status.busy": "2020-09-06T15:36:56.172600Z",
     "iopub.status.idle": "2020-09-06T15:36:56.212997Z",
     "shell.execute_reply": "2020-09-06T15:36:56.211753Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.173016Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[  z^5 5*z^4]\n",
      "[    0   z^5]\n",
      "\n",
      "[  z^10 10*z^9]\n",
      "[     0   z^10]\n"
     ]
    }
   ],
   "source": [
    "_.<z> = QQ[]\n",
    "print(matrix([[z, 1], [0, z]])**5)\n",
    "print()\n",
    "print(matrix([[z, 1], [0, z]])**10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interesting! It seems to have terms $3^n$ and $n3^{n-1}$ only. Let's check for our large $n$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.217513Z",
     "iopub.status.busy": "2020-09-06T15:36:56.216841Z",
     "iopub.status.idle": "2020-09-06T15:36:56.233992Z",
     "shell.execute_reply": "2020-09-06T15:36:56.230293Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.217435Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a0p, a1p = (~As[0]) * vector(starts[0])\n",
    "a, b = As[0][0]\n",
    "ys[0] == (a * a0p + b * a1p) * pow(3, n, p) + a * a1p * pow(3, n-1, p) * n "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cool! We also know $3^n$, so we can actually compute $n$ by simple arithmetics:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.236728Z",
     "iopub.status.busy": "2020-09-06T15:36:56.236033Z",
     "iopub.status.idle": "2020-09-06T15:36:56.256675Z",
     "shell.execute_reply": "2020-09-06T15:36:56.254577Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.236634Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow3n = select3 * vector(ys[1:4])\n",
    "coef0 = a * a0p + b * a1p\n",
    "coef1 = a * a1p\n",
    "nsol = (ys[0] - coef0 * pow3n) / (pow3n / 3) / coef1\n",
    "nsol == n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's solve the challenge data. Note that all the coefficients are the same, we only change the $y$ values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.259580Z",
     "iopub.status.busy": "2020-09-06T15:36:56.258498Z",
     "iopub.status.idle": "2020-09-06T15:36:56.281602Z",
     "shell.execute_reply": "2020-09-06T15:36:56.280411Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.259353Z"
    }
   },
   "outputs": [],
   "source": [
    "ys = [\n",
    "    1676692106337556305706016770958074706883705493218787835803500458160553522426125469104058304906236524961048084572483189178908787893713024829966510890627053066279418122862473691624486823188135802,\n",
    "    2857964008499737244123466571337419134404523101896831014364752478262678705106912578400545946910842379193592617481759402862420715714781790030237246290673584587132334065412406222540095225886964680,\n",
    "    377100011534086235658104379801079570118458049751793753941421646112566213186676075464534398000332714495426504495371864334278835331209624236632121660999291442470627222536838461859856916754666911,\n",
    "    1452032184499983915936783392161922013770235576423037573850700970726680707755112154943113287273883628447114298114469426584835959464327248935513505491784021332818735403611670877092428106276909863,\n",
    "]\n",
    "b, c, d = -coef0 * select3\n",
    "pow3n = select3 * vector(ys[1:4])\n",
    "e, f, g = (K(coef1)/3) * select3\n",
    "nsol = (ys[0] - coef0 * pow3n) / (pow3n / 3) / coef1\n",
    "#nsol = (ys[0] + b * ys[1] + c * ys[2] + d * ys[3]) / (e * ys[1] + f * ys[2] + g * ys[3])\n",
    "assert nsol * (e * ys[1] + f * ys[2] + g * ys[3]) ==  (ys[0] + b * ys[1] + c * ys[2] + d * ys[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.285145Z",
     "iopub.status.busy": "2020-09-06T15:36:56.283931Z",
     "iopub.status.idle": "2020-09-06T15:36:56.306652Z",
     "shell.execute_reply": "2020-09-06T15:36:56.305024Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.284986Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'p4{on3_w0uld_th1nk_th@t_ma7rices_wou1d_b3_m0re_u5eful_f0r_att@ck1ng_r3currence5}'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int(nsol).to_bytes(1000, \"big\").strip(b\"\\x00\").decode()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bonus\n",
    "\n",
    "Note that the solution is a degree-1 rational function of the outputs. Knowing (or guessing) this is sufficient for solving it in a black-box style! We can simply interpolate the polynomial $n\\cdot g(y) = f(y)$, such that $n = f(y) / g(y)$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.309426Z",
     "iopub.status.busy": "2020-09-06T15:36:56.308744Z",
     "iopub.status.idle": "2020-09-06T15:36:56.579618Z",
     "shell.execute_reply": "2020-09-06T15:36:56.578341Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.309274Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 10 9\n"
     ]
    }
   ],
   "source": [
    "rows = []\n",
    "for i in range(10):\n",
    "    n = 100 + i\n",
    "    ys = [\n",
    "        hash_with_params(6, 9,   3141592653589793, 2384626433832795),\n",
    "        hash_with_params(8, 15,   288419716939937, 5105820974944592),\n",
    "        hash_with_params(10, 21, 3078164062862089, 9862803482534211),\n",
    "        hash_with_params(12, 35, 7067982148086513, 2823066470938446),\n",
    "    ]\n",
    "    # for generality,\n",
    "    # allow constants in numerator/denominator\n",
    "    # but we don't need them in this problem\n",
    "    row = []\n",
    "    row += [1] + ys  # [1] for constants in numerator\n",
    "    row += [n] + [n*y for y in ys] # [n] for constants in denominator\n",
    "    rows.append(row)\n",
    "m = matrix(K, rows)\n",
    "print(m.nrows(), m.ncols(), m.rank())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.583151Z",
     "iopub.status.busy": "2020-09-06T15:36:56.582133Z",
     "iopub.status.idle": "2020-09-06T15:36:56.595340Z",
     "shell.execute_reply": "2020-09-06T15:36:56.593953Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.582831Z"
    }
   },
   "outputs": [],
   "source": [
    "comb = m.right_kernel().matrix()[0]\n",
    "top = -comb[:5]\n",
    "bottom = comb[5:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.598361Z",
     "iopub.status.busy": "2020-09-06T15:36:56.597638Z",
     "iopub.status.idle": "2020-09-06T15:36:56.613461Z",
     "shell.execute_reply": "2020-09-06T15:36:56.611413Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.598234Z"
    }
   },
   "outputs": [],
   "source": [
    "ys = vector(K, [1] + [\n",
    "    1676692106337556305706016770958074706883705493218787835803500458160553522426125469104058304906236524961048084572483189178908787893713024829966510890627053066279418122862473691624486823188135802,\n",
    "    2857964008499737244123466571337419134404523101896831014364752478262678705106912578400545946910842379193592617481759402862420715714781790030237246290673584587132334065412406222540095225886964680,\n",
    "    377100011534086235658104379801079570118458049751793753941421646112566213186676075464534398000332714495426504495371864334278835331209624236632121660999291442470627222536838461859856916754666911,\n",
    "    1452032184499983915936783392161922013770235576423037573850700970726680707755112154943113287273883628447114298114469426584835959464327248935513505491784021332818735403611670877092428106276909863,\n",
    "])\n",
    "nsol = (top * ys) / (bottom * ys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "execution": {
     "iopub.execute_input": "2020-09-06T15:36:56.621349Z",
     "iopub.status.busy": "2020-09-06T15:36:56.620749Z",
     "iopub.status.idle": "2020-09-06T15:36:56.632640Z",
     "shell.execute_reply": "2020-09-06T15:36:56.630278Z",
     "shell.execute_reply.started": "2020-09-06T15:36:56.621268Z"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "b'p4{on3_w0uld_th1nk_th@t_ma7rices_wou1d_b3_m0re_u5eful_f0r_att@ck1ng_r3currence5}'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "int(nsol).to_bytes(1000, \"big\").strip(b\"\\x00\")#.decode()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.1",
   "language": "sage",
   "name": "sagemath3"
  },
  "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": 4
}
	{
	"cells": [
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"# CONFidence 2020 CTF Finals - FibHash (Crypto 421)"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T11:48:45.012344Z",
	"iopub.status.busy": "2020-09-06T11:48:45.011996Z",
	"iopub.status.idle": "2020-09-06T11:48:45.016374Z",
	"shell.execute_reply": "2020-09-06T11:48:45.015529Z",
	"shell.execute_reply.started": "2020-09-06T11:48:45.012303Z"
	}
	},
	"source": [
	"In this challenge, we are given four linear recurrences (modulo a large prime $p$):\n",
	"$$\n",
	"\\begin{align}\n",
	"(a, b) &\\mapsto (6 a - 9 b, a),\\\\\n",
	"(a, b) &\\mapsto (8 a - 15 b, a),\\\\\n",
	"(a, b) &\\mapsto (10 a - 21 b, a),\\\\\n",
	"(a, b) &\\mapsto (12 a - 35 b, a).\n",
	"\\end{align}\n",
	"$$\n",
	"Each recurrence is applied $n$ times to some known starting values, where $n$ is the flag's integer value. We are given the first element of each output. The goal is as usual to recover the flag, i.e. find $n$."
	]
	},
	{
	"cell_type": "code",
	"execution_count": null,
	"metadata": {},
	"outputs": [],
	"source": [
	"# import gensafeprime\n",
	"from Crypto.Util.number import bytes_to_long\n",
	"\n",
	"flag = b\"flag{local test flag}\"\n",
	"n = ZZ(bytes_to_long(flag))\n",
	"\n",
	"# p = gensafeprime.generate(n.nbits() + 1)\n",
	"# use challenge prime \n",
	"p = 3825410404746255934165193857151892506649946388303502923742559459860756754338954959067709726395434244171362767397769981378523965557840655385143008725493705117779476208930333229713993176785249759\n",
	"assert n < p\n",
	"print('p =', p)\n",
	"\n",
	"K = Zmod(p)\n",
	"\n",
	"def hash_with_params(g, h, a1, a0):\n",
	" def step(prev1, prev2):\n",
	" return vector([g * prev1 - h * prev2, prev1])\n",
	" def steps(n):\n",
	" Kx.<prev1, prev2> = K[]\n",
	" if n == 0: return vector([prev1, prev2])\n",
	" half = steps(n // 2)\n",
	" full = half(*half)\n",
	" if n % 2 == 0: return full\n",
	" else: return step(*full)\n",
	" return steps(n)[0](a1, a0)\n",
	"\n",
	"starts = [\n",
	" (3141592653589793, 2384626433832795),\n",
	" (288419716939937, 5105820974944592),\n",
	" (3078164062862089, 9862803482534211),\n",
	" (7067982148086513, 2823066470938446),\n",
	"]\n",
	"\n",
	"# local test with sample flag\n",
	"debug = 1\n",
	"ys = [\n",
	" hash_with_params(6, 9, 3141592653589793, 2384626433832795),\n",
	" hash_with_params(8, 15, 288419716939937, 5105820974944592),\n",
	" hash_with_params(10, 21, 3078164062862089, 9862803482534211),\n",
	" hash_with_params(12, 35, 7067982148086513, 2823066470938446),\n",
	"]\n"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Let's study the matrices $M_i$ of the steps of each linear recurrence. Jordan normal form is particularly useful in this case, as it will reveal a diagonalization if it exists. The hope is to find a basis change matrix $A_i$ such that $J_i = A_i^{-1} \\times M_i \\times A_i$ is diagonal matrix. Diagonal matrices are interesting because their $n$-th power is the diagonal matrix with each diagonal element raise to $n$'th power."
	]
	},
	{
	"cell_type": "code",
	"execution_count": 2,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:54.012411Z",
	"iopub.status.busy": "2020-09-06T15:36:54.012106Z",
	"iopub.status.idle": "2020-09-06T15:36:54.133249Z",
	"shell.execute_reply": "2020-09-06T15:36:54.132598Z",
	"shell.execute_reply.started": "2020-09-06T15:36:54.012380Z"
	}
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"[3 1]\n",
	"[0 3] \n",
	"\n",
	"[5 0]\n",
	"[0 3] \n",
	"\n",
	"[7 0]\n",
	"[0 3] \n",
	"\n",
	"[7 0]\n",
	"[0 5] \n",
	"\n"
	]
	}
	],
	"source": [
	"Ms = []\n",
	"Js = []\n",
	"As = []\n",
	"for g, h in [(6, 9), (8, 15), (10, 21), (12, 35)]:\n",
	" # decomposes over Z\n",
	" # otherwise, have to look in GF(p)\n",
	" M = matrix(ZZ, 2, 2, [\n",
	" g, -h,\n",
	" 1, 0,\n",
	" ])\n",
	" J, A = M.jordan_form(subdivide=False, transformation=True)\n",
	" assert (~A) * M * A == J\n",
	" print(J, \"\\n\")\n",
	" Ms.append(M.change_ring(K))\n",
	" Js.append(J.change_ring(K))\n",
	" As.append(A.change_ring(K))"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Interesting! We can see that the 2nd, 3rd and 4th matrices compute powers of 3, 5 and 7. For example:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 3,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:54.134734Z",
	"iopub.status.busy": "2020-09-06T15:36:54.134385Z",
	"iopub.status.idle": "2020-09-06T15:36:54.165030Z",
	"shell.execute_reply": "2020-09-06T15:36:54.161948Z",
	"shell.execute_reply.started": "2020-09-06T15:36:54.134695Z"
	}
	},
	"outputs": [
	{
	"data": {
	"text/plain": [
	"True"
	]
	},
	"execution_count": 3,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"ys[1] == (As[1] * Js[1]*n (~As[1]) * vector(starts[1]))[0] \\\n",
	" == (As[1] * diagonal_matrix([K(5)n, K(3)n]) * (~As[1]) * vector(starts[1]))[0]"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"We can also immediately notice that one side of the basis change simply modifies the starting points. However, we can not \"remove\" the other one, because we are given only one output of a pair. As a result, we obtain linear combinations of the diagonal powers:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 4,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:54.170233Z",
	"iopub.status.busy": "2020-09-06T15:36:54.168391Z",
	"iopub.status.idle": "2020-09-06T15:36:54.186377Z",
	"shell.execute_reply": "2020-09-06T15:36:54.185336Z",
	"shell.execute_reply.started": "2020-09-06T15:36:54.170021Z"
	}
	},
	"outputs": [
	{
	"data": {
	"text/plain": [
	"True"
	]
	},
	"execution_count": 4,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"a0p, a1p = (~As[1]) * vector(starts[1])\n",
	"a, b = As[1][0]\n",
	"ys[1] == a * a0p * pow(5, n, p) + b * a1p * pow(3, n, p)"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"It is likely that they are linearly independent and we can obtain values of $3^n,5^n,7^n$ separately. Let's try:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 5,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:54.188741Z",
	"iopub.status.busy": "2020-09-06T15:36:54.187976Z",
	"iopub.status.idle": "2020-09-06T15:36:55.186483Z",
	"shell.execute_reply": "2020-09-06T15:36:55.185759Z",
	"shell.execute_reply.started": "2020-09-06T15:36:54.188641Z"
	}
	},
	"outputs": [
	{
	"data": {
	"text/plain": [
	"3"
	]
	},
	"execution_count": 5,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"coefs = []\n",
	"for i in range(1, 4):\n",
	" a0p, a1p = (~As[i]) * vector(starts[i])\n",
	" a, b = As[i][0]\n",
	" coefs.append((a * a0p, b * a1p))\n",
	" \n",
	"a, b = coefs[0]\n",
	"c, d = coefs[1]\n",
	"e, f = coefs[2]\n",
	"\n",
	"# matrix mapping\n",
	"# 3^n, 5^n, 7^n\n",
	"# to outputs y1, y2, y3\n",
	"m = matrix(GF(p), 3, 3, [\n",
	" b, a, 0,\n",
	" d, 0, c,\n",
	" 0, f, e\n",
	"])\n",
	"m.rank()"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Great! We can obtain the powers now:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 6,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:55.188202Z",
	"iopub.status.busy": "2020-09-06T15:36:55.187715Z",
	"iopub.status.idle": "2020-09-06T15:36:56.150276Z",
	"shell.execute_reply": "2020-09-06T15:36:56.149662Z",
	"shell.execute_reply.started": "2020-09-06T15:36:55.188140Z"
	}
	},
	"outputs": [],
	"source": [
	"assert (~m)[0] * vector(ys[1:4]) == pow(3, n, p)\n",
	"assert (~m)[1] * vector(ys[1:4]) == pow(5, n, p)\n",
	"assert (~m)[2] * vector(ys[1:4]) == pow(7, n, p)\n",
	"select3 = (~m)[0]"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"But what now? We have reduced the problem to standard discrete logarithm modulo $p$, which has 640 bits. This is rather infeasible for a CTF-level challenge.\n",
	"\n",
	"But wait, we haven't used one of the outputs! Recall its Jordan form:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 7,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.151740Z",
	"iopub.status.busy": "2020-09-06T15:36:56.151324Z",
	"iopub.status.idle": "2020-09-06T15:36:56.170374Z",
	"shell.execute_reply": "2020-09-06T15:36:56.169606Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.151686Z"
	}
	},
	"outputs": [
	{
	"data": {
	"text/plain": [
	"[3 1]\n",
	"[0 3]"
	]
	},
	"execution_count": 7,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"Js[0]"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"How do it's powers look like? Let's compute symbolically:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 8,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.173079Z",
	"iopub.status.busy": "2020-09-06T15:36:56.172600Z",
	"iopub.status.idle": "2020-09-06T15:36:56.212997Z",
	"shell.execute_reply": "2020-09-06T15:36:56.211753Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.173016Z"
	}
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"[ z^5 5*z^4]\n",
	"[ 0 z^5]\n",
	"\n",
	"[ z^10 10*z^9]\n",
	"[ 0 z^10]\n"
	]
	}
	],
	"source": [
	"_.<z> = QQ[]\n",
	"print(matrix([[z, 1], [0, z]])**5)\n",
	"print()\n",
	"print(matrix([[z, 1], [0, z]])**10)"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Interesting! It seems to have terms $3^n$ and $n3^{n-1}$ only. Let's check for our large $n$:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 9,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.217513Z",
	"iopub.status.busy": "2020-09-06T15:36:56.216841Z",
	"iopub.status.idle": "2020-09-06T15:36:56.233992Z",
	"shell.execute_reply": "2020-09-06T15:36:56.230293Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.217435Z"
	}
	},
	"outputs": [
	{
	"data": {
	"text/plain": [
	"True"
	]
	},
	"execution_count": 9,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"a0p, a1p = (~As[0]) * vector(starts[0])\n",
	"a, b = As[0][0]\n",
	"ys[0] == (a * a0p + b * a1p) * pow(3, n, p) + a * a1p * pow(3, n-1, p) * n "
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Cool! We also know $3^n$, so we can actually compute $n$ by simple arithmetics:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 10,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.236728Z",
	"iopub.status.busy": "2020-09-06T15:36:56.236033Z",
	"iopub.status.idle": "2020-09-06T15:36:56.256675Z",
	"shell.execute_reply": "2020-09-06T15:36:56.254577Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.236634Z"
	}
	},
	"outputs": [
	{
	"data": {
	"text/plain": [
	"True"
	]
	},
	"execution_count": 10,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"pow3n = select3 * vector(ys[1:4])\n",
	"coef0 = a * a0p + b * a1p\n",
	"coef1 = a * a1p\n",
	"nsol = (ys[0] - coef0 * pow3n) / (pow3n / 3) / coef1\n",
	"nsol == n"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"Now let's solve the challenge data. Note that all the coefficients are the same, we only change the $y$ values:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 11,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.259580Z",
	"iopub.status.busy": "2020-09-06T15:36:56.258498Z",
	"iopub.status.idle": "2020-09-06T15:36:56.281602Z",
	"shell.execute_reply": "2020-09-06T15:36:56.280411Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.259353Z"
	}
	},
	"outputs": [],
	"source": [
	"ys = [\n",
	" 1676692106337556305706016770958074706883705493218787835803500458160553522426125469104058304906236524961048084572483189178908787893713024829966510890627053066279418122862473691624486823188135802,\n",
	" 2857964008499737244123466571337419134404523101896831014364752478262678705106912578400545946910842379193592617481759402862420715714781790030237246290673584587132334065412406222540095225886964680,\n",
	" 377100011534086235658104379801079570118458049751793753941421646112566213186676075464534398000332714495426504495371864334278835331209624236632121660999291442470627222536838461859856916754666911,\n",
	" 1452032184499983915936783392161922013770235576423037573850700970726680707755112154943113287273883628447114298114469426584835959464327248935513505491784021332818735403611670877092428106276909863,\n",
	"]\n",
	"b, c, d = -coef0 * select3\n",
	"pow3n = select3 * vector(ys[1:4])\n",
	"e, f, g = (K(coef1)/3) * select3\n",
	"nsol = (ys[0] - coef0 * pow3n) / (pow3n / 3) / coef1\n",
	"#nsol = (ys[0] + b * ys[1] + c * ys[2] + d * ys[3]) / (e * ys[1] + f * ys[2] + g * ys[3])\n",
	"assert nsol * (e * ys[1] + f * ys[2] + g * ys[3]) == (ys[0] + b * ys[1] + c * ys[2] + d * ys[3])"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 12,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.285145Z",
	"iopub.status.busy": "2020-09-06T15:36:56.283931Z",
	"iopub.status.idle": "2020-09-06T15:36:56.306652Z",
	"shell.execute_reply": "2020-09-06T15:36:56.305024Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.284986Z"
	}
	},
	"outputs": [
	{
	"data": {
	"text/plain": [
	"'p4{on3_w0uld_th1nk_th@t_ma7rices_wou1d_b3_m0re_u5eful_f0r_att@ck1ng_r3currence5}'"
	]
	},
	"execution_count": 12,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"int(nsol).to_bytes(1000, \"big\").strip(b\"\\x00\").decode()"
	]
	},
	{
	"cell_type": "markdown",
	"metadata": {},
	"source": [
	"## Bonus\n",
	"\n",
	"Note that the solution is a degree-1 rational function of the outputs. Knowing (or guessing) this is sufficient for solving it in a black-box style! We can simply interpolate the polynomial $n\\cdot g(y) = f(y)$, such that $n = f(y) / g(y)$:"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 13,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.309426Z",
	"iopub.status.busy": "2020-09-06T15:36:56.308744Z",
	"iopub.status.idle": "2020-09-06T15:36:56.579618Z",
	"shell.execute_reply": "2020-09-06T15:36:56.578341Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.309274Z"
	}
	},
	"outputs": [
	{
	"name": "stdout",
	"output_type": "stream",
	"text": [
	"10 10 9\n"
	]
	}
	],
	"source": [
	"rows = []\n",
	"for i in range(10):\n",
	" n = 100 + i\n",
	" ys = [\n",
	" hash_with_params(6, 9, 3141592653589793, 2384626433832795),\n",
	" hash_with_params(8, 15, 288419716939937, 5105820974944592),\n",
	" hash_with_params(10, 21, 3078164062862089, 9862803482534211),\n",
	" hash_with_params(12, 35, 7067982148086513, 2823066470938446),\n",
	" ]\n",
	" # for generality,\n",
	" # allow constants in numerator/denominator\n",
	" # but we don't need them in this problem\n",
	" row = []\n",
	" row += [1] + ys # [1] for constants in numerator\n",
	" row += [n] + [n*y for y in ys] # [n] for constants in denominator\n",
	" rows.append(row)\n",
	"m = matrix(K, rows)\n",
	"print(m.nrows(), m.ncols(), m.rank())"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 14,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.583151Z",
	"iopub.status.busy": "2020-09-06T15:36:56.582133Z",
	"iopub.status.idle": "2020-09-06T15:36:56.595340Z",
	"shell.execute_reply": "2020-09-06T15:36:56.593953Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.582831Z"
	}
	},
	"outputs": [],
	"source": [
	"comb = m.right_kernel().matrix()[0]\n",
	"top = -comb[:5]\n",
	"bottom = comb[5:]"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 15,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.598361Z",
	"iopub.status.busy": "2020-09-06T15:36:56.597638Z",
	"iopub.status.idle": "2020-09-06T15:36:56.613461Z",
	"shell.execute_reply": "2020-09-06T15:36:56.611413Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.598234Z"
	}
	},
	"outputs": [],
	"source": [
	"ys = vector(K, [1] + [\n",
	" 1676692106337556305706016770958074706883705493218787835803500458160553522426125469104058304906236524961048084572483189178908787893713024829966510890627053066279418122862473691624486823188135802,\n",
	" 2857964008499737244123466571337419134404523101896831014364752478262678705106912578400545946910842379193592617481759402862420715714781790030237246290673584587132334065412406222540095225886964680,\n",
	" 377100011534086235658104379801079570118458049751793753941421646112566213186676075464534398000332714495426504495371864334278835331209624236632121660999291442470627222536838461859856916754666911,\n",
	" 1452032184499983915936783392161922013770235576423037573850700970726680707755112154943113287273883628447114298114469426584835959464327248935513505491784021332818735403611670877092428106276909863,\n",
	"])\n",
	"nsol = (top * ys) / (bottom * ys)"
	]
	},
	{
	"cell_type": "code",
	"execution_count": 16,
	"metadata": {
	"execution": {
	"iopub.execute_input": "2020-09-06T15:36:56.621349Z",
	"iopub.status.busy": "2020-09-06T15:36:56.620749Z",
	"iopub.status.idle": "2020-09-06T15:36:56.632640Z",
	"shell.execute_reply": "2020-09-06T15:36:56.630278Z",
	"shell.execute_reply.started": "2020-09-06T15:36:56.621268Z"
	}
	},
	"outputs": [
	{
	"data": {
	"text/plain": [
	"b'p4{on3_w0uld_th1nk_th@t_ma7rices_wou1d_b3_m0re_u5eful_f0r_att@ck1ng_r3currence5}'"
	]
	},
	"execution_count": 16,
	"metadata": {},
	"output_type": "execute_result"
	}
	],
	"source": [
	"int(nsol).to_bytes(1000, \"big\").strip(b\"\\x00\")#.decode()"
	]
	}
	],
	"metadata": {
	"kernelspec": {
	"display_name": "SageMath 9.1",
	"language": "sage",
	"name": "sagemath3"
	},
	"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": 4
	}