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?

Answer 1

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

Answer 2

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)