Python/BBS_KeyGen.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5949bd41-5c1a-4dab-bc39-b4287da63b91",
   "metadata": {},
   "source": [
    "# BBS+ KeyGen Check\n",
    "\n",
    "Reproducing the test vector from the BBS+ draft:\n",
    "\n",
    "IKM value `746869732d49532d6a7573742d616e2d546573742d494b4d2d746f2d67656e65726174652d246528724074232d6b6579`\n",
    "key_info = `746869732d49532d736f6d652d6b65792d6d657461646174612d746f2d62652d757365642d696e2d746573742d6b65792d67656e`\n",
    "\n",
    "Results in the SK value of `4a39afffd624d69e81808b2e84385cc80bf86adadf764e030caa46c231f2a8d7`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c3434e60-17f9-4953-969a-4c25244925e2",
   "metadata": {},
   "source": [
    "## Algorithm from Draft\n",
    "\n",
    "```\n",
    "SK = KeyGen(IKM, key_info)\n",
    "\n",
    "Inputs:\n",
    "\n",
    "- IKM (REQUIRED), a secret octet string. See requirements above.\n",
    "- key_info (OPTIONAL), an octet string. if this is not supplied, it\n",
    "                       MUST default to an empty string.\n",
    "\n",
    "Definitions:\n",
    "\n",
    "- HKDF-Extract is as defined in [@!RFC5869], instantiated with hash function hash.\n",
    "- HKDF-Expand is as defined in [@!RFC5869], instantiated with hash function hash.\n",
    "- I2OSP and OS2IP are as defined in [@!RFC8017], Section 4.\n",
    "- L is the integer given by ceil((3 * ceil(log2(r))) / 16).\n",
    "- INITSALT is the ASCII string \"BBS-SIG-KEYGEN-SALT-\".\n",
    "\n",
    "Outputs:\n",
    "\n",
    "- SK, a uniformly random integer such that 0 < SK < r.\n",
    "\n",
    "Procedure:\n",
    "\n",
    "1. salt = INITSALT\n",
    "2. SK = 0\n",
    "3. while SK == 0:\n",
    "4.     salt = hash(salt)\n",
    "5.     PRK = HKDF-Extract(salt, IKM || I2OSP(0, 1))\n",
    "6.     OKM = HKDF-Expand(PRK, key_info || I2OSP(L, 2), L)\n",
    "7.     SK = OS2IP(OKM) mod r\n",
    "8. return SK\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1a41505f-5f4b-45f8-b67f-852e5ffe08d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# IKM as bytes\n",
    "IKM = bytes.fromhex('746869732d49532d6a7573742d616e2d546573742d494b4d2d746f2d67656e65726174652d246528724074232d6b6579')\n",
    "print(IKM)\n",
    "print(IKM.hex())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fc76cd3c-ec8e-4224-a27d-ba8beaa0d5c3",
   "metadata": {},
   "outputs": [],
   "source": [
    "# key_info as bytes\n",
    "key_info = bytes.fromhex('746869732d49532d736f6d652d6b65792d6d657461646174612d746f2d62652d757365642d696e2d746573742d6b65792d67656e')\n",
    "print(key_info)\n",
    "print(key_info.hex())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67513844-79a7-4545-8e5a-77861f2e497c",
   "metadata": {},
   "outputs": [],
   "source": [
    "salt = b\"BBS-SIG-KEYGEN-SALT-\"\n",
    "print(salt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca830587-22e8-4ef6-bdc0-33e6f8073072",
   "metadata": {},
   "outputs": [],
   "source": [
    "from hashlib import sha256, sha512\n",
    "use_hash = sha256 # So I can easily try different hashes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f916afd-4384-4cf8-8b47-424928d0865c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Hash the salt\n",
    "m = use_hash()\n",
    "m.update(salt)\n",
    "hashed_salt = m.digest()\n",
    "print(hashed_salt.hex())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9c916b7d-b515-4cdd-b202-288cbc4bd641",
   "metadata": {},
   "outputs": [],
   "source": [
    "import hkdf # From local file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cc134baa-ab2b-4dbd-b14e-be759e2e4f9a",
   "metadata": {},
   "outputs": [],
   "source": [
    "# PRK = HKDF-Extract(salt, IKM || I2OSP(0, 1))\n",
    "PRK = hkdf.hkdf_extract(hashed_salt, IKM + bytes.fromhex('00'), hash=use_hash)\n",
    "print(PRK.hex())\n",
    "print(len(PRK))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8ee2a81b-2931-4bd6-bb1b-779d6e75d2d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Check simple concatenation works...\n",
    "temp_concat = IKM + bytes.fromhex('00')\n",
    "print(temp_concat.hex())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e0c7f8e-e920-42ec-8c89-462c46cb8b8c",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa8b13bc-3ad0-4aa8-8a3a-e65804e92df2",
   "metadata": {},
   "outputs": [],
   "source": [
    "# L is the integer given by ceil((3 * ceil(log2(r))) / 16).\n",
    "r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001\n",
    "L = math.ceil((3 * math.ceil(math.log2(r))) / 16)\n",
    "print(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d0c7bed4-5d81-4e7a-b77b-f448ce39ece7",
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# OKM = HKDF-Expand(PRK, key_info || I2OSP(L, 2), L)\n",
    "i2oL2 = bytes.fromhex('0030') # L=48 which is 0x30\n",
    "print(i2oL2[0], i2oL2[1])\n",
    "OKM = hkdf.hkdf_expand(PRK, key_info + i2oL2, L, hash=use_hash)\n",
    "print(OKM.hex())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "53605195-7adb-43bf-a668-812b50dfffec",
   "metadata": {},
   "outputs": [],
   "source": [
    "# To number and mod\n",
    "OKM_number = int.from_bytes(OKM, \"big\")\n",
    "sk = OKM_number % r\n",
    "# Results in the SK value of `4a39afffd624d69e81808b2e84385cc80bf86adadf764e030caa46c231f2a8d7`?\n",
    "print(hex(sk))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3e4f02c6-343b-4de3-97bb-5d79e0b28aca",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}