renxida/hw5.ipynb

## hw5.ipynb
{
  "cells": [
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Code given"
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "import random\n\n_mrpt_num_trials = 5 # number of bases to test\n\ndef is_probable_prime(n):\n    \"\"\"\n    Miller-Rabin primality test.\n\n    A return value of False means n is certainly not prime. A return value of\n    True means n is very likely a prime.\n\n    >>> is_probable_prime(1)\n    Traceback (most recent call last):\n        ...\n    AssertionError\n    >>> is_probable_prime(2)\n    True\n    >>> is_probable_prime(3)\n    True\n    >>> is_probable_prime(4)\n    False\n    >>> is_probable_prime(5)\n    True\n    >>> is_probable_prime(123456789)\n    False\n\n    >>> primes_under_1000 = [i for i in range(2, 1000) if is_probable_prime(i)]\n    >>> len(primes_under_1000)\n    168\n    >>> primes_under_1000[-10:]\n    [937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n\n    >>> is_probable_prime(6438080068035544392301298549614926991513861075340134\\\n3291807343952413826484237063006136971539473913409092293733259038472039\\\n7133335969549256322620979036686633213903952966175107096769180017646161\\\n851573147596390153)\n    True\n\n    >>> is_probable_prime(7438080068035544392301298549614926991513861075340134\\\n3291807343952413826484237063006136971539473913409092293733259038472039\\\n7133335969549256322620979036686633213903952966175107096769180017646161\\\n851573147596390153)\n    False\n    \"\"\"\n    assert n >= 2\n    # special case 2\n    if n == 2:\n        return True\n    # ensure n is odd\n    if n % 2 == 0:\n        return False\n    # write n-1 as 2**s * d\n    # repeatedly try to divide n-1 by 2\n    s = 0\n    d = n-1\n    while True:\n        quotient, remainder = divmod(d, 2)\n        if remainder == 1:\n            break\n        s += 1\n        d = quotient\n    assert(2**s * d == n-1)\n\n    # test the base a to see whether it is a witness for the compositeness of n\n    def try_composite(a):\n        if pow(a, d, n) == 1:\n            return False\n        for i in range(s):\n            if pow(a, 2**i * d, n) == n-1:\n                return False\n        return True # n is definitely composite\n\n    for i in range(_mrpt_num_trials):\n        a = random.randrange(2, n)\n        if try_composite(a):\n            return False\n\n    return True # no base tested showed n as composite",
      "execution_count": 1,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "import math",
      "execution_count": 2,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "#!/usr/bin/python2.7\n\nimport random\nimport time\n#from mr import is_probable_prime as is_prime\n\ndef int_to_bin(i):\n    o = '{0:08b}'.format(i)\n    o = (8 - (len(o) % 8)) * '0' + o\n    return o\n\ndef bin_to_int(b):\n    return int(b,2)\n\ndef str_to_bin(s):\n    o = ''\n    for i in s:\n        o += '{0:08b}'.format(ord(i))\n    return o\n\ndef bin_to_str(b):\n    l = [b[i:i+8] for i in xrange(0,len(b),8)]\n    o = ''\n    for i in l:\n        o+=chr(int(i,2))\n    return o\n\ndef egcd(a, b): # can be used to test if numbers are co-primes\n    if a == 0:\n        return (b, 0, 1)\n    else:\n        g, y, x = egcd(b % a, a)\n        return (g, x - (b // a) * y, y)\n        #if g==1, the numbers are co-prime\n\ndef modinv(a, m):\n    #returns multiplicative modular inverse of a in mod m\n    g, x, y = egcd(a, m)\n    if g != 1:\n        raise Exception('modular inverse does not exist')\n    else:\n        return x % m",
      "execution_count": 3,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Implement LSFR"
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "# some helper functions to deal with character-represented binaries\ndef cand(a,b):\n    return '1' if (a=='1') and (b=='1') else '0'\n\ndef cor(a,b):\n    return '1' if (a=='1') or (b=='1') else '0'\n\ndef cxor(a,b):\n    return '1' if (a=='1') ^ (b=='1') else '0'\n\ndef cnot(a):\n    return '1' if (a=='0') else '0'",
      "execution_count": 4,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "from functools import reduce",
      "execution_count": 5,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "class lfsr:\n    # Class implementing linear feedback shift register. Please note that it operates\n    # with binary strings, strings of '0's and '1's.\n    taps = []\n    def __init__ (self, taps):\n    # Receives a list of taps. Taps are the bit positions that are XOR-ed\n    #together and provided to the input of lfsr\n        # initial state of lfsr\n        self.register = '1111111111111111'\n        # taps\n        self.taps = taps\n        self.mask = ['0'] * len(self.register)\n        for i in self.taps:\n            self.mask[i] = '1'\n        \n    \n\n    def clock(self, i='0'):\n    #Receives input bit and simulates one cycle\n    #This include xoring, shifting, updating input bit and returning output\n    #input bit must be XOR-ed with the taps!!\n        b = reduce(cxor, map(cand, self.mask, self.register), '0')\n        b = cxor(b, i)\n        o = self.register[-1]\n        self.register = b + self.register[:-1]\n        return o #returns output bit\n\n    def seed(self, s):\n    # This function seeds the lfsr by feeding all bits from s into input of\n    # lfsr, output is ignored\n        for i in s:\n            o = self.clock(i)\n\n    def gen(self,n,skip=0):\n    # This function clocks lfsr 'skip' number of cycles ignoring output,\n    # then clocks 'n' cycles more and records the output. Then returns\n    # the recorded output. This is used as hash or pad\n        for x in range(skip):\n            self.clock()\n        out = ''\n        for x in range(n):\n            out += self.clock()\n        return out",
      "execution_count": 6,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Problem 1"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "l = lfsr([2,4,5,7,11,14])\nl.seed(int_to_bin(1234))\nl.gen(10,1000)",
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 7,
          "data": {
            "text/plain": "'0010000100'"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Problem 2"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "# need to figure out hash length\nlen('10101010001011011011011010001001110111100001101110000100')",
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 8,
          "data": {
            "text/plain": "56"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def H(inp):\n    # Hash function, it must initialize a new lfsr, seed it with the inp binary string\n    # skip and read the required number of lfsr output bits, returns binary string\n\n    ## -- Implement me -- ##\n\n    # Example: H(int_to_bin(0)) -> '10111000111111111111111000110001010010000101011101001100'\n    # Example: H('0') -> '01010101010001110111000111111111111111000110001010010000'\n    # Example: H(int_to_bin(777)) -> '00010101011001100111111100110111101011001111001101011001'\n    s = lfsr([2,4,5,7,11,14])\n    s.seed(inp)\n    return s.gen(56, 1000)",
      "execution_count": 9,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "scrolled": true
      },
      "cell_type": "code",
      "source": "H(str_to_bin('My name is Bart Simpson and I like krusty burgers'))",
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 10,
          "data": {
            "text/plain": "'10101010001011011011011010001001110111100001101110000100'"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Problem 3"
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "def enc_pad(m,p):\n    # encrypt message m with pad p, return binary string\n    o = ''\n\n    ## -- Implement me -- ##\n\n    return ''.join(map(cxor, m, p))",
      "execution_count": 11,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "xrange = range",
      "execution_count": 12,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "s = \"Hello, my name is Bobby Hill\"\nbs = str_to_bin(s)\nbs",
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 13,
          "data": {
            "text/plain": "'01001000011001010110110001101100011011110010110000100000011011010111100100100000011011100110000101101101011001010010000001101001011100110010000001000010011011110110001001100010011110010010000001001000011010010110110001101100'"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "l = lfsr([2,4,5,7,11,14])\nl.seed(int_to_bin(77))\npad = l.gen(len(bs), 1000)\npad",
      "execution_count": 14,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 14,
          "data": {
            "text/plain": "'00111110100111000001101100110001110001010010001100001110111010011100101010101111101001110100110010110111011011100111001001011001000101100001111000011000011010100110101110011000010111101011001011100100100010000110011110100110'"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "cipher = enc_pad(bs,pad)\ncipher\n\nbin_to_str(cipher)",
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 15,
          "data": {
            "text/plain": "\"vùw]ª\\x0f.\\x84³\\x8fÉ-Ú\\x0bR0e>Z\\x05\\tú'\\x92¬á\\x0bÊ\""
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "bin_to_str(enc_pad(cipher,pad))",
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 16,
          "data": {
            "text/plain": "'Hello, my name is Bobby Hill'"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Problem 4"
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "def is_prime(n):\n    if n % 2 == 0 and n > 2: \n        return False\n    if not is_probable_prime(n):\n        return False\n    return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))",
      "execution_count": 17,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "def GenRSA():\n    # Function to generate RSA keys. Use the Euler's totient function (phi)\n    # As we discussed in lectures. Function must: 1) seed python's random number\n    # generator with time.time() 2) Generate RSA primes by keeping generating\n    # random integers of size 512 bit using the random.getrandbits(512) and testing\n    # whether they are prime or not using the is_prime function until both primes found.\n    # 3) compute phi 4) find e that is coprime to phi. Start from e=3 and keep\n    # incrementing until you find a suitable one. 4) derive d 5) return tuple (n,e,d)\n    # n - public modulo, e - public exponent, d - private exponent\n\n    random.seed(time.time())\n\n    while 1:\n        p = random.getrandbits(512)\n        if is_probable_prime(p):\n            break\n    print(f'p = {p}')\n        \n    while 1:\n        q = random.getrandbits(512)\n        if is_probable_prime(q):\n            break\n    print(f'q = {q}')\n            \n    n = p*q\n    phin = (p-1)*(q-1)\n    \n    while 1:\n        e = random.getrandbits(512)\n        g = egcd(e, phin)[0]\n        print(f'gcd: {g}')\n        if g == 1 and e != 1:\n            break\n    \n            \n    d = modinv(e, phin)\n    \n    return (n,e,d)",
      "execution_count": 18,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "(n, e, d) = GenRSA()",
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "text": "p = 5210305813163478779467637689471907823300298019836508858976724867020381587757230271023901985724692412493531137217006389462992412412843940711267327130327491\nq = 10893109859988628768429924698318202278961722621882257734543853259215703478499065179083588615065539845157107987404549170624697845566228212188845305588742411\ngcd: 1\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print(n)",
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "text": "56756433626927160890567298249835538181072848115373026951998622751936808435933770113842081967799293724431564623085178459726669634972601913160035275592630214437620133638277770754849532324913497351084298552523501902813283740381107995046054084253137581418700967990542443069442726646585552930142828014473270920801\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print(e)",
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "text": "3102160972872790819191091100263082283019767465522225714682135187382054135625400736983705330441456571648011057007745265729752577020427193317583614967395669\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "print(d)",
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "text": "40061730088138388265205059528303006196362922036172940301757070625993965057958600818259741959647566716681680001637205277726299876787313339379010451941386570666745210077003696190958650849061931885005506587604310601089089592506284625894757366533237435665159679592192942793180632906022715615469793662108135499129\n",
          "name": "stdout"
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "# Problem 5"
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Testing rsa on simple dumb message:"
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "m = 13",
      "execution_count": 23,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "ct = pow(m, e,n)",
      "execution_count": 24,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "pt = pow(ct, d, n)",
      "execution_count": 25,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "pt",
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 26,
          "data": {
            "text/plain": "13"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Testing on string:"
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "def numfy(s):\n    number = 0\n    for e in [ord(c) for c in s]:\n        number = (number * 0x110000) + e\n    return number\n\ndef denumfy(number):\n    l = []\n    while(number != 0):\n        l.append(chr(number % 0x110000))\n        number = number // 0x110000\n    return ''.join(reversed(l))",
      "execution_count": 27,
      "outputs": []
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Encrypt signature (sender side)"
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "m = numfy('Xida Ren xren@email.wm.edu')",
      "execution_count": 28,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "m",
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 29,
          "data": {
            "text/plain": "1311307174389762671823524074404195751504230430632247255936799416993280055955498414405218130567801372045454808677323509881278962936714222191168285602742389"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "ct = pow(m, e, n)",
      "execution_count": 30,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "ct",
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 31,
          "data": {
            "text/plain": "33481921995922537420670537489331761785783983627272239683211619181485506355077076365179517438383597821321898391312213141615019938555036578889080587656585145177657181015984592009878832164482492986955942965604218753993404613173029265432399169289016359695157633801054563416879936793280666608704654387315678216044"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {},
      "cell_type": "markdown",
      "source": "Decrypt signature (receiver side)"
    },
    {
      "metadata": {
        "trusted": true,
        "collapsed": true
      },
      "cell_type": "code",
      "source": "pt = pow(ct, d, n)",
      "execution_count": 32,
      "outputs": []
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "pt",
      "execution_count": 33,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 33,
          "data": {
            "text/plain": "1311307174389762671823524074404195751504230430632247255936799416993280055955498414405218130567801372045454808677323509881278962936714222191168285602742389"
          },
          "metadata": {}
        }
      ]
    },
    {
      "metadata": {
        "trusted": true
      },
      "cell_type": "code",
      "source": "denumfy(pt)",
      "execution_count": 34,
      "outputs": [
        {
          "output_type": "execute_result",
          "execution_count": 34,
          "data": {
            "text/plain": "'Xida Ren xren@email.wm.edu'"
          },
          "metadata": {}
        }
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3",
      "language": "python"
    },
    "hide_input": false,
    "language_info": {
      "name": "python",
      "version": "3.6.3",
      "mimetype": "text/x-python",
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "pygments_lexer": "ipython3",
      "nbconvert_exporter": "python",
      "file_extension": ".py"
    },
    "gist": {
      "id": "",
      "data": {
        "description": "hw5 rsa",
        "public": true
      }
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}
	{
	"cells": [
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "# Code given"
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "import random\n\n_mrpt_num_trials = 5 # number of bases to test\n\ndef is_probable_prime(n):\n \"\"\"\n Miller-Rabin primality test.\n\n A return value of False means n is certainly not prime. A return value of\n True means n is very likely a prime.\n\n >>> is_probable_prime(1)\n Traceback (most recent call last):\n ...\n AssertionError\n >>> is_probable_prime(2)\n True\n >>> is_probable_prime(3)\n True\n >>> is_probable_prime(4)\n False\n >>> is_probable_prime(5)\n True\n >>> is_probable_prime(123456789)\n False\n\n >>> primes_under_1000 = [i for i in range(2, 1000) if is_probable_prime(i)]\n >>> len(primes_under_1000)\n 168\n >>> primes_under_1000[-10:]\n [937, 941, 947, 953, 967, 971, 977, 983, 991, 997]\n\n >>> is_probable_prime(6438080068035544392301298549614926991513861075340134\\\n3291807343952413826484237063006136971539473913409092293733259038472039\\\n7133335969549256322620979036686633213903952966175107096769180017646161\\\n851573147596390153)\n True\n\n >>> is_probable_prime(7438080068035544392301298549614926991513861075340134\\\n3291807343952413826484237063006136971539473913409092293733259038472039\\\n7133335969549256322620979036686633213903952966175107096769180017646161\\\n851573147596390153)\n False\n \"\"\"\n assert n >= 2\n # special case 2\n if n == 2:\n return True\n # ensure n is odd\n if n % 2 == 0:\n return False\n # write n-1 as 2*s d\n # repeatedly try to divide n-1 by 2\n s = 0\n d = n-1\n while True:\n quotient, remainder = divmod(d, 2)\n if remainder == 1:\n break\n s += 1\n d = quotient\n assert(2*s d == n-1)\n\n # test the base a to see whether it is a witness for the compositeness of n\n def try_composite(a):\n if pow(a, d, n) == 1:\n return False\n for i in range(s):\n if pow(a, 2*i d, n) == n-1:\n return False\n return True # n is definitely composite\n\n for i in range(_mrpt_num_trials):\n a = random.randrange(2, n)\n if try_composite(a):\n return False\n\n return True # no base tested showed n as composite",
	"execution_count": 1,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "import math",
	"execution_count": 2,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "#!/usr/bin/python2.7\n\nimport random\nimport time\n#from mr import is_probable_prime as is_prime\n\ndef int_to_bin(i):\n o = '{0:08b}'.format(i)\n o = (8 - (len(o) % 8)) * '0' + o\n return o\n\ndef bin_to_int(b):\n return int(b,2)\n\ndef str_to_bin(s):\n o = ''\n for i in s:\n o += '{0:08b}'.format(ord(i))\n return o\n\ndef bin_to_str(b):\n l = [b[i:i+8] for i in xrange(0,len(b),8)]\n o = ''\n for i in l:\n o+=chr(int(i,2))\n return o\n\ndef egcd(a, b): # can be used to test if numbers are co-primes\n if a == 0:\n return (b, 0, 1)\n else:\n g, y, x = egcd(b % a, a)\n return (g, x - (b // a) * y, y)\n #if g==1, the numbers are co-prime\n\ndef modinv(a, m):\n #returns multiplicative modular inverse of a in mod m\n g, x, y = egcd(a, m)\n if g != 1:\n raise Exception('modular inverse does not exist')\n else:\n return x % m",
	"execution_count": 3,
	"outputs": []
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "# Implement LSFR"
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "# some helper functions to deal with character-represented binaries\ndef cand(a,b):\n return '1' if (a=='1') and (b=='1') else '0'\n\ndef cor(a,b):\n return '1' if (a=='1') or (b=='1') else '0'\n\ndef cxor(a,b):\n return '1' if (a=='1') ^ (b=='1') else '0'\n\ndef cnot(a):\n return '1' if (a=='0') else '0'",
	"execution_count": 4,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "from functools import reduce",
	"execution_count": 5,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "class lfsr:\n # Class implementing linear feedback shift register. Please note that it operates\n # with binary strings, strings of '0's and '1's.\n taps = []\n def __init__ (self, taps):\n # Receives a list of taps. Taps are the bit positions that are XOR-ed\n #together and provided to the input of lfsr\n # initial state of lfsr\n self.register = '1111111111111111'\n # taps\n self.taps = taps\n self.mask = ['0'] * len(self.register)\n for i in self.taps:\n self.mask[i] = '1'\n \n \n\n def clock(self, i='0'):\n #Receives input bit and simulates one cycle\n #This include xoring, shifting, updating input bit and returning output\n #input bit must be XOR-ed with the taps!!\n b = reduce(cxor, map(cand, self.mask, self.register), '0')\n b = cxor(b, i)\n o = self.register[-1]\n self.register = b + self.register[:-1]\n return o #returns output bit\n\n def seed(self, s):\n # This function seeds the lfsr by feeding all bits from s into input of\n # lfsr, output is ignored\n for i in s:\n o = self.clock(i)\n\n def gen(self,n,skip=0):\n # This function clocks lfsr 'skip' number of cycles ignoring output,\n # then clocks 'n' cycles more and records the output. Then returns\n # the recorded output. This is used as hash or pad\n for x in range(skip):\n self.clock()\n out = ''\n for x in range(n):\n out += self.clock()\n return out",
	"execution_count": 6,
	"outputs": []
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "# Problem 1"
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "l = lfsr([2,4,5,7,11,14])\nl.seed(int_to_bin(1234))\nl.gen(10,1000)",
	"execution_count": 7,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 7,
	"data": {
	"text/plain": "'0010000100'"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "# Problem 2"
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "# need to figure out hash length\nlen('10101010001011011011011010001001110111100001101110000100')",
	"execution_count": 8,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 8,
	"data": {
	"text/plain": "56"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "def H(inp):\n # Hash function, it must initialize a new lfsr, seed it with the inp binary string\n # skip and read the required number of lfsr output bits, returns binary string\n\n ## -- Implement me -- ##\n\n # Example: H(int_to_bin(0)) -> '10111000111111111111111000110001010010000101011101001100'\n # Example: H('0') -> '01010101010001110111000111111111111111000110001010010000'\n # Example: H(int_to_bin(777)) -> '00010101011001100111111100110111101011001111001101011001'\n s = lfsr([2,4,5,7,11,14])\n s.seed(inp)\n return s.gen(56, 1000)",
	"execution_count": 9,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true,
	"scrolled": true
	},
	"cell_type": "code",
	"source": "H(str_to_bin('My name is Bart Simpson and I like krusty burgers'))",
	"execution_count": 10,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 10,
	"data": {
	"text/plain": "'10101010001011011011011010001001110111100001101110000100'"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "# Problem 3"
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "def enc_pad(m,p):\n # encrypt message m with pad p, return binary string\n o = ''\n\n ## -- Implement me -- ##\n\n return ''.join(map(cxor, m, p))",
	"execution_count": 11,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "xrange = range",
	"execution_count": 12,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "s = \"Hello, my name is Bobby Hill\"\nbs = str_to_bin(s)\nbs",
	"execution_count": 13,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 13,
	"data": {
	"text/plain": "'01001000011001010110110001101100011011110010110000100000011011010111100100100000011011100110000101101101011001010010000001101001011100110010000001000010011011110110001001100010011110010010000001001000011010010110110001101100'"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "l = lfsr([2,4,5,7,11,14])\nl.seed(int_to_bin(77))\npad = l.gen(len(bs), 1000)\npad",
	"execution_count": 14,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 14,
	"data": {
	"text/plain": "'00111110100111000001101100110001110001010010001100001110111010011100101010101111101001110100110010110111011011100111001001011001000101100001111000011000011010100110101110011000010111101011001011100100100010000110011110100110'"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "cipher = enc_pad(bs,pad)\ncipher\n\nbin_to_str(cipher)",
	"execution_count": 15,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 15,
	"data": {
	"text/plain": "\"vùw]ª\\x0f.\\x84³\\x8fÉ-Ú\\x0bR0e>Z\\x05\\tú'\\x92¬á\\x0bÊ\""
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "bin_to_str(enc_pad(cipher,pad))",
	"execution_count": 16,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 16,
	"data": {
	"text/plain": "'Hello, my name is Bobby Hill'"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "# Problem 4"
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "def is_prime(n):\n if n % 2 == 0 and n > 2: \n return False\n if not is_probable_prime(n):\n return False\n return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))",
	"execution_count": 17,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "def GenRSA():\n # Function to generate RSA keys. Use the Euler's totient function (phi)\n # As we discussed in lectures. Function must: 1) seed python's random number\n # generator with time.time() 2) Generate RSA primes by keeping generating\n # random integers of size 512 bit using the random.getrandbits(512) and testing\n # whether they are prime or not using the is_prime function until both primes found.\n # 3) compute phi 4) find e that is coprime to phi. Start from e=3 and keep\n # incrementing until you find a suitable one. 4) derive d 5) return tuple (n,e,d)\n # n - public modulo, e - public exponent, d - private exponent\n\n random.seed(time.time())\n\n while 1:\n p = random.getrandbits(512)\n if is_probable_prime(p):\n break\n print(f'p = {p}')\n \n while 1:\n q = random.getrandbits(512)\n if is_probable_prime(q):\n break\n print(f'q = {q}')\n \n n = pq\n phin = (p-1)(q-1)\n \n while 1:\n e = random.getrandbits(512)\n g = egcd(e, phin)[0]\n print(f'gcd: {g}')\n if g == 1 and e != 1:\n break\n \n \n d = modinv(e, phin)\n \n return (n,e,d)",
	"execution_count": 18,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "(n, e, d) = GenRSA()",
	"execution_count": 19,
	"outputs": [
	{
	"output_type": "stream",
	"text": "p = 5210305813163478779467637689471907823300298019836508858976724867020381587757230271023901985724692412493531137217006389462992412412843940711267327130327491\nq = 10893109859988628768429924698318202278961722621882257734543853259215703478499065179083588615065539845157107987404549170624697845566228212188845305588742411\ngcd: 1\n",
	"name": "stdout"
	}
	]
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "print(n)",
	"execution_count": 20,
	"outputs": [
	{
	"output_type": "stream",
	"text": "56756433626927160890567298249835538181072848115373026951998622751936808435933770113842081967799293724431564623085178459726669634972601913160035275592630214437620133638277770754849532324913497351084298552523501902813283740381107995046054084253137581418700967990542443069442726646585552930142828014473270920801\n",
	"name": "stdout"
	}
	]
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "print(e)",
	"execution_count": 21,
	"outputs": [
	{
	"output_type": "stream",
	"text": "3102160972872790819191091100263082283019767465522225714682135187382054135625400736983705330441456571648011057007745265729752577020427193317583614967395669\n",
	"name": "stdout"
	}
	]
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "print(d)",
	"execution_count": 22,
	"outputs": [
	{
	"output_type": "stream",
	"text": "40061730088138388265205059528303006196362922036172940301757070625993965057958600818259741959647566716681680001637205277726299876787313339379010451941386570666745210077003696190958650849061931885005506587604310601089089592506284625894757366533237435665159679592192942793180632906022715615469793662108135499129\n",
	"name": "stdout"
	}
	]
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "# Problem 5"
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "Testing rsa on simple dumb message:"
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "m = 13",
	"execution_count": 23,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "ct = pow(m, e,n)",
	"execution_count": 24,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "pt = pow(ct, d, n)",
	"execution_count": 25,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "pt",
	"execution_count": 26,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 26,
	"data": {
	"text/plain": "13"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "Testing on string:"
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "def numfy(s):\n number = 0\n for e in [ord(c) for c in s]:\n number = (number * 0x110000) + e\n return number\n\ndef denumfy(number):\n l = []\n while(number != 0):\n l.append(chr(number % 0x110000))\n number = number // 0x110000\n return ''.join(reversed(l))",
	"execution_count": 27,
	"outputs": []
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "Encrypt signature (sender side)"
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "m = numfy('Xida Ren xren@email.wm.edu')",
	"execution_count": 28,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "m",
	"execution_count": 29,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 29,
	"data": {
	"text/plain": "1311307174389762671823524074404195751504230430632247255936799416993280055955498414405218130567801372045454808677323509881278962936714222191168285602742389"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "ct = pow(m, e, n)",
	"execution_count": 30,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "ct",
	"execution_count": 31,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 31,
	"data": {
	"text/plain": "33481921995922537420670537489331761785783983627272239683211619181485506355077076365179517438383597821321898391312213141615019938555036578889080587656585145177657181015984592009878832164482492986955942965604218753993404613173029265432399169289016359695157633801054563416879936793280666608704654387315678216044"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {},
	"cell_type": "markdown",
	"source": "Decrypt signature (receiver side)"
	},
	{
	"metadata": {
	"trusted": true,
	"collapsed": true
	},
	"cell_type": "code",
	"source": "pt = pow(ct, d, n)",
	"execution_count": 32,
	"outputs": []
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "pt",
	"execution_count": 33,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 33,
	"data": {
	"text/plain": "1311307174389762671823524074404195751504230430632247255936799416993280055955498414405218130567801372045454808677323509881278962936714222191168285602742389"
	},
	"metadata": {}
	}
	]
	},
	{
	"metadata": {
	"trusted": true
	},
	"cell_type": "code",
	"source": "denumfy(pt)",
	"execution_count": 34,
	"outputs": [
	{
	"output_type": "execute_result",
	"execution_count": 34,
	"data": {
	"text/plain": "'Xida Ren xren@email.wm.edu'"
	},
	"metadata": {}
	}
	]
	}
	],
	"metadata": {
	"kernelspec": {
	"name": "python3",
	"display_name": "Python 3",
	"language": "python"
	},
	"hide_input": false,
	"language_info": {
	"name": "python",
	"version": "3.6.3",
	"mimetype": "text/x-python",
	"codemirror_mode": {
	"name": "ipython",
	"version": 3
	},
	"pygments_lexer": "ipython3",
	"nbconvert_exporter": "python",
	"file_extension": ".py"
	},
	"gist": {
	"id": "",
	"data": {
	"description": "hw5 rsa",
	"public": true
	}
	}
	},
	"nbformat": 4,
	"nbformat_minor": 2
	}