El-Gamal Crypto-Scheme.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# El-Gamal Encryption Scheme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Group-11 \n",
    "+ Ritu Thombre (BT17CSE084)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id='index'>Index</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ <a href='#primitive_roots'>1. Finding primitive roots of a prime</a>\n",
    "+ <a href='#key'>2. Generation of Keys</a>\n",
    "+ <a href='#encrypt'>3. Encrypting plain_text</a>\n",
    "+ <a href='#decrypt'>4. Decrypting cipher_text</a>\n",
    "+ <a href='#aux'>5. Auxiliary functions</a>\n",
    "+ <a href='#implementation'>6. Implementation</a>\n",
    "    + <a href='#6.1'>6.1 Generating Keys</a>\n",
    "    + <a href='#6.2'>6.2 Generating plain_text</a>\n",
    "    + <a href='#6.3'>6.3 Encrypting plain_text to generate cipher_text</a>\n",
    "    + <a href='#6.4'>6.4 Decrypting cipher_text to generate plain_text</a>\n",
    "    + <a href='#6.5'>6.5 Checking if decrypted plain_text is same as original plain_text</a>\n",
    "+ <a href='#final'>7. Final Remarks</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from Crypto.Util import number\n",
    "import math\n",
    "import gmpy2\n",
    "from gmpy2 import powmod,mpz,isqrt,invert\n",
    "import pyecm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id='primitive_roots'>1. Finding primitive roots of a prime</a>\n",
    "<a href='#index'>Go back to the top</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ If $ m $ is a primitive root modulo $ n $, then the multiplicative order of m is $ {\\displaystyle \\varphi (n)} $ i.e  $ a^{\\phi (n)} \\equiv 1 mod(n) $\n",
    "\n",
    "+ We can use this to test a candidate m to see if it is primitive.\n",
    "\n",
    "+ First, compute $ {\\displaystyle \\varphi (n)} $. Then determine the different prime factors of $ {\\displaystyle \\varphi (n)} $, say p1, ..., pk. \n",
    "\n",
    "+ Finally, compute $ {\\displaystyle m^{\\varphi (n)/p_{i}}{\\bmod {n}}\\qquad {\\mbox{ for }}i=1,\\ldots ,k}$ using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number m for which these k results are all different from 1 is a primitive root."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_primitive_root(prime):\n",
    "    # calculate phi(n)\n",
    "    # phi(prime) is (prime-1)\n",
    "    phi = prime-1\n",
    "    prime_factors = list(pyecm.factors(phi, False, True, 10, 1))\n",
    "    # set range for primitive root\n",
    "    # so that we don't have to calculate all the roots\n",
    "    d_range = np.random.randint(20,30)\n",
    "    possible_root = 5\n",
    "    while possible_root < prime:\n",
    "        temp = []\n",
    "        is_root = True\n",
    "        for i in range(len(prime_factors)):\n",
    "            remainder = gmpy2.powmod(possible_root,(phi//prime_factors[i]),prime)\n",
    "            # if remainder is 1, then current number we're checking is not a primitive root\n",
    "            if remainder == 1:\n",
    "                is_root = False\n",
    "                break\n",
    "        if is_root and possible_root >= d_range:\n",
    "            return possible_root\n",
    "        possible_root=possible_root+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id='key'>2. Generation of Keys</a>\n",
    "<a href='#index'>Go back to the top</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Key Generation In El-Gamal :***\n",
    "\n",
    "+ Choose a prime p using Crypto-Util\n",
    "+ Choose e1 $ \\in $ primitive_roots($ p $) \n",
    "    + Refer to <a href='#primitive_roots'>3. Finding primitive roots of a prime</a>\n",
    "+ Choose $ d \\in [2,p-2] $\n",
    "+ Choose $ e2 = e1^d mod(p) $\n",
    "    + Refer to <a href='#power_mod'>2. Modular exponentiation by squaring $ m^i mod(p) $</a>\n",
    "+ Return ***Public keys :*** $ (e1,e2,p) $\n",
    "+ Return ***Private key :*** $ (d) $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def generate_keys():\n",
    "    # prime number of 25 digits i.e 84 bits\n",
    "    n = 1000000000000000000000000\n",
    "    random_add = np.random.randint(1,1000000)\n",
    "    n = n + random_add\n",
    "    p = int(gmpy2.next_prime(n))\n",
    "    d = 0\n",
    "    for i in range(2,p-1):\n",
    "        select1 = np.random.randint(0,20)\n",
    "        select2 = np.random.randint(0,20)\n",
    "        if select1 == select2:\n",
    "            d=i\n",
    "            break\n",
    "    e1 = get_primitive_root(p)\n",
    "    e2 = gmpy2.powmod(e1,d,p)\n",
    "    return e1,e2,p,d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id='encrypt'>3. Encrypting plain_text blocks</a>\n",
    "<a href='#index'>Go back to the top</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Encyption in El-Gamal :***\n",
    "\n",
    "***Input :*** $ Plain Text = [p_1,p_2,p_3,..........,p_k] $\n",
    "\n",
    "***Output :*** $ Cipher Text = [c_1,c_2,c_3,..........,c_k] $\n",
    "\n",
    "$ c_i = (c_{i1},c_{i2}) $\n",
    "\n",
    "where\n",
    "\n",
    "$ c_{i1} = e_1^{r} mod(p) $ and $ c_{i2} = ((e_2^{r})*p_i) mod(p) $ where $ i = 1,2.....,k $\n",
    "\n",
    "***New $ r $ is used during every encryption to prevent any attacks***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def encrypt(plain_text_blocks,public_keys):\n",
    "    cipher_text_blocks = []\n",
    "    e1,e2,p = public_keys\n",
    "    r = np.random.randint(2,50)\n",
    "    print(\"\\nr:\",r)\n",
    "    for plain_text in plain_text_blocks:\n",
    "        cipher_text1 = gmpy2.powmod(e1,r,p)\n",
    "        cipher_text2 = ((gmpy2.powmod(e2,r,p))*plain_text)%p\n",
    "        cipher_text_blocks.append((cipher_text1,cipher_text2))\n",
    "    return cipher_text_blocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id='decrypt'>4. Decrypting cipher_text</a>\n",
    "<a href='#index'>Go back to the top</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Decryption in El-Gamal :***\n",
    "\n",
    "***Input :*** $ Cipher Text = [c_1,c_2,c_3,..........,c_k] $\n",
    "\n",
    "***Output :*** $ Plain Text = [p_1,p_2,p_3,..........,p_k] $\n",
    "\n",
    "$ p_{i} = ((c_{i1}^{-d})*c_{i2}) mod(p) $ where $ i = 1,2,...,k $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def decrypt(cipher_text_blocks,secret_key,public_keys):\n",
    "    e1,e2,p = public_keys\n",
    "    d = secret_key\n",
    "    decypted_plain_text_blocks = []\n",
    "    for cipher_text in cipher_text_blocks:\n",
    "        cipher_text1,cipher_text2 = cipher_text\n",
    "        cipher_text1 = gmpy2.powmod(cipher_text1,d,p)\n",
    "        cipher_text1 = gmpy2.invert(cipher_text1,p)\n",
    "        cipher_text2 = cipher_text2*cipher_text1\n",
    "        plain_text = cipher_text2 % p\n",
    "        decypted_plain_text_blocks.append(plain_text)\n",
    "    return decypted_plain_text_blocks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id='aux'>5. Auxiliary functions</a>\n",
    "<a href='#index'>Go back to the top</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ get_blocks() function converts the plain_text into blocks of plain_text by using the ***blocksize = 3***.\n",
    "    + In this case, since prime used is 20 bits long i.e 7 digits long, it can encrypt upto 7 digit number\n",
    "    + Since, each aplha-numeric character gives 2 digit plain_text, so we can use maximum of ***3 alphabets in a block***\n",
    "+ format_plain_text() takes in the alphabetical plain_text blocks and returns their corresponding numeric plain_text blocks\n",
    "+ def format_decrypted_plain_text() takes in the numeric_decrypted_plain_text blocks and return a single original plain text."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# taken in 'Hello World!!!' returns ['Hel','lo ','Wor','ld!','!!']\n",
    "def get_blocks(PT,block_size):\n",
    "    blocks = []\n",
    "    i = 0\n",
    "    while i<len(PT):\n",
    "        temp_str=''\n",
    "        if i+block_size-1 < len(PT):\n",
    "            temp_str=temp_str+PT[i:i+block_size]\n",
    "        else :\n",
    "            temp_str=temp_str+PT[i::]\n",
    "        blocks.append(temp_str)\n",
    "        i=i+block_size\n",
    "    return blocks\n",
    "        \n",
    "# covert plain_text block from characters to the numbers\n",
    "def format_plain_text(PT):\n",
    "    plain_text_blocks = []\n",
    "    for block in PT:\n",
    "        plain_text = 0\n",
    "        for i in range(len(block)):\n",
    "            # for 'd'\n",
    "            if ord(block[i]) == 100:\n",
    "                plain_text = plain_text*100 + 28\n",
    "            # between (101,127)\n",
    "            elif ord(block[i])>100:\n",
    "                plain_text = plain_text*100 + (ord(block[i])-100)\n",
    "            else :\n",
    "                plain_text = plain_text*100 + (ord(block[i]))\n",
    "        plain_text_blocks.append(plain_text)\n",
    "    return plain_text_blocks\n",
    "\n",
    "# convert numeric decypted_plain_text_blocks into a single plain text of characters\n",
    "def format_decrypted_plain_text(decypted_plain_text_blocks):\n",
    "    plain_text_blocks = []\n",
    "    for dc_pt in decypted_plain_text_blocks:\n",
    "        plain_text = ''\n",
    "        temp = dc_pt\n",
    "        # for 'd' temp = 28\n",
    "        while temp > 0:\n",
    "            if temp%100 == 28:\n",
    "                plain_text = plain_text + 'd'\n",
    "            elif (temp%100) in range(0,27):\n",
    "                plain_text = plain_text + chr((temp%100)+100)\n",
    "            else :\n",
    "                plain_text = plain_text + chr((temp%100))\n",
    "            temp = temp//100\n",
    "        plain_text = plain_text[::-1] \n",
    "        plain_text_blocks.append(plain_text)\n",
    "    final_plain_text = ''\n",
    "    for plain_text_block in plain_text_blocks:\n",
    "        final_plain_text = final_plain_text + plain_text_block\n",
    "    return final_plain_text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id='implementation'>6. Implementation</a>\n",
    "<a href='#index'>Go back to the top</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='6.1'>6.1 Generating Keys</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "e1,e2,p,d = generate_keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Public Key :\n",
      "e1 : 33\n",
      "e2 : 103441435086731682718531\n",
      "p : 1000000000000000000854211\n",
      "Secret Key :\n",
      "d : 24\n"
     ]
    }
   ],
   "source": [
    "public_keys = (e1,e2,p)\n",
    "secret_key = d\n",
    "print(\"\\nPublic Key :\")\n",
    "print('e1 :',e1)\n",
    "print('e2 :',e2)\n",
    "print('p :',p)\n",
    "print(\"Secret Key :\\nd :\",d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='6.2'>6.2 Generating plain_text</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Enter Plain Text to encrypt : Schrodinger's cat is dead and alive at the same time. This cat represents the (|psi_cat>=0.5*|psi_cat_alive> + 0.5*|psi_cat_dead>) i.e superposition of wave-functions representing cat being dead and alive at the same time.\n"
     ]
    }
   ],
   "source": [
    "PT = input(\"\\nEnter Plain Text to encrypt : \")\n",
    "\n",
    "original_plain_text = PT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Plain Text after converting to blocks [\"Schrodinger'\", 's cat is dea', 'd and alive ', 'at the same ', 'time. This c', 'at represent', 's the (|psi_', 'cat>=0.5*|ps', 'i_cat_alive>', ' + 0.5*|psi_', 'cat_dead>) i', '.e superposi', 'tion of wave', '-functions r', 'epresenting ', 'cat being de', 'ad and alive', ' at the same', ' time.']\n"
     ]
    }
   ],
   "source": [
    "block_size = 12\n",
    "PT = get_blocks(PT,block_size)\n",
    "print('\\nPlain Text after converting to blocks',PT)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Plain text blocks after formatting to numbers: [839904141128051003011439, 153299971632051532280197, 283297102832970805180132, 971632160401321597090132, 160509014632840405153299, 971632140112140115011016, 153216040132402412150595, 999716626148465342241215, 59599971695970805180162, 324332484653422412150595, 999716952801972862413205, 460132151712011412111505, 160511103211023219971801, 450217109916051110153214, 11214011501101605100332, 999716329801051003322801, 972832971028329708051801, 329716321604013215970901, 321605090146]\n"
     ]
    }
   ],
   "source": [
    "plain_text_blocks = format_plain_text(PT)\n",
    "print('\\nPlain text blocks after formatting to numbers:',plain_text_blocks)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='6.3'>6.3 Encrypting plain_text to generate cipher_text</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "r: 11\n",
      "\n",
      "Cipher Text Blocks After El-Gamal encryption : [(mpz(50542106513726817), mpz(661963134578601353476006)), (mpz(50542106513726817), mpz(333166471840262813733456)), (mpz(50542106513726817), mpz(779080389800749467598945)), (mpz(50542106513726817), mpz(634040066868952112822104)), (mpz(50542106513726817), mpz(834379670376416829510185)), (mpz(50542106513726817), mpz(537528310516560150344972)), (mpz(50542106513726817), mpz(707020192838887142375559)), (mpz(50542106513726817), mpz(756174458299967416409923)), (mpz(50542106513726817), mpz(511953963743033305967736)), (mpz(50542106513726817), mpz(501127419720146001066490)), (mpz(50542106513726817), mpz(627562860235094724667896)), (mpz(50542106513726817), mpz(855773254002290700548161)), (mpz(50542106513726817), mpz(683369455057462161575308)), (mpz(50542106513726817), mpz(926770823009990023869435)), (mpz(50542106513726817), mpz(742378575165044177097731)), (mpz(50542106513726817), mpz(61360634019597105565900)), (mpz(50542106513726817), mpz(93605898911820439865852)), (mpz(50542106513726817), mpz(461192274417235870047223)), (mpz(50542106513726817), mpz(297336396514581573232722))]\n"
     ]
    }
   ],
   "source": [
    "cipher_text_blocks = encrypt(plain_text_blocks,public_keys)\n",
    "print(\"\\nCipher Text Blocks After El-Gamal encryption :\",cipher_text_blocks)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='6.4'>6.4 Decrypting cipher_text to generate plain_text</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Plain Text blocks after decryption of Cipher Text blocks : [mpz(839904141128051003011439), mpz(153299971632051532280197), mpz(283297102832970805180132), mpz(971632160401321597090132), mpz(160509014632840405153299), mpz(971632140112140115011016), mpz(153216040132402412150595), mpz(999716626148465342241215), mpz(59599971695970805180162), mpz(324332484653422412150595), mpz(999716952801972862413205), mpz(460132151712011412111505), mpz(160511103211023219971801), mpz(450217109916051110153214), mpz(11214011501101605100332), mpz(999716329801051003322801), mpz(972832971028329708051801), mpz(329716321604013215970901), mpz(321605090146)]\n"
     ]
    }
   ],
   "source": [
    "decypted_plain_text_blocks = decrypt(cipher_text_blocks,secret_key,public_keys)\n",
    "print(\"\\nPlain Text blocks after decryption of Cipher Text blocks :\",decypted_plain_text_blocks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "After decryption Plain Text : Schrodinger's cat is dead and alive at the same time. This cat represents the (|psi_cat>=0.5*|psi_cat_alive> + 0.5*|psi_cat_dead>) i.e superposition of wave-functions representing cat being dead and alive at the same time.\n"
     ]
    }
   ],
   "source": [
    "plain_text_after_decryption = format_decrypted_plain_text(decypted_plain_text_blocks)\n",
    "print(\"\\nAfter decryption Plain Text :\",plain_text_after_decryption)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='6.5'>6.5 Checking if decrypted plain_text is same as original plain_text</a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Hurrayyy!!!\n",
      "\n",
      "Decrypted plain_text is same as original plain_text! :) \n"
     ]
    }
   ],
   "source": [
    "if (original_plain_text == plain_text_after_decryption):\n",
    "    print(\"\\nHurrayyy!!!\\n\\nDecrypted plain_text is same as original plain_text! :) \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <a id='final'>7. Final Remarks</a>\n",
    "<a href='#index'>Go back to the top</a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "+ ASCII values :\n",
    "    + ASCII values from 0-31 are not alpha-numeric characters.\n",
    "    + ASCII values from ***32-99 contain [A_Z,a,b,c] and special characters such as @,#,',\",space,etc***\n",
    "    + ASCII values from ***100-126 contain [d-z] which are 3 digit.***\n",
    "    + Since we're ***not using ASCII values from 0-31, we can convert ASCII values of [d-z] to 2-digit number, by subtracting 100 from them.***\n",
    "    + If we subtract 100 from ASCII values of 'd', which is 100, we get 00. ***dam will be 009709 which 9709***, so 'd' is lost in the processing. \n",
    "    + Unused ASCII values we have now are [27,28,29,30,31], so we assign d=28. \n",
    "+ This program uses 25 digit prime number, so it can encrypt upto maximum of 12 characters at a time i.e 24 digits\n",
    "+ So, to encrypt large plain text, ***El-Gamal was implemented as a block cipher.***"
   ]
  },
  {
   "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}