1 /* Curve25519 (Montgomery form)
2 * Daniel Beer <dlbeer@gmail.com>, 18 Apr 2014
3 *
4 * This file is in the public domain.
5 */
6
7 #include "c25519.h"
8
9 const uint8_t c25519_base_x[F25519_SIZE] = {9};
10
11 /* Double an X-coordinate */
xc_double(uint8_t * x3,uint8_t * z3,const uint8_t * x1,const uint8_t * z1)12 static void xc_double(uint8_t *x3, uint8_t *z3,
13 const uint8_t *x1, const uint8_t *z1)
14 {
15 /* Explicit formulas database: dbl-1987-m
16 *
17 * source 1987 Montgomery "Speeding the Pollard and elliptic
18 * curve methods of factorization", page 261, fourth display
19 * compute X3 = (X1^2-Z1^2)^2
20 * compute Z3 = 4 X1 Z1 (X1^2 + a X1 Z1 + Z1^2)
21 */
22 uint8_t x1sq[F25519_SIZE];
23 uint8_t z1sq[F25519_SIZE];
24 uint8_t x1z1[F25519_SIZE];
25 uint8_t a[F25519_SIZE];
26
27 f25519_mul__distinct(x1sq, x1, x1);
28 f25519_mul__distinct(z1sq, z1, z1);
29 f25519_mul__distinct(x1z1, x1, z1);
30
31 f25519_sub(a, x1sq, z1sq);
32 f25519_mul__distinct(x3, a, a);
33
34 f25519_mul_c(a, x1z1, 486662);
35 f25519_add(a, x1sq, a);
36 f25519_add(a, z1sq, a);
37 f25519_mul__distinct(x1sq, x1z1, a);
38 f25519_mul_c(z3, x1sq, 4);
39 }
40
41 /* Differential addition */
xc_diffadd(uint8_t * x5,uint8_t * z5,const uint8_t * x1,const uint8_t * z1,const uint8_t * x2,const uint8_t * z2,const uint8_t * x3,const uint8_t * z3)42 static void xc_diffadd(uint8_t *x5, uint8_t *z5,
43 const uint8_t *x1, const uint8_t *z1,
44 const uint8_t *x2, const uint8_t *z2,
45 const uint8_t *x3, const uint8_t *z3)
46 {
47 /* Explicit formulas database: dbl-1987-m3
48 *
49 * source 1987 Montgomery "Speeding the Pollard and elliptic curve
50 * methods of factorization", page 261, fifth display, plus
51 * common-subexpression elimination
52 * compute A = X2+Z2
53 * compute B = X2-Z2
54 * compute C = X3+Z3
55 * compute D = X3-Z3
56 * compute DA = D A
57 * compute CB = C B
58 * compute X5 = Z1(DA+CB)^2
59 * compute Z5 = X1(DA-CB)^2
60 */
61 uint8_t da[F25519_SIZE];
62 uint8_t cb[F25519_SIZE];
63 uint8_t a[F25519_SIZE];
64 uint8_t b[F25519_SIZE];
65
66 f25519_add(a, x2, z2);
67 f25519_sub(b, x3, z3); /* D */
68 f25519_mul__distinct(da, a, b);
69
70 f25519_sub(b, x2, z2);
71 f25519_add(a, x3, z3); /* C */
72 f25519_mul__distinct(cb, a, b);
73
74 f25519_add(a, da, cb);
75 f25519_mul__distinct(b, a, a);
76 f25519_mul__distinct(x5, z1, b);
77
78 f25519_sub(a, da, cb);
79 f25519_mul__distinct(b, a, a);
80 f25519_mul__distinct(z5, x1, b);
81 }
82
c25519_smult(uint8_t * result,const uint8_t * q,const uint8_t * e)83 void c25519_smult(uint8_t *result, const uint8_t *q, const uint8_t *e)
84 {
85 /* Current point: P_m */
86 uint8_t xm[F25519_SIZE];
87 uint8_t zm[F25519_SIZE] = {1};
88
89 /* Predecessor: P_(m-1) */
90 uint8_t xm1[F25519_SIZE] = {1};
91 uint8_t zm1[F25519_SIZE] = {0};
92
93 int i;
94
95 /* Note: bit 254 is assumed to be 1 */
96 f25519_copy(xm, q);
97
98 for (i = 253; i >= 0; i--) {
99 const int bit = (e[i >> 3] >> (i & 7)) & 1;
100 uint8_t xms[F25519_SIZE];
101 uint8_t zms[F25519_SIZE];
102
103 /* From P_m and P_(m-1), compute P_(2m) and P_(2m-1) */
104 xc_diffadd(xm1, zm1, q, f25519_one, xm, zm, xm1, zm1);
105 xc_double(xm, zm, xm, zm);
106
107 /* Compute P_(2m+1) */
108 xc_diffadd(xms, zms, xm1, zm1, xm, zm, q, f25519_one);
109
110 /* Select:
111 * bit = 1 --> (P_(2m+1), P_(2m))
112 * bit = 0 --> (P_(2m), P_(2m-1))
113 */
114 f25519_select(xm1, xm1, xm, bit);
115 f25519_select(zm1, zm1, zm, bit);
116 f25519_select(xm, xm, xms, bit);
117 f25519_select(zm, zm, zms, bit);
118 }
119
120 /* Freeze out of projective coordinates */
121 f25519_inv__distinct(zm1, zm);
122 f25519_mul__distinct(result, zm1, xm);
123 f25519_normalize(result);
124 }
125