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