#!/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)
