Talk:Blum Blum Shub

From Wikipedia, the free encyclopedia

You have new messages (last change).

Contents

[edit] Good example of particular parameters?

Tried to get a feeling what BBS is producing, and how fast it will be on 32bit CPU.

I tried these params: M = 0xffffffe9 = 4294967273 = 10847 * 395959; p = 10847, phi(p-1) = 4480 = 2^7 * 5 * 7; q = 395959, phi(q-1) = 131984 = 2^4 * 73 * 113; gcd(phi(p-1),phi(q-1)) = 2^4 - not "big", right?

seed is, of course, shouldn't be 0 or 1.

Yet, starting with seed 3, I get

9 81 6561 43046721 3793632897 2038349057 2324068865 120648705 1995565057 2418266113 2840043521 1989099521 2099150849 977076225 1954152449 3908304897 3521642497 2748317697 1201668097 2403336193 511705089 1023410177 2046820353 4093640705 3892314113 3489660929 2684354561 1073741825 2147483649 1 1 ...

Seeds 5 and 7 perform similarly... Seems like there are some additional requiremens on params and/or seeds? In case I made silly mistake, code is:

#include <stdio.h>
#define NEXT(x) ((x)*(x)) % 0xffffffe9
int main() {
       unsigned i = 7;
       while(1) {
               i = NEXT(i);
               printf("%u\n", i);
       }
       return 0;
}

Googled some BBS related info: http://www.ciphersbyritter.com/NEWS2/TESTSBBS.HTM

Your M is too large for 32-bit ints. (x)*(x) will cause integer overflow when x > 0xffff. Your code seems to work fine when using 64-bit ints.Ufretin 07:54, 10 January 2007 (UTC)

[edit] Parity

To anonymous editor on 64.151.29.184: I more or less reverted your change, as I found your explanation of the LSB (least significant bit) not very clear. Also, I don't know what you mean with the expression "x+1n+1". -- Jitse Niesen 12:06, 4 Feb 2004 (UTC)

Your cleanup unfortunately muddied a few things while clarifying others; the point of the original was that output could be derived from the parity or from least-significant bits, not that they were the same thing. I've done my best to clear that up. Cheers. Andrew Rodland 05:31, 28 August 2005 (UTC)

Sorry. Just to clarify, with "bit parity", you mean the number of ones in the binary representation? -- Jitse Niesen (talk) 14:07, 28 August 2005 (UTC)

Yes, that's what I was after. Now, I realize that the original may have simply intended a meaning of "parity" indicating the least-significant bit. You may wish to remove "either the bit parity of xn or". It's possible that parity in the sense of parity bit is used for the output of BBS, but I have no reason to believe that it is other than my (probably mistaken) reading of a previous revision. Andrew Rodland

Actually, [1] says "the output is the least significant bit of xn + 1 or the parity of xn + 1", so your initial reading was probably right after all. -- Jitse Niesen (talk) 12:57, 31 October 2005 (UTC)

[edit] Symmetric or Assymetric?

I've been looking through the references in this page trying to find an answer to that question. Nowehere does it explicitly say that the algorithm is symmetric or assymmetric (I had a hard time finding decryption algorithm resources & definition, only the mention of the chinese remainder algorithm). I am guessing that it is symmetric, but from what I read I cannot say for sure. Any help would be appreciated. --Stux 15:34, 24 October 2005 (UTC)

I am not sure what you mean here by "symmetric". As far as I can see from the article, the Blum Blum Shub algorithm only generates (pseudo)random numbers. It is not an algorithm for encrypting and decrypting text. Apologies if this is obvious to you, in which case I probably can't help. -- Jitse Niesen (talk) 16:29, 24 October 2005 (UTC)
No apologies needed, you raise a good point (and thank you for the quick reply!) -- all of the primary descriptions of the algorithm list it as a PRNG, and it is not entirely clear how it would be used for encryption. However both the article itself and the integer factorization page itself both list it as cryptographic tools. For "symmetric" what I mean is if it is a tool for private key encrytion (using a symmetric key) or public key encrytion (using an assymetric pair/set of keys) --Stux 17:56, 24 October 2005 (UTC)
Many cryptographic algorithms need a good PRNG. It is used both in symmetric and asymmetric encryption. In asymmetric algorithms it is used to generate big prime numbers, in symmetric algorithms it is used to generate random keys (for example GPG generates a random key, encrypts the plaintext using a symmetric algorithm (for example AES) and then sends the random key encrypted with RSA). From this point of view BBS is just a "tool" that can be used by any algorithm that needs random bits. In real world BBS is rarely used because of it is too slow, but there is an algorithm, the Blum-Goldwasser probabilistic encryption (which is asymmetric), that relays explicitly on BBS to generate keys. Sorry for poor grammar and spelling :-P. If you need more details you can contact me at my page on Wikipedia Italia: --Ippatsu (talk)
I would like to add that, although this is not a cipher algorithm, it's based on the original Rabin cryptosystem. By the way, one statement in the article may be wrong (which we can't decide yet). Cracking RSA is not proven to be as difficult as factoring the modulus, so you currently cannot say that RSA is tied to the factoring problem, and as such the BBS generator might be even more secure than RSA. However, its security is equivalent the Rabin's security. -- Ertugrul Soeylemez
On using the BBS generator to encrypt: it's possible to use it as part of a public-key encryption scheme. The private key is the pair p,q, both congruent to 3 (mod 4); the public key is their product, the Blum integer n = pq. To encrypt an n-bit message m = m_0 m_1 \ldots m_{n-1}, one chooses a random s \in \mathbb{Z}/n\mathbb{Z} and sets x0 = s2, and x_i = x_{i-1}^2 for i > 0; one then transmits the ciphertext c,xn where c = c_0 c_1 \ldots c_{n-1} and c_i = m_i \oplus (x_i \bmod 2). To decrypt, one takes xn and computes x0 by means of the Chinese Remainder Theorem. In particular, let ep = ((p + 1) / 4)nmod p − 1; then x_0 = x_n^{e_p}. So the recipient can recover x0 and therefore the other xi and hence decrypt the message. Conversely, the bits ximod 2 are hard-core of the squaring map modulo n, which is one-way if factoring is hard. Hence the ci are computationally indistinguishable from independent uniformly random bits. This proves the semantic security of the construction. It was introduced in M. Blum and S. Goldwasser, `An efficient probabilistic public-key enryption scheme which hides all partial information', CRYPTO '84.

[edit] Integers are "suspected" hard to factor?

I was thinking about adding an external link to the P vs. NP Millenium prize problem at the Clay institute, but it's much more straightforward to hyperlink the phrase "integer factorization" to the Wikipedia page with that title, so I did that instead, even though there was already another link to that page in the preceding sentence.

[edit] Move page?

I don't like the name "Blum Blum Shub" for this page. I think this material should exist at "Blum-Blum-Shub pseudorandom generator" because (1) that title makes it clear what the article is about, and (2) the standard in crypto literature is to hyphenate author names when written out, eg. Diffie-Hellman key exchange, Goldwasser-Micali cryptosystem, Boneh-Franklin IBE, et cetera. Actually, now that I think about it, I may try to start a naming convention for crypto articles, because a lot of them are named badly. Anyway, that's why I moved the page. Mangojuice 02:06, 21 January 2006 (UTC)

[edit] Possible Mistake

Is the Big O function supposed to be "log log M" or is that just a typo? Is it supposed to be the log of the log of M? Zero 13:15, 12 September 2006 (UTC)

  • Gotta be. If it were just the log of M, we would be looking at all the bits of the modulus. 209.210.225.6 03:59, 3 February 2007 (UTC)

[edit] Note on the unhelpfulness of the security proof

The security of the BBS generator is proven by means of a reduction, showing that an algorithm which successfully distinguishes a BBS output from a random string (equivalently, predicts the next bit) with non-negligible success can be used to factor the modulus. However, this `reduction' is very inefficient. In fact, as discussed in section 6.1 of N. Koblitz and A. Menezes, `Another look at ``provable security, II', http://eprint.iacr.org/2006/229, the current security reductions are almost completely useless. For currently-sensible key sizes (up to 3072 bits) they show security against an adversary who uses at most 2 − 175 clock cycles. Yes, that was a minus sign. You've got to distinguish the bits from random bits in much less than one clock cycle!

Another warning. The current proof shows that O(loglogn) bits are simultaneously hard-core, and can therefore be extracted at each iteration. There's a constant hidden in that O(\cdot), and seems to be less than one. Again, this is discussed in Koblitz and Menezes paper.

Summary: beware of asymptotic results. At least as far as security is concerned, they're much less useful than they look.

[edit] Mistake in the Example?

The page says that p and q should be primes, but q = 15 in the example doesn't seem like a prime to me. Either there is a mistake in the example, or the description of the algorithm is somehow misleading. -- Samuli, 1 September 2006.

There is yet another mistake in the example. For p = 11 and q = 19 the resulting bits would be b0b1...b5 = 1 0 0 0 0 0. Michael Prager 13:29, 15 November 2006 (UTC)
The writer probably meant that bi is determined by taking the bit parity of xi. I tried to clarify this. -- Jitse Niesen (talk) 02:24, 16 November 2006 (UTC)
Retrieved from "http://en.wikipedia.org../../../b/l/u/Talk%7EBlum_Blum_Shub_62d0.html"