1 /*
2 * Copyright (C) 2017 - This file is part of libecc project
3 *
4 * Authors:
5 * Ryad BENADJILA <ryadbenadjila@gmail.com>
6 * Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
7 * Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
8 *
9 * Contributors:
10 * Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
11 * Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
12 *
13 * This software is licensed under a dual BSD and GPL v2 license.
14 * See LICENSE file at the root folder of the project.
15 */
16 #include <libecc/fp/fp_mul.h>
17 #include <libecc/fp/fp_pow.h>
18 #include <libecc/nn/nn_add.h>
19 #include <libecc/nn/nn_mul_public.h>
20 #include <libecc/nn/nn_modinv.h>
21 /* Include the "internal" header as we use non public API here */
22 #include "../nn/nn_div.h"
23
24 /*
25 * Compute out = in1 * in2 mod p. 'out' parameter must have been initialized
26 * by the caller. Returns 0 on success, -1 on error.
27 *
28 * Aliasing is supported.
29 */
fp_mul(fp_t out,fp_src_t in1,fp_src_t in2)30 int fp_mul(fp_t out, fp_src_t in1, fp_src_t in2)
31 {
32 int ret;
33
34 ret = fp_check_initialized(in1); EG(ret, err);
35 ret = fp_check_initialized(in2); EG(ret, err);
36 ret = fp_check_initialized(out); EG(ret, err);
37
38 MUST_HAVE(out->ctx == in1->ctx, ret, err);
39 MUST_HAVE(out->ctx == in2->ctx, ret, err);
40
41 ret = nn_mul(&(out->fp_val), &(in1->fp_val), &(in2->fp_val)); EG(ret, err);
42 ret = nn_mod_unshifted(&(out->fp_val), &(out->fp_val), &(in1->ctx->p_normalized),
43 in1->ctx->p_reciprocal, in1->ctx->p_shift);
44
45 err:
46 return ret;
47 }
48
49 /*
50 * Compute out = in * in mod p. 'out' parameter must have been initialized
51 * by the caller. Returns 0 on success, -1 on error.
52 *
53 * Aliasing is supported.
54 */
fp_sqr(fp_t out,fp_src_t in)55 int fp_sqr(fp_t out, fp_src_t in)
56 {
57 return fp_mul(out, in, in);
58 }
59
60 /* We use Fermat's little theorem for our inversion in Fp:
61 * x^(p-1) = 1 mod (p) means that x^(p-2) mod(p) is the modular
62 * inverse of x mod (p)
63 *
64 * Aliasing is supported.
65 */
fp_inv(fp_t out,fp_src_t in)66 int fp_inv(fp_t out, fp_src_t in)
67 {
68 /* Use our lower layer Fermat modular inversion with precomputed
69 * Montgomery coefficients.
70 */
71 int ret;
72
73 ret = fp_check_initialized(in); EG(ret, err);
74 ret = fp_check_initialized(out); EG(ret, err);
75
76 MUST_HAVE(out->ctx == in->ctx, ret, err);
77
78 /* We can use the Fermat inversion as p is surely prime here */
79 ret = nn_modinv_fermat_redc(&(out->fp_val), &(in->fp_val), &(in->ctx->p), &(in->ctx->r), &(in->ctx->r_square), in->ctx->mpinv);
80
81 err:
82 return ret;
83 }
84
85 /*
86 * Compute out = w^-1 mod p. 'out' parameter must have been initialized
87 * by the caller. Returns 0 on success, -1 on error.
88 */
fp_inv_word(fp_t out,word_t w)89 int fp_inv_word(fp_t out, word_t w)
90 {
91 int ret;
92
93 ret = fp_check_initialized(out); EG(ret, err);
94
95 ret = nn_modinv_word(&(out->fp_val), w, &(out->ctx->p));
96
97 err:
98 return ret;
99 }
100
101 /*
102 * Compute out such that num = out * den mod p. 'out' parameter must have been initialized
103 * by the caller. Returns 0 on success, -1 on error.
104 *
105 * Aliasing is supported.
106 */
fp_div(fp_t out,fp_src_t num,fp_src_t den)107 int fp_div(fp_t out, fp_src_t num, fp_src_t den)
108 {
109 int ret;
110
111 ret = fp_check_initialized(num); EG(ret, err);
112 ret = fp_check_initialized(den); EG(ret, err);
113 ret = fp_check_initialized(out); EG(ret, err);
114
115 MUST_HAVE(out->ctx == num->ctx, ret, err);
116 MUST_HAVE(out->ctx == den->ctx, ret, err);
117
118 if(out == num){
119 /* Handle aliasing of out and num */
120 fp _num;
121 _num.magic = WORD(0);
122
123 ret = fp_copy(&_num, num); EG(ret, err1);
124 ret = fp_inv(out, den); EG(ret, err1);
125 ret = fp_mul(out, &_num, out);
126
127 err1:
128 fp_uninit(&_num);
129 EG(ret, err);
130 }
131 else{
132 ret = fp_inv(out, den); EG(ret, err);
133 ret = fp_mul(out, num, out);
134 }
135
136 err:
137 return ret;
138 }
139