private keys bigger than N

[FossilFable]

Hi,

we can read in https://en.bitcoin.it/wiki/Private_key the following:

Range of valid ECDSA private keys
Nearly every 256-bit number is a valid ECDSA private key. Specifically, any 256-bit number from 0x1 to N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140 is a valid private key.
The range of valid private keys is governed by the secp256k1 ECDSA standard used by Bitcoin

In reality, even the full 256 bits range and beyond work
For Example,
 using 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, we get the address 1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm that is valid.

As far as I understood, in ECDSA calculations we use %N, therefore we loop, and there is also a prviate key < N that also gives the same address 1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm.

is that right ? (I am new at bitcoin & trying to learn these)

[/quote]

[ertil]

In reality, even the full 256 bits range and beyond work

It works, but it is unnecessary complicated.

using 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, we get the address 1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm that is valid.

Code:

private_key=000000000000000000000000000000014551231950b75fc4402da1732fc9bebe
public_key=039166C289B9F905E55F9E3DF9F69D7F356B4A22095F894F4715714AA4B56606AF
hash160=f5f5c490b6d86d83fda2143ebfab443f51bd3ebd
address=1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm

If you use values between 1 and N-1, then they are unique. If you keep adding N-value, then it doesn't change anything, it only makes everything more complicated, than it should be.

The only case, when it can be useful, is if you can optimize private to public key conversion somehow. For example: using double-and-add algorithm on 0x14551231950b75fc4402da1732fc9bebe is slow. But computing 2^256, and subtracting the base point is much faster, especially if you have pre-computed some tables of public keys, and you for example have hardcoded 2^255 as a private key for this double-and-add algorithm.

[mcdouglasx]

Technically, there are N/2 unique public keys on the x-axis. After that, the x-values ​​are repeated, but with the y-axis reversed, essentially mirroring them. Furthermore, for example, P2PKH addresses could have multiple private keys at different points on the curve. After all, Ripemd160 is 160 bits, as its name indicates, meaning there's a high probability that addresses have multiple access points. However, this doesn't affect Bitcoin because the probability of encountering such a collision is mathematically and computationally infeasible.

You can visualize it like an analog clock: 1 AM to 12 PM is half the curve, and 1 PM to 12 AM is its mirror image. Then everything repeats.

[Cricktor]

In reality, even the full 256 bits range and beyond work
For Example,
 using 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, we get the address 1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm that is valid.

The fact that you can derive a public address from a private key which is outside of valid range of Bitcoin private keys doesn't make it valid or useful. Normally a properly programmed wallet should reject such private keys.

You can try with Bitcoin Testnet3 or Testnet4 how far you get. At least that way you don't risk loosing valuable coins.

A quick test at bitaddress.org makes it reject above cited invalid private key.

[mcdouglasx]

In reality, even the full 256 bits range and beyond work
For Example,
 using 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, we get the address 1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm that is valid.

The fact that you can derive a public address from a private key which is outside of valid range of Bitcoin private keys doesn't make it valid or useful. Normally a properly programmed wallet should reject such private keys.

You can try with Bitcoin Testnet3 or Testnet4 how far you get. At least that way you don't risk loosing valuable coins.

A quick test at bitaddress.org makes it reject above cited invalid private key.

I agree. A clear example is that BIP32 or BIP39 don't use mod n; they simply invalidate it.

Any numerical key greater than N (the order of the curve) is modified by mod n to always remain within the curve. This is what I explained to the OP in my clock analogy. Technically, there is no number greater than N on the elliptic curve; it is only an illusion.

example:

python

Code:

N = 115792089237316195423570985008687907852837564279074904382605163141518161494337

Target = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

print(Target % N)

r: 432420386565659656852420866394968145598

Pk: 432420386565659656852420866394968145598
Pk HEX: 0x000000000000000000000000000000014551231950b75fc4402da1732fc9bebe
wif: KwDiBf89QgGbjEhKnhXJuH7grrzmjVFJVSqqLimWN6cB6k6v8AAF
cPub: 039166c289b9f905e55f9e3df9f69d7f356b4a22095f894f4715714aa4b56606af
uPub: 049166c289b9f905e55f9e3df9f69d7f356b4a22095f894f4715714aa4b56606aff181eb966be4a cb5cff9e16b66d809be94e214f06c93fd091099af98499255e7
H160: f5f5c490b6d86d83fda2143ebfab443f51bd3ebd
C_Addr: 1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm

Although trying to import the private key into many software programs will give you an error because it's larger than the order (it's just a redundant representation of a much smaller one), it's always possible to recover the real private key by applying the modulo. Most wallets don't allow you to do this because you could accidentally generate a very long private key whose modulo n is a vulnerable private key of just a few bits, like the one in the example.

[NotATether]

mod N is only used by software that actually generates private keys by first generating a general random 256-bit array, e.g. by random() or some equivalent call in C.

Because it is much faster - and safer - to generate an arbitrary number in a 256-bit boundary and then mod it than to try to patch the RNG.

AFAIK no other code bothers to do mod N.

[gmaxwell]

In reality, even the full 256 bits range and beyond work

only in defective software.

Reduction mod N is not even a valid way to generate private key-- it result in non-uniform keys. For secp256k1 the security loss is VERY small-- because N is so close to 2^256 you're never going to land in that range-- but for other curves it can be quite substantial.

Software should use rejection sampling.

Often the same procedures are used for generating nonces as private keys and even tiny biases of nonces will leak your keys.  All these people posting about lattice attacks are hoping you use biased nonces. Discard software that uses biased sampling.

[odolvlobo]

As far as I understood, in ECDSA calculations we use %N, therefore we loop, and there is also a prviate key < N that also gives the same address 1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm.

is that right ? (I am new at bitcoin & trying to learn these)

The answer to your question is yes, that is correct.

However, as gmaxwell has already pointed out, generating a random private key does not involve the mod operator because that would result in some keys being generated more often than others, which would be a security flaw.