tls

x25519.h (4782B)

---

 // https://martin.kleppmann.com/papers/curve25519.pdf
 
 #include <stdint.h>
 #include <string.h>
 
 struct x25519_point {
 	uint8_t vs[32];
 };
 
 struct x25519_field_element {
 	int64_t vs[16]; // array of 16, 16-bit numbers (stored as 64-bit)
 };
 
 static inline void
 x25519_unpack(struct x25519_field_element *out, struct x25519_point const *in)
 {
 	for (size_t i = 0; i < 16; i++) {
 		out->vs[i] = in->vs[2*i] + ((int64_t) in->vs[(2*i) + 1] << 8);
 	}
 
 	out->vs[15] &= 0x7fff;
 }
 
 static inline void
 x25519_carry(struct x25519_field_element *elem)
 {
 	int64_t carry;
 	for (size_t i = 0; i < 16; i++) {
 		carry = elem->vs[i] >> 16;
 
 		elem->vs[i] -= carry << 16;
 
 		if (i < 15) {
 			elem->vs[i + 1] += carry;
 		} else { // i == 15
 			elem->vs[0] += 38 * carry;
 		}
 	}
 }
 
 static inline void
 x25519_fadd(struct x25519_field_element *out,
 	    struct x25519_field_element const *a,
 	    struct x25519_field_element const *b)
 {
 	for (size_t i = 0; i < 16; i++) {
 		out->vs[i] = a->vs[i] + b->vs[i];
 	}
 }
 
 static inline void
 x25519_fsub(struct x25519_field_element *out,
 	    struct x25519_field_element const *a,
 	    struct x25519_field_element const *b)
 {
 	for (size_t i = 0; i < 16; i++) {
 		out->vs[i] = a->vs[i] - b->vs[i];
 	}
 }
 
 static inline void
 x25519_fmul(struct x25519_field_element *out,
 	    struct x25519_field_element const *a,
 	    struct x25519_field_element const *b)
 {
 	int64_t product[31];
 	memset(product, 0, sizeof product); // TODO: is this elided?
 
 	for (size_t i = 0; i < 16; i++) {
 		for (size_t j = 0; j < 16; j++) {
 			product[i + j] = a->vs[i] * b->vs[j];
 		}
 	}
 
 	for (size_t i = 0; i < 15; i++) {
 		product[i] += 38 * product[i + 16];
 	}
 
 	memcpy(out->vs, product, sizeof out->vs);
 	x25519_carry(out);
 	x25519_carry(out);
 }
 
 static inline void
 x25519_finv(struct x25519_field_element *out,
 	    struct x25519_field_element const *in)
 {
 	struct x25519_field_element c;
 	memcpy(&c, in, sizeof c);
 
 	for (int i = 253; i >= 0; i--) {
 		x25519_fmul(&c, &c, &c);
 
 		if (i != 2 && i != 4)
 			x25519_fmul(&c, &c, in);
 	}
 
 	memcpy(out, &c, sizeof c);
 }
 
 static inline void
 x25519_swap(struct x25519_field_element *p,
 	    struct x25519_field_element *q,
 	    size_t bit)
 {
 	int64_t c = ~(bit - 1);
 	for (size_t i = 0; i < 16; i++) {
 		int64_t t = c & (p->vs[i] ^ q->vs[i]);
 		p->vs[i] ^= t;
 		q->vs[i] ^= t;
 	}
 }
 
 static inline void
 x25519_pack(struct x25519_point *out, struct x25519_field_element const *in)
 {
 	int carry;
 	struct x25519_field_element m, t;
 	memcpy(&t, in, sizeof t);
 
 	// reduce module p
 	x25519_carry(&t); x25519_carry(&t); x25519_carry(&t);
 
 	for (size_t j = 0; j < 2; j++) {
 		m.vs[0] = t.vs[0] - 0xffed;
 		for (size_t i = 1; i < 15; i++) {
 			m.vs[i] = t.vs[i] - 0xffff - ((m.vs[i - 1] >> 16) & 1);
 			m.vs[i - 1] &= 0xffff;
 		}
 
 		m.vs[15] = t.vs[15] - 0x7fff - ((m.vs[14] >> 16) & 1);
 		carry = (m.vs[15] >> 16) & 1;
 		m.vs[14] &= 0xffff;
 
 		x25519_swap(&t, &m, 1 - carry);
 	}
 
 	for (size_t i = 0; i < 16; i++) {
 		out->vs[2*i] = t.vs[i] & 0xff;
 		out->vs[(2*i) + 1] = t.vs[i] >> 8;
 	}
 }
 
 static inline void
 x25519_scalarmult(struct x25519_point *restrict out,
 		  struct x25519_point const *restrict scalar,
 		  struct x25519_point const *restrict point)
 {
 	static const struct x25519_field_element _121665 = {
 		.vs = { 0xdb41, 1 }
 	};
 
 	uint8_t clamped[32];
 	int64_t bit;
 
 	struct x25519_field_element a, b, c, d, e, f, x;
 
 	memcpy(clamped, scalar, sizeof clamped);
 	clamped[0] &= 0xf8;
 	clamped[31] = (clamped[31] & 0x7f) | 0x40;
 
 	x25519_unpack(&x, point);
 
 	memcpy(&b, &x, sizeof b);
 	memset(&d, 0, sizeof d);
 	memset(&c, 0, sizeof c);
 	memset(&a, 0, sizeof a);
 	a.vs[0] = d.vs[0] = 1;
 
 	for (int i = 254; i >= 0; i--) {
 		bit = (clamped[i >> 3] >> (i & 7)) & 1;
 
 		x25519_swap(&a, &b, bit);
 		x25519_swap(&c, &d, bit);
 
 		x25519_fadd(&e, &a, &c);
 		x25519_fsub(&a, &a, &c);
 		x25519_fadd(&c, &b, &d);
 		x25519_fsub(&b, &b, &d);
 		x25519_fmul(&d, &e, &f);
 		x25519_fmul(&f, &a, &a);
 		x25519_fmul(&a, &c, &a);
 		x25519_fmul(&c, &b, &e);
 		x25519_fadd(&e, &a, &c);
 		x25519_fsub(&a, &a, &c);
 		x25519_fmul(&b, &a, &a);
 		x25519_fsub(&c, &d, &f);
 		x25519_fmul(&a, &c, &_121665);
 		x25519_fadd(&a, &a, &d);
 		x25519_fmul(&c, &c, &a);
 		x25519_fmul(&a, &d, &f);
 		x25519_fmul(&d, &b, &x);
 		x25519_fmul(&b, &e, &e);
 
 		x25519_swap(&a, &b, bit);
 		x25519_swap(&c, &d, bit);
 	}
 
 	x25519_finv(&c, &c);
 	x25519_fmul(&a, &a, &c);
 	x25519_pack(out, &a);
 }
 
 static inline void
 x25519_genpubkey(struct x25519_point *restrict pk,
 		 struct x25519_point const *restrict sk)
 {
 	static const struct x25519_point _9 = { .vs = {9} };
 	x25519_scalarmult(pk, sk, &_9);
 }
 
 static inline void
 x25519(struct x25519_point *restrict out,
        struct x25519_point const *restrict pk,
        struct x25519_point const *restrict sk)
 {
 	x25519_scalarmult(out, sk, pk);
 }