Re: EC-PRNG

• Previous message: Brian Inglis: "Re: [Lit.] Buffer overruns"
• In reply to: Cristiano: "Re: EC-PRNG"
• Next in thread: Cristiano: "Re: EC-PRNG"
• Reply: Cristiano: "Re: EC-PRNG"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Date: Tue, 01 Feb 2005 21:24:53 -0200

Cristiano wrote:

> Décio Luiz Gazzoni Filho wrote:
>
> <snip>
>
> Call it "a security improvement". :-)
> If you hide informations the attacker should work much harder.
> I _think_ (but I'm not sure) that the same thing could be applied also to
> the BBS and RSA generators. I don't know why one should take the lsb
> instead of the above step 2b.

Quoting Donald Knuth: `random numbers should not be generated with a method
chosen at random.' If using the LSB makes the algorithm easier to analyze,
and after analysis it's shown to be good enough, why change the algorithm
in a way that you can't analyze?

Now I agree that using your original rule instead of the LSB `feels' more
secure in a common-sense kind of way, but who can be sure?

> <snip>
>
> Now that I understand the "kP + 1" notation, I understand also that point.
> As I said, knowing the lsb of Qy you can easily find Qx (because you know
> the base point) and thus Q, but hiding Qy I don't see any way to find Qx.

`Not seeing a way to find Qx' is not nearly as good as `proving that the LSB
of Qx can't be found.' Not that I'm saying that I've proved that, but I
believe it can be done. The point comes back to whether you have the tools
to analyze your original formulation -- and for all I know, somebody might
have done such analysis before, and indeed your scheme might be more
secure! But unless you can prove that, I'd stick to a scheme that's easier
to analyze, if you can prove it's secure enough.
 

> <snip>
>
> Yes, it is much slower (I get 1365 bits/s with a 112-bit curve, while with
> my algorithm I get 5734 bits/s), but the speed is not a problem because
> usually only few bits are needed (session keys and per session secret
> integer for ECC).

Supposing you wanted some extra speed, there are some tricks you can use. I
know you mentioned speed is not an issue, but for me speed is *always* an
issue (:

First of all, I think one can generate more than a single bit per
multiplication. You might search the literature if you're interested. I'd
guess it's nowhere near as much as an entire coordinate, but still, it
might help.

Next you should look at doing some parallel computations on different
curves/points/values of k. I believe there are improvements to
exponentiation algorithms that significantly speed up this situation. You
could also use an algorithm called Montgomery's trick, which can compute k
modular inversions in parallel using 3k - 3 modmuls and a single modular
inversion. Using this, the use of affine coordinates for elliptic curve
arithmetic becomes quite advantageous.

There are probably other speedups, but that's what I though for now.

> Certainly your scheme is harder to crack and it seems to pass some
> statistical tests (I'm generating some Mbits...).
> Do you think k should have some constraint, for example with respect to n?

Of course, it should be chosen uniformly at random from 0 to the group order
of the elliptic curve, but I guess you knew that. Also, the curve should
have prime order, so you don't risk being stuck in a subgroup and reducing
the periodicity of your random number sequence. But I bet you knew that
too.

Décio

• Previous message: Brian Inglis: "Re: [Lit.] Buffer overruns"
• In reply to: Cristiano: "Re: EC-PRNG"
• Next in thread: Cristiano: "Re: EC-PRNG"
• Reply: Cristiano: "Re: EC-PRNG"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]