Re: EC-PRNG

From: Décio Luiz Gazzoni Filho (decio_at_decpp.removethis.net)
Date: 02/04/05 

Date: Thu, 03 Feb 2005 23:00:34 -0200

Cristiano wrote:

> Décio Luiz Gazzoni Filho wrote:
>> <snip>
>
> The order of a curve in F_p (which can be written as #E(F_p)) is an even
> number because there is also O.

That's why you compute the group order already taking the point at infinity
into account. If you don't, then you get a curve of order n-1, not n as you
wanted.

> The order of any other point is a divisor of #E(F_p).

I know that, I've mentioned it before in a previous post.

> See, for example this curve in F_23:
> y^2 = x^3 + x + 1 (mod 23)
> the point (0,1) has order 28, the point (6,4) has order 14, the point
> (4,0) has order 2.
> So I don't understand what you're trying to say.

Just pick a curve of prime order. Try y^2 + x^3 + x + 4 (mod 29). It has 29
points: the point at infinity plus
(0,2), (0,21), (1,11), (1,12), (4,7), (4,16), (7,3)
(7,20), (8,8), (8,15), (9,11), (9,12), (10,5), (10,18),
(11,9), (11,14), (13,11), (13,12), (14,5), (14,18), (15,6),
(15,17), (17,9), (17,14), (18,9), (18,14), (22,5), (22,18).

That's a total of 29 points. You can check (I did, using PARI/GP) that
picking a point P at random from any of the 28 points listed (excepting the
point at infinity, of course) and computing 1*P, 2*P, 3*P, ..., 27*P, 28*P,
you'll never arrive at the point at infinity. Now, for each of them,
computing 29*P will give the point at infinity as an answer. I hope that
was clear.

If you were using curves of non-prime order (like the one you described
above) in your generator, then biases are indeed more likely, though I
believe the probability is still negligible. Could you please provide me
the curve, point and value of k you used in the run which was flagged by
RaBiGeTe as having biases? That way I can check whether biases were
expected.

>> <snip>
>
> When I write a crypto application, I must be sure that all the "objects"
> are good. No matter how small the probability of the step 3c is; it cost
> nothing and if I don't have in mind any better... :-)

No offense meant, but you appear to share the inability of evaluating
ludicrously small probabilities with the crackpots who came up with the
distributed computing project called `The Neo Project'.

>> Now if you're really that worried, I'd just check that k is a
>> primitive root of (Z/nZ)*, or at least an element of high order,
>> right after step 1. Better than performing a check on every iteration
>> of the loop.
>
> Agreed, but afaik it is not as trivial as the step 3c.

That depends on the library you're using, of course. If you were using PARI,
for instance, this could be done through a single library call.

>>> <snip>
>>>
>>> Where did you find the above algorithm? I don't understand anything
>>> in that paper! :-)
>>
>> See section 7.1 (theorem 33) and section 7.2 (lemma 34). In
>> particular I believe equation 47 describes step 3a, and equation 49
>> describes step 3b.
>
> Ah! It seems you're right.
>
> Unfortunately, also in this case there is a big "degeneration problem" and
> this one seems much worse than the other (k^i = k mod n).
> Also in this case consider the curve in F_23.
> I take the generator G= (0,1) (of order 28, the maximum order) and k= 3.
> Q_0 = 3 * (0,1) = (3,13)
> and this is the sequence generated:
> (9,16) (17,3) (3,13) (9,16) (17,3) (3,13) (9,16) (17,3) (3,13)
> (9,16)
> (17,3) (3,13) (9,16) (17,3) (3,13) (9,16) (17,3) (3,13) (9,16)
> (17,3)
> (3,13) (9,16) (17,3)
> as you can see the sequence degenerates very quickly (I seen the same with
> many point on several curves).

I invoke the law of small numbers
(http://mathworld.wolfram.com/StrongLawofSmallNumbers.html). This should be
a non-issue for a 112-bit curve, particularly if the curve has prime order
(have a look at my comments above.) Of course, I'm assuming there is,
somewhere, an analysis of the security of Kaliski's scheme; otherwise,
Donald Knuth's quote about not using random methods to generate random
numbers applies -- by the way, TAOCP v.2 has a nice example of a
degenerating PRNG which uses `random methods'.

> The statistical tests say that the sequence is good (I tested about 39
> Mbits).
> Perhaps also in this case the probability to see a degenerating sequence
> is very small (as you said in a message).

Personally I'd think it's harder to analyze; but I haven't looked at Blum
and Micali's paper, of course.

>>> <snip>
>>>
>> I take it the cost is similar to the generator where Q_i = k*Q_(i-1)
>> for fixed k?
>
> I get 1381 bits/s with that method and 1349 bits/s with Kaliski's method
> (about 2%).

I guess the exponentiation ladder for the particular value of k you used was
somewhat easier than average to evaluate.

Décio

Relevant Pages

  • Re: Calculus XOR Probability
    ... I am assuming that when n is a specific infinity, ... That's the common notion of a curve, but a general definition may be adopted ... A sequence ... Except that a staircase of n steps is made up of 2*n segments. ...
    (sci.math)
  • Re: Calculus XOR Probability
    ... The length of the nth staircase is 2. ... one can't define what the probability of each is. ... saying and agreeing that the definition of the limiting curve you're ...
    (sci.math)
  • Quantum Gravity 166.3: Comparing dy/dt = ky and y = exp(kt) As Linear vs Exponential
    ... a bounded linear operator or bounded linear transformation T has ... rather Birkhoff Causation which approximates Probable ... To try to piece together how they relate, look at the curve y = exp ... is not only a Singularity but an Infinity! ...
    (sci.physics)
  • Quantum Gravity 136.1: Non-Tunneling Condition Yields 1 + y - x
    ... terminates on the boundary of the unit square except at. ... then the y coordinate of the curve would have reached infinity ... Substitute for gfrom into: ...
    (sci.physics)
  • Re: Infinitly many squares for y rational?
    ... seek rational points on the curve. ... elliptic curves, and Silverman's first book on elliptic curves. ... s=0 (and the point at infinity). ... no solution to x+1/x=0 in the rationals, so the only points on the ...
    (sci.math.research)
Quantcast