2
$\begingroup$

Having a large set of ECC public keys $P_i = n_iB$ on a fixed curve $E$ over a prime field, is there a way to determine if coefficients $n_i$ were generated using a bad PRNG?

In other words, can a quality of PRNG be tested by knowning the ECC public keys?

$\endgroup$
  • $\begingroup$ Well you could just use the "badness" of the PRNG to guess the correct $n_i$ and this would be standard approach. But this doesn't make DLP any easier as DLP requires randomly chosen $n_i$, so you're still breaking the PRNG. As for the test: You can use this, but simply guessing the (next) output is faster as you don't need the time-intense EC multiplication. $\endgroup$ – SEJPM Aug 19 '15 at 13:40
  • 1
    $\begingroup$ In fact, I have just a bunch of ECC public keys, have no access to the PRNG, only a notion that the PRNG is bad. And so to be precise, my question is if the "badness" of PRNG could be confirmed by looking at a large set of public keys. $\endgroup$ – NumberFour Aug 19 '15 at 13:50
  • $\begingroup$ Well, the RNG is used to generate the private key and the public key is derived from that if I understood correctly. So if you are worrying about repetition then it will have to be repetition for at least the size of the private key. In that case you would get duplicate public keys. So if you find a dupe, then you are sure that the PRNG is bad. Not finding a dupe doesn't mean the PRNG is good though. $\endgroup$ – Maarten Bodewes Aug 19 '15 at 21:04
  • 1
    $\begingroup$ Do you have a hint on how the PRNG is bad? Is it also using an ECC calculation, e.g. the Dual-ECC generator? I could imagine that if you can substitute $n_i$ by any algorithm that there are solutions to the equation. On the other hand, if it is just a badly seeded PRNG using a hash, I would hazard that you could not prove that fact (as you can obviously not gain enough knowledge about $n_i$, it is a private key after all. $\endgroup$ – Maarten Bodewes Aug 20 '15 at 14:38
1
$\begingroup$

No, not in general without a model for how the PRNG might be bad. If the PRNG is bad, then there is a test to distinguish it from (say) uniform random bit string outputs; you must then adapt that test to work not on bit string outputs, but on the resulting curve points. How you do this depends entirely on how the PRNG is bad.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.