Damien Miller | 8a56dc2 | 2013-12-18 17:48:11 +1100 | [diff] [blame] | 1 | /* $OpenBSD: sc25519.c,v 1.3 2013/12/09 11:03:45 markus Exp $ */ |
Damien Miller | 5be9d9e | 2013-12-07 11:24:01 +1100 | [diff] [blame] | 2 | |
Damien Miller | 8a56dc2 | 2013-12-18 17:48:11 +1100 | [diff] [blame] | 3 | /* |
| 4 | * Public Domain, Authors: Daniel J. Bernstein, Niels Duif, Tanja Lange, |
| 5 | * Peter Schwabe, Bo-Yin Yang. |
| 6 | * Copied from supercop-20130419/crypto_sign/ed25519/ref/sc25519.c |
| 7 | */ |
Damien Miller | 5be9d9e | 2013-12-07 11:24:01 +1100 | [diff] [blame] | 8 | |
| 9 | #include "sc25519.h" |
| 10 | |
| 11 | /*Arithmetic modulo the group order m = 2^252 + 27742317777372353535851937790883648493 = 7237005577332262213973186563042994240857116359379907606001950938285454250989 */ |
| 12 | |
| 13 | static const crypto_uint32 m[32] = {0xED, 0xD3, 0xF5, 0x5C, 0x1A, 0x63, 0x12, 0x58, 0xD6, 0x9C, 0xF7, 0xA2, 0xDE, 0xF9, 0xDE, 0x14, |
| 14 | 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10}; |
| 15 | |
| 16 | static const crypto_uint32 mu[33] = {0x1B, 0x13, 0x2C, 0x0A, 0xA3, 0xE5, 0x9C, 0xED, 0xA7, 0x29, 0x63, 0x08, 0x5D, 0x21, 0x06, 0x21, |
| 17 | 0xEB, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0F}; |
| 18 | |
| 19 | static crypto_uint32 lt(crypto_uint32 a,crypto_uint32 b) /* 16-bit inputs */ |
| 20 | { |
| 21 | unsigned int x = a; |
| 22 | x -= (unsigned int) b; /* 0..65535: no; 4294901761..4294967295: yes */ |
| 23 | x >>= 31; /* 0: no; 1: yes */ |
| 24 | return x; |
| 25 | } |
| 26 | |
| 27 | /* Reduce coefficients of r before calling reduce_add_sub */ |
| 28 | static void reduce_add_sub(sc25519 *r) |
| 29 | { |
| 30 | crypto_uint32 pb = 0; |
| 31 | crypto_uint32 b; |
| 32 | crypto_uint32 mask; |
| 33 | int i; |
| 34 | unsigned char t[32]; |
| 35 | |
| 36 | for(i=0;i<32;i++) |
| 37 | { |
| 38 | pb += m[i]; |
| 39 | b = lt(r->v[i],pb); |
| 40 | t[i] = r->v[i]-pb+(b<<8); |
| 41 | pb = b; |
| 42 | } |
| 43 | mask = b - 1; |
| 44 | for(i=0;i<32;i++) |
| 45 | r->v[i] ^= mask & (r->v[i] ^ t[i]); |
| 46 | } |
| 47 | |
| 48 | /* Reduce coefficients of x before calling barrett_reduce */ |
| 49 | static void barrett_reduce(sc25519 *r, const crypto_uint32 x[64]) |
| 50 | { |
| 51 | /* See HAC, Alg. 14.42 */ |
| 52 | int i,j; |
| 53 | crypto_uint32 q2[66]; |
| 54 | crypto_uint32 *q3 = q2 + 33; |
| 55 | crypto_uint32 r1[33]; |
| 56 | crypto_uint32 r2[33]; |
| 57 | crypto_uint32 carry; |
| 58 | crypto_uint32 pb = 0; |
| 59 | crypto_uint32 b; |
| 60 | |
| 61 | for (i = 0;i < 66;++i) q2[i] = 0; |
| 62 | for (i = 0;i < 33;++i) r2[i] = 0; |
| 63 | |
| 64 | for(i=0;i<33;i++) |
| 65 | for(j=0;j<33;j++) |
| 66 | if(i+j >= 31) q2[i+j] += mu[i]*x[j+31]; |
| 67 | carry = q2[31] >> 8; |
| 68 | q2[32] += carry; |
| 69 | carry = q2[32] >> 8; |
| 70 | q2[33] += carry; |
| 71 | |
| 72 | for(i=0;i<33;i++)r1[i] = x[i]; |
| 73 | for(i=0;i<32;i++) |
| 74 | for(j=0;j<33;j++) |
| 75 | if(i+j < 33) r2[i+j] += m[i]*q3[j]; |
| 76 | |
| 77 | for(i=0;i<32;i++) |
| 78 | { |
| 79 | carry = r2[i] >> 8; |
| 80 | r2[i+1] += carry; |
| 81 | r2[i] &= 0xff; |
| 82 | } |
| 83 | |
| 84 | for(i=0;i<32;i++) |
| 85 | { |
| 86 | pb += r2[i]; |
| 87 | b = lt(r1[i],pb); |
| 88 | r->v[i] = r1[i]-pb+(b<<8); |
| 89 | pb = b; |
| 90 | } |
| 91 | |
| 92 | /* XXX: Can it really happen that r<0?, See HAC, Alg 14.42, Step 3 |
| 93 | * If so: Handle it here! |
| 94 | */ |
| 95 | |
| 96 | reduce_add_sub(r); |
| 97 | reduce_add_sub(r); |
| 98 | } |
| 99 | |
| 100 | void sc25519_from32bytes(sc25519 *r, const unsigned char x[32]) |
| 101 | { |
| 102 | int i; |
| 103 | crypto_uint32 t[64]; |
| 104 | for(i=0;i<32;i++) t[i] = x[i]; |
| 105 | for(i=32;i<64;++i) t[i] = 0; |
| 106 | barrett_reduce(r, t); |
| 107 | } |
| 108 | |
| 109 | void shortsc25519_from16bytes(shortsc25519 *r, const unsigned char x[16]) |
| 110 | { |
| 111 | int i; |
| 112 | for(i=0;i<16;i++) r->v[i] = x[i]; |
| 113 | } |
| 114 | |
| 115 | void sc25519_from64bytes(sc25519 *r, const unsigned char x[64]) |
| 116 | { |
| 117 | int i; |
| 118 | crypto_uint32 t[64]; |
| 119 | for(i=0;i<64;i++) t[i] = x[i]; |
| 120 | barrett_reduce(r, t); |
| 121 | } |
| 122 | |
| 123 | void sc25519_from_shortsc(sc25519 *r, const shortsc25519 *x) |
| 124 | { |
| 125 | int i; |
| 126 | for(i=0;i<16;i++) |
| 127 | r->v[i] = x->v[i]; |
| 128 | for(i=0;i<16;i++) |
| 129 | r->v[16+i] = 0; |
| 130 | } |
| 131 | |
| 132 | void sc25519_to32bytes(unsigned char r[32], const sc25519 *x) |
| 133 | { |
| 134 | int i; |
| 135 | for(i=0;i<32;i++) r[i] = x->v[i]; |
| 136 | } |
| 137 | |
| 138 | int sc25519_iszero_vartime(const sc25519 *x) |
| 139 | { |
| 140 | int i; |
| 141 | for(i=0;i<32;i++) |
| 142 | if(x->v[i] != 0) return 0; |
| 143 | return 1; |
| 144 | } |
| 145 | |
| 146 | int sc25519_isshort_vartime(const sc25519 *x) |
| 147 | { |
| 148 | int i; |
| 149 | for(i=31;i>15;i--) |
| 150 | if(x->v[i] != 0) return 0; |
| 151 | return 1; |
| 152 | } |
| 153 | |
| 154 | int sc25519_lt_vartime(const sc25519 *x, const sc25519 *y) |
| 155 | { |
| 156 | int i; |
| 157 | for(i=31;i>=0;i--) |
| 158 | { |
| 159 | if(x->v[i] < y->v[i]) return 1; |
| 160 | if(x->v[i] > y->v[i]) return 0; |
| 161 | } |
| 162 | return 0; |
| 163 | } |
| 164 | |
| 165 | void sc25519_add(sc25519 *r, const sc25519 *x, const sc25519 *y) |
| 166 | { |
| 167 | int i, carry; |
| 168 | for(i=0;i<32;i++) r->v[i] = x->v[i] + y->v[i]; |
| 169 | for(i=0;i<31;i++) |
| 170 | { |
| 171 | carry = r->v[i] >> 8; |
| 172 | r->v[i+1] += carry; |
| 173 | r->v[i] &= 0xff; |
| 174 | } |
| 175 | reduce_add_sub(r); |
| 176 | } |
| 177 | |
| 178 | void sc25519_sub_nored(sc25519 *r, const sc25519 *x, const sc25519 *y) |
| 179 | { |
| 180 | crypto_uint32 b = 0; |
| 181 | crypto_uint32 t; |
| 182 | int i; |
| 183 | for(i=0;i<32;i++) |
| 184 | { |
| 185 | t = x->v[i] - y->v[i] - b; |
| 186 | r->v[i] = t & 255; |
| 187 | b = (t >> 8) & 1; |
| 188 | } |
| 189 | } |
| 190 | |
| 191 | void sc25519_mul(sc25519 *r, const sc25519 *x, const sc25519 *y) |
| 192 | { |
| 193 | int i,j,carry; |
| 194 | crypto_uint32 t[64]; |
| 195 | for(i=0;i<64;i++)t[i] = 0; |
| 196 | |
| 197 | for(i=0;i<32;i++) |
| 198 | for(j=0;j<32;j++) |
| 199 | t[i+j] += x->v[i] * y->v[j]; |
| 200 | |
| 201 | /* Reduce coefficients */ |
| 202 | for(i=0;i<63;i++) |
| 203 | { |
| 204 | carry = t[i] >> 8; |
| 205 | t[i+1] += carry; |
| 206 | t[i] &= 0xff; |
| 207 | } |
| 208 | |
| 209 | barrett_reduce(r, t); |
| 210 | } |
| 211 | |
| 212 | void sc25519_mul_shortsc(sc25519 *r, const sc25519 *x, const shortsc25519 *y) |
| 213 | { |
| 214 | sc25519 t; |
| 215 | sc25519_from_shortsc(&t, y); |
| 216 | sc25519_mul(r, x, &t); |
| 217 | } |
| 218 | |
| 219 | void sc25519_window3(signed char r[85], const sc25519 *s) |
| 220 | { |
| 221 | char carry; |
| 222 | int i; |
| 223 | for(i=0;i<10;i++) |
| 224 | { |
| 225 | r[8*i+0] = s->v[3*i+0] & 7; |
| 226 | r[8*i+1] = (s->v[3*i+0] >> 3) & 7; |
| 227 | r[8*i+2] = (s->v[3*i+0] >> 6) & 7; |
| 228 | r[8*i+2] ^= (s->v[3*i+1] << 2) & 7; |
| 229 | r[8*i+3] = (s->v[3*i+1] >> 1) & 7; |
| 230 | r[8*i+4] = (s->v[3*i+1] >> 4) & 7; |
| 231 | r[8*i+5] = (s->v[3*i+1] >> 7) & 7; |
| 232 | r[8*i+5] ^= (s->v[3*i+2] << 1) & 7; |
| 233 | r[8*i+6] = (s->v[3*i+2] >> 2) & 7; |
| 234 | r[8*i+7] = (s->v[3*i+2] >> 5) & 7; |
| 235 | } |
| 236 | r[8*i+0] = s->v[3*i+0] & 7; |
| 237 | r[8*i+1] = (s->v[3*i+0] >> 3) & 7; |
| 238 | r[8*i+2] = (s->v[3*i+0] >> 6) & 7; |
| 239 | r[8*i+2] ^= (s->v[3*i+1] << 2) & 7; |
| 240 | r[8*i+3] = (s->v[3*i+1] >> 1) & 7; |
| 241 | r[8*i+4] = (s->v[3*i+1] >> 4) & 7; |
| 242 | |
| 243 | /* Making it signed */ |
| 244 | carry = 0; |
| 245 | for(i=0;i<84;i++) |
| 246 | { |
| 247 | r[i] += carry; |
| 248 | r[i+1] += r[i] >> 3; |
| 249 | r[i] &= 7; |
| 250 | carry = r[i] >> 2; |
| 251 | r[i] -= carry<<3; |
| 252 | } |
| 253 | r[84] += carry; |
| 254 | } |
| 255 | |
| 256 | void sc25519_window5(signed char r[51], const sc25519 *s) |
| 257 | { |
| 258 | char carry; |
| 259 | int i; |
| 260 | for(i=0;i<6;i++) |
| 261 | { |
| 262 | r[8*i+0] = s->v[5*i+0] & 31; |
| 263 | r[8*i+1] = (s->v[5*i+0] >> 5) & 31; |
| 264 | r[8*i+1] ^= (s->v[5*i+1] << 3) & 31; |
| 265 | r[8*i+2] = (s->v[5*i+1] >> 2) & 31; |
| 266 | r[8*i+3] = (s->v[5*i+1] >> 7) & 31; |
| 267 | r[8*i+3] ^= (s->v[5*i+2] << 1) & 31; |
| 268 | r[8*i+4] = (s->v[5*i+2] >> 4) & 31; |
| 269 | r[8*i+4] ^= (s->v[5*i+3] << 4) & 31; |
| 270 | r[8*i+5] = (s->v[5*i+3] >> 1) & 31; |
| 271 | r[8*i+6] = (s->v[5*i+3] >> 6) & 31; |
| 272 | r[8*i+6] ^= (s->v[5*i+4] << 2) & 31; |
| 273 | r[8*i+7] = (s->v[5*i+4] >> 3) & 31; |
| 274 | } |
| 275 | r[8*i+0] = s->v[5*i+0] & 31; |
| 276 | r[8*i+1] = (s->v[5*i+0] >> 5) & 31; |
| 277 | r[8*i+1] ^= (s->v[5*i+1] << 3) & 31; |
| 278 | r[8*i+2] = (s->v[5*i+1] >> 2) & 31; |
| 279 | |
| 280 | /* Making it signed */ |
| 281 | carry = 0; |
| 282 | for(i=0;i<50;i++) |
| 283 | { |
| 284 | r[i] += carry; |
| 285 | r[i+1] += r[i] >> 5; |
| 286 | r[i] &= 31; |
| 287 | carry = r[i] >> 4; |
| 288 | r[i] -= carry<<5; |
| 289 | } |
| 290 | r[50] += carry; |
| 291 | } |
| 292 | |
| 293 | void sc25519_2interleave2(unsigned char r[127], const sc25519 *s1, const sc25519 *s2) |
| 294 | { |
| 295 | int i; |
| 296 | for(i=0;i<31;i++) |
| 297 | { |
| 298 | r[4*i] = ( s1->v[i] & 3) ^ (( s2->v[i] & 3) << 2); |
| 299 | r[4*i+1] = ((s1->v[i] >> 2) & 3) ^ (((s2->v[i] >> 2) & 3) << 2); |
| 300 | r[4*i+2] = ((s1->v[i] >> 4) & 3) ^ (((s2->v[i] >> 4) & 3) << 2); |
| 301 | r[4*i+3] = ((s1->v[i] >> 6) & 3) ^ (((s2->v[i] >> 6) & 3) << 2); |
| 302 | } |
| 303 | r[124] = ( s1->v[31] & 3) ^ (( s2->v[31] & 3) << 2); |
| 304 | r[125] = ((s1->v[31] >> 2) & 3) ^ (((s2->v[31] >> 2) & 3) << 2); |
| 305 | r[126] = ((s1->v[31] >> 4) & 3) ^ (((s2->v[31] >> 4) & 3) << 2); |
| 306 | } |