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

[1714687982]

1714687982

[1714687982]

1714687982

[1714687982]

1714687982

[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://bitcointalk.org/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://bitcointalk.org/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