Score:1

Crypto

Recovering public key from scalar multiplication inverse

sg777

12/24/23, 2:45 AM

I have two keypairs on the curve curve25519

k1 --> (a, aG)
k2 --> (b, bG)

I can compute and verify that a(bG) = b(aG).

Lets say k = a (bG), I'm computing scalar inverse of a which is pow(a, -1) and computing pow(a, -1) a (bG) and expecting that it will be equal to (bG) but i see its not equal to bG.

From a(bG) by only knowing a and aG, is it possible to know bG?

127

1 + 5

elliptic-curves

fgrieu

12/24/23, 8:07 AM

Hint: Choose how you define/compute `pow(a, -1)` according to the property you want for the quantity `pow(a, -1) a`. That's _not_ `pow(a, -1) a = 1` in the field $\mathbb F_{2^{255}-19}$, nor in the field $\mathbb R$.

sg777

12/24/23, 8:38 AM

Thank you for the clarification, I was thinking like multiple of any scalar variable with its inverse is congruent to 1 modp in any prime field.

fgrieu

12/24/23, 9:24 AM

Yes, $a\,a^{-1}\equiv 1$ in any prime field (and any ring when the inverse $a^{-1}$ is defined). But $a^{-1}$ is dependent on the field/ring, and you need to choose the one appropriate for your goal in the problem. Again what property do you want $a\,a^{-1}$ to have?

sg777

12/26/23, 4:06 AM

I'm doing the point mul to blind the point, so by doing ```a a -1``` I'm looking to nullify the effect of point multiplication of a on a given point in the curve25519. For example in my case by doing `aG` is a point that hides `a`, and if B blinds the point `aG` by multiplying it with `b`, i.e `b(aG)`, then I rewrite that as `a(bG)` and then if i do scalar multiplication of that point with `a-1`, i,e `a-1a(bG)`, i was expecting that I might be having `(bG)` and since the `bG` is public I can verify that B done the blinding of the point `aG`.

knaccc

12/27/23, 6:06 PM

You need a library to do a modular multiplicative inverse, where the modulus is the group size, which as fgrieu has pointed out is 2^252+27742317777372353535851937790883648493 for curve25519

Score:4

Crypto

fgrieu

12/27/23, 3:30 PM

On curve25519, from $a(bG)$ by only knowing $a$ and $aG$, is it possible to know $bG$?

Yes. We can compute $bG$ as $(a^{-1}\bmod n)(a(bG))$, where $n$ is the order of $G$, with $n=2^{252}+27742317777372353535851937790883648493$.

Proof: By definition of the order of $G$, it holds $nG=\mathcal O$ where $\mathcal O$ is the neutral of point addition. By definition of $a^{-1}\bmod n$, there exists integer $k$ such that $(a^{-1}\bmod n)\,a=1+k\,n$. It holds $$\begin{align}(a^{-1}\bmod n)(a(bG))&=((a^{-1}\bmod n)a)(bG)\\ &=(1+k\,n)(bG)\\ &=1(bG)+(k\,n)(bG)\\ &=bG+k((n\,b)G)\\ &=bG+k((b\,n)G)\\ &=bG+(k\,b)(nG)\\ &=bG+(k\,b)\mathcal O\\ &=bG+\mathcal O\\ &=bG\\ \end{align}$$

Notice $a^{-1}\bmod n$ is unrelated to $a^{-1}\bmod p$ where $p=2^{255}-19$ is the order of the field used for coordinates of points on curve25519.

+ 2

sg777

12/28/23, 11:14 PM

Thank you for the detailed proof, when im testing with the impl i have, when I do $a a^{-1}$, I always be getting `0100000000000000000000000000000000000000000000000000000000000000` for any $a$. So is $2^{248}$ is the point of infinity for the curve25519?

fgrieu

12/29/23, 9:36 AM

If $a\,a^{-1}$ turns out $2^{248}$ for any $a$, it's not computed right. Again, you want to compute $a^{-1}$ modulo $n$. In python 3.8 and later, that's `pow(a,-1,2**252+27742317777372353535851937790883648493)`. Then you do point multiplication of this integer with $a(bG)$ and get $bG$.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Recovering public key from scalar multiplication inverse

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.