Skip to content

Instantly share code, notes, and snippets.

@WitherOrNot

WitherOrNot/pidgenx.ipynb

Last active February 16, 2025 03:27
Show Gist options
  • Save WitherOrNot/d467df09161164f1f1846a61b55a7d6d to your computer and use it in GitHub Desktop.
Save WitherOrNot/d467df09161164f1f1846a61b55a7d6d to your computer and use it in GitHub Desktop.
Download ZIP
PIDGENX validation implementation in SageMath (works on SageMath 9.0)
Display the source blob
Display the rendered blob
Raw
pidgenx.ipynb
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The math in this notebook is described in [this patent](https://patentimages.storage.googleapis.com/a3/27/c1/3c0948a078cb28/US7587605.pdf). Be warned, the math is very complicated."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Windows 7 Retail/GVLK, public key ID 170\n",
"\n",
"pubkey_data = {\n",
" \"field\": {\n",
" \"modulus\": 886368969471450739924935101400677,\n",
" \"ec_base_order\": 886368969471450710152985728350703,\n",
" \"k3_minpoly\": [\n",
" 4,\n",
" 1,\n",
" 0,\n",
" 1\n",
" ],\n",
" \"k6_minpoly\": [\n",
" 2,\n",
" 0,\n",
" 1\n",
" ]\n",
" },\n",
" \"h1_bases\": [\n",
" 1,\n",
" 3,\n",
" 8,\n",
" 15,\n",
" 15,\n",
" 15,\n",
" 31,\n",
" 3,\n",
" 3,\n",
" 3,\n",
" 3,\n",
" 3,\n",
" 7,\n",
" 63\n",
" ],\n",
" \"curve\": {\n",
" \"a\": 26392827536965106777121445123290,\n",
" \"b\": 372325368096095544195525883520589\n",
" },\n",
" \"points\": [\n",
" {\n",
" \"x\": [\n",
" 365236101742748463929673543888206,\n",
" 858097895593939865996182272259769,\n",
" 148438159087534462792506738986740\n",
" ],\n",
" \"y\": [\n",
" 776418047571862972603801173382237,\n",
" 873677028107508092012208744232957,\n",
" 622138327043805563266794621920098\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 940136574680879136511599445781,\n",
" 566978253317108608042529258054523,\n",
" 176284220413545220121710961573292\n",
" ],\n",
" \"y\": [\n",
" 828856809691743749590800150937649,\n",
" 225146018128364550960496522448712,\n",
" 348601659612301002638949468744847\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 733747358623171948496764545320051,\n",
" 728506535527490173098593825125337,\n",
" 82462451162574422717677160727098\n",
" ],\n",
" \"y\": [\n",
" 416331132638004657079841565104549,\n",
" 366794872410090667339979925100938,\n",
" 154519017608105570119249112044121\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 849718119860311390685018324089317,\n",
" 69736499980142833460080381132368,\n",
" 72139323263966224829624934948858\n",
" ],\n",
" \"y\": [\n",
" 122550620604034160835298121626961,\n",
" 232865179257577260620478614346661,\n",
" 96495922331236902442197840422963\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 737949449696062407373114808812927,\n",
" 526576673882551145431025311648593,\n",
" 577710732700754839750249914833193\n",
" ],\n",
" \"y\": [\n",
" 245977198113437420529250724111432,\n",
" 316396368275232555978824338443046,\n",
" 755792900000892204654488821885538\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 712586405875738967442641545880322,\n",
" 615445286425878710157557053762371,\n",
" 734183236086095230968388017605820\n",
" ],\n",
" \"y\": [\n",
" 851284376759840359812981263306021,\n",
" 769237654873203944088649987250083,\n",
" 359324880331507581802773028306633\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 579665839598807564349118802507078,\n",
" 793103874095793223248478622956780,\n",
" 502860226530799804560661048077280\n",
" ],\n",
" \"y\": [\n",
" 526775274489316486107329470634542,\n",
" 828721161962151275145535457964404,\n",
" 204415317809040518371881977645416\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 804790447447351785544412956578788,\n",
" 119046642031064430140912082580578,\n",
" 475159529884254928674792290619954\n",
" ],\n",
" \"y\": [\n",
" 458245266057063984580129835988070,\n",
" 338411981227059768831710308435687,\n",
" 577923375329917551735757167190702\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 448295070796654878810211055051604,\n",
" 482910785083759911781193909334072,\n",
" 795628820954832750108065551162801\n",
" ],\n",
" \"y\": [\n",
" 417757375223493128894380427308216,\n",
" 755520039102173573177271365439537,\n",
" 863842006193777913816171128026446\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 663389221842281261857262032548436,\n",
" 846447543951704162020988219326272,\n",
" 686142287698732386980948449542167\n",
" ],\n",
" \"y\": [\n",
" 769015970121598916167134609518482,\n",
" 738460771147019950148429256265493,\n",
" 613009789239563486872501072748270\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 23530113060362511985797534739195,\n",
" 718131004725002854064127778364823,\n",
" 140870968646848990835780066321375\n",
" ],\n",
" \"y\": [\n",
" 641031697928634900295866764583620,\n",
" 295544383156746469642549388283327,\n",
" 133766761871461067699690599056442\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 7518354584460889742005963384331,\n",
" 340825540582760123772991939806390,\n",
" 525549834323799848592419044187971\n",
" ],\n",
" \"y\": [\n",
" 585295007893871934790357000030208,\n",
" 117490751031779271453224407217079,\n",
" 838852298106199238437827740364400\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 806036388470182281562651653929939,\n",
" 266085928879449679004785507000719,\n",
" 201474020142460453395308745398496\n",
" ],\n",
" \"y\": [\n",
" 573468377549807523205344415925956,\n",
" 667459718759242575444856430313959,\n",
" 226975716159080217447594275999935\n",
" ]\n",
" },\n",
" {\n",
" \"x\": [\n",
" 794167987155642331621801361756614,\n",
" 809201520617560616339201020039820,\n",
" 198696155869194654384403079624544\n",
" ],\n",
" \"y\": [\n",
" 725959545288387914551997303844726,\n",
" 49262476800238214847233993847181,\n",
" 537326577113493149345527624223733\n",
" ]\n",
" }\n",
" ],\n",
" \"pairing_val\": [\n",
" [\n",
" 242940802691096077821709859741616,\n",
" 178851543248946074944443141484182,\n",
" 802059826004050667481466713086225\n",
" ],\n",
" [\n",
" 701042518368651902930590425782509,\n",
" 265571225406900742458432149860962,\n",
" 699432283102586243018242179516873\n",
" ]\n",
" ]\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"p = pubkey_data[\"field\"][\"modulus\"]\n",
"a = pubkey_data[\"curve\"][\"a\"]\n",
"b = pubkey_data[\"curve\"][\"b\"]\n",
"order = pubkey_data[\"field\"][\"ec_base_order\"]\n",
"h1_bases = list(map(lambda x: x+1, pubkey_data[\"h1_bases\"]))\n",
"KCHARS = \"BCDFGHJKMPQRTVWXY2346789\"\n",
"\n",
"def decode_pkey(k):\n",
" k = k.replace(\"-\", \"\")\n",
" out = 0\n",
" \n",
" for c in k:\n",
" out *= 24\n",
" out += KCHARS.index(c)\n",
" \n",
" return out\n",
"\n",
"K = GF(p)\n",
"Kx.<x> = K[]\n",
"K3.<u> = K.extension(Kx(pubkey_data[\"field\"][\"k3_minpoly\"]))\n",
"K3y.<y> = K3[]\n",
"K6.<t> = K3.extension(K3y(pubkey_data[\"field\"][\"k6_minpoly\"]))\n",
"\n",
"E = EllipticCurve(K, [a, b])\n",
"E6 = EllipticCurve(K6, [a, b])\n",
"\n",
"Qi = [E6(K3(point[\"x\"]) * t^-2, K3(point[\"y\"]) * t^-3) for point in pubkey_data[\"points\"]]\n",
"\n",
"# pairing_val = e_m(P, S)\n",
"pairing_val = K6([K3(pubkey_data[\"pairing_val\"][0]), K3(pubkey_data[\"pairing_val\"][1])])\n",
"\n",
"assert is_prime(p)\n",
"assert len(h1_bases) == len(Qi)\n",
"assert h1_bases[0] == 2\n",
"assert pairing_val^order == 1"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pkey_chars = \"33PXH-7Y6KF-2VJC9-XBBR8-HVTHH\"\n",
"\n",
"# pkey = HASH(M)\n",
"# HASH is a currently unknown hash function\n",
"pkey = decode_pkey(pkey_chars)\n",
"\n",
"# h1_coeffs = H1(M)\n",
"# During validation, coeffs must be found by a search that i havent implemented\n",
"# h1_coeffs = [1, 0, 7, 1, 4, 15, 9, 1, 1, 0, 2, 1, 0, 19]\n",
"\n",
"# 10 bits unknown, 30 bits product ID, 1 bit unknown (upgrade?)\n",
"key_data = (342 << 31 | 918500000 << 1 | 0)\n",
"h1_coeffs = [1]\n",
"\n",
"for i in range(len(h1_bases) - 1):\n",
" h1_coeffs.append(key_data % h1_bases[i + 1])\n",
" key_data //= h1_bases[i + 1]\n",
"\n",
"print(h1_coeffs)\n",
"\n",
"# H2(M) = E.lift_x(HASH(M) % p)\n",
"T = E6(E.lift_x(pkey % p))\n",
"Q = sum(map(lambda x: x[0] * x[1], zip(h1_coeffs, Qi))) \n",
"\n",
"test_pairing = T.tate_pairing(Q, order, 6, q=p)\n",
"\n",
"print(test_pairing == pairing_val or test_pairing == 1/pairing_val)\n",
"\n",
"key_data = 0\n",
"\n",
"for i in range(len(h1_bases) - 1, 0, -1):\n",
" key_data *= h1_bases[i]\n",
" key_data += h1_coeffs[i]\n",
" print(h1_bases[i], h1_coeffs[i], key_data)\n",
"\n",
"pid = (key_data & ((1 << 31) - 1)) >> 1"
]
}
],
"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.8.10"
}
},
"nbformat": 4,
"nbformat_minor": 4
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment