3

请帮我理解BBS算法。我做了这个实现：

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!")

我有几个问题。起初我不想使用random库，这太天真了。我的序列在增加，它不是绝对随机的。如何防止返回序列增加？我不明白这部分算法描述：

在算法的每一步，一些输出来自x n+1；输出通常是 x n+1 的位奇偶校验或x n + 1的一个或多个最低有效位。

请给我解释一下这是什么意思？

编辑总结：

  • 算法被修正。
  • 引用替换为 en.wikipedia 引用。
4

3 回答 3

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

只需生成[(x ** 2) % m for x in range(self.length)]，大致为 x n+1 = n 2 mod M。

该算法应该是： x n+1 = x n 2 mod M

你看到你的版本有什么不同吗？

至于报价 - 你没有说它来自哪里，但维基百科有：

在算法的每一步，一些输出来自x n+1；输出通常是 x n+1 的位奇偶校验或x n + 1的一个或多个最低有效位。

这意味着x n+1是下一次迭代的种子，而不是返回的伪随机数。相反，返回值是从 x n+1通过计算其位奇偶性（每次迭代产生 0 或 1）或仅获取一些最高位而得出的。

于 2013-06-14T11:07:21.653 回答
3

Blum Blum Shub 在应用密码学手册的第五章第 5.5.2 节中进行了描述。在那一章中有很多关于随机数生成的有用的东西。

于 2013-06-15T11:41:20.367 回答
2

我宁愿将我的理解形式化为答案。

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 是伪随机位生成器，它必须返回随机位，而不是整数。
  • 返回值只是结果 x n+1 2 % m 操作的奇偶校验位。

如果我理解错误，请解释我的错误。

于 2013-06-16T15:10:23.607 回答