← Back to branch summary

~ubuntu-branches/ubuntu/utopic/dropbear/utopic-proposed

« back to all changes in this revision

Viewing changes to libtommath/bn_fast_mp_invmod.c

  • Committer: Bazaar Package Importer
  • Author(s): Matt Johnston
  • Date: 2005-12-08 19:20:21 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051208192021-nyp9rwnt77nsg6ty
Tags: 0.47-1
* New upstream release.
* SECURITY: Fix incorrect buffer sizing.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libtommath/bn_fast_mp_invmod.c
21
21
 * Based on slow invmod except this is optimized for the case where b is 
22
22
 * odd as per HAC Note 14.64 on pp. 610
23
23
 */
24
 
int
25
 
fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
 
24
int fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
26
25
{
27
26
  mp_int  x, y, u, v, B, D;
28
27
  int     res, neg;
39
38
 
40
39
  /* x == modulus, y == value to invert */
41
40
  if ((res = mp_copy (b, &x)) != MP_OKAY) {
42
 
    goto __ERR;
 
41
    goto LBL_ERR;
43
42
  }
44
43
 
45
44
  /* we need y = |a| */
46
 
  if ((res = mp_abs (a, &y)) != MP_OKAY) {
47
 
    goto __ERR;
 
45
  if ((res = mp_mod (a, b, &y)) != MP_OKAY) {
 
46
    goto LBL_ERR;
48
47
  }
49
48
 
50
49
  /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
51
50
  if ((res = mp_copy (&x, &u)) != MP_OKAY) {
52
 
    goto __ERR;
 
51
    goto LBL_ERR;
53
52
  }
54
53
  if ((res = mp_copy (&y, &v)) != MP_OKAY) {
55
 
    goto __ERR;
 
54
    goto LBL_ERR;
56
55
  }
57
56
  mp_set (&D, 1);
58
57
 
61
60
  while (mp_iseven (&u) == 1) {
62
61
    /* 4.1 u = u/2 */
63
62
    if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
64
 
      goto __ERR;
 
63
      goto LBL_ERR;
65
64
    }
66
65
    /* 4.2 if B is odd then */
67
66
    if (mp_isodd (&B) == 1) {
68
67
      if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
69
 
        goto __ERR;
 
68
        goto LBL_ERR;
70
69
      }
71
70
    }
72
71
    /* B = B/2 */
73
72
    if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
74
 
      goto __ERR;
 
73
      goto LBL_ERR;
75
74
    }
76
75
  }
77
76
 
79
78
  while (mp_iseven (&v) == 1) {
80
79
    /* 5.1 v = v/2 */
81
80
    if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
82
 
      goto __ERR;
 
81
      goto LBL_ERR;
83
82
    }
84
83
    /* 5.2 if D is odd then */
85
84
    if (mp_isodd (&D) == 1) {
86
85
      /* D = (D-x)/2 */
87
86
      if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
88
 
        goto __ERR;
 
87
        goto LBL_ERR;
89
88
      }
90
89
    }
91
90
    /* D = D/2 */
92
91
    if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
93
 
      goto __ERR;
 
92
      goto LBL_ERR;
94
93
    }
95
94
  }
96
95
 
98
97
  if (mp_cmp (&u, &v) != MP_LT) {
99
98
    /* u = u - v, B = B - D */
100
99
    if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
101
 
      goto __ERR;
 
100
      goto LBL_ERR;
102
101
    }
103
102
 
104
103
    if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
105
 
      goto __ERR;
 
104
      goto LBL_ERR;
106
105
    }
107
106
  } else {
108
107
    /* v - v - u, D = D - B */
109
108
    if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
110
 
      goto __ERR;
 
109
      goto LBL_ERR;
111
110
    }
112
111
 
113
112
    if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
114
 
      goto __ERR;
 
113
      goto LBL_ERR;
115
114
    }
116
115
  }
117
116
 
125
124
  /* if v != 1 then there is no inverse */
126
125
  if (mp_cmp_d (&v, 1) != MP_EQ) {
127
126
    res = MP_VAL;
128
 
    goto __ERR;
 
127
    goto LBL_ERR;
129
128
  }
130
129
 
131
130
  /* b is now the inverse */
132
131
  neg = a->sign;
133
132
  while (D.sign == MP_NEG) {
134
133
    if ((res = mp_add (&D, b, &D)) != MP_OKAY) {
135
 
      goto __ERR;
 
134
      goto LBL_ERR;
136
135
    }
137
136
  }
138
137
  mp_exch (&D, c);
139
138
  c->sign = neg;
140
139
  res = MP_OKAY;
141
140
 
142
 
__ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL);
 
141
LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL);
143
142
  return res;
144
143
}
145
144
#endif