6

You can see a little background about this on this bitcointalk post by the late Hal Finney.

Beta and lambda are the values on the secp256k1 curve where:

λ^3 (mod N) = 1

β^3 (mod P) = 1

As seen here, in hex, N and P are:

N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

The actual values of lambda and beta are easily verifiable and are:

λ = 5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

β = 7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

The question for me is, how do you derive this? Can someone show me step-by-step how you can figure out these values?

Also posted to the Cryptography Stack Exchange

  • You might be more likely to get an answer on the cryptography SE site. – Tyler Feb 2 '15 at 7:03
  • Hal Finney says he found hints about how to compute it in pages 125-129 of the Guide to Elliptic Curve Cryptography, by Hankerson, Menezes and Vanstone. He found a PDF on a Russian website. – David Grayson Feb 2 '15 at 23:55
  • I've actually read that book and those particular pages multiple times and couldn't figure it out. – Jimmy Song Feb 2 '15 at 23:57
3

With a bit of reverse engineering, I think I was able to see how Hal was able to get to these results.

First, it's a pretty well known result of Fermat's little theorem that if p is a prime number and g is a generator for the field Z/pZ, then:

g ^ (p - 1) = 1

Note, don't confuse this abstract generator g with the generator for the secp256k1 group G. Now, given the above equation, it's not a big leap to see that:

(g ^ ((p - 1)/3)^3 = g ^ (p - 1) = 1

Thus, we can find λ and β by first finding generators for Z/NZ and Z/PZ (N and P being the parameters given in the original question), and then raising them to the (N-1)/3 and (P-1)/3 powers, respectively. You can check that both N-1 and P-1 are divisible by 3.

The generator that it seems Hal used for λ is 3, and for β is 2. I'm not sure why he picked those, there are plenty of other good generators to choose from. It was probably on a trial and error basis.

Using sage mathematics notebook, I was able to produce the same values for λ and β.

enter image description here

2

Quoting cryptography.stackexchange.com:

Given that N and P are prime, one obvious way to do this is to select a random value g from [1,N−1], and compute g^((N−1)/3) mod N; assuming that N≡1(mod 3), this resulting value will either be 1, the displayed value of λ, or N−λ−1 (with equal probabilities of each). If N≢1(mod 3), then the only modular cube root of 1 will be 1.

And, to compute β, you do the same with P.


The reason this works is due to Fermat's little theorem which states:

g^(N-1) ≡ 1 (mod N)

which implies

(g^((N-1)/3))^3 ≡ 1 (mod N)

which implies

g^((N-1)/3) is our potential λ. If it's not 1, it'll work for the purposes of endomorphism.

  • I'm in the middle of writing the same thing up, basically, but with some more concrete numbers. :/ – morsecoder Feb 3 '15 at 4:56
0

Python code to get beta and lambda values for p and n of secp256k1 curve

Getting beta of p

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
print "beta of p = 0x%x" % pow(2, (p-1)/3, p)

beta of p = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

Getting lambda of n

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
print "lambda of n = 0x%x" % pow(3, (n-1)/3 , n)

lambda of n = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72


More info

I experimented further with this by getting beta and lambda for both p and n and discovered that all the results generated become useful for finding the identical values for x or y in the equation y ^ 2 = x ^ 3 + 7 mod p

#beta and lambda for p
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
betaOfP = pow(2, (p-1)/3, p)
lambdaOfP = pow(3, (p-1)/3, p)
print "betaOfP \t= 0x%x " % betaOfP 
print "lambdaOfP\t= 0x%x " % lambdaOfP 
print

#beta and lambda for n
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
betaOfN = pow(2, (n-1)/3 , n)
lambdaOfN = pow(3, (n-1)/3 , n)
print "betaOfN \t= 0x%x" % betaOfN
print "lambdaOfN\t= 0x%x" % lambdaOfN

betaOfP = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee lambdaOfP = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40

betaOfN = 0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce lambdaOfN = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.