After a decade of discussion and sci.crypt messages probably numbering in the thousands, we finally have a reasonable way to provably eliminate the (extremely low) possibility of using a short cycle in BB&S. This requires us to go beyond current cryptographic practice and use the special primes construction as described in the original article:
Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-Random Number Generators. Advances in Cryptology: CRYPTO '82 Proceedings. Plenum Press: New York. 61-78.Blum, L., M. Blum and M. Shub. 1986. A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal on Computing. 15: 364-383.
Construct N as the product of two large distinct primes, P and Q.
Both P and Q must be congruent to
The special primes construction apparently assures that we have only "long enough" cycles and degenerate cycles. Then we can choose our seed x0 at random, and check to see that we have not selected a degenerate cycle. See the messages, culminating with a prescription: 2001-06-26 Terry Ritter.
Subject: Seed selection in Blum Blum Shub generators. Date: Tue, 19 Jun 2001 23:04:52 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Message-ID: <20010619230452.A1216@home.com> Newsgroups: sci.crypt Lines: 29 While reading http://www.io.com/~ritter/NEWS2/94061801.HTM I came across the following comment regarding the selection of the initial seed in a BBS generator: "Thus, a BB&S generator cannot be initialized with random state, because this state may happen to be on a short cycle. If this were allowed, the resulting sequence would become "predictable" as soon as the cycle started to repeat." "This is prevented in a *real* BB&S design by mathematical proof showing that such a design will have a long cycle of a predictable length (given certain strenuous conditions on N), *and* by using the algorithm in Section 9 (Algorithms for determining length of period and random accessing) to show that an initial state (X0) is on such a cycle." Immediately above these paragraphs Terry shows a simple example of the short cycles that can result from poor seed selection. Later in the paper he talks about the proper selection of P and Q. The problem is that I don't have a copy of the original paper and don't know how to go about verifying that my initial seed isn't on a short cycle when P and Q are large (> 1024 bits). Generating the large P and Q that satisfy the "special" properties isn't a problem (time isn't an issue for my specific application.) Verifying that the initial seed is good has got me stumped though. Any advice and/or pointers to information I overlooked would be greatly appreciated.
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Wed, 20 Jun 2001 04:52:59 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b302b78.5993797@news.io.com> References: <20010619230452.A1216@home.com> Newsgroups: sci.crypt Lines: 69 On Tue, 19 Jun 2001 23:04:52 -0400, in <20010619230452.A1216@home.com>, in sci.crypt Mixtim <Use-Author-Address-Header@[127.1]> wrote: >While reading http://www.io.com/~ritter/NEWS2/94061801.HTM I came across >the following comment regarding the selection of the initial seed in a >BBS generator: > > "Thus, a BB&S generator cannot be initialized with random state, > because this state may happen to be on a short cycle. If this were > allowed, the resulting sequence would become "predictable" as soon > as the cycle started to repeat." > > "This is prevented in a *real* BB&S design by mathematical proof > showing that such a design will have a long cycle of a predictable > length (given certain strenuous conditions on N), *and* by using the > algorithm in Section 9 (Algorithms for determining length of period > and random accessing) to show that an initial state (X0) is on such > a cycle." > >Immediately above these paragraphs Terry shows a simple example of the >short cycles that can result from poor seed selection. Later in the >paper he talks about the proper selection of P and Q. > >The problem is that I don't have a copy of the original paper and don't >know how to go about verifying that my initial seed isn't on a short >cycle when P and Q are large (> 1024 bits). Generating the large P and Q >that satisfy the "special" properties isn't a problem (time isn't an >issue for my specific application.) Verifying that the initial seed is >good has got me stumped though. > >Any advice and/or pointers to information I overlooked would be greatly >appreciated. First of all, in practice, the short cycle weakness is not usually considered an issue worth defending against. Of course, BB&S is rarely used in practice anyway. My problem in BB&S conversations over many years basically is the use of the moniker "proven secure" for a system which obviously does have a potential weakness (and one which was avoided in the original article). The math crypto guys say this is no contradiction, once we understand what the security proof actually is. Apparently the security guarantee is that no weakness exists which is easier than, say, factoring N. Yet I am reluctant to accept a security proof which includes a *known* possibility of weakness which can be avoided. Almost a decade ago, I had an e-mail conversation with Robert Eachus, who suggested the following: We use the "special primes" construction for P and Q of public-key size, and then check that x is not degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but 23 is not degenerate. Why?) But we don't need much analysis, because finding a degenerate cycle is easy: choose x at random, take a step, record that result, then step again. If the result is the same, start over with a new x. Supposedly the special-primes construction allows us to analyze the other cycles in the system, which are all found to be "long enough" for use. So we just use whatever comes up. That should simplify things considerably, even though special primes are substantially harder to find than ordinary primes. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Thu, 21 Jun 2001 22:03:37 +0200 From: "Cristiano" <cristiano.p@mclink.it> Message-ID: <9gtjus$c3u$1@news.mclink.it> References: <3b302b78.5993797@news.io.com> Newsgroups: sci.crypt Lines: 16 "Terry Ritter" <ritter@io.com> wrote: .> Almost a decade ago, I had an e-mail conversation with Robert Eachus, .> who suggested the following: We use the "special primes" construction .> for P and Q of public-key size, and then check that x is not .> degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 .> degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but .> 23 is not degenerate. Why?) But we don't need much analysis, because .> finding a degenerate cycle is easy: choose x at random, take a step, .> record that result, then step again. If the result is the same, start .> over with a new x. But if the cycle is long only 3, 4 or 5 is not too short? Cristiano
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Thu, 21 Jun 2001 20:39:35 GMT From: Tom St Denis <tomstdenis@yahoo.com> Message-ID: <3B325B91.9190CF2F@yahoo.com> References: <9gtjus$c3u$1@news.mclink.it> Newsgroups: sci.crypt Lines: 19 Cristiano wrote: > > "Terry Ritter" <ritter@io.com> wrote: > .> Almost a decade ago, I had an e-mail conversation with Robert Eachus, > .> who suggested the following: We use the "special primes" construction > .> for P and Q of public-key size, and then check that x is not > .> degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 > .> degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but > .> 23 is not degenerate. Why?) But we don't need much analysis, because > .> finding a degenerate cycle is easy: choose x at random, take a step, > .> record that result, then step again. If the result is the same, start > .> over with a new x. > > But if the cycle is long only 3, 4 or 5 is not too short? You're onto it. There is no proof of cycle length, nor any proof of the entropy in the output. Tom
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Thu, 21 Jun 2001 23:02:27 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b327bad.3282601@news.io.com> References: <3B325B91.9190CF2F@yahoo.com> Newsgroups: sci.crypt Lines: 34 On Thu, 21 Jun 2001 20:39:35 GMT, in <3B325B91.9190CF2F@yahoo.com>, in sci.crypt Tom St Denis <tomstdenis@yahoo.com> wrote: >Cristiano wrote: >> >> "Terry Ritter" <ritter@io.com> wrote: >> .> Almost a decade ago, I had an e-mail conversation with Robert Eachus, >> .> who suggested the following: We use the "special primes" construction >> .> for P and Q of public-key size, and then check that x is not >> .> degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 >> .> degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but >> .> 23 is not degenerate. Why?) But we don't need much analysis, because >> .> finding a degenerate cycle is easy: choose x at random, take a step, >> .> record that result, then step again. If the result is the same, start >> .> over with a new x. >> >> But if the cycle is long only 3, 4 or 5 is not too short? > >You're onto it. There is no proof of cycle length, nor any proof of the >entropy in the output. Apparently, given the special primes construction, the resulting cycle lengths do not occur at random but are instead controlled by the construction itself. Eachus said the cycle lengths *can* be proven to consist only of degenerate cycles and "long enough" cycles (assuming huge special primes). (The "short cycles" *are* "relatively" short, but actually very long.) So, once we eliminate the use of degenerate cycles, whatever we get is fine. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Thu, 21 Jun 2001 23:25:38 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <SnvY6.7734$St6.1009632@news3.rdc1.on.home.com> References: <3b327bad.3282601@news.io.com> Newsgroups: sci.crypt Lines: 52 "Terry Ritter" <ritter@io.com> wrote in message news:3b327bad.3282601@news.io.com... > > On Thu, 21 Jun 2001 20:39:35 GMT, in <3B325B91.9190CF2F@yahoo.com>, in > sci.crypt Tom St Denis <tomstdenis@yahoo.com> wrote: > > >Cristiano wrote: > >> > >> "Terry Ritter" <ritter@io.com> wrote: > >> .> Almost a decade ago, I had an e-mail conversation with Robert Eachus, > >> .> who suggested the following: We use the "special primes" construction > >> .> for P and Q of public-key size, and then check that x is not > >> .> degenerate. (For P = 23, Q = 47, N = P * Q = 1081, we have 4 > >> .> degenerate cycles, at 0, 1, 47, and 1035. Now, 1035 = N + 1 - 47, but > >> .> 23 is not degenerate. Why?) But we don't need much analysis, because > >> .> finding a degenerate cycle is easy: choose x at random, take a step, > >> .> record that result, then step again. If the result is the same, start > >> .> over with a new x. > >> > >> But if the cycle is long only 3, 4 or 5 is not too short? > > > >You're onto it. There is no proof of cycle length, nor any proof of the > >entropy in the output. > > Apparently, given the special primes construction, the resulting cycle > lengths do not occur at random but are instead controlled by the > construction itself. Eachus said the cycle lengths *can* be proven to > consist only of degenerate cycles and "long enough" cycles (assuming > huge special primes). (The "short cycles" *are* "relatively" short, > but actually very long.) So, once we eliminate the use of degenerate > cycles, whatever we get is fine. Well a degenerate cycle and short cycle are in fact different types of cycles. A => B => B is degenerate. A => B => ...lots more times => A is a "short" cycle [assume 'lots more times' is not an exceedingly large # of times]. We probably can avoid the former but I am certain no method exists to avoid the latter. Tom
Subject: Re: Seed selection in Blum Blum Shub generators. Date: 22 Jun 2001 14:38:36 GMT From: mdw@nsict.org (Mark Wooding) Message-ID: <slrn9j6m3b.clo.mdw@daryl.nsict.org> References: <SnvY6.7734$St6.1009632@news3.rdc1.on.home.com> Newsgroups: sci.crypt Lines: 51 Tom St Denis <tomstdenis@yahoo.com> wrote: > We probably can avoid the former but I am certain no method exists to avoid > the latter. You're talking rubbish (and not trimming your quotes). The cycle length is related to the order of the starting element (actually, to the order of 2 mod the order of...) I don't think it takes a great deal of imagination to see that, if the maximum cycle length has only large prime factors (and maybe a few tiny ones), it's very easy to check for a cycle which has length product-of-only-tiny- factors and once you've done that, you know that the cycle length must be at least as large as your smallest large prime. Doing this properly-ish... Let n = p q. Let's look at cycle length for x |-> x^2 mod p. (mod q will be completely symmetrical, and then we combine the cycle lengths with lcm if we really care.) A cycle will have the form x, x^2, x^{2^2}, x^{2^3}, ..., x^{2^k} = x. If we write the order of x mod n as ord_n(x), we see that we've found that 2^k = 1 (mod ord_p(x)), i.e., k = ord_{ord_p(x)}(2). We'd like k to be either tiny (so we notice) or enormous (so we're safe). As a first cut, choose p = 2 r + 1 where r is prime. Then ord_p(x) is one of: 1, 2, r, 2 r. ord_p(x) = 1 only happens when x = 1, and ord_p(x) = 2 only happens when x = p - 1, so don't do that. Now we look at the order of 2 mod ord_p(x). It must be a factor of \lambda(ord_p(x)), which (by design) is r - 1. If we choose r = 2 s + 1 where s is also prime. Then we know that the cycle length is either 1, 2 or huge. There are very few primes p of this sort. Finding them is a lot of work. However, if we decide that t is a good minimum cycle length then we can use an approach similar to the Lim-Lee construction: we can choose a pool of primes s_i >= t such that r_i = 2 s_i + 1 is prime, and then choose p, q = 2 \prod_i r_i^{c_i} + 1 for appropriately chosen c_i \in {0, 1}. If we're not too ambitious with t, then finding the s_i isn't a vast amount of work and constructing p and q is fairly easy. Of course, this is all a bit of a waste of effort. p - 1 is unlikely to be particularly smooth, and the order of any element x mod p will probably have a large prime factor r. Similarly, the order of 2 mod ord_x(p) will probably be large (because r - 1 probably has a large prime factor). I'm sure that better number theorists than I can put proper numbers on my handwaving here. -- [mdw]
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Fri, 22 Jun 2001 20:11:38 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <_DNY6.2050$Mf5.741678@news3.rdc1.on.home.com> References: <slrn9j6m3b.clo.mdw@daryl.nsict.org> Newsgroups: sci.crypt Lines: 85 "Mark Wooding" <mdw@nsict.org> wrote in message news:slrn9j6m3b.clo.mdw@daryl.nsict.org... > Tom St Denis <tomstdenis@yahoo.com> wrote: > > > We probably can avoid the former but I am certain no method exists to avoid > > the latter. > > You're talking rubbish (and not trimming your quotes). Rubbish... hehehe > The cycle length is related to the order of the starting element > (actually, to the order of 2 mod the order of...) I don't think it > takes a great deal of imagination to see that, if the maximum cycle > length has only large prime factors (and maybe a few tiny ones), it's > very easy to check for a cycle which has length product-of-only-tiny- > factors and once you've done that, you know that the cycle length must > be at least as large as your smallest large prime. > > Doing this properly-ish... > > Let n = p q. Let's look at cycle length for x |-> x^2 mod p. (mod q > will be completely symmetrical, and then we combine the cycle lengths > with lcm if we really care.) > > A cycle will have the form x, x^2, x^{2^2}, x^{2^3}, ..., x^{2^k} = x. > If we write the order of x mod n as ord_n(x), we see that we've found > that 2^k = 1 (mod ord_p(x)), i.e., k = ord_{ord_p(x)}(2). We'd like k > to be either tiny (so we notice) or enormous (so we're safe). This is nonce. There is no reason to suggest that the cycle won't have a leading edge... try p = 7 q = 11 x = 7 you get 7, [49, 14, 42, 70] Where 7 is never repeated. Not only that but the lsb is biased [P(X=0) = 3/4] > As a first cut, choose p = 2 r + 1 where r is prime. Then ord_p(x) is > one of: 1, 2, r, 2 r. ord_p(x) = 1 only happens when x = 1, and > ord_p(x) = 2 only happens when x = p - 1, so don't do that. <snip> This theory only applies if you are multiplying a base repeatedly... i.e b^1, b^2, b^3, b^4, ... Doing (b^2), b^4, b^8, b^16 with BBS is not guaranteed to be secure since a user will not know if b is a primitive [or at least long perioded] generator. Not only that but just toying around with BBS lends me to think it's none to good. I tried about 13 diff bases for pq = 77, and none of them had a period over 4 elements and some were very degernerate. like 22^2 mod 77 = 22. I would imagine that the cycles are longer as you get up there, but unless you pick a generator as your base the period is not guaranteed at all. Let's say that you have pq = 768 bit number. such that p,q are 384 bits each. Let's suppose both p and q are strong primes. Then some base will have a period of 1, 2, 4, p-1, q-1, 2p - 2, 2q- 2, (q-1)(p-1), 2(q-1)(p-1) or 4(q-1)(p - 1) [I forgot a few but you get the point] Let's say some base G makes a sub-group of order p-1. this is a group with 2^384 elements. In order for the period of G to be maximal in the sub-group, 2 must be a primitive element modulo p-1, which clearly can't be since p-1 is even. We require 2 to be a primitive element since we are doing 2^k mod p-1. Tom
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Fri, 22 Jun 2001 23:59:59 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B33CDEF.607032B7@zetnet.co.uk> References: <_DNY6.2050$Mf5.741678@news3.rdc1.on.home.com> Newsgroups: sci.crypt Lines: 80 -----BEGIN PGP SIGNED MESSAGE----- Tom St Denis wrote: > "Mark Wooding" <mdw@nsict.org> wrote in message > news:slrn9j6m3b.clo.mdw@daryl.nsict.org... > > Doing this properly-ish... > > > > Let n = p q. Let's look at cycle length for x |-> x^2 mod p. (mod q > > will be completely symmetrical, and then we combine the cycle lengths > > with lcm if we really care.) > > > > A cycle will have the form x, x^2, x^{2^2}, x^{2^3}, ..., x^{2^k} = x. > > If we write the order of x mod n as ord_n(x), we see that we've found > > that 2^k = 1 (mod ord_p(x)), i.e., k = ord_{ord_p(x)}(2). We'd like k > > to be either tiny (so we notice) or enormous (so we're safe). > > This is nonce. There is no reason to suggest that the cycle won't have a > leading edge... Think about it more carefully. In the paragraph quoted above, x is an arbitrary element. There's nothing wrong with Mark Wooding's informal proof (although as he says, it isn't really necessary to use this method, since the cycle length is large except with negligable probability anyway). [snip] > Not only that but just toying around with BBS lends me to think it's none to > good. > > I tried about 13 diff bases for pq = 77, and none of them had a period over > 4 elements and some were very degernerate. like 22^2 mod 77 = 22. That isn't surprising, since numbers this size are not difficult to factor. > I would imagine that the cycles are longer as you get up there, but unless > you pick a generator as your base the period is not guaranteed at all. > Let's say that you have pq = 768 bit number. such that p,q are 384 bits > each. Let's suppose both p and q are strong primes. I assume you mean safe primes. > Then some base will > have a period of 1, 2, 4, p-1, q-1, 2p - 2, 2q- 2, (q-1)(p-1), 2(q-1)(p-1) > or 4(q-1)(p - 1) [I forgot a few but you get the point] The possible orders are the factors of the group order lcm(p-1, q-1), i.e. { 1, 2, (p-1)/2, p-1, (q-1)/2, q-1, (p-1)(q-1)/4, (p-1)(q-1)/2 }. > Let's say some base G makes a sub-group of order p-1. this is a group with > 2^384 elements. In order for the period of G to be maximal in the > sub-group, 2 must be a primitive element modulo p-1, which clearly can't be > since p-1 is even. We require 2 to be a primitive element since we are > doing 2^k mod p-1. No, we don't require that, since the order of *any* element of Z*_n must be 1, 2, 4, or >= (min(p, q)-1)/2. - -- David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBOzPNdzkCAxeYt5gVAQEm3gf/Vbhpyfm4iP5Qfq4h0DbVb72EMwb2E+7w u8zSeHVjS9PSNi7H6f47/6XcfsYCF1YSQPFuP1QOQ2pm7B/yQCWvw8jupqyduO6J 5A4Bqmq7wx7GmomZeU7gd0fsT71lU7gYaYeBk9+Y/cHOuD/ELV3VVfaIXpqeLoB0 O3olkpfKgelZIHNLnlnjQ+X7mrPYK3dX2tBJS6of8mYFaBQ+tEGBxGza1yhL1lqw ORTbQm2SmfLHF5O1nL+OrUJmpYrTXO9q7qHYp9afpKIF+LXvR/xilwjlYZhgEkNw 9FbyWkM4G9s65qbaP3OZywHxiEcjNarbRwEGwlxsPZFSS4WWORs2Ow== =3oOW -----END PGP SIGNATURE-----
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Sat, 23 Jun 2001 16:16:52 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B34B2E4.D993E79C@zetnet.co.uk> References: <sR_Y6.6226$Mf5.2223898@news3.rdc1.on.home.com> <3B33CDEF.607032B7@zetnet.co.uk> Newsgroups: sci.crypt Lines: 86 -----BEGIN PGP SIGNED MESSAGE----- Tom St Denis wrote: > "David Hopwood" <david.hopwood@zetnet.co.uk> wrote in message > news:3B33CDEF.607032B7@zetnet.co.uk... > > [context: let p and q be safe 384-bit primes, and consider the group > > Z*_{pq}.] > > > > The possible orders are the factors of the group order lcm(p-1, q-1), i.e. > > { 1, 2, (p-1)/2, p-1, (q-1)/2, q-1, (p-1)(q-1)/4, (p-1)(q-1)/2 }. > > And any linear combination thereof ... 2q - 2, etc... or is that wrong? That's wrong. A cyclic group G of order k is isomorphic to (Z_k, +). Consider the orders of elements of (Z_k, +); clearly they are the factors of k. > I always though the order of any element can be any linear combination of > the factors of phi(p) or lcm(p-1,q-1)? No. Also, I think you're still confusing phi and lambda; if p and q are prime, then phi(pq) = (p-1)(q-1) lambda(pq) = lcm(p-1, q-1). > > > Let's say some base G makes a sub-group of order p-1. this is a group > > > with 2^384 elements. In order for the period of G to be maximal in the > > > sub-group, 2 must be a primitive element modulo p-1, which clearly can't > > > be since p-1 is even. We require 2 to be a primitive element since we > > > are doing 2^k mod p-1. > > > > No, we don't require that, since the order of *any* element of Z*_n must > > be 1, 2, 4, or >= (min(p, q)-1)/2. I meant 1, 2, or >= (min(p, q)-1)/2; it can't be 4. I was sure I'd corrected that before posting, but obviously not. However, you're right in pointing out that I had also missed out another essential part of the argument; see below. > This is not true. You are not doing > > g^x mod n > > You are doing > > g^(2^k) mod n = g^(2^k mod phi(g)) mod p > > So the order of 2 modulo the order of the sub-group that g generates modulo > p is important. Yes, but Mark Wooding already took that into account: # Now we look at the order of 2 mod ord_p(x). It must be a factor of # \lambda(ord_p(x)), So, since in the example ord_p(x) is a factor of 2((p-1)/2)((q-1)/2), and (p-1)/2 and (q-1)/2 are prime, we have that the order of 2 mod ord_p(x) is a factor of lcm((p-1)/2 - 1, (q-1)/2 - 1). Mark had set p = 2r + 1 and r = 2s + 1. If we similarly set q = 2r' + 1 and r' = 2s' + 1, then the cycle length is a factor of lcm(2s, 2s') = 2 lcm(s, s'). So if s and s' have no small factors (except 1), then the cycle length is either 1, 2, or large. - -- David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBOzSynjkCAxeYt5gVAQEgLwf/by/RIlf7kXruwEhSH1TtZdyZ1PVOuxJO BGuN9NBqRrqp71HI0ZMIbPjzQu2iqMiq0kexj9MDfYF8GpweTpC+ivZXE5KoIKHS iCGeygmq3OtqgZkwF532Znp+pha4aKLVaIYoM8GvlYjImIf3iGJyC963SZNm7OAQ rxxnB+lVqPGhbODChobZ98zNxRAwChfflzS+K41DB2ofoC0RI1LC9goh2WwPQi3+ bB1HTGPgawtkjCwAzMuYix3pGlWOO4HL4f81exFz+J40foRWBkenyhOwAMtXOUvp MNFQyqkXIJP5lCV6YMVtCyb+YejFkXwiAl13C++hx4E7GI2SuIYysg== =uESN -----END PGP SIGNATURE-----
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Sat, 23 Jun 2001 20:20:52 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <ES6Z6.11217$Mf5.3040393@news3.rdc1.on.home.com> References: <3B34B2E4.D993E79C@zetnet.co.uk> Newsgroups: sci.crypt Lines: 16 "David Hopwood" <david.hopwood@zetnet.co.uk> wrote in message news:3B34B2E4.D993E79C@zetnet.co.uk... > -----BEGIN PGP SIGNED MESSAGE----- <snip> Yeah I see the faulty of my math. I agree that your cycle lengths are correct. Mind if I ask what is the signficant difference between phi and lamda? Isn't lamda a factor of phi? [more precisely isn't phi a multiple of lamda?] Tom
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Tue, 26 Jun 2001 04:12:12 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b380b71.4332015@news.io.com> References: <3B34B2E4.D993E79C@zetnet.co.uk> Newsgroups: sci.crypt Lines: 28 On Sat, 23 Jun 2001 16:16:52 +0100, in <3B34B2E4.D993E79C@zetnet.co.uk>, in sci.crypt David Hopwood <david.hopwood@zetnet.co.uk> wrote: >[...] >Mark had set p = 2r + 1 and >r = 2s + 1. If we similarly set q = 2r' + 1 and r' = 2s' + 1, then the cycle >length is a factor of lcm(2s, 2s') = 2 lcm(s, s'). > >So if s and s' have no small factors (except 1), then the cycle length is >either 1, 2, or large. In my experience traversing the states and cycles of tiny BB&S constructions (see http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect7.2.2 ), I have never found a cycle of length 2 in a "special primes" construction. Do you have or can you construct an example of special primes BB&S construction with a length 2 cycle? --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Tue, 26 Jun 2001 17:01:15 +0100 From: David Hopwood <david.hopwood@zetnet.co.uk> Message-ID: <3B38B1CB.D2C7F37D@zetnet.co.uk> References: <3b380b71.4332015@news.io.com> Newsgroups: sci.crypt Lines: 53 -----BEGIN PGP SIGNED MESSAGE----- Terry Ritter wrote: > David Hopwood <david.hopwood@zetnet.co.uk> wrote: > >[...] > >Mark had set p = 2r + 1 and > >r = 2s + 1. If we similarly set q = 2r' + 1 and r' = 2s' + 1, then the cycle > >length is a factor of lcm(2s, 2s') = 2 lcm(s, s'). > > > >So if s and s' have no small factors (except 1), then the cycle length is > >either 1, 2, or large. More precisely, it can be proven by this argument that the cycle length is 1, 2 or large (but in fact 2 is ruled out for a different reason; see below). > In my experience traversing the states and cycles of tiny BB&S > constructions (see > > http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect7.2.2 > > ), I have never found a cycle of length 2 in a "special primes" > construction. > > Do you have or can you construct an example of special primes BB&S > construction with a length 2 cycle? That would require the element 2 to be of order 2 in Z*_{lambda(N)}. If lambda(N) > 4 then this obviously can't occur, and lambda(N) must be > 4 since p, q >= 7. - -- David Hopwood <david.hopwood@zetnet.co.uk> Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/ RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01 Nothing in this message is intended to be legally binding. If I revoke a public key but refuse to specify why, it is because the private key has been seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip -----BEGIN PGP SIGNATURE----- Version: 2.6.3i Charset: noconv iQEVAwUBOzixsDkCAxeYt5gVAQH0hggAxQFSkdyr+RaORERSeS6FJMaaXd9Qgppi I4jm0Mb3nDVgycl4ySrz2j9f/buFEHvi9eq3QGYNL82eOLmhM2Qq4DRSbUwpemCj QoMWZae7ka91cNQkuwq/zlPVzFMP9OOTKygIfSr+D/HRWKpjCmc/aKvOZDkcRqtv VjlheZxtTQrKRzYUCygXpimye34DF0gcUXS0zsBKBLGA3MUWUTBj5qrA3mFdnHmL ygrpF2XbirOZIJ3oKdMWAML1aQCXQjvIUHzku88oSUyS10hCfy90irV8CrMFSDun QKkQ8uyBo6tsLILFfKJxvd4573md6D9F4qLXtdcxIyry5ZMlYMuA0g== =GdfS -----END PGP SIGNATURE-----
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Tue, 26 Jun 2001 19:13:46 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b38de9b.1115567@news.io.com> References: <3B38B1CB.D2C7F37D@zetnet.co.uk> Newsgroups: sci.crypt Lines: 34 On Tue, 26 Jun 2001 17:01:15 +0100, in <3B38B1CB.D2C7F37D@zetnet.co.uk>, in sci.crypt David Hopwood <david.hopwood@zetnet.co.uk> wrote: >>[...] >> Do you have or can you construct an example of special primes BB&S >> construction with a length 2 cycle? > >That would require the element 2 to be of order 2 in Z*_{lambda(N)}. >If lambda(N) > 4 then this obviously can't occur, and lambda(N) must >be > 4 since p, q >= 7. So one way to provably eliminate the use of dangerously short cycles in a practical BB&S is: 1. Use two *special* primes of public-key size. 2. Select the initial state x[0] at random. 3. Take a step (skip any lead-in), save x[1], take another step, then compare the current state x[2] with saved state x[1]; if they are the same, go to 2. (Note that the comparison can terminate as soon as a single bit difference is found; almost always, only one word comparison need execute.) This eliminates the use of degenerate cycles. And -- due to the special primes construction -- all of the remaining cycles, even the relatively "short" ones, are "long enough" for use. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Seed selection in Blum Blum Shub generators. Date: Wed, 27 Jun 2001 14:40:22 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Author-Address: mixtim <AT> home <DOT> com Message-ID: <20010627144022.A5184@home.com> References: <3B38B1CB.D2C7F37D@zetnet.co.uk> Newsgroups: sci.crypt Lines: 22 On Tue, Jun 26, 2001 at 07:13:46PM +0000, Terry Ritter wrote: > So one way to provably eliminate the use of dangerously short cycles > in a practical BB&S is: [snip] One simple program I wrote to generate the BBS primes produced the following output: $ time bbsgen /dev/urandom 128 attempt number 1031 attempt number 4875 p = 5e67ef2826ec916de1279b65eec9367 q = 12205916de2de95df58e176388ea6988f n = 6af3ca948c41280993fe97724864cb7e7346dfa9c8af116deb7c4ee34757e89 real 0m18.372s user 0m18.290s sys 0m0.280s Do those times seem too long to anyone? Anyone have anything significantly quicker?
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 11:24:57 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Author-Address: mixtim <AT> home <DOT> com Message-ID: <20010623112457.A45240@home.com> References: <3B38B1CB.D2C7F37D@zetnet.co.uk> Newsgroups: sci.crypt Lines: 21 On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > So as long as you use double-safe primes the order of any element is huge > (assuming p' is about 384 bits the period will be around 2^383). > Now the good question: How likely is it to find such a doubly safe prime? I don't know how likely it is but the procedure isn't hard, just time consuming. Simply: 1. Pick a really big prime -- however many bits you want. 2. Multiply the prime by 2 and add 1. 3. Check that the number obtained in step 2 is a prime. If not then start over at step 1. 4. Multiply the new prime by 2 and add 1. 5. Check that the number obtained in step 4 is a prime. If not then start over at step 1. You now have one of the numbers you need (as any prime times 2 plus 1 is congruent to 3 mod 4). Yes it takes a while, but if you are writing an application for which this time is not significant then its ok.
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 18:22:04 +0100 From: "Mike Scott" <mscott@indigo.ie> Message-ID: <%f4Z6.10494$Fk7.94018@news.indigo.ie> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 34 You could speed this process up substantially by using trial division on all three numbers that need to be prime, to quickly eliminate the majority of "non-double-safe-primes". Only if all three pass this test will expensive primality testing be required Mike Scott "Mixtim" <Use-Author-Address-Header@[127.1]> wrote in message news:20010623112457.A45240@home.com... > On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > > So as long as you use double-safe primes the order of any element is huge > > (assuming p' is about 384 bits the period will be around 2^383). > > Now the good question: How likely is it to find such a doubly safe prime? > > I don't know how likely it is but the procedure isn't hard, just time > consuming. Simply: > > 1. Pick a really big prime -- however many bits you want. > 2. Multiply the prime by 2 and add 1. > 3. Check that the number obtained in step 2 is a prime. > If not then start over at step 1. > 4. Multiply the new prime by 2 and add 1. > 5. Check that the number obtained in step 4 is a prime. > If not then start over at step 1. > > You now have one of the numbers you need (as any prime times 2 plus 1 > is congruent to 3 mod 4). > > Yes it takes a while, but if you are writing an application for which > this time is not significant then its ok.
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 20:12:30 +0200 From: "Cristiano" <cristiano.p@mclink.it> Message-ID: <9h2mbs$m11$1@news.mclink.it> References: <q12Z6.7939$Mf5.2479512@news3.rdc1.on.home.com> Newsgroups: sci.crypt Lines: 52 "Tom St Denis" <tomstdenis@yahoo.com> wrote: > Now the good question: How likely is it to find such a doubly safe prime? The code proposed by Mixtim works but it is terribly slow. I wrote code to find p1=p2*2+1 and p=p1*2+1 (p, p1 and p2 primes; do you have read the paper by Thierry Moreau?). I suggest to initialize to one 3 vectors of size n, 2*n and 4*n (n depend on platform and on size of p). Then set to zero the numbers wich are divisible for small primes (also this limit depend on platform). Now we can check with Miller-Rabin test the numbers with flag to 1. MR test should be done with primes bases and random numbers bases. I hope the following c++ code will be a little bit more explanatory (xi is the starting point, T is the numbers of iterations for MR test): void FIND_BBS(Big &xi,const int T) { const unsigned SS=10000,SSb=SS*32; ULONG *const b1=new ULONG[SS],*const b2=new ULONG[2*SS],*const b3=new ULONG[4*SS]; while(1) { memset(b1,255,SS*4); memset(b2,255,2*SS*4); memset(b3,255,4*SS*4); for(unsigned i=0;i<mip->npri;i++) { const unsigned p=mip->PRIMES[i]; unsigned r=xi%p; if(r) r=p-r; while(r<SSb) { set_bit(r,0,b1); r+=p; } r=(xi*2+1)%p; if(r) r=p-r; while(r<2*SSb) { set_bit(r,0,b2); r+=p; } r=(xi*4+3)%p; if(r) r=p-r; while(r<4*SSb) { set_bit(r,0,b3); r+=p; } } for(int i=0;i<SSb;i++) { if(get_bit(i,b1)) if(get_bit(i*2,b2)) if(get_bit(i*4,b3)) { if(MR(xi,2)) if(MR(xi*2+1,2)) if(MR(xi*4+3,T)) if(MR(xi,T)) if(MR(xi*2+1,T)) { delete[] b1; delete[] b2; delete[] b3; return; } } ++xi; } } } If SS and mip->npri will have regulated well, we will get the fastest code that I know. Cristiano
Subject: Re: BBS and safe primes Date: Sun, 24 Jun 2001 01:56:14 +0300 From: Fat Phil <fatphil_without_this_suffix@altavista.com> Message-ID: <3B351E8E.5A7DC67B@altavista.com> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 50 Mixtim wrote: > > On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > > So as long as you use double-safe primes the order of any element is huge > > (assuming p' is about 384 bits the period will be around 2^383). > > Now the good question: How likely is it to find such a doubly safe prime? > > I don't know how likely it is but the procedure isn't hard, just time > consuming. Simply: > > 1. Pick a really big prime -- however many bits you want. > 2. Multiply the prime by 2 and add 1. > 3. Check that the number obtained in step 2 is a prime. > If not then start over at step 1. > 4. Multiply the new prime by 2 and add 1. > 5. Check that the number obtained in step 4 is a prime. > If not then start over at step 1. > > You now have one of the numbers you need (as any prime times 2 plus 1 > is congruent to 3 mod 4). > > Yes it takes a while, but if you are writing an application for which > this time is not significant then its ok. There is a program, initially called "PrimeForm", now called "PFGW", which can find numbers that satisfy these conditions trivially. www.primeform.net should get you to a site where it can be downloaded. Look up "ABC2" file formats in the documentation, and start with something like the following: <<< ABC2: (2^768+2*$a+1) & (2^769+4*$a+3) & (2^770+8*$a+7) a in 1 to 1000000 >>> Run it with -f and it will trial factor first (which makes a lot of sense as most of the above will have small factors. It then does an incredibly fast SPRP (strong probable primality test). I used it to find the my 1800-digit 'illegal prime'. It found the PRP in only a few minutes (though the formal Elliptic Curve Primality Proof took several weeks). For tiny primes (such as 384 bits) an individual PRP should take bugger all time, but finding the combination of three primes will be substantially harder (about 1 in 10million tests?). Presieving and using an "ABC file" rather than an "ABC2 file" is another possibility. Phil
Subject: BBS Standalone Code Date: Sat, 30 Jun 2001 20:50:15 GMT From: Flip@safebunch.com Message-ID: <bYq%6.2921$Kf3.27493@www.newsranger.com> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 14 Hi All, does anyone know where I can get a copy of the Blum-Blum-Shaub (I may have the last name wrong ... sorry), otherwise known as BBS PRNG code. It would be nice to have standalone C code if it is available. I tried on the net, but to no avail. Any help is appreciated. By the way, does BBS have good crypto-PRNG properties (like entropy)? Thank you ... Wilson
Subject: Re: BBS Standalone Code Date: Sat, 30 Jun 2001 17:49:13 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Author-Address: mixtim <AT> home <DOT> com Message-ID: <20010630174913.A36797@home.com> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 32 On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > have the last name wrong ... sorry), otherwise known as BBS code. If you go to http://www.swox.com/gmp/ you can get a library for arbitrary precision arithmetic. The BBS algorithm is simply one gmp library call over and over: mpz_powm_ui(x, x, 2, n); After each call you use one (or more) bits from x. The hard part is generating the two special primes p and q to get n. I have a program that generates these special primes if you want it. $ time ./bbsprime 128 2c89599636259a1d586e3db8a25ecfc7 real 0m0.624s user 0m0.619s sys 0m0.001s $ time ./bbsprime 128 9157b3e960da3ea5f4cb433ff98c6647 real 0m5.440s user 0m5.396s sys 0m0.008s It can take a few seconds to get just a 128 bit special prime. Generating 512 bit special primes can take much longer. I'm sure other programs exist that find them more quickly. But once you have them then BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Wed, 04 Jul 2001 15:59:01 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B439FB5.9501AFD8@postoffice.pacbell.net> References: <20010630174913.A36797@home.com> Newsgroups: sci.crypt Lines: 39 Do the special primes guarantee that the generator will not have short cycles? Mixtim wrote: > On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > > have the last name wrong ... sorry), otherwise known as BBS code. > > If you go to http://www.swox.com/gmp/ you can get a library for > arbitrary precision arithmetic. The BBS algorithm is simply one gmp > library call over and over: > > mpz_powm_ui(x, x, 2, n); > > After each call you use one (or more) bits from x. The hard part is > generating the two special primes p and q to get n. I have a program > that generates these special primes if you want it. > > $ time ./bbsprime 128 > 2c89599636259a1d586e3db8a25ecfc7 > > real 0m0.624s > user 0m0.619s > sys 0m0.001s > $ time ./bbsprime 128 > 9157b3e960da3ea5f4cb433ff98c6647 > > real 0m5.440s > user 0m5.396s > sys 0m0.008s > > It can take a few seconds to get just a 128 bit special prime. > Generating 512 bit special primes can take much longer. I'm sure other > programs exist that find them more quickly. But once you have them then > BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Wed, 04 Jul 2001 23:01:17 GMT From: "Tom St Denis" <tomstdenis@yahoo.com> Message-ID: <1fN07.93093$Mf5.26695719@news3.rdc1.on.home.com> References: <3B439FB5.9501AFD8@postoffice.pacbell.net> Newsgroups: sci.crypt Lines: 12 <subnet2@postoffice.pacbell.net> wrote in message news:3B439FB5.9501AFD8@postoffice.pacbell.net... > Do the special primes guarantee that the generator will not have short > cycles? Yes doubly safe primes will ensure that any non-trivial base will have a long period. Tom
Subject: Re: BBS Standalone Code Date: Thu, 05 Jul 2001 03:48:15 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b43e36c.737664@news.io.com> References: <3B439FB5.9501AFD8@postoffice.pacbell.net> Newsgroups: sci.crypt Lines: 18 On Wed, 04 Jul 2001 15:59:01 -0700, in <3B439FB5.9501AFD8@postoffice.pacbell.net>, in sci.crypt subnet2@postoffice.pacbell.net wrote: >Do the special primes guarantee that the generator will not have short >cycles? Not completely. The special primes construction guarantees that *if* we avoid selecting a degenerate cycle (and that is easy enough to check), all the remaining cycles are "long enough" for use. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: BBS Standalone Code Date: Thu, 05 Jul 2001 22:19:12 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B454A50.CD546325@postoffice.pacbell.net> References: <20010630174913.A36797@home.com> Newsgroups: sci.crypt Lines: 38 Do the special primes guarantee that the BBS will not have short cycles? Mixtim wrote: > On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > > have the last name wrong ... sorry), otherwise known as BBS code. > > If you go to http://www.swox.com/gmp/ you can get a library for > arbitrary precision arithmetic. The BBS algorithm is simply one gmp > library call over and over: > > mpz_powm_ui(x, x, 2, n); > > After each call you use one (or more) bits from x. The hard part is > generating the two special primes p and q to get n. I have a program > that generates these special primes if you want it. > > $ time ./bbsprime 128 > 2c89599636259a1d586e3db8a25ecfc7 > > real 0m0.624s > user 0m0.619s > sys 0m0.001s > $ time ./bbsprime 128 > 9157b3e960da3ea5f4cb433ff98c6647 > > real 0m5.440s > user 0m5.396s > sys 0m0.008s > > It can take a few seconds to get just a 128 bit special prime. > Generating 512 bit special primes can take much longer. I'm sure other > programs exist that find them more quickly. But once you have them then > BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Thu, 05 Jul 2001 22:19:29 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B454A61.2FD3AD73@postoffice.pacbell.net> References: <20010630174913.A36797@home.com> Newsgroups: sci.crypt Lines: 38 Do the special primes guarantee that the BBS will not have short cycles? Mixtim wrote: > On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > > have the last name wrong ... sorry), otherwise known as BBS code. > > If you go to http://www.swox.com/gmp/ you can get a library for > arbitrary precision arithmetic. The BBS algorithm is simply one gmp > library call over and over: > > mpz_powm_ui(x, x, 2, n); > > After each call you use one (or more) bits from x. The hard part is > generating the two special primes p and q to get n. I have a program > that generates these special primes if you want it. > > $ time ./bbsprime 128 > 2c89599636259a1d586e3db8a25ecfc7 > > real 0m0.624s > user 0m0.619s > sys 0m0.001s > $ time ./bbsprime 128 > 9157b3e960da3ea5f4cb433ff98c6647 > > real 0m5.440s > user 0m5.396s > sys 0m0.008s > > It can take a few seconds to get just a 128 bit special prime. > Generating 512 bit special primes can take much longer. I'm sure other > programs exist that find them more quickly. But once you have them then > BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Thu, 05 Jul 2001 22:18:49 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B454A39.FBD8D86F@postoffice.pacbell.net> References: <20010630174913.A36797@home.com> Newsgroups: sci.crypt Lines: 38 Do the special primes guarantee that the BBS will not have short cycles? Mixtim wrote: > On Sat, Jun 30, 2001 at 08:50:15PM +0000, Flip@safebunch.com wrote: > > does anyone know where I can get a copy of the Blum-Blum-Shub (I may > > have the last name wrong ... sorry), otherwise known as BBS code. > > If you go to http://www.swox.com/gmp/ you can get a library for > arbitrary precision arithmetic. The BBS algorithm is simply one gmp > library call over and over: > > mpz_powm_ui(x, x, 2, n); > > After each call you use one (or more) bits from x. The hard part is > generating the two special primes p and q to get n. I have a program > that generates these special primes if you want it. > > $ time ./bbsprime 128 > 2c89599636259a1d586e3db8a25ecfc7 > > real 0m0.624s > user 0m0.619s > sys 0m0.001s > $ time ./bbsprime 128 > 9157b3e960da3ea5f4cb433ff98c6647 > > real 0m5.440s > user 0m5.396s > sys 0m0.008s > > It can take a few seconds to get just a 128 bit special prime. > Generating 512 bit special primes can take much longer. I'm sure other > programs exist that find them more quickly. But once you have them then > BBS is just that one function call over and over.
Subject: Re: BBS Standalone Code Date: Fri, 06 Jul 2001 06:33:45 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b455ba0.3515922@news.io.com> References: <3B454A39.FBD8D86F@postoffice.pacbell.net> Newsgroups: sci.crypt Lines: 21 On Thu, 05 Jul 2001 22:18:49 -0700, in <3B454A39.FBD8D86F@postoffice.pacbell.net>, in sci.crypt subnet2@postoffice.pacbell.net wrote: >Do the special primes guarantee that the BBS will not have short cycles? No. No, no, no. With public-key size special primes, the "short" cycles will either be "long enough" to use, or degenerate (i.e., single-cycle loops). To eliminate the possibility of using a degenerate cycle in practice, we choose x[0] at random, take a step (thus skipping any lead-in), save x[1], step again, and compare x[2] with x[1]. If x[2] == x[1] (which almost never happens in practice, so we need to force that to check the code), we choose another x[0] and start over. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: BBS Standalone Code Date: Fri, 06 Jul 2001 08:08:39 -0700 From: subnet2@postoffice.pacbell.net Message-ID: <3B45D476.4D020774@postoffice.pacbell.net> References: <3b455ba0.3515922@news.io.com> Newsgroups: sci.crypt Lines: 26 Thanks. I did not undertand this. Terry Ritter wrote: > On Thu, 05 Jul 2001 22:18:49 -0700, in > <3B454A39.FBD8D86F@postoffice.pacbell.net>, in sci.crypt > subnet2@postoffice.pacbell.net wrote: > > >Do the special primes guarantee that the BBS will not have short cycles? > > No. No, no, no. > > With public-key size special primes, the "short" cycles will either be > "long enough" to use, or degenerate (i.e., single-cycle loops). To > eliminate the possibility of using a degenerate cycle in practice, we > choose x[0] at random, take a step (thus skipping any lead-in), save > x[1], step again, and compare x[2] with x[1]. If x[2] == x[1] (which > almost never happens in practice, so we need to force that to check > the code), we choose another x[0] and start over. > > --- > Terry Ritter ritter@io.com http://www.io.com/~ritter/ > Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 11:24:57 -0400 From: Mixtim <Use-Author-Address-Header@[127.1]> Author-Address: mixtim <AT> home <DOT> com Message-ID: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 21 On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > So as long as you use double-safe primes the order of any element is huge > (assuming p' is about 384 bits the period will be around 2^383). > Now the good question: How likely is it to find such a doubly safe prime? I don't know how likely it is but the procedure isn't hard, just time consuming. Simply: 1. Pick a really big prime -- however many bits you want. 2. Multiply the prime by 2 and add 1. 3. Check that the number obtained in step 2 is a prime. If not then start over at step 1. 4. Multiply the new prime by 2 and add 1. 5. Check that the number obtained in step 4 is a prime. If not then start over at step 1. You now have one of the numbers you need (as any prime times 2 plus 1 is congruent to 3 mod 4). Yes it takes a while, but if you are writing an application for which this time is not significant then its ok.
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 18:22:04 +0100 From: "Mike Scott" <mscott@indigo.ie> Message-ID: <%f4Z6.10494$Fk7.94018@news.indigo.ie> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 34 You could speed this process up substantially by using trial division on all three numbers that need to be prime, to quickly eliminate the majority of "non-double-safe-primes". Only if all three pass this test will expensive primality testing be required Mike Scott "Mixtim" <Use-Author-Address-Header@[127.1]> wrote in message news:20010623112457.A45240@home.com... > On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > > So as long as you use double-safe primes the order of any element is huge > > (assuming p' is about 384 bits the period will be around 2^383). > > Now the good question: How likely is it to find such a doubly safe prime? > > I don't know how likely it is but the procedure isn't hard, just time > consuming. Simply: > > 1. Pick a really big prime -- however many bits you want. > 2. Multiply the prime by 2 and add 1. > 3. Check that the number obtained in step 2 is a prime. > If not then start over at step 1. > 4. Multiply the new prime by 2 and add 1. > 5. Check that the number obtained in step 4 is a prime. > If not then start over at step 1. > > You now have one of the numbers you need (as any prime times 2 plus 1 > is congruent to 3 mod 4). > > Yes it takes a while, but if you are writing an application for which > this time is not significant then its ok.
Subject: Re: BBS and safe primes Date: Sat, 23 Jun 2001 20:12:30 +0200 From: "Cristiano" <cristiano.p@mclink.it> Message-ID: <9h2mbs$m11$1@news.mclink.it> References: <q12Z6.7939$Mf5.2479512@news3.rdc1.on.home.com> Newsgroups: sci.crypt Lines: 52 "Tom St Denis" <tomstdenis@yahoo.com> wrote: > Now the good question: How likely is it to find such a doubly safe prime? The code proposed by Mixtim works but it is terribly slow. I wrote code to find p1=p2*2+1 and p=p1*2+1 (p, p1 and p2 primes; do you have read the paper by Thierry Moreau?). I suggest to initialize to one 3 vectors of size n, 2*n and 4*n (n depend on platform and on size of p). Then set to zero the numbers wich are divisible for small primes (also this limit depend on platform). Now we can check with Miller-Rabin test the numbers with flag to 1. MR test should be done with primes bases and random numbers bases. I hope the following c++ code will be a little bit more explanatory (xi is the starting point, T is the numbers of iterations for MR test): void FIND_BBS(Big &xi,const int T) { const unsigned SS=10000,SSb=SS*32; ULONG *const b1=new ULONG[SS],*const b2=new ULONG[2*SS],*const b3=new ULONG[4*SS]; while(1) { memset(b1,255,SS*4); memset(b2,255,2*SS*4); memset(b3,255,4*SS*4); for(unsigned i=0;i<mip->npri;i++) { const unsigned p=mip->PRIMES[i]; unsigned r=xi%p; if(r) r=p-r; while(r<SSb) { set_bit(r,0,b1); r+=p; } r=(xi*2+1)%p; if(r) r=p-r; while(r<2*SSb) { set_bit(r,0,b2); r+=p; } r=(xi*4+3)%p; if(r) r=p-r; while(r<4*SSb) { set_bit(r,0,b3); r+=p; } } for(int i=0;i<SSb;i++) { if(get_bit(i,b1)) if(get_bit(i*2,b2)) if(get_bit(i*4,b3)) { if(MR(xi,2)) if(MR(xi*2+1,2)) if(MR(xi*4+3,T)) if(MR(xi,T)) if(MR(xi*2+1,T)) { delete[] b1; delete[] b2; delete[] b3; return; } } ++xi; } } } If SS and mip->npri will have regulated well, we will get the fastest code that I know. Cristiano
Subject: Re: BBS and safe primes Date: Sun, 24 Jun 2001 01:56:14 +0300 From: Fat Phil <fatphil_without_this_suffix@altavista.com> Message-ID: <3B351E8E.5A7DC67B@altavista.com> References: <20010623112457.A45240@home.com> Newsgroups: sci.crypt Lines: 50 Mixtim wrote: > > On Sat, Jun 23, 2001 at 02:51:02PM +0000, Tom St Denis wrote: > > So as long as you use double-safe primes the order of any element is huge > > (assuming p' is about 384 bits the period will be around 2^383). > > Now the good question: How likely is it to find such a doubly safe prime? > > I don't know how likely it is but the procedure isn't hard, just time > consuming. Simply: > > 1. Pick a really big prime -- however many bits you want. > 2. Multiply the prime by 2 and add 1. > 3. Check that the number obtained in step 2 is a prime. > If not then start over at step 1. > 4. Multiply the new prime by 2 and add 1. > 5. Check that the number obtained in step 4 is a prime. > If not then start over at step 1. > > You now have one of the numbers you need (as any prime times 2 plus 1 > is congruent to 3 mod 4). > > Yes it takes a while, but if you are writing an application for which > this time is not significant then its ok. There is a program, initially called "PrimeForm", now called "PFGW", which can find numbers that satisfy these conditions trivially. www.primeform.net should get you to a site where it can be downloaded. Look up "ABC2" file formats in the documentation, and start with something like the following: <<< ABC2: (2^768+2*$a+1) & (2^769+4*$a+3) & (2^770+8*$a+7) a in 1 to 1000000 >>> Run it with -f and it will trial factor first (which makes a lot of sense as most of the above will have small factors. It then does an incredibly fast SPRP (strong probable primality test). I used it to find the my 1800-digit 'illegal prime'. It found the PRP in only a few minutes (though the formal Elliptic Curve Primality Proof took several weeks). For tiny primes (such as 384 bits) an individual PRP should take bugger all time, but finding the combination of three primes will be substantially harder (about 1 in 10million tests?). Presieving and using an "ABC file" rather than an "ABC2 file" is another possibility. Phil
Subject: Re: Q: Internet banking Date: 9 Jul 2001 00:40:03 -0000 From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> Message-ID: <20010709004003.22385.qmail@nym.alias.net> References: <3B48A275.DDA62121@arcormail.de> Newsgroups: sci.crypt Lines: 31 Mixtim writes: > On Sun, Jul 08, 2001 at 07:00:05PM -0000, lcs Mixmaster Remailer wrote: > > (And by the way, the reductions and proofs make no assumptions about > > special primes, they are for ordinary RSA primes. Choosing special primes > > does not increase the proven security of BBS at all. If someone wishes > > to deny this, let them give the specific formula for the greater security > > that is obtained with special primes. How many additional calls to the > > BBS oracle are necessary to achieve a specific factoring or QR attack? > > How much additional work? Let them quantify the difference. They can't > > do it, because it can't be done. The claim that special primes are > > needed or helpful is nothing but handwaving and hot air.) > > You are only speaking of academic weaknesses. In practice, BBS > is quite strong. If you'd care to demonstrate a weakness then > feel free to try the following data. N is a product of two > "special" primes p and q. It is represented here as a base 16 > number. The uuencoded data following N is the first 1020 bytes > from a BBS using N and a random starting X that was 640 bits long. > What are the next 4 bytes of the sequence? Of course the sequence is not predictable. The point is, why did you use "special" primes? They are not necessary. They do not add any security to your system. All of the BBS proofs which give us reason to trust it are based on ordinary primes, not special ones. There is no reason to use special primes. It's not that special primes weaken it, as you seemed to be reading the comment; it's that they fail to strengthen BBS, hence they are not necessary. Those who spread the misinformation that BBS requires special primes make people think it's a lot more complicated than it is.
Subject: Re: Q: Internet banking Date: Mon, 09 Jul 2001 04:30:23 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b49334b.4281079@news.io.com> References: <20010709004003.22385.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 69 On 9 Jul 2001 00:40:03 -0000, in <20010709004003.22385.qmail@nym.alias.net>, in sci.crypt lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> wrote: >Mixtim writes: >> On Sun, Jul 08, 2001 at 07:00:05PM -0000, lcs Mixmaster Remailer wrote: >> > (And by the way, the reductions and proofs make no assumptions about >> > special primes, they are for ordinary RSA primes. Choosing special primes >> > does not increase the proven security of BBS at all. If someone wishes >> > to deny this, let them give the specific formula for the greater security >> > that is obtained with special primes. How many additional calls to the >> > BBS oracle are necessary to achieve a specific factoring or QR attack? >> > How much additional work? Let them quantify the difference. They can't >> > do it, because it can't be done. The claim that special primes are >> > needed or helpful is nothing but handwaving and hot air.) >> >> You are only speaking of academic weaknesses. In practice, BBS >> is quite strong. If you'd care to demonstrate a weakness then >> feel free to try the following data. N is a product of two >> "special" primes p and q. It is represented here as a base 16 >> number. The uuencoded data following N is the first 1020 bytes >> from a BBS using N and a random starting X that was 640 bits long. >> What are the next 4 bytes of the sequence? > >Of course the sequence is not predictable. > >The point is, why did you use "special" primes? They are not necessary. >They do not add any security to your system. All of the BBS proofs which >give us reason to trust it are based on ordinary primes, not special ones. >There is no reason to use special primes. > >It's not that special primes weaken it, as you seemed to be reading >the comment; it's that they fail to strengthen BBS, hence they are >not necessary. Those who spread the misinformation that BBS requires >special primes make people think it's a lot more complicated than it is. There is a very good reason to use the special primes construction as given in the original BB&S article: Failing to use the special primes construction creates a -- admittedly tiny -- possibility that usefully short cycles may exist and may be selected at random. And if that should happen, the proven secure generator is not secure. Yet the whole point of using BB&S is to end up with a secure generator. By using the special primes construction, the only possible "short" cycles are shown to be either degenerate or "long enough." It is easy to check that any seed we select at random is not on a degenerate cycle, and that is cheap and easy proof that we are not enabling that particular weakness. Yes, the probability of selecting a short cycle is very, very low. But short cycles are the "weak keystreams" of BB&S. And it is not entirely unknown for crypto implementors to explicitly avoid weak keys, even if a mathematician might think such keys would "never" be encountered. Never is a very long time. I claim that avoiding weak keys does in fact "strengthen" BB&S by avoiding the possibility that a weak key might be used. Furthermore, since that is raw fact, the only possible debate is over how useful that strengthening really is. And since the issue may include both confidence for the user and professional pride for the designer, I doubt mathematics can resolve it. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: 9 Jul 2001 20:20:44 -0000 From: lcs Mixmaster Remailer <mix@anon.lcs.mit.edu> Message-ID: <20010709202044.1740.qmail@nym.alias.net> References: <3b49334b.4281079@news.io.com> Newsgroups: sci.crypt Lines: 34 Terry Ritter writes: > I claim that avoiding weak keys does in fact "strengthen" BB&S by > avoiding the possibility that a weak key might be used. Furthermore, > since that is raw fact, the only possible debate is over how useful > that strengthening really is. And since the issue may include both > confidence for the user and professional pride for the designer, I > doubt mathematics can resolve it. But if it does strengthen BBS, then you should be able to quantify the degree of strengthening. We can, after all, quantify the strength of BBS, at least in principle. We can show how many calls to the BBS prediction oracle are necessary to have a given chance of factoring N. This is the basis for our belief in the strength of BBS. There is no reason for debate. It is not a subjective issue where user confidence and professional pride enter into it. This is mathematics. Either you can strengthen BBS or not. We can calculate numerically how strong BBS is, in terms of numbers of oracle calls to break the modulus. If your method strengthens it, it should lead to a larger numerical estimate of that strength. You need to tell us what that number is, for people to judge whether the additional expense of generating special primes is worth it. Imagine a bridge made of steel. We have calculated its strength numerically. Now a magician proposes to put a magic spell on it to make it stronger. The designer is skeptical and asks him to calculate how many more tonnes of traffic it can hold. The magician claims this will increase user confidence and add professional pride, but that mathematics cannot resolve it. Who is more convincing, the one who relies on mathematics, or the one who says that the strength of a construction (cryptographic or mechanical) cannot be resolved mathematically?
Subject: Re: Q: Internet banking Date: Mon, 9 Jul 2001 22:07:59 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9id9vv$1bog$2@agate.berkeley.edu> References: <20010709202044.1740.qmail@nym.alias.net> Newsgroups: sci.crypt Lines: 29 lcs Mixmaster Remailer wrote: >But if it does strengthen BBS, then you should be able to quantify >the degree of strengthening. I would say something that is just a little less strong. Namely: The whole point of BBS is to get something that is provably strong. If you don't care about provably strong, we've got constructions that are far better than BBS. However, my understanding about why Ritter likes BBS is because he is not willing to accept anything less than a proof as evidence of security. Therefore, if he is considering some extension to BBS (such as "only use strong primes") that adds no provable strength---i.e., where we don't have any proof that it adds strength---I see no point to add it. In the absence of a proof that the extension adds strength, you might as well omit it, if all you care about is what can be proven. If you're worried that the version without the extension might be insecure, then maybe you should be just as worried that the version with the extension is insecure, too: after all, we have no proof that the extended version is any better than the unextended version. Now if what you want is heuristic security, possibly because you want to use the darn thing in practice and you want to minimize the likelihood that it gets broken as much as possible, then you might be willing to combine both techniques that have some proven properties and techniques with no proven properties. However, I *believe* Ritter's position is that we have no good reason to trust things without proven properties, so this doesn't apply. I hope he'll correct me if I'm mis-stating his position.
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 05:10:36 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4a8e48.8894712@news.io.com> References: <9id9vv$1bog$2@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 155 On Mon, 9 Jul 2001 22:07:59 +0000 (UTC), in <9id9vv$1bog$2@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >lcs Mixmaster Remailer wrote: >>But if it does strengthen BBS, then you should be able to quantify >>the degree of strengthening. > >I would say something that is just a little less strong. > >Namely: The whole point of BBS is to get something that is provably >strong. That is what the designer and user care about, yes. There would seem to be no other point to use awkward and slow BB&S. >If you don't care about provably strong, we've got constructions >that are far better than BBS. However, my understanding about why Ritter >likes BBS is because he is not willing to accept anything less than a >proof as evidence of security. Actually, I am just not willing to have mathematicians claim "proven secure" to designers and users without extensive caveats. And if designers and users do buy into the "proven secure" we have (again, there being no other reason for using BB&S), then the actual design should reflect a real attempt to eliminate all known weakness, as users expect a mathematical proof to do automatically. As far as I know, the sole known *weakness* of BB&S is the existence and possible use of short cycles, especially in the ordinary construction. This flaw was eliminated in the original BB&S article with modest front-end cost, but high per-use cost. It now turns out that we can do the same thing at negligible per-use cost. Merely by using the special primes construction from the BB&S article, all "short" cycles are known to be "long enough" for use except degenerate cycles, which we can easily test with just a couple of steppings. The usual mathematical spin on this is that the security improvement thus gained is so modest as to be lost in the asymptotic results. However, we have actual experience with what users expect perfection to mean: The original Intel Pentium design also had a flaw. Very rarely, it would produce incorrect arithmetic results. It was such an unlikely flaw that it hardly every occurred. (Already we see the correspondence with BB&S short cycles which are hardly ever selected.) Intel argued that such a very unlikely flaw was no flaw at all. (Just as mathematical cryptographers now argue that choosing short cycles is so unlikely that it can be ignored.) Intel thus concluded that there was no need to replace the faulty Pentiums. Alas, their customers felt differently. Large technical companies like IBM and various accounting firms also felt differently. Eventually, Intel changed their position. As Intel learned, the issue was not actual wrong answers, but instead lack of confidence. Just as it is in BB&S. >Therefore, if he is considering some >extension to BBS (such as "only use strong primes") that adds no provable >strength---i.e., where we don't have any proof that it adds strength---I >see no point to add it. If you do not see that avoiding the use of short cycles improves (statistical) strength, you have your sums wrong. The improvement is indisputable. The only issue is whether the amount of improvement is useful, and the interpretation of "useful" depends upon the cost of the improvement, and the outlook of the designer and user. We have just covered that. >In the absence of a proof that the extension adds strength, There is no such absence. >you might >as well omit it, if all you care about is what can be proven. That is what users want, but not what they get. >If you're >worried that the version without the extension might be insecure, then >maybe you should be just as worried that the version with the extension >is insecure, too: after all, we have no proof that the extended version >is any better than the unextended version. I guess it's "turtles all the way down," again, which does not apply to my position this time any more than it did the last. Proof of strength in practice is not available, so I could hardly demand it, now could I? If and when that changes we will have a brave new world. For now, we are constrained to follow the same path that the entire previous history of cryptography has followed before us. Which is to say: no such proof. Nevertheless, the existence of new mathematical "security proofs" has reached the ears of the user. They are impressed. Eventually this may have negative repercussions, as users are informed that they are not getting what they expected, but for now some want proofs. That is the reason for using BB&S. And an implementation which achieves what the original BB&S article describes is more trustworthy and deserves more confidence than the simplified modern version even if that is asymptotically just as secure. >Now if what you want is heuristic security, possibly because you want >to use the darn thing in practice and you want to minimize the likelihood >that it gets broken as much as possible, then you might be willing to >combine both techniques that have some proven properties and techniques >with no proven properties. I think that would be a different issue than we discuss here. >However, I *believe* Ritter's position is that >we have no good reason to trust things without proven properties, Taken alone, that is a correct statement of one position. I'm not sure how that relates to BB&S, however. I think all of cryptography needs to address the implications of the absence of the feedback which is normal in all other areas of design and manufacture. Absent proof and absent feedback (since the opponents do not tell us what successes they have), we can have no idea whether or not our ciphers accomplish what we want them to do. Our situation is not necessarily hopeless: I think steps *can* be taken to improve things. In particular we can introduce the common use of multi-ciphering with independent keys, and selection from among different ciphers on a message-by-message basis, both of which are inspired by Shannon. The intent is not to provide the missing proof, but instead to protect against particular kinds of potential fault. But none of that will occur until there is a general realization that we have a design problem created by a lack of real feedback. >so this >doesn't apply. Having looked at the OTP and found it wanting, and having looked at BB&S and found that wanting, I don't expect cryptographic "proven strength" to apply in practice, no. >I hope he'll correct me if I'm mis-stating his position. I do try. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 06:14:07 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9ie6ff$27bs$1@agate.berkeley.edu> References: <3b4a8e48.8894712@news.io.com> Newsgroups: sci.crypt Lines: 34 Terry Ritter wrote: >As far as I know, the sole known *weakness* of BB&S is the existence >and possible use of short cycles, especially in the ordinary >construction. As others have observed, this is only a weakness if factoring is easy, and we have to assume that factoring is hard anyway if we want to use BB&S. Since this has been discussed at length before, I'll leave it at that. >The usual mathematical spin on this is that the security improvement >thus gained is so modest as to be lost [...] >The original Intel Pentium design also had a flaw. Very rarely, it >would produce incorrect arithmetic results. It was such an unlikely >flaw that it hardly every occurred. (Already we see the >correspondence with BB&S short cycles which are hardly ever selected.) The analogy is flawed. For floating point arithmetic, we can build algorithms whose answers are guaranteed 100% correct (of course implementation can introduce flaws, but the algorithms themselves have zero chance of an error). In cryptography, we cannot. There is always an epsilon chance that a single lucky guess at the key will succeed, breaking the system. This is a fundamental and unavoidable property of computational-based cryptography. Therefore, it is unreasonable to ask for zero chance of being broken---such a request would be impossible to satisfy. I agree that this is the natural first thing to think of asking for, but when you realize that this is unattainable, then you have to set your sights a little bit lower. Fortunately, what is attainable appears to be quite satisfactory for all practical purposes. Therefore, it is reasonable to ask Intel to use floating point algorithms that have a zero chance of error, but it is not reasonable to ask crypto manufacturers to provide crypto algorithms that have a zero chance of being broken.
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 06:36:27 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4aa25a.14033453@news.io.com> References: <9ie6ff$27bs$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 74 On Tue, 10 Jul 2001 06:14:07 +0000 (UTC), in <9ie6ff$27bs$1@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>As far as I know, the sole known *weakness* of BB&S is the existence >>and possible use of short cycles, especially in the ordinary >>construction. > >As others have observed, this is only a weakness if factoring is easy, >and we have to assume that factoring is hard anyway if we want to use BB&S. If a short cycle happens to be selected, that allows factoring. What the proof means to me is that, asymptotically, it is at least as hard to find a short cycle as it is to factor N. But "finding a short cycle" is not and has never been the issue. Short cycles do exist and *may* be selected. This is equivalent to accidentally using a weak key, and is a preventable weakness. Checking for and not using weak keys is hardly unknown. We do *not* have to believe the math or assume factoring is hard to address the use of short cycles. Instead, we can actually prevent that use, and at reasonable cost. >Since this has been discussed at length before, I'll leave it at that. > >>The usual mathematical spin on this is that the security improvement >>thus gained is so modest as to be lost [...] >>The original Intel Pentium design also had a flaw. Very rarely, it >>would produce incorrect arithmetic results. It was such an unlikely >>flaw that it hardly every occurred. (Already we see the >>correspondence with BB&S short cycles which are hardly ever selected.) > >The analogy is flawed. For floating point arithmetic, we can build >algorithms whose answers are guaranteed 100% correct (of course >implementation can introduce flaws, but the algorithms themselves have >zero chance of an error). In cryptography, we cannot. There is always >an epsilon chance that a single lucky guess at the key will succeed, >breaking the system. This is a fundamental and unavoidable property of >computational-based cryptography. Therefore, it is unreasonable to ask >for zero chance of being broken---such a request would be impossible >to satisfy. I agree that this is the natural first thing to think of >asking for, but when you realize that this is unattainable, then you have >to set your sights a little bit lower. Fortunately, what is attainable >appears to be quite satisfactory for all practical purposes. > >Therefore, it is reasonable to ask Intel to use floating point algorithms >that have a zero chance of error, but it is not reasonable to ask crypto >manufacturers to provide crypto algorithms that have a zero chance of >being broken. The analogy stands. Intel does not claim (in more than a marketing sense) that no error exists in their chips. I believe the arithmetic logic has been checked, but even that could be wrong. No, the issue was never that Intel should make a provably error-free chip. The issue was that an error was found, and that Intel dismissed the known flaw as meaningless because it was very rare. That is the same issue as BB&S. In practice, it is unreasonable to expect a zero chance of fault. But we can hope that no *known* fault will be allowed to exist. The existence and possible use of short cycles in BB&S is a known fault which fortunately can be eliminated at minimal cost -- or not. Allowing that fault to exist is exactly the issue Intel encountered. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 07:55:01 +0000 (UTC) From: daw@mozart.cs.berkeley.edu (David Wagner) Message-ID: <9ieccl$2cts$1@agate.berkeley.edu> References: <3b4aa25a.14033453@news.io.com> Newsgroups: sci.crypt Lines: 28 Terry Ritter wrote: >But "finding a short cycle" is not and has never been the issue. >Short cycles do exist and *may* be selected. This is equivalent to >accidentally using a weak key, and is a preventable weakness. >Checking for and not using weak keys is hardly unknown. Right. But using the prime 1208923250890892301 is a possibility and it may be selected; when it is selected, the adversary will be able to break our system. This means that any RSA modulus that has this as a factor is a weak key. Therefore, we should add a special tweak to our implementation to double-check that we're not using one of these weak keys, i.e., we're not using this prime as a factor of our RSA modulus. Checking for and not using weak keys is hardly unknown. We do *not* have to believe the math or assume factoring is hard to address the use of this class of weak keys. Instead, we can actually address that use, and at reasonable cost. The logic seems indisputable. We'd better fix all implementations to check for this prime, and post haste! Surely you must agree. Right? (P.S. Ok, ok, most likely the number I gave isn't actually prime. I didn't bother checking. Don't complain to me if it isn't! Just humor me and pretend this is an example of some randomly chosen prime. I'm too lazy to generate a real prime of the right length.)
Subject: Re: Q: Internet banking Date: Tue, 10 Jul 2001 18:44:05 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4b4cce.8097446@news.io.com> References: <9ieccl$2cts$1@agate.berkeley.edu> Newsgroups: sci.crypt Lines: 54 On Tue, 10 Jul 2001 07:55:01 +0000 (UTC), in <9ieccl$2cts$1@agate.berkeley.edu>, in sci.crypt daw@mozart.cs.berkeley.edu (David Wagner) wrote: >Terry Ritter wrote: >>But "finding a short cycle" is not and has never been the issue. >>Short cycles do exist and *may* be selected. This is equivalent to >>accidentally using a weak key, and is a preventable weakness. >>Checking for and not using weak keys is hardly unknown. > >Right. But using the prime 1208923250890892301 is a possibility >and it may be selected; when it is selected, the adversary will be >able to break our system. This means that any RSA modulus that has >this as a factor is a weak key. Therefore, we should add a special >tweak to our implementation to double-check that we're not using one >of these weak keys, i.e., we're not using this prime as a factor of >our RSA modulus. Checking for and not using weak keys is hardly >unknown. We do *not* have to believe the math or assume factoring >is hard to address the use of this class of weak keys. Instead, we >can actually address that use, and at reasonable cost. > >The logic seems indisputable. We'd better fix all implementations >to check for this prime, and post haste! Surely you must agree. >Right? No. You describe a brute force break: finding the key (in this case a factor) by "luck," at random. That cannot be avoided in any system which uses a key. In contrast, short cycles are weakness *in* *addition* to the chance of finding the right key. Short cycles thus make the system weaker than brute force. This may be a tiny additional weakness, but it can be avoided, and at reasonable cost. There is nothing wrong with a desire to provably reduce weakness; it is certainly not worthy of ridicule. Deciding whether designers and users should pay what it costs to remove a weakness is not a mathematical issue. That is a designer and user decision based on their goals and costs. >(P.S. Ok, ok, most likely the number I gave isn't actually prime. >I didn't bother checking. Don't complain to me if it isn't! Just >humor me and pretend this is an example of some randomly chosen prime. >I'm too lazy to generate a real prime of the right length.) --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM Organisation: The Clue Factory
Subject: Re: Q: Internet banking Date: Thu, 12 Jul 2001 05:34:47 GMT From: Paul Crowley <paul@JUNKCATCHER.cluefactory.org.uk> Message-ID: <874rsju6sx.fsf@saltationism.subnet.hedonism.cluefactory.org.uk> References: <3b4b4cce.8097446@news.io.com> Newsgroups: sci.crypt Lines: 14 ritter@io.com (Terry Ritter) writes: > You describe a brute force break: finding the key (in this case a > factor) by "luck," at random. That cannot be avoided in any system > which uses a key. No, he isn't. He's describing an attack based on testing for the specific prime that he named. The prime is named in advance; it's possible for the BBS implementation to test for that specific prime and avoid using it. -- __ Paul Crowley \/ o\ sig@paul.cluefactory.org.uk /\__/ http://www.cluefactory.org.uk/paul/ "Conservation of angular momentum makes the world go around" - John Clark
Subject: Re: Q: Internet banking Date: Thu, 12 Jul 2001 21:37:15 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4e186c.2192247@news.io.com> References: <874rsju6sx.fsf@saltationism.subnet.hedonism.cluefactory.org.uk> Newsgroups: sci.crypt Lines: 46 On Thu, 12 Jul 2001 05:34:47 GMT, in <874rsju6sx.fsf@saltationism.subnet.hedonism.cluefactory.org.uk>, in sci.crypt Paul Crowley <paul@JUNKCATCHER.cluefactory.org.uk> wrote: >ritter@io.com (Terry Ritter) writes: >> You describe a brute force break: finding the key (in this case a >> factor) by "luck," at random. That cannot be avoided in any system >> which uses a key. > >No, he isn't. He's describing an attack based on testing for the >specific prime that he named. The prime is named in advance; it's >possible for the BBS implementation to test for that specific prime >and avoid using it. And yet you did not retain the issue in your quote so we could all see it and come to a conclusion. Why is that? Referring back, I see that my comment was charitably on target. The primes and the "seed" are the key in a BB&S system. In any system where we have a key, the opponent may guess the key. Guessing the key *is* brute force, even if one just waits for the key to come up. (And it may not, since N is often retained and re-used.) There must always be a key, but short cycles need *not* be available for selection or use. Short cycles thus represent *additional* weakness, beyond the simple existence of a key. And we can act to eliminate this added weakness at modest or even trivial cost. This is not rocket science: * Weak short cycles do exist in BB&S. * Weak cycles can be completely avoided by using the special primes construction and then checking that we have not selected a degenerate cycle. * In any system which seeks *guaranteed* strength, the existence of known uncorrected faults is disturbing. So the modest cost of avoiding weak keys is hardly an unreasonable design. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 11:13:22 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3B4F2C32.F4F48949@sandia.gov> References: <3b4e186c.2192247@news.io.com> Newsgroups: sci.crypt Lines: 36 Terry Ritter wrote: <snip> > This is not rocket science: > > * Weak short cycles do exist in BB&S. Ok. > * Weak cycles can be completely avoided by using the special primes > construction and then checking that we have not selected a degenerate > cycle. Ok. > * In any system which seeks *guaranteed* strength, the existence of > known uncorrected faults is disturbing. So the modest cost of > avoiding weak keys is hardly an unreasonable design. It seems unreasonable to me unless and until one provides a reason to believe that the improvement stands a chance of being worth the cost. I think it is central to this debate that the nature of the strength "guarantee" is clear. It is certainly not true that BB&S is guaranteed not to be breakable, period. Instead, we have that breaking (a given) BB&S has a certain probability. Using the special primes construction will change the probability by some amount. Neither you nor those who have disagreed with you have shown an actual computation of the improvement in probability. Thus, an implementor is left with choosing whose faith to believe. It's not "is the improvement non-zero?", but "how much is it worth?" Even a "modest" cost can sometimes be too much. JM
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 19:39:40 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B4F325C.19F4C1BC@t-online.de> References: <3B4F2C32.F4F48949@sandia.gov> Newsgroups: sci.crypt Lines: 36 John Myre wrote: > > Terry Ritter wrote: > > * In any system which seeks *guaranteed* strength, the existence of > > known uncorrected faults is disturbing. So the modest cost of > > avoiding weak keys is hardly an unreasonable design. > > It seems unreasonable to me unless and until one provides > a reason to believe that the improvement stands a chance of > being worth the cost. > > I think it is central to this debate that the nature of the > strength "guarantee" is clear. It is certainly not true that > BB&S is guaranteed not to be breakable, period. Instead, we > have that breaking (a given) BB&S has a certain probability. > Using the special primes construction will change the > probability by some amount. > > Neither you nor those who have disagreed with you have shown > an actual computation of the improvement in probability. Thus, > an implementor is left with choosing whose faith to believe. > It's not "is the improvement non-zero?", but "how much is it > worth?" Even a "modest" cost can sometimes be too much. If one wants to rely on the extremely small probability of encountering degenerate cycles, then I believe one has to know that these are sufficiently 'randomly' distributed, i.e. not clustered in some zones which a user with bad luck might step into. I asked about the question of distribution, but haven't yet got an answer. M. K. Shen
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 19:27:21 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b4f4ae4.7581659@news.io.com> References: <3B4F2C32.F4F48949@sandia.gov> Newsgroups: sci.crypt Lines: 104 On Fri, 13 Jul 2001 11:13:22 -0600, in <3B4F2C32.F4F48949@sandia.gov>, in sci.crypt John Myre <jmyre@sandia.gov> wrote: >Terry Ritter wrote: ><snip> >> This is not rocket science: >> >> * Weak short cycles do exist in BB&S. > >Ok. > >> * Weak cycles can be completely avoided by using the special primes >> construction and then checking that we have not selected a degenerate >> cycle. > >Ok. > >> * In any system which seeks *guaranteed* strength, the existence of >> known uncorrected faults is disturbing. So the modest cost of >> avoiding weak keys is hardly an unreasonable design. > >It seems unreasonable to me unless and until one provides >a reason to believe that the improvement stands a chance of >being worth the cost. All this isn't about *you*: It isn't up to you to decide for everybody else. I consider the tradeoff to be beyond "reasonable" to "necessary." >I think it is central to this debate that the nature of the >strength "guarantee" is clear. It is certainly not true that >BB&S is guaranteed not to be breakable, period. Sadly, correct. >Instead, we >have that breaking (a given) BB&S has a certain probability. I'm not sure we really do have that probability, per se. Perhaps if we had such an expression we could begin to see the numerical security consequences of the expected wild variations in cycle structure in the casual construction. In my view, it is not useful to simply have a mean value; indeed, the worst case (e.g., the shortest non-degenerate cycle) is usually most appropriate to cryptography. And, in a sense, the longer a "short cycle" is, the more trouble it is (the more likely it is to be selected at random), until the cycle length becomes "long enough" and it is no longer a threat. >Using the special primes construction will change the >probability by some amount. The special primes construction was the construction in the original BB&S article. Do you have a problem with that? >Neither you nor those who have disagreed with you have shown >an actual computation of the improvement in probability. *Of* *course* I have shown "an actual computational improvement in probability." There is some probability of fault in the special primes construction. That probability includes short cycle faults. I take away the short cycle faults. The resulting probability of fault is less. QED. Unfortunately, the proof is disturbingly silent about the actual probability of flaws, and about the types of flaws that remain in either construction. As long as the math is silent on the details, we are left with "whatever weak cycles might have existed in the casual construction have been eliminated," instead of "the probability of weakness is z." >Thus, >an implementor is left with choosing whose faith to believe. Such is always the case when the conventional wisdom is wrong. >It's not "is the improvement non-zero?", but "how much is it >worth?" Even a "modest" cost can sometimes be too much. Again, that comparison is not up to you. It is common and widely accepted in practice that in many things it is necessary to pay more the closer to perfection one comes. Since one cannot really hope for a "proven secure" cryptosystem to be actually "guaranteed fault free" in practice, the best one can do is to take the "proven secure" cryptosystem and eliminate the faults one can do something about. That may be the closest to perfection one can get, and there is usually an escalating cost to perfection. Those interested in perfection are often more than willing to pay. --- Terry Ritter ritter@io.com http://www.io.com/~ritter/ Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 14:59:56 -0600 From: John Myre <jmyre@sandia.gov> Message-ID: <3B4F614C.97307C55@sandia.gov> References: <3b4f4ae4.7581659@news.io.com> Newsgroups: sci.crypt Lines: 160 Terry Ritter wrote: <snip> > >> * In any system which seeks *guaranteed* strength, the existence of > >> known uncorrected faults is disturbing. So the modest cost of > >> avoiding weak keys is hardly an unreasonable design. I replied: > >It seems unreasonable to me unless and until one provides > >a reason to believe that the improvement stands a chance of > >being worth the cost. And Terry riposted: > All this isn't about *you*: It isn't up to you to decide for > everybody else. That sure *reads* like an insult. What's your point? > I consider the tradeoff to be beyond "reasonable" to > "necessary." You are certainly entitled to your opinion, as am I. > >I think it is central to this debate that the nature of the > >strength "guarantee" is clear. It is certainly not true that > >BB&S is guaranteed not to be breakable, period. > > Sadly, correct. > > >Instead, we > >have that breaking (a given) BB&S has a certain probability. > > I'm not sure we really do have that probability, per se. I don't mean we know the probability, I mean that we know that the security is probabalistic. The enemy has some definite chance (not zero) of breaking the scheme. > Perhaps if we had such an expression we could begin to see the > numerical security consequences of the expected wild variations in > cycle structure in the casual construction. Indeed. > In my view, it is not > useful to simply have a mean value; indeed, the worst case (e.g., the > shortest non-degenerate cycle) is usually most appropriate to > cryptography. And, in a sense, the longer a "short cycle" is, the > more trouble it is (the more likely it is to be selected at random), > until the cycle length becomes "long enough" and it is no longer a > threat. Quite so. It would also be helpful to know the probabilities of the various cycle lengths. To be concrete, suppose for the sake of argument that we knew, for the modulus size we have chosen, that a short cycle would occur one time in 2^400. I would argue that the chance of a short cycle occurring is therefore so small that the chance of a bug in the cycle-length-checking code introducing a fatal insecurity is greater, and we would thus be fools to include such code. Of course, the problem is, as you say, that such concrete facts are not abundant. > >Using the special primes construction will change the > >probability by some amount. > > The special primes construction was the construction in the original > BB&S article. Do you have a problem with that? A problem with what? Should I be using different terminology? > >Neither you nor those who have disagreed with you have shown > >an actual computation of the improvement in probability. > > *Of* *course* I have shown "an actual computational improvement in > probability." I mean, no one (to my knowledge) has computed what the difference in probability is. (You might compare what I said with what you put in quotes.) > There is some probability of fault in the special primes construction. > That probability includes short cycle faults. I take away the short > cycle faults. The resulting probability of fault is less. QED. Clearly one cannot disagree with that. > Unfortunately, the proof is disturbingly silent about the actual > probability of flaws, and about the types of flaws that remain in > either construction. As long as the math is silent on the details, we > are left with "whatever weak cycles might have existed in the casual > construction have been eliminated," instead of "the probability of > weakness is z." Exactly. > >Thus, > >an implementor is left with choosing whose faith to believe. > > Such is always the case when the conventional wisdom is wrong. Please. The reason for the problem is not who's wrong, but the lack of concrete, numerical values on which to base a judgement. > >It's not "is the improvement non-zero?", but "how much is it > >worth?" Even a "modest" cost can sometimes be too much. > > Again, that comparison is not up to you. It's up to somebody, in each case. Whoever that is, would like to know what the actual cost and actual benefit of using the special primes construction is. All you have ever said is that the benefit is positive, not zero. Almost no one has ever disagreed with that. The "conventional wisdom" is that the actual improvement in security with the inclusion of the special primes construction, as opposed to without, is small enough to be ignored. Your position, as I understand it, is that the improvement can be reasonably expected to be large enough not to be ignored. I have seen no particular reason to choose one over the other. > It is common and widely accepted in practice that in many things it is > necessary to pay more the closer to perfection one comes. > > Since one cannot really hope for a "proven secure" cryptosystem to be > actually "guaranteed fault free" in practice, the best one can do is > to take the "proven secure" cryptosystem and eliminate the faults one > can do something about. (Including faults introduced by adding extra features.) > That may be the closest to perfection one can > get, and there is usually an escalating cost to perfection. Those > interested in perfection are often more than willing to pay. My only problem with this is that, if someone is interested in perfection, they had better not mess with BB&S, in any configuration. You can eliminate short cycles, but that won't give you a system with perfect security. For that matter, the proof that BB&S is breakable only if we can factor (well, OK, decide quadratic reciduousity) was made *without* requiring the special primes construction. Which means that including the special primes construction does not add to the proven strength. What it does, is add some unknown amount of security. It may be worth the cost, in some or even all situations, to include the special primes construction. I just can't see that there's any way for a bystander to judge, except by appeal to authority (yours or others). JM
Subject: Re: Q: Internet banking Date: Fri, 13 Jul 2001 23:15:09 +0200 From: Mok-Kong Shen <mok-kong.shen@t-online.de> Message-ID: <3B4F64DD.AAB53A3B@t-online.de> References: <3B4F614C.97307C55@sandia.gov> Newsgroups: sci.crypt Lines: 47 John Myre wrote: > > Terry Ritter wrote: > <snip> > I replied: > > >It seems unreasonable to me unless and until one provides > > >a reason to believe that the improvement stands a chance of > > >being worth the cost. > > And Terry riposted: > > All this isn't about *you*: It isn't up to you to decide for > > everybody else. > > That sure *reads* like an insult. What's your point? As a third person, I would say that Terry Ritter didn't have an insult in mind. He meant that the cost issue is to be decided in each concrete case by the user of the application (and not us, who are only discussing in this group), I believe. [snip] > My only problem with this is that, if someone is interested > in perfection, they had better not mess with BB&S, in any > configuration. You can eliminate short cycles, but that won't > give you a system with perfect security. > > For that matter, the proof that BB&S is breakable only if > we can factor (well, OK, decide quadratic reciduousity) was > made *without* requiring the special primes construction. > Which means that including the special primes construction > does not add to the proven strength. What it does, is add > some unknown amount of security. > > It may be worth the cost, in some or even all situations, to > include the special primes construction. I just can't see > that there's any way for a bystander to judge, except by > appeal to authority (yours or others). I may be wrong, since my memory about the BBS paper is no longer good. Isn't it that the special primes construction is in the paper? M. K. Shen
Subject: Re: Q: Internet banking Date: Sun, 15 Jul 2001 07:20:32 GMT From: ritter@io.com (Terry Ritter) Message-ID: <3b51443d.7325968@news.io.com> References: <3B4F614C.97307C55@sandia.gov> Newsgroups: sci.crypt Lines: 187 On Fri, 13 Jul 2001 14:59:56 -0600, in <3B4F614C.97307C55@sandia.gov>, in sci.crypt John Myre <jmyre@sandia.gov> wrote: >Terry Ritter wrote: [...] >> >I think it is central to this debate that the nature of the >> >strength "guarantee" is clear. It is certainly not true that >> >BB&S is guaranteed not to be breakable, period. >> >> Sadly, correct. >> >> >Instead, we >> >have that breaking (a given) BB&S has a certain probability. The BB&S security proof is probabilistic. Weak degenerate cycles do always exist in BB&S constructions, so the proof clearly does not represent the worst case. Yet in practice we can and do judge cryptosystems by the worst known flaw. And if we do that here, the system strength is always almost zero unless we eliminate degenerate cycles and short cycles. >> I'm not sure we really do have that probability, per se. > >I don't mean we know the probability, I mean that we know >that the security is probabalistic. The enemy has some >definite chance (not zero) of breaking the scheme. So it's just OK to leave known flaws in the design when we can fix those flaws at minimal expense? I don't think so. BB&S is a slow huge-integer system, and is already vastly more costly than, say, the huge and nonlinearized RNG's I build (and which have no strength proof). Since there is already a huge cost involved, why would anyone not spend a little more to eliminate some *known* worst-case faults? >[...] >It would also be helpful to know the probabilities of the >various cycle lengths. To be concrete, suppose for the sake >of argument that we knew, for the modulus size we have chosen, >that a short cycle would occur one time in 2^400. As I understand it, the determining factor for cycle structure is not really modulus size per se, but rather the specific relationship between the primes. I expect the cycle structure to vary wildly even with a fixed modulus, unless both primes are special. Again, one might get some mean value for probability here, but what we want to know is worst-case weakness, not average strength. >I would >argue that the chance of a short cycle occurring is therefore >so small that the chance of a bug in the cycle-length-checking >code introducing a fatal insecurity is greater, and we would >thus be fools to include such code. It's not like we can avoid using computer code. Nor is it like we can improve system strength by using the simplest possible RNG (e.g., a counter). Some amount of complexity is necessary for good cryptography. Simply choosing BB&S also means complex huge-integer math code and the ability to check and select primes. This is vastly more machinery than needed for "simple" Additive RNG's. Are they thus "better"? I have seen no claim that we should not use BB&S at all because we cannot guarantee the implementation. No, the claim is instead that we should not fix *known* faults in BB&S because that *might* in