Last active
September 22, 2022 07:03
-
-
Save 0xB10C/62cb252c24cbe5a8b3f3014ec0acc625 to your computer and use it in GitHub Desktop.
Code for the write-up of Elliott's first Bitcoin-flavored cryptography challenge. https://b10c.me/blog/009-schnorr-nonce-reuse-challenge/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"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" | |
] | |
} | |
] | |
} | |
] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment