|
Packit Service |
4684c1 |
/* ecc-add-jjj.c
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
Copyright (C) 2013 Niels Möller
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
This file is part of GNU Nettle.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
GNU Nettle is free software: you can redistribute it and/or
|
|
Packit Service |
4684c1 |
modify it under the terms of either:
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
* the GNU Lesser General Public License as published by the Free
|
|
Packit Service |
4684c1 |
Software Foundation; either version 3 of the License, or (at your
|
|
Packit Service |
4684c1 |
option) any later version.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
or
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
* the GNU General Public License as published by the Free
|
|
Packit Service |
4684c1 |
Software Foundation; either version 2 of the License, or (at your
|
|
Packit Service |
4684c1 |
option) any later version.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
or both in parallel, as here.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
GNU Nettle is distributed in the hope that it will be useful,
|
|
Packit Service |
4684c1 |
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
4684c1 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Packit Service |
4684c1 |
General Public License for more details.
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
You should have received copies of the GNU General Public License and
|
|
Packit Service |
4684c1 |
the GNU Lesser General Public License along with this program. If
|
|
Packit Service |
4684c1 |
not, see http://www.gnu.org/licenses/.
|
|
Packit Service |
4684c1 |
*/
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
#if HAVE_CONFIG_H
|
|
Packit Service |
4684c1 |
# include "config.h"
|
|
Packit Service |
4684c1 |
#endif
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
#include <nettle/ecc.h>
|
|
Packit Service |
4684c1 |
#include "ecc-internal.h"
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
void
|
|
Packit Service |
4684c1 |
ecc_add_jjj (const struct ecc_curve *ecc,
|
|
Packit Service |
4684c1 |
mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
|
|
Packit Service |
4684c1 |
mp_limb_t *scratch)
|
|
Packit Service |
4684c1 |
{
|
|
Packit Service |
4684c1 |
/* Formulas, from djb,
|
|
Packit Service |
4684c1 |
http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl:
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
Computation Operation Live variables
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
Z1Z1 = Z1^2 sqr Z1Z1
|
|
Packit Service |
4684c1 |
Z2Z2 = Z2^2 sqr Z1Z1, Z2Z2
|
|
Packit Service |
4684c1 |
U1 = X1*Z2Z2 mul Z1Z1, Z2Z2, U1
|
|
Packit Service |
4684c1 |
U2 = X2*Z1Z1 mul Z1Z1, Z2Z2, U1, U2
|
|
Packit Service |
4684c1 |
H = U2-U1 Z1Z1, Z2Z2, U1, H
|
|
Packit Service |
4684c1 |
Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2)*H sqr, mul Z1Z1, Z2Z2, U1, H
|
|
Packit Service |
4684c1 |
S1 = Y1*Z2*Z2Z2 mul, mul Z1Z1, U1, H, S1
|
|
Packit Service |
4684c1 |
S2 = Y2*Z1*Z1Z1 mul, mul U1, H, S1, S2
|
|
Packit Service |
4684c1 |
W = 2*(S2-S1) (djb: r) U1, H, S1, W
|
|
Packit Service |
4684c1 |
I = (2*H)^2 sqr U1, H, S1, W, I
|
|
Packit Service |
4684c1 |
J = H*I mul U1, S1, W, J, V
|
|
Packit Service |
4684c1 |
V = U1*I mul S1, W, J, V
|
|
Packit Service |
4684c1 |
X3 = W^2-J-2*V sqr S1, W, J, V
|
|
Packit Service |
4684c1 |
Y3 = W*(V-X3)-2*S1*J mul, mul
|
|
Packit Service |
4684c1 |
*/
|
|
Packit Service |
4684c1 |
mp_limb_t *z1z1 = scratch;
|
|
Packit Service |
4684c1 |
mp_limb_t *z2z2 = scratch + ecc->p.size;
|
|
Packit Service |
4684c1 |
mp_limb_t *u1 = scratch + 2*ecc->p.size;
|
|
Packit Service |
4684c1 |
mp_limb_t *u2 = scratch + 3*ecc->p.size;
|
|
Packit Service |
4684c1 |
mp_limb_t *s1 = scratch; /* overlap z1z1 */
|
|
Packit Service |
4684c1 |
mp_limb_t *s2 = scratch + ecc->p.size; /* overlap z2z2 */
|
|
Packit Service |
4684c1 |
mp_limb_t *i = scratch + 4*ecc->p.size;
|
|
Packit Service |
4684c1 |
mp_limb_t *j = scratch + 5*ecc->p.size;
|
|
Packit Service |
4684c1 |
mp_limb_t *v = scratch + 6*ecc->p.size;
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* z1^2, z2^2, u1 = x1 x2^2, u2 = x2 z1^2 - u1 */
|
|
Packit Service |
4684c1 |
ecc_mod_sqr (&ecc->p, z1z1, p + 2*ecc->p.size);
|
|
Packit Service |
4684c1 |
ecc_mod_sqr (&ecc->p, z2z2, q + 2*ecc->p.size);
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, u1, p, z2z2);
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, u2, q, z1z1);
|
|
Packit Service |
4684c1 |
ecc_mod_sub (&ecc->p, u2, u2, u1); /* Store h in u2 */
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* z3, use i, j, v as scratch, result at i. */
|
|
Packit Service |
4684c1 |
ecc_mod_add (&ecc->p, i, p + 2*ecc->p.size, q + 2*ecc->p.size);
|
|
Packit Service |
4684c1 |
ecc_mod_sqr (&ecc->p, v, i);
|
|
Packit Service |
4684c1 |
ecc_mod_sub (&ecc->p, v, v, z1z1);
|
|
Packit Service |
4684c1 |
ecc_mod_sub (&ecc->p, v, v, z2z2);
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, i, v, u2);
|
|
Packit Service |
4684c1 |
/* Delayed write, to support in-place operation. */
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* s1 = y1 z2^3, s2 = y2 z1^3, scratch at j and v */
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, j, z1z1, p + 2*ecc->p.size); /* z1^3 */
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, v, z2z2, q + 2*ecc->p.size); /* z2^3 */
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, s1, p + ecc->p.size, v);
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, v, j, q + ecc->p.size);
|
|
Packit Service |
4684c1 |
ecc_mod_sub (&ecc->p, s2, v, s1);
|
|
Packit Service |
4684c1 |
ecc_mod_mul_1 (&ecc->p, s2, s2, 2);
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* Store z3 */
|
|
Packit Service |
4684c1 |
mpn_copyi (r + 2*ecc->p.size, i, ecc->p.size);
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* i, j, v */
|
|
Packit Service |
4684c1 |
ecc_mod_sqr (&ecc->p, i, u2);
|
|
Packit Service |
4684c1 |
ecc_mod_mul_1 (&ecc->p, i, i, 4);
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, j, u2, i);
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, v, u1, i);
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* now, u1, u2 and i are free for reuse .*/
|
|
Packit Service |
4684c1 |
/* x3, use u1, u2 as scratch */
|
|
Packit Service |
4684c1 |
ecc_mod_sqr (&ecc->p, u1, s2);
|
|
Packit Service |
4684c1 |
ecc_mod_sub (&ecc->p, r, u1, j);
|
|
Packit Service |
4684c1 |
ecc_mod_submul_1 (&ecc->p, r, v, 2);
|
|
Packit Service |
4684c1 |
|
|
Packit Service |
4684c1 |
/* y3 */
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, u1, s1, j); /* Frees j */
|
|
Packit Service |
4684c1 |
ecc_mod_sub (&ecc->p, u2, v, r); /* Frees v */
|
|
Packit Service |
4684c1 |
ecc_mod_mul (&ecc->p, i, s2, u2);
|
|
Packit Service |
4684c1 |
ecc_mod_submul_1 (&ecc->p, i, u1, 2);
|
|
Packit Service |
4684c1 |
mpn_copyi (r + ecc->p.size, i, ecc->p.size);
|
|
Packit Service |
4684c1 |
}
|