Ben Laurie wrote: > > gfgs pedo wrote: > > > > hi, > > > > --- [EMAIL PROTECTED] wrote: > > > On 22 Apr 2002 at 0:08, Ben Laurie wrote: > > > > > > Oh surely you can do better than that - making it > > > hard to guess the seed > > > > is also clearly a desirable property (and one that > > > the square root "rng" > > > > does not have). > > U can choose any arbitrary seed(greater than 100 bits > > as he (i forgot who) mentioned earlier.Then subject it > > to the Rabin-Miller test. > > Since the seed value is a very large number,it would > > be impossible to determine the actual value.The > > chances the intruder find the correct seed or the > > prime number hence generated is practically verly low. > > Uhuh - and how do you choose this large seed?
Suppose an attacker knows some of your outputs. The whole sitiuation can be written as three numbers: x = integer part of root plus unknown "random" bits previously generated y = "random" bits attacker knows z = future "random" bits Shift everything left until you get: root*10^a = x*10^b + y + z with z < 1 We may not know a since that depends on the number of x bits, but we do know b since that depends only on the number of y bits. squaring to find the prime: prime*10^2a = x^2 * 10^2b + y^2 + z^2 + 2xy*10^b + 2xz*10^b + 2yz which is obviously zero mod 2a, so all bits to the right of that are zero. So it's also zero mod 10^b, since b < 2a, and we get: mod 10^b 0 = y^2 + z^2 + 2yz with z^2 < 1 so for bits to the left of the decimal, we have: y^2 + 2yz = 0 mod 10^b and since y and b are known, this is easliy solved for some z bits. Iterate with y' = y + discovered z bits. Methinks this is a fatal weakness, irrespective of the size of the prime.