glv.nim
1 # Research into the paper 2 3 # - Efficient and Secure Algorithms for GLV-Based Scalar 4 # Multiplication and their Implementation on GLV-GLS 5 # Curves (Extended Version) 6 # Armando Faz-Hernández, Patrick Longa, Ana H. Sánchez, 2013 7 # https://eprint.iacr.org/2013/158.pdf 8 9 import ../constantine/math/elliptic/ec_endomorphism_accel {.all.}, 10 ../constantine/platforms/abstractions, 11 ../constantine/math/io/io_bigints, 12 ../constantine/math/arithmetic 13 14 proc toString(glvSac: GLV_SAC): string = 15 for j in 0 ..< glvSac.M: 16 result.add "k" & $j & ": [" 17 for i in countdown(glvSac.LengthInDigits-1, 0): 18 result.add " " & (block: 19 case glvSac[j][i] 20 of 0: "0" 21 of 1: "1" 22 else: 23 raise newException(ValueError, "Unexpected encoded value: " & $glvSac[j][i]) 24 ) 25 result.add " ]\n" 26 27 iterator bits(u: SomeInteger): tuple[bitIndex: int32, bitValue: uint8] = 28 ## bit iterator, starts from the least significant bit 29 var u = u 30 var idx = 0'i32 31 while u != 0: 32 yield (idx, uint8(u and 1)) 33 u = u shr 1 34 inc idx 35 36 func buildLookupTable_naive[M: static int]( 37 P: string, 38 endomorphisms: array[M-1, string], 39 lut: var array[1 shl (M-1), string], 40 ) = 41 ## Checking the LUT by building strings of endomorphisms additions 42 ## This naively translates the lookup table algorithm 43 ## Compute P[u] = P0 + u0 P1 +...+ um−2 Pm−1 for all 0≤u<2m−1, where 44 ## u= (um−2,...,u0)_2. 45 ## The number of additions done per entries is equal to the 46 ## iteration variable `u` Hamming Weight 47 for u in 0 ..< 1 shl (M-1): 48 lut[u] = P 49 for u in 0 ..< 1 shl (M-1): 50 for idx, bit in bits(u): 51 if bit == 1: 52 lut[u] &= " + " & endomorphisms[idx] 53 54 func buildLookupTable_reuse[M: static int]( 55 P: string, 56 endomorphisms: array[M-1, string], 57 lut: var array[1 shl (M-1), string], 58 ) = 59 ## Checking the LUT by building strings of endomorphisms additions 60 ## This reuses previous table entries so that only one addition is done 61 ## per new entries 62 lut[0] = P 63 for u in 1'u32 ..< 1 shl (M-1): 64 let msb = u.log2_vartime() # No undefined, u != 0 65 lut[u] = lut[u.clearBit(msb)] & " + " & endomorphisms[msb] 66 67 proc main_lut() = 68 const M = 4 # GLS-4 decomposition 69 const miniBitwidth = 4 # Bitwidth of the miniscalars resulting from scalar decomposition 70 71 var k: MultiScalar[M, miniBitwidth] 72 var kRecoded: GLV_SAC[M, miniBitwidth] 73 74 k[0].fromUint(11) 75 k[1].fromUint(6) 76 k[2].fromuint(14) 77 k[3].fromUint(3) 78 79 kRecoded.nDimMultiScalarRecoding(k) 80 81 echo "Recoded bytesize: ", sizeof(kRecoded) 82 echo kRecoded.toString() 83 84 var lut: array[1 shl (M-1), string] 85 let 86 P = "P0" 87 endomorphisms = ["P1", "P2", "P3"] 88 89 buildLookupTable_naive(P, endomorphisms, lut) 90 echo lut 91 doAssert lut[0] == "P0" 92 doAssert lut[1] == "P0 + P1" 93 doAssert lut[2] == "P0 + P2" 94 doAssert lut[3] == "P0 + P1 + P2" 95 doAssert lut[4] == "P0 + P3" 96 doAssert lut[5] == "P0 + P1 + P3" 97 doAssert lut[6] == "P0 + P2 + P3" 98 doAssert lut[7] == "P0 + P1 + P2 + P3" 99 100 var lut_reuse: array[1 shl (M-1), string] 101 buildLookupTable_reuse(P, endomorphisms, lut_reuse) 102 echo lut_reuse 103 doAssert lut == lut_reuse 104 105 main_lut() 106 echo "---------------------------------------------" 107 108 # This tests the multiplication against the Table 1 109 # of the paper 110 111 # Coef Decimal Binary GLV-SAC recoded 112 # | k0 | | 11 | | 0 1 0 1 1 | | 1 -1 1 -1 1 | 113 # | k1 | = | 6 | = | 0 0 1 1 0 | = | 1 -1 0 -1 0 | 114 # | k2 | | 14 | | 0 1 1 1 0 | | 1 0 0 -1 0 | 115 # | k3 | | 3 | | 0 0 0 1 1 | | 0 0 1 -1 1 | 116 117 # i | 3 2 1 0 118 # -------------------+---------------------------------------------------------------------- 119 # 2Q | 2P0+2P1+2P2 2P0+2P1+4P2 6P0+4P1+8P2+2P3 10P0+6P1+14P2+2P3 120 # Q + sign_i T[ki] | P0+P1+2P2 3P0+2P1+4P2+P3 5P0+3P1+7P2+P3 11P0+6P1+14P2+3P3 121 122 type Endo = enum 123 P0 124 P1 125 P2 126 P3 127 128 func buildLookupTable_reuse[M: static int]( 129 P: Endo, 130 endomorphisms: array[M-1, Endo], 131 lut: var array[1 shl (M-1), set[Endo]], 132 ) = 133 ## Checking the LUT by building strings of endomorphisms additions 134 ## This reuses previous table entries so that only one addition is done 135 ## per new entries 136 lut[0].incl P 137 for u in 1'u32 ..< 1 shl (M-1): 138 let msb = u.log2_vartime() # No undefined, u != 0 139 lut[u] = lut[u.clearBit(msb)] + {endomorphisms[msb]} 140 141 142 proc mainFullMul() = 143 const M = 4 # GLS-4 decomposition 144 const miniBitwidth = 4 # Bitwidth of the miniscalars resulting from scalar decomposition 145 const L = miniBitwidth + 1 # Bitwidth of the recoded scalars 146 147 var k: MultiScalar[M, L] 148 var kRecoded: GLV_SAC[M, L] 149 150 k[0].fromUint(11) 151 k[1].fromUint(6) 152 k[2].fromuint(14) 153 k[3].fromUint(3) 154 155 kRecoded.nDimMultiScalarRecoding(k) 156 157 echo kRecoded.toString() 158 159 var lut: array[1 shl (M-1), set[Endo]] 160 let 161 P = P0 162 endomorphisms = [P1, P2, P3] 163 164 buildLookupTable_reuse(P, endomorphisms, lut) 165 echo lut 166 167 var Q: array[Endo, int] 168 169 # Multiplication 170 assert bool k[0].isOdd() 171 # Q = sign_l-1 P[K_l-1] 172 let idx = kRecoded.tableIndex(L-1) 173 for p in lut[int(idx)]: 174 Q[p] = if kRecoded[0][L-1] == 0: 1 else: -1 175 # Loop 176 for i in countdown(L-2, 0): 177 # Q = 2Q 178 for val in Q.mitems: val *= 2 179 echo "2Q: ", Q 180 # Q = Q + sign_l-1 P[K_l-1] 181 let idx = kRecoded.tableIndex(i) 182 for p in lut[int(idx)]: 183 Q[p] += (if kRecoded[0][i] == 0: 1 else: -1) 184 echo "Q + sign_l-1 P[K_l-1]: ", Q 185 186 echo Q 187 188 mainFullMul() 189 echo "---------------------------------------------" 190 191 func buildLookupTable_m2w2( 192 lut: var array[8, array[2, int]], 193 ) = 194 ## Build a lookup table for GLV with 2-dimensional decomposition 195 ## and window of size 2 196 197 # with [k0, k1] the mini-scalars with digits of size 2-bit 198 # 199 # 0 = 0b000 - encodes [0b01, 0b00] ≡ P0 200 lut[0] = [1, 0] 201 # 1 = 0b001 - encodes [0b01, 0b01] ≡ P0 - P1 202 lut[1] = [1, -1] 203 # 3 = 0b011 - encodes [0b01, 0b11] ≡ P0 + P1 204 lut[3] = [1, 1] 205 # 2 = 0b010 - encodes [0b01, 0b10] ≡ P0 + 2P1 206 lut[2] = [1, 2] 207 208 # 4 = 0b100 - encodes [0b00, 0b00] ≡ 3P0 209 lut[4] = [3, 0] 210 # 5 = 0b101 - encodes [0b00, 0b01] ≡ 3P0 + P1 211 lut[5] = [3, 1] 212 # 6 = 0b110 - encodes [0b00, 0b10] ≡ 3P0 + 2P1 213 lut[6] = [3, 2] 214 # 7 = 0b111 - encodes [0b00, 0b11] ≡ 3P0 + 3P1 215 lut[7] = [3, 3] 216 217 proc mainFullMulWindowed() = 218 const M = 2 # GLS-2 decomposition 219 const miniBitwidth = 8 # Bitwidth of the miniscalars resulting from scalar decomposition 220 const W = 2 # Window 221 const L = computeRecodedLength(miniBitwidth, W) 222 223 var k: MultiScalar[M, L] 224 var kRecoded: GLV_SAC[M, L] 225 226 k[0].fromUint(11) 227 k[1].fromUint(14) 228 229 kRecoded.nDimMultiScalarRecoding(k) 230 231 echo "Recoded bytesize: ", sizeof(kRecoded) 232 echo kRecoded.toString() 233 234 var lut: array[8, array[range[P0..P1], int]] 235 buildLookupTable_m2w2(lut) 236 echo lut 237 238 # Assumes k[0] is odd to simplify test 239 # and having to conditional substract at the end 240 assert bool k[0].isOdd() 241 242 var Q: array[Endo, int] 243 var isNeg: SecretBool 244 245 let idx = kRecoded.w2TableIndex((L div 2)-1, isNeg) 246 for p, coef in lut[int(idx)]: 247 # Unneeeded by construction 248 # let sign = if isNeg: -1 else: 1 249 Q[p] = coef 250 251 # Loop 252 for i in countdown((L div 2)-2, 0): 253 # Q = 4Q 254 for val in Q.mitems: val *= 4 255 echo "4Q: ", Q 256 # Q = Q + sign_l-1 P[K_l-1] 257 let idx = kRecoded.w2TableIndex(i, isNeg) 258 for p, coef in lut[int(idx)]: 259 let sign = (if bool isNeg: -1 else: 1) 260 Q[p] += sign * coef 261 echo "Q + sign_l-1 P[K_l-1]: ", Q 262 263 echo Q 264 265 mainFullMulWindowed()