algorithm_overview.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ecdsa.ellipticcurve as ecc\n",
    "import ecdsa.numbertheory as nt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Diffie Hellman Shared Secret\n",
    "Elliptic Cryptography is based on the [Discrete Logarithm Problem](https://jeremykun.com/2014/03/31/elliptic-curve-diffie-hellman/). In essense, we can simplify the idea to\n",
    "> Adding  is easy on elliptic curves,  but **undoing** addition seems hard\n",
    "\n",
    "More formally, we can give the following definition: Let $G$ be an additive  group, and let $x,y$ be elements of $G$ so that $x=ny$ for some integer $n$. The Discrete  Logarithm Problem asks one to find $n$ when given $x$ and $y$.\n",
    "\n",
    "In integers, this problem is quite easy.\n",
    "If I have:\n",
    "- $x=12$\n",
    "- $y=4185072$\n",
    "\n",
    "Then, I can compute that $y=41805072=348756*12=348756x \\rightarrow  n=348756$.\n",
    "\n",
    "> Division for integers is efficient, **but for elliptic curves this is not the case**.\n",
    "\n",
    "Here is a toy problem testing my understanding of DH's shared secret protocol."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Diffie Hellman Shared Secret POC\n",
    "def sendDH(privateKey, generator, sendFunction):\n",
    "   return sendFunction(privateKey * generator)\n",
    "\n",
    "def receiveDH(privateKey, receiveFunction):\n",
    "   return privateKey * receiveFunction()\n",
    "\n",
    "prime = 3851\n",
    "a = 324\n",
    "b = 1287\n",
    "myCurve = ecc.CurveFp(prime, a, b, 1)\n",
    "basePoint = ecc.Point(myCurve, 920, 303)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "aliceSecretKey = 233    # generateSecretKey(8)\n",
    "bobSecretKey = 25       # generateSecretKey(8)\n",
    "\n",
    "alicePublicKey = sendDH(aliceSecretKey, basePoint, lambda x:x)\n",
    "bobPublicKey = sendDH(bobSecretKey, basePoint, lambda x:x)\n",
    "\n",
    "sharedSecret1 = receiveDH(bobSecretKey, lambda: alicePublicKey)\n",
    "sharedSecret2 = receiveDH(aliceSecretKey, lambda: bobPublicKey)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CurveFp(p=3851, a=324, b=1287, h=1)\n",
      "(920,303)\n",
      "Shared secret is (1001,3826) == (1001,3826)\n"
     ]
    }
   ],
   "source": [
    "print(myCurve)\n",
    "print(basePoint)\n",
    "print('Shared secret is %s == %s' % (sharedSecret1, sharedSecret2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithm Overview\n",
    "Steps to implement\n",
    "1. Hashing password into elliptic curve\n",
    "    - PWD entered by user\n",
    "    - SHA-256 computation, hashing into the NIST P-256 Curve\n",
    "    - this is computed on input + iteration_counter $\\rightarrow Z_q$.\n",
    "    - computed value is considered $x$ coord of a point on curve if $y$-value is associated with it is a quadratic residue (i.e. $x,y$ satisfy the curve equation).\n",
    "    - this is repeated until a curve element is obtained. (which is the output)\n",
    "    - Password is concatenated with domain name and input into H'. (ADD RESISTANCE AGAINST PHISHING)\n",
    "2. FK-PTR OPRF protocol\n",
    "    1. EXTENSION:\n",
    "        - Blind the password with OPRF\n",
    "            - OPRF: $F_k(x)=H(x,(H'(x))^k)$\n",
    "                - input $x$ from client\n",
    "                - $k$ is from device\n",
    "                - H maps from arbitrary length string $\\rightarrow e \\in \\{0,1\\}^\\tau$, $\\tau$ is a security parameter\n",
    "                    - Looking at the formula for OPRF, we assume that H(xbytearray, point in G) = $H(x || P_x || P_y)$\n",
    "                - H' maps from arbitrary length string $\\rightarrow g \\in G$\n",
    "                    - H' is the \"Hash into Elliptic Curve\" function, which maps the password into a point on NIST P-256 curve\n",
    "            - works over a group $G$ of prime order $p$ (e.g. NIST P-256 group)\n",
    "        - extension picks a random number $\\rho \\in Z_q$ and raises the hash value of the input to the power $\\rho$.\n",
    "            - this blinding factor $\\rho$ hides the password with information-theoretic security)\n",
    "        SEND THIS AS $\\alpha$\n",
    "    2. DEVICE\n",
    "        - check if $\\alpha$ is $\\in G$\n",
    "        - compute and SEND BACK $\\beta = \\alpha^k$\n",
    "    3. BACK TO EXTENSION\n",
    "        - check if $\\beta$ is $\\in G$\n",
    "        - raise the recieved value to the power of $\\rho^{-1} \\in Z_q$\n",
    "        - then compute the SHA-256 hash of calculated value.\n",
    "    4. BACK TO RWD PASSWORD\n",
    "        - (same as PwdHash implementation)\n",
    "        - encoded to a random combination of letters, numbers and symbols matching the passwrod requirement of the visited website and entered into pwd field of login page.\n",
    "        \n",
    "## N.B.\n",
    "- taking the exponential in a group is just repetition of the operation\n",
    "    - i.e. $\\forall x \\in G, n \\in Z, x^n = \\underbrace{x+...+x}_\\text{n times}$.\n",
    "    - see this [crypto stack exchange thread](https://crypto.stackexchange.com/questions/57768/exponentiation-in-ecc)\n",
    "- how to take the inverse power in a group\n",
    "    - Raise the point to the power $a^{-1} \\in Z_p$\n",
    "    - this is fairly easy to do with [euclidean algorithm](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)\n",
    "    - see [stack exchange link](https://math.stackexchange.com/questions/471269/point-division-in-elliptic-curve-cryptography) for more info\n",
    "- Instantiation assumes a cyclic group $G$ of prime order $q$, $|q|=\\tau$, with generator $g$. \n",
    "    - At init, User chooses master password pwd, while Device chooses and stores $k \\leftarrow Z_q$.\n",
    "- H which looks like it accepts two arguments when it's called in $H(x, (H'(x))^k)$ really just means hash it all at once, by appending it.\n",
    "    - in the paper, it describes this step as \"Client hashes this value $(H'(pwd|domain))^k$ with the pwd to obtain rwd\"\n",
    "    - in the implementation, they use `crypto_generichash_update()` from [source.](https://github.com/stef/libsphinx/blob/master/src/sphinx.c)\n",
    "    - furthermore, in the documentation for `<sodium.h>` they use this function to compute the hash on a multi-part [example](https://libsodium.gitbook.io/doc/hashing/generic_hashing#multi-part-example-with-a-key)\n",
    "    - there is a reddit thread which also explains how the function used can be used to hash variable length things such as a [stream](https://www.reddit.com/r/crypto/comments/7ooot2/using_libsodiums_generic_hash_to_hash_a_file/)\n",
    "- the notation of $\\{0,1\\}^\\tau$ means a bit string of length $\\tau$\n",
    "    - From this [paper on hashing into Elliptic Curves](https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-01#page-4), they describe the following notation:\n",
    "        - \"bitstring of arbitrary length is denoted as $\\{0, 1\\}^*$\"\n",
    "- octet means base-256, and not to be confused with octal which is base-8"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Curve definition\n",
    "Using the primitives from `ecdsa` package in python, we will create the following curve based on the parameters for P-256."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# https://github.com/warner/python-ecdsa/blob/333ee3feb1dfc6797db7a83d221e5a3a9fafdc3f/src/ecdsa/ecdsa.py\n",
    "# NIST Curve P-256:\n",
    "# ORDER = 115792089210356248762697446949407573529996955224135760342422259061068512044369\n",
    "PRIME = 115792089210356248762697446949407573530086143415290314195533631308867097853951\n",
    "R = 115792089210356248762697446949407573529996955224135760342422259061068512044369\n",
    "# s = 0xc49d360886e704936a6678e1139d26b7819f7e90L\n",
    "# c = 0x7efba1662985be9403cb055c75d4f7e0ce8d84a9c5114abcaf3177680104fa0dL\n",
    "A = -3\n",
    "B = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B\n",
    "Gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296\n",
    "Gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5\n",
    "\n",
    "curve_256 = ecc.CurveFp(PRIME, A, B, 1)\n",
    "curve_256_generator = ecc.PointJacobi(curve_256, Gx, Gy, 1, R, generator=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Hashing password into elliptic curve\n",
    "### 1.1 HashToBase Implementation\n",
    "Here is a definition of the function:\n",
    "HashToBase(x): $H(x)[0:log_2(p) + 1]$, i.e., hash-truncate-reduce, where H is a cryptographic hash function, such as SHA256, and $p$ is the prime order of base field $F_p$.\n",
    "Here is some psuedo code:\n",
    "```\n",
    "HashToBase(x, i)\n",
    "\n",
    "Parameters:\n",
    "\n",
    " H - cryptographic hash function to use\n",
    " hbits - number of bits output by H\n",
    " p - order of the base field Fp\n",
    " label - context label for domain separation\n",
    "\n",
    "Preconditions:\n",
    "\n",
    " floor(log2(p)) + 1 >= hbits\n",
    "\n",
    "Input:\n",
    "\n",
    " x - value to be hashed, an octet string\n",
    " i - hash call index, a non-negative integer\n",
    "\n",
    "Output:\n",
    "\n",
    " y - a value in the field Fp\n",
    "\n",
    "Steps:\n",
    "\n",
    " 1. t1 = H(\"h2c\" || label || I2OSP(i, 4) || x)\n",
    " 2. t2 = OS2IP(t1)\n",
    " 3. y = t2 (mod p)\n",
    " 4. Output y\n",
    "\n",
    "where I2OSP, OS2IP [RFC8017] are used to convert an octet string to\n",
    "and from a non-negative integer, and a || b denotes concatenation of\n",
    "a and b.\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "OCT TEST: I2OSP(23) = b'\\x00\\x00\\x00\\x17', and then OS2IP(I2OSP(23)) = 23\n",
      "115792089210356248762697446949407573530086143415290314195533631308867097853951\n",
      "115792089210356248762697446949407573529996955224135760342422259061068512044369\n",
      "HashToBase(I2OSP(23)=b'\\x00\\x00\\x00\\x17', 11) = 52666019840208479355183598407159392888009956878866650321053742936543132317912\n"
     ]
    }
   ],
   "source": [
    "from binascii import hexlify, unhexlify\n",
    "from hashlib import sha1, sha256, sha384, sha512\n",
    "import hashlib\n",
    "from ecdsa import NIST256p\n",
    "\n",
    "# http://www.secg.org/sec2-v2.pdf\n",
    "# print(NIST256p.oid)\n",
    "ORDER = NIST256p.order\n",
    "# from https://tools.ietf.org/html/rfc8017#section-4.1\n",
    "# Octet-String-to-Integer primitive\n",
    "\n",
    "# https://stackoverflow.com/questions/39964383/implementation-of-i2osp-and-os2ip\n",
    "# def OS2IP(X):\n",
    "#         xLen = len(X)\n",
    "#         X = X[::-1]\n",
    "#         x = 0\n",
    "#         for i in range(xLen):\n",
    "#             x += X[i] * 256**i\n",
    "#         return x\n",
    "\n",
    "# https://stackoverflow.com/questions/2267362/how-to-convert-an-integer-in-any-base-to-a-string\n",
    "# def numberToBase(n, b):\n",
    "#     if n == 0:\n",
    "#         return [0]\n",
    "#     digits = []\n",
    "#     while n:\n",
    "#         digits.append(int(n % b))\n",
    "#         n //= b\n",
    "#     return digits[::-1]\n",
    "\n",
    "# https://github.com/bdauvergne/python-pkcs1/blob/master/pkcs1/primitives.py\n",
    "def OS2IP(x: str) -> int:\n",
    "    '''Converts the byte string x representing an integer reprented using the\n",
    "       big-endian convient to an integer.\n",
    "    '''\n",
    "    h = hexlify(x) #.binascii\n",
    "    return int(h, 16)\n",
    "\n",
    "#Integer-to-Octet-String primitive\n",
    "# def I2OSP(integer, length):\n",
    "#     # find the length, or pass it in\n",
    "#     if integer >= 256**length:\n",
    "#         raise ValueError(\"integer {} too large\".format(integer))\n",
    "#     return numberToBase(integer, 256)[:length]\n",
    "\n",
    "# https://stackoverflow.com/questions/39964383/implementation-of-i2osp-and-os2ip\n",
    "# def I2OSP(x, xLen):\n",
    "#         if x >= 256**xLen:\n",
    "#             raise ValueError(\"integer too large\")\n",
    "#         digits = []\n",
    "\n",
    "#         while x:\n",
    "#             digits.append(int(x % 256))\n",
    "#             x //= 256\n",
    "#         for i in range(xLen - len(digits)):\n",
    "#             digits.append(0)\n",
    "#         return digits[::-1]\n",
    "\n",
    "# https://en.wikipedia.org/wiki/Mask_generation_function\n",
    "# def I2OSP(integer: int, size: int = 4) -> str:\n",
    "#     return ''.join([chr((integer >> (8 * i)) & 0xFF) for i in reversed(range(size))])\n",
    "\n",
    "# https://github.com/bdauvergne/python-pkcs1/blob/master/pkcs1/primitives.py\n",
    "def I2OSP(x: int, x_len: int = 4) -> str:\n",
    "    '''Converts the integer x to its big-endian representation of length\n",
    "       x_len.\n",
    "    '''\n",
    "    if x > 256**x_len:\n",
    "        raise ValueError(\"Integer too large.\")\n",
    "    h = hex(x)[2:]\n",
    "    if h[-1] == 'L':\n",
    "        h = h[:-1]\n",
    "    if len(h) & 1 == 1:\n",
    "        h = '0%s' % h\n",
    "    x = unhexlify(h) #.binascii\n",
    "    return b'\\x00' * int(x_len-len(x)) + x\n",
    "\n",
    "print(\"OCT TEST: I2OSP(23) = {}, and then OS2IP(I2OSP(23)) = {}\".format(I2OSP(23, 4), OS2IP(I2OSP(23, 4))))\n",
    "\n",
    "\n",
    "\n",
    "# https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-02#appendix-C.5\n",
    "def HashToBase(x: bytearray, i: int, label: str=\"label\", p: int=ORDER) -> int:\n",
    "    '''Hashes the bytearray x with a label string, the hash call index i, and\n",
    "       returns y, a value in the field F_p\n",
    "    '''\n",
    "    H = sha256()\n",
    "    toHash = [\"h2c\", label, I2OSP(i, 4), x]\n",
    "    H.update(b\"hc2\")\n",
    "    H.update(label.encode())\n",
    "#     H.update(I2OSP(i,4))\n",
    "    H.update(str(i).encode())\n",
    "    H.update(x)\n",
    "    t1 = H.digest()\n",
    "    t2 = OS2IP(t1)\n",
    "    return (t2 % p) # = y\n",
    "    \n",
    "valueToBeHashed = 23\n",
    "hashCallIndex = 11\n",
    "print(PRIME)\n",
    "print(ORDER)\n",
    "print(\"HashToBase(I2OSP({})={}, {}) = {}\".format(valueToBeHashed, \n",
    "                                                 I2OSP(valueToBeHashed), \n",
    "                                                 hashCallIndex, \n",
    "                                                 HashToBase(I2OSP(valueToBeHashed), hashCallIndex)\n",
    "                                                ))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Simplified SWU Method (5.2.3.)\n",
    "As per the [hashing into elliptic curves paper](https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-02#section-5.2.3), for P-256 curve, we should use Simple SWU. \n",
    "\n",
    "```\n",
    "The following map2curve_simple_swu(alpha) implements the simplified\n",
    "Shallue-Woestijne-Ulas algorithm from [SimpleSWU].  This algorithm\n",
    "works for any curve over F_{p^n}, where p = 3 mod 4, including:\n",
    "\n",
    "o  P256\n",
    "\n",
    "o  ...\n",
    "```\n",
    "Given curve equation $g(x) = x^3 + Ax + B$, this algorithm works as follows:\n",
    "   1. t = `HashToBase(\\alpha)`\n",
    "   2. $\\alpha = \\frac{-b}{a} * (1+\\frac{1}{t^4 + t^2})$\n",
    "   3. $\\beta = -t^2 * \\alpha$\n",
    "   4. If $g(\\alpha)$ is square, output $(\\alpha, \\sqrt{g(\\alpha)})$\n",
    "   5. Output $(\\beta, \\sqrt{g(\\beta)})$\n",
    "\n",
    "The following procedure implements this algorithm.  It outputs a point with affine coordinates.  It requires knowledge of A and B, the constants from the curve Weierstrass form.\n",
    "```\n",
    "map2curve_simple_swu(alpha)\n",
    "\n",
    "   Input:\n",
    "\n",
    "     alpha - value to be encoded, an octet string\n",
    "\n",
    "   Output:\n",
    "\n",
    "     (x, y) - a point in E\n",
    "\n",
    "   Steps:\n",
    "\n",
    "   1.     t = HashToBase(alpha)\n",
    "   2. alpha = t^2 (mod p)\n",
    "   3. alpha = alpha * -1 (mod p)\n",
    "   4. right = alpha^2 + alpha (mod p)\n",
    "   5. right = right^(-1) (mod p)\n",
    "   6. right = right + 1 (mod p)\n",
    "   7.  left = B * -1 (mod p)\n",
    "   8.  left = left / A (mod p)\n",
    "   9.    x2 = left * right (mod p)\n",
    "   10.   x3 = alpha * x2 (mod p)\n",
    "   11.   h2 = x2 ^ 3 (mod p)\n",
    "   12.   i2 = x2 * A (mod p)\n",
    "   13.   i2 = i2 + B (mod p)\n",
    "   14.   h2 = h2 + i2 (mod p)\n",
    "   15.   h3 = x3 ^ 3 (mod p)\n",
    "   16.   i3 = x3 * A (mod p)\n",
    "   17.   i3 = i3 + B (mod p)\n",
    "   18.   h3 = h3 + i3 (mod p)\n",
    "   19.   y1 = h2 ^ ((p + 1) / 4) (mod p)\n",
    "   20.   y2 = h3 ^ ((p + 1) / 4) (mod p)\n",
    "   21.    e = CTEQ(y1 ^ 2, h2)   // Constant-time equality\n",
    "   22.    x = CMOV(x2, x3, e)    // If e = 1, choose x2, else choose x3\n",
    "   23.    y = CMOV(y1, y2, e)    // If e = 1, choose y1, else choose y2\n",
    "   24. Output (x, y)\n",
    "```\n",
    "\n",
    "### Helper functions\n",
    "```\n",
    "o  CMOV(a, b, c): If c = 1, return a, else return b.\n",
    "\n",
    "  Common software implementations of constant-time selects assume c\n",
    "  = 1 or c = 0.  CMOV may be implemented by computing the desired\n",
    "  selector (0 or 1) by ORing all bits of c together.  The end result\n",
    "  will be either 0 if all bits of c are zero, or 1 if at least one\n",
    "  bit of c is 1.\n",
    "\n",
    "o  CTEQ(a, b): Returns a == b.  Inputs a and b must be the same\n",
    "  length (as bytestrings) and the comparison must be implemented in\n",
    "  constant time.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CHECK: ensure p = 115792089210356248762697446949407573530086143415290314195533631308867097853951 = 3 mod 4, 3mod4 = 3mod4: True\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Note: you cannot do A // B % PRIME, instead you should do A * B^-1 = A * pow(B, PRIME-2, PRIME)\n",
    "# genius> 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B / 3 mod 115792089210356248762697446949407573530086143415290314195533631308867097853951\n",
    "# = 52283484311836130297341192243151613979733528143761346583456295874302188418414\n",
    "negBonA = 52283484311836130297341192243151613979733528143761346583456295874302188418414 \n",
    "\n",
    "print(\"CHECK: ensure p = {} = 3 mod 4, {}mod4 = 3mod4: {}\\n\".format(PRIME, PRIME%4, PRIME%4==3))\n",
    "\n",
    "# https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-02#section-5.2.3\n",
    "# Implementation of H' which maps from bytearray -> g \\in G\n",
    "def map2curve_simple_swu(alpha: bytearray) -> (int, int):\n",
    "    '''Maps the octet bytearray alpha into the elliptic curve, and returns a\n",
    "       point from the elliptic curve.\n",
    "    '''\n",
    "    t =  HashToBase(alpha, 1)\n",
    "    alpha = pow(t, 2, PRIME)\n",
    "    alpha = -alpha % PRIME\n",
    "    right = (pow(alpha, 2, PRIME) + alpha) % PRIME\n",
    "    right = pow(right, PRIME-2, PRIME) # right^(-1) % PRIME    \n",
    "    right = (right + 1)  % PRIME\n",
    "    left = -B % PRIME\n",
    "    left =  (left * pow(A, PRIME-2, PRIME)) % PRIME # (left * A^-1) % PRIME\n",
    "    x2 = (left * right) % PRIME\n",
    "    x3 = (alpha * x2)  % PRIME\n",
    "    h2 = pow(x2, 3, PRIME) # x2 ^ 3  % PRIME\n",
    "    i2 = (x2 * A)  % PRIME\n",
    "    i2 = (i2 + B) % PRIME\n",
    "    h2 = (h2 + i2)  % PRIME\n",
    "    h3 = pow(x3, 3, PRIME) # x3 ^ 3  % PRIME\n",
    "    i3 = (x3 * A)  % PRIME\n",
    "    i3 = (i3 + B)  % PRIME\n",
    "    h3 = (h3 + i3)  % PRIME\n",
    "    y1 = pow(h2, (PRIME+1) // 4, PRIME) # h2 ^ ((p + 1) / 4)  % PRIME\n",
    "    y2 = pow(h3, (PRIME+1) // 4, PRIME) # h3 ^ ((p + 1) / 4)  % PRIME\n",
    "    if pow(y1, 2, PRIME) == h2:\n",
    "        return ecc.Point(curve_256, x2, y1)\n",
    "    else:\n",
    "        return ecc.Point(curve_256, x3, y2)\n",
    "\n",
    "# # 1. t = HashToBase(alpha)\n",
    "# # 2. alpha = (-B / A) * (1 + (1 / (t^4 + t^2)))\n",
    "# # 3. beta = -t^2 * alpha\n",
    "# # 4. If g(alpha) is square, output (alpha, sqrt(g(alpha)))\n",
    "# # 5. Output (beta, sqrt(g(beta)))\n",
    "# def my_swu(alpha: bytearray) -> (int, int):\n",
    "#     t = HashToBase(alpha,1)\n",
    "#     alpha_left = -B % PRIME\n",
    "#     alpha_left = (alpha_left // A) % PRIME\n",
    "#     alpha_right = pow(t, 4, PRIME)\n",
    "#     alpha_right = (alpha_right + pow(t, 2, PRIME)) % PRIME\n",
    "#     alpha_right = pow(alpha_right, PRIME-2, PRIME)\n",
    "#     alpha = (alpha_left * alpha_right) % PRIME\n",
    "#     beta = -alpha % PRIME\n",
    "#     beta = (beta * pow(t, 2, PRIME)) % PRIME\n",
    "#     galpha = (pow(alpha, 2, PRIME) + A) % PRIME\n",
    "#     galpha = (galpha * alpha) % PRIME\n",
    "#     galpha = (galpha + B) % PRIME\n",
    "#     sqrtgalpha = pow(galpha, (PRIME + 1) // 4, PRIME)\n",
    "#     if pow(sqrtgalpha, 2, PRIME) == galpha:\n",
    "#         print(\"alpha, \\tsga^2 = ga\")\n",
    "#         return (alpha, sqrtgalpha)\n",
    "#     else:\n",
    "#         gbeta = (pow(beta, 2, PRIME) + A) % PRIME\n",
    "#         gbeta = (gbeta * beta) % PRIME\n",
    "#         gbeta = (gbeta + B) % PRIME\n",
    "#         sqrtgbeta = pow(gbeta, (PRIME + 1) // 4, PRIME)\n",
    "#         print(\"beta, \\tsgb^2 = gb? {}\".format(pow(sqrtgbeta,2,PRIME)%PRIME == gbeta))\n",
    "#         return (beta, sqrtgbeta)\n",
    "\n",
    "# Implemented via the Simple SWU paper: https://eprint.iacr.org/2009/340.pdf\n",
    "# 1. alpha = -t^2\n",
    "# 2. X2 = -B/A * (1 + 1/(alpha^2 + alpha))\n",
    "# 3. X3 = alpha*X2\n",
    "# 4. h2 = g(X2), h3 = g(x3), if g(x) = x^3 + Ax + B\n",
    "# 5. if h2 is square, return (X2, sqrt(g(X2))), else return (X3, sqrt(g(X3)))\n",
    "def my_swu(alpha: bytearray, debug: bool=False) -> (int, int):\n",
    "    # 1. alpha = -t^2\n",
    "    t = HashToBase(alpha,1)\n",
    "    print(\"0. HashToBase(alpha)= \\t\\t\\t\", t) if debug else None\n",
    "    alpha = (-pow(t, 2, PRIME)) % PRIME\n",
    "    print(\"1. alpha=-t^2= \\t\\t\\t\\t\", alpha) if debug else None\n",
    "    \n",
    "    #X2 = -B/A * (1 + 1/(alpha^2 + alpha))\n",
    "    X2_left = -B % PRIME\n",
    "    X2_left = (X2_left * pow(A, PRIME-2, PRIME)) % PRIME\n",
    "    # X2_left = 52283484311836130297341192243151613979733528143761346583456295874302188418414\n",
    "    print(\"2.1 X2_left=-B/A= \\t\\t\\t\", X2_left) if debug else None\n",
    "    \n",
    "    X2_right = (alpha+1) % PRIME\n",
    "    X2_right = (X2_right*alpha) % PRIME\n",
    "    X2_right = pow(X2_right, PRIME-2, PRIME)\n",
    "    X2_right = (X2_right + 1) % PRIME\n",
    "    print(\"2.2 X2_right=1+1/(alpha^2+alpha)= \\t\", X2_right) if debug else None\n",
    "    X2 = (X2_left * X2_right) % PRIME\n",
    "    print(\"2.3 X2= \\t\\t\\t\\t\", X2) if debug else None\n",
    "    \n",
    "    # X3 = alpha*X2\n",
    "    X3 = (alpha*X2) % PRIME\n",
    "    print(\"3. X3=alpha*X2= \\t\\t\\t\", X3) if debug else None\n",
    "    \n",
    "    # h2 = g(X2), h3 = g(x3), if g(x) = x^3 + Ax + B\n",
    "    h2 = (pow(X2, 3, PRIME) + (A * X2)%PRIME + B) % PRIME\n",
    "    h3 = (pow(X3, 3, PRIME) + (A * X3)%PRIME + B) % PRIME\n",
    "    print(\"4.1 g(X2)= \\t\\t\\t\\t\", h2) if debug else None\n",
    "    print(\"4.2 g(X3)= \\t\\t\\t\\t\", h3) if debug else None\n",
    "    sh2 = pow(h2, (PRIME+1)//4, PRIME)\n",
    "    sh3 = pow(h3, (PRIME+1)//4, PRIME)\n",
    "    print(\"5.1 sqrt(g(X2))= \\t\\t\\t\", sh2) if debug else None\n",
    "    print(\"5.2 sqrt(g(X3))= \\t\\t\\t\", sh3) if debug else None\n",
    "    if pow(sh2, 2, PRIME) == h2:\n",
    "        print(\"X2, sh2^2 = h2\") if debug else None\n",
    "        return ecc.Point(curve_256, X2, sh2)\n",
    "    else:\n",
    "        print(\"X3, sh3^2 = h3? {}\".format(pow(sh3,2,PRIME) == h3)) if debug else None\n",
    "        return ecc.Point(curve_256, X3, sh3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2.1 Testing Correctness\n",
    "Testing the SWU's implementation vs HashToBase's implementation, and showing it can successfully hash into the curve with all inputs `range(0, test_cases)`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "correct: 30, are [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]\n"
     ]
    }
   ],
   "source": [
    "test_cases = 30\n",
    "correct = 0\n",
    "correct_list = []\n",
    "for test in range(test_cases):\n",
    "    p = map2curve_simple_swu(I2OSP(test))\n",
    "    if curve_256.contains_point(p.x(), p.y()):\n",
    "        correct += 1\n",
    "        correct_list.append(test)\n",
    "    \n",
    "print(\"correct: {}, are {}\".format(correct, correct_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "correct: 30, are [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]\n"
     ]
    }
   ],
   "source": [
    "test_cases = 30\n",
    "correct = 0\n",
    "correct_list = []\n",
    "for test in range(test_cases):\n",
    "    p = my_swu(I2OSP(test))\n",
    "    if curve_256.contains_point(p.x(), p.y()):\n",
    "        correct += 1\n",
    "        correct_list.append(test)\n",
    "    \n",
    "print(\"correct: {}, are {}\".format(correct, correct_list))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3 Usage of SWU"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(50560896577634328033374378148020771698070026914100043083631439008968958738601,96434689098651036750287593872426977420942250920898794682863763170885260996734)\n",
      "(50560896577634328033374378148020771698070026914100043083631439008968958738601,96434689098651036750287593872426977420942250920898794682863763170885260996734)\n"
     ]
    }
   ],
   "source": [
    "# Example of hashing from password to point on curve\n",
    "print(map2curve_simple_swu(b\"passwordwww.facebook.com\"))\n",
    "\n",
    "# or you can use the og swu implementation\n",
    "print(my_swu(b\"passwordwww.facebook.com\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2 SPHINX architecture\n",
    "## steps to reproduce\n",
    "Notes:\n",
    "- x is a byte array\n",
    "- $g \\in G$\n",
    "\n",
    "\n",
    "1. client(x: bytearray) -> Point:\n",
    "    - takes $x=masterpassword || domainname$\n",
    "    - calculates $H'(x)$: bytearray -> $P(x,y) \\in G$\n",
    "    - picks a random number $\\rho$\n",
    "    - calculates and returns the blinded result $\\alpha = H'(x)^\\rho$\n",
    "2. device($\\alpha$: Point) -> Point:\n",
    "    - checks if $\\alpha$ is in group $G$\n",
    "    - retrieves (or creates and store) $d$ in database\n",
    "    - calculates and returns $\\beta = \\alpha^d$\n",
    "3. client(\\beta: Point) -> bytearray:\n",
    "    - checks if $\\beta$ is in group $G$\n",
    "    - calculates $\\beta^\\frac{1}{\\rho}$ and unblinds the result\n",
    "    - calculates and returns H(x || \\beta^(1/\\rho))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "H'(x):\n",
      "(9647045120380072016896367801436216089517385294113691900224368540592147852881,63780912247584663447060568763839704993950614958143814955131411688625580648907)\n",
      "0x155408b6f6f87082d9d97dbb4d9322e279709ae7e591ec2a2cd02db7e548ee51 0x8d02b7900d4d11105589f57d5c2b8a871f372b26a0c1464b884671c6dad9a9cb\n",
      "alpha = (H'(x))^rho:\n",
      "(96060363318793445308142303247957725785598212468546760216643989368154363422182,67253679145713470788686215502821137612357123005677477254415963606436937150077)\n",
      "0xd4603d2897e719a966dd41810e0d547f8e5141bb24b02792af8a4f0b401665e6 0x94b03bc36fb71a95dc6c50198870a85f7f0d52e0f0fb5ee0fdd41d09f3c72e7d\n"
     ]
    }
   ],
   "source": [
    "# 1 client:\n",
    "x = \"masterpasswordwww.google.com\"\n",
    "hdashx = map2curve_simple_swu(x.encode())\n",
    "print(\"H'(x):\")\n",
    "print(hdashx)\n",
    "print(hex(hdashx.x()), hex(hdashx.y()))\n",
    "rho = 23 # generate a random number here\n",
    "alpha = hdashx * rho # hdashx^rho\n",
    "print(\"alpha = (H'(x))^rho:\")\n",
    "print(alpha)\n",
    "print(hex(alpha.x()), hex(alpha.y()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "d =  49593046683349734658837698885206452611033450058247891428920244266019060051104\n",
      "0x6da4ab71e4602e1eb332ad0143eddb1ba07bd258ed2716a4f9271821e6a5eca0\n",
      "beta = alpha^d:\n",
      "(20902386769593356422803755726142762975644522947047497806519940156789227647566,37820471632289113646378000102094571407461625006655530832469911478145755153402)\n",
      "0x2e3654e7b2bf3d4ff2ad21cdfc9f73670a42bf5a807e799e726ebd048f91f24e 0x539da0dc00fcea9ef0d42ec0fca00aafad897c01e1ba5cf901992ac4f67883fa\n"
     ]
    }
   ],
   "source": [
    "# 2 device:\n",
    "assert (curve_256.contains_point(alpha.x(), alpha.y()) == True)\n",
    "d = HashToBase(b\"some random way to produce this d key\", 1)\n",
    "print(\"d = \", d)\n",
    "print(hex(d))\n",
    "beta = d * alpha\n",
    "print(\"beta = alpha^d:\")\n",
    "print(beta)\n",
    "print(hex(beta.x()), hex(beta.y()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "rho^-1 * rho =  1\n",
      "final = beta^(1/rho)\n",
      "(34550786935032766327755133052490331274309469427745266322787923543983364811861,49690625575606612910815333321718443879931197308857771898142620989441619363396)\n",
      "0x4c630d6a1aea8b7ff03f4c9996dd21f978f9609eb387b3bb7b73b20ce694ac55 0x6ddbe5bc2a5b6a1514a6b6b7a1340ce4debe089a530c5b5cee2ba720b6b58644\n"
     ]
    }
   ],
   "source": [
    "# 3 client:\n",
    "assert (curve_256.contains_point(beta.x(), beta.y()) == True)\n",
    "# n.b.\n",
    "print(\"rho^-1 * rho = \",pow(rho, PRIME-2, PRIME) * rho % PRIME)\n",
    "final = beta * pow(rho, ORDER-2, ORDER)\n",
    "print(\"final = beta^(1/rho)\")\n",
    "print(final)\n",
    "print(hex(final.x()), hex(final.y()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(34550786935032766327755133052490331274309469427745266322787923543983364811861,49690625575606612910815333321718443879931197308857771898142620989441619363396)\n",
      "Check that this result `check final` equals `final`:\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# check correctness\n",
    "check_final = hdashx * d\n",
    "print(check_final)\n",
    "assert (curve_256.contains_point(check_final.x(), check_final.y()) == True)\n",
    "print(\"Check that this result `check final` equals `final`:\")\n",
    "print (check_final == final)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b\"\\xec\\xf8J\\xf9\\xd7\\xe6\\xa9e\\xa5h\\x1duj\\x16\\x91''\\xd4\\xe4\\x89\\x1c\\xc9\\xef\\xfeo}\\x17\\xb7\\x10\\x8d.$\" 32\n",
      "Your facebook password is:  %*U(8#vcudIgdGoKK7#mH4^)fjGzEnMK\n"
     ]
    }
   ],
   "source": [
    "# Finally, hash this result\n",
    "# Oblivious Psuedo-Random Function\n",
    "def OPRF(x: str, point: ecc.Point) -> bytearray:\n",
    "    '''Performs the actual Hash H of H(x, (H'(X))^d), which is the hash of a\n",
    "       bytearray x and a Point on the curve. Returns a bytearray result.\n",
    "    '''\n",
    "    H = sha256()\n",
    "    H.update(x.encode())\n",
    "    H.update(I2OSP(point.x(), 256))\n",
    "    H.update(I2OSP(point.y(), 256))\n",
    "    return H.digest()\n",
    "\n",
    "rwdbytes = OPRF(x, final)\n",
    "print(rwdbytes, len(rwdbytes))\n",
    "\n",
    "# convert this to a password\n",
    "import os\n",
    "\n",
    "def gen_password(rwd: bytearray, length: int=32, charset: str=\"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()\") -> str:\n",
    "    '''Generates the password based on the result of the OPRF function\n",
    "    '''\n",
    "    len_charset = len(charset)\n",
    "    indices = [int(len_charset * (ord(chr(byte)) / 256.0)) for byte in rwd]\n",
    "    return \"\".join([charset[index] for index in indices])\n",
    "\n",
    "print(\"Your facebook password is: \", gen_password(rwdbytes))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1 Overview\n",
    "Here is all the basic functionality of the each part captured as a function. \n",
    "\n",
    "They follow the naming convension \"AToB\", where A is the current Entity (Client, Device), as shown below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALPHAS:  0x6d68db7cb3dc8e41218e21c99686a1c4b15f4b28b042c20e9cf1a5ec4269f77a 0x6caf2ff7e2661f15eabc9b92dac5c99847ee9af38eade284e2fe4dcdc41246cf\n",
      "DEVICE: I am going to store d:  39293753817579684587358563962791485292162063136866083282799165565461415876781\n",
      "FINAL:  0x7e5b03b2c70b79dbf3ebee465c1af0dacf48abb1659a26251cf90c9324da7d43 0x7ef85457e3fa4289a7b49cd37d6ca2b285fd51ad68433a70598cad63033cb52b\n",
      "CLIENT: my password is 5tce4XdQQHobplMPqhfUIwtR%RbOnlAw\n"
     ]
    }
   ],
   "source": [
    "x = \"masterpasswordwww.google.com\"\n",
    "\n",
    "# Client 1\n",
    "def clientToPoint(x: str) -> ecc.Point:\n",
    "    '''input the master password pwd and returns a point on the curve alpha\n",
    "       with the random integer that was used to blind it.\n",
    "    '''\n",
    "    hdashx = map2curve_simple_swu(x.encode())\n",
    "    rho = OS2IP(os.urandom(32))\n",
    "    return hdashx * rho # alpha = hdashx^rho\n",
    "\n",
    "# Device\n",
    "def deviceToClient(alpha: ecc.Point, index: int=1) -> ecc.Point:\n",
    "    '''input the point on the curve. If it is in the Group, we store\n",
    "       a random key D that corresponds to this point, and return the point\n",
    "       exponeniated to D.\n",
    "    '''\n",
    "    if curve_256.contains_point(alpha.x(), alpha.y()) != True:\n",
    "        return 0\n",
    "    print(\"ALPHAS: \", hex(alpha.x()), hex(alpha.y()))\n",
    "    randomBytes = os.urandom(32)\n",
    "    d = HashToBase(randomBytes, index)\n",
    "    print(\"DEVICE: I am going to store d: \", d)\n",
    "    return d * alpha # beta = alpha^d\n",
    "\n",
    "#Client 2\n",
    "def clientToPassword(beta: ecc.Point) -> str:\n",
    "    '''input the point on the curve. If it is in the Group, we compute\n",
    "       this point exponeniated to the inverse of rho, and then we use the\n",
    "       OPRF to create the byte array which generates the final password rwd\n",
    "    '''\n",
    "    if curve_256.contains_point(beta.x(), beta.y()) != True:\n",
    "        return 0\n",
    "    final = beta * pow(rho, ORDER-2, ORDER)\n",
    "    print(\"FINAL: \", hex(final.x()), hex(final.y()))\n",
    "    rwdbytes = OPRF(x, final)\n",
    "    return gen_password(rwdbytes, charset=\"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!@#$%^&*()\")\n",
    "\n",
    "# Usage\n",
    "# --------- Start Client --------- \n",
    "alpha = clientToPoint(x)\n",
    "# ---------  End Client  ---------\n",
    "\n",
    "# send alpha to Device\n",
    "\n",
    "# --------- Start Device ---------\n",
    "beta = deviceToClient(alpha)\n",
    "# ---------  End Device  ---------\n",
    "\n",
    "# send beta to Client\n",
    "\n",
    "# --------- Start Client ---------\n",
    "rwd = clientToPassword(beta)\n",
    "print(\"CLIENT: my password is\", rwd)\n",
    "# ---------  End Client  ---------"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2 Issues I ran Into during Implementation\n",
    "Here is a collection of issues I've ran into over the past week about my implementation experience, having basically no experience in cryptography and trying to play around with elliptic curves. \n",
    "- Implementing Octet String <-> Integer Primitives\n",
    "    - In order to implement HashToBase, I had to first implement these primitive functions. I looked at the papers but had trouble figuring out what I had to implement, and the implementation presented in the second paper was not very helpful in terms of how to actually implement it.\n",
    "        - it said stuff like, \"convert x to it's base 256 form such that x = x_{i-1} * 256^{i-1} + ... + x_1 * 256 + x_0\"\n",
    "    - I was wondering, Do I need to actually calculate this value, when I've read online that this is literally the byte representation of an integer (in python its called `bytearray`!)\n",
    "    - Mixed up octet with octal, and when was sad when I realised I could not use the python built-in `oct()`.\n",
    "- HashToBase\n",
    "    - I was pretty confused with the notation of the hash function and how it accepted multiple arguments\n",
    "        - found out during week 4 tutorial and from personal research that you should concatenate it, but be careful of length extension attacks\n",
    "        - many implementations of hash functions (for example, `hashlib.sha256` in python), implement the hash function in a special way:\n",
    "            - ```python\n",
    "            myHash = hashlib.sha256(). # instantiation\n",
    "            ```\n",
    "            - ```python\n",
    "            myHash.update(b'This is the byte representation of something I want to hash') # update\n",
    "            myHash.update(b' , and you can keep hash multi-part lines like this')\n",
    "            ```\n",
    "            - ```python\n",
    "            myHash.digest() # result of the hash is returned when you run digest\n",
    "            ```\n",
    "            - I.e. use the update function sequentially to add multiple parts to the hash, this is done for multiple reasons\n",
    "                - encourage good standards, so people hash multiple arguments through the `update()` function rather than concatenating the strings before applying the hash\n",
    "                - so that each call to hash runs in constant time, no need to worry about variable-length string hashing\n",
    "- Simple SWU\n",
    "    - modular arithmetic is very particular\n",
    "        - `A // B` is usually how you do integer division, however, this does not work for modular arithmetic. \n",
    "            - Use `A * pow(B, PRIME-2, PRIME)`, where `B^-1 % PRIME == pow(B, PRIME-2, PRIME)` and `PRIME mod 4 == 3 mod 4` is required.\n",
    "        - make sure the entire result is enclosed in brackets before applying `%PRIME` or else you may only be applying modulo to part of the result\n",
    "        - I was really just stuck on that first point for while, the algorithm was failing to hash 8/30 cases, and I was having a hard time figuring out why until I played around with genius, the cli calculator capable of modular arithmetic.\n",
    "- SPHINX\n",
    "    - I could not get the actual math to work, when I exponiated $\\beta$ to the inverse of $\\rho$, it was not equal to what the OPRF function dictated, when I knew that the paper said that this unblinding process should do so\n",
    "        - Make sure you know the difference between the prime number p of a Finite Integer Field Z_p, and the ORDER of Z_p. They are different numbers, It should be inverted w.r.t ORDER, not PRIME.\n",
    "\n",
    "## 3. Further Work\n",
    "This is basically most of the functionality of SPHINX completed in python. Now It will be time to prove that this concept works by implementing it into a working password store to demonstrate the power. I have a few ideas that also need to be implemented before I can go towards creating the front ends:\n",
    "\n",
    "- Have a configurable bytes to password generating system, for example, If passwords need to be a certain length or if they only contain certain characters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}