notebooks/17_cryptography.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cf5b777d",
   "metadata": {},
   "source": [
    "# Substitution Ciphers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c5a64277",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "vpf tziuo slqer hqw czxab qnfl vpf mjdg yqk\n",
      "the quick brown fox jumps over the lazy dog\n"
     ]
    }
   ],
   "source": [
    "alphabet = 'abcdefghijklmnopqrstuvwxyz'\n",
    "key =      'jsuyfhkpicomxrqatlbvznewgd'\n",
    "\n",
    "\n",
    "def substitute(text, substitute_what, substitute_by):\n",
    "    result = ''\n",
    "    for symbol in text.lower():\n",
    "        if symbol in substitute_what:\n",
    "            result += substitute_by[\n",
    "                substitute_what.index(symbol)\n",
    "            ]\n",
    "        else:\n",
    "            result += symbol\n",
    "\n",
    "    return result\n",
    "\n",
    "\n",
    "def encode(plaintext):\n",
    "    return substitute(plaintext, alphabet, key)\n",
    "\n",
    "\n",
    "def decode(ciphertext):\n",
    "    return substitute(ciphertext, key, alphabet)\n",
    "\n",
    "\n",
    "message = 'the quick brown fox jumps over the lazy dog'\n",
    "code = encode(message)\n",
    "print(code)\n",
    "print(decode(code))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "debddcff",
   "metadata": {},
   "source": [
    "Cyclic shift of the alphabet:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "bbe4c6bc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "abcdefghijklmnopqrstuvwxyz\n",
      "defghijklmnopqrstuvwxyzabc\n"
     ]
    }
   ],
   "source": [
    "alphabet = 'abcdefghijklmnopqrstuvwxyz'\n",
    "key = alphabet[3:] + alphabet[:3]\n",
    "\n",
    "print(alphabet)\n",
    "print(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e9596f7",
   "metadata": {},
   "source": [
    "Trying all cyclic shifts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "de0d650c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "kyv wzmv sfozex nzqriuj aldg hlztbcp\n",
      "jxu vylu renydw mypqhti zkcf gkysabo\n",
      "iwt uxkt qdmxcv lxopgsh yjbe fjxrzan\n",
      "hvs twjs pclwbu kwnofrg xiad eiwqyzm\n",
      "gur svir obkvat jvmneqf whzc dhvpxyl\n",
      "ftq ruhq najuzs iulmdpe vgyb cguowxk\n",
      "esp qtgp mzityr htklcod ufxa bftnvwj\n",
      "dro psfo lyhsxq gsjkbnc tewz aesmuvi\n",
      "cqn oren kxgrwp frijamb sdvy zdrltuh\n",
      "bpm nqdm jwfqvo eqhizla rcux ycqkstg\n",
      "aol mpcl ivepun dpghykz qbtw xbpjrsf\n",
      "znk lobk hudotm cofgxjy pasv waoiqre\n",
      "ymj knaj gtcnsl bnefwix ozru vznhpqd\n",
      "xli jmzi fsbmrk amdevhw nyqt uymgopc\n",
      "wkh ilyh eralqj zlcdugv mxps txlfnob\n",
      "vjg hkxg dqzkpi ykbctfu lwor swkemna\n",
      "uif gjwf cpyjoh xjabset kvnq rvjdlmz\n",
      "the five boxing wizards jump quickly\n",
      "sgd ehud anwhmf vhyzqcr itlo pthbjkx\n",
      "rfc dgtc zmvgle ugxypbq hskn osgaijw\n",
      "qeb cfsb ylufkd tfwxoap grjm nrfzhiv\n",
      "pda bera xktejc sevwnzo fqil mqeyghu\n",
      "ocz adqz wjsdib rduvmyn ephk lpdxfgt\n",
      "nby zcpy vircha qctulxm dogj kocwefs\n",
      "max ybox uhqbgz pbstkwl cnfi jnbvder\n",
      "lzw xanw tgpafy oarsjvk bmeh imaucdq\n"
     ]
    }
   ],
   "source": [
    "ciphertext = 'kyv wzmv sfozex nzqriuj aldg hlztbcp'\n",
    "for shift in range(26):\n",
    "    key = alphabet[shift:] + alphabet[:shift]\n",
    "    print(decode(ciphertext))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ef78a40",
   "metadata": {},
   "source": [
    "# One-time Pad"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "52efdb3e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "\n",
    "def encode(plain_text, private_key):\n",
    "    assert plain_text in {0, 1} and private_key in {0, 1}\n",
    "    return plain_text ^ private_key\n",
    "\n",
    "\n",
    "def decode(cypher_text, private_key):\n",
    "    assert cypher_text in {0, 1} and private_key in {0, 1}\n",
    "    return cypher_text ^ private_key\n",
    "\n",
    "\n",
    "for plaintext, private_key in product({0, 1}, repeat=2):\n",
    "    ciphertext = encode(plaintext, private_key)\n",
    "    print(f'key: {private_key}, '\n",
    "          f'plaintext: {plaintext}, '\n",
    "          f'ciphertext: {ciphertext}, '\n",
    "          f'decoded: {decode(ciphertext, private_key)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0260606",
   "metadata": {},
   "source": [
    "## Many Time Pad Attack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "e46afde3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hex of Hello World is: 48656c6c6f20576f726c64\n",
      "str of 736f6d65206d657373616765 is: some message\n",
      "hex of secret message is: 736563726574206d657373616765\n",
      "6d7920736563726574206b657973\n",
      "ciphertext: 1e1c430100175208115318041e16\n",
      "recovered message: secret message\n",
      "071c00410e4f0d4811481645041b1718\n",
      "071c00410e4f0d4811481645041b1718\n",
      "Xor of the ciphertexts is the same as xor of messages\n",
      "Good guesses:\n",
      "position 5:\n",
      "       one message part: \" the \"\n",
      " the other message part: \"oy th\"\n",
      "position 7:\n",
      "       one message part: \" the \"\n",
      " the other message part: \"he se\"\n",
      "Good guesses:\n",
      "position 5:\n",
      "       one message part: \"oy the \"\n",
      " the other message part: \" the se\"\n"
     ]
    }
   ],
   "source": [
    "def to_hex(plain_text):\n",
    "    hex_codes = []\n",
    "    for symbol in plain_text:\n",
    "        hex_code = hex(ord(symbol)).replace('0x', '')\n",
    "        if len(hex_code) == 1:\n",
    "            hex_code = '0' + hex_code\n",
    "        hex_codes.append(hex_code)\n",
    "    return ''.join(hex_codes)\n",
    "\n",
    "\n",
    "def to_str(hex_code):\n",
    "    if hex_code:\n",
    "        return chr(int(hex_code[:2], base=16)) + to_str(hex_code[2:])\n",
    "    return ''\n",
    "\n",
    "\n",
    "message = 'Hello World'\n",
    "print(f'hex of {message} is: {to_hex(message)}')\n",
    "\n",
    "code = '736f6d65206d657373616765'\n",
    "print(f'str of {code} is: {to_str(code)}')\n",
    "\n",
    "\n",
    "def bitwise_xor(first_text, second_text):\n",
    "    assert len(first_text) == len(second_text)\n",
    "    return ''.join(format(int(s1, 16) ^ int(s2, 16), '01x')\n",
    "                   for s1, s2 in zip(first_text, second_text))\n",
    "\n",
    "\n",
    "message = 'secret message'\n",
    "key =     'my secret keys'\n",
    "print(f'hex of {message} is: {to_hex(message)}')\n",
    "print(to_hex(key))\n",
    "\n",
    "ciphertext = bitwise_xor(to_hex(message), to_hex(key))\n",
    "print('ciphertext:', ciphertext)\n",
    "\n",
    "recovered_message = to_str(bitwise_xor(ciphertext, to_hex(key)))\n",
    "print('recovered message:', recovered_message)\n",
    "\n",
    "\n",
    "message1 = 'steal the secret'\n",
    "message2 = 'the boy the girl'\n",
    "key = 'supersecretverys'\n",
    "\n",
    "ciphertext1 = bitwise_xor(to_hex(message1), to_hex(key))\n",
    "ciphertext2 = bitwise_xor(to_hex(message2), to_hex(key))\n",
    "\n",
    "xor_ciphertexts = bitwise_xor(ciphertext1, ciphertext2)\n",
    "xor_messages = bitwise_xor(to_hex(message1), to_hex(message2))\n",
    "\n",
    "print(xor_ciphertexts)\n",
    "print(xor_messages)\n",
    "\n",
    "if xor_ciphertexts == xor_messages:\n",
    "    print('Xor of the ciphertexts is the same as xor of messages')\n",
    "else:\n",
    "    print('Xor of the ciphertexts differs from the xor of messages')\n",
    "\n",
    "\n",
    "def try_guessing_substring(substring, message_length, xor_messages):\n",
    "    good_guesses = []\n",
    "    for pos in range(message_length - len(substring) + 1):\n",
    "        guess = to_hex(chr(0) * pos + substring +\n",
    "                       chr(0) * (message_length - len(substring) - pos))\n",
    "        other_message_part = to_str(\n",
    "            bitwise_xor(guess, xor_messages)\n",
    "        )[pos:pos + len(substring)]\n",
    "        good_guess = True\n",
    "        for i in range(len(other_message_part)):\n",
    "            if not other_message_part[i].isalpha() and \\\n",
    "                    not other_message_part[i].isspace():\n",
    "                good_guess = False\n",
    "                break\n",
    "        if good_guess:\n",
    "            good_guesses.append((guess, pos, other_message_part))\n",
    "\n",
    "    print('Good guesses:')\n",
    "    for guess in good_guesses:\n",
    "        print(f'position {guess[1]}:\\n'\n",
    "              f'       one message part: \\\"{substring}\\\"\\n'\n",
    "              f' the other message part: \\\"{guess[2]}\\\"')\n",
    "\n",
    "\n",
    "try_guessing_substring(' the ', len(message1), xor_messages)\n",
    "\n",
    "try_guessing_substring('oy the ', len(message1), xor_messages)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "96f71642",
   "metadata": {},
   "source": [
    "# RSA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "a10f4734",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n=16921456439215439701\n",
      "phi=16921456430439366112\n",
      "e=3\n",
      "d=11280970953626244075\n",
      "message: 92616855427\n",
      "decoded: 92616855427\n"
     ]
    }
   ],
   "source": [
    "from math import gcd\n",
    "p, q = 5915587277, 2860486313\n",
    "\n",
    "n = p * q\n",
    "print(f'n={n}')\n",
    "\n",
    "phi = (p - 1) * (q - 1)\n",
    "print(f'phi={phi}')\n",
    "e = 3\n",
    "print(f'e={e}')\n",
    "assert gcd(phi, e) == 1\n",
    "\n",
    "d = pow(e, -1, phi)\n",
    "print(f'd={d}')\n",
    "assert d * e % phi == 1\n",
    "\n",
    "\n",
    "def encode(m):\n",
    "    assert 0 <= m < n\n",
    "    return pow(m, e, n)\n",
    "\n",
    "\n",
    "message = 92616855427\n",
    "print(f'message: {message}')\n",
    "cipher_text = encode(message)\n",
    "\n",
    "\n",
    "def decode(c):\n",
    "    return pow(c, d, n)\n",
    "\n",
    "\n",
    "print(f'decoded: {decode(cipher_text)}')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}