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  
 25  # Working directory
 26  # ---------------------------------------------------------
 27  
 28  os.chdir(os.path.dirname(__file__))
 29  
 30  # Sage imports
 31  # ---------------------------------------------------------
 32  # Accelerate arithmetic by accepting probabilistic proofs
 33  from sage.structure.proof.all import arithmetic
 34  arithmetic(False)
 35  
 36  load('curves.sage')
 37  
 38  # Utilities
 39  # ---------------------------------------------------------
 40  
 41  def fp2_to_hex(a):
 42      v = vector(a)
 43      return '0x' + Integer(v[0]).hex() + ' + β * ' + '0x' + Integer(v[1]).hex()
 44  
 45  def field_to_nim(value, field, curve, prefix = "", comment_above = "", comment_right = ""):
 46    result = '# ' + comment_above + '\n' if comment_above else ''
 47    comment_right = ' # ' + comment_right if comment_right else ''
 48  
 49    if field == 'Fp2':
 50      v = vector(value)
 51  
 52      result += inspect.cleandoc(f"""
 53        {prefix}Fp2[{curve}].fromHex( {comment_right}
 54          "0x{Integer(v[0]).hex()}",
 55          "0x{Integer(v[1]).hex()}"
 56        )""")
 57    elif field == 'Fp':
 58      result += inspect.cleandoc(f"""
 59        {prefix}Fp[{curve}].fromHex( {comment_right}
 60          "0x{Integer(value).hex()}")
 61        """)
 62    else:
 63      raise NotImplementedError()
 64  
 65    return result
 66  
 67  # Code generators
 68  # ---------------------------------------------------------
 69  
 70  def genSqrtFp2Constants(curve_name, curve_config):
 71    embdeg = curve_config[curve_name]['tower']['embedding_degree']
 72    twdeg = curve_config[curve_name]['tower']['twist_degree']
 73    g2field = f'Fp{embdeg//twdeg}' if (embdeg//twdeg) > 1 else 'Fp'
 74  
 75    p = curve_config[curve_name]['field']['modulus']
 76    Fp = GF(p)
 77    K.<u> = PolynomialRing(Fp)
 78    if g2field == 'Fp2':
 79      QNR_Fp = curve_config[curve_name]['tower']['QNR_Fp']
 80      Fp2.<beta> = Fp.extension(u^2 - QNR_Fp)
 81    else:
 82      SNR_Fp = curve_config[curve_name]['tower']['SNR_Fp']
 83      Fp2.<beta> = Fp.extension(u^2 - SNR_Fp)
 84  
 85    sqrt_QNR = Fp2([0, 1])
 86    sqrt_sqrt_QNR = sqrt_QNR.sqrt()
 87    sqrt_minus_sqrt_QNR = (-sqrt_QNR).sqrt()
 88  
 89    print('\n----> Square root on Fp2 constants <----\n')
 90    buf = inspect.cleandoc(f"""
 91        # Square Root Fp2 constants
 92        # -----------------------------------------------------------------
 93    """)
 94    buf += '\n'
 95  
 96    buf += f'const {curve_name}_sqrt_QNR* = '
 97    buf += field_to_nim(sqrt_QNR, 'Fp2', curve_name)
 98    buf += '\n'
 99  
100    buf += f'const {curve_name}_sqrt_sqrt_QNR* = '
101    buf += field_to_nim(sqrt_sqrt_QNR, 'Fp2', curve_name)
102    buf += '\n'
103  
104    buf += f'const {curve_name}_sqrt_minus_sqrt_QNR* = '
105    buf += field_to_nim(sqrt_minus_sqrt_QNR, 'Fp2', curve_name)
106    buf += '\n'
107  
108    return buf
109  
110  # CLI
111  # ---------------------------------------------------------
112  
113  if __name__ == "__main__":
114    # Usage
115    # BLS12-381
116    # sage sage/derive_sqrt.sage BLS12_381
117  
118    from argparse import ArgumentParser
119  
120    parser = ArgumentParser()
121    parser.add_argument("curve",nargs="+")
122    args = parser.parse_args()
123  
124    curve = args.curve[0]
125  
126    if curve not in Curves:
127      raise ValueError(
128        curve +
129        ' is not one of the available curves: ' +
130        str(Curves.keys())
131      )
132    else:
133      sqrt = genSqrtFp2Constants(curve, Curves)
134  
135      with open(f'{curve.lower()}_square_root.nim', 'w') as f:
136        f.write(copyright())
137        f.write('\n\n')
138  
139        f.write(inspect.cleandoc("""
140            import
141              ../config/curves,
142              ../io/io_extfields
143        """))
144  
145        f.write('\n\n')
146        f.write(sqrt)
147  
148      print(f'Successfully created {curve}_sqrt_fp2.nim')