1 /* LibTomCrypt, modular cryptographic library -- Tom St Denis */
2 /* SPDX-License-Identifier: Unlicense */
3
4 #include "tomcrypt_private.h"
5
6 /**
7 @file ltc_ecc_projective_add_point.c
8 ECC Crypto, Tom St Denis
9 */
10
11 #if defined(LTC_MECC) && (!defined(LTC_MECC_ACCEL) || defined(LTM_DESC))
12
13 /**
14 Add two ECC points
15 @param P The point to add
16 @param Q The point to add
17 @param R [out] The destination of the double
18 @param ma ECC curve parameter a in montgomery form
19 @param modulus The modulus of the field the ECC curve is in
20 @param mp The "b" value from montgomery_setup()
21 @return CRYPT_OK on success
22 */
ltc_ecc_projective_add_point(const ecc_point * P,const ecc_point * Q,ecc_point * R,void * ma,void * modulus,void * mp)23 int ltc_ecc_projective_add_point(const ecc_point *P, const ecc_point *Q, ecc_point *R, void *ma, void *modulus, void *mp)
24 {
25 void *t1, *t2, *x, *y, *z;
26 int err, inf;
27
28 LTC_ARGCHK(P != NULL);
29 LTC_ARGCHK(Q != NULL);
30 LTC_ARGCHK(R != NULL);
31 LTC_ARGCHK(modulus != NULL);
32 LTC_ARGCHK(mp != NULL);
33
34 if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, LTC_NULL)) != CRYPT_OK) {
35 return err;
36 }
37
38 if ((err = ltc_ecc_is_point_at_infinity(P, modulus, &inf)) != CRYPT_OK) return err;
39 if (inf) {
40 /* P is point at infinity >> Result = Q */
41 err = ltc_ecc_copy_point(Q, R);
42 goto done;
43 }
44
45 if ((err = ltc_ecc_is_point_at_infinity(Q, modulus, &inf)) != CRYPT_OK) return err;
46 if (inf) {
47 /* Q is point at infinity >> Result = P */
48 err = ltc_ecc_copy_point(P, R);
49 goto done;
50 }
51
52 if ((mp_cmp(P->x, Q->x) == LTC_MP_EQ) && (mp_cmp(P->z, Q->z) == LTC_MP_EQ)) {
53 if (mp_cmp(P->y, Q->y) == LTC_MP_EQ) {
54 /* here P = Q >> Result = 2 * P (use doubling) */
55 mp_clear_multi(t1, t2, x, y, z, LTC_NULL);
56 return ltc_ecc_projective_dbl_point(P, R, ma, modulus, mp);
57 }
58 if ((err = mp_sub(modulus, Q->y, t1)) != CRYPT_OK) { goto done; }
59 if (mp_cmp(P->y, t1) == LTC_MP_EQ) {
60 /* here Q = -P >>> Result = the point at infinity */
61 err = ltc_ecc_set_point_xyz(1, 1, 0, R);
62 goto done;
63 }
64 }
65
66 if ((err = mp_copy(P->x, x)) != CRYPT_OK) { goto done; }
67 if ((err = mp_copy(P->y, y)) != CRYPT_OK) { goto done; }
68 if ((err = mp_copy(P->z, z)) != CRYPT_OK) { goto done; }
69
70 /* if Z is one then these are no-operations */
71 if (Q->z != NULL) {
72 /* T1 = Z' * Z' */
73 if ((err = mp_sqr(Q->z, t1)) != CRYPT_OK) { goto done; }
74 if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; }
75 /* X = X * T1 */
76 if ((err = mp_mul(t1, x, x)) != CRYPT_OK) { goto done; }
77 if ((err = mp_montgomery_reduce(x, modulus, mp)) != CRYPT_OK) { goto done; }
78 /* T1 = Z' * T1 */
79 if ((err = mp_mul(Q->z, t1, t1)) != CRYPT_OK) { goto done; }
80 if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; }
81 /* Y = Y * T1 */
82 if ((err = mp_mul(t1, y, y)) != CRYPT_OK) { goto done; }
83 if ((err = mp_montgomery_reduce(y, modulus, mp)) != CRYPT_OK) { goto done; }
84 }
85
86 /* T1 = Z*Z */
87 if ((err = mp_sqr(z, t1)) != CRYPT_OK) { goto done; }
88 if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; }
89 /* T2 = X' * T1 */
90 if ((err = mp_mul(Q->x, t1, t2)) != CRYPT_OK) { goto done; }
91 if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; }
92 /* T1 = Z * T1 */
93 if ((err = mp_mul(z, t1, t1)) != CRYPT_OK) { goto done; }
94 if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; }
95 /* T1 = Y' * T1 */
96 if ((err = mp_mul(Q->y, t1, t1)) != CRYPT_OK) { goto done; }
97 if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; }
98
99 /* Y = Y - T1 */
100 if ((err = mp_sub(y, t1, y)) != CRYPT_OK) { goto done; }
101 if (mp_cmp_d(y, 0) == LTC_MP_LT) {
102 if ((err = mp_add(y, modulus, y)) != CRYPT_OK) { goto done; }
103 }
104 /* T1 = 2T1 */
105 if ((err = mp_add(t1, t1, t1)) != CRYPT_OK) { goto done; }
106 if (mp_cmp(t1, modulus) != LTC_MP_LT) {
107 if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; }
108 }
109 /* T1 = Y + T1 */
110 if ((err = mp_add(t1, y, t1)) != CRYPT_OK) { goto done; }
111 if (mp_cmp(t1, modulus) != LTC_MP_LT) {
112 if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; }
113 }
114 /* X = X - T2 */
115 if ((err = mp_sub(x, t2, x)) != CRYPT_OK) { goto done; }
116 if (mp_cmp_d(x, 0) == LTC_MP_LT) {
117 if ((err = mp_add(x, modulus, x)) != CRYPT_OK) { goto done; }
118 }
119 /* T2 = 2T2 */
120 if ((err = mp_add(t2, t2, t2)) != CRYPT_OK) { goto done; }
121 if (mp_cmp(t2, modulus) != LTC_MP_LT) {
122 if ((err = mp_sub(t2, modulus, t2)) != CRYPT_OK) { goto done; }
123 }
124 /* T2 = X + T2 */
125 if ((err = mp_add(t2, x, t2)) != CRYPT_OK) { goto done; }
126 if (mp_cmp(t2, modulus) != LTC_MP_LT) {
127 if ((err = mp_sub(t2, modulus, t2)) != CRYPT_OK) { goto done; }
128 }
129
130 /* if Z' != 1 */
131 if (Q->z != NULL) {
132 /* Z = Z * Z' */
133 if ((err = mp_mul(z, Q->z, z)) != CRYPT_OK) { goto done; }
134 if ((err = mp_montgomery_reduce(z, modulus, mp)) != CRYPT_OK) { goto done; }
135 }
136
137 /* Z = Z * X */
138 if ((err = mp_mul(z, x, z)) != CRYPT_OK) { goto done; }
139 if ((err = mp_montgomery_reduce(z, modulus, mp)) != CRYPT_OK) { goto done; }
140
141 /* T1 = T1 * X */
142 if ((err = mp_mul(t1, x, t1)) != CRYPT_OK) { goto done; }
143 if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; }
144 /* X = X * X */
145 if ((err = mp_sqr(x, x)) != CRYPT_OK) { goto done; }
146 if ((err = mp_montgomery_reduce(x, modulus, mp)) != CRYPT_OK) { goto done; }
147 /* T2 = T2 * x */
148 if ((err = mp_mul(t2, x, t2)) != CRYPT_OK) { goto done; }
149 if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; }
150 /* T1 = T1 * X */
151 if ((err = mp_mul(t1, x, t1)) != CRYPT_OK) { goto done; }
152 if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; }
153
154 /* X = Y*Y */
155 if ((err = mp_sqr(y, x)) != CRYPT_OK) { goto done; }
156 if ((err = mp_montgomery_reduce(x, modulus, mp)) != CRYPT_OK) { goto done; }
157 /* X = X - T2 */
158 if ((err = mp_sub(x, t2, x)) != CRYPT_OK) { goto done; }
159 if (mp_cmp_d(x, 0) == LTC_MP_LT) {
160 if ((err = mp_add(x, modulus, x)) != CRYPT_OK) { goto done; }
161 }
162
163 /* T2 = T2 - X */
164 if ((err = mp_sub(t2, x, t2)) != CRYPT_OK) { goto done; }
165 if (mp_cmp_d(t2, 0) == LTC_MP_LT) {
166 if ((err = mp_add(t2, modulus, t2)) != CRYPT_OK) { goto done; }
167 }
168 /* T2 = T2 - X */
169 if ((err = mp_sub(t2, x, t2)) != CRYPT_OK) { goto done; }
170 if (mp_cmp_d(t2, 0) == LTC_MP_LT) {
171 if ((err = mp_add(t2, modulus, t2)) != CRYPT_OK) { goto done; }
172 }
173 /* T2 = T2 * Y */
174 if ((err = mp_mul(t2, y, t2)) != CRYPT_OK) { goto done; }
175 if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; }
176 /* Y = T2 - T1 */
177 if ((err = mp_sub(t2, t1, y)) != CRYPT_OK) { goto done; }
178 if (mp_cmp_d(y, 0) == LTC_MP_LT) {
179 if ((err = mp_add(y, modulus, y)) != CRYPT_OK) { goto done; }
180 }
181 /* Y = Y/2 */
182 if (mp_isodd(y)) {
183 if ((err = mp_add(y, modulus, y)) != CRYPT_OK) { goto done; }
184 }
185 if ((err = mp_div_2(y, y)) != CRYPT_OK) { goto done; }
186
187 if ((err = mp_copy(x, R->x)) != CRYPT_OK) { goto done; }
188 if ((err = mp_copy(y, R->y)) != CRYPT_OK) { goto done; }
189 if ((err = mp_copy(z, R->z)) != CRYPT_OK) { goto done; }
190
191 err = CRYPT_OK;
192 done:
193 mp_clear_multi(t1, t2, x, y, z, LTC_NULL);
194 return err;
195 }
196
197 #endif
198
199