sc_muladd.c (12790B)
1 #include "sc.h" 2 #include "crypto_int64.h" 3 #include "crypto_uint32.h" 4 #include "crypto_uint64.h" 5 6 static crypto_uint64 load_3(const unsigned char *in) 7 { 8 crypto_uint64 result; 9 result = (crypto_uint64) in[0]; 10 result |= ((crypto_uint64) in[1]) << 8; 11 result |= ((crypto_uint64) in[2]) << 16; 12 return result; 13 } 14 15 static crypto_uint64 load_4(const unsigned char *in) 16 { 17 crypto_uint64 result; 18 result = (crypto_uint64) in[0]; 19 result |= ((crypto_uint64) in[1]) << 8; 20 result |= ((crypto_uint64) in[2]) << 16; 21 result |= ((crypto_uint64) in[3]) << 24; 22 return result; 23 } 24 25 /* 26 Input: 27 a[0]+256*a[1]+...+256^31*a[31] = a 28 b[0]+256*b[1]+...+256^31*b[31] = b 29 c[0]+256*c[1]+...+256^31*c[31] = c 30 31 Output: 32 s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l 33 where l = 2^252 + 27742317777372353535851937790883648493. 34 */ 35 36 void sc_muladd(unsigned char *s,const unsigned char *a,const unsigned char *b,const unsigned char *c) 37 { 38 crypto_int64 a0 = 2097151 & load_3(a); 39 crypto_int64 a1 = 2097151 & (load_4(a + 2) >> 5); 40 crypto_int64 a2 = 2097151 & (load_3(a + 5) >> 2); 41 crypto_int64 a3 = 2097151 & (load_4(a + 7) >> 7); 42 crypto_int64 a4 = 2097151 & (load_4(a + 10) >> 4); 43 crypto_int64 a5 = 2097151 & (load_3(a + 13) >> 1); 44 crypto_int64 a6 = 2097151 & (load_4(a + 15) >> 6); 45 crypto_int64 a7 = 2097151 & (load_3(a + 18) >> 3); 46 crypto_int64 a8 = 2097151 & load_3(a + 21); 47 crypto_int64 a9 = 2097151 & (load_4(a + 23) >> 5); 48 crypto_int64 a10 = 2097151 & (load_3(a + 26) >> 2); 49 crypto_int64 a11 = (load_4(a + 28) >> 7); 50 crypto_int64 b0 = 2097151 & load_3(b); 51 crypto_int64 b1 = 2097151 & (load_4(b + 2) >> 5); 52 crypto_int64 b2 = 2097151 & (load_3(b + 5) >> 2); 53 crypto_int64 b3 = 2097151 & (load_4(b + 7) >> 7); 54 crypto_int64 b4 = 2097151 & (load_4(b + 10) >> 4); 55 crypto_int64 b5 = 2097151 & (load_3(b + 13) >> 1); 56 crypto_int64 b6 = 2097151 & (load_4(b + 15) >> 6); 57 crypto_int64 b7 = 2097151 & (load_3(b + 18) >> 3); 58 crypto_int64 b8 = 2097151 & load_3(b + 21); 59 crypto_int64 b9 = 2097151 & (load_4(b + 23) >> 5); 60 crypto_int64 b10 = 2097151 & (load_3(b + 26) >> 2); 61 crypto_int64 b11 = (load_4(b + 28) >> 7); 62 crypto_int64 c0 = 2097151 & load_3(c); 63 crypto_int64 c1 = 2097151 & (load_4(c + 2) >> 5); 64 crypto_int64 c2 = 2097151 & (load_3(c + 5) >> 2); 65 crypto_int64 c3 = 2097151 & (load_4(c + 7) >> 7); 66 crypto_int64 c4 = 2097151 & (load_4(c + 10) >> 4); 67 crypto_int64 c5 = 2097151 & (load_3(c + 13) >> 1); 68 crypto_int64 c6 = 2097151 & (load_4(c + 15) >> 6); 69 crypto_int64 c7 = 2097151 & (load_3(c + 18) >> 3); 70 crypto_int64 c8 = 2097151 & load_3(c + 21); 71 crypto_int64 c9 = 2097151 & (load_4(c + 23) >> 5); 72 crypto_int64 c10 = 2097151 & (load_3(c + 26) >> 2); 73 crypto_int64 c11 = (load_4(c + 28) >> 7); 74 crypto_int64 s0; 75 crypto_int64 s1; 76 crypto_int64 s2; 77 crypto_int64 s3; 78 crypto_int64 s4; 79 crypto_int64 s5; 80 crypto_int64 s6; 81 crypto_int64 s7; 82 crypto_int64 s8; 83 crypto_int64 s9; 84 crypto_int64 s10; 85 crypto_int64 s11; 86 crypto_int64 s12; 87 crypto_int64 s13; 88 crypto_int64 s14; 89 crypto_int64 s15; 90 crypto_int64 s16; 91 crypto_int64 s17; 92 crypto_int64 s18; 93 crypto_int64 s19; 94 crypto_int64 s20; 95 crypto_int64 s21; 96 crypto_int64 s22; 97 crypto_int64 s23; 98 crypto_int64 carry0; 99 crypto_int64 carry1; 100 crypto_int64 carry2; 101 crypto_int64 carry3; 102 crypto_int64 carry4; 103 crypto_int64 carry5; 104 crypto_int64 carry6; 105 crypto_int64 carry7; 106 crypto_int64 carry8; 107 crypto_int64 carry9; 108 crypto_int64 carry10; 109 crypto_int64 carry11; 110 crypto_int64 carry12; 111 crypto_int64 carry13; 112 crypto_int64 carry14; 113 crypto_int64 carry15; 114 crypto_int64 carry16; 115 crypto_int64 carry17; 116 crypto_int64 carry18; 117 crypto_int64 carry19; 118 crypto_int64 carry20; 119 crypto_int64 carry21; 120 crypto_int64 carry22; 121 122 s0 = c0 + a0*b0; 123 s1 = c1 + a0*b1 + a1*b0; 124 s2 = c2 + a0*b2 + a1*b1 + a2*b0; 125 s3 = c3 + a0*b3 + a1*b2 + a2*b1 + a3*b0; 126 s4 = c4 + a0*b4 + a1*b3 + a2*b2 + a3*b1 + a4*b0; 127 s5 = c5 + a0*b5 + a1*b4 + a2*b3 + a3*b2 + a4*b1 + a5*b0; 128 s6 = c6 + a0*b6 + a1*b5 + a2*b4 + a3*b3 + a4*b2 + a5*b1 + a6*b0; 129 s7 = c7 + a0*b7 + a1*b6 + a2*b5 + a3*b4 + a4*b3 + a5*b2 + a6*b1 + a7*b0; 130 s8 = c8 + a0*b8 + a1*b7 + a2*b6 + a3*b5 + a4*b4 + a5*b3 + a6*b2 + a7*b1 + a8*b0; 131 s9 = c9 + a0*b9 + a1*b8 + a2*b7 + a3*b6 + a4*b5 + a5*b4 + a6*b3 + a7*b2 + a8*b1 + a9*b0; 132 s10 = c10 + a0*b10 + a1*b9 + a2*b8 + a3*b7 + a4*b6 + a5*b5 + a6*b4 + a7*b3 + a8*b2 + a9*b1 + a10*b0; 133 s11 = c11 + a0*b11 + a1*b10 + a2*b9 + a3*b8 + a4*b7 + a5*b6 + a6*b5 + a7*b4 + a8*b3 + a9*b2 + a10*b1 + a11*b0; 134 s12 = a1*b11 + a2*b10 + a3*b9 + a4*b8 + a5*b7 + a6*b6 + a7*b5 + a8*b4 + a9*b3 + a10*b2 + a11*b1; 135 s13 = a2*b11 + a3*b10 + a4*b9 + a5*b8 + a6*b7 + a7*b6 + a8*b5 + a9*b4 + a10*b3 + a11*b2; 136 s14 = a3*b11 + a4*b10 + a5*b9 + a6*b8 + a7*b7 + a8*b6 + a9*b5 + a10*b4 + a11*b3; 137 s15 = a4*b11 + a5*b10 + a6*b9 + a7*b8 + a8*b7 + a9*b6 + a10*b5 + a11*b4; 138 s16 = a5*b11 + a6*b10 + a7*b9 + a8*b8 + a9*b7 + a10*b6 + a11*b5; 139 s17 = a6*b11 + a7*b10 + a8*b9 + a9*b8 + a10*b7 + a11*b6; 140 s18 = a7*b11 + a8*b10 + a9*b9 + a10*b8 + a11*b7; 141 s19 = a8*b11 + a9*b10 + a10*b9 + a11*b8; 142 s20 = a9*b11 + a10*b10 + a11*b9; 143 s21 = a10*b11 + a11*b10; 144 s22 = a11*b11; 145 s23 = 0; 146 147 carry0 = (s0 + (1<<20)) >> 21; s1 += carry0; s0 -= SHL64(carry0,21); 148 carry2 = (s2 + (1<<20)) >> 21; s3 += carry2; s2 -= SHL64(carry2,21); 149 carry4 = (s4 + (1<<20)) >> 21; s5 += carry4; s4 -= SHL64(carry4,21); 150 carry6 = (s6 + (1<<20)) >> 21; s7 += carry6; s6 -= SHL64(carry6,21); 151 carry8 = (s8 + (1<<20)) >> 21; s9 += carry8; s8 -= SHL64(carry8,21); 152 carry10 = (s10 + (1<<20)) >> 21; s11 += carry10; s10 -= SHL64(carry10,21); 153 carry12 = (s12 + (1<<20)) >> 21; s13 += carry12; s12 -= SHL64(carry12,21); 154 carry14 = (s14 + (1<<20)) >> 21; s15 += carry14; s14 -= SHL64(carry14,21); 155 carry16 = (s16 + (1<<20)) >> 21; s17 += carry16; s16 -= SHL64(carry16,21); 156 carry18 = (s18 + (1<<20)) >> 21; s19 += carry18; s18 -= SHL64(carry18,21); 157 carry20 = (s20 + (1<<20)) >> 21; s21 += carry20; s20 -= SHL64(carry20,21); 158 carry22 = (s22 + (1<<20)) >> 21; s23 += carry22; s22 -= SHL64(carry22,21); 159 160 carry1 = (s1 + (1<<20)) >> 21; s2 += carry1; s1 -= SHL64(carry1,21); 161 carry3 = (s3 + (1<<20)) >> 21; s4 += carry3; s3 -= SHL64(carry3,21); 162 carry5 = (s5 + (1<<20)) >> 21; s6 += carry5; s5 -= SHL64(carry5,21); 163 carry7 = (s7 + (1<<20)) >> 21; s8 += carry7; s7 -= SHL64(carry7,21); 164 carry9 = (s9 + (1<<20)) >> 21; s10 += carry9; s9 -= SHL64(carry9,21); 165 carry11 = (s11 + (1<<20)) >> 21; s12 += carry11; s11 -= SHL64(carry11,21); 166 carry13 = (s13 + (1<<20)) >> 21; s14 += carry13; s13 -= SHL64(carry13,21); 167 carry15 = (s15 + (1<<20)) >> 21; s16 += carry15; s15 -= SHL64(carry15,21); 168 carry17 = (s17 + (1<<20)) >> 21; s18 += carry17; s17 -= SHL64(carry17,21); 169 carry19 = (s19 + (1<<20)) >> 21; s20 += carry19; s19 -= SHL64(carry19,21); 170 carry21 = (s21 + (1<<20)) >> 21; s22 += carry21; s21 -= SHL64(carry21,21); 171 172 s11 += s23 * 666643; 173 s12 += s23 * 470296; 174 s13 += s23 * 654183; 175 s14 -= s23 * 997805; 176 s15 += s23 * 136657; 177 s16 -= s23 * 683901; 178 s23 = 0; 179 180 s10 += s22 * 666643; 181 s11 += s22 * 470296; 182 s12 += s22 * 654183; 183 s13 -= s22 * 997805; 184 s14 += s22 * 136657; 185 s15 -= s22 * 683901; 186 s22 = 0; 187 188 s9 += s21 * 666643; 189 s10 += s21 * 470296; 190 s11 += s21 * 654183; 191 s12 -= s21 * 997805; 192 s13 += s21 * 136657; 193 s14 -= s21 * 683901; 194 s21 = 0; 195 196 s8 += s20 * 666643; 197 s9 += s20 * 470296; 198 s10 += s20 * 654183; 199 s11 -= s20 * 997805; 200 s12 += s20 * 136657; 201 s13 -= s20 * 683901; 202 s20 = 0; 203 204 s7 += s19 * 666643; 205 s8 += s19 * 470296; 206 s9 += s19 * 654183; 207 s10 -= s19 * 997805; 208 s11 += s19 * 136657; 209 s12 -= s19 * 683901; 210 s19 = 0; 211 212 s6 += s18 * 666643; 213 s7 += s18 * 470296; 214 s8 += s18 * 654183; 215 s9 -= s18 * 997805; 216 s10 += s18 * 136657; 217 s11 -= s18 * 683901; 218 s18 = 0; 219 220 carry6 = (s6 + (1<<20)) >> 21; s7 += carry6; s6 -= SHL64(carry6,21); 221 carry8 = (s8 + (1<<20)) >> 21; s9 += carry8; s8 -= SHL64(carry8,21); 222 carry10 = (s10 + (1<<20)) >> 21; s11 += carry10; s10 -= SHL64(carry10,21); 223 carry12 = (s12 + (1<<20)) >> 21; s13 += carry12; s12 -= SHL64(carry12,21); 224 carry14 = (s14 + (1<<20)) >> 21; s15 += carry14; s14 -= SHL64(carry14,21); 225 carry16 = (s16 + (1<<20)) >> 21; s17 += carry16; s16 -= SHL64(carry16,21); 226 227 carry7 = (s7 + (1<<20)) >> 21; s8 += carry7; s7 -= SHL64(carry7,21); 228 carry9 = (s9 + (1<<20)) >> 21; s10 += carry9; s9 -= SHL64(carry9,21); 229 carry11 = (s11 + (1<<20)) >> 21; s12 += carry11; s11 -= SHL64(carry11,21); 230 carry13 = (s13 + (1<<20)) >> 21; s14 += carry13; s13 -= SHL64(carry13,21); 231 carry15 = (s15 + (1<<20)) >> 21; s16 += carry15; s15 -= SHL64(carry15,21); 232 233 s5 += s17 * 666643; 234 s6 += s17 * 470296; 235 s7 += s17 * 654183; 236 s8 -= s17 * 997805; 237 s9 += s17 * 136657; 238 s10 -= s17 * 683901; 239 s17 = 0; 240 241 s4 += s16 * 666643; 242 s5 += s16 * 470296; 243 s6 += s16 * 654183; 244 s7 -= s16 * 997805; 245 s8 += s16 * 136657; 246 s9 -= s16 * 683901; 247 s16 = 0; 248 249 s3 += s15 * 666643; 250 s4 += s15 * 470296; 251 s5 += s15 * 654183; 252 s6 -= s15 * 997805; 253 s7 += s15 * 136657; 254 s8 -= s15 * 683901; 255 s15 = 0; 256 257 s2 += s14 * 666643; 258 s3 += s14 * 470296; 259 s4 += s14 * 654183; 260 s5 -= s14 * 997805; 261 s6 += s14 * 136657; 262 s7 -= s14 * 683901; 263 s14 = 0; 264 265 s1 += s13 * 666643; 266 s2 += s13 * 470296; 267 s3 += s13 * 654183; 268 s4 -= s13 * 997805; 269 s5 += s13 * 136657; 270 s6 -= s13 * 683901; 271 s13 = 0; 272 273 s0 += s12 * 666643; 274 s1 += s12 * 470296; 275 s2 += s12 * 654183; 276 s3 -= s12 * 997805; 277 s4 += s12 * 136657; 278 s5 -= s12 * 683901; 279 s12 = 0; 280 281 carry0 = (s0 + (1<<20)) >> 21; s1 += carry0; s0 -= SHL64(carry0,21); 282 carry2 = (s2 + (1<<20)) >> 21; s3 += carry2; s2 -= SHL64(carry2,21); 283 carry4 = (s4 + (1<<20)) >> 21; s5 += carry4; s4 -= SHL64(carry4,21); 284 carry6 = (s6 + (1<<20)) >> 21; s7 += carry6; s6 -= SHL64(carry6,21); 285 carry8 = (s8 + (1<<20)) >> 21; s9 += carry8; s8 -= SHL64(carry8,21); 286 carry10 = (s10 + (1<<20)) >> 21; s11 += carry10; s10 -= SHL64(carry10,21); 287 288 carry1 = (s1 + (1<<20)) >> 21; s2 += carry1; s1 -= SHL64(carry1,21); 289 carry3 = (s3 + (1<<20)) >> 21; s4 += carry3; s3 -= SHL64(carry3,21); 290 carry5 = (s5 + (1<<20)) >> 21; s6 += carry5; s5 -= SHL64(carry5,21); 291 carry7 = (s7 + (1<<20)) >> 21; s8 += carry7; s7 -= SHL64(carry7,21); 292 carry9 = (s9 + (1<<20)) >> 21; s10 += carry9; s9 -= SHL64(carry9,21); 293 carry11 = (s11 + (1<<20)) >> 21; s12 += carry11; s11 -= SHL64(carry11,21); 294 295 s0 += s12 * 666643; 296 s1 += s12 * 470296; 297 s2 += s12 * 654183; 298 s3 -= s12 * 997805; 299 s4 += s12 * 136657; 300 s5 -= s12 * 683901; 301 s12 = 0; 302 303 carry0 = s0 >> 21; s1 += carry0; s0 -= SHL64(carry0,21); 304 carry1 = s1 >> 21; s2 += carry1; s1 -= SHL64(carry1,21); 305 carry2 = s2 >> 21; s3 += carry2; s2 -= SHL64(carry2,21); 306 carry3 = s3 >> 21; s4 += carry3; s3 -= SHL64(carry3,21); 307 carry4 = s4 >> 21; s5 += carry4; s4 -= SHL64(carry4,21); 308 carry5 = s5 >> 21; s6 += carry5; s5 -= SHL64(carry5,21); 309 carry6 = s6 >> 21; s7 += carry6; s6 -= SHL64(carry6,21); 310 carry7 = s7 >> 21; s8 += carry7; s7 -= SHL64(carry7,21); 311 carry8 = s8 >> 21; s9 += carry8; s8 -= SHL64(carry8,21); 312 carry9 = s9 >> 21; s10 += carry9; s9 -= SHL64(carry9,21); 313 carry10 = s10 >> 21; s11 += carry10; s10 -= SHL64(carry10,21); 314 carry11 = s11 >> 21; s12 += carry11; s11 -= SHL64(carry11,21); 315 316 s0 += s12 * 666643; 317 s1 += s12 * 470296; 318 s2 += s12 * 654183; 319 s3 -= s12 * 997805; 320 s4 += s12 * 136657; 321 s5 -= s12 * 683901; 322 s12 = 0; 323 324 carry0 = s0 >> 21; s1 += carry0; s0 -= SHL64(carry0,21); 325 carry1 = s1 >> 21; s2 += carry1; s1 -= SHL64(carry1,21); 326 carry2 = s2 >> 21; s3 += carry2; s2 -= SHL64(carry2,21); 327 carry3 = s3 >> 21; s4 += carry3; s3 -= SHL64(carry3,21); 328 carry4 = s4 >> 21; s5 += carry4; s4 -= SHL64(carry4,21); 329 carry5 = s5 >> 21; s6 += carry5; s5 -= SHL64(carry5,21); 330 carry6 = s6 >> 21; s7 += carry6; s6 -= SHL64(carry6,21); 331 carry7 = s7 >> 21; s8 += carry7; s7 -= SHL64(carry7,21); 332 carry8 = s8 >> 21; s9 += carry8; s8 -= SHL64(carry8,21); 333 carry9 = s9 >> 21; s10 += carry9; s9 -= SHL64(carry9,21); 334 carry10 = s10 >> 21; s11 += carry10; s10 -= SHL64(carry10,21); 335 336 s[0] = s0 >> 0; 337 s[1] = s0 >> 8; 338 s[2] = (s0 >> 16) | SHL64(s1,5); 339 s[3] = s1 >> 3; 340 s[4] = s1 >> 11; 341 s[5] = (s1 >> 19) | SHL64(s2,2); 342 s[6] = s2 >> 6; 343 s[7] = (s2 >> 14) | SHL64(s3,7); 344 s[8] = s3 >> 1; 345 s[9] = s3 >> 9; 346 s[10] = (s3 >> 17) | SHL64(s4,4); 347 s[11] = s4 >> 4; 348 s[12] = s4 >> 12; 349 s[13] = (s4 >> 20) | SHL64(s5,1); 350 s[14] = s5 >> 7; 351 s[15] = (s5 >> 15) | SHL64(s6,6); 352 s[16] = s6 >> 2; 353 s[17] = s6 >> 10; 354 s[18] = (s6 >> 18) | SHL64(s7,3); 355 s[19] = s7 >> 5; 356 s[20] = s7 >> 13; 357 s[21] = s8 >> 0; 358 s[22] = s8 >> 8; 359 s[23] = (s8 >> 16) | SHL64(s9,5); 360 s[24] = s9 >> 3; 361 s[25] = s9 >> 11; 362 s[26] = (s9 >> 19) | SHL64(s10,2); 363 s[27] = s10 >> 6; 364 s[28] = (s10 >> 14) | SHL64(s11,7); 365 s[29] = s11 >> 1; 366 s[30] = s11 >> 9; 367 s[31] = s11 >> 17; 368 }