#!/usr/bin/python2.7
# Authored by Adam Carpenter
# Initial code base authored by Prof. Dmitry Evtyushkin

import random
import time
from mr import is_probable_prime as is_prime

def int_to_bin(i):
    o = '{0:08b}'.format(i)
    o = (8 - (len(o) % 8)) * '0' + o
    return o

# def int_to_bin(i):
#     # deprecated; incorrect output
#     return "{0:08b}".format(i)

def bin_to_int(b):
    return int(b,2)

def str_to_bin(s):
    o = ''
    for i in s:
        o += '{0:08b}'.format(ord(i))
    return o

def bin_to_str(b):
    l = [b[i:i+8] for i in xrange(0,len(b),8)]
    o = ''
    for i in l:
        o+=chr(int(i,2))
    return o

def egcd(a, b): # can be used to test if numbers are co-primes
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
        #if g==1, the numbers are co-prime

def modinv(a, m):
    #returns multiplicative modular inverse of a in mod m
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def sxor(a, b):
    # returns the exclusive-or result of two strings/characters
    if a == b:
        return "0"
    else:
        return "1"

def srshift(a, b = "0"):
    # performs right-shift-like operation on a string;
    # b serves as the replacement most-significant bit
    return b + a[:-1]

class lfsr:
    # Class implementing linear feedback shift register. Please note that it operates
    # with binary strings, strings of '0's and '1's.
    taps = []

    def __init__ (self, taps):
        # Receives a list of taps. Taps are the bit positions that are XOR-ed
        # together and provided to the input of lfsr

        globals()['taps'] = taps
        self.register = '1111111111111111'
        # initial state of lfsr

    def clock(self, i='0'):
        # Receives input bit and simulates one cycle
        # This include xoring, shifting, updating input bit and returning output
        # input bit must be XOR-ed with the taps!!

        # grab output bit
        outputBit = self.register[-1]

        # xor all tap values together
        tapXor = "0"

        for tap in taps:
            tapXor = sxor(tapXor, self.register[tap])

        # xor input bit with resulting tap
        inputBit = sxor(i, tapXor)

        # shift register bits and prepend input bit to stream
        self.register = srshift(self.register, inputBit)

        # return output bit
        return outputBit

    def seed(self, s):
        # This function seeds the lfsr by feeding all bits from s into input of
        # lfsr, output is ignored
        for i in s:
            o = self.clock(i)

    def gen(self,n,skip=0):
        # This function clocks lfsr 'skip' number of cycles ignoring output,
        # then clocks 'n' cycles more and records the output. Then returns
        # the recorded output. This is used as hash or pad
        for x in xrange(skip):
            self.clock()
        out = ''
        for x in xrange(n):
            out += self.clock()
        return out

def H(inp):
    # Hash function, it must initialize a new lfsr, seed it with the inp binary string
    # skip and read the required number of lfsr output bits, returns binary string

    l = lfsr([2,4,5,7,11,14])
    l.seed(inp)
    return l.gen(56, 1000)

def enc_pad(m,p):
    # encrypt message m with pad p, return binary string
    # note: function assumes pad p is the same length
    # as message m, per the definition of OTP
    o = ''

    for i in range(0, len(m)):
        o +=  sxor(m[i], p[i])

    return o

def GenRSA():
    # Function to generate RSA keys. Use the Euler's totient function (phi)
    # As we discussed in lectures. Function must: 1) seed python's random number
    # generator with time.time() 2) Generate RSA primes by keeping generating
    # random integers of size 512 bit using the random.getrandbits(512) and testing
    # whether they are prime or not using the is_prime function until both primes found.
    # 3) compute phi 4) find e that is coprime to phi. Start from e=3 and keep
    # incrementing until you find a suitable one. 4) derive d 5) return tuple (n,e,d)
    # n - public modulo, e - public exponent, d - private exponent

    # seed random number generator
    random.seed(time.time())

    # generate rsa primes
    p = random.getrandbits(512)
    q = random.getrandbits(512)

    while not is_prime(p):
        p = random.getrandbits(512)

    while not is_prime(q):
        q = random.getrandbits(512)

    # compute n and phi
    n = p * q
    phi = (p - 1) * (q - 1)

    # find an e coprime to phi
    e = 3

    while egcd(e, phi)[0] != 1:
        e += 1

    # derive d
    d = modinv(e, phi)

    # return the tuple
    return (n,e,d)