1 files changed, 171 insertions, 0 deletions
diff --git a/hw3/carpenter_adam_hw3.py b/hw3/carpenter_adam_hw3.py
new file mode 100755
index 0000000..050afc5
--- /dev/null
+++ b/hw3/carpenter_adam_hw3.py
@@ -0,0 +1,171 @@
+#!/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)