1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
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)
|
