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