2
$\begingroup$

Note: This question was reposted from Bitcoin Stack Exchange, where it received alike answers.


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 such that: $$\begin{align} \lambda^3 &= 1 \mod N \\ \beta^3 &= 1 \mod P \\ \end{align}$$

As seen here, in hex, $N$ and $P$ are: $$\begin{align} N &= \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFE\ BAAEDCE6\ AF48A03B\ BFD25E8C\ D0364141} \\ P &= \mathtt{FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFF\ FFFFFFFE\ FFFFFC2F} \\ \end{align}$$

The actual values of lambda and beta are easily verifiable and are: $$\begin{align} \lambda &= \mathtt{5363ad4c\ c05c30e0\ a5261c02\ 8812645a\ 122e22ea\ 20816678\ df02967c\ 1b23bd72} \\ \beta &= \mathtt{7ae96a2b\ 657c0710\ 6e64479e\ ac3434e9\ 9cf04975\ 12f58995\ c1396c28\ 719501ee} \\ \end{align}$$

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

$\endgroup$
  • $\begingroup$ protected to prevent superfluous copy-and-paste answers from being posted back-and-forth between Crypto.SE and Bitcoin.SE $\endgroup$ – e-sushi Oct 29 '15 at 16:36
4
$\begingroup$

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} \bmod N$; assuming that $N \equiv 1 \pmod{3}$, this resulting value will either be 1, the displayed value of $\lambda$, or $N-\lambda-1$ (with equal probabilities of each). If $N \not\equiv 1 \pmod{3}$, then the only modular cube root of 1 will be 1.

And, to compute $\beta$, you do the same with $P$.

$\endgroup$
  • $\begingroup$ Thank you so much! I've confirmed this works for both $\lambda$ and $\beta$. What number theory theorem is used to come up with this? $\endgroup$ – Jimmy Song Feb 3 '15 at 4:53
  • $\begingroup$ Actually, nevermind, it's clear you're using Fermat's little theorem. $\endgroup$ – Jimmy Song Feb 3 '15 at 5:00
1
$\begingroup$

Steps for calculating beta of P

  • Get ⅓ of P-1
  • Calculate 2^[⅓ of P-1] mod P

Example Python Code

#method for calculating beta of p
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
print hex(p)
#get ⅓ of p-1
thirdOfPm1 = (p-1)/3
print hex(thirdOfPm1 )
#calculate 2^thirdOfPm1 mod p
beta = pow(2, thirdOfPm1, p)
print hex(beta)

0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2fL 0x55555555555555555555555555555555555555555555555555555554fffffebaL 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501eeL


Steps for calculating lambda of N

  • Get ⅓ of N-1
  • Calculate 3^[⅓ of N-1] mod N

Example Python Code

#method for calculating lambda of n
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
print hex(n)
#get ⅓ of n-1
thirdOfNm1 = (n-1)/3
print hex(thirdOfNm1)
#calculate 3^thirdOfNm1 mod n
lmbda = pow(3, thirdOfNm1, n)
print hex(lmbda)

0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141L 0x55555555555555555555555555555554e8e4f44ce51835693ff0ca2ef01215c0L 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72L


more info

The above method demonstrates getting beta and lambda for the parameters used in secp256k1. I applied the same method for the parameters used in curve secp192k1 and also got these results.

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37
beta = 0x447a96e6c647963e2f7809feaab46947f34b0aa3ca0bba74L

n = 0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D
lambda = 0x3d84f26c12238d7b4f3d516613c1759033b1a5800175d0b1L

$\endgroup$

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