Mercurial > dropbear
annotate curve25519-donna.c @ 1562:768ebf737aa0 fuzz
merge from main
| author | Matt Johnston <matt@ucc.asn.au> |
|---|---|
| date | Wed, 28 Feb 2018 22:11:39 +0800 |
| parents | 27b9ddb06b09 |
| children |
| rev | line source |
|---|---|
| 848 | 1 /* Copyright 2008, Google Inc. |
| 2 * All rights reserved. | |
| 3 * | |
| 4 * Redistribution and use in source and binary forms, with or without | |
| 5 * modification, are permitted provided that the following conditions are | |
| 6 * met: | |
| 7 * | |
| 8 * * Redistributions of source code must retain the above copyright | |
| 9 * notice, this list of conditions and the following disclaimer. | |
| 10 * * Redistributions in binary form must reproduce the above | |
| 11 * copyright notice, this list of conditions and the following disclaimer | |
| 12 * in the documentation and/or other materials provided with the | |
| 13 * distribution. | |
| 14 * * Neither the name of Google Inc. nor the names of its | |
| 15 * contributors may be used to endorse or promote products derived from | |
| 16 * this software without specific prior written permission. | |
| 17 * | |
| 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
| 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
| 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
| 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
| 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
| 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
| 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
| 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
| 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
| 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
| 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
| 29 * | |
| 30 * curve25519-donna: Curve25519 elliptic curve, public key function | |
| 31 * | |
| 32 * http://code.google.com/p/curve25519-donna/ | |
| 33 * | |
| 34 * Adam Langley <[email protected]> | |
| 35 * | |
| 36 * Derived from public domain C code by Daniel J. Bernstein <[email protected]> | |
| 37 * | |
| 38 * More information about curve25519 can be found here | |
| 39 * http://cr.yp.to/ecdh.html | |
| 40 * | |
| 41 * djb's sample implementation of curve25519 is written in a special assembly | |
| 42 * language called qhasm and uses the floating point registers. | |
| 43 * | |
| 44 * This is, almost, a clean room reimplementation from the curve25519 paper. It | |
| 45 * uses many of the tricks described therein. Only the crecip function is taken | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
46 * from the sample implementation. */ |
| 848 | 47 |
| 48 #include <string.h> | |
| 49 #include <stdint.h> | |
| 50 | |
| 51 #ifdef _MSC_VER | |
| 52 #define inline __inline | |
| 53 #endif | |
| 54 | |
| 55 typedef uint8_t u8; | |
| 56 typedef int32_t s32; | |
| 57 typedef int64_t limb; | |
| 58 | |
| 59 /* Field element representation: | |
| 60 * | |
| 61 * Field elements are written as an array of signed, 64-bit limbs, least | |
| 62 * significant first. The value of the field element is: | |
| 63 * x[0] + 2^26·x[1] + x^51·x[2] + 2^102·x[3] + ... | |
| 64 * | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
65 * i.e. the limbs are 26, 25, 26, 25, ... bits wide. */ |
| 848 | 66 |
| 67 /* Sum two numbers: output += in */ | |
| 68 static void fsum(limb *output, const limb *in) { | |
| 69 unsigned i; | |
| 70 for (i = 0; i < 10; i += 2) { | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
71 output[0+i] = output[0+i] + in[0+i]; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
72 output[1+i] = output[1+i] + in[1+i]; |
| 848 | 73 } |
| 74 } | |
| 75 | |
| 76 /* Find the difference of two numbers: output = in - output | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
77 * (note the order of the arguments!). */ |
| 848 | 78 static void fdifference(limb *output, const limb *in) { |
| 79 unsigned i; | |
| 80 for (i = 0; i < 10; ++i) { | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
81 output[i] = in[i] - output[i]; |
| 848 | 82 } |
| 83 } | |
| 84 | |
| 85 /* Multiply a number by a scalar: output = in * scalar */ | |
| 86 static void fscalar_product(limb *output, const limb *in, const limb scalar) { | |
| 87 unsigned i; | |
| 88 for (i = 0; i < 10; ++i) { | |
| 89 output[i] = in[i] * scalar; | |
| 90 } | |
| 91 } | |
| 92 | |
| 93 /* Multiply two numbers: output = in2 * in | |
| 94 * | |
| 95 * output must be distinct to both inputs. The inputs are reduced coefficient | |
| 96 * form, the output is not. | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
97 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
98 * output[x] <= 14 * the largest product of the input limbs. */ |
| 848 | 99 static void fproduct(limb *output, const limb *in2, const limb *in) { |
| 100 output[0] = ((limb) ((s32) in2[0])) * ((s32) in[0]); | |
| 101 output[1] = ((limb) ((s32) in2[0])) * ((s32) in[1]) + | |
| 102 ((limb) ((s32) in2[1])) * ((s32) in[0]); | |
| 103 output[2] = 2 * ((limb) ((s32) in2[1])) * ((s32) in[1]) + | |
| 104 ((limb) ((s32) in2[0])) * ((s32) in[2]) + | |
| 105 ((limb) ((s32) in2[2])) * ((s32) in[0]); | |
| 106 output[3] = ((limb) ((s32) in2[1])) * ((s32) in[2]) + | |
| 107 ((limb) ((s32) in2[2])) * ((s32) in[1]) + | |
| 108 ((limb) ((s32) in2[0])) * ((s32) in[3]) + | |
| 109 ((limb) ((s32) in2[3])) * ((s32) in[0]); | |
| 110 output[4] = ((limb) ((s32) in2[2])) * ((s32) in[2]) + | |
| 111 2 * (((limb) ((s32) in2[1])) * ((s32) in[3]) + | |
| 112 ((limb) ((s32) in2[3])) * ((s32) in[1])) + | |
| 113 ((limb) ((s32) in2[0])) * ((s32) in[4]) + | |
| 114 ((limb) ((s32) in2[4])) * ((s32) in[0]); | |
| 115 output[5] = ((limb) ((s32) in2[2])) * ((s32) in[3]) + | |
| 116 ((limb) ((s32) in2[3])) * ((s32) in[2]) + | |
| 117 ((limb) ((s32) in2[1])) * ((s32) in[4]) + | |
| 118 ((limb) ((s32) in2[4])) * ((s32) in[1]) + | |
| 119 ((limb) ((s32) in2[0])) * ((s32) in[5]) + | |
| 120 ((limb) ((s32) in2[5])) * ((s32) in[0]); | |
| 121 output[6] = 2 * (((limb) ((s32) in2[3])) * ((s32) in[3]) + | |
| 122 ((limb) ((s32) in2[1])) * ((s32) in[5]) + | |
| 123 ((limb) ((s32) in2[5])) * ((s32) in[1])) + | |
| 124 ((limb) ((s32) in2[2])) * ((s32) in[4]) + | |
| 125 ((limb) ((s32) in2[4])) * ((s32) in[2]) + | |
| 126 ((limb) ((s32) in2[0])) * ((s32) in[6]) + | |
| 127 ((limb) ((s32) in2[6])) * ((s32) in[0]); | |
| 128 output[7] = ((limb) ((s32) in2[3])) * ((s32) in[4]) + | |
| 129 ((limb) ((s32) in2[4])) * ((s32) in[3]) + | |
| 130 ((limb) ((s32) in2[2])) * ((s32) in[5]) + | |
| 131 ((limb) ((s32) in2[5])) * ((s32) in[2]) + | |
| 132 ((limb) ((s32) in2[1])) * ((s32) in[6]) + | |
| 133 ((limb) ((s32) in2[6])) * ((s32) in[1]) + | |
| 134 ((limb) ((s32) in2[0])) * ((s32) in[7]) + | |
| 135 ((limb) ((s32) in2[7])) * ((s32) in[0]); | |
| 136 output[8] = ((limb) ((s32) in2[4])) * ((s32) in[4]) + | |
| 137 2 * (((limb) ((s32) in2[3])) * ((s32) in[5]) + | |
| 138 ((limb) ((s32) in2[5])) * ((s32) in[3]) + | |
| 139 ((limb) ((s32) in2[1])) * ((s32) in[7]) + | |
| 140 ((limb) ((s32) in2[7])) * ((s32) in[1])) + | |
| 141 ((limb) ((s32) in2[2])) * ((s32) in[6]) + | |
| 142 ((limb) ((s32) in2[6])) * ((s32) in[2]) + | |
| 143 ((limb) ((s32) in2[0])) * ((s32) in[8]) + | |
| 144 ((limb) ((s32) in2[8])) * ((s32) in[0]); | |
| 145 output[9] = ((limb) ((s32) in2[4])) * ((s32) in[5]) + | |
| 146 ((limb) ((s32) in2[5])) * ((s32) in[4]) + | |
| 147 ((limb) ((s32) in2[3])) * ((s32) in[6]) + | |
| 148 ((limb) ((s32) in2[6])) * ((s32) in[3]) + | |
| 149 ((limb) ((s32) in2[2])) * ((s32) in[7]) + | |
| 150 ((limb) ((s32) in2[7])) * ((s32) in[2]) + | |
| 151 ((limb) ((s32) in2[1])) * ((s32) in[8]) + | |
| 152 ((limb) ((s32) in2[8])) * ((s32) in[1]) + | |
| 153 ((limb) ((s32) in2[0])) * ((s32) in[9]) + | |
| 154 ((limb) ((s32) in2[9])) * ((s32) in[0]); | |
| 155 output[10] = 2 * (((limb) ((s32) in2[5])) * ((s32) in[5]) + | |
| 156 ((limb) ((s32) in2[3])) * ((s32) in[7]) + | |
| 157 ((limb) ((s32) in2[7])) * ((s32) in[3]) + | |
| 158 ((limb) ((s32) in2[1])) * ((s32) in[9]) + | |
| 159 ((limb) ((s32) in2[9])) * ((s32) in[1])) + | |
| 160 ((limb) ((s32) in2[4])) * ((s32) in[6]) + | |
| 161 ((limb) ((s32) in2[6])) * ((s32) in[4]) + | |
| 162 ((limb) ((s32) in2[2])) * ((s32) in[8]) + | |
| 163 ((limb) ((s32) in2[8])) * ((s32) in[2]); | |
| 164 output[11] = ((limb) ((s32) in2[5])) * ((s32) in[6]) + | |
| 165 ((limb) ((s32) in2[6])) * ((s32) in[5]) + | |
| 166 ((limb) ((s32) in2[4])) * ((s32) in[7]) + | |
| 167 ((limb) ((s32) in2[7])) * ((s32) in[4]) + | |
| 168 ((limb) ((s32) in2[3])) * ((s32) in[8]) + | |
| 169 ((limb) ((s32) in2[8])) * ((s32) in[3]) + | |
| 170 ((limb) ((s32) in2[2])) * ((s32) in[9]) + | |
| 171 ((limb) ((s32) in2[9])) * ((s32) in[2]); | |
| 172 output[12] = ((limb) ((s32) in2[6])) * ((s32) in[6]) + | |
| 173 2 * (((limb) ((s32) in2[5])) * ((s32) in[7]) + | |
| 174 ((limb) ((s32) in2[7])) * ((s32) in[5]) + | |
| 175 ((limb) ((s32) in2[3])) * ((s32) in[9]) + | |
| 176 ((limb) ((s32) in2[9])) * ((s32) in[3])) + | |
| 177 ((limb) ((s32) in2[4])) * ((s32) in[8]) + | |
| 178 ((limb) ((s32) in2[8])) * ((s32) in[4]); | |
| 179 output[13] = ((limb) ((s32) in2[6])) * ((s32) in[7]) + | |
| 180 ((limb) ((s32) in2[7])) * ((s32) in[6]) + | |
| 181 ((limb) ((s32) in2[5])) * ((s32) in[8]) + | |
| 182 ((limb) ((s32) in2[8])) * ((s32) in[5]) + | |
| 183 ((limb) ((s32) in2[4])) * ((s32) in[9]) + | |
| 184 ((limb) ((s32) in2[9])) * ((s32) in[4]); | |
| 185 output[14] = 2 * (((limb) ((s32) in2[7])) * ((s32) in[7]) + | |
| 186 ((limb) ((s32) in2[5])) * ((s32) in[9]) + | |
| 187 ((limb) ((s32) in2[9])) * ((s32) in[5])) + | |
| 188 ((limb) ((s32) in2[6])) * ((s32) in[8]) + | |
| 189 ((limb) ((s32) in2[8])) * ((s32) in[6]); | |
| 190 output[15] = ((limb) ((s32) in2[7])) * ((s32) in[8]) + | |
| 191 ((limb) ((s32) in2[8])) * ((s32) in[7]) + | |
| 192 ((limb) ((s32) in2[6])) * ((s32) in[9]) + | |
| 193 ((limb) ((s32) in2[9])) * ((s32) in[6]); | |
| 194 output[16] = ((limb) ((s32) in2[8])) * ((s32) in[8]) + | |
| 195 2 * (((limb) ((s32) in2[7])) * ((s32) in[9]) + | |
| 196 ((limb) ((s32) in2[9])) * ((s32) in[7])); | |
| 197 output[17] = ((limb) ((s32) in2[8])) * ((s32) in[9]) + | |
| 198 ((limb) ((s32) in2[9])) * ((s32) in[8]); | |
| 199 output[18] = 2 * ((limb) ((s32) in2[9])) * ((s32) in[9]); | |
| 200 } | |
| 201 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
202 /* Reduce a long form to a short form by taking the input mod 2^255 - 19. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
203 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
204 * On entry: |output[i]| < 14*2^54 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
205 * On exit: |output[0..8]| < 280*2^54 */ |
| 848 | 206 static void freduce_degree(limb *output) { |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
207 /* Each of these shifts and adds ends up multiplying the value by 19. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
208 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
209 * For output[0..8], the absolute entry value is < 14*2^54 and we add, at |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
210 * most, 19*14*2^54 thus, on exit, |output[0..8]| < 280*2^54. */ |
| 848 | 211 output[8] += output[18] << 4; |
| 212 output[8] += output[18] << 1; | |
| 213 output[8] += output[18]; | |
| 214 output[7] += output[17] << 4; | |
| 215 output[7] += output[17] << 1; | |
| 216 output[7] += output[17]; | |
| 217 output[6] += output[16] << 4; | |
| 218 output[6] += output[16] << 1; | |
| 219 output[6] += output[16]; | |
| 220 output[5] += output[15] << 4; | |
| 221 output[5] += output[15] << 1; | |
| 222 output[5] += output[15]; | |
| 223 output[4] += output[14] << 4; | |
| 224 output[4] += output[14] << 1; | |
| 225 output[4] += output[14]; | |
| 226 output[3] += output[13] << 4; | |
| 227 output[3] += output[13] << 1; | |
| 228 output[3] += output[13]; | |
| 229 output[2] += output[12] << 4; | |
| 230 output[2] += output[12] << 1; | |
| 231 output[2] += output[12]; | |
| 232 output[1] += output[11] << 4; | |
| 233 output[1] += output[11] << 1; | |
| 234 output[1] += output[11]; | |
| 235 output[0] += output[10] << 4; | |
| 236 output[0] += output[10] << 1; | |
| 237 output[0] += output[10]; | |
| 238 } | |
| 239 | |
| 240 #if (-1 & 3) != 3 | |
| 241 #error "This code only works on a two's complement system" | |
| 242 #endif | |
| 243 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
244 /* return v / 2^26, using only shifts and adds. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
245 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
246 * On entry: v can take any value. */ |
| 848 | 247 static inline limb |
| 248 div_by_2_26(const limb v) | |
| 249 { | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
250 /* High word of v; no shift needed. */ |
| 848 | 251 const uint32_t highword = (uint32_t) (((uint64_t) v) >> 32); |
| 252 /* Set to all 1s if v was negative; else set to 0s. */ | |
| 253 const int32_t sign = ((int32_t) highword) >> 31; | |
| 254 /* Set to 0x3ffffff if v was negative; else set to 0. */ | |
| 255 const int32_t roundoff = ((uint32_t) sign) >> 6; | |
| 256 /* Should return v / (1<<26) */ | |
| 257 return (v + roundoff) >> 26; | |
| 258 } | |
| 259 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
260 /* return v / (2^25), using only shifts and adds. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
261 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
262 * On entry: v can take any value. */ |
| 848 | 263 static inline limb |
| 264 div_by_2_25(const limb v) | |
| 265 { | |
| 266 /* High word of v; no shift needed*/ | |
| 267 const uint32_t highword = (uint32_t) (((uint64_t) v) >> 32); | |
| 268 /* Set to all 1s if v was negative; else set to 0s. */ | |
| 269 const int32_t sign = ((int32_t) highword) >> 31; | |
| 270 /* Set to 0x1ffffff if v was negative; else set to 0. */ | |
| 271 const int32_t roundoff = ((uint32_t) sign) >> 7; | |
| 272 /* Should return v / (1<<25) */ | |
| 273 return (v + roundoff) >> 25; | |
| 274 } | |
| 275 | |
| 276 /* Reduce all coefficients of the short form input so that |x| < 2^26. | |
| 277 * | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
278 * On entry: |output[i]| < 280*2^54 */ |
| 848 | 279 static void freduce_coefficients(limb *output) { |
| 280 unsigned i; | |
| 281 | |
| 282 output[10] = 0; | |
| 283 | |
| 284 for (i = 0; i < 10; i += 2) { | |
| 285 limb over = div_by_2_26(output[i]); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
286 /* The entry condition (that |output[i]| < 280*2^54) means that over is, at |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
287 * most, 280*2^28 in the first iteration of this loop. This is added to the |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
288 * next limb and we can approximate the resulting bound of that limb by |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
289 * 281*2^54. */ |
| 848 | 290 output[i] -= over << 26; |
| 291 output[i+1] += over; | |
| 292 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
293 /* For the first iteration, |output[i+1]| < 281*2^54, thus |over| < |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
294 * 281*2^29. When this is added to the next limb, the resulting bound can |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
295 * be approximated as 281*2^54. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
296 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
297 * For subsequent iterations of the loop, 281*2^54 remains a conservative |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
298 * bound and no overflow occurs. */ |
| 848 | 299 over = div_by_2_25(output[i+1]); |
| 300 output[i+1] -= over << 25; | |
| 301 output[i+2] += over; | |
| 302 } | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
303 /* Now |output[10]| < 281*2^29 and all other coefficients are reduced. */ |
| 848 | 304 output[0] += output[10] << 4; |
| 305 output[0] += output[10] << 1; | |
| 306 output[0] += output[10]; | |
| 307 | |
| 308 output[10] = 0; | |
| 309 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
310 /* Now output[1..9] are reduced, and |output[0]| < 2^26 + 19*281*2^29 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
311 * So |over| will be no more than 2^16. */ |
| 848 | 312 { |
| 313 limb over = div_by_2_26(output[0]); | |
| 314 output[0] -= over << 26; | |
| 315 output[1] += over; | |
| 316 } | |
| 317 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
318 /* Now output[0,2..9] are reduced, and |output[1]| < 2^25 + 2^16 < 2^26. The |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
319 * bound on |output[1]| is sufficient to meet our needs. */ |
| 848 | 320 } |
| 321 | |
| 322 /* A helpful wrapper around fproduct: output = in * in2. | |
| 323 * | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
324 * On entry: |in[i]| < 2^27 and |in2[i]| < 2^27. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
325 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
326 * output must be distinct to both inputs. The output is reduced degree |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
327 * (indeed, one need only provide storage for 10 limbs) and |output[i]| < 2^26. */ |
| 848 | 328 static void |
| 329 fmul(limb *output, const limb *in, const limb *in2) { | |
| 330 limb t[19]; | |
| 331 fproduct(t, in, in2); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
332 /* |t[i]| < 14*2^54 */ |
| 848 | 333 freduce_degree(t); |
| 334 freduce_coefficients(t); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
335 /* |t[i]| < 2^26 */ |
| 848 | 336 memcpy(output, t, sizeof(limb) * 10); |
| 337 } | |
| 338 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
339 /* Square a number: output = in**2 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
340 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
341 * output must be distinct from the input. The inputs are reduced coefficient |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
342 * form, the output is not. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
343 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
344 * output[x] <= 14 * the largest product of the input limbs. */ |
| 848 | 345 static void fsquare_inner(limb *output, const limb *in) { |
| 346 output[0] = ((limb) ((s32) in[0])) * ((s32) in[0]); | |
| 347 output[1] = 2 * ((limb) ((s32) in[0])) * ((s32) in[1]); | |
| 348 output[2] = 2 * (((limb) ((s32) in[1])) * ((s32) in[1]) + | |
| 349 ((limb) ((s32) in[0])) * ((s32) in[2])); | |
| 350 output[3] = 2 * (((limb) ((s32) in[1])) * ((s32) in[2]) + | |
| 351 ((limb) ((s32) in[0])) * ((s32) in[3])); | |
| 352 output[4] = ((limb) ((s32) in[2])) * ((s32) in[2]) + | |
| 353 4 * ((limb) ((s32) in[1])) * ((s32) in[3]) + | |
| 354 2 * ((limb) ((s32) in[0])) * ((s32) in[4]); | |
| 355 output[5] = 2 * (((limb) ((s32) in[2])) * ((s32) in[3]) + | |
| 356 ((limb) ((s32) in[1])) * ((s32) in[4]) + | |
| 357 ((limb) ((s32) in[0])) * ((s32) in[5])); | |
| 358 output[6] = 2 * (((limb) ((s32) in[3])) * ((s32) in[3]) + | |
| 359 ((limb) ((s32) in[2])) * ((s32) in[4]) + | |
| 360 ((limb) ((s32) in[0])) * ((s32) in[6]) + | |
| 361 2 * ((limb) ((s32) in[1])) * ((s32) in[5])); | |
| 362 output[7] = 2 * (((limb) ((s32) in[3])) * ((s32) in[4]) + | |
| 363 ((limb) ((s32) in[2])) * ((s32) in[5]) + | |
| 364 ((limb) ((s32) in[1])) * ((s32) in[6]) + | |
| 365 ((limb) ((s32) in[0])) * ((s32) in[7])); | |
| 366 output[8] = ((limb) ((s32) in[4])) * ((s32) in[4]) + | |
| 367 2 * (((limb) ((s32) in[2])) * ((s32) in[6]) + | |
| 368 ((limb) ((s32) in[0])) * ((s32) in[8]) + | |
| 369 2 * (((limb) ((s32) in[1])) * ((s32) in[7]) + | |
| 370 ((limb) ((s32) in[3])) * ((s32) in[5]))); | |
| 371 output[9] = 2 * (((limb) ((s32) in[4])) * ((s32) in[5]) + | |
| 372 ((limb) ((s32) in[3])) * ((s32) in[6]) + | |
| 373 ((limb) ((s32) in[2])) * ((s32) in[7]) + | |
| 374 ((limb) ((s32) in[1])) * ((s32) in[8]) + | |
| 375 ((limb) ((s32) in[0])) * ((s32) in[9])); | |
| 376 output[10] = 2 * (((limb) ((s32) in[5])) * ((s32) in[5]) + | |
| 377 ((limb) ((s32) in[4])) * ((s32) in[6]) + | |
| 378 ((limb) ((s32) in[2])) * ((s32) in[8]) + | |
| 379 2 * (((limb) ((s32) in[3])) * ((s32) in[7]) + | |
| 380 ((limb) ((s32) in[1])) * ((s32) in[9]))); | |
| 381 output[11] = 2 * (((limb) ((s32) in[5])) * ((s32) in[6]) + | |
| 382 ((limb) ((s32) in[4])) * ((s32) in[7]) + | |
| 383 ((limb) ((s32) in[3])) * ((s32) in[8]) + | |
| 384 ((limb) ((s32) in[2])) * ((s32) in[9])); | |
| 385 output[12] = ((limb) ((s32) in[6])) * ((s32) in[6]) + | |
| 386 2 * (((limb) ((s32) in[4])) * ((s32) in[8]) + | |
| 387 2 * (((limb) ((s32) in[5])) * ((s32) in[7]) + | |
| 388 ((limb) ((s32) in[3])) * ((s32) in[9]))); | |
| 389 output[13] = 2 * (((limb) ((s32) in[6])) * ((s32) in[7]) + | |
| 390 ((limb) ((s32) in[5])) * ((s32) in[8]) + | |
| 391 ((limb) ((s32) in[4])) * ((s32) in[9])); | |
| 392 output[14] = 2 * (((limb) ((s32) in[7])) * ((s32) in[7]) + | |
| 393 ((limb) ((s32) in[6])) * ((s32) in[8]) + | |
| 394 2 * ((limb) ((s32) in[5])) * ((s32) in[9])); | |
| 395 output[15] = 2 * (((limb) ((s32) in[7])) * ((s32) in[8]) + | |
| 396 ((limb) ((s32) in[6])) * ((s32) in[9])); | |
| 397 output[16] = ((limb) ((s32) in[8])) * ((s32) in[8]) + | |
| 398 4 * ((limb) ((s32) in[7])) * ((s32) in[9]); | |
| 399 output[17] = 2 * ((limb) ((s32) in[8])) * ((s32) in[9]); | |
| 400 output[18] = 2 * ((limb) ((s32) in[9])) * ((s32) in[9]); | |
| 401 } | |
| 402 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
403 /* fsquare sets output = in^2. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
404 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
405 * On entry: The |in| argument is in reduced coefficients form and |in[i]| < |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
406 * 2^27. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
407 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
408 * On exit: The |output| argument is in reduced coefficients form (indeed, one |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
409 * need only provide storage for 10 limbs) and |out[i]| < 2^26. */ |
| 848 | 410 static void |
| 411 fsquare(limb *output, const limb *in) { | |
| 412 limb t[19]; | |
| 413 fsquare_inner(t, in); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
414 /* |t[i]| < 14*2^54 because the largest product of two limbs will be < |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
415 * 2^(27+27) and fsquare_inner adds together, at most, 14 of those |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
416 * products. */ |
| 848 | 417 freduce_degree(t); |
| 418 freduce_coefficients(t); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
419 /* |t[i]| < 2^26 */ |
| 848 | 420 memcpy(output, t, sizeof(limb) * 10); |
| 421 } | |
| 422 | |
| 423 /* Take a little-endian, 32-byte number and expand it into polynomial form */ | |
| 424 static void | |
| 425 fexpand(limb *output, const u8 *input) { | |
| 426 #define F(n,start,shift,mask) \ | |
| 427 output[n] = ((((limb) input[start + 0]) | \ | |
| 428 ((limb) input[start + 1]) << 8 | \ | |
| 429 ((limb) input[start + 2]) << 16 | \ | |
| 430 ((limb) input[start + 3]) << 24) >> shift) & mask; | |
| 431 F(0, 0, 0, 0x3ffffff); | |
| 432 F(1, 3, 2, 0x1ffffff); | |
| 433 F(2, 6, 3, 0x3ffffff); | |
| 434 F(3, 9, 5, 0x1ffffff); | |
| 435 F(4, 12, 6, 0x3ffffff); | |
| 436 F(5, 16, 0, 0x1ffffff); | |
| 437 F(6, 19, 1, 0x3ffffff); | |
| 438 F(7, 22, 3, 0x1ffffff); | |
| 439 F(8, 25, 4, 0x3ffffff); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
440 F(9, 28, 6, 0x1ffffff); |
| 848 | 441 #undef F |
| 442 } | |
| 443 | |
| 444 #if (-32 >> 1) != -16 | |
| 445 #error "This code only works when >> does sign-extension on negative numbers" | |
| 446 #endif | |
| 447 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
448 /* s32_eq returns 0xffffffff iff a == b and zero otherwise. */ |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
449 static s32 s32_eq(s32 a, s32 b) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
450 a = ~(a ^ b); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
451 a &= a << 16; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
452 a &= a << 8; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
453 a &= a << 4; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
454 a &= a << 2; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
455 a &= a << 1; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
456 return a >> 31; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
457 } |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
458 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
459 /* s32_gte returns 0xffffffff if a >= b and zero otherwise, where a and b are |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
460 * both non-negative. */ |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
461 static s32 s32_gte(s32 a, s32 b) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
462 a -= b; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
463 /* a >= 0 iff a >= b. */ |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
464 return ~(a >> 31); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
465 } |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
466 |
| 848 | 467 /* Take a fully reduced polynomial form number and contract it into a |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
468 * little-endian, 32-byte array. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
469 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
470 * On entry: |input_limbs[i]| < 2^26 */ |
| 848 | 471 static void |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
472 fcontract(u8 *output, limb *input_limbs) { |
| 848 | 473 int i; |
| 474 int j; | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
475 s32 input[10]; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
476 s32 mask; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
477 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
478 /* |input_limbs[i]| < 2^26, so it's valid to convert to an s32. */ |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
479 for (i = 0; i < 10; i++) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
480 input[i] = input_limbs[i]; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
481 } |
| 848 | 482 |
| 483 for (j = 0; j < 2; ++j) { | |
| 484 for (i = 0; i < 9; ++i) { | |
| 485 if ((i & 1) == 1) { | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
486 /* This calculation is a time-invariant way to make input[i] |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
487 * non-negative by borrowing from the next-larger limb. */ |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
488 const s32 mask = input[i] >> 31; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
489 const s32 carry = -((input[i] & mask) >> 25); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
490 input[i] = input[i] + (carry << 25); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
491 input[i+1] = input[i+1] - carry; |
| 848 | 492 } else { |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
493 const s32 mask = input[i] >> 31; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
494 const s32 carry = -((input[i] & mask) >> 26); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
495 input[i] = input[i] + (carry << 26); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
496 input[i+1] = input[i+1] - carry; |
| 848 | 497 } |
| 498 } | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
499 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
500 /* There's no greater limb for input[9] to borrow from, but we can multiply |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
501 * by 19 and borrow from input[0], which is valid mod 2^255-19. */ |
| 848 | 502 { |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
503 const s32 mask = input[9] >> 31; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
504 const s32 carry = -((input[9] & mask) >> 25); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
505 input[9] = input[9] + (carry << 25); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
506 input[0] = input[0] - (carry * 19); |
| 848 | 507 } |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
508 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
509 /* After the first iteration, input[1..9] are non-negative and fit within |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
510 * 25 or 26 bits, depending on position. However, input[0] may be |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
511 * negative. */ |
| 848 | 512 } |
| 513 | |
| 514 /* The first borrow-propagation pass above ended with every limb | |
| 515 except (possibly) input[0] non-negative. | |
| 516 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
517 If input[0] was negative after the first pass, then it was because of a |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
518 carry from input[9]. On entry, input[9] < 2^26 so the carry was, at most, |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
519 one, since (2**26-1) >> 25 = 1. Thus input[0] >= -19. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
520 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
521 In the second pass, each limb is decreased by at most one. Thus the second |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
522 borrow-propagation pass could only have wrapped around to decrease |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
523 input[0] again if the first pass left input[0] negative *and* input[1] |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
524 through input[9] were all zero. In that case, input[1] is now 2^25 - 1, |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
525 and this last borrow-propagation step will leave input[1] non-negative. */ |
| 848 | 526 { |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
527 const s32 mask = input[0] >> 31; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
528 const s32 carry = -((input[0] & mask) >> 26); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
529 input[0] = input[0] + (carry << 26); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
530 input[1] = input[1] - carry; |
| 848 | 531 } |
| 532 | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
533 /* All input[i] are now non-negative. However, there might be values between |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
534 * 2^25 and 2^26 in a limb which is, nominally, 25 bits wide. */ |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
535 for (j = 0; j < 2; j++) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
536 for (i = 0; i < 9; i++) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
537 if ((i & 1) == 1) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
538 const s32 carry = input[i] >> 25; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
539 input[i] &= 0x1ffffff; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
540 input[i+1] += carry; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
541 } else { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
542 const s32 carry = input[i] >> 26; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
543 input[i] &= 0x3ffffff; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
544 input[i+1] += carry; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
545 } |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
546 } |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
547 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
548 { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
549 const s32 carry = input[9] >> 25; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
550 input[9] &= 0x1ffffff; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
551 input[0] += 19*carry; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
552 } |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
553 } |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
554 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
555 /* If the first carry-chain pass, just above, ended up with a carry from |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
556 * input[9], and that caused input[0] to be out-of-bounds, then input[0] was |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
557 * < 2^26 + 2*19, because the carry was, at most, two. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
558 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
559 * If the second pass carried from input[9] again then input[0] is < 2*19 and |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
560 * the input[9] -> input[0] carry didn't push input[0] out of bounds. */ |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
561 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
562 /* It still remains the case that input might be between 2^255-19 and 2^255. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
563 * In this case, input[1..9] must take their maximum value and input[0] must |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
564 * be >= (2^255-19) & 0x3ffffff, which is 0x3ffffed. */ |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
565 mask = s32_gte(input[0], 0x3ffffed); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
566 for (i = 1; i < 10; i++) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
567 if ((i & 1) == 1) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
568 mask &= s32_eq(input[i], 0x1ffffff); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
569 } else { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
570 mask &= s32_eq(input[i], 0x3ffffff); |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
571 } |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
572 } |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
573 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
574 /* mask is either 0xffffffff (if input >= 2^255-19) and zero otherwise. Thus |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
575 * this conditionally subtracts 2^255-19. */ |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
576 input[0] -= mask & 0x3ffffed; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
577 |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
578 for (i = 1; i < 10; i++) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
579 if ((i & 1) == 1) { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
580 input[i] -= mask & 0x1ffffff; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
581 } else { |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
582 input[i] -= mask & 0x3ffffff; |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
583 } |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
584 } |
| 848 | 585 |
| 586 input[1] <<= 2; | |
| 587 input[2] <<= 3; | |
| 588 input[3] <<= 5; | |
| 589 input[4] <<= 6; | |
| 590 input[6] <<= 1; | |
| 591 input[7] <<= 3; | |
| 592 input[8] <<= 4; | |
| 593 input[9] <<= 6; | |
| 594 #define F(i, s) \ | |
| 595 output[s+0] |= input[i] & 0xff; \ | |
| 596 output[s+1] = (input[i] >> 8) & 0xff; \ | |
| 597 output[s+2] = (input[i] >> 16) & 0xff; \ | |
| 598 output[s+3] = (input[i] >> 24) & 0xff; | |
| 599 output[0] = 0; | |
| 600 output[16] = 0; | |
| 601 F(0,0); | |
| 602 F(1,3); | |
| 603 F(2,6); | |
| 604 F(3,9); | |
| 605 F(4,12); | |
| 606 F(5,16); | |
| 607 F(6,19); | |
| 608 F(7,22); | |
| 609 F(8,25); | |
| 610 F(9,28); | |
| 611 #undef F | |
| 612 } | |
| 613 | |
| 614 /* Input: Q, Q', Q-Q' | |
| 615 * Output: 2Q, Q+Q' | |
| 616 * | |
| 617 * x2 z3: long form | |
| 618 * x3 z3: long form | |
| 619 * x z: short form, destroyed | |
| 620 * xprime zprime: short form, destroyed | |
| 621 * qmqp: short form, preserved | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
622 * |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
623 * On entry and exit, the absolute value of the limbs of all inputs and outputs |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
624 * are < 2^26. */ |
| 848 | 625 static void fmonty(limb *x2, limb *z2, /* output 2Q */ |
| 626 limb *x3, limb *z3, /* output Q + Q' */ | |
| 627 limb *x, limb *z, /* input Q */ | |
| 628 limb *xprime, limb *zprime, /* input Q' */ | |
| 629 const limb *qmqp /* input Q - Q' */) { | |
| 630 limb origx[10], origxprime[10], zzz[19], xx[19], zz[19], xxprime[19], | |
| 631 zzprime[19], zzzprime[19], xxxprime[19]; | |
| 632 | |
| 633 memcpy(origx, x, 10 * sizeof(limb)); | |
| 634 fsum(x, z); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
635 /* |x[i]| < 2^27 */ |
|
1038
d3925ed45a85
Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents:
848
diff
changeset
|
636 fdifference(z, origx); /* does x - z */ |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
637 /* |z[i]| < 2^27 */ |
| 848 | 638 |
| 639 memcpy(origxprime, xprime, sizeof(limb) * 10); | |
| 640 fsum(xprime, zprime); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
641 /* |xprime[i]| < 2^27 */ |
| 848 | 642 fdifference(zprime, origxprime); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
643 /* |zprime[i]| < 2^27 */ |
| 848 | 644 fproduct(xxprime, xprime, z); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
645 /* |xxprime[i]| < 14*2^54: the largest product of two limbs will be < |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
646 * 2^(27+27) and fproduct adds together, at most, 14 of those products. |
|
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
647 * (Approximating that to 2^58 doesn't work out.) */ |
| 848 | 648 fproduct(zzprime, x, zprime); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
649 /* |zzprime[i]| < 14*2^54 */ |
| 848 | 650 freduce_degree(xxprime); |
| 651 freduce_coefficients(xxprime); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
652 /* |xxprime[i]| < 2^26 */ |
| 848 | 653 freduce_degree(zzprime); |
| 654 freduce_coefficients(zzprime); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
655 /* |zzprime[i]| < 2^26 */ |
| 848 | 656 memcpy(origxprime, xxprime, sizeof(limb) * 10); |
| 657 fsum(xxprime, zzprime); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
658 /* |xxprime[i]| < 2^27 */ |
| 848 | 659 fdifference(zzprime, origxprime); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
660 /* |zzprime[i]| < 2^27 */ |
| 848 | 661 fsquare(xxxprime, xxprime); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
662 /* |xxxprime[i]| < 2^26 */ |
| 848 | 663 fsquare(zzzprime, zzprime); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
664 /* |zzzprime[i]| < 2^26 */ |
| 848 | 665 fproduct(zzprime, zzzprime, qmqp); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
666 /* |zzprime[i]| < 14*2^52 */ |
| 848 | 667 freduce_degree(zzprime); |
| 668 freduce_coefficients(zzprime); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
669 /* |zzprime[i]| < 2^26 */ |
| 848 | 670 memcpy(x3, xxxprime, sizeof(limb) * 10); |
| 671 memcpy(z3, zzprime, sizeof(limb) * 10); | |
| 672 | |
| 673 fsquare(xx, x); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
674 /* |xx[i]| < 2^26 */ |
| 848 | 675 fsquare(zz, z); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
676 /* |zz[i]| < 2^26 */ |
| 848 | 677 fproduct(x2, xx, zz); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
678 /* |x2[i]| < 14*2^52 */ |
| 848 | 679 freduce_degree(x2); |
| 680 freduce_coefficients(x2); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
681 /* |x2[i]| < 2^26 */ |
|
1038
d3925ed45a85
Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents:
848
diff
changeset
|
682 fdifference(zz, xx); /* does zz = xx - zz */ |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
683 /* |zz[i]| < 2^27 */ |
| 848 | 684 memset(zzz + 10, 0, sizeof(limb) * 9); |
| 685 fscalar_product(zzz, zz, 121665); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
686 /* |zzz[i]| < 2^(27+17) */ |
| 848 | 687 /* No need to call freduce_degree here: |
| 688 fscalar_product doesn't increase the degree of its input. */ | |
| 689 freduce_coefficients(zzz); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
690 /* |zzz[i]| < 2^26 */ |
| 848 | 691 fsum(zzz, xx); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
692 /* |zzz[i]| < 2^27 */ |
| 848 | 693 fproduct(z2, zz, zzz); |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
694 /* |z2[i]| < 14*2^(26+27) */ |
| 848 | 695 freduce_degree(z2); |
| 696 freduce_coefficients(z2); | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
697 /* |z2|i| < 2^26 */ |
| 848 | 698 } |
| 699 | |
| 700 /* Conditionally swap two reduced-form limb arrays if 'iswap' is 1, but leave | |
| 701 * them unchanged if 'iswap' is 0. Runs in data-invariant time to avoid | |
| 702 * side-channel attacks. | |
| 703 * | |
| 704 * NOTE that this function requires that 'iswap' be 1 or 0; other values give | |
| 705 * wrong results. Also, the two limb arrays must be in reduced-coefficient, | |
| 706 * reduced-degree form: the values in a[10..19] or b[10..19] aren't swapped, | |
| 707 * and all all values in a[0..9],b[0..9] must have magnitude less than | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
708 * INT32_MAX. */ |
| 848 | 709 static void |
| 710 swap_conditional(limb a[19], limb b[19], limb iswap) { | |
| 711 unsigned i; | |
| 712 const s32 swap = (s32) -iswap; | |
| 713 | |
| 714 for (i = 0; i < 10; ++i) { | |
| 715 const s32 x = swap & ( ((s32)a[i]) ^ ((s32)b[i]) ); | |
| 716 a[i] = ((s32)a[i]) ^ x; | |
| 717 b[i] = ((s32)b[i]) ^ x; | |
| 718 } | |
| 719 } | |
| 720 | |
| 721 /* Calculates nQ where Q is the x-coordinate of a point on the curve | |
| 722 * | |
| 723 * resultx/resultz: the x coordinate of the resulting curve point (short form) | |
| 724 * n: a little endian, 32-byte number | |
|
1434
27b9ddb06b09
Update curve25519-donna to f7837adf95a2c2dcc36233cb02a1fb34081c0c4a
Matt Johnston <matt@ucc.asn.au>
parents:
1038
diff
changeset
|
725 * q: a point of the curve (short form) */ |
| 848 | 726 static void |
| 727 cmult(limb *resultx, limb *resultz, const u8 *n, const limb *q) { | |
| 728 limb a[19] = {0}, b[19] = {1}, c[19] = {1}, d[19] = {0}; | |
| 729 limb *nqpqx = a, *nqpqz = b, *nqx = c, *nqz = d, *t; | |
| 730 limb e[19] = {0}, f[19] = {1}, g[19] = {0}, h[19] = {1}; | |
| 731 limb *nqpqx2 = e, *nqpqz2 = f, *nqx2 = g, *nqz2 = h; | |
| 732 | |
| 733 unsigned i, j; | |
| 734 | |
| 735 memcpy(nqpqx, q, sizeof(limb) * 10); | |
| 736 | |
| 737 for (i = 0; i < 32; ++i) { | |
| 738 u8 byte = n[31 - i]; | |
| 739 for (j = 0; j < 8; ++j) { | |
| 740 const limb bit = byte >> 7; | |
| 741 | |
| 742 swap_conditional(nqx, nqpqx, bit); | |
| 743 swap_conditional(nqz, nqpqz, bit); | |
| 744 fmonty(nqx2, nqz2, | |
| 745 nqpqx2, nqpqz2, | |
| 746 nqx, nqz, | |
| 747 nqpqx, nqpqz, | |
| 748 q); | |
| 749 swap_conditional(nqx2, nqpqx2, bit); | |
| 750 swap_conditional(nqz2, nqpqz2, bit); | |
| 751 | |
| 752 t = nqx; | |
| 753 nqx = nqx2; | |
| 754 nqx2 = t; | |
| 755 t = nqz; | |
| 756 nqz = nqz2; | |
| 757 nqz2 = t; | |
| 758 t = nqpqx; | |
| 759 nqpqx = nqpqx2; | |
| 760 nqpqx2 = t; | |
| 761 t = nqpqz; | |
| 762 nqpqz = nqpqz2; | |
| 763 nqpqz2 = t; | |
| 764 | |
| 765 byte <<= 1; | |
| 766 } | |
| 767 } | |
| 768 | |
| 769 memcpy(resultx, nqx, sizeof(limb) * 10); | |
| 770 memcpy(resultz, nqz, sizeof(limb) * 10); | |
| 771 } | |
| 772 | |
|
1038
d3925ed45a85
Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents:
848
diff
changeset
|
773 /* ----------------------------------------------------------------------------- |
|
d3925ed45a85
Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents:
848
diff
changeset
|
774 * Shamelessly copied from djb's code |
|
d3925ed45a85
Fix for old compilers, variable declarations at beginning of functions
Thorsten Horstmann <thorsten.horstmann@web.de>
parents:
848
diff
changeset
|
775 * ----------------------------------------------------------------------------- */ |
| 848 | 776 static void |
| 777 crecip(limb *out, const limb *z) { | |
| 778 limb z2[10]; | |
| 779 limb z9[10]; | |
| 780 limb z11[10]; | |
| 781 limb z2_5_0[10]; | |
| 782 limb z2_10_0[10]; | |
| 783 limb z2_20_0[10]; | |
| 784 limb z2_50_0[10]; | |
| 785 limb z2_100_0[10]; | |
| 786 limb t0[10]; | |
| 787 limb t1[10]; | |
| 788 int i; | |
| 789 | |
| 790 /* 2 */ fsquare(z2,z); | |
| 791 /* 4 */ fsquare(t1,z2); | |
| 792 /* 8 */ fsquare(t0,t1); | |
| 793 /* 9 */ fmul(z9,t0,z); | |
| 794 /* 11 */ fmul(z11,z9,z2); | |
| 795 /* 22 */ fsquare(t0,z11); | |
| 796 /* 2^5 - 2^0 = 31 */ fmul(z2_5_0,t0,z9); | |
| 797 | |
| 798 /* 2^6 - 2^1 */ fsquare(t0,z2_5_0); | |
| 799 /* 2^7 - 2^2 */ fsquare(t1,t0); | |
| 800 /* 2^8 - 2^3 */ fsquare(t0,t1); | |
| 801 /* 2^9 - 2^4 */ fsquare(t1,t0); | |
| 802 /* 2^10 - 2^5 */ fsquare(t0,t1); | |
| 803 /* 2^10 - 2^0 */ fmul(z2_10_0,t0,z2_5_0); | |
| 804 | |
| 805 /* 2^11 - 2^1 */ fsquare(t0,z2_10_0); | |
| 806 /* 2^12 - 2^2 */ fsquare(t1,t0); | |
| 807 /* 2^20 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } | |
| 808 /* 2^20 - 2^0 */ fmul(z2_20_0,t1,z2_10_0); | |
| 809 | |
| 810 /* 2^21 - 2^1 */ fsquare(t0,z2_20_0); | |
| 811 /* 2^22 - 2^2 */ fsquare(t1,t0); | |
| 812 /* 2^40 - 2^20 */ for (i = 2;i < 20;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } | |
| 813 /* 2^40 - 2^0 */ fmul(t0,t1,z2_20_0); | |
| 814 | |
| 815 /* 2^41 - 2^1 */ fsquare(t1,t0); | |
| 816 /* 2^42 - 2^2 */ fsquare(t0,t1); | |
| 817 /* 2^50 - 2^10 */ for (i = 2;i < 10;i += 2) { fsquare(t1,t0); fsquare(t0,t1); } | |
| 818 /* 2^50 - 2^0 */ fmul(z2_50_0,t0,z2_10_0); | |
| 819 | |
| 820 /* 2^51 - 2^1 */ fsquare(t0,z2_50_0); | |
| 821 /* 2^52 - 2^2 */ fsquare(t1,t0); | |
| 822 /* 2^100 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } | |
| 823 /* 2^100 - 2^0 */ fmul(z2_100_0,t1,z2_50_0); | |
| 824 | |
| 825 /* 2^101 - 2^1 */ fsquare(t1,z2_100_0); | |
| 826 /* 2^102 - 2^2 */ fsquare(t0,t1); | |
| 827 /* 2^200 - 2^100 */ for (i = 2;i < 100;i += 2) { fsquare(t1,t0); fsquare(t0,t1); } | |
| 828 /* 2^200 - 2^0 */ fmul(t1,t0,z2_100_0); | |
| 829 | |
| 830 /* 2^201 - 2^1 */ fsquare(t0,t1); | |
| 831 /* 2^202 - 2^2 */ fsquare(t1,t0); | |
| 832 /* 2^250 - 2^50 */ for (i = 2;i < 50;i += 2) { fsquare(t0,t1); fsquare(t1,t0); } | |
| 833 /* 2^250 - 2^0 */ fmul(t0,t1,z2_50_0); | |
| 834 | |
| 835 /* 2^251 - 2^1 */ fsquare(t1,t0); | |
| 836 /* 2^252 - 2^2 */ fsquare(t0,t1); | |
| 837 /* 2^253 - 2^3 */ fsquare(t1,t0); | |
| 838 /* 2^254 - 2^4 */ fsquare(t0,t1); | |
| 839 /* 2^255 - 2^5 */ fsquare(t1,t0); | |
| 840 /* 2^255 - 21 */ fmul(out,t1,z11); | |
| 841 } | |
| 842 | |
| 843 int | |
| 844 curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) { | |
| 845 limb bp[10], x[10], z[11], zmone[10]; | |
| 846 uint8_t e[32]; | |
| 847 int i; | |
| 848 | |
| 849 for (i = 0; i < 32; ++i) e[i] = secret[i]; | |
| 850 e[0] &= 248; | |
| 851 e[31] &= 127; | |
| 852 e[31] |= 64; | |
| 853 | |
| 854 fexpand(bp, basepoint); | |
| 855 cmult(x, z, e, bp); | |
| 856 crecip(zmone, z); | |
| 857 fmul(z, x, zmone); | |
| 858 fcontract(mypublic, z); | |
| 859 return 0; | |
| 860 } |