curve25519-donna-32bit.h (22614B)
1 /* 2 Public domain by Andrew M. <liquidsun@gmail.com> 3 See: https://github.com/floodyberry/curve25519-donna 4 5 32 bit integer curve25519 implementation 6 */ 7 8 typedef uint32_t bignum25519[10]; 9 typedef uint32_t bignum25519align16[12]; 10 11 static const uint32_t reduce_mask_25 = (1 << 25) - 1; 12 static const uint32_t reduce_mask_26 = (1 << 26) - 1; 13 14 15 /* out = in */ 16 DONNA_INLINE static void 17 curve25519_copy(bignum25519 out, const bignum25519 in) { 18 out[0] = in[0]; 19 out[1] = in[1]; 20 out[2] = in[2]; 21 out[3] = in[3]; 22 out[4] = in[4]; 23 out[5] = in[5]; 24 out[6] = in[6]; 25 out[7] = in[7]; 26 out[8] = in[8]; 27 out[9] = in[9]; 28 } 29 30 /* out = a + b */ 31 DONNA_INLINE static void 32 curve25519_add(bignum25519 out, const bignum25519 a, const bignum25519 b) { 33 out[0] = a[0] + b[0]; 34 out[1] = a[1] + b[1]; 35 out[2] = a[2] + b[2]; 36 out[3] = a[3] + b[3]; 37 out[4] = a[4] + b[4]; 38 out[5] = a[5] + b[5]; 39 out[6] = a[6] + b[6]; 40 out[7] = a[7] + b[7]; 41 out[8] = a[8] + b[8]; 42 out[9] = a[9] + b[9]; 43 } 44 45 DONNA_INLINE static void 46 curve25519_add_after_basic(bignum25519 out, const bignum25519 a, const bignum25519 b) { 47 uint32_t c; 48 out[0] = a[0] + b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26; 49 out[1] = a[1] + b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25; 50 out[2] = a[2] + b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26; 51 out[3] = a[3] + b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25; 52 out[4] = a[4] + b[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26; 53 out[5] = a[5] + b[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25; 54 out[6] = a[6] + b[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26; 55 out[7] = a[7] + b[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25; 56 out[8] = a[8] + b[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26; 57 out[9] = a[9] + b[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25; 58 out[0] += 19 * c; 59 } 60 61 DONNA_INLINE static void 62 curve25519_add_reduce(bignum25519 out, const bignum25519 a, const bignum25519 b) { 63 uint32_t c; 64 out[0] = a[0] + b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26; 65 out[1] = a[1] + b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25; 66 out[2] = a[2] + b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26; 67 out[3] = a[3] + b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25; 68 out[4] = a[4] + b[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26; 69 out[5] = a[5] + b[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25; 70 out[6] = a[6] + b[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26; 71 out[7] = a[7] + b[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25; 72 out[8] = a[8] + b[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26; 73 out[9] = a[9] + b[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25; 74 out[0] += 19 * c; 75 } 76 77 /* multiples of p */ 78 static const uint32_t twoP0 = 0x07ffffda; 79 static const uint32_t twoP13579 = 0x03fffffe; 80 static const uint32_t twoP2468 = 0x07fffffe; 81 static const uint32_t fourP0 = 0x0fffffb4; 82 static const uint32_t fourP13579 = 0x07fffffc; 83 static const uint32_t fourP2468 = 0x0ffffffc; 84 85 /* out = a - b */ 86 DONNA_INLINE static void 87 curve25519_sub(bignum25519 out, const bignum25519 a, const bignum25519 b) { 88 uint32_t c; 89 out[0] = twoP0 + a[0] - b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26; 90 out[1] = twoP13579 + a[1] - b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25; 91 out[2] = twoP2468 + a[2] - b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26; 92 out[3] = twoP13579 + a[3] - b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25; 93 out[4] = twoP2468 + a[4] - b[4] + c; 94 out[5] = twoP13579 + a[5] - b[5] ; 95 out[6] = twoP2468 + a[6] - b[6] ; 96 out[7] = twoP13579 + a[7] - b[7] ; 97 out[8] = twoP2468 + a[8] - b[8] ; 98 out[9] = twoP13579 + a[9] - b[9] ; 99 } 100 101 /* out = a - b, where a is the result of a basic op (add,sub) */ 102 DONNA_INLINE static void 103 curve25519_sub_after_basic(bignum25519 out, const bignum25519 a, const bignum25519 b) { 104 uint32_t c; 105 out[0] = fourP0 + a[0] - b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26; 106 out[1] = fourP13579 + a[1] - b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25; 107 out[2] = fourP2468 + a[2] - b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26; 108 out[3] = fourP13579 + a[3] - b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25; 109 out[4] = fourP2468 + a[4] - b[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26; 110 out[5] = fourP13579 + a[5] - b[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25; 111 out[6] = fourP2468 + a[6] - b[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26; 112 out[7] = fourP13579 + a[7] - b[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25; 113 out[8] = fourP2468 + a[8] - b[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26; 114 out[9] = fourP13579 + a[9] - b[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25; 115 out[0] += 19 * c; 116 } 117 118 DONNA_INLINE static void 119 curve25519_sub_reduce(bignum25519 out, const bignum25519 a, const bignum25519 b) { 120 uint32_t c; 121 out[0] = fourP0 + a[0] - b[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26; 122 out[1] = fourP13579 + a[1] - b[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25; 123 out[2] = fourP2468 + a[2] - b[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26; 124 out[3] = fourP13579 + a[3] - b[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25; 125 out[4] = fourP2468 + a[4] - b[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26; 126 out[5] = fourP13579 + a[5] - b[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25; 127 out[6] = fourP2468 + a[6] - b[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26; 128 out[7] = fourP13579 + a[7] - b[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25; 129 out[8] = fourP2468 + a[8] - b[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26; 130 out[9] = fourP13579 + a[9] - b[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25; 131 out[0] += 19 * c; 132 } 133 134 /* out = -a */ 135 DONNA_INLINE static void 136 curve25519_neg(bignum25519 out, const bignum25519 a) { 137 uint32_t c; 138 out[0] = twoP0 - a[0] ; c = (out[0] >> 26); out[0] &= reduce_mask_26; 139 out[1] = twoP13579 - a[1] + c; c = (out[1] >> 25); out[1] &= reduce_mask_25; 140 out[2] = twoP2468 - a[2] + c; c = (out[2] >> 26); out[2] &= reduce_mask_26; 141 out[3] = twoP13579 - a[3] + c; c = (out[3] >> 25); out[3] &= reduce_mask_25; 142 out[4] = twoP2468 - a[4] + c; c = (out[4] >> 26); out[4] &= reduce_mask_26; 143 out[5] = twoP13579 - a[5] + c; c = (out[5] >> 25); out[5] &= reduce_mask_25; 144 out[6] = twoP2468 - a[6] + c; c = (out[6] >> 26); out[6] &= reduce_mask_26; 145 out[7] = twoP13579 - a[7] + c; c = (out[7] >> 25); out[7] &= reduce_mask_25; 146 out[8] = twoP2468 - a[8] + c; c = (out[8] >> 26); out[8] &= reduce_mask_26; 147 out[9] = twoP13579 - a[9] + c; c = (out[9] >> 25); out[9] &= reduce_mask_25; 148 out[0] += 19 * c; 149 } 150 151 /* out = a * b */ 152 #define curve25519_mul_noinline curve25519_mul 153 static void 154 curve25519_mul(bignum25519 out, const bignum25519 a, const bignum25519 b) { 155 uint32_t r0,r1,r2,r3,r4,r5,r6,r7,r8,r9; 156 uint32_t s0,s1,s2,s3,s4,s5,s6,s7,s8,s9; 157 uint64_t m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,c; 158 uint32_t p; 159 160 r0 = b[0]; 161 r1 = b[1]; 162 r2 = b[2]; 163 r3 = b[3]; 164 r4 = b[4]; 165 r5 = b[5]; 166 r6 = b[6]; 167 r7 = b[7]; 168 r8 = b[8]; 169 r9 = b[9]; 170 171 s0 = a[0]; 172 s1 = a[1]; 173 s2 = a[2]; 174 s3 = a[3]; 175 s4 = a[4]; 176 s5 = a[5]; 177 s6 = a[6]; 178 s7 = a[7]; 179 s8 = a[8]; 180 s9 = a[9]; 181 182 m1 = mul32x32_64(r0, s1) + mul32x32_64(r1, s0); 183 m3 = mul32x32_64(r0, s3) + mul32x32_64(r1, s2) + mul32x32_64(r2, s1) + mul32x32_64(r3, s0); 184 m5 = mul32x32_64(r0, s5) + mul32x32_64(r1, s4) + mul32x32_64(r2, s3) + mul32x32_64(r3, s2) + mul32x32_64(r4, s1) + mul32x32_64(r5, s0); 185 m7 = mul32x32_64(r0, s7) + mul32x32_64(r1, s6) + mul32x32_64(r2, s5) + mul32x32_64(r3, s4) + mul32x32_64(r4, s3) + mul32x32_64(r5, s2) + mul32x32_64(r6, s1) + mul32x32_64(r7, s0); 186 m9 = mul32x32_64(r0, s9) + mul32x32_64(r1, s8) + mul32x32_64(r2, s7) + mul32x32_64(r3, s6) + mul32x32_64(r4, s5) + mul32x32_64(r5, s4) + mul32x32_64(r6, s3) + mul32x32_64(r7, s2) + mul32x32_64(r8, s1) + mul32x32_64(r9, s0); 187 188 r1 *= 2; 189 r3 *= 2; 190 r5 *= 2; 191 r7 *= 2; 192 193 m0 = mul32x32_64(r0, s0); 194 m2 = mul32x32_64(r0, s2) + mul32x32_64(r1, s1) + mul32x32_64(r2, s0); 195 m4 = mul32x32_64(r0, s4) + mul32x32_64(r1, s3) + mul32x32_64(r2, s2) + mul32x32_64(r3, s1) + mul32x32_64(r4, s0); 196 m6 = mul32x32_64(r0, s6) + mul32x32_64(r1, s5) + mul32x32_64(r2, s4) + mul32x32_64(r3, s3) + mul32x32_64(r4, s2) + mul32x32_64(r5, s1) + mul32x32_64(r6, s0); 197 m8 = mul32x32_64(r0, s8) + mul32x32_64(r1, s7) + mul32x32_64(r2, s6) + mul32x32_64(r3, s5) + mul32x32_64(r4, s4) + mul32x32_64(r5, s3) + mul32x32_64(r6, s2) + mul32x32_64(r7, s1) + mul32x32_64(r8, s0); 198 199 r1 *= 19; 200 r2 *= 19; 201 r3 = (r3 / 2) * 19; 202 r4 *= 19; 203 r5 = (r5 / 2) * 19; 204 r6 *= 19; 205 r7 = (r7 / 2) * 19; 206 r8 *= 19; 207 r9 *= 19; 208 209 m1 += (mul32x32_64(r9, s2) + mul32x32_64(r8, s3) + mul32x32_64(r7, s4) + mul32x32_64(r6, s5) + mul32x32_64(r5, s6) + mul32x32_64(r4, s7) + mul32x32_64(r3, s8) + mul32x32_64(r2, s9)); 210 m3 += (mul32x32_64(r9, s4) + mul32x32_64(r8, s5) + mul32x32_64(r7, s6) + mul32x32_64(r6, s7) + mul32x32_64(r5, s8) + mul32x32_64(r4, s9)); 211 m5 += (mul32x32_64(r9, s6) + mul32x32_64(r8, s7) + mul32x32_64(r7, s8) + mul32x32_64(r6, s9)); 212 m7 += (mul32x32_64(r9, s8) + mul32x32_64(r8, s9)); 213 214 r3 *= 2; 215 r5 *= 2; 216 r7 *= 2; 217 r9 *= 2; 218 219 m0 += (mul32x32_64(r9, s1) + mul32x32_64(r8, s2) + mul32x32_64(r7, s3) + mul32x32_64(r6, s4) + mul32x32_64(r5, s5) + mul32x32_64(r4, s6) + mul32x32_64(r3, s7) + mul32x32_64(r2, s8) + mul32x32_64(r1, s9)); 220 m2 += (mul32x32_64(r9, s3) + mul32x32_64(r8, s4) + mul32x32_64(r7, s5) + mul32x32_64(r6, s6) + mul32x32_64(r5, s7) + mul32x32_64(r4, s8) + mul32x32_64(r3, s9)); 221 m4 += (mul32x32_64(r9, s5) + mul32x32_64(r8, s6) + mul32x32_64(r7, s7) + mul32x32_64(r6, s8) + mul32x32_64(r5, s9)); 222 m6 += (mul32x32_64(r9, s7) + mul32x32_64(r8, s8) + mul32x32_64(r7, s9)); 223 m8 += (mul32x32_64(r9, s9)); 224 225 r0 = (uint32_t)m0 & reduce_mask_26; c = (m0 >> 26); 226 m1 += c; r1 = (uint32_t)m1 & reduce_mask_25; c = (m1 >> 25); 227 m2 += c; r2 = (uint32_t)m2 & reduce_mask_26; c = (m2 >> 26); 228 m3 += c; r3 = (uint32_t)m3 & reduce_mask_25; c = (m3 >> 25); 229 m4 += c; r4 = (uint32_t)m4 & reduce_mask_26; c = (m4 >> 26); 230 m5 += c; r5 = (uint32_t)m5 & reduce_mask_25; c = (m5 >> 25); 231 m6 += c; r6 = (uint32_t)m6 & reduce_mask_26; c = (m6 >> 26); 232 m7 += c; r7 = (uint32_t)m7 & reduce_mask_25; c = (m7 >> 25); 233 m8 += c; r8 = (uint32_t)m8 & reduce_mask_26; c = (m8 >> 26); 234 m9 += c; r9 = (uint32_t)m9 & reduce_mask_25; p = (uint32_t)(m9 >> 25); 235 m0 = r0 + mul32x32_64(p,19); r0 = (uint32_t)m0 & reduce_mask_26; p = (uint32_t)(m0 >> 26); 236 r1 += p; 237 238 out[0] = r0; 239 out[1] = r1; 240 out[2] = r2; 241 out[3] = r3; 242 out[4] = r4; 243 out[5] = r5; 244 out[6] = r6; 245 out[7] = r7; 246 out[8] = r8; 247 out[9] = r9; 248 } 249 250 /* out = in*in */ 251 static void 252 curve25519_square(bignum25519 out, const bignum25519 in) { 253 uint32_t r0,r1,r2,r3,r4,r5,r6,r7,r8,r9; 254 uint32_t d6,d7,d8,d9; 255 uint64_t m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,c; 256 uint32_t p; 257 258 r0 = in[0]; 259 r1 = in[1]; 260 r2 = in[2]; 261 r3 = in[3]; 262 r4 = in[4]; 263 r5 = in[5]; 264 r6 = in[6]; 265 r7 = in[7]; 266 r8 = in[8]; 267 r9 = in[9]; 268 269 m0 = mul32x32_64(r0, r0); 270 r0 *= 2; 271 m1 = mul32x32_64(r0, r1); 272 m2 = mul32x32_64(r0, r2) + mul32x32_64(r1, r1 * 2); 273 r1 *= 2; 274 m3 = mul32x32_64(r0, r3) + mul32x32_64(r1, r2 ); 275 m4 = mul32x32_64(r0, r4) + mul32x32_64(r1, r3 * 2) + mul32x32_64(r2, r2); 276 r2 *= 2; 277 m5 = mul32x32_64(r0, r5) + mul32x32_64(r1, r4 ) + mul32x32_64(r2, r3); 278 m6 = mul32x32_64(r0, r6) + mul32x32_64(r1, r5 * 2) + mul32x32_64(r2, r4) + mul32x32_64(r3, r3 * 2); 279 r3 *= 2; 280 m7 = mul32x32_64(r0, r7) + mul32x32_64(r1, r6 ) + mul32x32_64(r2, r5) + mul32x32_64(r3, r4 ); 281 m8 = mul32x32_64(r0, r8) + mul32x32_64(r1, r7 * 2) + mul32x32_64(r2, r6) + mul32x32_64(r3, r5 * 2) + mul32x32_64(r4, r4 ); 282 m9 = mul32x32_64(r0, r9) + mul32x32_64(r1, r8 ) + mul32x32_64(r2, r7) + mul32x32_64(r3, r6 ) + mul32x32_64(r4, r5 * 2); 283 284 d6 = r6 * 19; 285 d7 = r7 * 2 * 19; 286 d8 = r8 * 19; 287 d9 = r9 * 2 * 19; 288 289 m0 += (mul32x32_64(d9, r1 ) + mul32x32_64(d8, r2 ) + mul32x32_64(d7, r3 ) + mul32x32_64(d6, r4 * 2) + mul32x32_64(r5, r5 * 2 * 19)); 290 m1 += (mul32x32_64(d9, r2 / 2) + mul32x32_64(d8, r3 ) + mul32x32_64(d7, r4 ) + mul32x32_64(d6, r5 * 2)); 291 m2 += (mul32x32_64(d9, r3 ) + mul32x32_64(d8, r4 * 2) + mul32x32_64(d7, r5 * 2) + mul32x32_64(d6, r6 )); 292 m3 += (mul32x32_64(d9, r4 ) + mul32x32_64(d8, r5 * 2) + mul32x32_64(d7, r6 )); 293 m4 += (mul32x32_64(d9, r5 * 2) + mul32x32_64(d8, r6 * 2) + mul32x32_64(d7, r7 )); 294 m5 += (mul32x32_64(d9, r6 ) + mul32x32_64(d8, r7 * 2)); 295 m6 += (mul32x32_64(d9, r7 * 2) + mul32x32_64(d8, r8 )); 296 m7 += (mul32x32_64(d9, r8 )); 297 m8 += (mul32x32_64(d9, r9 )); 298 299 r0 = (uint32_t)m0 & reduce_mask_26; c = (m0 >> 26); 300 m1 += c; r1 = (uint32_t)m1 & reduce_mask_25; c = (m1 >> 25); 301 m2 += c; r2 = (uint32_t)m2 & reduce_mask_26; c = (m2 >> 26); 302 m3 += c; r3 = (uint32_t)m3 & reduce_mask_25; c = (m3 >> 25); 303 m4 += c; r4 = (uint32_t)m4 & reduce_mask_26; c = (m4 >> 26); 304 m5 += c; r5 = (uint32_t)m5 & reduce_mask_25; c = (m5 >> 25); 305 m6 += c; r6 = (uint32_t)m6 & reduce_mask_26; c = (m6 >> 26); 306 m7 += c; r7 = (uint32_t)m7 & reduce_mask_25; c = (m7 >> 25); 307 m8 += c; r8 = (uint32_t)m8 & reduce_mask_26; c = (m8 >> 26); 308 m9 += c; r9 = (uint32_t)m9 & reduce_mask_25; p = (uint32_t)(m9 >> 25); 309 m0 = r0 + mul32x32_64(p,19); r0 = (uint32_t)m0 & reduce_mask_26; p = (uint32_t)(m0 >> 26); 310 r1 += p; 311 312 out[0] = r0; 313 out[1] = r1; 314 out[2] = r2; 315 out[3] = r3; 316 out[4] = r4; 317 out[5] = r5; 318 out[6] = r6; 319 out[7] = r7; 320 out[8] = r8; 321 out[9] = r9; 322 } 323 324 325 /* out = in ^ (2 * count) */ 326 static void 327 curve25519_square_times(bignum25519 out, const bignum25519 in, int count) { 328 uint32_t r0,r1,r2,r3,r4,r5,r6,r7,r8,r9; 329 uint32_t d6,d7,d8,d9; 330 uint64_t m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,c; 331 uint32_t p; 332 333 r0 = in[0]; 334 r1 = in[1]; 335 r2 = in[2]; 336 r3 = in[3]; 337 r4 = in[4]; 338 r5 = in[5]; 339 r6 = in[6]; 340 r7 = in[7]; 341 r8 = in[8]; 342 r9 = in[9]; 343 344 do { 345 m0 = mul32x32_64(r0, r0); 346 r0 *= 2; 347 m1 = mul32x32_64(r0, r1); 348 m2 = mul32x32_64(r0, r2) + mul32x32_64(r1, r1 * 2); 349 r1 *= 2; 350 m3 = mul32x32_64(r0, r3) + mul32x32_64(r1, r2 ); 351 m4 = mul32x32_64(r0, r4) + mul32x32_64(r1, r3 * 2) + mul32x32_64(r2, r2); 352 r2 *= 2; 353 m5 = mul32x32_64(r0, r5) + mul32x32_64(r1, r4 ) + mul32x32_64(r2, r3); 354 m6 = mul32x32_64(r0, r6) + mul32x32_64(r1, r5 * 2) + mul32x32_64(r2, r4) + mul32x32_64(r3, r3 * 2); 355 r3 *= 2; 356 m7 = mul32x32_64(r0, r7) + mul32x32_64(r1, r6 ) + mul32x32_64(r2, r5) + mul32x32_64(r3, r4 ); 357 m8 = mul32x32_64(r0, r8) + mul32x32_64(r1, r7 * 2) + mul32x32_64(r2, r6) + mul32x32_64(r3, r5 * 2) + mul32x32_64(r4, r4 ); 358 m9 = mul32x32_64(r0, r9) + mul32x32_64(r1, r8 ) + mul32x32_64(r2, r7) + mul32x32_64(r3, r6 ) + mul32x32_64(r4, r5 * 2); 359 360 d6 = r6 * 19; 361 d7 = r7 * 2 * 19; 362 d8 = r8 * 19; 363 d9 = r9 * 2 * 19; 364 365 m0 += (mul32x32_64(d9, r1 ) + mul32x32_64(d8, r2 ) + mul32x32_64(d7, r3 ) + mul32x32_64(d6, r4 * 2) + mul32x32_64(r5, r5 * 2 * 19)); 366 m1 += (mul32x32_64(d9, r2 / 2) + mul32x32_64(d8, r3 ) + mul32x32_64(d7, r4 ) + mul32x32_64(d6, r5 * 2)); 367 m2 += (mul32x32_64(d9, r3 ) + mul32x32_64(d8, r4 * 2) + mul32x32_64(d7, r5 * 2) + mul32x32_64(d6, r6 )); 368 m3 += (mul32x32_64(d9, r4 ) + mul32x32_64(d8, r5 * 2) + mul32x32_64(d7, r6 )); 369 m4 += (mul32x32_64(d9, r5 * 2) + mul32x32_64(d8, r6 * 2) + mul32x32_64(d7, r7 )); 370 m5 += (mul32x32_64(d9, r6 ) + mul32x32_64(d8, r7 * 2)); 371 m6 += (mul32x32_64(d9, r7 * 2) + mul32x32_64(d8, r8 )); 372 m7 += (mul32x32_64(d9, r8 )); 373 m8 += (mul32x32_64(d9, r9 )); 374 375 r0 = (uint32_t)m0 & reduce_mask_26; c = (m0 >> 26); 376 m1 += c; r1 = (uint32_t)m1 & reduce_mask_25; c = (m1 >> 25); 377 m2 += c; r2 = (uint32_t)m2 & reduce_mask_26; c = (m2 >> 26); 378 m3 += c; r3 = (uint32_t)m3 & reduce_mask_25; c = (m3 >> 25); 379 m4 += c; r4 = (uint32_t)m4 & reduce_mask_26; c = (m4 >> 26); 380 m5 += c; r5 = (uint32_t)m5 & reduce_mask_25; c = (m5 >> 25); 381 m6 += c; r6 = (uint32_t)m6 & reduce_mask_26; c = (m6 >> 26); 382 m7 += c; r7 = (uint32_t)m7 & reduce_mask_25; c = (m7 >> 25); 383 m8 += c; r8 = (uint32_t)m8 & reduce_mask_26; c = (m8 >> 26); 384 m9 += c; r9 = (uint32_t)m9 & reduce_mask_25; p = (uint32_t)(m9 >> 25); 385 m0 = r0 + mul32x32_64(p,19); r0 = (uint32_t)m0 & reduce_mask_26; p = (uint32_t)(m0 >> 26); 386 r1 += p; 387 } while (--count); 388 389 out[0] = r0; 390 out[1] = r1; 391 out[2] = r2; 392 out[3] = r3; 393 out[4] = r4; 394 out[5] = r5; 395 out[6] = r6; 396 out[7] = r7; 397 out[8] = r8; 398 out[9] = r9; 399 } 400 401 /* Take a little-endian, 32-byte number and expand it into polynomial form */ 402 static void 403 curve25519_expand(bignum25519 out, const unsigned char in[32]) { 404 static const union { uint8_t b[2]; uint16_t s; } endian_check = {{1,0}}; 405 uint32_t x0,x1,x2,x3,x4,x5,x6,x7; 406 407 if (endian_check.s == 1) { 408 x0 = *(uint32_t *)(in + 0); 409 x1 = *(uint32_t *)(in + 4); 410 x2 = *(uint32_t *)(in + 8); 411 x3 = *(uint32_t *)(in + 12); 412 x4 = *(uint32_t *)(in + 16); 413 x5 = *(uint32_t *)(in + 20); 414 x6 = *(uint32_t *)(in + 24); 415 x7 = *(uint32_t *)(in + 28); 416 } else { 417 #define F(s) \ 418 ((((uint32_t)in[s + 0]) ) | \ 419 (((uint32_t)in[s + 1]) << 8) | \ 420 (((uint32_t)in[s + 2]) << 16) | \ 421 (((uint32_t)in[s + 3]) << 24)) 422 x0 = F(0); 423 x1 = F(4); 424 x2 = F(8); 425 x3 = F(12); 426 x4 = F(16); 427 x5 = F(20); 428 x6 = F(24); 429 x7 = F(28); 430 #undef F 431 } 432 433 out[0] = ( x0 ) & 0x3ffffff; 434 out[1] = ((((uint64_t)x1 << 32) | x0) >> 26) & 0x1ffffff; 435 out[2] = ((((uint64_t)x2 << 32) | x1) >> 19) & 0x3ffffff; 436 out[3] = ((((uint64_t)x3 << 32) | x2) >> 13) & 0x1ffffff; 437 out[4] = (( x3) >> 6) & 0x3ffffff; 438 out[5] = ( x4 ) & 0x1ffffff; 439 out[6] = ((((uint64_t)x5 << 32) | x4) >> 25) & 0x3ffffff; 440 out[7] = ((((uint64_t)x6 << 32) | x5) >> 19) & 0x1ffffff; 441 out[8] = ((((uint64_t)x7 << 32) | x6) >> 12) & 0x3ffffff; 442 out[9] = (( x7) >> 6) & 0x1ffffff; 443 } 444 445 /* Take a fully reduced polynomial form number and contract it into a 446 * little-endian, 32-byte array 447 */ 448 static void 449 curve25519_contract(unsigned char out[32], const bignum25519 in) { 450 bignum25519 f; 451 curve25519_copy(f, in); 452 453 #define carry_pass() \ 454 f[1] += f[0] >> 26; f[0] &= reduce_mask_26; \ 455 f[2] += f[1] >> 25; f[1] &= reduce_mask_25; \ 456 f[3] += f[2] >> 26; f[2] &= reduce_mask_26; \ 457 f[4] += f[3] >> 25; f[3] &= reduce_mask_25; \ 458 f[5] += f[4] >> 26; f[4] &= reduce_mask_26; \ 459 f[6] += f[5] >> 25; f[5] &= reduce_mask_25; \ 460 f[7] += f[6] >> 26; f[6] &= reduce_mask_26; \ 461 f[8] += f[7] >> 25; f[7] &= reduce_mask_25; \ 462 f[9] += f[8] >> 26; f[8] &= reduce_mask_26; 463 464 #define carry_pass_full() \ 465 carry_pass() \ 466 f[0] += 19 * (f[9] >> 25); f[9] &= reduce_mask_25; 467 468 #define carry_pass_final() \ 469 carry_pass() \ 470 f[9] &= reduce_mask_25; 471 472 carry_pass_full() 473 carry_pass_full() 474 475 /* now t is between 0 and 2^255-1, properly carried. */ 476 /* case 1: between 0 and 2^255-20. case 2: between 2^255-19 and 2^255-1. */ 477 f[0] += 19; 478 carry_pass_full() 479 480 /* now between 19 and 2^255-1 in both cases, and offset by 19. */ 481 f[0] += (reduce_mask_26 + 1) - 19; 482 f[1] += (reduce_mask_25 + 1) - 1; 483 f[2] += (reduce_mask_26 + 1) - 1; 484 f[3] += (reduce_mask_25 + 1) - 1; 485 f[4] += (reduce_mask_26 + 1) - 1; 486 f[5] += (reduce_mask_25 + 1) - 1; 487 f[6] += (reduce_mask_26 + 1) - 1; 488 f[7] += (reduce_mask_25 + 1) - 1; 489 f[8] += (reduce_mask_26 + 1) - 1; 490 f[9] += (reduce_mask_25 + 1) - 1; 491 492 /* now between 2^255 and 2^256-20, and offset by 2^255. */ 493 carry_pass_final() 494 495 #undef carry_pass 496 #undef carry_full 497 #undef carry_final 498 499 f[1] <<= 2; 500 f[2] <<= 3; 501 f[3] <<= 5; 502 f[4] <<= 6; 503 f[6] <<= 1; 504 f[7] <<= 3; 505 f[8] <<= 4; 506 f[9] <<= 6; 507 508 #define F(i, s) \ 509 out[s+0] |= (unsigned char )(f[i] & 0xff); \ 510 out[s+1] = (unsigned char )((f[i] >> 8) & 0xff); \ 511 out[s+2] = (unsigned char )((f[i] >> 16) & 0xff); \ 512 out[s+3] = (unsigned char )((f[i] >> 24) & 0xff); 513 514 out[0] = 0; 515 out[16] = 0; 516 F(0,0); 517 F(1,3); 518 F(2,6); 519 F(3,9); 520 F(4,12); 521 F(5,16); 522 F(6,19); 523 F(7,22); 524 F(8,25); 525 F(9,28); 526 #undef F 527 } 528 529 530 /* out = (flag) ? in : out */ 531 DONNA_INLINE static void 532 curve25519_move_conditional_bytes(uint8_t out[96], const uint8_t in[96], uint32_t flag) { 533 const uint32_t nb = flag - 1, b = ~nb; 534 const uint32_t *inl = (const uint32_t *)in; 535 uint32_t *outl = (uint32_t *)out; 536 outl[0] = (outl[0] & nb) | (inl[0] & b); 537 outl[1] = (outl[1] & nb) | (inl[1] & b); 538 outl[2] = (outl[2] & nb) | (inl[2] & b); 539 outl[3] = (outl[3] & nb) | (inl[3] & b); 540 outl[4] = (outl[4] & nb) | (inl[4] & b); 541 outl[5] = (outl[5] & nb) | (inl[5] & b); 542 outl[6] = (outl[6] & nb) | (inl[6] & b); 543 outl[7] = (outl[7] & nb) | (inl[7] & b); 544 outl[8] = (outl[8] & nb) | (inl[8] & b); 545 outl[9] = (outl[9] & nb) | (inl[9] & b); 546 outl[10] = (outl[10] & nb) | (inl[10] & b); 547 outl[11] = (outl[11] & nb) | (inl[11] & b); 548 outl[12] = (outl[12] & nb) | (inl[12] & b); 549 outl[13] = (outl[13] & nb) | (inl[13] & b); 550 outl[14] = (outl[14] & nb) | (inl[14] & b); 551 outl[15] = (outl[15] & nb) | (inl[15] & b); 552 outl[16] = (outl[16] & nb) | (inl[16] & b); 553 outl[17] = (outl[17] & nb) | (inl[17] & b); 554 outl[18] = (outl[18] & nb) | (inl[18] & b); 555 outl[19] = (outl[19] & nb) | (inl[19] & b); 556 outl[20] = (outl[20] & nb) | (inl[20] & b); 557 outl[21] = (outl[21] & nb) | (inl[21] & b); 558 outl[22] = (outl[22] & nb) | (inl[22] & b); 559 outl[23] = (outl[23] & nb) | (inl[23] & b); 560 561 } 562 563 /* if (iswap) swap(a, b) */ 564 DONNA_INLINE static void 565 curve25519_swap_conditional(bignum25519 a, bignum25519 b, uint32_t iswap) { 566 const uint32_t swap = (uint32_t)(-(int32_t)iswap); 567 uint32_t x0,x1,x2,x3,x4,x5,x6,x7,x8,x9; 568 569 x0 = swap & (a[0] ^ b[0]); a[0] ^= x0; b[0] ^= x0; 570 x1 = swap & (a[1] ^ b[1]); a[1] ^= x1; b[1] ^= x1; 571 x2 = swap & (a[2] ^ b[2]); a[2] ^= x2; b[2] ^= x2; 572 x3 = swap & (a[3] ^ b[3]); a[3] ^= x3; b[3] ^= x3; 573 x4 = swap & (a[4] ^ b[4]); a[4] ^= x4; b[4] ^= x4; 574 x5 = swap & (a[5] ^ b[5]); a[5] ^= x5; b[5] ^= x5; 575 x6 = swap & (a[6] ^ b[6]); a[6] ^= x6; b[6] ^= x6; 576 x7 = swap & (a[7] ^ b[7]); a[7] ^= x7; b[7] ^= x7; 577 x8 = swap & (a[8] ^ b[8]); a[8] ^= x8; b[8] ^= x8; 578 x9 = swap & (a[9] ^ b[9]); a[9] ^= x9; b[9] ^= x9; 579 }