{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ElGamal\n",
    "==============="
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diffie-Hellman key distribution scheme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "IN 1975, Diffie and Hellman introduced the concept of public key cryptography.\n",
    "\n",
    "Suppose that $A$ and $B$ want to share a secret $K_{AB}$ , where A has a secret $x_A$ and $B$ has a secret $x_B$ . Let $p$ be a large prime and $\\alpha$ be a **primitive element** mod $p$, both known. computes $y \\equiv \\alpha^{x_a} \\mod p$ , and sends $y_A$ . Similarly, $B$ computes $y_B \\equiv \\alpha^{x_B} \\mod p$ and sends $y_B$ . Then the secret $K_{AB}$ is computed as:\n",
    "\n",
    "\\begin{align}\n",
    "K_{AB} &\\equiv \\alpha^{x_ax_B} \\mod p\\\\\n",
    "&\\equiv y_A^{x_B} \\mod p\\\\\n",
    "&\\equiv y_B^{x_A} \\mod p\n",
    "\\end{align}\n",
    "\n",
    "In any of the cryptographic systems based on discrete logarithms, p must be chosen such that $p - 1$ has at least one large prime factor. If $p - 1$ has only small prime factors, then computing discrete logarithms is easy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from klefki.numbers.primes import generate_prime\n",
    "from klefki.algebra.meta import field\n",
    "from klefki.algebra.utils import randfield\n",
    "from math import gcd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = generate_prime(32)\n",
    "F = field(p)\n",
    "mF = field(p-1)\n",
    "G = F(generate_prime(32))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "xa, xb = randfield(F).value, randfield(F).value\n",
    "ya, yb = G ** xa, G ** xb\n",
    "G ** (xa * xb) == ya ** xb == yb ** xa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ElGamal signature scheme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let m be a document to be signed, where $0 \\le m \\ge p - 1$. The public file still consists of the public key $y \\equiv x \\mod p$ for each user."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To sign a document, a user $A$ should be able to use the secret key $x_A$ to find a signature for $m$ in such a way that all users can verify the authenticity of the signature by using the public key $y_A$ (together with $\\alpha$ and $p$), and no one can forge a signature without knowing the secret $x_A$ ."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The signature for $m$ is the pair $(r, s), 0 \\le r, s < p - 1$, chosen such that the equation\n",
    "\n",
    "$$\n",
    "\\alpha^m \\equiv y^r r^s \\mod p\n",
    "$$\n",
    "\n",
    "is satisfied."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = randfield(F).value\n",
    "alpha = G\n",
    "x = xa\n",
    "y = ya"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The Signing Procedure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The signing procedure consists of the following three steps.\n",
    "\n",
    "1) Choose a random number $k$, uniformly between $0$ and $p - 1$, such that $gcd(k, p - 1) = 1$.\n",
    "\n",
    "2) Compute\n",
    "\n",
    "$$\n",
    "r \\equiv \\alpha^k \\mod p\\\\\n",
    "\\alpha^m \\equiv \\alpha^{xr}\\alpha^{ks} \\mod p\n",
    "$$\n",
    "\n",
    "which can be solved for $s$ by using\n",
    "\n",
    "$$\n",
    "m \\equiv xr + ks \\mod (p-1)\n",
    "$$\n",
    "\n",
    "Above Equation as a solution for $s$ if $k$ is chosen such that $gcd(k, p - 1) = 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "k = generate_prime(32)\n",
    "assert gcd(k, p-1) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from klefki.numbers import invmod\n",
    "r = (alpha ** k).value\n",
    "s = ((mF(m) - mF(r) * mF(x)) * ~mF(k)).value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert pow(alpha, m) ==  pow(alpha, (x * r + k * s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* The Verification Procedure\n",
    "\n",
    "Given $m, r$, an $s$, it is easy to verify the authenticity of the signature by computing both sides of $\\alpha^m \\equiv y^r r^s \\mod p$ and checking that they are equal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alpha ** m == y ** r * F(r) ** s"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ElGamal encryption over Cyclic Group"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from klefki.curves.secp256k1 import EllipticCurveGroupSecp256k1 as Curve\n",
    "from klefki.curves.secp256k1 import FiniteFieldSecp256k1 as F\n",
    "\n",
    "from klefki.algebra.meta import field"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Key generation\n",
    "\n",
    "The first party, Alice, generates a key pair as follows:\n",
    "\n",
    "* Generate an efficient description of a cyclic group $G$, of order $q$  with generator $g$. Let $e$ represent the unit element of $G$.\n",
    "\n",
    "* Choose an integer $x\\leftarrow Z_q$\n",
    "\n",
    "* Compute $h:=g^x$\n",
    "\n",
    "* he public key consists of the values $( G , q , g , h )$. Alice publishes this public key and retains $x$ as her private key, which must be kept secret."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = Curve.G\n",
    "sk = randfield(F)\n",
    "H = G @ sk\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Encryption"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A second party, Bob, encrypts a message $M$ to Alice under her public key $( G , q , g , h )$  as follows: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Map the message $M$ to an element $m$ of $G$ using a reversible mapping function.\n",
    "\n",
    "* Choose an integer $y$ randomly from $\\{ 1 , … , q − 1 \\}$ \n",
    "\n",
    "* Compute $s := h^y$. This is called the shared secret.\n",
    "\n",
    "* Compute $c_1 := g^y$\n",
    "\n",
    "* Compute $c_2 := m \\cdot s$\n",
    "\n",
    "Bob sends the ciphertext $( c_1 , c_2 )$ to Alice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "c=g^r, h^{mr}\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "M = F(1235)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::0xad78a3d6fd61dbf18585d0bdfc5263ead132b1dcb2fcf5d008e1f30662299c9e, FiniteFieldSecp256k1::0xc691845486a1ceebf28e1092de6b875f155b594e99036dc216207e36884167db),\n",
       " EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::0xa81a8ede02088dd0fabc535a5a58621ed70cdfdc34c5d71cec152845bffcb3d5, FiniteFieldSecp256k1::0x189dbf0231b9df69af56e5dd08fa5f7026078d9faf2480c32e5c5406de58cade))"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y = randfield(F).value\n",
    "m = Curve.lift_x(M)\n",
    "\n",
    "c1 = G @ y\n",
    "c2 = H @ y + m\n",
    "\n",
    "(c1, c2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decryption"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alice decrypts a ciphertext $c_1, c_2$ with her private key $sk$ as follows: "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Compute $s := c_1^{x}$.\n",
    "\n",
    "* Compute $s^{-1}$,  the inverse of $s$ in the group $G$.\n",
    "\n",
    "* Compute $m:=c_2\\cdot s^{-1}$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\\begin{align}\n",
    "m&=\\frac{c_2}{c_1^x}=\\frac{H^{rm}}{G^{xr}}=\\frac{G^{xrm}}{G^{xr}}\n",
    "\\end{align}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "m = (c2 - (c1 @ sk))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m.x == M"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "from klefki.curves.secp256k1 import EllipticCurveGroupSecp256k1 as Curve\n",
    "from klefki.curves.secp256k1 import FiniteFieldCyclicSecp256k1 as CF\n",
    "from klefki.curves.secp256k1 import FiniteFieldSecp256k1 as F\n",
    "from klefki.algebra.meta import field\n",
    "from klefki.blockchain.ethereum.private import decode_privkey, encode_privkey\n",
    "from klefki.crypto.ecdsa.secp256k1 import pubkey\n",
    "\n",
    "\n",
    "from klefki.utils import int_to_byte, byte_to_int\n",
    "\n",
    "key = decode_privkey(\"65860affb4b570dba06db294aa7c676f68e04a5bf2721243ad3cbc05a79c68c0\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "pubkey = G @ F(key)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "m_x = [253, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 116, 101, 115, 116]\n",
    "m_y = [102, 240, 6, 242, 139, 13, 202, 191, 92, 132, 250, 2, 205, 187, 196, 131, 154, 248, 95, 123, 242, 215, 83, 237, 38, 195, 221, 29, 137, 141, 2, 132]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "m_x = F(byte_to_int(m_x))\n",
    "m_y = F(byte_to_int(m_y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::0xfd00000000000000000000000000000000000000000000000000000074657374, FiniteFieldSecp256k1::0x66f006f28b0dcabf5c84fa02cdbbc4839af85f7bf2d753ed26c3dd1d898d0284)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m = Curve(m_x, m_y)\n",
    "m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "r = F(0x1f9275dbafdfba81942eb3330b07f38cbee4ebb86bdc2174af9648d5f5509a54)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "c1 = G @ r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "EllipticCurveGroupSecp256k1::(FiniteFieldSecp256k1::0xfca855e9dc774cd9346ca71beabcc55f48d594d46fff063b09866f79af09bd69, FiniteFieldSecp256k1::0x142d0d3df53288b7b6d2a97854cc4d8a0c74320973628af5183ddf9037b4e73b)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "ss = pubkey @ r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "98638154376543494645275106847376508464438552902924450790959126183159388906274"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ss.x.value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "c2 = ss + m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = c1 @ key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = (c2 - (c1 @ key))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d.x == m.x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ref:\n",
    "    \n",
    "   * T. ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Trans. Info. Theory, IT 31:469–472, 1985.\n",
    "    \n",
    "   * ElGamal encryption https://en.wikipedia.org/wiki/ElGamal_encryption\n",
    "    \n",
    "   * http://www.docsdrive.com/pdfs/ansinet/itj/2005/299-306.pdf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}