Code for the write-up of Elliott's first Bitcoin-flavored cryptography challenge. https://b10c.me/blog/009-schnorr-nonce-reuse-challenge/

schnorr-nonce-reuse-challenge.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Untitled14.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "source": [
        "# Run if you're on Google Colab:\n",
        "!sudo apt install libgmp-dev\n",
        "!pip install fastecdsa"
      ],
      "metadata": {
        "id": "mDkhgjJGnbLg"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "d7CciFiT6zpU"
      },
      "outputs": [],
      "source": [
        "# curve group order\n",
        "n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141\n",
        "\n",
        "# public key\n",
        "P = 0x463F9E1F3808CEDF5BB282427ECD1BFE8FC759BC6F65A42C90AA197EFC6F9F26\n",
        "\n",
        "# first message and signature\n",
        "m1 = 0x6368616E63656C6C6F72206F6E20746865206272696E6B206F66207365636F6E\n",
        "sig1 = 0xF3F148DBF94B1BCAEE1896306141F319729DCCA9451617D4B529EB22C2FB521A32A1DB8D2669A00AFE7BE97AF8C355CCF2B49B9938B9E451A5C231A45993D920\n",
        "\n",
        "# second message and signature\n",
        "m2 = 0x6974206D69676874206D616B652073656E7365206A75737420746F2067657420\n",
        "sig2 = 0xF3F148DBF94B1BCAEE1896306141F319729DCCA9451617D4B529EB22C2FB521A974240A9A9403996CA01A06A3BC8F0D7B71D87FB510E897FF3EC5BF347E5C5C1"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# the first 256 bits of the signatures are R\n",
        "R = sig2 >> 256\n",
        "\n",
        "# the last 256 bits of the signatures sig1 and sig2 are the reponses s1 and s2\n",
        "s1 = sig1 - (R << 256)\n",
        "s2 = sig2 - (R << 256)"
      ],
      "metadata": {
        "id": "T9FNpR89626y"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "import hashlib\n",
        "challenge_tag = hashlib.sha256(b\"BIP0340/challenge\").digest() * 2"
      ],
      "metadata": {
        "id": "r9Gpq82y64wl"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "byteorder = \"big\"\n",
        "\n",
        "def int_to_bytes(i):\n",
        "  return i.to_bytes(32, byteorder, signed=False)\n",
        "\n",
        "def challenge_hash(tag, R, P, m):\n",
        "  return hashlib.sha256(tag + R + P + m).digest()\n",
        "\n",
        "e1_hash = challenge_hash(challenge_tag, int_to_bytes(R), int_to_bytes(P), int_to_bytes(m1))\n",
        "e2_hash = challenge_hash(challenge_tag, int_to_bytes(R), int_to_bytes(P), int_to_bytes(m2))"
      ],
      "metadata": {
        "id": "FASvpuxL66Mj"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def bytes_to_int(b):\n",
        "  return int.from_bytes(b, byteorder, signed=False)\n",
        "\n",
        "e1 = bytes_to_int(e1_hash) % n\n",
        "e2 = bytes_to_int(e2_hash) % n"
      ],
      "metadata": {
        "id": "fp6od_qr672S"
      },
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "i = (s1 - s2) % n\n",
        "j = (e1 - e2) % n"
      ],
      "metadata": {
        "id": "MOlD34mh7rYr"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# incorrect modular division!\n",
        "p_ =  i / j"
      ],
      "metadata": {
        "id": "ucEqm0247spU"
      },
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def eea(a, b):\n",
        "    \"\"\"return (g, x, y) such that a*x + b*y = g = gcd(a, b)\"\"\"\n",
        "    if a == 0:\n",
        "        return (b, 0, 1)\n",
        "    else:\n",
        "        b_div_a, b_mod_a = divmod(b, a)\n",
        "        g, x, y = eea(b_mod_a, a)\n",
        "        return (g, y - b_div_a * x, x)\n",
        "\n",
        "(gcd, x, _) = eea(j, n)\n",
        "if gcd != 1:\n",
        "  raise Exception('GCD of divisor mod n is not 1. Modular inverse is not defined.')"
      ],
      "metadata": {
        "id": "BHgMVjmY7uN0"
      },
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "p = (i * (x % n)) % n"
      ],
      "metadata": {
        "id": "edgk4Wyh7xwE"
      },
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# The output is purposefully omitted here.\n",
        "print(int_to_bytes(p))"
      ],
      "metadata": {
        "id": "xgVaSg9r7zXd"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "from fastecdsa.curve import secp256k1\n",
        "\n",
        "if (p * secp256k1.G).x == P:\n",
        "  print(\"Congratulations, you found the private key\")\n",
        "else:\n",
        "  print(\"Public keys don't match: the private key is incorrect!\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7Niy2eK970iP",
        "outputId": "e9613c5b-d223-4a2c-cce4-2c4935bc8846"
      },
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Congratulations, you found the private key\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Bonus: Extracting the nonce"
      ],
      "metadata": {
        "id": "REHaCdLSsean"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "r1 = (((e1 * p) % n) - s1) % n\n",
        "r2 = (((e2 * p) % n) - s2) % n\n",
        "assert(r1 == r2)"
      ],
      "metadata": {
        "id": "M6VhAh2A76Tb"
      },
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "if (r2 * secp256k1.G).x == R:\n",
        "  print(\"The provided and the calculated nonce commitment R match!\")\n",
        "else:\n",
        "  print(\"Nonce commitments don't match!\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "yLJcIznl78a8",
        "outputId": "c5a05ebe-16eb-4929-fd8c-4c84b5003f87"
      },
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The provided and the calculated nonce commitment R match!\n"
          ]
        }
      ]
    }
  ]
}