summaryrefslogtreecommitdiff
path: root/hw3
diff options
context:
space:
mode:
author53hornet <53hornet@gmail.com>2019-02-02 23:10:20 -0500
committer53hornet <53hornet@gmail.com>2019-02-02 23:10:20 -0500
commit24cd8bc11345395f1a0bb64d61e51e207d8b3ace (patch)
treeef8242cda1175c11dd4a565e1ba16cb531c11c47 /hw3
downloadcsci454-24cd8bc11345395f1a0bb64d61e51e207d8b3ace.tar.xz
csci454-24cd8bc11345395f1a0bb64d61e51e207d8b3ace.zip
Diffstat (limited to 'hw3')
-rw-r--r--hw3/.gitignore2
-rwxr-xr-xhw3/carpenter_adam_hw3.py171
-rwxr-xr-xhw3/mr.py78
3 files changed, 251 insertions, 0 deletions
diff --git a/hw3/.gitignore b/hw3/.gitignore
new file mode 100644
index 0000000..dbfb78d
--- /dev/null
+++ b/hw3/.gitignore
@@ -0,0 +1,2 @@
+*.log
+*.pyc
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)
diff --git a/hw3/mr.py b/hw3/mr.py
new file mode 100755
index 0000000..092d294
--- /dev/null
+++ b/hw3/mr.py
@@ -0,0 +1,78 @@
+import random
+
+_mrpt_num_trials = 5 # number of bases to test
+
+def is_probable_prime(n):
+ """
+ Miller-Rabin primality test.
+
+ A return value of False means n is certainly not prime. A return value of
+ True means n is very likely a prime.
+
+ >>> is_probable_prime(1)
+ Traceback (most recent call last):
+ ...
+ AssertionError
+ >>> is_probable_prime(2)
+ True
+ >>> is_probable_prime(3)
+ True
+ >>> is_probable_prime(4)
+ False
+ >>> is_probable_prime(5)
+ True
+ >>> is_probable_prime(123456789)
+ False
+
+ >>> primes_under_1000 = [i for i in range(2, 1000) if is_probable_prime(i)]
+ >>> len(primes_under_1000)
+ 168
+ >>> primes_under_1000[-10:]
+ [937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
+
+ >>> is_probable_prime(6438080068035544392301298549614926991513861075340134\
+3291807343952413826484237063006136971539473913409092293733259038472039\
+7133335969549256322620979036686633213903952966175107096769180017646161\
+851573147596390153)
+ True
+
+ >>> is_probable_prime(7438080068035544392301298549614926991513861075340134\
+3291807343952413826484237063006136971539473913409092293733259038472039\
+7133335969549256322620979036686633213903952966175107096769180017646161\
+851573147596390153)
+ False
+ """
+ assert n >= 2
+ # special case 2
+ if n == 2:
+ return True
+ # ensure n is odd
+ if n % 2 == 0:
+ return False
+ # write n-1 as 2**s * d
+ # repeatedly try to divide n-1 by 2
+ s = 0
+ d = n-1
+ while True:
+ quotient, remainder = divmod(d, 2)
+ if remainder == 1:
+ break
+ s += 1
+ d = quotient
+ assert(2**s * d == n-1)
+
+ # test the base a to see whether it is a witness for the compositeness of n
+ def try_composite(a):
+ if pow(a, d, n) == 1:
+ return False
+ for i in range(s):
+ if pow(a, 2**i * d, n) == n-1:
+ return False
+ return True # n is definitely composite
+
+ for i in range(_mrpt_num_trials):
+ a = random.randrange(2, n)
+ if try_composite(a):
+ return False
+
+ return True # no base tested showed n as composite