generate_sqrt.sh (1876B)
1 #!/usr/bin/env bash 2 3 # generates a constant-time haskell function for performing modular 4 # square root with montgomery arithmetic on the secp256k1 field prime. 5 # 6 # tonelli-shanks is used. since p = 3 mod 4 for secp256k1, the square 7 # root simplifies to a single exponentiation: 8 # 9 # sqrt(a) = a ^ ((p + 1) / 4) mod p 10 # 11 # one proceeds through the (fixed, known) bit-string of the exponent 12 # in MSB order, montgomery-squaring an accumulator each time, and 13 # montgomery-multiplying on every '1' bit. this script generates a 14 # function consisting of this loop, unrolled. 15 # 16 # since the square-and-multiply schedule is fixed, then given 17 # constant-time 'sqr#' and 'mul#", 'sqrt#' is also constant-time by 18 # construction. 19 20 # for tonelli-shanks on secp256k1, p = 3 mod 4, so we compute: 21 # 22 # sqrt(a) = a ^ ((p + 1) / 4) mod p 23 # 24 # where p is the secp256k1 field prime: 25 # 26 # p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F 27 # 28 # and the exponent (p + 1) / 4 is: 29 # 30 # e = 0x3fffffffffffffffffffffffffffffffffffffffffffffffffffffffbfffff0c 31 32 exponent="0011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111100001100" 33 34 echo "-- generated by etc/generate_sqrt.sh" 35 echo "sqrt#" 36 echo " :: (# Limb, Limb, Limb, Limb #)" 37 echo " -> (# Limb, Limb, Limb, Limb #)" 38 echo "sqrt# a =" 39 echo " let !t0 = (# Limb 0x1000003D1##, Limb 0##, Limb 0##, Limb 0## #)" 40 41 label=1 42 43 for ((i = 0; i < ${#exponent}; i++)); do 44 echo " !t""$label"" = sqr# t""$((label-1))" 45 if [[ "${exponent:i:1}" == "1" ]]; then 46 label=$((label+1)) 47 echo " !t""$label"" = mul# a t""$((label-1))" 48 fi 49 label=$((label+1)) 50 done 51 52 echo " !r = t""$((label-1))" 53 echo " in r" 54 echo '{-# INLINE sqrt# #-}'