12
$\begingroup$

I often see in papers (e.g. this one) that for an elliptic curve with generator point $G$ and order $n$ the private key $d$ can take on any integer value in the range $[1, n)$. When $d = 1$ the corresponding public key $Q = dG$ is of course then just the generator point $G$. Why is this allowed? I understand that the chances that $d = 1$ for a sufficient size curve are basically non-existant, but doesn't $d = 1$ break the hardness assumption that elliptic curve schemes are based on (i.e. if I see $Q = G$ I can immediately infer $d$ without having to compute a discrete log over an elliptic curve).

$\endgroup$
3
  • 4
    $\begingroup$ If an attacker can guess the $d$ then all bets are off. What if $d$ is two? Brute forcing $d$ would take zero seconds flat. $\endgroup$
    – Maarten Bodewes
    May 24, 2016 at 18:36
  • $\begingroup$ Truly, actually, zero seconds flat. $\endgroup$
    – L0j1k
    May 25, 2016 at 6:03
  • 1
    $\begingroup$ It seems equivalent to a question "Why can a 4-digit pin code be 0000?" $\endgroup$
    – Peteris
    May 25, 2016 at 9:37

1 Answer 1

21
$\begingroup$

By the same argument, they would have to forbid $d = 1234$; after all, an attacker can trivially compute the value of $1234 G$; and if they see it, then they can immediately infer $d$ without having to complete a discrete log over an elliptic curve. Of course, this logic would forbid all possible values of $d$...

The issue is that if the attacker gets lucky and guesses $d$, he wins (and there's nothing special about $d=1$ in this). However, he is quite unlikely to get lucky (and again, there's nothing special about $d=1$ in this either).

$\endgroup$
5
  • 1
    $\begingroup$ I get the reasoning, but it does seem like in the case of $Q = 1234G$ there is no reason to suspect $d$ is within the range of a brute force given $Q$. In the case of $d=1$, since $G$ is public, it is immediately apparent what $d$ is given $Q$ (so the attacker doesn't even have to guess). $\endgroup$ May 24, 2016 at 18:45
  • 17
    $\begingroup$ Put another way, if you forbid $d=1$, now an attacker could start brute-forcing at $d=2$. If you forbid $d=2$, attackers may start at $d=3$, so it should be forbidden. Repeat ad infinitum. $\endgroup$ May 24, 2016 at 18:45
  • 4
    $\begingroup$ @StephenTouset I understand that inductive reasoning, but I'm not considering a brute force approach but rather the fact that one can infer $d$ given $Q$ and $G$ when $d=1$ without having to compute anything. E.g. if I know what $G$ is and observe a $Q$ with value $2G$ this doesn't immediately reveal $d$ to me, I'd have to try a couple values of $d$ before I discover this, and given only $Q$ I'd have no reason to attempt the brute force as nothing about $Q$ would indicate a low value $d$. $\endgroup$ May 24, 2016 at 20:29
  • 2
    $\begingroup$ Calculating $Q=dG$ is trivial for any $d \in [1,n)$. $d=1$ isn't really too much of a special case in that regard. At any rate, given the odds that $d=1$, testing for such a case is more likely to result in a bug than in actually catching it happening. $\endgroup$ May 24, 2016 at 21:38
  • 1
    $\begingroup$ I think the key that OP is missing here is that for any attacker to compare $d$ and $Q$, they must be beginning a brute force attempt otherwise, why do it? Further, if an attacker, as per habit, always checks to see that $d \ne Q$, what value does this give to them? The $1/n$ chance that it is for this given key pair? The key feature that the others are trying to point out is that by the time the attacker is moving to comparing $d$ and $Q$ for a sufficiently strong algorithm then they have already ceded the one of the core strengths of the algorithm: the size of $n$. $\endgroup$ May 24, 2016 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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