Bitcoin Forum
May 10, 2024, 12:37:32 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Comparing Jacobian/Affine points  (Read 121 times)
PawGo (OP)
Legendary
*
Offline Offline

Activity: 952
Merit: 1367


View Profile
April 28, 2022, 07:31:07 AM
Merited by ABCbits (1)
 #1

Hello,

Please correct me if I am fundamentally wrong, but recently I was wondering about one thing - is it possible to somehow compare points from two different representations? We know that theoretically Affine point (xa,ya) could come from operations on Jacobian point (xj/zj^2, yj/zj^3). On the other hand, Jacobian (x,z,y) from Affine would be just (xa, ya, 1).

I would like to compare Affine point (AP) with a given Jacobian point (JP) - or at least exclude possibility that JP would be converted into given AP.

In other words: https://github.com/bitcoin-core/secp256k1/blob/master/src/secp256k1.c
We have JP (secp256k1_gej) and to receive "well-known" public key (through secp256k1_ge), we must launch launch:
Code:
secp256k1_ec_pubkey_create_helper + secp256k1_pubkey_save
which basically is (forget variables names, operations are important):
Code:
secp256k1_fe_sqr(&zi2, zi);
secp256k1_fe_mul(&zi3, &zi2, zi);
secp256k1_fe_mul(&r->x, &a->x, &zi2);
secp256k1_fe_mul(&r->y, &a->y, &zi3);

secp256k1_fe_normalize_var(&ge->x);
secp256k1_fe_normalize_var(&ge->y);
secp256k1_fe_get_b32(pubkey->data, &ge->x);
secp256k1_fe_get_b32(pubkey->data + 32, &ge->y);

Now, the question is:
Is there any step where I may stay (or operations I may skip) in that path (Jp->AP pubkey), if for a given generated Jacobian Point (secp256k1_gej) I want to exclude/ (or confirm) possibility that JP will == known public key? If I convert my pubkey into secp256k1_ge, which is basically (x, y, 1), may I compare it with unprocessed secp256k1_gej ?

1715301452
Hero Member
*
Offline Offline

Posts: 1715301452

View Profile Personal Message (Offline)

Ignore
1715301452
Reply with quote  #2

1715301452
Report to moderator
1715301452
Hero Member
*
Offline Offline

Posts: 1715301452

View Profile Personal Message (Offline)

Ignore
1715301452
Reply with quote  #2

1715301452
Report to moderator
1715301452
Hero Member
*
Offline Offline

Posts: 1715301452

View Profile Personal Message (Offline)

Ignore
1715301452
Reply with quote  #2

1715301452
Report to moderator
Activity + Trust + Earned Merit == The Most Recognized Users on Bitcointalk
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1715301452
Hero Member
*
Offline Offline

Posts: 1715301452

View Profile Personal Message (Offline)

Ignore
1715301452
Reply with quote  #2

1715301452
Report to moderator
1715301452
Hero Member
*
Offline Offline

Posts: 1715301452

View Profile Personal Message (Offline)

Ignore
1715301452
Reply with quote  #2

1715301452
Report to moderator
j2002ba2
Full Member
***
Offline Offline

Activity: 204
Merit: 437


View Profile
April 28, 2022, 08:16:33 AM
Merited by hugeblack (4), PawGo (4), ABCbits (3), NeuroticFish (2)
 #2

You could use the method for comparing two jacobian points directly.
(xa, ya, za=1) and (xj, yj, zj)

Code:
xa / za^2 = xj / zj^2
ya / za^3 = yj / zj^3

xa * zj^2 = xj * za^2
ya * zj^3 = yj * za^2

which becomes
xa * zj^2 = xj
ya * zj^3 = yj

No inversion, so this is considerably faster.

It depends on how many affine points you want to compare to. In the above case each check costs two multiplications (since we compute zj^2 and zj^3 once). It might be cheaper to convert the point to affine, and just compare. Additionally the known public keys might be organized in a radix tree for even faster comparison, which is not possible in jacobian coordinates.


PawGo (OP)
Legendary
*
Offline Offline

Activity: 952
Merit: 1367


View Profile
April 29, 2022, 10:07:32 PM
 #3

Works, thanks!
I am using now "secp256k1_fe_equal_var" and results are indeed like expected.
Good to know there is no one single way to do something.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!