Why so many p-values were skipped in case of secp160k1?

[stwenhao]

When we try to re-generate curves secp160k1, secp192k1, secp224k1, and secp256k1, we start from "2^n-2^32", and decrement p-value, to get some prime number, forming a curve. In case of secp192k1, secp224k1, and secp256k1, the first matching value was picked. However, in case of secp160k1, the p-value is actually the fifth below 2^160-2^32:

Code:

p=0xfffffffffffffffffffffffffffffffefffff0a7   n=0xffffffffffffffffffff66fcc05801f00e15f6a5    b=12
p=0xfffffffffffffffffffffffffffffffeffffbde9   n=0xfffffffffffffffffffe280724f449253bc2e9ab    b=11
p=0xfffffffffffffffffffffffffffffffeffffb88b   n=0xfffffffffffffffffffe206e5eb5194f32e3ca55    b=2
p=0xfffffffffffffffffffffffffffffffeffffb0ab   n=0xfffffffffffffffffffe01cf87c16ee51306af13    b=17
p=0xfffffffffffffffffffffffffffffffeffffac73   n=0x100000000000000000001b8fa16dfab9aca16b6b3   b=7
...

Why those four p-values were skipped? All of them have some matching b-value, where n-value is a prime.

This is how it looks for secp192k1:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffeffffee37   n=0xfffffffffffffffffffffffe26f2fc170f69466a74defd8d    b=3
p=0xfffffffffffffffffffffffffffffffffffffffeffffccb9   n=0x1000000000000000000000001e58d67ad78297d7bbd3171ab   b=5
p=0xfffffffffffffffffffffffffffffffffffffffeffff9eb1   n=0xffffffffffffffffffffffffa52c5f9d6368c4ecfda4b679    b=7
p=0xfffffffffffffffffffffffffffffffffffffffeffff9e45   n=0xfffffffffffffffffffffffebaf27eff4602ec4421c5be6b    b=2
p=0xfffffffffffffffffffffffffffffffffffffffeffff91eb   n=0x10000000000000000000000008b5b258a479c4ec50f0453fb   b=3
...

secp224k1:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d   n=0x10000000000000000000000000001dce8d2ec6184caf0a971769fb1f7   b=2
p=0xfffffffffffffffffffffffffffffffffffffffffffffffeffffc2a5   n=0x100000000000000000000000000017b648f48e73e5bad81df9899f021   b=5
p=0xfffffffffffffffffffffffffffffffffffffffffffffffeffffb29d   n=0xffffffffffffffffffffffffffff59d54bf3175c3f7aa7dd7cf534bd    b=6
p=0xfffffffffffffffffffffffffffffffffffffffffffffffeffff9671   n=0x10000000000000000000000000001fcadd7fc4b7f91a2f7f7dab61a81   b=29
p=0xfffffffffffffffffffffffffffffffffffffffffffffffeffff75dd   n=0xffffffffffffffffffffffffffffe2716c960d555bc3a98c1a97cd15    b=6
...

secp256k1:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f   n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141    b=7
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffe117   n=0xffffffffffffffffffffffffffffffffc0ad397ea94d65ed5001a2f3f2812f4d    b=10
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffbaef   n=0x100000000000000000000000000000000f2cfcb48012d9e76586a1c1564109bed   b=12
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffb0ed   n=0x100000000000000000000000000000000f35b461eedf9baf1d8393eecc2fef1ff   b=5
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffa33d   n=0x100000000000000000000000000000001f2cfdf190f0eff9bfa36ca2fe9add651   b=15
...

Also, I wonder why b=5 was picked for secp224k1, where b=2 would work as well, and would lead to the same n-value. Are there any hidden constraints, that should be considered, when picking b-value?

[gmaxwell]

The field and curve have to admit a primitive root of unity in order to make the efficient endomorphism work, so that's going to be part of the selection criteria for any of the K curves.

[COBRAS]

The field and curve have to admit a primitive root of unity in order to make the efficient endomorphism work, so that's going to be part of the selection criteria for any of the K curves.

primitive root ?

Now I understand. It is slightly more complicated than that.
Private keys are not multiple of 18051648. Private keys are power of z mod q, where z is a primitive root mod q.

source

https://github.com/cysecud/ecc_weak_keys/issues/2#issuecomment-2508282587


primitive root generate vulnerable subgroups what provide way to breack 256 bit key in seconds.On github more info about it.

[gmaxwell]

The field and curve have to admit a primitive root of unity in order to make the efficient endomorphism work, so that's going to be part of the selection criteria for any of the K curves.

primitive root ?

Now I understand. It is slightly more complicated than that.
Private keys are not multiple of 18051648. Private keys are power of z mod q, where z is a primitive root mod q.

source

(URL REMOVED)


primitive root generate vulnerable subgroups what provide way to breack 256 bit key in seconds.On github more info about it.

You're spouting nonsense, stop linking to fake 'weak key' bullshit.  These are posts of scammers tricking people into running malware.

Secp256k1 is prime ordered, there are no subgroups and all keys are equivalent.

[stwenhao]

The field and curve have to admit a primitive root of unity in order to make the efficient endomorphism work

Then, why the fifth result is better, than the previous four?

First case:

Code:

p=0xfffffffffffffffffffffffffffffffefffff0a7
n=0xffffffffffffffffffff66fcc05801f00e15f6a5
print(factor(p-1))
print(factor(n-1))
2 * 3 * 5^3 * 47 * 53047029017 * 781590225224828585519938229586371
2^2 * 3 * 5^2 * 7 * 2899747 * 36757921 * 6529335183103701884104987031471
(p-1)/6=0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffffd71
3^0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffffd71 mod p = 0x91aff7895cf35b08d22f52015ae9d8825b737115
0x91aff7895cf35b08d22f52015ae9d8825b737115^1 mod p = 0x91aff7895cf35b08d22f52015ae9d8825b737115
0x91aff7895cf35b08d22f52015ae9d8825b737115^2 mod p = 0x91aff7895cf35b08d22f52015ae9d8825b737114
0x91aff7895cf35b08d22f52015ae9d8825b737115^3 mod p = 0xfffffffffffffffffffffffffffffffefffff0a6
0x91aff7895cf35b08d22f52015ae9d8825b737115^4 mod p = 0x6e500876a30ca4f72dd0adfea516277ca48c7f92
0x91aff7895cf35b08d22f52015ae9d8825b737115^5 mod p = 0x6e500876a30ca4f72dd0adfea516277ca48c7f93
0x91aff7895cf35b08d22f52015ae9d8825b737115^6 mod p = 1
(n-1)/6=0x2aaaaaaaaaaaaaaaaaaa912a200eaafd57ae53c6
2^0x2aaaaaaaaaaaaaaaaaaa912a200eaafd57ae53c6 mod n = 0x3676556091e5d5f4412340f820c45e0d95720bb1
0x3676556091e5d5f4412340f820c45e0d95720bb1^1 mod n = 0x3676556091e5d5f4412340f820c45e0d95720bb1
0x3676556091e5d5f4412340f820c45e0d95720bb1^2 mod n = 0x3676556091e5d5f4412340f820c45e0d95720bb0
0x3676556091e5d5f4412340f820c45e0d95720bb1^3 mod n = 0xffffffffffffffffffff66fcc05801f00e15f6a4
0x3676556091e5d5f4412340f820c45e0d95720bb1^4 mod n = 0xc989aa9f6e1a2a0bbedc26049f93a3e278a3eaf4
0x3676556091e5d5f4412340f820c45e0d95720bb1^5 mod n = 0xc989aa9f6e1a2a0bbedc26049f93a3e278a3eaf5
0x3676556091e5d5f4412340f820c45e0d95720bb1^6 mod n = 1

Second case:

Code:

p=0xfffffffffffffffffffffffffffffffeffffbde9
n=0xfffffffffffffffffffe280724f449253bc2e9ab
print(factor(p-1))
print(factor(n-1))
2^3 * 3 * 5 * 13 * 35311 * 1734105407 * 15299921361408479232101220799823
2 * 3^2 * 1239751872323 * 65492569295445503842094731524235663
(p-1)/6=0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffff4fc
7^0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffff4fc mod p = 0x9da186f30c058cd41ce19f4fbabba0bd2edeea1d
0x9da186f30c058cd41ce19f4fbabba0bd2edeea1d^1 mod p = 0x9da186f30c058cd41ce19f4fbabba0bd2edeea1d
0x9da186f30c058cd41ce19f4fbabba0bd2edeea1d^2 mod p = 0x9da186f30c058cd41ce19f4fbabba0bd2edeea1c
0x9da186f30c058cd41ce19f4fbabba0bd2edeea1d^3 mod p = 0xfffffffffffffffffffffffffffffffeffffbde8
0x9da186f30c058cd41ce19f4fbabba0bd2edeea1d^4 mod p = 0x625e790cf3fa732be31e60b045445f41d120d3cc
0x9da186f30c058cd41ce19f4fbabba0bd2edeea1d^5 mod p = 0x625e790cf3fa732be31e60b045445f41d120d3cd
0x9da186f30c058cd41ce19f4fbabba0bd2edeea1d^6 mod p = 1
(n-1)/6=0x2aaaaaaaaaaaaaaaaaaa5c0130d3618634a07c47
2^0x2aaaaaaaaaaaaaaaaaaa5c0130d3618634a07c47 mod n = 0xcd1ac91ea54ed58289537871ef83ba4696ef6541
0xcd1ac91ea54ed58289537871ef83ba4696ef6541^1 mod n = 0xcd1ac91ea54ed58289537871ef83ba4696ef6541
0xcd1ac91ea54ed58289537871ef83ba4696ef6541^2 mod n = 0xcd1ac91ea54ed58289537871ef83ba4696ef6540
0xcd1ac91ea54ed58289537871ef83ba4696ef6541^3 mod n = 0xfffffffffffffffffffe280724f449253bc2e9aa
0xcd1ac91ea54ed58289537871ef83ba4696ef6541^4 mod n = 0x32e536e15ab12a7d76aaaf9535708edea4d3846a
0xcd1ac91ea54ed58289537871ef83ba4696ef6541^5 mod n = 0x32e536e15ab12a7d76aaaf9535708edea4d3846b
0xcd1ac91ea54ed58289537871ef83ba4696ef6541^6 mod n = 1

Third case:

Code:

p=0xfffffffffffffffffffffffffffffffeffffb88b
n=0xfffffffffffffffffffe206e5eb5194f32e3ca55
print(factor(p-1))
print(factor(n-1))
2 * 3 * 79 * 89075355247 * 15672870695221 * 2208588725957035913947
2^2 * 3 * 11 * 55333 * 62971 * 448387 * 591997856471113 * 11970917036057113
(p-1)/6=0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffff417
2^0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffff417 mod p = 0x60b88c0a9e45bee27d8e95123c9fb491c7c3f66a
0x60b88c0a9e45bee27d8e95123c9fb491c7c3f66a^1 mod p = 0x60b88c0a9e45bee27d8e95123c9fb491c7c3f66a
0x60b88c0a9e45bee27d8e95123c9fb491c7c3f66a^2 mod p = 0x60b88c0a9e45bee27d8e95123c9fb491c7c3f669
0x60b88c0a9e45bee27d8e95123c9fb491c7c3f66a^3 mod p = 0xfffffffffffffffffffffffffffffffeffffb88a
0x60b88c0a9e45bee27d8e95123c9fb491c7c3f66a^4 mod p = 0x9f4773f561ba411d82716aedc3604b6d383bc221
0x60b88c0a9e45bee27d8e95123c9fb491c7c3f66a^5 mod p = 0x9f4773f561ba411d82716aedc3604b6d383bc222
0x60b88c0a9e45bee27d8e95123c9fb491c7c3f66a^6 mod p = 1
(n-1)/6=0x2aaaaaaaaaaaaaaaaaaa5abd0fc8d98d3325f70e
2^0x2aaaaaaaaaaaaaaaaaaa5abd0fc8d98d3325f70e mod n = 0x1bba2725f9272f0be7d791d11bc24a9559b2197f
0x1bba2725f9272f0be7d791d11bc24a9559b2197f^1 mod n = 0x1bba2725f9272f0be7d791d11bc24a9559b2197f
0x1bba2725f9272f0be7d791d11bc24a9559b2197f^2 mod n = 0x1bba2725f9272f0be7d791d11bc24a9559b2197e
0x1bba2725f9272f0be7d791d11bc24a9559b2197f^3 mod n = 0xfffffffffffffffffffe206e5eb5194f32e3ca54
0x1bba2725f9272f0be7d791d11bc24a9559b2197f^4 mod n = 0xe445d8da06d8d0f418268e9d42f2ceb9d931b0d6
0x1bba2725f9272f0be7d791d11bc24a9559b2197f^5 mod n = 0xe445d8da06d8d0f418268e9d42f2ceb9d931b0d7
0x1bba2725f9272f0be7d791d11bc24a9559b2197f^6 mod n = 1

Fourth case:

Code:

p=0xfffffffffffffffffffffffffffffffeffffb0ab
n=0xfffffffffffffffffffe01cf87c16ee51306af13
print(factor(p-1))
print(factor(n-1))
2 * 3 * 5 * 19 * 140651526998393461 * 18229720038936662228091119381
2 * 3 * 243583606221817153033947070569211419720146121347
(p-1)/6=0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffff2c7
2^0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffff2c7 mod p = 0x2f34ffb5c9465714553f55d709e49101276de86c
0x2f34ffb5c9465714553f55d709e49101276de86c^1 mod p = 0x2f34ffb5c9465714553f55d709e49101276de86c
0x2f34ffb5c9465714553f55d709e49101276de86c^2 mod p = 0x2f34ffb5c9465714553f55d709e49101276de86b
0x2f34ffb5c9465714553f55d709e49101276de86c^3 mod p = 0xfffffffffffffffffffffffffffffffeffffb0aa
0x2f34ffb5c9465714553f55d709e49101276de86c^4 mod p = 0xd0cb004a36b9a8ebaac0aa28f61b6efdd891c83f
0x2f34ffb5c9465714553f55d709e49101276de86c^5 mod p = 0xd0cb004a36b9a8ebaac0aa28f61b6efdd891c840
0x2f34ffb5c9465714553f55d709e49101276de86c^6 mod p = 1
(n-1)/6=0x2aaaaaaaaaaaaaaaaaaa55a296a03d262dd67283
2^0x2aaaaaaaaaaaaaaaaaaa55a296a03d262dd67283 mod n = 0x61059493356bfd9f6c69fe6ac3c0ddae8d424bb9
0x61059493356bfd9f6c69fe6ac3c0ddae8d424bb9^1 mod n = 0x61059493356bfd9f6c69fe6ac3c0ddae8d424bb9
0x61059493356bfd9f6c69fe6ac3c0ddae8d424bb9^2 mod n = 0x61059493356bfd9f6c69fe6ac3c0ddae8d424bb8
0x61059493356bfd9f6c69fe6ac3c0ddae8d424bb9^3 mod n = 0xfffffffffffffffffffe01cf87c16ee51306af12
0x61059493356bfd9f6c69fe6ac3c0ddae8d424bb9^4 mod n = 0x9efa6b6cca94026093940364c400913685c4635a
0x61059493356bfd9f6c69fe6ac3c0ddae8d424bb9^5 mod n = 0x9efa6b6cca94026093940364c400913685c4635b
0x61059493356bfd9f6c69fe6ac3c0ddae8d424bb9^6 mod n = 1

And the original secp160k1:

Code:

p=0xfffffffffffffffffffffffffffffffeffffac73
n=0x100000000000000000001b8fa16dfab9aca16b6b3
print(factor(p-1))
print(factor(n-1))
2 * 3 * 5 * 7 * 113 * 61588775277324185343602394973294691093621473
2 * 3 * 5 * 8837 * 42918291593381467397 * 128449012680369359431471
(p-1)/6=0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffff213
2^0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa7ffff213 mod p = 0x9ba48cba5ebcb9b6bd33b92830b2a2e0e192f10b
0x9ba48cba5ebcb9b6bd33b92830b2a2e0e192f10b^1 mod p = 0x9ba48cba5ebcb9b6bd33b92830b2a2e0e192f10b
0x9ba48cba5ebcb9b6bd33b92830b2a2e0e192f10b^2 mod p = 0x9ba48cba5ebcb9b6bd33b92830b2a2e0e192f10a
0x9ba48cba5ebcb9b6bd33b92830b2a2e0e192f10b^3 mod p = 0xfffffffffffffffffffffffffffffffeffffac72
0x9ba48cba5ebcb9b6bd33b92830b2a2e0e192f10b^4 mod p = 0x645b7345a143464942cc46d7cf4d5d1e1e6cbb68
0x9ba48cba5ebcb9b6bd33b92830b2a2e0e192f10b^5 mod p = 0x645b7345a143464942cc46d7cf4d5d1e1e6cbb69
0x9ba48cba5ebcb9b6bd33b92830b2a2e0e192f10b^6 mod p = 1
(n-1)/6=0x2aaaaaaaaaaaaaaaaaaaf429ae7a9c99cc591e73
2^0x2aaaaaaaaaaaaaaaaaaaf429ae7a9c99cc591e73 mod n = 0xf3c6393c4c5c9288fe47f1dff787a6ec6d16b2bf
0xf3c6393c4c5c9288fe47f1dff787a6ec6d16b2bf^1 mod n = 0xf3c6393c4c5c9288fe47f1dff787a6ec6d16b2bf
0xf3c6393c4c5c9288fe47f1dff787a6ec6d16b2bf^2 mod n = 0xf3c6393c4c5c9288fe47f1dff787a6ec6d16b2be
0xf3c6393c4c5c9288fe47f1dff787a6ec6d16b2bf^3 mod n = 0x100000000000000000001b8fa16dfab9aca16b6b2
0xf3c6393c4c5c9288fe47f1dff787a6ec6d16b2bf^4 mod n = 0xc39c6c3b3a36d7701b9c71a1f5804ae5d0003f4
0xf3c6393c4c5c9288fe47f1dff787a6ec6d16b2bf^5 mod n = 0xc39c6c3b3a36d7701b9c71a1f5804ae5d0003f5
0xf3c6393c4c5c9288fe47f1dff787a6ec6d16b2bf^6 mod n = 1

[magick]

Also, I wonder why b=5 was picked for secp224k1, where b=2 would work as well, and would lead to the same n-value. Are there any hidden constraints, that should be considered, when picking b-value?

https://csrc.nist.gov/pubs/sp/800/57/pt1/r5/final

https://csrc.nist.gov/pubs/sp/800/186/final

https://cacr.uwaterloo.ca/hac/