derive_hash_to_curve.sage
1 #!/usr/bin/sage 2 # vim: syntax=python 3 # vim: set ts=2 sw=2 et: 4 5 # Constantine 6 # Copyright (c) 2018-2019 Status Research & Development GmbH 7 # Copyright (c) 2020-Present Mamy André-Ratsimbazafy 8 # Licensed and distributed under either of 9 # * MIT license (license terms in the root directory or at http://opensource.org/licenses/MIT). 10 # * Apache v2 license (license terms in the root directory or at http://www.apache.org/licenses/LICENSE-2.0). 11 # at your option. This file may not be copied, modified, or distributed except according to those terms. 12 13 # ############################################################ 14 # 15 # Frobenius constants 16 # 17 # ############################################################ 18 19 # Imports 20 # --------------------------------------------------------- 21 22 import os 23 import inspect, textwrap 24 import sage.schemes.elliptic_curves.isogeny_small_degree as isd 25 26 # Working directory 27 # --------------------------------------------------------- 28 29 os.chdir(os.path.dirname(__file__)) 30 31 # Sage imports 32 # --------------------------------------------------------- 33 # Accelerate arithmetic by accepting probabilistic proofs 34 from sage.structure.proof.all import arithmetic 35 arithmetic(False) 36 37 load('curves.sage') 38 39 # Utilities 40 # --------------------------------------------------------- 41 42 def fp2_to_hex(a): 43 v = vector(a) 44 return '0x' + Integer(v[0]).hex() + ' + β * ' + '0x' + Integer(v[1]).hex() 45 46 def field_to_nim(value, field, curve, prefix = "", comment_above = "", comment_right = ""): 47 result = '# ' + comment_above + '\n' if comment_above else '' 48 comment_right = ' # ' + comment_right if comment_right else '' 49 50 if field == 'Fp2': 51 v = vector(value) 52 53 result += inspect.cleandoc(f""" 54 {prefix}Fp2[{curve}].fromHex( {comment_right} 55 "0x{Integer(v[0]).hex()}", 56 "0x{Integer(v[1]).hex()}" 57 )""") 58 elif field == 'Fp': 59 result += inspect.cleandoc(f""" 60 {prefix}Fp[{curve}].fromHex( {comment_right} 61 "0x{Integer(value).hex()}") 62 """) 63 else: 64 raise NotImplementedError() 65 66 return result 67 68 def dump_poly(name, poly, field, curve): 69 result = f'const {name}* = [\n' 70 result += ' # Polynomial k₀ + k₁ x + k₂ x² + k₃ x³ + ... + kₙ xⁿ\n' 71 result += ' # The polynomial is stored as an array of coefficients ordered from k₀ to kₙ\n' 72 result += '\n' 73 74 poly = list(poly) 75 lastRow = len(poly) - 1 76 77 for rowID, val in enumerate(reversed(poly)): 78 (coef, power) = val 79 result += textwrap.indent( 80 field_to_nim( 81 coef, field, curve, 82 comment_above = str(power) 83 ), 84 ' ') 85 result += ',\n' if rowID != lastRow else '\n' 86 87 result += ']' 88 return result 89 90 ZZR = PolynomialRing(ZZ, name='XX') 91 def sgn0(x): 92 """ 93 Returns 1 if x is 'negative' (little-endian sense), else 0. 94 """ 95 degree = x.parent().degree() 96 if degree == 1: 97 # not a field extension 98 xi_values = (ZZ(x),) 99 else: 100 # field extension 101 xi_values = ZZR(x) # extract vector repr of field element (faster than x._vector_()) 102 sign = 0 103 zero = 1 104 # compute the sign in constant time 105 for i in range(0, degree): 106 zz_xi = xi_values[i] 107 # sign of this digit 108 sign_i = zz_xi % 2 109 zero_i = zz_xi == 0 110 # update sign and zero 111 sign = sign | (zero & sign_i) 112 zero = zero & zero_i 113 return sign 114 115 # Generic Shallue-van de Woestijne map 116 # --------------------------------------------------------- 117 118 def find_z_svdw(F, A, B): 119 """ 120 https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-14#appendix-H.1 121 Arguments: 122 - F, a field object, e.g., F = GF(2^521 - 1) 123 - A and B, the coefficients of the curve y^2 = x^3 + A * x + B 124 """ 125 g = lambda x: F(x)^3 + F(A) * F(x) + F(B) 126 h = lambda Z: -(F(3) * Z^2 + F(4) * A) / (F(4) * g(Z)) 127 ctr = F.gen() 128 while True: 129 for Z_cand in (F(ctr), F(-ctr)): 130 if g(Z_cand) == F(0): 131 # Criterion 1: g(Z) != 0 in F. 132 continue 133 if h(Z_cand) == F(0): 134 # Criterion 2: -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0 in F. 135 continue 136 if not h(Z_cand).is_square(): 137 # Criterion 3: -(3 * Z^2 + 4 * A) / (4 * g(Z)) is square in F. 138 continue 139 if g(Z_cand).is_square() or g(-Z_cand / F(2)).is_square(): 140 # Criterion 4: At least one of g(Z) and g(-Z / 2) is square in F. 141 return Z_cand 142 ctr += 1 143 144 145 # Isogenies for Simplified Shallue-van de Woestijne-Ulas map 146 # --------------------------------------------------------- 147 148 def find_iso(E): 149 """ 150 Find an isogenous curve with j-invariant not in {0, 1728} so that 151 Simplified Shallue-van de Woestijne method is directly applicable 152 (i.e the Elliptic Curve coefficient y² = x³ + A*x + B have AB != 0) 153 """ 154 for p_test in primes(30): 155 isos = [i for i in isd.isogenies_prime_degree(E, p_test) 156 if i.codomain().j_invariant() not in (0, 1728) ] 157 if len(isos) > 0: 158 print(f'✔️✔️✔️ Found {len(isos)} isogenous curves of degree {p_test}') 159 return isos[0].dual() 160 print(f'⚠️⚠️⚠️ Found no isogenies for {E}') 161 return None 162 163 def find_z_sswu(F, A, B): 164 """ 165 https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-14#appendix-H.2 166 Arguments: 167 - F, a field object, e.g., F = GF(2^521 - 1) 168 - A and B, the coefficients of the curve equation y² = x³ + A * x + B 169 """ 170 R.<xx> = F[] # Polynomial ring over F 171 g = xx^3 + F(A) * xx + F(B) # y² = g(x) = x³ + A * x + B 172 ctr = F.gen() 173 while True: 174 for Z_cand in (F(ctr), F(-ctr)): 175 if Z_cand.is_square(): 176 # Criterion 1: Z is non-square in F. 177 continue 178 if Z_cand == F(-1): 179 # Criterion 2: Z != -1 in F. 180 continue 181 if not (g - Z_cand).is_irreducible(): 182 # Criterion 3: g(x) - Z is irreducible over F. 183 continue 184 if g(B / (Z_cand * A)).is_square(): 185 # Criterion 4: g(B / (Z * A)) is square in F. 186 return Z_cand 187 ctr += 1 188 189 def search_isogeny(curve_name, curve_config): 190 p = curve_config[curve_name]['field']['modulus'] 191 Fp = GF(p) 192 193 # Base constants - E1 194 A = curve_config[curve_name]['curve']['a'] 195 B = curve_config[curve_name]['curve']['b'] 196 E1 = EllipticCurve(Fp, [A, B]) 197 198 # Base constants - E2 199 embedding_degree = curve_config[curve_name]['tower']['embedding_degree'] 200 twist_degree = curve_config[curve_name]['tower']['twist_degree'] 201 twist = curve_config[curve_name]['tower']['twist'] 202 203 G2_field_degree = embedding_degree // twist_degree 204 G2_field = f'Fp{G2_field_degree}' if G2_field_degree > 1 else 'Fp' 205 206 if G2_field_degree == 2: 207 non_residue_fp = curve_config[curve_name]['tower']['QNR_Fp'] 208 elif G2_field_degree == 1: 209 if twist_degree == 6: 210 # Only for complete serialization 211 non_residue_fp = curve_config[curve_name]['tower']['SNR_Fp'] 212 else: 213 raise NotImplementedError() 214 else: 215 raise NotImplementedError() 216 217 Fp = GF(p) 218 K.<u> = PolynomialRing(Fp) 219 220 if G2_field == 'Fp2': 221 Fp2.<beta> = Fp.extension(u^2 - non_residue_fp) 222 G2F = Fp2 223 if twist_degree == 6: 224 non_residue_twist = curve_config[curve_name]['tower']['SNR_Fp2'] 225 else: 226 raise NotImplementedError() 227 elif G2_field == 'Fp': 228 G2F = Fp 229 if twist_degree == 6: 230 non_residue_twist = curve_config[curve_name]['tower']['SNR_Fp'] 231 else: 232 raise NotImplementedError() 233 else: 234 raise NotImplementedError() 235 236 if twist == 'D_Twist': 237 G2B = B/G2F(non_residue_twist) 238 E2 = EllipticCurve(G2F, [0, G2B]) 239 elif twist == 'M_Twist': 240 G2B = B*G2F(non_residue_twist) 241 E2 = EllipticCurve(G2F, [0, G2B]) 242 else: 243 raise ValueError('E2 must be a D_Twist or M_Twist but found ' + twist) 244 245 # Isogenies: 246 iso_G1 = find_iso(E1) 247 iso_G2 = find_iso(E2) 248 249 if iso_G1 == None or iso_G2 == None: 250 # TODO: case when G1 has a cheap isogeny but G2 does not 251 Z_G1 = find_z_svdw(Fp, A, B) 252 print(f"Z G1 (svdw): {Z_G1}") 253 Z_G2 = find_z_svdw(Fp2, A, G2B) 254 print(f"Z G2 (svdw): {fp2_to_hex(Z_G2)}") 255 return 256 257 a_G1 = iso_G1.domain().a4() 258 b_G1 = iso_G1.domain().a6() 259 260 a_G2 = iso_G2.domain().a4() 261 b_G2 = iso_G2.domain().a6() 262 263 # Z 264 Z_G1 = find_z_sswu(Fp, a_G1, b_G1) 265 Z_G2 = find_z_sswu(Fp2, a_G2, b_G2) 266 267 print(f"{curve_name} G1 - isogeny of degree {iso_G1.degree()} with eq y² = x³ + A'x + B':") 268 print(f" A': 0x{Integer(a_G1).hex()}") 269 print(f" B': 0x{Integer(b_G1).hex()}") 270 print(f" Z (sswu): {Z_G1}") 271 272 print(f"{curve_name} G2 - isogeny of degree {iso_G2.degree()} with eq y² = x³ + A'x + B':") 273 print(f" A': {fp2_to_hex(a_G2)}") 274 print(f" B': {fp2_to_hex(b_G2)}") 275 print(f" Z (sswu): {fp2_to_hex(Z_G2)}") 276 277 # BLS12-381 G1 278 # --------------------------------------------------------- 279 # Hardcoding from spec: 280 # - https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-8.8.1 281 # - https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/blob/f7dd3761/poc/sswu_opt_3mod4.sage#L126-L132 282 283 def genBLS12381G1_H2C_constants(curve_config): 284 curve_name = 'BLS12_381' 285 286 # ------------------------------------------ 287 p = curve_config[curve_name]['field']['modulus'] 288 Fp = GF(p) 289 # ------------------------------------------ 290 291 # Hash to curve isogenous curve parameters 292 # y² = x³ + A'*x + B' 293 294 print('\n----> Hash-to-Curve map to isogenous BLS12-381 E\'1 <----\n') 295 buf = inspect.cleandoc(f""" 296 # Hash-to-Curve map to isogenous BLS12-381 E'1 constants 297 # ----------------------------------------------------------------- 298 # 299 # y² = x³ + A'*x + B' with p ≡ 3 (mod 4) the BLS12-381 characteristic (base modulus) 300 # 301 # Hardcoding from spec: 302 # - https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-8.8.1 303 # - https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/blob/f7dd3761/poc/sswu_opt_3mod4.sage#L126-L132 304 """) 305 buf += '\n\n' 306 307 # Base constants 308 Aprime_E1 = Fp('0x144698a3b8e9433d693a02c96d4982b0ea985383ee66a8d8e8981aefd881ac98936f8da0e0f97f5cf428082d584c1d') 309 Bprime_E1 = Fp('0x12e2908d11688030018b12e8753eee3b2016c1f0f24f4070a0b9c14fcef35ef55a23215a316ceaa5d1cc48e98e172be0') 310 Z = Fp(11) 311 # Extra 312 minus_A = -Aprime_E1 313 ZmulA = Z * Aprime_E1 314 sqrt_minus_Z3 = sqrt(-Z^3) 315 316 buf += f'const {curve_name}_h2c_G1_Aprime_E1* = ' 317 buf += field_to_nim(Aprime_E1, 'Fp', curve_name) 318 buf += '\n' 319 320 buf += f'const {curve_name}_h2c_G1_Bprime_E1* = ' 321 buf += field_to_nim(Bprime_E1, 'Fp', curve_name) 322 buf += '\n' 323 324 buf += f'const {curve_name}_h2c_G1_Z* = ' 325 buf += field_to_nim(Z, 'Fp', curve_name) 326 buf += '\n' 327 328 buf += f'const {curve_name}_h2c_G1_minus_A* = ' 329 buf += field_to_nim(minus_A, 'Fp', curve_name) 330 buf += '\n' 331 332 buf += f'const {curve_name}_h2c_G1_ZmulA* = ' 333 buf += field_to_nim(ZmulA, 'Fp', curve_name) 334 buf += '\n' 335 336 buf += f'const {curve_name}_h2c_G1_sqrt_minus_Z3* = ' 337 buf += field_to_nim(sqrt_minus_Z3, 'Fp', curve_name) 338 buf += '\n' 339 340 return buf 341 342 def genBLS12381G1_H2C_isogeny_map(curve_config): 343 curve_name = 'BLS12_381' 344 345 # Hash to curve isogenous curve parameters 346 # y² = x³ + A'*x + B' 347 348 print('\n----> Hash-to-Curve 3-isogeny map BLS12-381 E\'1 constants <----\n') 349 buf = inspect.cleandoc(f""" 350 # Hash-to-Curve 11-isogeny map BLS12-381 E'1 constants 351 # ----------------------------------------------------------------- 352 # 353 # The polynomials map a point (x', y') on the isogenous curve E'1 354 # to (x, y) on E1, represented as (xnum/xden, y' * ynum/yden) 355 356 """) 357 buf += '\n\n' 358 359 p = curve_config[curve_name]['field']['modulus'] 360 Fp = GF(p) 361 362 # Base constants - E1 363 A = curve_config[curve_name]['curve']['a'] 364 B = curve_config[curve_name]['curve']['b'] 365 E1 = EllipticCurve(Fp, [A, B]) 366 367 # Base constants - Isogenous curve E'1, degree 11 368 Aprime_E1 = Fp('0x144698a3b8e9433d693a02c96d4982b0ea985383ee66a8d8e8981aefd881ac98936f8da0e0f97f5cf428082d584c1d') 369 Bprime_E1 = Fp('0x12e2908d11688030018b12e8753eee3b2016c1f0f24f4070a0b9c14fcef35ef55a23215a316ceaa5d1cc48e98e172be0') 370 Eprime1 = EllipticCurve(Fp, [Aprime_E1, Bprime_E1]) 371 372 iso = EllipticCurveIsogeny(E=E1, kernel=None, codomain=Eprime1, degree=11).dual() 373 if (- iso.rational_maps()[1])(1, 1) > iso.rational_maps()[1](1, 1): 374 iso.switch_sign() 375 376 (xm, ym) = iso.rational_maps() 377 maps = (xm.numerator(), xm.denominator(), ym.numerator(), ym.denominator()) 378 379 buf += dump_poly( 380 'BLS12_381_h2c_G1_11_isogeny_map_xnum', 381 xm.numerator(), 'Fp', curve_name) 382 buf += '\n' 383 buf += dump_poly( 384 'BLS12_381_h2c_G1_11_isogeny_map_xden', 385 xm.denominator(), 'Fp', curve_name) 386 buf += '\n' 387 buf += dump_poly( 388 'BLS12_381_h2c_G1_11_isogeny_map_ynum', 389 ym.numerator(), 'Fp', curve_name) 390 buf += '\n' 391 buf += dump_poly( 392 'BLS12_381_h2c_G1_11_isogeny_map_yden', 393 ym.denominator(), 'Fp', curve_name) 394 395 return buf 396 397 # BLS12-381 G2 398 # --------------------------------------------------------- 399 # Hardcoding from spec: 400 # - https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-8.8.2 401 # - https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/blob/f7dd3761/poc/sswu_opt_9mod16.sage#L142-L148 402 403 def genBLS12381G2_H2C_constants(curve_config): 404 curve_name = 'BLS12_381' 405 406 # ------------------------------------------ 407 embdeg = curve_config[curve_name]['tower']['embedding_degree'] 408 twdeg = curve_config[curve_name]['tower']['twist_degree'] 409 g2field = f'Fp{embdeg//twdeg}' if (embdeg//twdeg) > 1 else 'Fp' 410 411 p = curve_config[curve_name]['field']['modulus'] 412 Fp = GF(p) 413 K.<u> = PolynomialRing(Fp) 414 if g2field == 'Fp2': 415 QNR_Fp = curve_config[curve_name]['tower']['QNR_Fp'] 416 Fp2.<beta> = Fp.extension(u^2 - QNR_Fp) 417 else: 418 SNR_Fp = curve_config[curve_name]['tower']['SNR_Fp'] 419 Fp2.<beta> = Fp.extension(u^2 - SNR_Fp) 420 # ------------------------------------------ 421 422 # Hash to curve isogenous curve parameters 423 # y² = x³ + A'*x + B' 424 425 print('\n----> Hash-to-Curve map to isogenous BLS12-381 E\'2 <----\n') 426 buf = inspect.cleandoc(f""" 427 # Hash-to-Curve map to isogenous BLS12-381 E'2 constants 428 # ----------------------------------------------------------------- 429 # 430 # y² = x³ + A'*x + B' with p² = q ≡ 9 (mod 16), p the BLS12-381 characteristic (base modulus) 431 # 432 # Hardcoding from spec: 433 # - https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#section-8.8.2 434 # - https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/blob/f7dd3761/poc/sswu_opt_9mod16.sage#L142-L148 435 """) 436 buf += '\n\n' 437 438 # Base constants 439 Aprime_E2 = Fp2([0, 240]) 440 Bprime_E2 = Fp2([1012, 1012]) 441 Z = Fp2([-2, -1]) 442 # Extra 443 minus_A = -Aprime_E2 444 ZmulA = Z * Aprime_E2 445 inv_Z3 = (Z^3)^-1 # modular inverse of Z³ 446 (a, b) = vector(inv_Z3) 447 squared_norm_inv_Z3 = a^2 + b^2 # ||1/Z³||² 448 # x^((p-3)/4)) ≡ 1/√x (mod p) if p ≡ 3 (mod 4) 449 inv_norm_inv_Z3 = squared_norm_inv_Z3^((p-3)/4) # 1/||1/Z³|| 450 451 buf += f'const {curve_name}_h2c_G2_Aprime_E2* = ' 452 buf += field_to_nim(Aprime_E2, 'Fp2', curve_name, comment_right = "240𝑖") 453 buf += '\n' 454 455 buf += f'const {curve_name}_h2c_G2_Bprime_E2* = ' 456 buf += field_to_nim(Bprime_E2, 'Fp2', curve_name, comment_right = "1012 * (1 + 𝑖)") 457 buf += '\n' 458 459 buf += f'const {curve_name}_h2c_G2_Z* = ' 460 buf += field_to_nim(Z, 'Fp2', curve_name, comment_right = "-(2 + 𝑖)") 461 buf += '\n' 462 463 buf += f'const {curve_name}_h2c_G2_minus_A* = ' 464 buf += field_to_nim(minus_A, 'Fp2', curve_name, comment_right = "-240𝑖") 465 buf += '\n' 466 467 buf += f'const {curve_name}_h2c_G2_ZmulA* = ' 468 buf += field_to_nim(ZmulA, 'Fp2', curve_name, comment_right = "Z*A = 240-480𝑖") 469 buf += '\n' 470 471 buf += f'const {curve_name}_h2c_G2_inv_Z3* = ' 472 buf += field_to_nim(inv_Z3, 'Fp2', curve_name, comment_right = "1/Z³") 473 buf += '\n' 474 475 buf += f'const {curve_name}_h2c_G2_squared_norm_inv_Z3* = ' 476 buf += field_to_nim(squared_norm_inv_Z3, 'Fp', curve_name, comment_right = "||1/Z³||²") 477 buf += '\n' 478 479 buf += f'const {curve_name}_h2c_G2_inv_norm_inv_Z3* = ' 480 buf += field_to_nim(inv_norm_inv_Z3, 'Fp', curve_name, comment_right = "1/||1/Z³||") 481 buf += '\n' 482 483 return buf 484 485 def genBLS12381G2_H2C_isogeny_map(curve_config): 486 curve_name = 'BLS12_381' 487 488 # ------------------------------------------ 489 p = curve_config[curve_name]['field']['modulus'] 490 # This extension field construction 491 # does not work with isogenies :/ 492 # 493 # embdeg = curve_config[curve_name]['tower']['embedding_degree'] 494 # twdeg = curve_config[curve_name]['tower']['twist_degree'] 495 # g2field = f'Fp{embdeg//twdeg}' if (embdeg//twdeg) > 1 else 'Fp' 496 # 497 # Fp = GF(p) 498 # K.<u> = PolynomialRing(Fp) 499 # if g2field == 'Fp2': 500 # QNR_Fp = curve_config[curve_name]['tower']['QNR_Fp'] 501 # Fp2.<beta> = Fp.extension(u^2 - QNR_Fp) 502 # else: 503 # SNR_Fp = curve_config[curve_name]['tower']['SNR_Fp'] 504 # Fp2.<beta> = Fp.extension(u^2 - SNR_Fp) 505 # ------------------------------------------ 506 507 QNR_Fp = curve_config[curve_name]['tower']['QNR_Fp'] 508 Fp2.<beta> = GF(p^2, modulus=(x^2-QNR_Fp)) 509 510 # Hash to curve isogenous curve parameters 511 # y² = x³ + A'*x + B' 512 513 print('\n----> Hash-to-Curve 3-isogeny map BLS12-381 E\'2 constants <----\n') 514 buf = inspect.cleandoc(f""" 515 # Hash-to-Curve 3-isogeny map BLS12-381 E'2 constants 516 # ----------------------------------------------------------------- 517 # 518 # The polynomials map a point (x', y') on the isogenous curve E'2 519 # to (x, y) on E2, represented as (xnum/xden, y' * ynum/yden) 520 521 """) 522 buf += '\n\n' 523 524 # Base constants - E2 525 A = curve_config[curve_name]['curve']['a'] 526 B = curve_config[curve_name]['curve']['b'] 527 twist = curve_config[curve_name]['tower']['twist'] 528 SNR_Fp2 = curve_config[curve_name]['tower']['SNR_Fp2'] 529 530 if twist == 'M_twist': 531 Btwist = B * Fp2(SNR_Fp2) 532 else: 533 Btwist = B / Fp2(SNR_Fp2) 534 535 E2 = EllipticCurve(Fp2, [A, Btwist]) 536 537 # Base constants - Isogenous curve E'2, degree 3 538 Aprime_E2 = Fp2([0, 240]) 539 Bprime_E2 = Fp2([1012, 1012]) 540 Eprime2 = EllipticCurve(Fp2, [Aprime_E2, Bprime_E2]) 541 542 iso_kernel = [6 * (1 - beta), 1] 543 iso = EllipticCurveIsogeny(E=Eprime2, kernel=iso_kernel, codomain=E2, degree=3) 544 if (- iso.rational_maps()[1])(1, 1) > iso.rational_maps()[1](1, 1): 545 iso.switch_sign() 546 547 (xm, ym) = iso.rational_maps() 548 maps = (xm.numerator(), xm.denominator(), ym.numerator(), ym.denominator()) 549 550 buf += dump_poly( 551 'BLS12_381_h2c_G2_3_isogeny_map_xnum', 552 xm.numerator(), 'Fp2', curve_name) 553 buf += '\n' 554 buf += dump_poly( 555 'BLS12_381_h2c_G2_3_isogeny_map_xden', 556 xm.denominator(), 'Fp2', curve_name) 557 buf += '\n' 558 buf += dump_poly( 559 'BLS12_381_h2c_G2_3_isogeny_map_ynum', 560 ym.numerator(), 'Fp2', curve_name) 561 buf += '\n' 562 buf += dump_poly( 563 'BLS12_381_h2c_G2_3_isogeny_map_yden', 564 ym.denominator(), 'Fp2', curve_name) 565 566 return buf 567 568 def genSVDW_H2C_G1_constants(curve, curve_config, Z): 569 p = curve_config[curve]['field']['modulus'] 570 a = curve_config[curve]['curve']['a'] 571 b = curve_config[curve]['curve']['b'] 572 573 Fp = GF(p) 574 575 print(f'\n----> Hash-to-Curve Shallue-van de Woestijne {curve} G1 map <----\n') 576 buf = inspect.cleandoc(f""" 577 # Hash-to-Curve Shallue-van de Woestijne {curve} G1 map 578 # ----------------------------------------------------------------- 579 # Spec: 580 # - https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-14#appendix-F.1 581 """) 582 buf += '\n\n' 583 584 c1 = Z^3 + a*Z + b 585 c2 = -Z/2 586 t = 3 * Z^2 + 4 * a 587 c3 = sqrt(-c1 * t) 588 if sgn0(c3) == 1: 589 c3 = -c3 590 c4 = -4 * c1 / t 591 592 buf += f'const {curve}_h2c_svdw_G1_Z* = ' 593 buf += field_to_nim(Z, 'Fp', curve) 594 buf += '\n' 595 596 buf += f'const {curve}_h2c_svdw_G1_curve_eq_rhs_Z* = ' 597 buf += field_to_nim(c1, 'Fp', curve) 598 buf += '\n' 599 600 buf += f'const {curve}_h2c_svdw_G1_minus_Z_div_2* = ' 601 buf += field_to_nim(c2, 'Fp', curve) 602 buf += '\n' 603 604 buf += f'const {curve}_h2c_svdw_G1_z3* = ' 605 buf += field_to_nim(c3, 'Fp', curve) 606 buf += '\n' 607 608 buf += f'const {curve}_h2c_svdw_G1_z4* = ' 609 buf += field_to_nim(c4, 'Fp', curve) 610 buf += '\n' 611 612 return buf 613 614 def genSVDW_H2C_G2_constants(curve, curve_config, Z): 615 p = curve_config[curve]['field']['modulus'] 616 a = curve_config[curve]['curve']['a'] 617 b = curve_config[curve]['curve']['b'] 618 619 embedding_degree = curve_config[curve]['tower']['embedding_degree'] 620 twist_degree = curve_config[curve]['tower']['twist_degree'] 621 twist = curve_config[curve]['tower']['twist'] 622 623 G2_field_degree = embedding_degree // twist_degree 624 G2_field = f'Fp{G2_field_degree}' if G2_field_degree > 1 else 'Fp' 625 626 if G2_field_degree == 2: 627 non_residue_fp = curve_config[curve]['tower']['QNR_Fp'] 628 elif G2_field_degree == 1: 629 if twist_degree == 6: 630 # Only for complete serialization 631 non_residue_fp = curve_config[curve]['tower']['SNR_Fp'] 632 else: 633 raise NotImplementedError() 634 else: 635 raise NotImplementedError() 636 637 Fp = GF(p) 638 K.<u> = PolynomialRing(Fp) 639 640 if G2_field == 'Fp2': 641 Fp2.<beta> = Fp.extension(u^2 - non_residue_fp) 642 G2F = Fp2 643 if twist_degree == 6: 644 non_residue_twist = curve_config[curve]['tower']['SNR_Fp2'] 645 else: 646 raise NotImplementedError() 647 elif G2_field == 'Fp': 648 G2F = Fp 649 if twist_degree == 6: 650 non_residue_twist = curve_config[curve]['tower']['SNR_Fp'] 651 else: 652 raise NotImplementedError() 653 else: 654 raise NotImplementedError() 655 656 if twist == 'D_Twist': 657 G2B = b/G2F(non_residue_twist) 658 elif twist == 'M_Twist': 659 G2B = b*G2F(non_residue_twist) 660 else: 661 raise ValueError('E2 must be a D_Twist or M_Twist but found ' + twist) 662 663 print(f'\n----> Hash-to-Curve Shallue-van de Woestijne {curve} G2 map <----\n') 664 buf = inspect.cleandoc(f""" 665 # Hash-to-Curve Shallue-van de Woestijne {curve} G2 map 666 # ----------------------------------------------------------------- 667 # Spec: 668 # - https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-14#appendix-F.1 669 """) 670 buf += '\n\n' 671 672 c1 = Z^3 + a*Z + G2B 673 c2 = -Z/2 674 t = 3 * Z^2 + 4 * a 675 c3 = sqrt(-c1 * t) 676 if sgn0(c3) == 1: 677 c3 = -c3 678 c4 = -4 * c1 / t 679 680 buf += f'const {curve}_h2c_svdw_G2_Z* = ' 681 buf += field_to_nim(Z, G2_field, curve) 682 buf += '\n' 683 684 buf += f'const {curve}_h2c_svdw_G2_curve_eq_rhs_Z* = ' 685 buf += field_to_nim(c1, G2_field, curve) 686 buf += '\n' 687 688 buf += f'const {curve}_h2c_svdw_G2_minus_Z_div_2* = ' 689 buf += field_to_nim(c2, G2_field, curve) 690 buf += '\n' 691 692 buf += f'const {curve}_h2c_svdw_G2_z3* = ' 693 buf += field_to_nim(c3, G2_field, curve) 694 buf += '\n' 695 696 buf += f'const {curve}_h2c_svdw_G2_z4* = ' 697 buf += field_to_nim(c4, G2_field, curve) 698 buf += '\n' 699 700 return buf 701 702 # CLI 703 # --------------------------------------------------------- 704 705 if __name__ == "__main__": 706 # Usage 707 # BLS12-381 708 # sage sage/derive_hash_to_curve.sage BLS12_381 G2 709 # for Hash-to-Curve 710 # or 711 # sage sage/derive_hash_to_curve.sage BLS12_381 iso 712 # to search for a suitable isogeny 713 714 from argparse import ArgumentParser 715 716 parser = ArgumentParser() 717 parser.add_argument("curve",nargs="+") 718 args = parser.parse_args() 719 720 curve = args.curve[0] 721 group_or_iso = args.curve[1] 722 723 if group_or_iso == 'iso': 724 search_isogeny(curve, Curves) 725 726 elif curve == 'BLS12_381' and group_or_iso == 'G1': 727 h2c = genBLS12381G1_H2C_constants(Curves) 728 h2c += '\n\n' 729 h2c += genBLS12381G1_H2C_isogeny_map(Curves) 730 731 with open(f'{curve.lower()}_hash_to_curve_g1.nim', 'w') as f: 732 f.write(copyright()) 733 f.write('\n\n') 734 735 f.write(inspect.cleandoc(""" 736 import 737 ../config/curves, 738 ../io/io_fields 739 """)) 740 741 f.write('\n\n') 742 f.write(h2c) 743 744 print(f'Successfully created {curve.lower()}_hash_to_curve_g1.nim') 745 746 elif curve == 'BLS12_381' and group_or_iso == 'G2': 747 h2c = genBLS12381G2_H2C_constants(Curves) 748 h2c += '\n\n' 749 h2c += genBLS12381G2_H2C_isogeny_map(Curves) 750 751 with open(f'{curve.lower()}_hash_to_curve_g2.nim', 'w') as f: 752 f.write(copyright()) 753 f.write('\n\n') 754 755 f.write(inspect.cleandoc(""" 756 import 757 ../config/curves, 758 ../io/[io_fields, io_extfields] 759 """)) 760 761 f.write('\n\n') 762 f.write(h2c) 763 764 print(f'Successfully created {curve.lower()}_hash_to_curve_g2.nim') 765 766 elif curve == 'BN254_Snarks' and group_or_iso == 'G1': 767 p = Curves['BN254_Snarks']['field']['modulus'] 768 769 Z = GF(p)(1) 770 h2c = genSVDW_H2C_G1_constants('BN254_Snarks', Curves, Z) 771 772 with open(f'{curve.lower()}_hash_to_curve_g1.nim', 'w') as f: 773 f.write(copyright()) 774 f.write('\n\n') 775 776 f.write(inspect.cleandoc(""" 777 import 778 ../config/curves, 779 ../io/io_fields 780 """)) 781 782 f.write('\n\n') 783 f.write(h2c) 784 785 print(f'Successfully created {curve.lower()}_hash_to_curve_g1.nim') 786 787 elif curve == 'BN254_Snarks' and group_or_iso == 'G2': 788 p = Curves['BN254_Snarks']['field']['modulus'] 789 non_residue_fp = Curves['BN254_Snarks']['tower']['QNR_Fp'] 790 Fp = GF(p) 791 K.<u> = PolynomialRing(Fp) 792 Fp2.<beta> = Fp.extension(u^2 - non_residue_fp) 793 794 Z = Fp2([0, 1]) 795 h2c = genSVDW_H2C_G2_constants('BN254_Snarks', Curves, Z) 796 797 with open(f'{curve.lower()}_hash_to_curve_g2.nim', 'w') as f: 798 f.write(copyright()) 799 f.write('\n\n') 800 801 f.write(inspect.cleandoc(""" 802 import 803 ../config/curves, 804 ../io/[io_fields, io_extfields] 805 """)) 806 807 f.write('\n\n') 808 f.write(h2c) 809 810 print(f'Successfully created {curve.lower()}_hash_to_curve_g2.nim') 811 else: 812 raise ValueError( 813 curve + group_or_iso + 814 ' is not configured ' 815 )