Consider the two EC points $X=abG$ and $Y=bG$. Is it possible for someone to examine $X$ and $Y$ to determine if there is a common factor, as long as $a$ and $b$ are randomly chosen numbers between 0 and the size of the finite field? Even if the common factor $b$ cannot be determined, can it be determined if there is, or if there is likely to be a common factor? Assume the ed25519 curve is being used.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Assuming this topic is the interest of this question, shouldn't a more relevant question be as follows: with fixed $a$ and random $b_i$ for $i=1,2$, and $Y_i=b_iG$ and $X_i=aY_i$, is it possible for an observer to find a link between the two pairs $(X_1,Y_1)$ and $(X_2,Y_2)$ by somehow figuring out that each $X_i$ is a multiplication of $Y_i$ by the same $a$ even though he couldn't know $a$ itself? I hope the answer is no :) $\endgroup$– kenshi84Feb 17, 2017 at 6:06
-
2$\begingroup$ Don't forget to upvote questions guys, we're slacking. $\endgroup$– Maarten Bodewes ♦Feb 17, 2017 at 9:09
-
$\begingroup$ @MaartenBodewes I'm sorry? When did upvoting questions become mandatory? $\endgroup$– fkraiemFeb 17, 2017 at 19:25
-
$\begingroup$ @fkraiem Never, but as mentioned before on meta, it's a bit strange that a well asked question doesn't receive any upvotes - not even by the person answering it. And, truth to be said, I often forget as well (especially when I'm focussed on answering). But if you don't think the question is worth an upvote then don't; this was just a friendly reminder to upvote good questions. Truth to be said, I think we're a pretty well organized Q/A site, but this we can do better. $\endgroup$– Maarten Bodewes ♦Feb 17, 2017 at 19:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Is it possible for someone to examine $X$ and $Y$ to determine if there is a common factor, as long as $a$ and $b$ are randomly chosen numbers between 0 and the size of the finite field?
(Actually, you mean the size of the group)
Technically, the answer is "yes, it is easy to determine that". The easiest subcase is if $G$ (and hence $X$ and $Y$) belong to the large prime subgroup of x25519; then the rule is "unless Y is the point-at-infinity and X is not, the answer is "yes".
That is, there will always be an $a$ such that $X = aY$.
It's a little trickier if $G$ generates a larger subgroup, but it is still easy (it might take a little computation on the attacker's part).
Of course, the fact that it's always true (whether or not you consciously generated such a relationship between $X$ and $Y$) means that the attacker can't deduce anything from that information.
-
3$\begingroup$ Thank you - just to clarify, you're saying there is no way that the common factor $b$ can be determined? $\endgroup$– knacccFeb 17, 2017 at 4:48
-
$\begingroup$ Well, we certainly hope lot. That's the discrete log problem, and if someone can solve that, well, essentially all crypto on elliptic curves is broken... $\endgroup$– ponchoFeb 18, 2017 at 4:38