Самый быстрый побитовый xor между двумя многобайтовыми переменными двоичных данных
Какой самый быстрый способ реализовать следующую логику:
def xor(data, key):
l = len(key)
buff = ""
for i in range(0, len(data)):
buff += chr(ord(data[i]) ^ ord(key[i % l]))
return buff
В моем случае ключ представляет собой 20-байтовый дайджест sha1, а данные - это двоичные данные длиной от 20 байтов до нескольких (1, 2, 3) мегабайт
ОБНОВИТЬ:
Хорошо, ребята. Вот реализация в 3,5 раза быстрее, которая разделяет данные и ключ на куски по 4, 2 или 1 байт (в моем случае, чаще всего это 4-байтовое целое число):
def xor(data, key):
index = len(data) % 4
size = (4, 1, 2, 1)[index]
type = ('L', 'B', 'H', 'B')[index]
key_len = len(key)/size
data_len = len(data)/size
key_fmt = "<" + str(key_len) + type;
data_fmt = "<" + str(data_len) + type;
key_list = struct.unpack(key_fmt, key)
data_list = struct.unpack(data_fmt, data)
result = []
for i in range(data_len):
result.append (key_list[i % key_len] ^ data_list[i])
return struct.pack(data_fmt, *result)
Использует много памяти, но в моем случае это не имеет большого значения.
Есть идеи, как увеличить скорость еще в несколько раз?:-)
ЗАКЛЮЧИТЕЛЬНОЕ ОБНОВЛЕНИЕ:
Хорошо, хорошо... Numpy сделал свою работу. Это просто чертовски быстро
def xor(data, key):
import numpy, math
# key multiplication in order to match the data length
key = (key*int(math.ceil(float(len(data))/float(len(key)))))[:len(data)]
# Select the type size in bytes
for i in (8,4,2,1):
if not len(data) % i: break
if i == 8: dt = numpy.dtype('<Q8');
elif i == 4: dt = numpy.dtype('<L4');
elif i == 2: dt = numpy.dtype('<H2');
else: dt = numpy.dtype('B');
return numpy.bitwise_xor(numpy.fromstring(key, dtype=dt), numpy.fromstring(data, dtype=dt)).tostring()
Первоначальная реализация потребовала 8 минут 50 секунд для обработки гигабайта, вторая - около 2 минут 30 секунд, а последняя - всего 0 минут 10 секунд.
Спасибо всем, кто внес идеи и код. Вы отличные ребята!
6 ответов
Не испытано
Не знаю, быстрее ли
Предположим, что len(mystring) кратно 4
def xor(hash,mystring):
s = struct.Struct("<L")
v1 = memoryview(hash)
tab1 = []
for i in range(5):
tab1.append(s.unpack_from(v1,i*4)
v2 = memoryview(mystring)
tab2=[]
for i in range(len(mystring)/4):
tab2.append(s.unpack_from(v1,i*4))
tab3 = []
try:
for i in range(len(mystring)/20):
for j in range(5):
tab3.append(s.pack(tab1[j]^tab2[5*i+j]))
expect IndexError:
pass
return "".join(tab3)
Отказ от ответственности: Как говорили другие авторы, это действительно плохой способ шифрования файлов. Эта статья демонстрирует, как полностью изменить этот вид запутывания.
во-первых, простой алгоритм XOR:
def xor(a,b,_xor8k=lambda a,b:struct.pack("!1000Q",*map(operator.xor,
struct.unpack("!1000Q",a),
struct.unpack("!1000Q",b)))
):
if len(a)<=8000:
s="!%iQ%iB"%divmod(len(a),8)
return struct.pack(s,*map(operator.xor,
struct.unpack(s,a),
struct.unpack(s,b)))
a=bytearray(a)
for i in range(8000,len(a),8000):
a[i-8000:i]=_xor8k(
a[i-8000:i],
b[i-8000:i])
a[i:]=xor(a[i:],b[i:])
return str(a)
во-вторых, алгоритм обтекания xor:
def xor_wrap(data,key,_struct8k=struct.Struct("!1000Q")):
l=len(key)
if len(data)>=8000:
keyrpt=key*((7999+2*l)//l)#this buffer is accessed with whatever offset is required for a given 8k block
#this expression should create at most 1 more copy of the key than is needed
data=bytearray(data)
offset=-8000#initial offset, set to zero on first loop iteration
modulo=0#offset used to access the repeated key
for offset in range(0,len(data)-7999,8000):
_struct8k.pack_into(data,offset,*map(operator.xor,
_struct8k.unpack_from(data,offset),
_struct8k.unpack_from(keyrpt,modulo)))
modulo+=8000;modulo%=l
offset+=8000
else:offset=0;keyrpt=key*(len(data)//l+1)#simple calculation guaranteed to be enough
rest=len(data)-offset
srest=struct.Struct("!%iQ%iB"%divmod(len(data)-offset,8))
srest.pack_into(data,offset,*map(operator.xor,
srest.unpack_from(data,offset),
srest.unpack_from(keyrpt,modulo)))
return data
Этот код должен работать в Python 2.6+, включая Py3k.
from binascii import hexlify as _hexlify
from binascii import unhexlify as _unhexlify
def packl(lnum, padmultiple=0):
"""Packs the lnum (which must be convertable to a long) into a
byte string 0 padded to a multiple of padmultiple bytes in size. 0
means no padding whatsoever, so that packing 0 result in an empty
string. The resulting byte string is the big-endian two's
complement representation of the passed in long."""
if lnum == 0:
return b'\0' * padmultiple
elif lnum < 0:
raise ValueError("Can only convert non-negative numbers.")
s = hex(lnum)[2:]
s = s.rstrip('L')
if len(s) & 1:
s = '0' + s
s = _unhexlify(s)
if (padmultiple != 1) and (padmultiple != 0):
filled_so_far = len(s) % padmultiple
if filled_so_far != 0:
s = b'\0' * (padmultiple - filled_so_far) + s
return s
def unpackl(bytestr):
"""Treats a byte string as a sequence of base 256 digits
representing an unsigned integer in big-endian format and converts
that representation into a Python integer."""
return int(_hexlify(bytestr), 16) if len(bytestr) > 0 else 0
def xor(data, key):
dlen = len(data)
klen = len(key)
if dlen > klen:
key = key * ((dlen + klen - 1) // klen)
key = key[:dlen]
result = packl(unpackl(data) ^ unpackl(key))
if len(result) < dlen:
result = b'\0' * (dlen - len(result)) + result
return result
Это также будет работать в Python 2.7 и 3.x. Его преимущество в том, что он намного проще, чем предыдущий, и делает примерно одно и то же за примерно одинаковое время:
from binascii import hexlify as _hexlify
from binascii import unhexlify as _unhexlify
def xor(data, key):
dlen = len(data)
klen = len(key)
if dlen > klen:
key = key * ((dlen + klen - 1) // klen)
key = key[:dlen]
data = int(_hexlify(data), 16)
key = int(_hexlify(key), 16)
result = (data ^ key) | (1 << (dlen * 8 + 7))
# Python 2.6/2.7 only lines (comment out in Python 3.x)
result = memoryview(hex(result))
result = (result[4:-1] if result[-1] == 'L' else result[4:])
# Python 3.x line
#result = memoryview(hex(result).encode('ascii'))[4:]
result = _unhexlify(result)
return result
Если len(data) большой, вы можете увидеть значительное улучшение от xrange, На самом деле, вы можете полностью заменить функцию диапазона на enumerate, Вы также можете воспользоваться списком вместо добавления в строку.
def xor(data, key):
l = len(key)
buff = []
for idx, val in enumerate(data):
buff.append(chr(ord(val) ^ ord(key[idx % l]))
return ''.join(buff)
Я не рассчитал это, но изо всех сил я ожидал бы, что это будет немного быстрее для больших объемов данных. Убедитесь, что вы измеряете каждое изменение.
Если профилирование предполагает, что вызов ord() на самом деле занимает время, вы можете запустить его на всех значениях в key заранее, чтобы сохранить вызов в цикле.
Вы также можете превратить цикл for в простое понимание списка, но это отрицательно скажется на удобочитаемости. В любом случае, попробуйте и посмотрите, будет ли это быстрее.
Следуя моему комментарию в первом сообщении, вы можете довольно быстро обрабатывать большие файлы, если будете придерживаться numpy для заполнения клавиш и побитового XOR, например:
import numpy as np
# ...
def xor(key, data):
data = np.fromstring(data, dtype=np.byte)
key = np.fromstring(key, dtype=np.byte)
# Pad the key to match the data length
key = np.pad(key, (0, len(data) - len(key)), 'wrap')
return np.bitwise_xor(key, data)
Вот версия, в которой используются только встроенные и стандартные модули Python, которые выглядят очень быстрыми, хотя я не сравнивал ее с вашей простой версией. Он использует несколько оптимизированных функций преобразования из Python Cryptography Toolkit, как указано.
# Part of the Python Cryptography Toolkit
# found here:
# http://www.google.com/codesearch/p?hl=en#Y_gnTlD6ECg/trunk/src/gdata/Crypto/Util/number.py&q=lang:python%20%22def%20long_to_bytes%22&sa=N&cd=1&ct=rc
# Improved conversion functions contributed by Barry Warsaw, after
# careful benchmarking
import struct
def long_to_bytes(n, blocksize=0):
"""long_to_bytes(n:long, blocksize:int) : string
Convert a long integer to a byte string.
If optional blocksize is given and greater than zero, pad the front of the
byte string with binary zeros so that the length is a multiple of
blocksize.
"""
# after much testing, this algorithm was deemed to be the fastest
s = ''
n = long(n)
pack = struct.pack
while n > 0:
s = pack('>I', n & 0xffffffffL) + s
n = n >> 32
# strip off leading zeros
for i in range(len(s)):
if s[i] != '\000':
break
else:
# only happens when n == 0
s = '\000'
i = 0
s = s[i:]
# add back some pad bytes. this could be done more efficiently w.r.t. the
# de-padding being done above, but sigh...
if blocksize > 0 and len(s) % blocksize:
s = (blocksize - len(s) % blocksize) * '\000' + s
return s
def bytes_to_long(s):
"""bytes_to_long(string) : long
Convert a byte string to a long integer.
This is (essentially) the inverse of long_to_bytes().
"""
acc = 0L
unpack = struct.unpack
length = len(s)
if length % 4:
extra = (4 - length % 4)
s = '\000' * extra + s
length = length + extra
for i in range(0, length, 4):
acc = (acc << 32) + unpack('>I', s[i:i+4])[0]
return acc
# original code in SO question
def xor_orig(data, key):
l = len(key)
buff = ""
for i in range(0, len(data)):
buff += chr(ord(data[i]) ^ ord(key[i % l]))
return buff
# faster pure python version
def xor_new(data, key):
import math
# key multiplication in order to match the data length
key = (key*int( math.ceil(float(len(data))/float(len(key)))))[:len(data)]
# convert key and data to long integers
key_as_long = bytes_to_long(key)
data_as_long = bytes_to_long(data)
# xor the numbers together and convert the result back to a byte string
return long_to_bytes(data_as_long ^ key_as_long)
if __name__=='__main__':
import random
import sha
TEST_DATA_LEN = 100000
data = ''.join(chr(random.randint(0, 255)) for i in xrange(TEST_DATA_LEN))
key = sha.new(data).digest()
assert xor_new(data, key) == xor_orig(data, key)
print 'done'
То, что у вас есть, уже так быстро, как вы можете получить в Python.
Если вам действительно нужно быстрее, внедрите это в C.