NSA and ECC

[brainless]

I am very satisfied with his answers.  The only thing left is to find out (if we can) is exactly how the random parameters were selected.

I did a quick check on this assumption

Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024.  I would not be surprised if s was the smallest value of this form, but I did not check.

The test code finds all primes of the form p = 2^256 - 2^32 - t where t < 1024.

Code:

import java.math.BigInteger;

public class PrimeTest {

        public static void main(String[] args) {

                BigInteger a = BigInteger.valueOf(2).pow(256);
                BigInteger b = BigInteger.valueOf(2).pow(32);

                BigInteger top = a.subtract(b);

                for (int t = 0; t < 1024; t++) {

                        BigInteger test = top.subtract(BigInteger.valueOf(t));

                        if (test.isProbablePrime(1024)) {
                                System.out.println(test.toString(16) + " (t = " + t + ")");
                        }

                }

        }
}

The result is

Code:

fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9 (t = 263)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe99 (t = 359)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe97 (t = 361)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe19 (t = 487)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1d (t = 739)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4b (t = 949)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f (t = 977)

The prime for t = 977 is the one that was selected for the curve.  It is the highest t that is lower than 1024.

pls check is your above found p is correct or wrong, or maybe i am doing calc wrong, advice

here is your selection P
115792089237316195423570985008687907853269984665640564039457584007908834672377
115792089237316195423570985008687907853269984665640564039457584007908834672281
115792089237316195423570985008687907853269984665640564039457584007908834672279
115792089237316195423570985008687907853269984665640564039457584007908834672153
115792089237316195423570985008687907853269984665640564039457584007908834671901
115792089237316195423570985008687907853269984665640564039457584007908834671691
115792089237316195423570985008687907853269984665640564039457584007908834671663
115792089237316195423570985008687907853269984665640564039457584007908834671591
115792089237316195423570985008687907853269984665640564039457584007908834671583
115792089237316195423570985008687907853269984665640564039457584007908834671301
115792089237316195423570985008687907853269984665640564039457584007908834671033
115792089237316195423570985008687907853269984665640564039457584007908834670671


go to this ecc calc and fill following details
http://www.christelbach.com/eccalculator.aspx

p = 115792089237316195423570985008687907853269984665640564039457584007908834671583
a = 0
b = 7
px = 115301655840403608332148854465368444683257224081574702572138639602380667382125
py = 103799472776126890762485670055583971987299536955028941653349419016168013365384

qx = 52658829913452240860711750781961153521895864895692055913373819304893658879667
qy = 33725064078989563529395744584539757872089003472888698368252453876478056770565

and press P + Q
you will see B=7 changed to
b = 32267065813313537246304986561842436172856576584501774751507060994620472625355

mean your Prime value for fit in formula Y2=X3+AX+B , p prime Failed
save try all with P value to change, only p value original got by 977 will work, and b =7 will never change on that testing site
can you all start again to find correct P other then - 977, which stand for b =7
or advice me where i am wrong

[vjudeu]

can you all start again to find correct P other then - 977, which stand for b =7

The next value is far away from that, it is this one:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffeb1f9
n=0x100000000000000000000000000000000504a3f8c8884f6dcad9dafa44b7060bd

If you want to reproduce that, you can use this Sage script:

Code:

p=previous_prime(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f)
n=4
while(not is_prime(n)):
    P=GF(p)
    aP=P(0x0)
    bP=P(0x7)
    curve=EllipticCurve(P,(aP,bP))
    n=curve.order()
    print("p="+hex(p))
    print("n="+hex(n))
    p=previous_prime(p)

If you put "2^256-2^32" as your starting point, you can see this result:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9
n=0xffffffffffffffffffffffffffffffff9d70b40e72725ad652cd62c55808d873
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe99
n=0x100000000000000000000000000000000b3c017eacf02babf49040910abee2e35
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe97
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe98
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe19
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe1a
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1d
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1e
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4b
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4c
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

or advice me where i am wrong

You are simply checking p-value only, while you should also check n-value. Recently, garlonicon had the same problem, see this topic: https://asktom.cf/index.php?topic=5464362.0

Also note that p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffeb1f9 does not allow you to use n-value to form another curve, that will give you p-value back. But it is acceptable, because for other curves it is also not the case, it is just a coincidence that secp256k1 has such property.

[Nellyj200x]

I wrote a small program that allows you to quickly check if a Bitcoin file has a transaction in it, and also checks whether it is a valid Bitcoin file and whether it is locked.
https://github.com/Humble2020/BitcoinFile-Verifier

[brainless]

pls check is your above found p is correct or wrong, or maybe i am doing calc wrong, advice

here is your selection P
115792089237316195423570985008687907853269984665640564039457584007908834672377
115792089237316195423570985008687907853269984665640564039457584007908834672281
115792089237316195423570985008687907853269984665640564039457584007908834672279
115792089237316195423570985008687907853269984665640564039457584007908834672153
115792089237316195423570985008687907853269984665640564039457584007908834671901
115792089237316195423570985008687907853269984665640564039457584007908834671691
115792089237316195423570985008687907853269984665640564039457584007908834671663
115792089237316195423570985008687907853269984665640564039457584007908834671591
115792089237316195423570985008687907853269984665640564039457584007908834671583
115792089237316195423570985008687907853269984665640564039457584007908834671301
115792089237316195423570985008687907853269984665640564039457584007908834671033
115792089237316195423570985008687907853269984665640564039457584007908834670671


go to this ecc calc and fill following details
http://www.christelbach.com/eccalculator.aspx

p = 115792089237316195423570985008687907853269984665640564039457584007908834671583
a = 0
b = 7
px = 115301655840403608332148854465368444683257224081574702572138639602380667382125
py = 103799472776126890762485670055583971987299536955028941653349419016168013365384

qx = 52658829913452240860711750781961153521895864895692055913373819304893658879667
qy = 33725064078989563529395744584539757872089003472888698368252453876478056770565

and press P + Q
you will see B=7 changed to
b = 32267065813313537246304986561842436172856576584501774751507060994620472625355

mean your Prime value for fit in formula Y2=X3+AX+B , p prime Failed
save try all with P value to change, only p value original got by 977 will work, and b =7 will never change on that testing site
can you all start again to find correct P other then - 977, which stand for b =7
or advice me where i am wrong
[/quote]

Question is below is simple formula for use P to substract 2 point, there is no n value involve,
p4 = int(2**256 - 2**32 - 977)

dx = (x1 - x2) % p4
dy = (y1 - ((p)-y2)) % p4
c1 = (dy * gmpy2.invert(dx, p4)) % p4
cu = dy * gmpy2.invert(dx, p4) % p4

Rx = (((c1*c1)%p4) - x2 - x1) % p4
Ry = ((c1*((x2 - Rx))) - y3) % p4
print (Rx , Ry) # 6 sub, 3 mul, 1 inv
print (hex(Rx), hex(Ry))

if P we choose from your generated P list as above you mention, results goes wrong, and even its fail to comply with B = 7

[brainless]

can you all start again to find correct P other then - 977, which stand for b =7

The next value is far away from that, it is this one:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffeb1f9
n=0x100000000000000000000000000000000504a3f8c8884f6dcad9dafa44b7060bd

If you want to reproduce that, you can use this Sage script:

Code:

p=previous_prime(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f)
n=4
while(not is_prime(n)):
    P=GF(p)
    aP=P(0x0)
    bP=P(0x7)
    curve=EllipticCurve(P,(aP,bP))
    n=curve.order()
    print("p="+hex(p))
    print("n="+hex(n))
    p=previous_prime(p)

If you put "2^256-2^32" as your starting point, you can see this result:

Code:

p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9
n=0xffffffffffffffffffffffffffffffff9d70b40e72725ad652cd62c55808d873
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe99
n=0x100000000000000000000000000000000b3c017eacf02babf49040910abee2e35
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe97
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe98
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe19
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe1a
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1d
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1e
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4b
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4c
p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

or advice me where i am wrong

You are simply checking p-value only, while you should also check n-value. Recently, garlonicon had the same problem, see this topic: https://asktom.cf/index.php?topic=5464362.0

Also note that p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffeb1f9 does not allow you to use n-value to form another curve, that will give you p-value back. But it is acceptable, because for other curves it is also not the case, it is just a coincidence that secp256k1 has such property.

Can we reverse this script, like we insert N for search P, in series search

[rdenkye]

...

1 : 29896722852569046015560700294576055776214335159245303116488692907525646231534  is a point on our curve, as is
2 : 46580984542418694471253469931035885126779956971428003686700937153791839982430

and so on. The first missing x, other than zero obviously, is 5.

(1,29896722852569046015560700294576055776214335159245303116488692907525646231534  )

The scalar value of this point is unknown, right?

[stwenhao]

The scalar value of this point is unknown, right?

It is unknown. But it doesn't stop people from moving coins from addresses with unknown public keys. For example: https://mempool.space/testnet/address/032baf163f5e27261ab3228e61fb86dc98054abd514751fce93d7444e8fbc6a293

As you can see, R-value of that signature is set to 020000000000000000000000000000000000000000000000000000000000000001, and it is valid. Because when the private key is not needed to verify a signature, bugs like SIGHASH_SINGLE can be abused, to move coins from precomputed P2PKs with unknown private keys.

[F- link]

Was reading something online that says that the NSA had added a backdoor into the standard by influencing the choice of constants in a way that an attacker with a secret value could predict future random numbers.

[Cricktor]

...

Have you tried to actually read a bit in this really old thread (it started in 2013, remember, and has been revived after 9 years maybe due to ignorance of necro-bumping)?

I ask because from a quick glimpse over it, this is at least partly covered on the first pages, isn't it?

You don't provide any source of what you're chewing over again. I don't say, you spread nonsense, urban legends or conspiracy, but it's simply bad habit to spit out such claims and spread them without referring to actual sources, facts, proposals and whatnot else to ground it better for a discussion.

In my glimpse over I've seen here the discussion of likely compromised PRNGs. Really, I did only a quick look, no thorough reading. Well, don't use those PRNGs which are suspicious or have been proven to be suspiciously pushed by certain three letter government entities.

[bitecdev]

Curves like secp256k1 - when treated as a bare elliptic curve group - are resistant to backdoors with our current mathematical understanding.
The reason is that the group itself doesn’t have any special additional structures or properties that can be easily exploited and hidden at the same time.

Note that doesn't directly imply that any cryptosystem that is based on EC principles is backdoor-free.
Many EC-based cryptosystems have been backdoored or at least deliberately weakened by leveraging hidden mathematical structures that were baked into the system from the start.