8000
Skip to content

Commit 5fda658

Browse files
author
Mathias Svensson
authored
Expose the BitPolynom (#755)
1 parent 9185437 commit 5fda658

File tree

2 files changed

+93
-11
lines changed

2 files changed

+93
-11
lines changed

‎pwn/toplevel.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,6 +51,7 @@
5151
from pwnlib.util import net
5252
from pwnlib.util import proc
5353
from pwnlib.util import safeeval
54+
from pwnlib.util.crc import BitPolynom
5455
from pwnlib.util.cyclic import *
5556
from pwnlib.util.fiddling import *
5657
from pwnlib.util.getdents import *

‎pwnlib/util/crc/__init__.py‎

Lines changed: 92 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,10 @@
11
"""Module for calculating CRC-sums.
22
3-
Contains all crc implementations know on the interwebz. For most implementations it
4-
contains only the core crc algorithm and not e.g. padding schemes.
3+
Contains all crc implementations know on the interwebz. For most implementations
4+
it contains only the core crc algorithm and not e.g. padding schemes.
55
66
It is horribly slow, as implements a naive algorithm working direclty on
7-
bit polynomials.
7+
bit polynomials. This class is exposed as `BitPolynom`.
88
99
The current algorithm is super-linear and takes about 4 seconds to calculate
1010
the crc32-sum of ``'A'*40000``.
@@ -18,15 +18,70 @@
1818
from . import known
1919
from .. import fiddling
2020
from .. import packing
21+
from .. import safeeval
2122

2223

2324
class BitPolynom(object):
25+
"""Class for representing GF(2)[X], i.e. the field of polynomials over
26+
GF(2).
27+
28+
In practice the polynomials are represented as numbers such that `x**n`
29+
corresponds to `1 << n`. In this representation calculations are easy: Just
30+
do everything as normal, but forget about everything the carries.
31+
32+
Addition becomes xor and multiplication becomes carry-less multiplication.
33+
34+
Examples:
35+
36+
>>> p1 = BitPolynom("x**3 + x + 1")
37+
>>> p1
38+
BitPolynom('x**3 + x + 1')
39+
>>> int(p1)
40+
11
41+
>>> p1 == BitPolynom(11)
42+
True
43+
>>> p2 = BitPolynom("x**2 + x + 1")
44+
>>> p1 + p2
45+
BitPolynom('x**3 + x**2')
46+
>>> p1 * p2
47+
BitPolynom('x**5 + x**4 + 1')
48+
>>> p1 / p2
49+
BitPolynom('x + 1')
50+
>>> p1 % p2
51+
BitPolynom('x')
52+
>>> d, r = divmod(p1, p2)
53+
>>> d * p2 + r == p1
54+
True
55+
>>> BitPolynom(-1)
56+
Traceback (most recent call last):
57+
...
58+
ValueError: Polynomials cannot be negative: -1
59+
>>> BitPolynom('y')
60+
Traceback (most recent call last):
61+
...
62+
ValueError: Not a valid polynomial: y
63+
"""
64+
65+
2466
def __init__(self, n):
25-
if not isinstance(n, (int, long)):
26-
raise TypeError("Polynomial must be called with an integer or a list")
27-
if n < 0:
28-
raise ValueError("Polynomials cannot be negative: %d" % n)
29-
self.n = n
67+
if isinstance(n, (str, unicode)):
68+
self.n = 0
69+
x = BitPolynom(2)
70+
try:
71+
for p in n.split('+'):
72+
k = safeeval.values(p.strip(), {'x': x, 'X': x})
73+
assert isinstance(k, (BitPolynom, int, long))
74+
assert k >= 0
75+
self.n ^= int(k)
76+
except (ValueError, NameError, AssertionError):
77+
raise ValueError("Not a valid polynomial: %s" % n)
78+
elif isinstance(n, (int, long)):
79+
if n >= 0:
80+
self.n = n
81+
else:
82+
raise ValueError("Polynomials cannot be negative: %d" % n)
83+
else:
84+
raise TypeError("Polynomial must be called with a string or integer")
3085

3186
def __int__(self):
3287
return self.n
@@ -126,25 +181,51 @@ def __rshift__(self, other):
126181
def __rrshift__(self, other):
127182
return BitPolynom(int(other) >> int(self))
128183

184+
def __pow__(self, other):
185+
r = BitPolynom(1)
186+
for _ in range(other):
187+
r *= self
188+
return r
189+
129190
def degree(self):
191+
"""Returns the degree of the polynomial.
192+
193+
Examples:
194+
195+
>>> BitPolynom(0).degree()
196+
0
197+
>>> BitPolynom(1).degree()
198+
0
199+
>>> BitPolynom(2).degree()
200+
1
201+
>>> BitPolynom(7).degree()
202+
2
203+
>>> BitPolynom((1 << 10) - 1).degree()
204+
9
205+
>>> BitPolynom(1 << 10).degree()
206+
10
207+
"""
130208
return max(0, int(self).bit_length()-1)
131209

132210
def __repr__(self):
133211
if int(self) == 0:
134212
return '0'
135213

136214
out = []
137-
for n in range(self.degree(), 0, -1):
215+
for n in range(self.degree(), 1, -1):
138216
if int(self) & (1 << n):
139217
out.append("x**%d" % n)
218+
if int(self) & 2:
219+
out.append("x")
140220
if int(self) & 1:
141221
out.append("1")
142-
return ' + '.join(out)
222+
return 'BitPolynom(%r)' % ' + '.join(out)
143223

144224
class Module(types.ModuleType):
145225
def __init__(self):
146226
super(Module, self).__init__(__name__)
147227
self._cached_crcs = None
228+
self.BitPolynom = BitPolynom
148229
self.__dict__.update({
149230
'__file__' : __file__,
150231
'__package__' : __package__,
@@ -154,7 +235,7 @@ def __getattr__(self, attr):
154235
crcs = known.all_crcs
155236

156237
if attr == '__all__':
157-
return ['generic_crc', 'cksum', 'find_crc_function'] + sorted(crcs.keys())
238+
return ['BitPolynom', 'generic_crc', 'cksum', 'find_crc_function'] + sorted(crcs.keys())
158239

159240
info = crcs.get(attr, None)
160241
if not info:

0 commit comments

Comments
 (0)
0