Skip to content

Better rounding of ECDSA key bit counts reported with -text key outputs? #29532

@vdukhovni

Description

@vdukhovni

[ This issue is a mishmash of a question, feature request and bug report. Unclear what category it fits best. Closely related to, but different from #10542 ]

Presently, when reporting the nominal bit counts of ECDSA private or public keys as part of the "TEXT" output format (e.g. with openssl pkey -text ...), the value used is the raw bit count of the order $n$ of the group's base point (element count of the generated cyclic group, i.e. the number of possible distinct private keys).
This is quite reasonable in the many cases in which the order is just below a power of two (when the group order is $2^k - ε$ the reported bit count is $k$).
It is at least somewhat surprising to report $k+1$ when the group order is $2^k + ε$. Yes it takes $k+1$ bits to represent the exact order, but what's relevant in terms of the key's security is that there are roughly $2^k$ possible private key values. The entropy of a uniform distribution over the private keys is essentially $k$, not $k+1$.

So perhaps we should round towards the nearest power of 2 (on a log scale), mapping $2^k \pm ε \rightarrow k$.

This would result in reporting 1 bit less for the curves listed below.

[ In some of the cases the group order is quite far from a 2-power, it is instead approximately ${4/3} \cdot 2^k \pm ε$ with a fractional entropy of $\log_2 (4/3) \sim 0.42$. These are also rounded down.
If rounding the key space entropy bits to the nearest whole number is not your cup tea, what should be reported instead? ]

ECC Named Groups: Order and Entropy Mapping

Curve Name Order Bits Effective Bits Cofactor ($h$) Entropy $log_2 n$
c2pnb163v1 163 162 2 162.000
c2tnb191v1 191 190 2 190.000
c2tnb191v2 190 189 4 189.000
c2tnb239v1 238 237 4 237.000
secp160k1 161 160 1 160.000
secp160r1 161 160 1 160.000
secp160r2 161 160 1 160.000
secp224k1 225 224 1 224.000
sect113r1 113 112 2 112.000
sect113r2 113 112 2 112.000
sect131r1 131 130 2 130.000
sect131r2 131 130 2 130.000
sect163k1 163 162 2 162.000
sect163r2 163 162 2 162.000
sect193r1 193 192 2 192.000
sect193r2 193 192 2 192.000
sect233k1 232 231 4 231.000
sect233r1 233 232 2 232.000
sect239k1 238 237 4 237.000
sect409r1 409 408 2 408.000
sect571k1 570 569 4 569.000
wap-wsg-idm-ecid-wtls10 232 231 4 231.000
wap-wsg-idm-ecid-wtls11 233 232 2 232.000
wap-wsg-idm-ecid-wtls3 163 162 2 162.000
wap-wsg-idm-ecid-wtls4 113 112 2 112.000
wap-wsg-idm-ecid-wtls5 163 162 2 162.000
wap-wsg-idm-ecid-wtls7 161 160 1 160.000
wap-wsg-idm-ecid-wtls8 113 112 1 112.000
wap-wsg-idm-ecid-wtls9 161 160 1 160.000
c2pnb176v1 161 160 65390 160.003
c2pnb368w1 353 352 65392 352.003
c2pnb272w1 257 256 65286 256.006
c2pnb208w1 193 192 65096 192.010
c2pnb304w1 289 288 65070 288.010
brainpoolP384r1 384 383 1 383.137
brainpoolP384t1 384 383 1 383.137
brainpoolP256r1 256 255 1 255.409
brainpoolP256t1 256 255 1 255.409
Oakley-EC2N-3 154 153 3 153.415
c2tnb191v3 189 188 6 188.415
c2tnb239v2 237 236 6 236.415
brainpoolP512r1 512 511 1 511.417
brainpoolP512t1 512 511 1 511.417

The table below shows curves whose current reported key bit count matches the rounded entropy bits.
The last 15 entries are rounded up non-trivially from a fractional part of ~0.6–0.9.

(Unchanged) ECC Named Groups: Order and Entropy Mapping

Curve Name Order Bits Effective Bits Cofactor ($h$) Entropy $log_2 n$
Oakley-EC2N-4 184 184 2 184.000
c2pnb163v2 162 162 2 162.000
c2pnb163v3 162 162 2 162.000
prime192v1 192 192 1 192.000
prime192v2 192 192 1 192.000
prime192v3 192 192 1 192.000
prime239v1 239 239 1 239.000
prime239v2 239 239 1 239.000
prime239v3 239 239 1 239.000
prime256v1 256 256 1 256.000
secp128r1 128 128 1 128.000
secp128r2 126 126 4 126.000
secp192k1 192 192 1 192.000
secp224r1 224 224 1 224.000
secp256k1 256 256 1 256.000
secp384r1 384 384 1 384.000
secp521r1 521 521 1 521.000
sect163r1 162 162 2 162.000
sect283k1 281 281 4 281.000
sect283r1 282 282 2 282.000
sect409k1 407 407 4 407.000
sect571r1 570 570 2 570.000
wap-wsg-idm-ecid-wtls1 112 112 2 112.000
wap-wsg-idm-ecid-wtls12 224 224 1 224.000
brainpoolP192r1 192 192 1 191.607
brainpoolP192t1 192 192 1 191.607
c2tnb239v3 236 236 10 235.678
c2tnb431r1 418 418 10080 417.701
brainpoolP320r1 320 320 1 319.724
brainpoolP320t1 320 320 1 319.724
c2tnb359v1 353 353 76 352.752
brainpoolP224r1 224 224 1 223.753
brainpoolP224t1 224 224 1 223.753
secp112r1 112 112 1 111.778
secp112r2 110 110 4 109.778
wap-wsg-idm-ecid-wtls6 112 112 1 111.778
brainpoolP160r1 160 160 1 159.866
brainpoolP160t1 160 160 1 159.866

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions