forked from baiger/DFT-Attack
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bma.py
executable file
·52 lines (41 loc) · 1.45 KB
/
bma.py
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
#!/usr/bin/env sage
from sage.all import *
# bma should never consider whether the sequence is periodic
# which instead should be handled by the caller of this funciton
def bma(sequence, TheFiniteField = GF(2)):
ThePolynomialRing = TheFiniteField['X']
s = sequence
"using the notations in 'Shift-register synthesis and BCH decoding' by Massey"
C = ThePolynomialRing(1)
B = ThePolynomialRing(1)
b = TheFiniteField(1)
m = 1 # replacing the orignial notation, x
L = 0
for N in range(len(s)):
d = TheFiniteField(s[N])
for l in range(1, len(C.list())): # range(1, L + 1) will cause out-of-index error
d += C.list()[l] * s[N - l]
if d == 0:
m += 1
else:
if 2 * L > N:
C -= d / b * B.shift(m)
m += 1
else:
T = C
C -= d / b * B.shift(m)
L = N + 1 - L
B = T
b = d
m = 1
C = C.reverse()
# must be reversed in this notation
return C.shift(L - C.degree())
# because reverse() cannot guarantee the overall degree
# so this is the very reason why the original BMA always output $L$!!!
if __name__ == '__main__':
# seq = [1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0]
seq = [0, 0, 0, 1, 0, 0, 1, 1]
pol = bma(seq)
print 'The input sequence is', seq
print 'Its characteristic polynomial is', pol