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