The Tor Browser / file comparison
comparison: security/nss/lib/freebl/ecl/ecp_mont.c
security/nss/lib/freebl/ecl/ecp_mont.c
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:84baff6a5c9c |
|---|---|
| 1 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 2 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 4 | |
| 5 /* Uses Montgomery reduction for field arithmetic. See mpi/mpmontg.c for | |
| 6 * code implementation. */ | |
| 7 | |
| 8 #include "mpi.h" | |
| 9 #include "mplogic.h" | |
| 10 #include "mpi-priv.h" | |
| 11 #include "ecl-priv.h" | |
| 12 #include "ecp.h" | |
| 13 #include <stdlib.h> | |
| 14 #include <stdio.h> | |
| 15 | |
| 16 /* Construct a generic GFMethod for arithmetic over prime fields with | |
| 17 * irreducible irr. */ | |
| 18 GFMethod * | |
| 19 GFMethod_consGFp_mont(const mp_int *irr) | |
| 20 { | |
| 21 mp_err res = MP_OKAY; | |
| 22 GFMethod *meth = NULL; | |
| 23 mp_mont_modulus *mmm; | |
| 24 | |
| 25 meth = GFMethod_consGFp(irr); | |
| 26 if (meth == NULL) | |
| 27 return NULL; | |
| 28 | |
| 29 mmm = (mp_mont_modulus *) malloc(sizeof(mp_mont_modulus)); | |
| 30 if (mmm == NULL) { | |
| 31 res = MP_MEM; | |
| 32 goto CLEANUP; | |
| 33 } | |
| 34 | |
| 35 meth->field_mul = &ec_GFp_mul_mont; | |
| 36 meth->field_sqr = &ec_GFp_sqr_mont; | |
| 37 meth->field_div = &ec_GFp_div_mont; | |
| 38 meth->field_enc = &ec_GFp_enc_mont; | |
| 39 meth->field_dec = &ec_GFp_dec_mont; | |
| 40 meth->extra1 = mmm; | |
| 41 meth->extra2 = NULL; | |
| 42 meth->extra_free = &ec_GFp_extra_free_mont; | |
| 43 | |
| 44 mmm->N = meth->irr; | |
| 45 mmm->n0prime = 0 - s_mp_invmod_radix(MP_DIGIT(&meth->irr, 0)); | |
| 46 | |
| 47 CLEANUP: | |
| 48 if (res != MP_OKAY) { | |
| 49 GFMethod_free(meth); | |
| 50 return NULL; | |
| 51 } | |
| 52 return meth; | |
| 53 } | |
| 54 | |
| 55 /* Wrapper functions for generic prime field arithmetic. */ | |
| 56 | |
| 57 /* Field multiplication using Montgomery reduction. */ | |
| 58 mp_err | |
| 59 ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r, | |
| 60 const GFMethod *meth) | |
| 61 { | |
| 62 mp_err res = MP_OKAY; | |
| 63 | |
| 64 #ifdef MP_MONT_USE_MP_MUL | |
| 65 /* if MP_MONT_USE_MP_MUL is defined, then the function s_mp_mul_mont | |
| 66 * is not implemented and we have to use mp_mul and s_mp_redc directly | |
| 67 */ | |
| 68 MP_CHECKOK(mp_mul(a, b, r)); | |
| 69 MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1)); | |
| 70 #else | |
| 71 mp_int s; | |
| 72 | |
| 73 MP_DIGITS(&s) = 0; | |
| 74 /* s_mp_mul_mont doesn't allow source and destination to be the same */ | |
| 75 if ((a == r) || (b == r)) { | |
| 76 MP_CHECKOK(mp_init(&s)); | |
| 77 MP_CHECKOK(s_mp_mul_mont | |
| 78 (a, b, &s, (mp_mont_modulus *) meth->extra1)); | |
| 79 MP_CHECKOK(mp_copy(&s, r)); | |
| 80 mp_clear(&s); | |
| 81 } else { | |
| 82 return s_mp_mul_mont(a, b, r, (mp_mont_modulus *) meth->extra1); | |
| 83 } | |
| 84 #endif | |
| 85 CLEANUP: | |
| 86 return res; | |
| 87 } | |
| 88 | |
| 89 /* Field squaring using Montgomery reduction. */ | |
| 90 mp_err | |
| 91 ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth) | |
| 92 { | |
| 93 return ec_GFp_mul_mont(a, a, r, meth); | |
| 94 } | |
| 95 | |
| 96 /* Field division using Montgomery reduction. */ | |
| 97 mp_err | |
| 98 ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r, | |
| 99 const GFMethod *meth) | |
| 100 { | |
| 101 mp_err res = MP_OKAY; | |
| 102 | |
| 103 /* if A=aZ represents a encoded in montgomery coordinates with Z and # | |
| 104 * and \ respectively represent multiplication and division in | |
| 105 * montgomery coordinates, then A\B = (a/b)Z = (A/B)Z and Binv = | |
| 106 * (1/b)Z = (1/B)(Z^2) where B # Binv = Z */ | |
| 107 MP_CHECKOK(ec_GFp_div(a, b, r, meth)); | |
| 108 MP_CHECKOK(ec_GFp_enc_mont(r, r, meth)); | |
| 109 if (a == NULL) { | |
| 110 MP_CHECKOK(ec_GFp_enc_mont(r, r, meth)); | |
| 111 } | |
| 112 CLEANUP: | |
| 113 return res; | |
| 114 } | |
| 115 | |
| 116 /* Encode a field element in Montgomery form. See s_mp_to_mont in | |
| 117 * mpi/mpmontg.c */ | |
| 118 mp_err | |
| 119 ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth) | |
| 120 { | |
| 121 mp_mont_modulus *mmm; | |
| 122 mp_err res = MP_OKAY; | |
| 123 | |
| 124 mmm = (mp_mont_modulus *) meth->extra1; | |
| 125 MP_CHECKOK(mp_copy(a, r)); | |
| 126 MP_CHECKOK(s_mp_lshd(r, MP_USED(&mmm->N))); | |
| 127 MP_CHECKOK(mp_mod(r, &mmm->N, r)); | |
| 128 CLEANUP: | |
| 129 return res; | |
| 130 } | |
| 131 | |
| 132 /* Decode a field element from Montgomery form. */ | |
| 133 mp_err | |
| 134 ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth) | |
| 135 { | |
| 136 mp_err res = MP_OKAY; | |
| 137 | |
| 138 if (a != r) { | |
| 139 MP_CHECKOK(mp_copy(a, r)); | |
| 140 } | |
| 141 MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1)); | |
| 142 CLEANUP: | |
| 143 return res; | |
| 144 } | |
| 145 | |
| 146 /* Free the memory allocated to the extra fields of Montgomery GFMethod | |
| 147 * object. */ | |
| 148 void | |
| 149 ec_GFp_extra_free_mont(GFMethod *meth) | |
| 150 { | |
| 151 if (meth->extra1 != NULL) { | |
| 152 free(meth->extra1); | |
| 153 meth->extra1 = NULL; | |
| 154 } | |
| 155 } |
