Bottleneck: easy obscurity "encryption" via xor

Discussion in 'Python' started by Tino Lange, Jul 29, 2003.

  1. Tino Lange

    Tino Lange Guest

    Hi!

    I identified a bottleneck in my programs.

    I just want to "encrypt" data by easy xoring. Ok - that's no
    encryption at all - I know. But it's hardly readable - and that's
    enough :) Just some quick obscurity.

    It turns out not to be quick at all. I really didn't expect this to be
    a bottleneck, but it takes quite some time.

    Here's the code:

    >$ cat python/EasyCrypt.py
    >#! /usr/bin/env python
    >import operator
    >def xorcrypt(str, salt = 255):
    > if salt > 255:
    > raise "Invalid salt! Must be < 255!"
    > return reduce(lambda x,y: operator.add(x, chr(y)), map(lambda char, _salt = salt: operator.xor(ord(char), _salt), str), "")


    xor'ing medium sized-files takes long time. For example a 360
    kByte-File takes:

    >$ time ./just_crypt.py Userdatan/ScanImage01.jpg > bert
    >real 1m52.138s
    >user 0m40.320s
    >sys 1m6.030s


    on my 2.66 GHz P4 machine!

    Hmmm, do you have some better implementation ideas? Some optimizing
    tricks? (Besides coding in C to avoid immutable string problems)
    I already took the operator module to speed up a bit - but it seems
    that's not enough...

    Thanks

    Tino
    Tino Lange, Jul 29, 2003
    #1
    1. Advertising

  2. Tino Lange wrote:

    > It turns out not to be quick at all. I really didn't expect this to be
    > a bottleneck, but it takes quite some time.


    >> return reduce(lambda x,y: operator.add(x, chr(y)), map(lambda char, _salt = salt: operator.xor(ord(char), _salt), str), "")


    Running this on a large string builds up a huge list of ints,
    that you are converting to chars and then concatenating them
    together using +... this creates a HUGE number of temporary
    string objects.
    The usual pattern of fast string joining is:

    ''.join(list-of-fragments)

    So first try:

    return ''.join(map(lambda char, _salt = salt: chr(operator.xor(ord(char), _salt)), string))

    This runs MUCH faster already.

    But the version I'd recommend is:

    def xorcrypt(string, salt = 255):
    if salt <0 or salt> 255:
    raise "Invalid salt! Must be 0<=salt<=255!"
    return ''.join( [ chr(ord(c) ^ salt) for c in string ] )

    because
    1) salt must be 0..255 not only <=255
    2) forget about map & lambda, use a list comprehension.

    That implementation runs about 20 times faster than your original one;
    0.11 seconds for 100 Kb source data. (python 2.3)

    HTH,
    --Irmen de Jong
    Irmen de Jong, Jul 29, 2003
    #2
    1. Advertising

  3. On Wed, 30 Jul 2003 00:25:59 +0200, Irmen de Jong <> wrote:

    >Tino Lange wrote:
    >
    >> It turns out not to be quick at all. I really didn't expect this to be
    >> a bottleneck, but it takes quite some time.

    >
    >>> return reduce(lambda x,y: operator.add(x, chr(y)), map(lambda char, _salt = salt: operator.xor(ord(char), _salt), str), "")

    >
    >Running this on a large string builds up a huge list of ints,
    >that you are converting to chars and then concatenating them
    >together using +... this creates a HUGE number of temporary
    >string objects.
    >The usual pattern of fast string joining is:
    >
    >''.join(list-of-fragments)
    >
    >So first try:
    >
    > return ''.join(map(lambda char, _salt = salt: chr(operator.xor(ord(char), _salt)), string))
    >
    >This runs MUCH faster already.
    >
    >But the version I'd recommend is:
    >
    >def xorcrypt(string, salt = 255):

    def xorcrypt(s, salt = 255): # better name choice, even though string module may not be used
    > if salt <0 or salt> 255:
    > raise "Invalid salt! Must be 0<=salt<=255!"
    > return ''.join( [ chr(ord(c) ^ salt) for c in string ] )

    return s.translate(''.join([chr(ic^salt) for ic in xrange(256)]))
    >
    >because
    >1) salt must be 0..255 not only <=255
    >2) forget about map & lambda, use a list comprehension.

    forget about list comprehension, use str.translate ;-)
    >
    >That implementation runs about 20 times faster than your original one;
    >0.11 seconds for 100 Kb source data. (python 2.3)
    >

    s.translate ought to a good deal faster yet ;-)

    Regards,
    Bengt Richter
    Bengt Richter, Jul 30, 2003
    #3
  4. Tino Lange

    Paul Rubin Guest

    Tino Lange <> writes:
    > Hmmm, do you have some better implementation ideas? Some optimizing
    > tricks? (Besides coding in C to avoid immutable string problems)
    > I already took the operator module to speed up a bit - but it seems
    > that's not enough...


    Use the array module. See <http://www.nightsong.com/phr/crypto/p2.py>.
    Paul Rubin, Jul 30, 2003
    #4
  5. Tino Lange

    Oren Tirosh Guest

    On Wed, Jul 30, 2003 at 12:03:06AM +0200, Tino Lange wrote:
    > Hi!
    >
    > I identified a bottleneck in my programs.
    >
    > I just want to "encrypt" data by easy xoring. Ok - that's no
    > encryption at all - I know. But it's hardly readable - and that's
    > enough :) Just some quick obscurity.
    >
    > It turns out not to be quick at all. I really didn't expect this to be
    > a bottleneck, but it takes quite some time.


    If you want higher performance always try to use things that operate
    on larger chunks. When you do things byte-by-byte you start to notice the
    fact that Python is really an interpreter.

    As noted by Bengt Richter xoring with a constant value can be done by
    str.translate. It doesn't work for variable values, though.

    This code does around 250kb/second on a Pentium 800. XORing is done 32
    bits at a time. Conversion to and from character strings is done in even
    larger chunks using the array module instead of using ord() and chr().

    Oren


    from __future__ import generators

    import sha

    def xor_stream_to_arrays(fin, seed, hashfunc=sha):
    """ fin is a file-like object.
    yields arrays that may be written to a stream """
    from array import array

    h = hashfunc.new(seed)
    maskchunk = h.digest()
    chunksize = len(maskchunk)

    while True:
    datachunk = fin.read(chunksize)
    if len(datachunk) < chunksize:
    break
    yield array('l', [x^y for (x,y) in zip(
    array('l', maskchunk),
    array('l', datachunk))])

    h.update('x')
    maskchunk = h.digest()

    maskchunk = maskchunk[:len(datachunk)] # trim to length of remainder

    # do the rest by bytes:
    yield array('b', [x^y for (x,y) in zip(
    array('b', maskchunk),
    array('b', datachunk))])

    def xor_stream_to_stream(fin, fout, seed):
    """ fin, fout are file-like objects """
    for a in xor_stream_to_arrays(fin, seed):
    fout.write(buffer(a))

    def xor_string_to_string(s, seed):
    """ gets a string, returns a string """
    from cStringIO import StringIO
    fin = StringIO(s)
    fout = StringIO()
    xor_stream_to_stream(fin, fout, seed)
    return fout.getvalue()
    Oren Tirosh, Jul 30, 2003
    #5
  6. Tino Lange

    Paul Rubin Guest

    Tino Lange <> writes:
    > And it seems that Bengt's reciepe is the fastest. For very small strings
    > (<255 chars) the method irmen2 should be the best choice - it doesn' have
    > to pre-create the translation-table and does everything on-the-fly.


    You should be able to use the array module to do the xor's 4 bytes at
    a time and get a speedup over the 1-byte version. The
    string.translate version is the fastest, of course, but depends on
    using the same translation table for every char in the string.

    If you want to encrypt in python, try the p2.py that I posted; it's
    been carefully designed with good algorithms and fairly well optimized
    and should give much better security than some roll-your-own method.
    Paul Rubin, Jul 30, 2003
    #6
  7. Tino Lange

    Bob Gailer Guest

    At 12:25 AM 7/30/2003 +0200, Irmen de Jong wrote:

    >Tino Lange wrote:
    >
    >>It turns out not to be quick at all. I really didn't expect this to be
    >>a bottleneck, but it takes quite some time.

    >
    >>> return reduce(lambda x,y: operator.add(x, chr(y)), map(lambda char,
    >>> _salt = salt: operator.xor(ord(char), _salt), str), "")

    >
    >Running this on a large string builds up a huge list of ints,
    >that you are converting to chars and then concatenating them
    >together using +... this creates a HUGE number of temporary
    >string objects.
    >The usual pattern of fast string joining is:
    >
    >''.join(list-of-fragments)
    >
    >So first try:
    >
    > return ''.join(map(lambda char, _salt = salt:
    > chr(operator.xor(ord(char), _salt)), string))
    >
    >This runs MUCH faster already.
    >
    >But the version I'd recommend is:
    >
    >def xorcrypt(string, salt = 255):
    > if salt <0 or salt> 255:
    > raise "Invalid salt! Must be 0<=salt<=255!"
    > return ''.join( [ chr(ord(c) ^ salt) for c in string ] )


    Great minds think alike? I came up with (independently!):
    return ''.join([chr(ord(char) ^ salt) for char in txt])
    I also favor comprehension because it is more readable.

    >because
    >1) salt must be 0..255 not only <=255
    >2) forget about map & lambda, use a list comprehension.
    >
    >That implementation runs about 20 times faster than your original one;
    >0.11 seconds for 100 Kb source data. (python 2.3)
    >
    >HTH,
    >--Irmen de Jong
    >
    >
    >--
    >http://mail.python.org/mailman/listinfo/python-list
    >
    >
    >
    >
    >---
    >Incoming mail is certified Virus Free.
    >Checked by AVG anti-virus system (http://www.grisoft.com).
    >Version: 6.0.500 / Virus Database: 298 - Release Date: 7/10/2003


    Bob Gailer

    303 442 2625


    ---
    Outgoing mail is certified Virus Free.
    Checked by AVG anti-virus system (http://www.grisoft.com).
    Version: 6.0.500 / Virus Database: 298 - Release Date: 7/10/2003
    Bob Gailer, Jul 30, 2003
    #7
  8. Tino Lange

    Paul Rubin Guest

    Tino Lange <> writes:
    > Thanks! But BTW your "time-bomb" and your comments in the file tell me that
    > this script must not be used anymore...


    Oh yeah. The code is ok, I just want to rename the function and
    release it as p3.py. I haven't gotten around to that because nobody
    seems to be using it. I keep forgetting. Anyway I'd appreciate it if
    you don't distribute p2.py to other people with the time bomb removed,
    but feel free to remove it for your own use.
    Paul Rubin, Jul 31, 2003
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Elaine Jackson

    terminological obscurity

    Elaine Jackson, May 21, 2004, in forum: Python
    Replies:
    3
    Views:
    291
  2. Michael Chermside

    terminological obscurity

    Michael Chermside, May 21, 2004, in forum: Python
    Replies:
    84
    Views:
    1,600
    Donn Cave
    Jun 2, 2004
  3. John Williams
    Replies:
    11
    Views:
    673
    Jerry Coffin
    Mar 13, 2007
  4. joe jacob

    XOR encryption

    joe jacob, Jan 18, 2008, in forum: Python
    Replies:
    2
    Views:
    305
    joe jacob
    Jan 18, 2008
  5. mistral

    javascript encryption XOR, etc

    mistral, Jul 7, 2006, in forum: Javascript
    Replies:
    2
    Views:
    117
    mistral
    Jul 7, 2006
Loading...

Share This Page