How to change 1 bit from a string python?

Question

I generate a 64 bits random string using os.urandom(8). Next, I want to randomly change the value of one bit of the string getting the bit to change first x = random.getrandbits(6) and doing the XOR operation for that bit like this rand_string ^= 1 << x but this last operation gives me the following error: TypeError: unsupported operand type(s) for ^=: 'str' and 'long'

It's important to me to generate a random binary string because I want to cipher it cipher.encrypt(rand_string) and only takes plain-text for parameters. I don't use random.getrandbits(64) because it returns a long but it doesn't match the 64 bits size block that I want.

Besides, I want to measure the hamming distance between the strings (should give me 1 because I only changed one bit) but I'm afraid that the algorithm I found is not valid to me because it compares the characters representations instead of comparing bit-level:

def hamming_distance(s1, s2):
    # Return the Hamming distance between equal-length sequences
    if len(s1) != len(s2):
        raise ValueError("Undefined for sequences of unequal length")
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

So there are two questions:

How could I change randomly a bit of my binary string?

Is the above algorithm valid for my purposes? If it is not, how could I measure the Hamming Distance at bit-level?

First, these are two different questions. Second, I don’t have os.random on either python2 or python3, you seem to have a typo there. Third, are you on python2 or python3? (Fourth, you can test hamming_distance part yourself; simply create two string pairs: one pair where the difference is in the same character but two different bits, one pair where the difference is in two bits spread across two characters; observe the output) — Jonas Schäfer
– Jonas Schäfer, Commented Oct 16, 2016 at 14:23
@JonasWielicki yes, there was a typo, I mean os.urandom(). I'm on python2 and actually I can't test the hamming algorithm because I cant modify the string the way I want (change 1 bit). I know that it works for list items or character strings. For example, "abcd" and "abcc" gives hamming distance 1 but in binary, the distance is greater because c and d representations have more than one bit different. — ander_3035
– ander_3035, Commented Oct 16, 2016 at 16:50

Community · Accepted Answer · 2017-05-23 10:32:29Z

3

I assume there's a typo in your question. As Jonas Wielicki says, os.random doesn't exist; presumably you meant os.urandom. Yes, it's a Good Idea to use the system's random source for crypto work, but using os.urandom directly isn't so convenient. Fortunately, the random module provides an interface toos.urandom: the SystemRandom class.

Doing bit-twiddling of multi-byte byte objects is possible in Python, although it is somewhat fiddly (especially in Python 2). It's much easier to do this sort of thing with Python integers. You can certainly get 64 random bits using the getrandbits method, although of course it's possible that some of those leading bits are zero bits.

Here's some code that runs on Python 2 or Python 3 that generates a random 64 bit number, flips one of its bits, and then computes the Hamming distance between the original number & the number with the flipped bit (which is of course 1).

import random

# SystemRandom uses os.urandom() 
sysrandom = random.SystemRandom()

def bincount(n):
    return bin(n).count("1")

for _ in range(5):
    bits0 = sysrandom.getrandbits(64)
    print('bits0: {:016x}'.format(bits0))

    bitnum = sysrandom.randint(0, 64)
    print('bitnum: {}'.format(bitnum))

    bits1 = bits0 ^ (1 << bitnum)
    print('bits1: {:016x}'.format(bits1))

    hamming = bincount(bits0 ^ bits1)
    print('Hamming distance: {}\n'.format(hamming))

typical output

bits0: a508c77693a0e7d7
bitnum: 32
bits1: a508c77793a0e7d7
Hamming distance: 1

bits0: 9608e25db458a350
bitnum: 3
bits1: 9608e25db458a358
Hamming distance: 1

bits0: f485bd53af91e2dc
bitnum: 62
bits1: b485bd53af91e2dc
Hamming distance: 1

bits0: 18f6749bc260fcd1
bitnum: 17
bits1: 18f6749bc262fcd1
Hamming distance: 1

bits0: 51b35142c99b6814
bitnum: 54
bits1: 51f35142c99b6814
Hamming distance: 1

There are faster ways to compute the number of 1 bits in a Python integer, but bincount is reasonably fast (and faster than a Python implementation of the well-known algorithm by Kernighan); see fast way of counting non-zero bits in python for other methods.

If you need to convert bits0 to a bytes object that's easy in Python 3: just use the .to_bytes method, eg

bytes0 = bits0.to_bytes(8, 'big')

If you need to use Python 2, converting an integer to a string and converting a string to an integer takes a little more work. Here's a demo, using a modified version of the above code.

from __future__ import print_function
import random
from binascii import hexlify

# SystemRandom uses os.urandom() 
sysrandom = random.SystemRandom()

def bincount(n):
    return bin(n).count("1")

def int_to_bytes(n, size):
    result = []
    for _ in range(size):
        result.append(chr(n & 0xff))
        n >>= 8
    return ''.join(result[::-1])

def bytes_to_int(bs):
    n = 0
    for b in bs:
        n = (n << 8) | ord(b)
    return n

for _ in range(4):
    bits0 = sysrandom.getrandbits(64)
    print('bits0: {0:016x}'.format(bits0))

    bs = int_to_bytes(bits0, 8)
    print('bytes:', repr(bs))
    print('hex:  ', hexlify(bs))

    n = bytes_to_int(bs)
    print('int:   {0:016x}, {1}\n'.format(n, n == bits0))

typical output

bits0: 69831968a1b0aff8
bytes: 'i\x83\x19h\xa1\xb0\xaf\xf8'
hex:   69831968a1b0aff8
int:   69831968a1b0aff8, True

bits0: c2c77e02969d3ebc
bytes: '\xc2\xc7~\x02\x96\x9d>\xbc'
hex:   c2c77e02969d3ebc
int:   c2c77e02969d3ebc, True

bits0: e87c78eb3929a76f
bytes: '\xe8|x\xeb9)\xa7o'
hex:   e87c78eb3929a76f
int:   e87c78eb3929a76f, True

bits0: 0d5d796c986ba329
bytes: '\r]yl\x98k\xa3)'
hex:   0d5d796c986ba329
int:   0d5d796c986ba329, True

edited May 23, 2017 at 10:32

CommunityBot

11 silver badge

answered Oct 16, 2016 at 14:59

PM 2Ring

55.6k6 gold badges96 silver badges202 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

ander_3035 Over a year ago

Thank you for the answer, definitely it helped me a lot but I still having the problem with the crypto function call because it needs a plain-text argument (problem solved because although to_bytes() doesn't work on python2.7 I found a similar function -link) and returns a string that I should transform into a byte string in order to do the XOR but bytes1 = to_bytes(encryptedString, 8, 'big') gives me the following error TypeError: %x format: a number is required, not str

PM 2Ring Over a year ago

@arkan_18 I've added some Python 2 code to my answer that does int-> bytes and bytes->int conversion.

ander_3035 Over a year ago

@PM_2Ring thank you! Last question... what would mean if this line gives me false? n == bits0

PM 2Ring Over a year ago

@arkan_18 n == bits0 should never be false. I just put that in there to make it easier to see that bytes_to_int gives the correct result.

Niclas M · Accepted Answer · 2016-10-16 14:22:38Z

0

I do not see the point in getting random bits and than lshifting. A randInt should do just right. Also if you want to change a single bit, try to xor a character instead of the string. If that does not work ...=chr(ord(char)^x)

answered Oct 16, 2016 at 14:22

Niclas M

3123 silver badges9 bronze badges

1 Comment

ander_3035 Over a year ago

Well, It makes sense in the cryptographic field

Collectives™ on Stack Overflow

How to change 1 bit from a string python?

2 Answers 2

4 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related