Set 5.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from lib import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 33: Implement Diffie-Hellman\n",
    "[Link](https://cryptopals.com/sets/4/challenges/33)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> For one of the most important algorithms in cryptography this exercise couldn't be a whole lot easier.  \n",
    "Set a variable \"p\" to 37 and \"g\" to 5. This algorithm is so easy I'm not even going to explain it. Just do what I do.  \n",
    "Generate \"a\", a random number mod 37. Now generate \"A\", which is \"g\" raised to the \"a\" power mode 37 --- A = (g\\*\\*a) % p.  \n",
    "Do the same for \"b\" and \"B\".  \n",
    "\"A\" and \"B\" are public keys. Generate a session key with them; set \"s\" to \"B\" raised to the \"a\" power mod 37 --- s = (B\\*\\*a) % p.  \n",
    "Do the same with A\\*\\*b, check that you come up with the same \"s\".  \n",
    "To turn \"s\" into a key, you can just hash it to create 128 bits of key material (or SHA256 it to create a key for encrypting and a key for a MAC).  \n",
    "Ok, that was fun, now repeat the exercise with bignums like in the real world. Here are parameters NIST likes:  \n",
    "**p:  \n",
    "ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024  \n",
    "e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd  \n",
    "3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec  \n",
    "6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f  \n",
    "24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361  \n",
    "c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552  \n",
    "bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff  \n",
    "fffffffffffff  \n",
    "g: 2**  \n",
    "This is very easy to do in Python or Ruby or other high-level languages that auto-promote fixnums to bignums, but it isn't \"hard\" anywhere.  \n",
    "Note that you'll need to write your own modexp (this is blackboard math, don't freak out), because you'll blow out your bignum library raising \"a\" to the 1024-bit-numberth power. You can find modexp routines on Rosetta Code for most languages."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import os\n",
    "import struct\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Given\n",
    "p = 37\n",
    "g = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DiffieHellman():\n",
    "    \"\"\"\n",
    "    Implements the Diffie-Helman key exchange. Each class is a party, which has his secret key (usually\n",
    "    referred to as lowercase a or b) shares the public key (usually referred to as uppercase A or B) and can\n",
    "    compute the shared secret key between itself and another party, given their public key, assuming that\n",
    "    they are agreeing on the same p and g.\n",
    "    \"\"\"\n",
    "\n",
    "    DEFAULT_G = 2\n",
    "    DEFAULT_P = int('ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b225'\n",
    "                    '14a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f4'\n",
    "                    '4c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc20'\n",
    "                    '07cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed5'\n",
    "                    '29077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff', 16)\n",
    "\n",
    "    def __init__(self: object, g=DEFAULT_G, p=DEFAULT_P):\n",
    "        self.g = g\n",
    "        self.p = p\n",
    "        self._secret_key = random.randint(0, p - 1)\n",
    "        self.shared_key = None\n",
    "\n",
    "    def gen_public_key(self: object) -> int:\n",
    "        return pow(self.g, self._secret_key, self.p)\n",
    "\n",
    "    def gen_shared_secret_key(self: object, other_party_public_key: int) -> int:\n",
    "        if self.shared_key is None:\n",
    "            self.shared_key = pow(other_party_public_key, self._secret_key, self.p)\n",
    "        return self.shared_key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create public and private keys for Alice and Bob."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Alice\n",
    "a = random.randint(0, 100)\n",
    "A = (g**a) % p\n",
    "\n",
    "# Bob\n",
    "b = random.randint(0, 100)\n",
    "B = (g**b) % p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Verify that the final session key comes out to be the same at Alice and Bob's end."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "session_key_Alice = (B**a) % p\n",
    "session_key_Bob = (A**b) % p\n",
    "\n",
    "assert session_key_Alice == session_key_Bob"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Verify that our DiffieHellman implementation works and two parties will agree on the same key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "client1 = DiffieHellman()\n",
    "client2 = DiffieHellman()\n",
    "\n",
    "assert client1.gen_shared_secret_key(client2.gen_public_key()) == client2.gen_shared_secret_key(client1.gen_public_key())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div style=\"border:1px solid #c3e6cb;padding:.75rem 3rem;border-radius:.5rem;font-weight:bold;text-align: center;background-color:#d4edda;color:#155724;border-color:#c3e6cb;\">Completed</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "test(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 34: Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection\n",
    "[Link](https://cryptopals.com/sets/5/challenges/34)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Use the code you just worked out to build a protocol and an \"echo\" bot. You don't actually have to do the network part of this if you don't want; just simulate that. The protocol is:  \n",
    "**A->B**  \n",
    "Send \"p\", \"g\", \"A\"  \n",
    "**B->A**  \n",
    "Send \"B\"  \n",
    "**A->B**  \n",
    "Send AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv  \n",
    "**B->A**  \n",
    "Send AES-CBC(SHA1(s)[0:16], iv=random(16), A's msg) + iv  \n",
    "(In other words, derive an AES key from DH with SHA1, use it in both directions, and do CBC with random IVs appended or prepended to the message).  \n",
    "Now implement the following MITM attack:  \n",
    "**A->M**  \n",
    "Send \"p\", \"g\", \"A\"  \n",
    "**M->B**   \n",
    "Send \"p\", \"g\", \"p\"  \n",
    "**B->M**   \n",
    "Send \"B\"\n",
    "**M->A**   \n",
    "Send \"p\"\n",
    "**A->M**   \n",
    "Send AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv  \n",
    "**M->B**   \n",
    "Relay that to B\n",
    "**B->M**   \n",
    "Send AES-CBC(SHA1(s)[0:16], iv=random(16), A's msg) + iv  \n",
    "**M->A**   \n",
    "Relay that to A  \n",
    "M should be able to decrypt the messages. \"A\" and \"B\" in the protocol --- the public keys, over the wire --- have been swapped out with \"p\". Do the DH math on this quickly to see what that does to the predictability of the key.  \n",
    "Decrypt the messages from M's vantage point as they go by.  \n",
    "Note that you don't actually have to inject bogus parameters to make this attack work; you could just generate Ma, MA, Mb, and MB as valid DH parameters to do a generic MITM attack. But do the parameter injection attack; it's going to come up again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import os\n",
    "import random\n",
    "import hashlib\n",
    "from Crypto.Cipher import AES"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Given\n",
    "p = 37\n",
    "g = 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parameter_injection_attack(alice: object, bob: object):\n",
    "    block_size = AES.block_size\n",
    "    # A -> M\n",
    "    A = alice.gen_public_key()\n",
    "    # M -> B\n",
    "    A = alice.p\n",
    "    # B -> M\n",
    "    B = bob.gen_public_key()\n",
    "    # M -> A\n",
    "    B = bob.p\n",
    "    \n",
    "    # A -> M\n",
    "    msg = b\"Hello there!\"\n",
    "    s_a = hashlib.sha1(str(alice.gen_shared_secret_key(B)).encode()).digest()[:AES.block_size]\n",
    "    iv = os.urandom(16)\n",
    "    cipher_a = AES_CBC_encrypt(msg, iv, s_a) + iv\n",
    "    \n",
    "    # M -> B\n",
    "    \n",
    "    # B -> M\n",
    "    s_b = hashlib.sha1(str(bob.gen_shared_secret_key(A)).encode()).digest()[:16]\n",
    "    a_iv = cipher_a[-AES.block_size:]\n",
    "    a_msg = AES_CBC_decrypt(cipher_a[:-AES.block_size], iv, s_b)\n",
    "    print(\"A sent:\", PKCS7_unpad(a_msg))\n",
    "    iv = os.urandom(16)\n",
    "    cipher_b = AES_CBC_encrypt(a_msg, iv, s_b) + iv\n",
    "    \n",
    "    # M -> A\n",
    "    \n",
    "    # Finding the key after replacing A and B with p is, in fact, very easy.\n",
    "    # Instead of (B^a % p) or (A^b % p), the shared secret key of the exercise became (p^a % p)\n",
    "    # and (p^b % p), both equal to zero!\n",
    "    mitm_key = hashlib.sha1(b'0').digest()[:AES.block_size]\n",
    "    \n",
    "    mitm_iv_a = cipher_a[-block_size:]\n",
    "    mitm_msg_a_read = AES_CBC_decrypt(cipher_a[:-block_size], mitm_iv_a, mitm_key)\n",
    "    print(\"MITM MSG A:\", PKCS7_unpad(mitm_msg_a_read))\n",
    "    \n",
    "    mitm_iv_b = cipher_b[-block_size:]\n",
    "    mitm_msg_b_read = AES_CBC_decrypt(cipher_b[:-block_size], mitm_iv_b, mitm_key)\n",
    "    print(\"MITM MSG B:\", PKCS7_unpad(mitm_msg_b_read))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A sent: b'Hello there!'\n",
      "MITM MSG A: b'Hello there!'\n",
      "MITM MSG B: b'Hello there!'\n"
     ]
    }
   ],
   "source": [
    "alice = DiffieHellman(g, p)\n",
    "bob = DiffieHellman(g, p)\n",
    "\n",
    "parameter_injection_attack(alice, bob)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div style=\"border:1px solid #c3e6cb;padding:.75rem 3rem;border-radius:.5rem;font-weight:bold;text-align: center;background-color:#d4edda;color:#155724;border-color:#c3e6cb;\">Completed</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "test(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 35: Implement DH with negotiated groups, and break with malicious \"g\" parameters\n",
    "[Link](https://cryptopals.com/sets/5/challenges/35)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> **A->B**  \n",
    "Send \"p\", \"g\"  \n",
    "**B->A**  \n",
    "Send ACK  \n",
    "**A->B**  \n",
    "Send \"A\"  \n",
    "**B->A**  \n",
    "Send \"B\"  \n",
    "**A->B**  \n",
    "Send AES-CBC(SHA1(s)[0:16], iv=random(16), msg) + iv  \n",
    "**B->A**\n",
    "Send AES-CBC(SHA1(s)[0:16], iv=random(16), A's msg) + iv  \n",
    "Do the MITM attack again, but play with \"g\". What happens with:  \n",
    "**g = 1  \n",
    "g = p  \n",
    "g = p - 1**  \n",
    "Write attacks for each."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import os\n",
    "import hashlib\n",
    "from Crypto.Cipher import AES"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "def malicious_g_attack():\n",
    "    \"\"\"\n",
    "    Simulates the break of Diffie-Hellman with negotiated groups by using malicious 'g' parameters.\n",
    "    \"\"\"\n",
    "    \n",
    "    p = DiffieHellman.DEFAULT_P\n",
    "    return_vals = []\n",
    "\n",
    "    # This loops over the values proposed for \"g\" by the question.\n",
    "    for g in [1, p, p - 1]:\n",
    "\n",
    "        # Step 1: the MITM changes the default g sent by Alice to Bob with a forced value.\n",
    "        alice = DiffieHellman()\n",
    "        bob = DiffieHellman(g=g)\n",
    "\n",
    "        # Step 2: Bob receives this forced g and sends an ACK to Alice.\n",
    "\n",
    "        # Step 3: Alice computes A and sends it to the MITM (thinking of Bob).\n",
    "        A = alice.gen_public_key()\n",
    "\n",
    "        # Step 4: Bob computes B and sends it to the MITM (thinking of Alice).\n",
    "        B = bob.gen_public_key()\n",
    "\n",
    "        # Step 5: Alice sends her encrypted message to Bob (without knowledge of MITM).\n",
    "        _msg = b\"Hello, how are you?\"\n",
    "        _a_key = hashlib.sha1(str(alice.gen_shared_secret_key(B)).encode()).digest()[:16]\n",
    "        _a_iv = os.urandom(AES.block_size)\n",
    "        a_question = AES_CBC_encrypt(_msg, _a_iv, _a_key) + _a_iv\n",
    "\n",
    "        # Step 6: Bob receives the message sent by Alice (without knowing of the attack)\n",
    "        # However, this time Bob will not be able to decrypt it, because (if I understood the\n",
    "        # challenge task correctly) Alice and Bob now use different values of g.\n",
    "\n",
    "        # Step 7: the MITM decrypts the Alice's question.\n",
    "        mitm_a_iv = a_question[-AES.block_size:]\n",
    "\n",
    "        # When g is 1, the secret key is also 1.\n",
    "        if g == 1:\n",
    "            mitm_hacked_key = hashlib.sha1(b'1').digest()[:16]\n",
    "            mitm_hacked_message = AES_CBC_decrypt(a_question[:-AES.block_size], mitm_a_iv, mitm_hacked_key)\n",
    "\n",
    "        # When g is equal to p, it works the same as in the S5C34 attack (the secret key is 0).\n",
    "        elif g == p:\n",
    "            mitm_hacked_key = hashlib.sha1(b'0').digest()[:16]\n",
    "            mitm_hacked_message = AES_CBC_decrypt(a_question[:-AES.block_size], mitm_a_iv, mitm_hacked_key)\n",
    "\n",
    "        # When g is equal to p - 1, the secret key is (-1)^(ab), which is either (+1 % p) or (-1 % p).\n",
    "        # We can try both and later check the padding to see which one is correct.\n",
    "        else:\n",
    "\n",
    "            for candidate in [str(1).encode(), str(p - 1).encode()]:\n",
    "                mitm_hacked_key = hashlib.sha1(candidate).digest()[:16]\n",
    "                mitm_hacked_message = AES_CBC_decrypt(a_question[:-AES.block_size], mitm_a_iv, mitm_hacked_key)\n",
    "                if PKCS7_padded(mitm_hacked_message):\n",
    "                    mitm_hacked_message = PKCS7_unpad(mitm_hacked_message)\n",
    "                    break\n",
    "        print(mitm_hacked_message)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b'\\xc2\\x90\\xc2\\xb4\\x07\\xc2\\x84]\\xc3\\x9fN\\xc3\\x9cx&\\xc2\\x89\\xc2\\x8b\\xc3\\x8d\\xc2\\xbb\\xc2\\x84\\xc3\\xab@\\xc2\\x80\\xc3\\xa2\\xc3\\xaf@\\xc3\\xb8]\\xc3\\x8c\\xc2\\xa6\\x04w\\xc3\\x8a\\xc2\\x98+\\x08\\xc2\\xa6'\n",
      "b'Hello, how are you?\\r\\r\\r\\r\\r\\r\\r\\r\\r\\r\\r\\r\\r'\n"
     ]
    }
   ],
   "source": [
    "malicious_g_attack()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div style=\"border:1px solid #c3e6cb;padding:.75rem 3rem;border-radius:.5rem;font-weight:bold;text-align: center;background-color:#d4edda;color:#155724;border-color:#c3e6cb;\">Completed</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "test(True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 36: Implement Secure Remote Password (SRP)\n",
    "[Link](https://cryptopals.com/sets/5/challenges/36)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> To understand SRP, look at how you generate an AES key from DH; now, just observe you can do the \"opposite\" operation an generate a numeric parameter from a hash. Then:  \n",
    "Replace A and B with C and S (client & server)  \n",
    "**C & S**  \n",
    "Agree on N=[NIST Prime], g=2, k=3, I (email), P (password)  \n",
    "**S**  \n",
    "Generate salt as random integer  \n",
    "Generate string xH=SHA256(salt|password)  \n",
    "Convert xH to integer x somehow (put 0x on hexdigest)  \n",
    "Generate v=g\\*\\*x % N  \n",
    "Save everything but x, xH  \n",
    "**C->S**  \n",
    "Send I, A=g\\*\\*a % N (a la Diffie Hellman)  \n",
    "**S->C**  \n",
    "Send salt, B=kv + g\\*\\*b % N  \n",
    "**S, C**  \n",
    "Compute string uH = SHA256(A|B), u = integer of uH  \n",
    "**C**  \n",
    "Generate string xH=SHA256(salt|password)  \n",
    "Convert xH to integer x somehow (put 0x on hexdigest)  \n",
    "Generate S = (B - k * g\\*\\*x)\\*\\*(a + u * x) % N  \n",
    "Generate K = SHA256(S)  \n",
    "**S**  \n",
    "Generate S = (A * v\\*\\*u) \\*\\* b % N  \n",
    "Generate K = SHA256(S)  \n",
    "**C->S**  \n",
    "Send HMAC-SHA256(K, salt)  \n",
    "**S->C**  \n",
    "Send \"OK\" if HMAC-SHA256(K, salt) validates  \n",
    "You're going to want to do this at a REPL of some sort; it may take a couple tries.  \n",
    "It doesn't matter how you go from integer to string or string to integer (where things are going in or out of SHA256) as long as you do it consistently. I tested by using the ASCII decimal representation of integers as input to SHA256, and by converting the hexdigest to an integer when processing its output.  \n",
    "This is basically Diffie Hellman with a tweak of mixing the password into the public keys. The server also takes an extra step to avoid storing an easily crackable password-equivalent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import os\n",
    "import web\n",
    "import json\n",
    "import time\n",
    "import random\n",
    "import hashlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Client and server agree on these values beforehand\n",
    "\n",
    "# Generated using \"openssl dhparam -text 1024\".\n",
    "N = int(\"008c5f8a80af99a7db03599f8dae8fb2f75b52501ef54a827b8a1a586f14dfb20d6b5e2ff878b9ad6bca0bb9\"\n",
    "        \"18d30431fca1770760aa48be455cf5b949f3b86aa85a2573769e6c598f8d902cc1a0971a92e55b6e04c4d07e\"\n",
    "        \"01ac1fa9bdefd1f04f95f197b000486c43917568ff58fafbffe12bde0c7e8f019fa1cb2b8e1bcb1f33\", 16)\n",
    "g = 2\n",
    "k = 3\n",
    "I = \"hextersik@hexterisk.com\"\n",
    "P = \"hexterisk\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Web server."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "urls = (\n",
    "    '/hello', 'Hello',\n",
    "    '/init', 'Initiate',\n",
    "    '/verify', 'Verify'\n",
    ")\n",
    "\n",
    "app = web.application(urls, globals())\n",
    "\n",
    "K = None\n",
    "salt = str(random.randint(0, 2**32 - 1))\n",
    "# since we can't save x, xH\n",
    "v = pow(g, int(hashlib.sha256(salt.encode()+P.encode()).hexdigest(), 16), N)\n",
    "\n",
    "class Hello:        \n",
    "    \n",
    "    def GET(self):\n",
    "        params = web.input()\n",
    "        name = params.name\n",
    "        if not name:\n",
    "            name = 'World'\n",
    "            \n",
    "        string = \"Hello, \" + name + \"!\"\n",
    "        return {\"name\" : string}\n",
    "    \n",
    "class Verify:\n",
    "\n",
    "    def GET(self):\n",
    "        \n",
    "        global K, salt\n",
    "        \n",
    "        params = web.input()\n",
    "        hmac_received = params.hmac\n",
    "        \n",
    "        HMAC_obj = HMAC(K, hashlib.sha256)\n",
    "        hmac = HMAC_obj.compute(salt.encode())\n",
    "        \n",
    "        if hmac == hmac_received:\n",
    "            return \"OK\"\n",
    "\n",
    "class Initiate:\n",
    "    \n",
    "    def GET(self):\n",
    "        \n",
    "        global K, salt\n",
    "        \n",
    "        params = web.input()\n",
    "        I = params.I\n",
    "        A = int(params.A)\n",
    "        \n",
    "        b = random.randint(0, N - 1)\n",
    "        B = k*v + pow(g, b, N)\n",
    "        \n",
    "        uH = hashlib.sha256(str(A).encode()+str(B).encode()).hexdigest()\n",
    "        u = int(uH, 16)\n",
    "        S = pow(A * pow(v, u, N), b, N)\n",
    "        K = hashlib.sha256(str(S).encode()).digest()\n",
    "        \n",
    "        return {\"salt\":salt, \"B\":B}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test the web server."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b\"{'name': 'Hello, World!'}\"\n",
      "{'name': 'Hello, hexterisk!'}\n"
     ]
    }
   ],
   "source": [
    "response1 = app.request(\"/hello?name=\")\n",
    "print(response1.data)\n",
    "\n",
    "response2 = app.request(\"/hello?name=hexterisk\")\n",
    "print(json.loads(response2.data.decode(\"utf-8\").replace(\"'\",'\"')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "def implement_SRP() -> bool:\n",
    "    \"\"\"\n",
    "    Implements SRP(Secure Remote Password).\n",
    "    \"\"\"\n",
    "    \n",
    "    a = random.randint(0, N - 1)\n",
    "    A = pow(g, a, N)\n",
    "    \n",
    "    response = app.request(\"/init?I=\" + I + \"&A=\" + str(A))\n",
    "    response_dict = json.loads(response.data.decode(\"utf-8\").replace(\"'\",'\"'))\n",
    "    salt = response_dict[\"salt\"]\n",
    "    B = int(response_dict[\"B\"])\n",
    "\n",
    "    uH = hashlib.sha256(str(A).encode()+str(B).encode()).hexdigest()\n",
    "    u = int(uH, 16)\n",
    "    \n",
    "    xH = hashlib.sha256(salt.encode()+P.encode()).hexdigest()\n",
    "    x = int(xH, 16)\n",
    "    \n",
    "    S = pow((B - k * pow(g, x, N)), (a + u * x), N)\n",
    "    K = hashlib.sha256(str(S).encode()).digest()\n",
    "\n",
    "    HMAC_obj = HMAC(K, hashlib.sha256)\n",
    "    hmac = HMAC_obj.compute(salt.encode())\n",
    "    \n",
    "    response = app.request(\"/verify?hmac=\" + hmac)\n",
    "    assert response.data.decode(\"utf-8\") == \"OK\"\n",
    "    print(\"> Verification successful.\")\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> Verification successful.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div style=\"border:1px solid #c3e6cb;padding:.75rem 3rem;border-radius:.5rem;font-weight:bold;text-align: center;background-color:#d4edda;color:#155724;border-color:#c3e6cb;\">Completed</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "test(implement_SRP())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 37: Break SRP with a zero key\n",
    "[Link](https://cryptopals.com/sets/5/challenges/37)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Get your SRP working in an actual client-server setting. \"Log in\" with a valid password using the protocol.  \n",
    "Now log in without your password by having the client send 0 as its \"A\" value. What does this to the \"S\" value that both sides compute?  \n",
    "Now log in without your password by having the client send N, N*2, &c."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import os\n",
    "import web\n",
    "import json\n",
    "import time\n",
    "import random\n",
    "import hashlib"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Web server."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "urls = (\n",
    "    '/hello', 'Hello',\n",
    "    '/init', 'Initiate',\n",
    "    '/verify', 'Verify'\n",
    ")\n",
    "\n",
    "app = web.application(urls, globals())\n",
    "\n",
    "K = None\n",
    "salt = str(random.randint(0, 2**32 - 1))\n",
    "# since we can't save x, xH\n",
    "v = pow(g, int(hashlib.sha256(salt.encode()+P.encode()).hexdigest(), 16), N)\n",
    "\n",
    "class Hello:        \n",
    "    \n",
    "    def GET(self):\n",
    "        params = web.input()\n",
    "        name = params.name\n",
    "        if not name:\n",
    "            name = 'World'\n",
    "            \n",
    "        string = \"Hello, \" + name + \"!\"\n",
    "        return {\"name\" : string}\n",
    "    \n",
    "class Verify:\n",
    "\n",
    "    def GET(self):\n",
    "        \n",
    "        global K, salt\n",
    "        \n",
    "        params = web.input()\n",
    "        hmac_received = params.hmac\n",
    "        \n",
    "        HMAC_obj = HMAC(K, hashlib.sha256)\n",
    "        hmac = HMAC_obj.compute(salt.encode())\n",
    "        \n",
    "        if hmac == hmac_received:\n",
    "            return \"OK\"\n",
    "\n",
    "class Initiate:\n",
    "    \n",
    "    def GET(self):\n",
    "        \n",
    "        global K, salt\n",
    "        \n",
    "        params = web.input()\n",
    "        I = params.I\n",
    "        A = int(params.A)\n",
    "        \n",
    "        b = random.randint(0, N - 1)\n",
    "        B = k*v + pow(g, b, N)\n",
    "        \n",
    "        uH = hashlib.sha256(str(A).encode()+str(B).encode()).hexdigest()\n",
    "        u = int(uH, 16)\n",
    "        # S will be zero since modulo N will be zero for 0 and multiples of N\n",
    "        S = pow(A * pow(v, u, N), b, N)\n",
    "        K = hashlib.sha256(str(S).encode()).digest()\n",
    "        \n",
    "        return {\"salt\":salt, \"B\":B}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test the web server."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b\"{'name': 'Hello, World!'}\"\n",
      "{'name': 'Hello, hexterisk!'}\n"
     ]
    }
   ],
   "source": [
    "response1 = app.request(\"/hello?name=\")\n",
    "print(response1.data)\n",
    "\n",
    "response2 = app.request(\"/hello?name=hexterisk\")\n",
    "print(json.loads(response2.data.decode(\"utf-8\").replace(\"'\",'\"')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "metadata": {},
   "outputs": [],
   "source": [
    "def implement_SRP_zero() -> bool:\n",
    "    \"\"\"\n",
    "    Implement SRP(Secure Remote Password) for proposed \"A\" values.\n",
    "    \"\"\"\n",
    "    \n",
    "    # This loop goes over proposed values for \"A\" by the question.\n",
    "    for A in [0, N, N*2]:\n",
    "        a = random.randint(0, N - 1)\n",
    "\n",
    "        response = app.request(\"/init?I=\" + I + \"&A=\" + str(A))\n",
    "        response_dict = json.loads(response.data.decode(\"utf-8\").replace(\"'\",'\"'))\n",
    "        salt = response_dict[\"salt\"]\n",
    "        B = int(response_dict[\"B\"])\n",
    "\n",
    "        uH = hashlib.sha256(str(A).encode()+str(B).encode()).hexdigest()\n",
    "        u = int(uH, 16)\n",
    "\n",
    "        xH = hashlib.sha256(salt.encode()+P.encode()).hexdigest()\n",
    "        x = int(xH, 16)\n",
    "\n",
    "        # S = modular_pow((B - k * modular_pow(g, x, N)), (a + u * x), N)\n",
    "        # We put S=0 because we know it's going to be zero on the server side\n",
    "        S = 0\n",
    "        K = hashlib.sha256(str(S).encode()).digest()\n",
    "\n",
    "        HMAC_obj = HMAC(K, hashlib.sha256)\n",
    "        hmac = HMAC_obj.compute(salt.encode())\n",
    "\n",
    "        response = app.request(\"/verify?hmac=\" + hmac)\n",
    "        assert response.data.decode(\"utf-8\") == \"OK\"\n",
    "        print(\"> Verification successful.\")\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> Verification successful.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div style=\"border:1px solid #c3e6cb;padding:.75rem 3rem;border-radius:.5rem;font-weight:bold;text-align: center;background-color:#d4edda;color:#155724;border-color:#c3e6cb;\">Completed</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "test(implement_SRP_zero())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 38: Offline dictionary attack on simplified SRP\n",
    "[Link](https://cryptopals.com/sets/5/challenges/38)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> S\n",
    "**x = SHA256(salt|password)  \n",
    "    v = g\\*\\*x % n  \n",
    "C->S  \n",
    "**I, A = g\\*\\*a % n**  \n",
    "S->C  \n",
    "**salt, B = g\\*\\*b % n, u = 128 bit random number**  \n",
    "C  \n",
    "**x = SHA256(salt|password)  \n",
    "    S = B\\*\\*(a + ux) % n  \n",
    "    K = SHA256(S)**  \n",
    "S  \n",
    "**S = (A * v ** u)**b % n  \n",
    "    K = SHA256(S)**  \n",
    "C->S  \n",
    "Send HMAC-SHA256(K, salt)  \n",
    "S->C  \n",
    "Send \"OK\" if HMAC-SHA256(K, salt) validates  \n",
    "Note that in this protocol, the server's \"B\" parameter doesn't depend on the password (it's just a Diffie Hellman public key).  \n",
    "Make sure the protocol works given a valid password.  \n",
    "Now, run the protocol as a MITM attacker: pose as the server and use arbitrary values for b, B, u, and salt.  \n",
    "Crack the password from A's HMAC-SHA256(K, salt)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import os\n",
    "import web\n",
    "import json\n",
    "import time\n",
    "import random\n",
    "import hashlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Client and server agree on these values beforehand\n",
    "\n",
    "# Generated using \"openssl dhparam -text 1024\".\n",
    "N = int(\"008c5f8a80af99a7db03599f8dae8fb2f75b52501ef54a827b8a1a586f14dfb20d6b5e2ff878b9ad6bca0bb9\"\n",
    "        \"18d30431fca1770760aa48be455cf5b949f3b86aa85a2573769e6c598f8d902cc1a0971a92e55b6e04c4d07e\"\n",
    "        \"01ac1fa9bdefd1f04f95f197b000486c43917568ff58fafbffe12bde0c7e8f019fa1cb2b8e1bcb1f33\", 16)\n",
    "g = 2\n",
    "k = 3\n",
    "I = \"hextersik@hexterisk.com\"\n",
    "P = \"BackupU$r\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Web server."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "urls = (\n",
    "    '/hello', 'Hello',\n",
    "    '/init', 'Initiate',\n",
    "    '/verify', 'Verify'\n",
    ")\n",
    "\n",
    "app = web.application(urls, globals())\n",
    "\n",
    "K = None\n",
    "salt = str(random.randint(0, 2**32 - 1))\n",
    "# since we can't save x, xH\n",
    "v = pow(g, int(hashlib.sha256(salt.encode()+P.encode()).hexdigest(), 16), N)\n",
    "\n",
    "class Hello:        \n",
    "    \n",
    "    def GET(self):\n",
    "        params = web.input()\n",
    "        name = params.name\n",
    "        if not name:\n",
    "            name = 'World'\n",
    "            \n",
    "        string = \"Hello, \" + name + \"!\"\n",
    "        return {\"name\" : string}\n",
    "    \n",
    "class Verify:\n",
    "\n",
    "    def GET(self):\n",
    "        \n",
    "        global K, salt\n",
    "        \n",
    "        params = web.input()\n",
    "        hmac_received = params.hmac\n",
    "        \n",
    "        HMAC_obj = HMAC(K, hashlib.sha256)\n",
    "        hmac = HMAC_obj.compute(salt.encode())\n",
    "        \n",
    "        if hmac == hmac_received:\n",
    "            return \"OK\"\n",
    "\n",
    "class Initiate:\n",
    "    \n",
    "    def GET(self):\n",
    "        \n",
    "        global K, salt\n",
    "        \n",
    "        params = web.input()\n",
    "        I = params.I\n",
    "        A = int(params.A)\n",
    "        \n",
    "        b = random.randint(0, N - 1)\n",
    "        B = pow(g, b, N)\n",
    "        \n",
    "        u = random.getrandbits(128)\n",
    "        S = pow(A * pow(v, u, N), b, N)\n",
    "        K = hashlib.sha256(str(S).encode()).digest()\n",
    "        \n",
    "        return {\"salt\":salt, \"B\":B, \"u\":u}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test the web server."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "b\"{'name': 'Hello, World!'}\"\n",
      "{'name': 'Hello, hexterisk!'}\n"
     ]
    }
   ],
   "source": [
    "response1 = app.request(\"/hello?name=\")\n",
    "print(response1.data)\n",
    "\n",
    "response2 = app.request(\"/hello?name=hexterisk\")\n",
    "print(json.loads(response2.data.decode(\"utf-8\").replace(\"'\",'\"')))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "def MITM_SRP() -> bool:\n",
    "    \"\"\"\n",
    "    Implements simplified SRP and performs MITM.\n",
    "    Performs an offline dictionary attack on it.\n",
    "    \"\"\"\n",
    "    a = random.randint(0, N - 1)\n",
    "    A = pow(g, a, N)\n",
    "    \n",
    "    response = app.request(\"/init?I=\" + I + \"&A=\" + str(A))\n",
    "    response_dict = json.loads(response.data.decode(\"utf-8\").replace(\"'\",'\"'))\n",
    "    salt = response_dict[\"salt\"]\n",
    "    B = int(response_dict[\"B\"])\n",
    "    u = int(response_dict[\"u\"])\n",
    "    \n",
    "    # Uses a dictionary.\n",
    "    data = open('dictionary.txt', 'r').read()\n",
    "    passwords = data.split('\\n')\n",
    "    \n",
    "    for password in passwords:\n",
    "        xH = hashlib.sha256(salt.encode()+password.encode()).hexdigest()\n",
    "        x = int(xH, 16)\n",
    "\n",
    "        S = pow(B, (a + u * x), N)\n",
    "        K = hashlib.sha256(str(S).encode()).digest()\n",
    "\n",
    "        HMAC_obj = HMAC(K, hashlib.sha256)\n",
    "        hmac = HMAC_obj.compute(salt.encode())\n",
    "\n",
    "        response = app.request(\"/verify?hmac=\" + hmac)\n",
    "        \n",
    "        if response.data.decode(\"utf-8\") == \"OK\":\n",
    "            print(\"> Brute force successful.\")\n",
    "            print(\"> Password found to be:\", P)\n",
    "            return True\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> Brute force successful.\n",
      "> Password found to be: BackupU$r\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div style=\"border:1px solid #c3e6cb;padding:.75rem 3rem;border-radius:.5rem;font-weight:bold;text-align: center;background-color:#d4edda;color:#155724;border-color:#c3e6cb;\">Completed</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "test(MITM_SRP())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 39: Implement RSA\n",
    "[Link](https://cryptopals.com/sets/5/challenges/39)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> There are two annoying things about implementing RSA. Both of them involve key generation; the actual encryption/decryption in RSA is trivial.  \n",
    "First, you need to generate random primes. You can't just agree on a prime ahead of time, like you do in DH. You can write this algorithm yourself, but I just cheat and use OpenSSL's BN library to do the work.  \n",
    "The second is that you need an \"invmod\" operation (the multiplicative inverse), which is not an operation that is wired into your language. The algorithm is just a couple lines, but I always lose an hour getting it to work.  \n",
    "I recommend you not bother with primegen, but do take the time to get your own EGCD and invmod algorithm working.  \n",
    "Now:  \n",
    "* Generate 2 random primes. We'll use small numbers to start, so you can just pick them out of a prime table. Call them \"p\" and \"q\".\n",
    "* Let n be p * q. Your RSA math is modulo n.\n",
    "* Let et be (p-1)*(q-1) (the \"totient\"). You need this value only for keygen.\n",
    "* Let e be 3.\n",
    "* Compute d = invmod(e, et). invmod(17, 3120) is 2753.\n",
    "* Your public key is [e, n]. Your private key is [d, n].\n",
    "* To encrypt: c = m**e%n. To decrypt: m = c**d%n\n",
    "* Test this out with a number, like \"42\".\n",
    "* Repeat with bignum primes (keep e=3).  \n",
    "\n",
    "> Finally, to encrypt a string, do something cheesy, like convert the string to hex and put \"0x\" on the front of it to turn it into a number. The math cares not how stupidly you feed it strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import math\n",
    "import random\n",
    "from Crypto.Util.number import getPrime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mod_inverse(a: int, n: int) -> int: \n",
    "    \"\"\"\n",
    "    Computes the multiplicative inverse of a modulo n using the extended Euclidean algorithm.\n",
    "    \"\"\"\n",
    "    \n",
    "    t, r = 0, n\n",
    "    new_t, new_r = 1, a\n",
    "\n",
    "    while new_r != 0:\n",
    "        quotient = r // new_r\n",
    "        t, new_t = new_t, t - quotient * new_t\n",
    "        r, new_r = new_r, r - quotient * new_r\n",
    "\n",
    "    if r > 1:\n",
    "        raise Exception(\"a is not invertible\")\n",
    "    if t < 0:\n",
    "        t = t + n\n",
    "\n",
    "    return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RSA:\n",
    "    \"\"\"\n",
    "    Implementation of the RSA (Rivest–Shamir–Adleman) algorithm.\n",
    "    \"\"\"\n",
    "    \n",
    "    def __init__(self: object, keysize: int):\n",
    "        e = 3\n",
    "        et = 0\n",
    "        n = 0\n",
    "\n",
    "        while math.gcd(e, et) != 1:\n",
    "            p, q = getPrime(keysize // 2), getPrime(keysize // 2)\n",
    "            et = ((p - 1) * (q - 1)) // math.gcd(p - 1, q - 1)\n",
    "            n = p * q\n",
    "\n",
    "        d = mod_inverse(e, et)\n",
    "        \n",
    "        self.pub = (e, n)\n",
    "        self.pvt = (d, n)\n",
    "\n",
    "    def encrypt(self: object, message: bytes, byteorder=\"big\") -> int:\n",
    "        (e, n) = self.pub\n",
    "        data = int.from_bytes(message, byteorder)\n",
    "        \n",
    "        if data < 0 or data >= n:\n",
    "            raise ValueError(str(data) + ' out of range')\n",
    "            \n",
    "        return pow(data, e, n)\n",
    "    \n",
    "    def encryptnum(self: object, m: int) -> int:\n",
    "        (e, n) = self.pub\n",
    "        if m < 0 or m >= n:\n",
    "            raise ValueError(str(m) + ' out of range')\n",
    "        return pow(m, e, n)\n",
    "    \n",
    "    def decrypt(self: object, ciphertext: bytes, byteorder=\"big\") -> bytes:\n",
    "        (d, n) = self.pvt\n",
    "        \n",
    "        if ciphertext < 0 or ciphertext >= n:\n",
    "            raise ValueError(str(ciphertext) + ' out of range')\n",
    "        \n",
    "        numeric_plain = pow(ciphertext, d, n)\n",
    "        return numeric_plain.to_bytes((numeric_plain.bit_length() + 7) // 8, byteorder)\n",
    "    \n",
    "    def decryptnum(self: object, m: int) -> int:\n",
    "        (d, n) = self.pvt\n",
    "        if m < 0 or m >= n:\n",
    "            raise ValueError(str(m) + ' out of range')\n",
    "        return pow(m, d, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div style=\"border:1px solid #c3e6cb;padding:.75rem 3rem;border-radius:.5rem;font-weight:bold;text-align: center;background-color:#d4edda;color:#155724;border-color:#c3e6cb;\">Completed</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "rsa = RSA(1024)\n",
    "message = \"Testing 1..2..3...\"\n",
    "ciphertext = rsa.encrypt(message.encode())\n",
    "test(rsa.decrypt(ciphertext).decode(\"utf-8\") == message)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Challenge 40: Implement an E=3 RSA Broadcast attack\n",
    "[Link](https://cryptopals.com/sets/5/challenges/40)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Assume you're a Javascript programmer. That is, you're using a naive handrolled RSA to encrypt without padding.  \n",
    "Assume you can be coerced into encrypting the same plaintext three times, under three different public keys. You can; it's happened.  \n",
    "Then an attacker can trivially decrypt your message, by:  \n",
    "Capturing any 3 of the ciphertexts and their corresponding pubkeys  \n",
    "Using the CRT to solve for the number represented by the three ciphertexts (which are residues mod their respective pubkeys)  \n",
    "Taking the cube root of the resulting number  \n",
    "The CRT says you can take any number and represent it as the combination of a series of residues mod a series of moduli. In the three-residue case, you have:\n",
    "**result =  \n",
    "  (c_0 * m_s_0 * invmod(m_s_0, n_0)) +  \n",
    "  (c_1 * m_s_1 * invmod(m_s_1, n_1)) +  \n",
    "  (c_2 * m_s_2 * invmod(m_s_2, n_2)) mod N_012**  \n",
    "where:  \n",
    "**c_0, c_1, c_2 are the three respective residues mod  \n",
    " n_0, n_1, n_2  \n",
    " m_s_n (for n in 0, 1, 2) are the product of the moduli  \n",
    " EXCEPT n_n --- ie, m_s_1 is n_0 * n_2  \n",
    " N_012 is the product of all three moduli**  \n",
    "To decrypt RSA using a simple cube root, leave off the final modulus operation; just take the raw accumulated result and cube-root it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Imports\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [],
   "source": [
    "def floorRoot(n: int, s: int) -> int:\n",
    "    \"\"\"\n",
    "    Finds the specified powered root of an integer and returns the resulting float's floor value.\n",
    "    \"\"\"\n",
    "    \n",
    "    b = n.bit_length()\n",
    "    p = math.ceil(b/s)\n",
    "    x = 2**p\n",
    "    while x > 1:\n",
    "        y = (((s - 1) * x) + (n // (x**(s-1)))) // s\n",
    "        if y >= x:\n",
    "            return x\n",
    "        x = y\n",
    "    return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "def RSA_Broadcast_Attack(message: bytes, rsa0: object, rsa1: object, rsa2: object) -> bytes:\n",
    "    \"\"\"\n",
    "    Uses the Chinese Remainder Theorem (CRT) to break e=3 RSA given three ciphertexts of the same plaintext.\n",
    "    This attack could be easily coded to work also when a different number of ciphertexts is provided.\n",
    "    Check here for reference: https://crypto.stanford.edu/pbc/notes/numbertheory/crt.html\n",
    "    \"\"\"\n",
    "\n",
    "    # Obtain the N from the public keys of the RSA objects.\n",
    "    n0 = rsa0.pub[1]\n",
    "    n1 = rsa1.pub[1]\n",
    "    n2 = rsa2.pub[1]\n",
    "    \n",
    "    # Encrypt the integer of the message via all three RSA objects.\n",
    "    plainnum = int.from_bytes(message, \"big\")\n",
    "    c0 = rsa0.encryptnum(plainnum)\n",
    "    c1 = rsa1.encryptnum(plainnum)\n",
    "    c2 = rsa2.encryptnum(plainnum)\n",
    "    \n",
    "    # Can't do N/n0 for ms0 instead because floating point operations arent accurate\n",
    "    N = n0 * n1 * n2\n",
    "    ms0 = n1 * n2\n",
    "    ms1 = n0 * n2\n",
    "    ms2 = n0 * n1\n",
    "    \n",
    "    r0 = (c0 * ms0 * mod_inverse(ms0, n0))\n",
    "    r1 = (c1 * ms1 * mod_inverse(ms1, n1))\n",
    "    r2 = (c2 * ms2 * mod_inverse(ms2, n2))\n",
    "    \n",
    "    R = (r0 + r1 + r2) % N\n",
    "    m = floorRoot(R, 3)\n",
    "    \n",
    "    return m.to_bytes((m.bit_length() + 7) // 8, \"big\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div style=\"border:1px solid #c3e6cb;padding:.75rem 3rem;border-radius:.5rem;font-weight:bold;text-align: center;background-color:#d4edda;color:#155724;border-color:#c3e6cb;\">Completed</div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "message = \"This is RSA Broadcast Attack\"\n",
    "test(RSA_Broadcast_Attack(message.encode(), RSA(256), RSA(256), RSA(256)).decode(\"utf-8\") == message)"
   ]
  }
 ],
 "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}