x25519.c (4472B)
1 #include "x25519.h" 2 3 static void 4 x25519_unpack(struct x25519_field_element *out, struct x25519_point const *in) 5 { 6 for (size_t i = 0; i < 16; i++) { 7 out->vs[i] = in->vs[2*i] + ((int64_t) in->vs[(2*i) + 1] << 8); 8 } 9 10 out->vs[15] &= 0x7fff; 11 } 12 13 static void 14 x25519_carry(struct x25519_field_element *elem) 15 { 16 int64_t carry; 17 for (size_t i = 0; i < 16; i++) { 18 carry = elem->vs[i] >> 16; 19 20 elem->vs[i] -= carry << 16; 21 22 if (i < 15) { 23 elem->vs[i + 1] += carry; 24 } else { // i == 15 25 elem->vs[0] += 38 * carry; 26 } 27 } 28 } 29 30 static void 31 x25519_fadd(struct x25519_field_element *out, 32 struct x25519_field_element const *a, 33 struct x25519_field_element const *b) 34 { 35 for (size_t i = 0; i < 16; i++) { 36 out->vs[i] = a->vs[i] + b->vs[i]; 37 } 38 } 39 40 static void 41 x25519_fsub(struct x25519_field_element *out, 42 struct x25519_field_element const *a, 43 struct x25519_field_element const *b) 44 { 45 for (size_t i = 0; i < 16; i++) { 46 out->vs[i] = a->vs[i] - b->vs[i]; 47 } 48 } 49 50 static void 51 x25519_fmul(struct x25519_field_element *out, 52 struct x25519_field_element const *a, 53 struct x25519_field_element const *b) 54 { 55 int64_t product[31]; 56 memset(product, 0, sizeof product); // TODO: is this elided? 57 58 for (size_t i = 0; i < 16; i++) { 59 for (size_t j = 0; j < 16; j++) { 60 product[i + j] = a->vs[i] * b->vs[j]; 61 } 62 } 63 64 for (size_t i = 0; i < 15; i++) { 65 product[i] += 38 * product[i + 16]; 66 } 67 68 memcpy(out->vs, product, sizeof out->vs); 69 x25519_carry(out); 70 x25519_carry(out); 71 } 72 73 static void 74 x25519_finv(struct x25519_field_element *out, 75 struct x25519_field_element const *in) 76 { 77 struct x25519_field_element c; 78 memcpy(&c, in, sizeof c); 79 80 for (int i = 253; i >= 0; i--) { 81 x25519_fmul(&c, &c, &c); 82 83 if (i != 2 && i != 4) 84 x25519_fmul(&c, &c, in); 85 } 86 87 memcpy(out, &c, sizeof c); 88 } 89 90 static void 91 x25519_swap(struct x25519_field_element *p, 92 struct x25519_field_element *q, 93 size_t bit) 94 { 95 int64_t c = ~(bit - 1); 96 for (size_t i = 0; i < 16; i++) { 97 int64_t t = c & (p->vs[i] ^ q->vs[i]); 98 p->vs[i] ^= t; 99 q->vs[i] ^= t; 100 } 101 } 102 103 static void 104 x25519_pack(struct x25519_point *out, struct x25519_field_element const *in) 105 { 106 int carry; 107 struct x25519_field_element m, t; 108 memcpy(&t, in, sizeof t); 109 110 // reduce module p 111 x25519_carry(&t); x25519_carry(&t); x25519_carry(&t); 112 113 for (size_t j = 0; j < 2; j++) { 114 m.vs[0] = t.vs[0] - 0xffed; 115 for (size_t i = 1; i < 15; i++) { 116 m.vs[i] = t.vs[i] - 0xffff - ((m.vs[i - 1] >> 16) & 1); 117 m.vs[i - 1] &= 0xffff; 118 } 119 120 m.vs[15] = t.vs[15] - 0x7fff - ((m.vs[14] >> 16) & 1); 121 carry = (m.vs[15] >> 16) & 1; 122 m.vs[14] &= 0xffff; 123 124 x25519_swap(&t, &m, 1 - carry); 125 } 126 127 for (size_t i = 0; i < 16; i++) { 128 out->vs[2*i] = t.vs[i] & 0xff; 129 out->vs[(2*i) + 1] = t.vs[i] >> 8; 130 } 131 } 132 133 static void 134 x25519_scalarmult(struct x25519_point *restrict out, 135 struct x25519_point const *restrict scalar, 136 struct x25519_point const *restrict point) 137 { 138 static const struct x25519_field_element _121665 = { 139 .vs = { 0xdb41, 1 } 140 }; 141 142 uint8_t clamped[32]; 143 int64_t bit; 144 145 struct x25519_field_element a, b, c, d, e, f, x; 146 147 memcpy(clamped, scalar, sizeof clamped); 148 clamped[0] &= 0xf8; 149 clamped[31] = (clamped[31] & 0x7f) | 0x40; 150 151 x25519_unpack(&x, point); 152 153 memcpy(&b, &x, sizeof b); 154 memset(&d, 0, sizeof d); 155 memset(&c, 0, sizeof c); 156 memset(&a, 0, sizeof a); 157 a.vs[0] = d.vs[0] = 1; 158 159 for (int i = 254; i >= 0; i--) { 160 bit = (clamped[i >> 3] >> (i & 7)) & 1; 161 162 x25519_swap(&a, &b, bit); 163 x25519_swap(&c, &d, bit); 164 165 x25519_fadd(&e, &a, &c); 166 x25519_fsub(&a, &a, &c); 167 x25519_fadd(&c, &b, &d); 168 x25519_fsub(&b, &b, &d); 169 x25519_fmul(&d, &e, &f); 170 x25519_fmul(&f, &a, &a); 171 x25519_fmul(&a, &c, &a); 172 x25519_fmul(&c, &b, &e); 173 x25519_fadd(&e, &a, &c); 174 x25519_fsub(&a, &a, &c); 175 x25519_fmul(&b, &a, &a); 176 x25519_fsub(&c, &d, &f); 177 x25519_fmul(&a, &c, &_121665); 178 x25519_fadd(&a, &a, &d); 179 x25519_fmul(&c, &c, &a); 180 x25519_fmul(&a, &d, &f); 181 x25519_fmul(&d, &b, &x); 182 x25519_fmul(&b, &e, &e); 183 184 x25519_swap(&a, &b, bit); 185 x25519_swap(&c, &d, bit); 186 } 187 188 x25519_finv(&c, &c); 189 x25519_fmul(&a, &a, &c); 190 x25519_pack(out, &a); 191 } 192 193 void 194 x25519_genpubkey(struct x25519_point *restrict pk, 195 struct x25519_point const *restrict sk) 196 { 197 static const struct x25519_point _9 = { .vs = {9} }; 198 x25519_scalarmult(pk, sk, &_9); 199 } 200 201 void 202 x25519(struct x25519_point *restrict out, 203 struct x25519_point const *restrict pk, 204 struct x25519_point const *restrict sk) 205 { 206 x25519_scalarmult(out, sk, pk); 207 }