3
$\begingroup$

Simple beginner question : I have 3 non equal elliptic curve points $A,B,G$. I both know that $A=scalar1×G$ and $B=scalar2×G$. Given this relation, is it possible to compute the scalar/discrete logarithm between $A$ and $B$ or $B$ and $A$ ?

If yes, does it apply if $A$ and $B$ have a different order which lies in a subgroup of order $G$ ? I’m meaning $G$ has a composite order and $B$ and $A$ have the same order which is a prime factor’s from $G$’s order. Where for example the Generator $G$’s point’s order is 5×2×7919 (79190) but $B$ and $A$ have order 7919.

$\endgroup$

2 Answers 2

2
$\begingroup$

Yes. If $A=s_1G$ and $B=s_2G$ and the group order is $\ell$, compute $s_3=s_1/s_2\pmod \ell$ (using the extended Euclidean algorithm) then $A=s_3B$.

Likewise if $s_4=s_2/s_1\pmod\ell$ then $B=s_4A$.

$\endgroup$
2
  • 1
    $\begingroup$ What if $A$ and $B$ have a different order which lies in a subgroup of order $G$ ? I’m meaning $G$ has a composite order and $B$ and $A$ have the same order which is a prime factor’s from $G$’s order. $\endgroup$ Commented Jul 27, 2024 at 8:09
  • $\begingroup$ Where $G$’s order is the same a as the full curve order. $\endgroup$ Commented Jul 27, 2024 at 13:11
1
$\begingroup$

The problem can be restated as: given a twisted Edwards curve over some finite field, $A$, $B$, $G$ on that curve, integers $s_1$ and $s_2$ with $A=s_1\times G$ and $B=s_2\times G$, can we find integer $s$ with $A=s\times B$, and how?

Optionally, we can immediately settle the case $B=\mathcal O$: if $A=\mathcal O$ any integer $s$ will do, otherwise there is no solution.

I'll assume we are given or find the order $m$ of the full curve (always a multiple of $4$), and it's factorization $m=\prod p^{m_p}$ for primes $p$, as is always the case in cryptography. For common curves $m=2^{m_2}\,q$ with $m_2\in\{2,3\}$ and a single large prime $q$, but we tackle the general case.

We find the order $\ell$ of $G$. E.g. we find one by one the multiplicities $\ell_p$ in $\ell=\prod p^{\ell_p}$, using that for each $p$ in the factorization of $m$, $\ell_p$ is the largest $i\le m_p$ such that $p^i\times\left(\left(m/p^{m_p}\right)\times G\right)=\mathcal O$.

Then we turn the problem into arithmetic modulo the (possibly composite) $\ell$: $$\begin{align} A=s_3\times B&\iff s_1\times G=s\times(s_2\times G)\\ &\iff s_1\times G=(s\,s_2)\times G\\ &\iff s_1\equiv s\,s_2\pmod\ell \end{align}$$

Compute $g=\gcd(s_2,\ell)$. If $s_1\bmod g\ne 0$ then there is no solution. Otherwise compute $\ell'=\ell/g\,$, $s_1'=(s_1/g)\bmod\ell'\,$, $s_2'=(s_2/g)\bmod\ell'$. The problem is reduced to $s'_1\equiv s\,s'_2\pmod{\ell'}$ with $\gcd(\ell',s'_2)=1$. Solutions are thus the $$s=\bigl(\left({s'_2}^{-1}\bmod\ell'\right)\,s'_1\bmod\ell'\bigr)+k\,\ell'\ \text{ for }\ k\in\mathbb Z$$ where ${s'_2}^{-1}\bmod\ell'$ is the inverse of $s'_2$ modulo $\ell'$, and can be efficiently computed by the (half-)extended Euclidean algorithm.

Notice that it's not necessary to make any use of the givens $A$ and $B$, nor or their order, and that the only necessary use of the given $G$ is to find it's order.


If we want to solve for $B=s\times A$ instead of $A=s\times B$, then we can proceed just as in the above solution of the original problem after exchanging $s_1$ and $s_2$.

$\endgroup$
5
  • $\begingroup$ What if $G=s_2×B$ instead of $B=s_2×G$? $\endgroup$ Commented Jul 27, 2024 at 12:36
  • $\begingroup$ @user2284570: If we change the problem statement to $G=s_2\times B$ instead of $B=s_2\times G$, then a solution to $A=s\times B$ is now $s=s_1\,s_2$, and that can be reduced modulo the order of $B$. $\endgroup$ Commented Jul 27, 2024 at 12:41
  • $\begingroup$ In reality I’m trying to solve this crypto.stackexchange.com/q/112290. So I need to find different non zero scalars such as $(s_4×A)+(s_5×B)=(s_6×A)+(s_7×B)$. So $G$ has the same order than the full curve. Doesn’t this change anything ? $\endgroup$ Commented Jul 27, 2024 at 12:53
  • $\begingroup$ @user2284570: It's unclear if the curve is a twisted Edward's curve as in the present question, or an Edward's curve as in the other. And the order of a twisted Edward's curve is a multiple of 4 thus $G$ can't have order 5×2×7919 as stated and the same order as the full curve as in above comment. There are answers to the present question, thus don't make changes invalidating existing answers. The other Q is currently unanswered, so please meticulously review it and change it slightly as required (e.g. tell if $P_1$, $P_2$ or/and $P_3$ are in the subgroup of large prime order if applicable). $\endgroup$ Commented Jul 27, 2024 at 13:26
  • $\begingroup$ I got wrong in the other as I failed to identify the twist. The real curve have a multiple of 4 order, yes. I gave only an example in my question. $\endgroup$ Commented Jul 27, 2024 at 13:29

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.