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.
