¿Cómo deriva los valores lambda y beta para el endomorfismo en la curva secp256k1?

Puede ver un poco de historia sobre esto en esta publicación de bitcointalk del difunto Hal Finney.

Beta y lambda son los valores en la curva secp256k1 donde:

λ^3 (mod N) = 1

β^3 (mod P) = 1

Como se ve aquí , en hexadecimal, N y P son:

N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Los valores reales de lambda y beta son fácilmente verificables y son:

λ = 5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

β = 7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

La pregunta para mí es, ¿cómo se deriva esto? ¿Puede alguien mostrarme paso a paso cómo puede averiguar estos valores?

También publicado en Cryptography Stack Exchange

Es más probable que obtenga una respuesta en el sitio de criptografía SE.
Hal Finney dice que encontró pistas sobre cómo calcularlo en las páginas 125-129 de la Guía de criptografía de curva elíptica , de Hankerson, Menezes y Vanstone. Encontró un PDF en un sitio web ruso.
De hecho, he leído ese libro y esas páginas en particular varias veces y no pude entenderlo.

Respuestas (3)

Con un poco de ingeniería inversa, creo que pude ver cómo Hal pudo llegar a estos resultados.

Primero, es un resultado bastante conocido del pequeño teorema de Fermat que si pes un número primo y ges un generador para el campo Z/pZ, entonces:

g ^ (p - 1) = 1

Tenga en cuenta que no confunda este generador abstracto gcon el generador para el grupo secp256k1 G. Ahora, dada la ecuación anterior, no es un gran salto ver que:

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

Por lo tanto, podemos encontrar λy encontrando βprimero generadores para Z/NZy Z/PZ( siendo Ny Plos parámetros dados en la pregunta original), y luego elevándolos a las potencias (N-1)/3y , respectivamente. (P-1)/3Puedes comprobar que ambos N-1y P-1son divisibles por 3.

El generador para el que parece que Hal usó λes 3, y para βes 2. No estoy seguro de por qué los eligió, hay muchos otros buenos generadores para elegir. Probablemente fue a base de prueba y error.

Usando el cuaderno de matemáticas Sage, pude producir los mismos valores para λy β.

ingrese la descripción de la imagen aquí

lambda y beta son raíces cúbicas no triviales de 1 en los campos respectivos (mod n para lambda, mod p para beta). Sólo hay dos de esos valores. Partiendo de un generador g y elevando a la potencia (n-1)/3 resp. (p-1)/3 encontrarlos es solo una forma de hacerlo. Y no importa con qué g se empiece, siempre se encuentra una de las dos soluciones válidas, o 1 (si la g de partida no fuera un generador, sino un cubo).

Citando cryptography.stackexchange.com :

Dado que N y P son primos, una forma obvia de hacerlo es seleccionar un valor aleatorio g de [1,N−1] y calcular g^((N−1)/3) mod N; suponiendo que N≡1(mod 3), este valor resultante será 1, el valor mostrado de λ, o N−λ−1 (con las mismas probabilidades de cada uno). Si N≢1(mod 3), entonces la única raíz cúbica modular de 1 será 1.

Y, para calcular β, haces lo mismo con P.

La razón por la que esto funciona se debe al pequeño teorema de Fermat que establece:

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

lo que implica

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

lo que implica

g^((N-1)/3) es nuestro potencial λ. Si no es 1, funcionará a los efectos del endomorfismo.

Estoy escribiendo lo mismo, básicamente, pero con algunos números más concretos. :/

Código de Python para obtener valores beta y lambda para p y n de la curva secp256k1

Obteniendo beta de p

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

beta de p = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

Obtener lambda de n

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

lambda de n = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

Más información

Experimenté más con esto obteniendo beta y lambda tanto para p como para n y descubrí que todos los resultados generados se vuelven útiles para encontrar valores idénticos para x o y en la ecuación 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

betaOfN = 0xac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce lambdaOfN = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967d72b

¿Cómo deriva los valores lambda y beta para el endomorfismo en la curva secp256k1?
RespuestasAquíPolítica de privacidad1y, 1v