Missing multiplies_x(k=2) for some curves

[garlonicon]

For secp256k1, it is easy to spot, that the generator was picked in a special way, if you halve that point:

multiplies_x(k=2)
+-------------+----------------------------------------------+
| Hx:         | 0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 |
| bits:       | 0xa6                                         |
| difference: | 0x5a                                         |
| ratio:      | 0.64844                                      |
+-------------+----------------------------------------------+

However, for some other curves, it is also the case, but the data is missing for some reason:

Sage code for sect163k1

F.<x> = GF(2)[]
K = GF(2^163, name="x", modulus= x^163 +  x^7 +  x^6 +  x^3 + 1)
E = EllipticCurve(K, (1, K.from_integer(0x000000000000000000000000000000000000000001), 0, 0, K.from_integer(0x000000000000000000000000000000000000000001)))
E.set_order(0x04000000000000000000020108a2e0cc0d99f8a5ef * 0x2)
G = E(K.from_integer(0x02fe13c0537bbc11acaa07d793de4e6d5e5c94eee8), K.from_integer(0x0289070fb05d38ff58321f2e800536d538ccdaa3d9))
private_key = 0x200000000000000000001008451706606ccfc52f7
P = private_key*G
print(hex(P[0].to_integer()),hex(P[1].to_integer()))

output:

0x23e21d6019e1211f6bd47ec180256e97 0x1055096ab0cce03fdb8ba9bf2d02e94a1205eee5e

Sage code for sect113r1

F.<x> = GF(2)[]
K = GF(2^113, name="x", modulus= x^113 +  x^9 + 1)
E = EllipticCurve(K, (1, K.from_integer(0x003088250ca6e7c7fe649ce85820f7), 0, 0, K.from_integer(0x00e8bee4d3e2260744188be0e9c723)))
E.set_order(0x0100000000000000d9ccec8a39e56f * 0x2)
G = E(K.from_integer(0x009d73616f35f4ab1407d73562c10f), K.from_integer(0x00a52830277958ee84d1315ed31886))
private_key = 0x800000000000006ce676451cf2b8
P = private_key*G
print(hex(P[0].to_integer()),hex(P[1].to_integer()))

output:

0x3 0x1a7078c5d29ee7ea6e8ff326518f5

Here, in sect163k1, half of the generator gives us some 128-bit number (instead of expected 163-bit), which sounds like "x=MD5(something)" or a similar way of picking the generator. And in case of sect113r1, there is "x=3", which is probably the lowest x-value, which resulted in a valid point on this curve.

[VladaSedlacek]

Hi, thank you for these observations. We decided against running most traits on the binary curves in the end, as they are internally handled a bit differently, and we felt it was not worth the effort and computation time due to their negligible practical usage.

It is good to see that the sect163k1 case is consistent with Thomas Pornin's explanation:
https://crypto.stackexchange.com/questions/60420/what-does-the-special-form-of-the-base-point-of-secp256k1-allow .
Perhaps the sect113r1 case was handled different because all the standard hash functions already had outputs of more than 113 bits?

[stwenhao]

One more interesting case: https://dissect.crocs.fi.muni.cz/curve/wap-wsg-idm-ecid-wtls5

In c2pnb163v1, half of the generator is also interesting:

F.<x> = GF(2)[]
K = GF(2^163, name="x", modulus= x^163 +  x^8 +  x^2 +  x^1 + 1)
E = EllipticCurve(K, (1, K.from_integer(0x072546b5435234a422e0789675f432c89435de5242), 0, 0, K.from_integer(0x00c9517d06d5240d3cff38c74b20b6cd4d6f9dd4d9)))
E.set_order(0x0400000000000000000001e60fc8821cc74daeafc1 * 0x2)
G = E(K.from_integer(0x07af69989546103d79329fcc3d74880f33bbe803cb), K.from_integer(0x01ec23211b5966adea1d3f87f7ea5848aef0b7ca9f))
private_key = 0x200000000000000000000f307e4410e63a6d757e1
P = private_key*G
print(hex(P[0].to_integer()),hex(P[1].to_integer()))

output:

0x13152a6b92ceb34c0969c282324645cb 0x77244f830c961828732d1dd15db2a61a049ab1d06

Here, half of the generator is again some 128-bit number, instead of expected 163-bit.