/src/relic/src/ed/relic_ed_add.c

Source
/*
 * RELIC is an Efficient LIbrary for Cryptography
 * Copyright (c) 2014 RELIC Authors
 *
 * This file is part of RELIC. RELIC is legal property of its developers,
 * whose names are not listed here. Please refer to the COPYRIGHT file
 * for contact information.
 *
 * RELIC is free software; you can redistribute it and/or modify it under the
 * terms of the version 2.1 (or later) of the GNU Lesser General Public License
 * as published by the Free Software Foundation; or version 2.0 of the Apache
 * License as published by the Apache Software Foundation. See the LICENSE files
 * for more details.
 *
 * RELIC is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the LICENSE files for more details.
 *
 * You should have received a copy of the GNU Lesser General Public or the
 * Apache License along with RELIC. If not, see <https://www.gnu.org/licenses/>
 * or <https://www.apache.org/licenses/>.
 */

/**
 * @file
 *
 * Implementation of the point addition on prime elliptic twisted Edwards curves.
 *
 * @version $Id$
 * @ingroup ed
 */

#include <assert.h>

#include "relic_core.h"
#include "relic_label.h"

/*============================================================================*/
/* Public definitions                                                         */
/*============================================================================*/

#if ED_ADD == BASIC || !defined(STRIP)

void ed_add_basic(ed_t r, const ed_t p, const ed_t q) {
  fp_t t0, t1, t2;

  fp_null(t0);
  fp_null(t1);
  fp_null(t2);

  RLC_TRY {
    fp_new(t0);
    fp_new(t1);
    fp_new(t2);

    /* x3 = (x1*y2+y1*x2)/(1+d*x1*x2*y1*y2)
     * y3 = (y1*y2-a*x1*x2)/(1-d*x1*x2*y1*y2) */

    fp_mul(t0, p->x, q->y);
    fp_mul(t1, p->y, q->x);
    fp_add(t0, t0, t1);

    fp_mul(t1, p->x, q->x);
    fp_mul(t2, p->y, q->y);
    fp_mul(t1, t1, t2);
    fp_mul(t1, t1, core_get()->ed_d);
    fp_add_dig(t2, t1, 1);
    fp_inv(t2, t2);
    fp_sub_dig(t1, t1, 1);
    fp_neg(t1, t1);
    fp_inv(t1, t1);

    fp_mul(t0, t0, t2);

    fp_mul(r->y, p->y, q->y);
    fp_mul(t2, p->x, q->x);
    fp_mul(t2, t2, core_get()->ed_a);
    fp_sub(r->y, r->y, t2);
    fp_mul(r->y, r->y, t1);

    fp_copy(r->x, t0);
    fp_copy(r->z, p->z);

    r->coord = BASIC;
  }
  RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT);
  }
  RLC_FINALLY {
    fp_free(t0);
    fp_free(t1);
    fp_free(t2);
  }
}

void ed_sub_basic(ed_t r, const ed_t p, const ed_t q) {
  ed_t t;

  ed_null(t);

  if (p == q) {
    ed_set_infty(r);
    return;
  }

  RLC_TRY {
    ed_new(t);

    ed_neg_basic(t, q);
    ed_add_basic(r, p, t);
    r->coord = BASIC;
  }
  RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT);
  }
  RLC_FINALLY {
    ed_free(t);
  }
}

#endif /* ED_ADD == BASIC */

#if ED_ADD == PROJC || !defined(STRIP)

void ed_add_projc(ed_t r, const ed_t p, const ed_t q) {
  fp_t t0, t1, t2, t3, t4, t5, t6, t7;

  fp_null(t0);
  fp_null(t1);
  fp_null(t2);
  fp_null(t3);
  fp_null(t4);
  fp_null(t5);
  fp_null(t6);
  fp_null(t7);

  RLC_TRY {
    fp_new(t0);
    fp_new(t1);
    fp_new(t2);
    fp_new(t3);
    fp_new(t4);
    fp_new(t5);
    fp_new(t6);
    fp_new(t7);

    /* A = z1 * z2, B = A^2 */
    fp_mul(t0, p->z, q->z);
    fp_sqr(t1, t0);

    /* C = x1 * x2, D = y1 * y2 */
    fp_mul(t2, p->x, q->x);
    fp_mul(t3, p->y, q->y);

    /* E = d * C * D */
    fp_mul(t4, core_get()->ed_d, t2);
    fp_mul(t4, t4, t3);

    /* F = B - E */
    fp_sub(t5, t1, t4);

    /* G = B + E */
    fp_add(t6, t1, t4);

    /* x3 = A * F * ((x1 + y1) * (x2 + y2) - C - D) */
    fp_mul(t7, t0, t5);
    fp_add(r->z, p->x, p->y);
    fp_add(r->x, q->x, q->y);
    fp_mul(r->x, r->z, r->x);
    fp_sub(r->x, r->x, t2);
    fp_sub(r->x, r->x, t3);
    fp_mul(r->x, t7, r->x);

    /* y3 = A * G * (D - a * C) */
    fp_mul(r->z, t0, t6);
    fp_mul(r->y, core_get()->ed_a, t2);
    fp_sub(r->y, t3, r->y);
    fp_mul(r->y, r->z, r->y);

    /* z3 = F * G */
    fp_mul(r->z, t5, t6);

    r->coord = PROJC;
  } RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT)
  } RLC_FINALLY {
    fp_free(t0);
    fp_free(t1);
    fp_free(t2);
    fp_free(t3);
    fp_free(t4);
    fp_free(t5);
    fp_free(t6);
    fp_free(t7);
  }
}

#endif /* ED_ADD == PROJC */

#if ED_ADD == PROJC || !defined(STRIP)

void ed_sub_projc(ed_t r, const ed_t p, const ed_t q) {
  ed_t t;

  ed_null(t);

  if (p == q) {
    ed_set_infty(r);
    return;
  }

  RLC_TRY {
    ed_new(t);

    ed_neg_projc(t, q);
    ed_add_projc(r, p, t);
  }
  RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT);
  }
  RLC_FINALLY {
    ed_free(t);
  }
}

#endif /* ED_ADD == PROJC || ED_ADD == EXTND */

#if ED_ADD == EXTND || !defined(STRIP)

void ed_add_extnd(ed_t r, const ed_t p, const ed_t q) {
  fp_t t0;
  fp_t t1;
  fp_t t2;
  fp_t t3;
  fp_t t4;

  fp_null(t0);
  fp_null(t1);
  fp_null(t2);
  fp_null(t3);
  fp_null(t4);

  RLC_TRY {
    fp_new(t0);
    fp_new(t1);
    fp_new(t2);
    fp_new(t3);
    fp_new(t4);

    /* A = x1 * x2, B = y1 * y2 */
    fp_mul(t0, p->x, q->x);
    fp_mul(t1, p->y, q->y);

    /* C = d * t1 * t2 */
    fp_mul(t2, core_get()->ed_d, p->t);
    fp_mul(r->t, t2, q->t);

    /* D = z1 * z2 */
    fp_mul(r->z, p->z, q->z);

    /* E = (x1 + y1) * (x2 + y2) - A - B */
    fp_add(t2, p->x, p->y);
    fp_add(t3, q->x, q->y);
    fp_mul(t2, t2, t3);
    fp_sub(t2, t2, t0);
    fp_sub(t2, t2, t1);

    /* F = D - C */
    fp_sub(t3, r->z, r->t);

    /* G = D + C */
    fp_add(t4, r->z, r->t);

    /* H = B - aA */
    fp_mul(r->x, core_get()->ed_a, t0);
    fp_sub(r->z, t1, r->x);

    /* x3 = E * F, y3 = G * H, t3 = E * H, z3 = F * G */
    fp_mul(r->x, t2, t3);
    fp_mul(r->y, t4, r->z);
    fp_mul(r->t, t2, r->z);
    fp_mul(r->z, t3, t4);

    r->coord = EXTND;
  } RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT)
  } RLC_FINALLY {
    fp_free(t0);
    fp_free(t1);
    fp_free(t2);
    fp_free(t3);
    fp_free(t4);
  }
}

void ed_sub_extnd(ed_t r, const ed_t p, const ed_t q) {
  ed_t t;

  ed_null(t);

  if (p == q) {
    ed_set_infty(r);
    return;
  }

  RLC_TRY {
    ed_new(t);

    ed_neg_projc(t, q);
    ed_add_extnd(r, p, t);
  }
  RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT);
  }
  RLC_FINALLY {
    ed_free(t);
  }
}

#endif

Coverage Report

Created: 2026-07-25 06:49

Line	Count	Source
1		/*
2		* RELIC is an Efficient LIbrary for Cryptography
3		* Copyright (c) 2014 RELIC Authors
4		*
5		* This file is part of RELIC. RELIC is legal property of its developers,
6		* whose names are not listed here. Please refer to the COPYRIGHT file
7		* for contact information.
8		*
9		* RELIC is free software; you can redistribute it and/or modify it under the
10		* terms of the version 2.1 (or later) of the GNU Lesser General Public License
11		* as published by the Free Software Foundation; or version 2.0 of the Apache
12		* License as published by the Apache Software Foundation. See the LICENSE files
13		* for more details.
14		*
15		* RELIC is distributed in the hope that it will be useful, but WITHOUT ANY
16		* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
17		* A PARTICULAR PURPOSE. See the LICENSE files for more details.
18		*
19		* You should have received a copy of the GNU Lesser General Public or the
20		* Apache License along with RELIC. If not, see <https://www.gnu.org/licenses/>
21		* or <https://www.apache.org/licenses/>.
22		*/
23
24		/**
25		* @file
26		*
27		* Implementation of the point addition on prime elliptic twisted Edwards curves.
28		*
29		* @version $Id$
30		* @ingroup ed
31		*/
32
33		#include <assert.h>
34
35		#include "relic_core.h"
36		#include "relic_label.h"
37
38		/============================================================================/
39		/* Public definitions */
40		/============================================================================/
41
42		#if ED_ADD == BASIC \|\| !defined(STRIP)
43
44	0	void ed_add_basic(ed_t r, const ed_t p, const ed_t q) {
45	0	fp_t t0, t1, t2;
46
47	0	fp_null(t0);
48	0	fp_null(t1);
49	0	fp_null(t2);
50
51	0	RLC_TRY {
52	0	fp_new(t0);
53	0	fp_new(t1);
54	0	fp_new(t2);
55
56		/* x3 = (x1y2+y1x2)/(1+dx1x2y1y2)
57		* y3 = (y1y2-ax1x2)/(1-dx1x2y1y2) /
58
59	0	fp_mul(t0, p->x, q->y);
60	0	fp_mul(t1, p->y, q->x);
61	0	fp_add(t0, t0, t1);
62
63	0	fp_mul(t1, p->x, q->x);
64	0	fp_mul(t2, p->y, q->y);
65	0	fp_mul(t1, t1, t2);
66	0	fp_mul(t1, t1, core_get()->ed_d);
67	0	fp_add_dig(t2, t1, 1);
68	0	fp_inv(t2, t2);
69	0	fp_sub_dig(t1, t1, 1);
70	0	fp_neg(t1, t1);
71	0	fp_inv(t1, t1);
72
73	0	fp_mul(t0, t0, t2);
74
75	0	fp_mul(r->y, p->y, q->y);
76	0	fp_mul(t2, p->x, q->x);
77	0	fp_mul(t2, t2, core_get()->ed_a);
78	0	fp_sub(r->y, r->y, t2);
79	0	fp_mul(r->y, r->y, t1);
80
81	0	fp_copy(r->x, t0);
82	0	fp_copy(r->z, p->z);
83
84	0	r->coord = BASIC;
85	0	}
86	0	RLC_CATCH_ANY {
87	0	RLC_THROW(ERR_CAUGHT);
88	0	}
89	0	RLC_FINALLY {
90	0	fp_free(t0);
91	0	fp_free(t1);
92	0	fp_free(t2);
93	0	}
94	0	}
95
96	0	void ed_sub_basic(ed_t r, const ed_t p, const ed_t q) {
97	0	ed_t t;
98
99	0	ed_null(t);
100
101	0	if (p == q) {
102	0	ed_set_infty(r);
103	0	return;
104	0	}
105
106	0	RLC_TRY {
107	0	ed_new(t);
108
109	0	ed_neg_basic(t, q);
110	0	ed_add_basic(r, p, t);
111	0	r->coord = BASIC;
112	0	}
113	0	RLC_CATCH_ANY {
114	0	RLC_THROW(ERR_CAUGHT);
115	0	}
116	0	RLC_FINALLY {
117	0	ed_free(t);
118	0	}
119	0	}
120
121		#endif /* ED_ADD == BASIC */
122
123		#if ED_ADD == PROJC \|\| !defined(STRIP)
124
125	0	void ed_add_projc(ed_t r, const ed_t p, const ed_t q) {
126	0	fp_t t0, t1, t2, t3, t4, t5, t6, t7;
127
128	0	fp_null(t0);
129	0	fp_null(t1);
130	0	fp_null(t2);
131	0	fp_null(t3);
132	0	fp_null(t4);
133	0	fp_null(t5);
134	0	fp_null(t6);
135	0	fp_null(t7);
136
137	0	RLC_TRY {
138	0	fp_new(t0);
139	0	fp_new(t1);
140	0	fp_new(t2);
141	0	fp_new(t3);
142	0	fp_new(t4);
143	0	fp_new(t5);
144	0	fp_new(t6);
145	0	fp_new(t7);
146
147		/* A = z1 * z2, B = A^2 */
148	0	fp_mul(t0, p->z, q->z);
149	0	fp_sqr(t1, t0);
150
151		/* C = x1 * x2, D = y1 * y2 */
152	0	fp_mul(t2, p->x, q->x);
153	0	fp_mul(t3, p->y, q->y);
154
155		/* E = d * C * D */
156	0	fp_mul(t4, core_get()->ed_d, t2);
157	0	fp_mul(t4, t4, t3);
158
159		/* F = B - E */
160	0	fp_sub(t5, t1, t4);
161
162		/* G = B + E */
163	0	fp_add(t6, t1, t4);
164
165		/* x3 = A * F * ((x1 + y1) * (x2 + y2) - C - D) */
166	0	fp_mul(t7, t0, t5);
167	0	fp_add(r->z, p->x, p->y);
168	0	fp_add(r->x, q->x, q->y);
169	0	fp_mul(r->x, r->z, r->x);
170	0	fp_sub(r->x, r->x, t2);
171	0	fp_sub(r->x, r->x, t3);
172	0	fp_mul(r->x, t7, r->x);
173
174		/* y3 = A * G * (D - a * C) */
175	0	fp_mul(r->z, t0, t6);
176	0	fp_mul(r->y, core_get()->ed_a, t2);
177	0	fp_sub(r->y, t3, r->y);
178	0	fp_mul(r->y, r->z, r->y);
179
180		/* z3 = F * G */
181	0	fp_mul(r->z, t5, t6);
182
183	0	r->coord = PROJC;
184	0	} RLC_CATCH_ANY {
185	0	RLC_THROW(ERR_CAUGHT)
186	0	} RLC_FINALLY {
187	0	fp_free(t0);
188	0	fp_free(t1);
189	0	fp_free(t2);
190	0	fp_free(t3);
191	0	fp_free(t4);
192	0	fp_free(t5);
193	0	fp_free(t6);
194	0	fp_free(t7);
195	0	}
196	0	}
197
198		#endif /* ED_ADD == PROJC */
199
200		#if ED_ADD == PROJC \|\| !defined(STRIP)
201
202	0	void ed_sub_projc(ed_t r, const ed_t p, const ed_t q) {
203	0	ed_t t;
204
205	0	ed_null(t);
206
207	0	if (p == q) {
208	0	ed_set_infty(r);
209	0	return;
210	0	}
211
212	0	RLC_TRY {
213	0	ed_new(t);
214
215	0	ed_neg_projc(t, q);
216	0	ed_add_projc(r, p, t);
217	0	}
218	0	RLC_CATCH_ANY {
219	0	RLC_THROW(ERR_CAUGHT);
220	0	}
221	0	RLC_FINALLY {
222	0	ed_free(t);
223	0	}
224	0	}
225
226		#endif /* ED_ADD == PROJC \|\| ED_ADD == EXTND */
227
228		#if ED_ADD == EXTND \|\| !defined(STRIP)
229
230	0	void ed_add_extnd(ed_t r, const ed_t p, const ed_t q) {
231	0	fp_t t0;
232	0	fp_t t1;
233	0	fp_t t2;
234	0	fp_t t3;
235	0	fp_t t4;
236
237	0	fp_null(t0);
238	0	fp_null(t1);
239	0	fp_null(t2);
240	0	fp_null(t3);
241	0	fp_null(t4);
242
243	0	RLC_TRY {
244	0	fp_new(t0);
245	0	fp_new(t1);
246	0	fp_new(t2);
247	0	fp_new(t3);
248	0	fp_new(t4);
249
250		/* A = x1 * x2, B = y1 * y2 */
251	0	fp_mul(t0, p->x, q->x);
252	0	fp_mul(t1, p->y, q->y);
253
254		/* C = d * t1 * t2 */
255	0	fp_mul(t2, core_get()->ed_d, p->t);
256	0	fp_mul(r->t, t2, q->t);
257
258		/* D = z1 * z2 */
259	0	fp_mul(r->z, p->z, q->z);
260
261		/* E = (x1 + y1) * (x2 + y2) - A - B */
262	0	fp_add(t2, p->x, p->y);
263	0	fp_add(t3, q->x, q->y);
264	0	fp_mul(t2, t2, t3);
265	0	fp_sub(t2, t2, t0);
266	0	fp_sub(t2, t2, t1);
267
268		/* F = D - C */
269	0	fp_sub(t3, r->z, r->t);
270
271		/* G = D + C */
272	0	fp_add(t4, r->z, r->t);
273
274		/* H = B - aA */
275	0	fp_mul(r->x, core_get()->ed_a, t0);
276	0	fp_sub(r->z, t1, r->x);
277
278		/* x3 = E * F, y3 = G * H, t3 = E * H, z3 = F * G */
279	0	fp_mul(r->x, t2, t3);
280	0	fp_mul(r->y, t4, r->z);
281	0	fp_mul(r->t, t2, r->z);
282	0	fp_mul(r->z, t3, t4);
283
284	0	r->coord = EXTND;
285	0	} RLC_CATCH_ANY {
286	0	RLC_THROW(ERR_CAUGHT)
287	0	} RLC_FINALLY {
288	0	fp_free(t0);
289	0	fp_free(t1);
290	0	fp_free(t2);
291	0	fp_free(t3);
292	0	fp_free(t4);
293	0	}
294	0	}
295
296	0	void ed_sub_extnd(ed_t r, const ed_t p, const ed_t q) {
297	0	ed_t t;
298
299	0	ed_null(t);
300
301	0	if (p == q) {
302	0	ed_set_infty(r);
303	0	return;
304	0	}
305
306	0	RLC_TRY {
307	0	ed_new(t);
308
309	0	ed_neg_projc(t, q);
310	0	ed_add_extnd(r, p, t);
311	0	}
312	0	RLC_CATCH_ANY {
313	0	RLC_THROW(ERR_CAUGHT);
314	0	}
315	0	RLC_FINALLY {
316		ed_free(t);
317	0	}
318	0	}
319
320		#endif