generate_inv.sh (1946B)
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="1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111110000101101" 26 27 # secp256k1 scalar group order - 2 28 exponent="1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010111010101011101101110011100110101011110100100010100000001110111011111111010010010111101000110011010000001101100100000101000001" 29 30 echo "-- generated by etc/generate_inv.sh" 31 echo "inv#" 32 echo " :: (# Word#, Word#, Word#, Word# #)" 33 echo " -> (# Word#, Word#, Word#, Word# #)" 34 echo "inv# a =" 35 echo " let !t0 = (# 0x1000003D1##, 0##, 0##, 0## #) -- montgomery 'one'" 36 37 label=1 38 39 for ((i = 0; i < ${#exponent}; i++)); do 40 echo " !t""$label"" = sqr# t""$((label-1))" 41 if [[ "${exponent:i:1}" == "1" ]]; then 42 label=$((label+1)) 43 echo " !t""$label"" = mul# a t""$((label-1))" 44 fi 45 label=$((label+1)) 46 done 47 48 echo " !r = t""$((label-1))" 49 echo " in r" 50 echo '{-# INLINE inv# #-}' 51