2 * Copyright (C) 2011-2012 Free Software Foundation, Inc.
4 * This file is part of GNUTLS.
6 * The GNUTLS library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public License
8 * as published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
11 * This library is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>
21 /* Based on public domain code of LibTomCrypt by Tom St Denis.
22 * Adapted to gmp and nettle by Nikos Mavrogiannopoulos.
27 /* size of sliding window, don't change this! */
31 Perform a point multiplication
32 @param k The scalar to multiply by
33 @param G The base point
34 @param R [out] Destination for kG
35 @param modulus The modulus of the field the ECC curve is in
36 @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective)
37 @return CRYPT_OK on success
40 ecc_mulmod (mpz_t k
, ecc_point
* G
, ecc_point
* R
, mpz_t a
, mpz_t modulus
,
45 int i
, j
, err
, bitidx
;
46 int first
, bitbuf
, bitcpy
, mode
;
48 if (k
== NULL
|| G
== NULL
|| R
== NULL
|| modulus
== NULL
)
51 /* alloc ram for window temps */
52 for (i
= 0; i
< 8; i
++) {
53 M
[i
] = ecc_new_point();
55 for (j
= 0; j
< i
; j
++) {
63 /* make a copy of G incase R==G */
71 /* tG = G and convert to montgomery */
72 mpz_set (tG
->x
, G
->x
);
73 mpz_set (tG
->y
, G
->y
);
74 mpz_set (tG
->z
, G
->z
);
76 /* calc the M tab, which holds kG for k==8..15 */
78 if ((err
= ecc_projective_dbl_point (tG
, M
[0], a
, modulus
)) != 0)
81 if ((err
= ecc_projective_dbl_point (M
[0], M
[0], a
, modulus
)) != 0)
84 if ((err
= ecc_projective_dbl_point (M
[0], M
[0], a
, modulus
)) != 0)
87 /* now find (8+k)G for k=1..7 */
88 for (j
= 9; j
< 16; j
++) {
89 if (ecc_projective_add_point(M
[j
-9], tG
, M
[j
-8], a
, modulus
) != 0)
93 /* setup sliding window */
95 bitidx
= mpz_size (k
) * GMP_NUMB_BITS
- 1;
101 /* grab next digit as required */
106 /* grab the next msb from the ltiplicand */
107 i
= mpz_tstbit (k
, bitidx
--);
109 /* skip leading zero bits */
110 if (mode
== 0 && i
== 0) {
114 /* if the bit is zero and mode == 1 then we double */
115 if (mode
== 1 && i
== 0) {
116 if ((err
= ecc_projective_dbl_point(R
, R
, a
, modulus
)) != 0)
121 /* else we add it to the window */
122 bitbuf
|= (i
<< (WINSIZE
- ++bitcpy
));
125 if (bitcpy
== WINSIZE
) {
126 /* if this is the first window we do a simple copy */
128 /* R = kG [k = first window] */
129 mpz_set(R
->x
, M
[bitbuf
-8]->x
);
130 mpz_set(R
->y
, M
[bitbuf
-8]->y
);
131 mpz_set(R
->z
, M
[bitbuf
-8]->z
);
135 /* ok window is filled so double as required and add */
137 for (j
= 0; j
< WINSIZE
; j
++) {
138 if ((err
= ecc_projective_dbl_point(R
, R
, a
, modulus
)) != 0)
142 /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */
143 if ((err
= ecc_projective_add_point(R
, M
[bitbuf
-8], R
, a
, modulus
)) != 0)
146 /* empty window and reset */
152 /* if bits remain then double/add */
153 if (mode
== 2 && bitcpy
> 0) {
154 /* double then add */
155 for (j
= 0; j
< bitcpy
; j
++) {
156 /* only double if we have had at least one add first */
158 if ((err
= ecc_projective_dbl_point(R
, R
, a
, modulus
)) != 0)
163 if ((bitbuf
& (1 << WINSIZE
)) != 0) {
165 /* first add, so copy */
166 mpz_set(R
->x
, tG
->x
);
167 mpz_set(R
->y
, tG
->y
);
168 mpz_set(R
->z
, tG
->z
);
172 if ((err
= ecc_projective_add_point(R
, tG
, R
, a
, modulus
)) != 0)
179 /* map R back from projective space */
181 err
= ecc_map(R
, modulus
);
187 for (i
= 0; i
< 8; i
++) {