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$
  • 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 '16 at 18:36
  • $\begingroup$ Truly, actually, zero seconds flat. $\endgroup$ – L0j1k May 25 '16 at 6:03
  • 1
    $\begingroup$ It seems equivalent to a question "Why can a 4-digit pin code be 0000?" $\endgroup$ – Peteris May 25 '16 at 9:37
20
$\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$
  • 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$ – puzzlepalace May 24 '16 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$ – Stephen Touset May 24 '16 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$ – puzzlepalace May 24 '16 at 20:29
  • 1
    $\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$ – Stephen Touset May 24 '16 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$ – Nate Diamond May 24 '16 at 22:22

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.