3

Please help me to understand BBS algorithm. I did this implementation:

class EmptySequenseError(Exception):                                  
    pass                                                              


class BlumBlumShub(object):                                           
    def __init__(self, length):                                       
        self.length = length                                          
        self.primes = e(1000)  # Primes obtained by my own Sieve of Eratosthenes implementation.                                                                            

    def get_primes(self):                                             
        out_primes = []                                               
        while len(out_primes) < 2:                                    
            curr_prime = self.primes.pop()          
            if curr_prime % 4 == 3:                                   
                out_primes.append(curr_prime)                         
        return out_primes                                             

    def set_random_sequence(self):                                    
        p, q = self.get_primes()                                      
        m = p * q                                                     
        self.random_sequence = [((x+1)**2)%m for x in range(self.length)]

    def get_random_sequence(self):                                    
        if self.random_sequence:                                      
           return self.random_sequence                               
        raise EmptySequenseError("Set random sequence before get it!")

And I have several questions. At first I do not want to use random library, it is too naive. My sequence is increasing, it is not absolutely random. How to prevent increasing in returned sequence? And I do not understand this part of the algorithm description:

At each step of the algorithm, some output is derived from xn+1; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1.

Please explain to me what does it mean?

Edit summary:

  • The algorithm is corrected.
  • Quote substituted to en.wikipedia quote.

3 Answers 3

5
    for x in range(self.length):                                  
        self.random_sequence.append((x ** 2) % m) 

Just generates [(x ** 2) % m for x in range(self.length)], which is roughly xn+1 = n2 mod M.

The algorithm is supposed to be: xn+1 = xn2 mod M

Do you see where your version is different?


As for the quote - you don't say where it's from, but Wikipedia has:

At each step of the algorithm, some output is derived from xn+1; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1.

It means that xn+1 is the seed for the next iteration, but not the pseudo-random number returned. Instead, the return value is derived from xn+1 by counting its bit parity (this yields either 0 or 1 each iteration), or by taking only some number of top bits.

2
  • I still can't get, what should I return? Is parity bit means en.wikipedia.org/wiki/Parity_bit ? Should I return ((x+1)**2) % m or something else? Or what the bitwise operation should be done?
    – I159
    Jun 14, 2013 at 20:01
  • 1
    bit parity the even/odd quality of the number of 1's in the bit string. in python, that's basically: parity_of_x = bin(x).count(1) % 2 Jun 14, 2013 at 20:56
3

Blum Blum Shub is described in Chapter Five of the Handbook of Applied Cryptography, Section 5.5.2. There is a lot of helpful stuff about random number generation in that chapter.

0
2

I would rather formalize my understanding as an answer.

class BlumBlumShub(object):                                             
    def __init__(self, length):                                         
        self.length = length                                            
        self.primes = e(1000)                                           

    def gen_primes(self):                                               
        out_primes = []                                                 
        while len(out_primes) < 2:                                      
            curr_prime = self.primes[random.randrange(len(self.primes))]
            if curr_prime % 4 == 3:                                     
                out_primes.append(curr_prime)                           
        return out_primes                                               

    def random_generator(self):                                         
        x = random.randrange(1000000)                                   
        while self.length:                                              
            x += 1                                                      
            p, q = self.gen_primes()                                    
            m = p * q                                                   
            z = (x**2) % m                                              
            self.length -= 1                                            
            yield str(bin(z).count('1') % 2)                            

    def get_random_bits(self):                                          
        return ''.join(self.random_generator())                         
  • BBS is pseudorandom bit generator, it must return random bits, not integers.
  • Return value is just parity bit of result xn+12 % m operation.

If I wrongly understood something, please explain my mistakes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.