Bitcoin Forum
May 27, 2024, 07:41:11 AM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Why there are so many non-existing keys in ECDSA?  (Read 241 times)
vjudeu (OP)
Hero Member
*****
Offline Offline

Activity: 696
Merit: 1607



View Profile
November 12, 2020, 08:10:36 AM
 #1

Compressed public key 02000...001 exists, as well as 02000...002, 02000...003 and 02000...004. But there is no 02000...005 key! Also, I noticed many other keys are missing, for example: {0x5, 0x7, 0x9, 0xa, 0xb, 0xf, 0x11, 0x12, 0x13, 0x15, 0x17, 0x18, 0x1a, 0x1c, 0x1d, 0x1e, 0x1f, 0x22, 0x23, 0x24, 0x25, 0x28, 0x29, 0x2a, 0x2e, 0x31, 0x32, 0x33, 0x35, 0x36, 0x37, 0x3a, ...}. It seems that around half of them are not existing. Why it is impossible to create such points? Is it because of holding one more bit in 02 and 03 prefixes or something else?

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
PawGo
Legendary
*
Offline Offline

Activity: 952
Merit: 1367


View Profile
November 12, 2020, 10:52:06 AM
 #2

How do you know that it is impossible to generate a given point?
NotATether
Legendary
*
Offline Offline

Activity: 1610
Merit: 6761


bitcoincleanup.com / bitmixlist.org


View Profile WWW
November 12, 2020, 10:56:44 AM
Merited by ABCbits (2), gmaxwell (1), Heisenberg_Hunter (1)
 #3

Elliptic curves such as secp256k1 which is used in bitcoin have an equation that needs to be solved to get Y, so the values of the compressed public keys you provided are X values and don’t have a corresponding Y number, according to my understanding. That’s how they don’t exist on the curve.

I don't understand.. Can you elaborate what is this "ECDSA"? Huh

ECDSA is an algorithm for creating digital signatures from a private key using elliptic curve cryptography. In bitcoin for example, it is used to create signatures required to broadcast transactions and can also make signed messages.

.
.BLACKJACK ♠ FUN.
█████████
██████████████
████████████
█████████████████
████████████████▄▄
░█████████████▀░▀▀
██████████████████
░██████████████
████████████████
░██████████████
████████████
███████████████░██
██████████
CRYPTO CASINO &
SPORTS BETTING
▄▄███████▄▄
▄███████████████▄
███████████████████
█████████████████████
███████████████████████
█████████████████████████
█████████████████████████
█████████████████████████
███████████████████████
█████████████████████
███████████████████
▀███████████████▀
█████████
.
vjudeu (OP)
Hero Member
*****
Offline Offline

Activity: 696
Merit: 1607



View Profile
November 12, 2020, 11:05:41 AM
 #4

Quote
How do you know that it is impossible to generate a given point?
You can try importing such public key. It simply won't work and you'll get error message saying that this public key doesn't exist.

Also, it's quite interesting that doubling some of such keys produces a key with some pattern. For example if you double 02000...001 public key, you'll get 03c7fff...fff37fffd03 public key.

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
j2002ba2
Full Member
***
Offline Offline

Activity: 204
Merit: 437


View Profile
November 12, 2020, 02:11:02 PM
Merited by nc50lc (1)
 #5

Why it is impossible to create such points?

secp256k1 uses the equation y2 = x3 + 7 (mod p). Only half of the possible x values give a solution for y. Compressed public key is the parity of y represented as 02 when even or 03 when odd followed by x.
vjudeu (OP)
Hero Member
*****
Offline Offline

Activity: 696
Merit: 1607



View Profile
December 07, 2020, 03:28:49 PM
Merited by Rath_ (2), vapourminer (1)
 #6

OK, so not all keys are valid, because of the way the curve is constructed. But still, I tried another thing and I'm curious why the things are the way they are:

We start with some public key, for example 02000...001. When converting from compressed to uncompressed form, we can get both X and Y values for such point. We take Y value as X and use 02 or 03 prefix, thus creating another public key. Sometimes we will see that there is no key that can be constructed in such way. Then, we mark such key with this Y value as "visited" and try another path, so if we chose 02 prefix and we failed to find matching key, we choose 03. If none of them matched, we go back, unless we will return to our starting key.

Example is the best explanation, so here it is how it looks like for such key:

Code:
000 | 02 0000000000000000000000000000000000000000000000000000000000000001 4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee -
001 |  02 4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee 37269a64bbcf3a3f227631c7a8ce532c77245a1c0db4343f16aa1d339fd2591a -
001 |  03 4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee c8d9659b4430c5c0dd89ce385731acd388dba5e3f24bcbc0e955e2cb602da315 -
002 |   02 c8d9659b4430c5c0dd89ce385731acd388dba5e3f24bcbc0e955e2cb602da315 a4d87747ecd146a09a14a531b889425c8fe308973b3fce622987d4fe27db17bc -
003 |    02 a4d87747ecd146a09a14a531b889425c8fe308973b3fce622987d4fe27db17bc 83a6221ccaf1844405bfd822cd7f99405efc4ad3f458ad08283f5f09a9ade2e2 -
004 |     02 83a6221ccaf1844405bfd822cd7f99405efc4ad3f458ad08283f5f09a9ade2e2 f365915449470f1213c754bdacd2bba94638914d363096f09fc233967a991bd2 -
004 |     03 83a6221ccaf1844405bfd822cd7f99405efc4ad3f458ad08283f5f09a9ade2e2 0c9a6eabb6b8f0edec38ab42532d4456b9c76eb2c9cf690f603dcc688566e05d -
005 |      02 0c9a6eabb6b8f0edec38ab42532d4456b9c76eb2c9cf690f603dcc688566e05d 8fd2ac8164f2a6a48d5cb1d81d3c590f00c7c70cfafb31e029d99a7239e634f4 -
006 |       02 8fd2ac8164f2a6a48d5cb1d81d3c590f00c7c70cfafb31e029d99a7239e634f4 6191828c8c58e53ceb6b4c0e9a3da3978259d7c0becc0d63f48415b4e345391c -
007 |        02 6191828c8c58e53ceb6b4c0e9a3da3978259d7c0becc0d63f48415b4e345391c a346c6ae84cfc95c25a699ea32461141196dee326974195ec7def6b798b3c3f0 -
008 |         02 a346c6ae84cfc95c25a699ea32461141196dee326974195ec7def6b798b3c3f0 06a12da0e28069c86c208df7f589b3006a76f121d2f9e61b44f2bfc64632d5d2 -
008 |         03 a346c6ae84cfc95c25a699ea32461141196dee326974195ec7def6b798b3c3f0 f95ed25f1d7f963793df72080a764cff95890ede2d0619e4bb0d4038b9cd265d -
009 |          02 f95ed25f1d7f963793df72080a764cff95890ede2d0619e4bb0d4038b9cd265d 25330680ad031aedbffaed80e15136f95c08c34240ac0c17eade96627fc9c234 -
009 |          03 f95ed25f1d7f963793df72080a764cff95890ede2d0619e4bb0d4038b9cd265d daccf97f52fce5124005127f1eaec906a3f73cbdbf53f3e81521699c803639fb -
007 |        03 6191828c8c58e53ceb6b4c0e9a3da3978259d7c0becc0d63f48415b4e345391c 5cb939517b3036a3da596615cdb9eebee69211cd968be6a138210947674c383f -
008 |         02 5cb939517b3036a3da596615cdb9eebee69211cd968be6a138210947674c383f e31050b3acff9b390e09ec092ccb0cb6dcad80923e46423ff0332476660b417e -
008 |         03 5cb939517b3036a3da596615cdb9eebee69211cd968be6a138210947674c383f 1cefaf4c530064c6f1f613f6d334f34923527f6dc1b9bdc00fccdb8899f4bab1 -
009 |          02 1cefaf4c530064c6f1f613f6d334f34923527f6dc1b9bdc00fccdb8899f4bab1 9efd555fe89618bb007517771c0089aeaf2c95a13370cef904d41b0384bcac2e -
010 |           02 9efd555fe89618bb007517771c0089aeaf2c95a13370cef904d41b0384bcac2e d3955faabb82062881f0ddc810be6d4058a72634d6e7ffaaee9ca30e7ff04702 -
010 |           03 9efd555fe89618bb007517771c0089aeaf2c95a13370cef904d41b0384bcac2e 2c6aa055447df9d77e0f2237ef4192bfa758d9cb2918005511635cf0800fb52d -
009 |          03 1cefaf4c530064c6f1f613f6d334f34923527f6dc1b9bdc00fccdb8899f4bab1 6102aaa01769e744ff8ae888e3ff765150d36a5ecc8f3106fb2be4fb7b435001 -
010 |           02 6102aaa01769e744ff8ae888e3ff765150d36a5ecc8f3106fb2be4fb7b435001 7a8257b216b550a3e6dc38940383d4dae7afc5effa2fa6627605819b5308eb3e -
010 |           03 6102aaa01769e744ff8ae888e3ff765150d36a5ecc8f3106fb2be4fb7b435001 857da84de94aaf5c1923c76bfc7c2b2518503a1005d0599d89fa7e63acf710f1 -
011 |            02 857da84de94aaf5c1923c76bfc7c2b2518503a1005d0599d89fa7e63acf710f1 2a81b4e46232c656f3f91a9b76afe106d1b005541f4446fe0019a813174bd64e -
012 |             02 2a81b4e46232c656f3f91a9b76afe106d1b005541f4446fe0019a813174bd64e c09a90df889fad7e0023e65b5ea3711744bbb1488a808862738dd3626385dcaa -
012 |             03 2a81b4e46232c656f3f91a9b76afe106d1b005541f4446fe0019a813174bd64e 3f656f2077605281ffdc19a4a15c8ee8bb444eb7757f779d8c722c9c9c7a1f85 -
013 |              02 3f656f2077605281ffdc19a4a15c8ee8bb444eb7757f779d8c722c9c9c7a1f85 4d7d648adcae055cbbcf763d8d4cb7269c0892dfcda933b18019ccf118c8048a -
013 |              03 3f656f2077605281ffdc19a4a15c8ee8bb444eb7757f779d8c722c9c9c7a1f85 b2829b752351faa3443089c272b348d963f76d203256cc4e7fe6330de737f7a5 -
014 |               02 b2829b752351faa3443089c272b348d963f76d203256cc4e7fe6330de737f7a5 73c0c2f556e0638e9a16f016705061fc9d1570084bc7106b8d87479fc9a3ccec -
014 |               03 b2829b752351faa3443089c272b348d963f76d203256cc4e7fe6330de737f7a5 8c3f3d0aa91f9c7165e90fe98faf9e0362ea8ff7b438ef947278b85f365c2f43 -
011 |            03 857da84de94aaf5c1923c76bfc7c2b2518503a1005d0599d89fa7e63acf710f1 d57e4b1b9dcd39a90c06e56489501ef92e4ffaabe0bbb901ffe657ebe8b425e1 -
012 |             02 d57e4b1b9dcd39a90c06e56489501ef92e4ffaabe0bbb901ffe657ebe8b425e1 4ed8571b1a642d8892ce67ba93795b60a99b8738cfc9faef53da30ea7e1d3ff0 -
013 |              02 4ed8571b1a642d8892ce67ba93795b60a99b8738cfc9faef53da30ea7e1d3ff0 7e40bf0ba054726cb6baa8fd81199e1b98ebcea5b3ceccd97d66bc7b10d42368 -
013 |              03 4ed8571b1a642d8892ce67ba93795b60a99b8738cfc9faef53da30ea7e1d3ff0 81bf40f45fab8d93494557027ee661e46714315a4c31332682994383ef2bd8c7 -
014 |               02 81bf40f45fab8d93494557027ee661e46714315a4c31332682994383ef2bd8c7 42efa2712643d4d193c06f22ae479125d3f8f2724a90c4bad17fbac687ef10de -
015 |                02 42efa2712643d4d193c06f22ae479125d3f8f2724a90c4bad17fbac687ef10de 5c4ce34e6581e69337039079e2e12c3e5aeded98d6a83864ffbb6ad6535bdd6a -
016 |                 02 5c4ce34e6581e69337039079e2e12c3e5aeded98d6a83864ffbb6ad6535bdd6a e160f20204aa1dce884358536f943c7b38a5997769968d78c4eb3e20ea2c3ee6 -
016 |                 03 5c4ce34e6581e69337039079e2e12c3e5aeded98d6a83864ffbb6ad6535bdd6a 1e9f0dfdfb55e23177bca7ac906bc384c75a6688966972873b14c1de15d3bd49 -
015 |                03 42efa2712643d4d193c06f22ae479125d3f8f2724a90c4bad17fbac687ef10de a3b31cb19a7e196cc8fc6f861d1ed3c1a51212672957c79b00449528aca41ec5 -
014 |               03 81bf40f45fab8d93494557027ee661e46714315a4c31332682994383ef2bd8c7 bd105d8ed9bc2b2e6c3f90dd51b86eda2c070d8db56f3b452e8045387810eb51 -
012 |             03 d57e4b1b9dcd39a90c06e56489501ef92e4ffaabe0bbb901ffe657ebe8b425e1 b127a8e4e59bd2776d3198456c86a49f566478c730360510ac25cf1481e2bc3f -
013 |              02 b127a8e4e59bd2776d3198456c86a49f566478c730360510ac25cf1481e2bc3f 99dd00e9457f558925e1b6797374a463bbbf924bab09f115d8fc8dca8e573654 -
013 |              03 b127a8e4e59bd2776d3198456c86a49f566478c730360510ac25cf1481e2bc3f 6622ff16ba80aa76da1e49868c8b5b9c44406db454f60eea2703723471a8c5db -
014 |               02 6622ff16ba80aa76da1e49868c8b5b9c44406db454f60eea2703723471a8c5db 19347dd5b145bd0489f6403f526dddeb1956343173948853aa080e30ac0c62e4 -
015 |                02 19347dd5b145bd0489f6403f526dddeb1956343173948853aa080e30ac0c62e4 07350190da5671855d8023b2a1efeb87a6d807e2623e7a175e60fb6f1a5f8812 -
015 |                03 19347dd5b145bd0489f6403f526dddeb1956343173948853aa080e30ac0c62e4 f8cafe6f25a98e7aa27fdc4d5e1014785927f81d9dc185e8a19f048fe5a0741d -
014 |               03 6622ff16ba80aa76da1e49868c8b5b9c44406db454f60eea2703723471a8c5db e6cb822a4eba42fb7609bfc0ad922214e6a9cbce8c6b77ac55f7f1ce53f3994b -
015 |                02 e6cb822a4eba42fb7609bfc0ad922214e6a9cbce8c6b77ac55f7f1ce53f3994b 1bc24cfcfed9f446ca9cd6f37a6dd665b819f69fd847a258c37565d0a02f6702 -
016 |                 02 1bc24cfcfed9f446ca9cd6f37a6dd665b819f69fd847a258c37565d0a02f6702 a4de9358f2110e7cc279767958c80ac587b31a817427508f60836868fa608e78 -
016 |                 03 1bc24cfcfed9f446ca9cd6f37a6dd665b819f69fd847a258c37565d0a02f6702 5b216ca70deef1833d868986a737f53a784ce57e8bd8af709f7c9796059f6db7 -
017 |                  02 5b216ca70deef1833d868986a737f53a784ce57e8bd8af709f7c9796059f6db7 60218ca9454b12c0e80b9f5c4a188dc38c2c89d6281a6769e42b01961743188e -
017 |                  03 5b216ca70deef1833d868986a737f53a784ce57e8bd8af709f7c9796059f6db7 9fde7356bab4ed3f17f460a3b5e7723c73d37629d7e598961bd4fe68e8bce3a1 -
015 |                03 e6cb822a4eba42fb7609bfc0ad922214e6a9cbce8c6b77ac55f7f1ce53f3994b e43db30301260bb93563290c8592299a47e6096027b85da73c8a9a2e5fd0952d -
016 |                 02 e43db30301260bb93563290c8592299a47e6096027b85da73c8a9a2e5fd0952d a0cd9641ba1d1d15fea2ad655e239462907c781357bb5570b184c04f4783ff74 -
017 |                  02 a0cd9641ba1d1d15fea2ad655e239462907c781357bb5570b184c04f4783ff74 5b1235b56a8a865083f3345d0451b0ec30a7557e1dc835b405c72929cf6536f2 -
017 |                  03 a0cd9641ba1d1d15fea2ad655e239462907c781357bb5570b184c04f4783ff74 a4edca4a957579af7c0ccba2fbae4f13cf58aa81e237ca4bfa38d6d5309ac53d -
018 |                   02 a4edca4a957579af7c0ccba2fbae4f13cf58aa81e237ca4bfa38d6d5309ac53d c574c02e0832011a23e6b3a0697c10c6b6dce89ed4559e7994d326adf255891c -
018 |                   03 a4edca4a957579af7c0ccba2fbae4f13cf58aa81e237ca4bfa38d6d5309ac53d 3a8b3fd1f7cdfee5dc194c5f9683ef39492317612baa61866b2cd9510daa7313 -
019 |                    02 3a8b3fd1f7cdfee5dc194c5f9683ef39492317612baa61866b2cd9510daa7313 997dae7cf5ae7d69c1d278888452482b0ac7bfe4e740f138a65e0f32fc34a044 -
020 |                     02 997dae7cf5ae7d69c1d278888452482b0ac7bfe4e740f138a65e0f32fc34a044 48d034303587ab4cbe63532ef731f9adcbed901328e130dd934d5c1d93e75392 -
020 |                     03 997dae7cf5ae7d69c1d278888452482b0ac7bfe4e740f138a65e0f32fc34a044 b72fcbcfca7854b3419cacd108ce065234126fecd71ecf226cb2a3e16c18a89d -
019 |                    03 3a8b3fd1f7cdfee5dc194c5f9683ef39492317612baa61866b2cd9510daa7313 668251830a5182963e2d87777badb7d4f538401b18bf0ec759a1f0cc03cb5beb -
016 |                 03 e43db30301260bb93563290c8592299a47e6096027b85da73c8a9a2e5fd0952d 5f3269be45e2e2ea015d529aa1dc6b9d6f8387eca844aa8f4e7b3fafb87bfcbb -
017 |                  02 5f3269be45e2e2ea015d529aa1dc6b9d6f8387eca844aa8f4e7b3fafb87bfcbb 6ce33508a3bfbb8f04028be8e2bbe7acc8487f8c932b6cbadd6212a27698ef8c -
018 |                   02 6ce33508a3bfbb8f04028be8e2bbe7acc8487f8c932b6cbadd6212a27698ef8c be18b23f78d4f67c9b7c75a6adc645c7c1e039f76f3024c78110a32daf3aedf8 -
019 |                    02 be18b23f78d4f67c9b7c75a6adc645c7c1e039f76f3024c78110a32daf3aedf8 fdec4113ca363db7d728beae6102f663c39ba04c961d34a8dcea95880b25ac52 -
020 |                     02 fdec4113ca363db7d728beae6102f663c39ba04c961d34a8dcea95880b25ac52 28c88f029f9d38b53a11712e07e04875781afcfe4f523f35ae4313e83ff1a07a -
021 |                      02 28c88f029f9d38b53a11712e07e04875781afcfe4f523f35ae4313e83ff1a07a e8c994be61e63f271c26355b24d367a3437e244fb7d90c936a8536165e70190a -
022 |                       02 e8c994be61e63f271c26355b24d367a3437e244fb7d90c936a8536165e70190a 13897f60497d971f9c73d981716fc61995f31ba291dd7c272676a4517a07a258 -
023 |                        02 13897f60497d971f9c73d981716fc61995f31ba291dd7c272676a4517a07a258 29b0f8cef948cd18e0226113cb0206c5d7ff547b83b2a7bf0e9990d83baac588 -
023 |                        03 13897f60497d971f9c73d981716fc61995f31ba291dd7c272676a4517a07a258 d64f073106b732e71fdd9eec34fdf93a2800ab847c4d5840f1666f26c45536a7 -
024 |                         02 d64f073106b732e71fdd9eec34fdf93a2800ab847c4d5840f1666f26c45536a7 ae66819a70a7521f83d426481ca6c99a663450338c57e851bc395359264a85fc -
024 |                         03 d64f073106b732e71fdd9eec34fdf93a2800ab847c4d5840f1666f26c45536a7 51997e658f58ade07c2bd9b7e359366599cbafcc73a817ae43c6aca5d9b57633 -
022 |                       03 e8c994be61e63f271c26355b24d367a3437e244fb7d90c936a8536165e70190a ec76809fb68268e0638c267e8e9039e66a0ce45d6e2283d8d9895bad85f859d7 -
023 |                        02 ec76809fb68268e0638c267e8e9039e66a0ce45d6e2283d8d9895bad85f859d7 2df102235aa73b1ed8984712fc57d2556e205433dafcedd7c68f73639ab37128 -
024 |                         02 2df102235aa73b1ed8984712fc57d2556e205433dafcedd7c68f73639ab37128 7d68719304953f48dd4ef996e5d05a72a32bd4ab83dae3e4102737c73689e2de -
024 |                         03 2df102235aa73b1ed8984712fc57d2556e205433dafcedd7c68f73639ab37128 82978e6cfb6ac0b722b106691a2fa58d5cd42b547c251c1befd8c837c9761951 -
025 |                          02 82978e6cfb6ac0b722b106691a2fa58d5cd42b547c251c1befd8c837c9761951 0919d314b1c5741bcea4b2ea2661d19c923db639a9f4ebba3090e8039f17e90c -
026 |                           02 0919d314b1c5741bcea4b2ea2661d19c923db639a9f4ebba3090e8039f17e90c 617702308f3b41f2f0371a8d96954b24bb72ccdf2df28c3d849ec0f0e9596b9e -
026 |                           03 0919d314b1c5741bcea4b2ea2661d19c923db639a9f4ebba3090e8039f17e90c 9e88fdcf70c4be0d0fc8e572696ab4db448d3320d20d73c27b613f0e16a69091 -
025 |                          03 82978e6cfb6ac0b722b106691a2fa58d5cd42b547c251c1befd8c837c9761951 f6e62ceb4e3a8be4315b4d15d99e2e636dc249c6560b1445cf6f17fb60e81323 -
023 |                        03 ec76809fb68268e0638c267e8e9039e66a0ce45d6e2283d8d9895bad85f859d7 d20efddca558c4e12767b8ed03a82daa91dfabcc2503122839708c9b654c8b07 -
021 |                      03 28c88f029f9d38b53a11712e07e04875781afcfe4f523f35ae4313e83ff1a07a 17366b419e19c0d8e3d9caa4db2c985cbc81dbb04826f36c957ac9e8a18fe325 -
020 |                     03 fdec4113ca363db7d728beae6102f663c39ba04c961d34a8dcea95880b25ac52 d73770fd6062c74ac5ee8ed1f81fb78a87e50301b0adc0ca51bcec16c00e5bb5 -
021 |                      02 d73770fd6062c74ac5ee8ed1f81fb78a87e50301b0adc0ca51bcec16c00e5bb5 488aad38234c458a6299b9e8f4429ffa98894bc81780d369924882beed5b2ada -
022 |                       02 488aad38234c458a6299b9e8f4429ffa98894bc81780d369924882beed5b2ada ff54ceb478fbc7b40830f950aaa221f71f06127427ac645c7a3dd64b465845dc -
023 |                        02 ff54ceb478fbc7b40830f950aaa221f71f06127427ac645c7a3dd64b465845dc 0b533bad6f5a3f99083ba7942f9a469efdfcdfecc47bde4e1c3ad5373fe350ba -
023 |                        03 ff54ceb478fbc7b40830f950aaa221f71f06127427ac645c7a3dd64b465845dc f4acc45290a5c066f7c4586bd065b961020320133b8421b1e3c52ac7c01cab75 -
022 |                       03 488aad38234c458a6299b9e8f4429ffa98894bc81780d369924882beed5b2ada 00ab314b8704384bf7cf06af555dde08e0f9ed8bd8539ba385c229b3b9a7b653 -
021 |                      03 d73770fd6062c74ac5ee8ed1f81fb78a87e50301b0adc0ca51bcec16c00e5bb5 b77552c7dcb3ba759d6646170bbd60056776b437e87f2c966db77d4012a4d155 -
022 |                       02 b77552c7dcb3ba759d6646170bbd60056776b437e87f2c966db77d4012a4d155 10a506c6664c6a7bdae6bdd4050cd850638a18f35a91d5517822e10b8bc0ba94 -
023 |                        02 10a506c6664c6a7bdae6bdd4050cd850638a18f35a91d5517822e10b8bc0ba94 4cc29786c7a1baf8267c50d77c6fa08392b0bd34cfa71f7e4800bacc14ac62c2 -
024 |                         02 4cc29786c7a1baf8267c50d77c6fa08392b0bd34cfa71f7e4800bacc14ac62c2 3c0ea1394d7f8414be3af91b7b8e6d7bd7d7b6057e6172309fc6fc60ba13afd6 -
025 |                          02 3c0ea1394d7f8414be3af91b7b8e6d7bd7d7b6057e6172309fc6fc60ba13afd6 422785e6835e7774a8848ea331c4d3635079a0b3f802c558a34d0bb8cb59603a -
025 |                          03 3c0ea1394d7f8414be3af91b7b8e6d7bd7d7b6057e6172309fc6fc60ba13afd6 bdd87a197ca1888b577b715cce3b2c9caf865f4c07fd3aa75cb2f44634a69bf5 -
026 |                           02 bdd87a197ca1888b577b715cce3b2c9caf865f4c07fd3aa75cb2f44634a69bf5 96237713e84baef184b9c72a4257a43f50a1c59817501174b27bf4df8d623d58 -
026 |                           03 bdd87a197ca1888b577b715cce3b2c9caf865f4c07fd3aa75cb2f44634a69bf5 69dc88ec17b4510e7b4638d5bda85bc0af5e3a67e8afee8b4d840b1f729dbed7 -
024 |                         03 4cc29786c7a1baf8267c50d77c6fa08392b0bd34cfa71f7e4800bacc14ac62c2 c3f15ec6b2807beb41c506e484719284282849fa819e8dcf6039039e45ec4c59 -
023 |                        03 10a506c6664c6a7bdae6bdd4050cd850638a18f35a91d5517822e10b8bc0ba94 b33d6879385e4507d983af2883905f7c6d4f42cb3058e081b7ff4532eb53996d -
024 |                         02 b33d6879385e4507d983af2883905f7c6d4f42cb3058e081b7ff4532eb53996d 85fdebbc6bf82a67281a087b788782743fb8fe80a3bfc12394d503cfee6e695c -
025 |                          02 85fdebbc6bf82a67281a087b788782743fb8fe80a3bfc12394d503cfee6e695c 2ae8c12bd48cb9a0dc0a28b978ead82ffdc1b0be3a77a50ebb5d47c5135ba004 -
026 |                           02 2ae8c12bd48cb9a0dc0a28b978ead82ffdc1b0be3a77a50ebb5d47c5135ba004 e1dfba096f4368c1166e8ba6b411177a53cf31f1ddd44e4284bd5e4d53afd1be -
026 |                           03 2ae8c12bd48cb9a0dc0a28b978ead82ffdc1b0be3a77a50ebb5d47c5135ba004 1e2045f690bc973ee99174594beee885ac30ce0e222bb1bd7b42a1b1ac502a71 -
025 |                          03 85fdebbc6bf82a67281a087b788782743fb8fe80a3bfc12394d503cfee6e695c d5173ed42b73465f23f5d746871527d0023e4f41c5885af144a2b839eca45c2b -
026 |                           02 d5173ed42b73465f23f5d746871527d0023e4f41c5885af144a2b839eca45c2b 4a6a29a03683937ef5ac74988c139f9c07bd9afe175d6bc0e52e08e7f6708eac -
026 |                           03 d5173ed42b73465f23f5d746871527d0023e4f41c5885af144a2b839eca45c2b b595d65fc97c6c810a538b6773ec6063f8426501e8a2943f1ad1f717098f6d83 -
027 |                            02 b595d65fc97c6c810a538b6773ec6063f8426501e8a2943f1ad1f717098f6d83 e3fb79c174f107afd0c01e57c80fd1a95667d9bfeb3a09d005931ac5d1d82c2e -
028 |                             02 e3fb79c174f107afd0c01e57c80fd1a95667d9bfeb3a09d005931ac5d1d82c2e f8b7642b8b916ca5e1f958a82f70a2d9e29cb500d0f35df4d21a0febe5a8de7a -
028 |                             03 e3fb79c174f107afd0c01e57c80fd1a95667d9bfeb3a09d005931ac5d1d82c2e 07489bd4746e935a1e06a757d08f5d261d634aff2f0ca20b2de5f0131a571db5 -
027 |                            03 b595d65fc97c6c810a538b6773ec6063f8426501e8a2943f1ad1f717098f6d83 1c04863e8b0ef8502f3fe1a837f02e56a998264014c5f62ffa6ce5392e27d001 -
028 |                             02 1c04863e8b0ef8502f3fe1a837f02e56a998264014c5f62ffa6ce5392e27d001 82950ae4fe2a4d19d679a3810057df6a42d6aa7746bd1b8647c91bc953de088c -
029 |                              02 82950ae4fe2a4d19d679a3810057df6a42d6aa7746bd1b8647c91bc953de088c bcddfaca3af6c142a5e7a367cc05867a7bb888662148bbf8d7e3bf5b88e1e550 -
029 |                              03 82950ae4fe2a4d19d679a3810057df6a42d6aa7746bd1b8647c91bc953de088c 43220535c5093ebd5a185c9833fa798584477799deb74407281c40a3771e16df -
030 |                               02 43220535c5093ebd5a185c9833fa798584477799deb74407281c40a3771e16df 1fc2b410cb0993d084c7a21ec279060a729f191368dd1cd8339795c588b27278 -
030 |                               03 43220535c5093ebd5a185c9833fa798584477799deb74407281c40a3771e16df e03d4bef34f66c2f7b385de13d86f9f58d60e6ec9722e327cc686a39774d89b7 -
031 |                                02 e03d4bef34f66c2f7b385de13d86f9f58d60e6ec9722e327cc686a39774d89b7 47073acf07368663b5d5aa75371a74336d344110bc07da5b274687d85154cd66 -
031 |                                03 e03d4bef34f66c2f7b385de13d86f9f58d60e6ec9722e327cc686a39774d89b7 b8f8c530f8c9799c4a2a558ac8e58bcc92cbbeef43f825a4d8b97826aeab2ec9 -
028 |                             03 1c04863e8b0ef8502f3fe1a837f02e56a998264014c5f62ffa6ce5392e27d001 7d6af51b01d5b2e629865c7effa82095bd295588b942e479b836e435ac21f3a3 -
024 |                         03 b33d6879385e4507d983af2883905f7c6d4f42cb3058e081b7ff4532eb53996d 7a0214439407d598d7e5f78487787d8bc047017f5c403edc6b2afc2f119192d3 -
022 |                       03 b77552c7dcb3ba759d6646170bbd60056776b437e87f2c966db77d4012a4d155 ef5af93999b395842519422bfaf327af9c75e70ca56e2aae87dd1ef3743f419b -
019 |                    03 be18b23f78d4f67c9b7c75a6adc645c7c1e039f76f3024c78110a32daf3aedf8 0213beec35c9c24828d741519efd099c3c645fb369e2cb5723156a76f4da4fdd -
018 |                   03 6ce33508a3bfbb8f04028be8e2bbe7acc8487f8c932b6cbadd6212a27698ef8c 41e74dc0872b098364838a595239ba383e1fc60890cfdb387eef5cd150c50e37 -
017 |                  03 5f3269be45e2e2ea015d529aa1dc6b9d6f8387eca844aa8f4e7b3fafb87bfcbb 931ccaf75c404470fbfd74171d44185337b780736cd49345229ded5c89670ca3 -
006 |       03 8fd2ac8164f2a6a48d5cb1d81d3c590f00c7c70cfafb31e029d99a7239e634f4 9e6e7d7373a71ac31494b3f165c25c687da6283f4133f29c0b7bea4a1cbac313 -
005 |      03 0c9a6eabb6b8f0edec38ab42532d4456b9c76eb2c9cf690f603dcc688566e05d 702d537e9b0d595b72a34e27e2c3a6f0ff3838f30504ce1fd626658cc619c73b -
003 |    03 a4d87747ecd146a09a14a531b889425c8fe308973b3fce622987d4fe27db17bc 7c59dde3350e7bbbfa4027dd328066bfa103b52c0ba752f7d7c0a0f55652194d -
002 |   03 c8d9659b4430c5c0dd89ce385731acd388dba5e3f24bcbc0e955e2cb602da315 5b2788b8132eb95f65eb5ace4776bda3701cf768c4c0319dd6782b00d824e473 -

For this key, the deepest key was flipped 31 times. What is the maximum number of times such thing can happen? So far I found a key 02000...090f, which can be flipped 4498 times! I thought that if the probability to get valid or invalid key is around 50%, then I will get something like 128, 256 or 512 as a hard maximum. Also, are there any numbers that can flip to themselves, so that X=Y and be a valid public keys?

█▀▀▀











█▄▄▄
▀▀▀▀▀▀▀▀▀▀▀
e
▄▄▄▄▄▄▄▄▄▄▄
█████████████
████████████▄███
██▐███████▄█████▀
█████████▄████▀
███▐████▄███▀
████▐██████▀
█████▀█████
███████████▄
████████████▄
██▄█████▀█████▄
▄█████████▀█████▀
███████████▀██▀
████▀█████████
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
c.h.
▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄
▀▀▀█











▄▄▄█
▄██████▄▄▄
█████████████▄▄
███████████████
███████████████
███████████████
███████████████
███░░█████████
███▌▐█████████
█████████████
███████████▀
██████████▀
████████▀
▀██▀▀
j2002ba2
Full Member
***
Offline Offline

Activity: 204
Merit: 437


View Profile
December 08, 2020, 11:14:37 AM
 #7

You could have fun the other way as well. For every y there are 3 possible x values. You could even combine both strategies.

For any number in range (0, p), 1/2 are valid x coordinates, 1/3 are valid y coordinates.
The probability any y coordinate is valid x coordinate is 50%.
There are (n-1)/3 y coordinates (n being the group order) ≈1.33*2254.
The average number of child points is 1. Any child point has 3 parents.
The longest chain could be in the order of 2128 points.
Most probably there are cycles, specially when the chain approaches 2127 points.

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4186
Merit: 8426



View Profile WWW
December 09, 2020, 02:41:23 AM
 #8

We start with some public key, for example 02000...001. When converting from compressed to uncompressed form, we can get both X and Y values for such point. We take Y value as X and use 02 or 03 prefix, thus creating another public key. Sometimes we will see that there is no key that can be constructed in such way. Then, we mark such key with this Y value as "visited" and try another path, so if we chose 02 prefix and we failed to find matching key, we choose 03. If none of them matched, we go back, unless we will return to our starting key.

If you want a real mind blower--

Given a field element t, compute


       c = sqrt(-3)
       d = (c - 1)/2
       w = c * t / (1 + 7 + t^2)
       x1 = d - t*w
       x2 = -(x1 + 1)
       x3 = 1 + 1/w^2


And at least one of x1, x2, or x3 will always be the x coordinate of a valid point.

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!