generate_inv.sh (2363B)
1 #!/usr/bin/env bash 2 3 # generates a constant-time haskell function for performing modular 4 # inversion with montgomery arithmetic on a secp256k1-derived field. 5 # 6 # fermat inversion is used. one proceeds through the (fixed, known) 7 # bit-string of the exponent in MSB order, montgomery-squaring an 8 # accumulator each time, and montgomery-multiplying on every '1' bit. 9 # this script generates a function consisting of this loop, unrolled. 10 # 11 # since the square-and-multiply schedule is fixed, then given 12 # constant-time 'sqr#' and 'mul#", 'inv#' is also constant-time by 13 # construction. 14 15 # for fermat inversion, we raise an argument to e.g. the secp256k1 field 16 # prime - 2. i.e.: 17 # 18 # a^-1 = a ^ p - 2 mod p 19 # 20 # or to the secp256k1 scalar group order - 2: 21 # 22 # a^-1 = a ^ q - 2 mod q 23 24 # secp256k1 field prime - 2 25 exponent_curve="1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111110000101101" 26 27 # secp256k1 scalar group order - 2 28 exponent_scalar="1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111010101011101101110011100110101011110100100010100000001110111011111111010010010111101000110011010000001101100100000100111111" 29 30 # adjust me as desired; use 'curve' or 'scalar' 31 target="scalar" 32 33 declare exponent 34 35 if [[ $target == "curve" ]]; then 36 exponent=$exponent_curve 37 elif [[ $target == "scalar" ]]; then 38 exponent=$exponent_scalar 39 fi 40 41 echo "-- generated by etc/generate_inv.sh" 42 echo "inv#" 43 echo " :: (# Word#, Word#, Word#, Word# #)" 44 echo " -> (# Word#, Word#, Word#, Word# #)" 45 echo "inv# a =" 46 if [[ $target == "curve" ]]; then 47 echo " let !t0 = (# 0x1000003D1##, 0##, 0##, 0## #)" 48 elif [[ $target == "scalar" ]]; then 49 echo " let !t0 = (# 0x402DA1732FC9BEBF##, 0x4551231950B75FC4##" 50 echo " , 0x0000000000000001##, 0x0000000000000000## #)" 51 fi 52 53 label=1 54 55 for ((i = 0; i < ${#exponent}; i++)); do 56 echo " !t""$label"" = sqr# t""$((label-1))" 57 if [[ "${exponent:i:1}" == "1" ]]; then 58 label=$((label+1)) 59 echo " !t""$label"" = mul# a t""$((label-1))" 60 fi 61 label=$((label+1)) 62 done 63 64 echo " !r = t""$((label-1))" 65 echo " in r" 66 echo '{-# INLINE inv# #-}' 67