Forbidden values in recursive scalar multiplications

forbidden.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Here are the common parameters for the two pasta curves"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "p = 28948022309329048855892746252171976963363056481941560715954676764349967630337\n",
    "q = 28948022309329048855892746252171976963363056481941647379679742748393362948097\n",
    "\n",
    "Fp = GF(p)\n",
    "Fq = GF(q)\n",
    "\n",
    "generator = 5\n",
    "\n",
    "a = 0\n",
    "b = 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Let's define the Pallas with base field Fp and order q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "Pallas = EllipticCurve([Fp(a), Fp(b)])\n",
    "assert Pallas.order() == q\n",
    "\n",
    "Pallas_G = Pallas(Fp(1), Fp(12418654782883325593414442427049395787963493412651469444558597405572177144507))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Then the Vesta curve with base field Fq and order p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "Vesta = EllipticCurve([Fq(a), Fq(b)])\n",
    "assert Vesta.order() == p\n",
    "\n",
    "Vesta_G = Vesta(Fq(1), Fq(11426906929455361843568202299992114520848200991084027513389447476559454104162))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Let's implement the fast multiplication algorithm from Daira (https://github.com/zcash/zcash/issues/3924)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "def mul(scalar, G):\n",
    "    ks = bin(scalar)[3:] # remove the first bit set as well\n",
    "    n = len(ks)\n",
    "    acc = 2 * G\n",
    "    ks = '0' + ks # add a 0 so that it looks like k_i+1\n",
    "    for i, ki in enumerate(ks):\n",
    "        # last iteration is the last step, theoretically outside the loop\n",
    "        if i == n:\n",
    "            if ki == '1':\n",
    "                res = acc\n",
    "            else:\n",
    "                assert acc != G\n",
    "                res = acc - G\n",
    "            return res\n",
    "        Q = G if ki == '1' else -G\n",
    "        assert acc != Q\n",
    "        temp = acc + Q\n",
    "        assert temp != acc\n",
    "        acc = temp + acc\n",
    "\n",
    "# asserts that the result is correct\n",
    "def checked_mul(scalar, G):\n",
    "    res = mul(scalar, G)\n",
    "    assert res == scalar * G\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Let's try it out!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "for i in [1, 2, 3, 4, 5, 6, 324234234]:\n",
    "    checked_mul(i, Pallas_G)\n",
    "    checked_mul(i, Vesta_G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "Now let's check the forbidden values, they are these values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "forbidden = [0, 45560315531506369815346746415080538112, 45560315531506369815346746415080538113, 14474011154664524427946373126085988481727088556502330059655218120611762012161, 91120631062839412180561524743370440705, 91120631062839412180561524743370440706]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "trying 0 with Pallas. didn't work!\n",
      "trying 0 with Vesta. didn't work!\n",
      "trying 45560315531506369815346746415080538112 with Pallas. ok\n",
      "trying 45560315531506369815346746415080538112 with Vesta. ok\n",
      "trying 45560315531506369815346746415080538113 with Pallas. ok\n",
      "trying 45560315531506369815346746415080538113 with Vesta. ok\n",
      "trying 14474011154664524427946373126085988481727088556502330059655218120611762012161 with Pallas. ok\n",
      "trying 14474011154664524427946373126085988481727088556502330059655218120611762012161 with Vesta. ok\n",
      "trying 91120631062839412180561524743370440705 with Pallas. ok\n",
      "trying 91120631062839412180561524743370440705 with Vesta. ok\n",
      "trying 91120631062839412180561524743370440706 with Pallas. ok\n",
      "trying 91120631062839412180561524743370440706 with Vesta. ok\n"
     ]
    }
   ],
   "source": [
    "for i in forbidden:\n",
    "    res = mul(i, Pallas_G)\n",
    "    expected = i * Pallas_G\n",
    "    sentence = \"ok\" if res == expected else \"didn't work!\"\n",
    "    print(f\"trying {i} with Pallas. {sentence}\")\n",
    "    res = mul(i, Vesta_G)\n",
    "    expected = i * Vesta_G\n",
    "    sentence = \"ok\" if res == expected else \"didn't work!\"\n",
    "    print(f\"trying {i} with Vesta. {sentence}\")\n",
    "    "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.3",
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 10,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sage-9.3",
   "resource_dir": "/ext/jupyter/kernels/sage-9.3"
  },
  "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}